Ingeniero en Computación

MATEMÁTICA DISCRETA Y LÓGICA
PRIMERA EDICIÓN
ROBERTO H. FANJUL
ISBN 987-43-9433-1, edición original publicada por
© Roberto H. Fanjul
San Miguel de Tucumán, Argentina

Copyright © 2005 Roberto H. Fanjul
España 2919, (T4001AEG)
San Miguel de Tucumán, Tucumán, Argentina
Todos los derechos reservados

Email: rfanjul@arnet.com.ar

ISBN 987-43-9433-1

Derechos Reservados
Quedanreservados todos los derechos para todos los
países. Esta obra es propiedad intelectual de su autor.
Ninguna parte de esta publicación, incluido el diseño
gráfico de la tapa y de las páginas interiores pueden
ser reproducidas, almacenadas o transmitida de ninguna
forma, por ningún medio, sea este electrónico, mecánico,
grabación, fotocopia, o cualquier medio sin la previa
autorización porescrito del propietario de los derechos
del copyright.

Queda hecho el depósito que previene la ley 11.723

Impreso en Argentina – Printed in Argentina
Septiembre de 2005

MATEMÁTICA DISCRETA Y LÓGICA
CAPITULO I: SINTAXIS Y SEMÁNTICA DEL
LENGUAJE FORMAL
1
1.- LOS ORÍGENES DE LA LÓGICA MATEMÁTICA
1.1.- LENGUAJE FORMAL (SINTAXIS Y SEMÁNTICA)
1.1.1.- ALGUNOS ARGUMENTOS LÓGICOS IMPORTANTES1
3
5

1.2.- MATERIAL SIMBÓLICO O ALFABETO DEL LENGUAJE
1.2.1.- VARIABLES Y CONSTANTES PROPOSICIONALES
1.2.2.- CONECTORES PROPOSICIONALES
1.2.3.- SÍMBOLOS DE PUNTUACIÓN
1.2.4.- REGLAS DE PRIORIDAD

7
7
8
9
10

1.3.- CADENAS DE CARACTERES, LONGITUD, CONCATENACIÓN

11

1.4.- EL LENGUAJE DEL CALCULO DE PROPOSICIONES O CONJUNTO F DE
EXPRESIONES BIEN FORMADAS (EBF)
11
1.4.1.-REGLAS DE BUENA FORMACIÓN 12
1.4.2.- RAZONAMIENTO POR RECURRENCIA SOBRE LA FORMACIÓN
DE LAS EXPRESIONES
13
1.4.3.- NO AMBIGÜEDAD DEL LENGUAJE CONSTRUIDO
13
1.4.4.- DECIDIBILIDAD DEL CONJUNTO F DE LAS EXPRESIONES BIEN
FORMADAS
14
1.5.- CONVENCIONES PARA ABREVIAR LA ESCRITURA

15

1.6.- OPERADORES O CONECTIVOS MONODIADICOS

15

1.7.- OPERADORES O CONECTIVOS DIÁDICOS

15

1.8.-OPERADORES O CONECTIVOS TRIÁDICOS

16

1.9.- NOCIÓN GENERAL DE LA SEMÁNTICA DEL LENGUAJE FORMAL

17

1.10.- DEFINICIÓN ALGEBRAICA DE LA SEMÁNTICA DEL LENGUAJE
PROPOSICIONAL
1.10.1.- DISTRIBUCIÓN DE LOS VALORES DE VERDAD (D.D.V.V.)
1.10.2.- EVALUACIÓN DE LAS EBF

17
17
18

1.11.- TABLAS DE VERDAD

21

1.12.- DEFINICIÓN DE LOS CONECTIVOS LÓGICOS
1.12.1.- FORMULAS PROPOSICIONALES1.12.2.- INTERPRETACIONES BOOLEANAS

23
26
28

1.13.- TAUTOLOGÍA, CONTRADICCIÓN E INDEFINIDOS
1.14.- SATISFACTORIO, VALIDEZ Y CONSECUENCIA
1.15.- LÓGICA TRIVALENTE (LUKASIEWICZ)
1.16.- PROBLEMAS DEL CAPITULO I
I

29
35
36
37

CAPITULO II: DECISIÓN EN EL LENGUAJE
FORMAL
44
2.1.- NOCIÓN GENERAL DE SISTEMAS AXIOMÁTICOS
2.1.1.- PROPIEDADES DE LOS SISTEMAS AXIOMÁTICOS

44
452.2.- LA LÓGICA PROPOSICIONAL COMO UN SISTEMA AXIOMÁTICO
2.2.1.- SISTEMAS GENTZEN
2.2.2.- SISTEMA AXIOMÁTICO DE RUSSEL
2.2.3.- SISTEMA AXIOMÁTICO DE HILBERT

45
46
48
49

2.3.- NOCIÓN GENERAL DE LA DECISIÓN EN EL LENGUAJE FORMAL

51

2.4.- LA DECISIÓN POR LAS FORMAS NORMALES
2.4.1.- LA TRANSFORMACIÓN DE UNA EBF EN FORMA NORMAL
2.4.2.- INTERPRETACIÓN DE LAS FORMAS NORMALES YDECISIÓN

51
52
53

2.5.- ENUNCIADOS Y FORMAS DE ENUNCIADOS

58

2.6.- EL RAZONAMIENTO
2.6.1.- FORMAS DE RAZONAMIENTO Y FORMAS DE ENUNCIADOS
2.6.2.- LA DECISIÓN EN EL RAZONAMIENTO

59
62
65

2.7.- LAS IMPLICACIONES Y DERIVACIONES LÓGICAS
2.7.1- IMPLICACIONES LÓGICAS
2.7.2.- SISTEMAS PARA DERIVACIONES
2.7.3.- TEOREMA DE LA DEDUCCIÓN

66
66
68
69

2.8.- LA DECISIÓN POR CUADROSEMÁNTICO
2.9.- PROBLEMAS CAPITULO II

71
76

CAPITULO III: LÓGICA DE PREDICADOS

80

3.1.- INTRODUCCIÓN
80
3.1.1.- REGLAS DE INFERENCIA
80
3.1.2.- LA LÓGICA TIENE NOTACIÓN TRADICIONAL
81
3.1.3.- CUANTIFICADORES DETERMINAN QUE ELEMENTOS SON CIERTOS 83
3.1.4.- VOCABULARIO DE LA LÓGICA DE PREDICADO
84
3.2.- ESTRUCTURA RELACIONAL DE UNA LÓGICA DE PREDICADO
3.2.1.- RELACIONES Y...