Cartilla Herramientas de Lógica Computacional

Sandor Ortegón Pineda

Politécnico Grancolombiano
Enero de 2011
 Índice general

Introducción 5

1. Introducción a la lógica simbólica: Expresiones booleanas 7

1.1. Sintaxis y evaluación de expresiones booleanas . . . . . . . . . . . . . . . . 7
1.1.1. Operadores unarios . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.2. Operadores binarios . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.3. Descripción de los principales conectivos binarios . . . . . . . . . . 9
1.2. Proposiciones y traducción de textos en lenguaje natural . . . . . . . . . . 10
1.2.1. Lectura de Negación, conjunción y disyunción . . . . . . . . . . . . 11
1.2.2. Lectura de Implicación y Equivalencia . . . . . . . . . . . . . . . . 12
1.2.3. Condiciones necesarias y suficientes . . . . . . . . . . . . . . . . . . 14
1.2.4. La equivalencia en el lenguaje natural . . . . . . . . . . . . . . . . . 14
1.2.5. Reglas de precedencia entre conectivos . . . . . . . . . . . . . . . . 15
1.3. Uso de Tablas de verdad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.4. Diferencias entre igualdad y equivalencia . . . . . . . . . . . . . . . . . . . 17
1.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2. Validez de expresiones booleanas y simbolización de argumentos 23

2.1. Satisfabilidad y validez . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2. Análisis de Razonamientos . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3. Validez de razonamientos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4. El método de forzamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.1. Un primer ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4.2. Un segundo ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.5. Ejercicios de simbolización con ayudas (para practicar) . . . . . . . . . . . 32
2.6. Ayudas en los ejercicios anteriores de simbolización . . . . . . . . . . . . . 33
2.7. Ejercicios (sin ayudas) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3. Preliminares al cálculo proposicional 39

3.1. Expresiones aritméticas y notación de sustitución textual . . . . . . . . . . 39

1
Cartilla Herramientas de Lógica Computacional

3.2. Sustitución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3. Sustitución y variables ocultas . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.4. La sustitución como regla de inferencia . . . . . . . . . . . . . . . . . . . . 43
3.5. Igualdad y sustitución. Regla de Leibniz . . . . . . . . . . . . . . . . . . . 44
3.6. Sistemas deductivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.6.1. El sistema deductivo que usaremos en nuestro curso . . . . . . . . . 47
3.7. Propiedades a evaluar en los conectivos lógicos . . . . . . . . . . . . . . . . 49
3.7.1. Asociatividad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.7.2. Conmutatividad (Simetrı́a) . . . . . . . . . . . . . . . . . . . . . . . 49
3.7.3. Reflexividad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.7.4. Distributividad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.7.5. Identidad (o elemento neutro) . . . . . . . . . . . . . . . . . . . . . 51
3.7.6. Elemento absorvente (cero) . . . . . . . . . . . . . . . . . . . . . . 52
3.8. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4. Axiomas y Teoremas de Cálculo Proposicional 55

4.1. Axiomas sobre la equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2. Esquema de demostración en cálculo proposicional . . . . . . . . . . . . . . 56
4.3. La negación, discrepancia (no equivalencia), y false . . . . . . . . . . . . . 58
4.4. Heurı́sticas y técnicas de demostración . . . . . . . . . . . . . . . . . . . . 59
4.5. La disyunción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.6. La conjunción y la Regla de Oro . . . . . . . . . . . . . . . . . . . . . . . . 63
4.7. Usos de la Regla de Oro . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.8. Usando lemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.9. La implicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.10. Prueba de teoremas en donde participa la implicación . . . . . . . . . . . . 70
4.11. Aplicación: Propiedades de Distributividad . . . . . . . . . . . . . . . . . . 71
4.12. Dualidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.13. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

5. Métodos de Demostración 85
5.1. Forma abreviada en la prueba de implicaciones . . . . . . . . . . . . . . . . 85

2
Cartilla Herramientas de Lógica Computacional

5.2. Suponiendo el antecedente . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

5.3. Analizando razonamientos en lenguaje corriente . . . . . . . . . . . . . . . 88
5.4. Construyendo contraejemplos . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.5. Un acertijo lógico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.5.1. Un pequeño ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.6. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

6. Expresiones cuantificadas y lenguaje de predicados 97

6.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.2. Tipos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.3. Predicados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.4. Sintaxis e interpretación de la cuantificación . . . . . . . . . . . . . . . . . 99
6.5. Los primeros ejemplos de traducción . . . . . . . . . . . . . . . . . . . . . 101
6.6. Lectura de expresiones cuantificadas . . . . . . . . . . . . . . . . . . . . . 102
6.7. Traducción de expresiones aritméticas . . . . . . . . . . . . . . . . . . . . . 102
6.8. Traducción de textos en lenguaje natural . . . . . . . . . . . . . . . . . . . 104
6.9. Teoremas matemáticos en lenguaje de predicados . . . . . . . . . . . . . . 106
6.10. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

7. Manejo de Expresiones Cuantificadas 113

7.1. Variables libres y ligadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
7.2. Reglas generales para expresiones cuantificadas . . . . . . . . . . . . . . . 114
7.3. Ejemplos de Cálculo de Expresiones Cuantificadas . . . . . . . . . . . . . . 117
7.4. Uso de Axiomas Generales de Cuantificación . . . . . . . . . . . . . . . . . 118
7.5. Casos especiales de cuantificadores . . . . . . . . . . . . . . . . . . . . . . 120
7.5.1. Máximos y mı́nimos . . . . . . . . . . . . . . . . . . . . . . . . . . 120
7.5.2. Operador de conteo . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
7.6. Sustitución en expresiones cuantificadas . . . . . . . . . . . . . . . . . . . . 122
7.7. Ejemplos de sustitución en expresiones cuantificadas . . . . . . . . . . . . . 123
7.8. Cálculo de predicados: El cuantificador universal . . . . . . . . . . . . . . . 124
7.8.1. Traslación con el operador universal . . . . . . . . . . . . . . . . . . 125
7.8.2. Distributividad con el cuantificador universal . . . . . . . . . . . . . 126

3
Cartilla Herramientas de Lógica Computacional

7.8.3. Manipulación de rango y término con el cuantificador universal . . 127

7.8.4. Instanciación con el cuantificador universal . . . . . . . . . . . . . . 128
7.8.5. Teoremas y el cuantificador universal . . . . . . . . . . . . . . . . . 129
7.9. Cálculo de predicados: El cuantificador existencial . . . . . . . . . . . . . . 130
7.9.1. Traslación en la cuantificación existencial . . . . . . . . . . . . . . . 132
7.9.2. Distributividad en la cuantificación existencial . . . . . . . . . . . . 133
7.9.3. Manipulación de rango y término con el cuantificador existencial . . 133
7.9.4. Introducción del operador existencial e intercambio . . . . . . . . . 134
7.9.5. Testigo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7.10. Un ejemplo matemático: Continuidad . . . . . . . . . . . . . . . . . . . . . 136
7.11. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

8. Nociones básicas de conjuntos 143

8.0.1. Conjunto universal . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
8.0.2. Pertenencia e igualdad de conjuntos . . . . . . . . . . . . . . . . . . 144
8.0.3. Conjuntos y predicados . . . . . . . . . . . . . . . . . . . . . . . . . 147
8.0.4. Cardinalidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
8.0.5. Operaciones entre conjuntos . . . . . . . . . . . . . . . . . . . . . . 150
8.0.6. Subconjunto y Superconjunto . . . . . . . . . . . . . . . . . . . . . 153
8.0.7. Conjunto potencia . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
8.0.8. Teoremas de Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . 153
8.0.9. Unión e intersección de familias de conjuntos . . . . . . . . . . . . . 156
8.1. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156

Bibliografı́a 159

4
 Introducción

Este libro constituye una introducción a los conceptos formales que cimientan la ela-
boración de demostraciones matemáticas. Con una frase tan corta como la anterior, se
pretende indicar que se describen técnicas y conceptos fundamentales que facilitarán la
formalización de argumentos y el entrenamiento en razonamiento deductivo.

El párrafo anterior puede corresponder a la introducción de una gran variedad de textos

de matemáticas. Por tanto, la primera pregunta que puede hacerse el lector es si existe
un elemento diferenciador de este libro respecto de otros existentes en el mercado. Para
responder a dicha pregunta, en esta introducción se quiere indicar las aplicaciones de los
contenidos que se verán, las motivaciones para escribir este documento y las caracterı́sticas
de la audiencia esperada para el mismo.

La segunda mitad del siglo XX significó entre otras cosas, un periodo de tiempo donde
la computación y las tecnologı́as de información ocuparon un papel preponderante, que
muy seguramente no tendrá marcha atrás. Con ello, se estableció la Ciencia de la Compu-
tación como disciplina académica, entendiendo por esta el conjunto de bases teóricas de la
computación y los sistemas computacionales. Y en esta área, el papel principal lo han ocu-
pado ciertas ramas de las matemáticas donde no tienen cabida nociones de “cercanı́a”,
“suavidad” o “continuidad” que son claves en el estudio del Cálculo Infinitesimal y el
Análisis Matemático. Estas ramas constituyen lo que hoy en dı́a se agrupa bajo el nombre
de Matemáticas Discretas y en la actualidad se considera que una formación adecuada
en matemáticas discretas es indispensable para cualquier matemático y para cualquier
estudioso de las ciencias de la computación.

Desde un punto de vista pedagógico, la pregunta fundamental es la siguiente: ¿Donde

inicia el estudio de las Matemáticas Discretas? La respuesta actual es que inicia justo
donde inicia el estudio de las matemáticas en general. Es decir, en el manejo básico
de sistemas numéricos, el conocimiento de la notación que permita expresar ideas en
lenguaje matemático y la comprensión de conceptos matemáticos que permitan realizar
justificaciones formales.

Entre estos tres aspectos mencionados en el párrafo anterior, los dos primeros consti-
tuyen la mayor parte de la formación matemática en la enseñanza primaria y secun-
daria. El tercero constituye el aspecto menos explorado y en el cual la formación de
muchos estudiantes es bastante . Debido a esto, las instituciones de enseñanza supe-
rior han diseñado cursos para suplir llenar estas carencias, de acuerdo a la carrera o
especialidad escogida por el estudiante. El común denominador de los mismos reside
en estudiar fundamentos de lógica formal (como bibliografı́a, podemos citar los libros
[Fer90, Góm98, Bal00, Ari09, Gri94, Gri98]).

5
Cartilla Herramientas de Lógica Computacional

6
Capı́tulo 1: Introducción a la lógica simbólica: Expresiones booleanas

La lógica simbólica surgió como una manera de analizar los razonamientos escritos en
lenguaje natural. Los operadores que se describirán en este capı́tulo fueron pensados
como contrapartidas formales de operadores del lenguaje. Si se tiene cierto cuidado puede
traducirse una proposición escrita en lenguaje natural en una expresión booleana.
Esta traducción nos permitirá dos cosas: por un lado resolver ambiguedades del lenguaje
natural, por otro manipular y analizar las expresiones booleanas ası́ obtenidas usando
reglas que serán introducidas en el próximo capı́tulo. Como veremos luego, las reglas
lógicas ofrecen una alternativa efectiva para razonamientos expresados en el lenguaje
corriente.
En este capı́tulo trabajaremos sobre las expresiones booleanas, cuyo nombre se debe a
George Boole (1815–1864), quien describió gran parte del material que veremos en los
primeros dos capı́tulos en su clásico libro The laws of thought (“Las leyes del pensamien-
to”) escrito en el siglo XIX. Podrı́amos considerar dicho libro como la primera referencia
escrita de la lógica simbólica y la aproximación de usar reglas de cálculo para determinar
la validez de argumentos lógicos. Es de mencionar que no hacemos mención histórica de la
aproximación a la lógica y el razonamiento usados en la Edad Antigua y la Edad Media;
el lector interesado en datos históricos adicionales y diversos enfoques puede consultar
textos como [Ari09] y [EJF03].
Las expresiones booleanas son utilizadas con frecuencia en distintos lenguajes de progra-
mación, por lo tanto el material de éste capı́tulo será familiar para aquellos que tengan
alguna noción de Pascal, C, Java o algún otro lenguaje. Veremos cómo expresar frases en
español a través de expresiones booleanas.

Sección 1.1: Sintaxis y evaluación de expresiones booleanas

El proceso de construcción de expresiones booleanas es análogo al que se ha trabajado

en el colegio para obtener expresiones aritméticas, nada más que es necesario sustituir en
la construcción las constantes aritméticas por las constantes True y False (constantes
booleanas), las variables aritméticas por variables booleanas, (aquellas que asumen sólo los
valores true o false) y los operadores aritméticos +, −, · y / por los operadores booleanos
≡, 6≡, ∧, ∨, ⇒ y ⇐, que serán introducidos más adelante.
Los operadores lógicos actúan sobre constantes o variables booleanas, de manera que re-
ciben variables booleanas como parámetros y sólo asumen los valores true o false. Pueden
enumerarse los distintos operadores observando para ello los valores que toman de acuerdo
a cada posible combinación de los valores de sus argumentos. Nos interesará fundamen-
talmente conocer sobre los operadores unarios y binarios (es decir, que reciben uno o dos

7
Cartilla Herramientas de Lógica Computacional Sintaxis y evaluación de expresiones booleanas

parámetros), pues todos los demás se pueden expresar a partir de estos.

1.1.1: Operadores unarios

Comenzaremos describiendo los operadores unarios, es decir aquellos que actúan sobre
un operando solamente. Una forma de hacer esto es enumerando todas las funciones del
conjunto {True, False} en el conjunto {True, False}. Aquellas funciones que asumen
valores en el conjunto {True, False} se conocen como funciones booleanas.
Si consideramos las funciones booleanas de un argumento definidas sobre el conjunto
{True, False}, entonces tenemos un total de cuatro funciones como aparecen en la si-
guiente tabla. Hay dos que aparecen “sin nombre”; aunque estas podrán expresarse en
términos de las que si tienen nombre (¿ Cómo?).

Posibles valores de verdad id ¬

True True True False False
False True False True False

La tabla anterior es conocida como Tabla de verdad. Las entradas en la tabla de verdad
tienen el significado siguiente: si p es una variable booleana, la primer columna se reserva
para p y sus distintos estados, mientras que en cada una de las siguientes aparece el
resultado de la aplicación de cada función sobre cada uno de los estados. Por ejemplo, en
la segunda columna de la derecha vemos que id(True) = True y id(False) = False, esta
función recibe el nombre de función idéntica o también identidad. También observamos
en la primera y la última columna dos funciones constantes que no tienen asignado un
nombre especı́fico. La función simbolizada con ¬ se llama negación y corresponde al
operador unario not, por ejemplo notaremos ¬False = True.

1.1.2: Operadores binarios

Si ahora consideramos todas las funciones booleanas de dos argumentos, es decir definidas
sobre el conjunto

{(True, True) , (True, False) , (False, True) , (False, False)} ,

se obtienen dieciseis posibles funciones. Para representarlas en una tabla, se puede abreviar
True con el número 1 y False con el número 0. Dependiendo del texto que se use, a veces
se usa esta convención o simplemente se escriben las letras V,F (o T,F según el idioma).
A continuación mostramos las tablas de los 16 operadores booleanos. Las dos primeras
columnas representan las combinaciones de valores que pueden tomar dos variables boo-
leanas. Por ejemplo, la primera fila, al indicar un 1 1, se está contemplando el caso donde
la primera variable vale 1 (True) y la segunda variable vale 0 (False). En las columnas
donde el nombre de los operadores es conocido, colocamos el sı́mbolo que corresponde;

8
Cartilla Herramientas de Lógica Computacional Sintaxis y evaluación de expresiones booleanas

cuando hay mas de una alternativa de sı́mbolo para un operador particular, se indica
arriba una alternativa.
A nivel de escritura por ejemplo, si se tuviera una variable booleana b y otra c que
representan las dos primeras columnas, la aplicación de las funciones correspondientes a
la segunda y tercer columna a la derecha (después de la división) se denota b ∨ c y b ⇐ c,
respectivamente.
En el siguiente apartado se describen esas funciones y en próximas secciones se indicará su
significado, se mostrarán textos de la vida cotideana donde dichos operadores aparecen y
se hablará de sus propiedades a nivel sintáctico.

⇔ xor
= 6=
∨ ⇐ ⇒ ≡ ∧ nand 6≡ nor
1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0
0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0
0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

1.1.3: Descripción de los principales conectivos binarios

A continuación daremos un detalle de cada uno de los conectivos binarios más conocidos.

1. El operador ≡ es la igualdad habitual. La expresión b = c se lee “b es igual a c”.

Al operador booleano igualdad también se le da el nombre de equivalencia y se lo
nota con un segundo sı́mbolo, ≡. La expresión b ≡ c se lee “b es equivalente a c”,
también se dice que los operandos b y c son equivalentes.

2. El operador 6≡ es la “no-equivalencia”. La expresión b 6= c se lee “b es distinto de c”.

El operador 6≡ satisface (b 6= c) = ¬ (b = c). A este operador booleano también se
le da el nombre de discrepancia y se lo nota con un segundo sı́mbolo, 6≡. Se lo suele
llamar también disyunción exclusiva u operador xor , dado que resulta verdadero
cuando exactamente uno de los dos operandos lo es.

3. El operador ∨ es llamado disyunción. La expresión b ∨ c se lee “b o c” dado que el

resultado es verdadero cuando al menos uno de los operandos lo es.

4. El operador ∧ es llamado conjunción. La expresión b ∧ c se lee “b y c”, dado que el

resultado es verdadero cuando ambos operandos lo son.

5. El operador ⇒ es llamado implicancia. La expresión b ⇒ c se lee “b implica c” o

bien “si b entonces c”. El primer operando b, es llamado antecedente y el segundo c,
consecuente. b ⇒ c será verdadera en todos los casos excepto cuando b sea verdadera
y c falsa. En la tabla de verdad se observa un resultado poco intuitivo, y es que si el

9
 Cartilla Herramientas de Lógica Computacional Proposiciones y traducción de textos en lenguaje nat

antecedente es falso, el resultado de la expresión b ⇒ c será verdadero, sin importar

el valor del consecuente.
Hay una historia particular al respecto, que sucedió a comienzos del siglo XX y que
es atribuida al matemático inglés Godfrey Harold Hardy: Resulta que en alguna
ocasión estaba dando una charla sobre el tema y fué interrumpido por una persona
que de manera despectiva le dijo: “Umm, o sea que si 2 + 2 = 5, entonces yo soy el
papa”.
Hardy muy calmado, no se dejó intimidar y respondió: Si, en efecto esta implicación
es cierta; para que no quedaran dudas, dió la siguiente justificación a la persona en
cuestión: “Si 2 + 2 = 5, entonces entonces estará de acuerdo que si restamos 2 de
cada lado obtenemos 2 = 3. Invirtiendo la igualdad y restando 1 de cada lado, da 2
= 1. Como el Papa y usted son dos personas y sabemos que 2 es igual a 1, entonces
el Papa y usted son uno; luego usted es el Papa”. Enseguida, recibió un gran aplauso
de parte de los presentes.
6. El operador ⇐ es llamado consecuencia. La expresión b ⇐ c se lee “b sigue de
c”. En la tabla de verdad se puede ver que son equivalentes c ⇒ b y b ⇐ c. Se
introduce en nuestras expresiones debido a su utilidad en el proceso de construcción
de demostraciones.
7. Los nombres de los operadores “nand” y “nor” siguen de “not and”(no y) y “not
or”( no o) en inglés respectivamente. La expresion b nand c es igual a ¬ (b ∧ c),
mientras que b nor c es igual a ¬ (b ∨ c).

Sección 1.2: Proposiciones y traducción de textos en lenguaje natural

Vamos a presentar ahora cierta terminologı́a que se utilizará en lógica simbólica.

Una proposición es una frase o expresión que sólo puede ser verdadera o falsa. En esto
las proposiciones se diferencian de otras frases o expresiones como las exclamaciones,
las preguntas o las órdenes. También es necesario diferenciarlas de las oraciones aunque
éstas bien pueden ser verdaderas o falsas. Dos oraciones pueden ser diferentes por estar
compuestas de diferentes palabras o éstas pueden estar dispuestas de formas distintas,
pero si expresan el mismo significado, constituyen la misma proposición, por ejemplo:

Juan ama a Marı́a.

Ama Juan a Marı́a.

Es claro, que se trata de dos oraciones diferentes, pero ambas tienen el mismo significado,
por lo tanto lo que ellas afirman es considerado una proposición.

10
Cartilla Herramientas de Lógica Computacional Proposiciones y traducción de textos en lenguaje nat

La idea básica de traducción consiste en identificar las proposiciones elementales de un

enunciado que serán representadas mediante variables booleanas y componerlas usando los
operadores booleanos asociados a los conectivos del lenguaje que aparecen en el enunciado.
Los conectivos del lenguaje serán traducidos a su interpretación “obvia”, aunque veremos
algunas sutilezas de esta traducción.
Por ejemplo, la oración
Hamlet defendió el honor de su padre pero no defendió la felicidad de su madre
ni la suya propia
puede analizarse como compuesta básicamente de tres proposiciones elementales
p : Hamlet defendió el honor de su padre
q : Hamlet defendió la felicidad de su madre
r : Hamlet defendió su propia felicidad
usando esta variables proposicionales la frase anterior puede traducirse como
p ∧ ¬ (q ∨ r)

1.1 Observación. La palabra “pero” se traduce como una conjunción, puesto que afir-
ma ambas componentes. Por otro lado la disyunción usada es inclusiva, ya que podrı́a
haber defendido la felicidad de su madre la propia o ambas.

1.2.1: Lectura de Negación, conjunción y disyunción

La operación de negación aparece usualmente en el lenguaje insertando un “no” en la

posición correcta del enunciado que se quiere negar, alternativamente puede anteponerse
la frase “es falso que” o la frase “no se da el caso que”. Por ejemplo el enunciado:
Todos los unicornios son azules (1.1)
puede negarse de las siguientes maneras:
No todos los unicornios son azules
No se da el caso de que todos los unicornios son azules
Es falso que todos los unicornios sean azules
Algunos unicornios no son azules
si simbolizamos con p a la proposición (1.1), cualquiera de las variantes de negación
propuestas se simbolizan mediante el operador lógico de negación y se expresan ¬p.
La conjunción aparece en el lenguaje con la palabra “y”, uniendo dos proposiciones.
También se interpretarán como conjunción las palabres “pero” y “aunque”. Por ejemplo,
si con p y q representamos las proposiciones siguientes:
p : Llueve
q : No hace frı́o

11
 Cartilla Herramientas de Lógica Computacional Proposiciones y traducción de textos en lenguaje nat

las siguientes oraciones representan la proposición p ∧ q

Llueve y no hace frı́o

Llueve aunque no hace frı́o
Llueve pero no hace frı́o

Es importante notar que no siempre la palabra “y” representa una conjunción, como es
el caso de la siguiente frase:

Joyce y Picasso fueron contemporáneos

aquı́ la palabra “y” se usa para expresar una relación entre Joyce y Picasso.
La palabra usual que corresponde a la disyunción es “o”, también la variante “o bien”.
El caso de la disyunción es más complejo que los anteriores, dado que existen en el
lenguaje dos tipos de disyunciones, la llamada inclusiva y la exclusiva. Básicamente ambos
tipos difieren cuando las proposiciones intervinientes son ambas verdaderas. La disyunción
inclusiva considera a este caso como verdadero. Por ejemplo:

Para ser emperador hay que tener el apoyo de la nobleza o del pueblo

obviamente teniendo el apoyo de ambos se está también en condiciones de ser emperador.

Esta proposición la expresamos como p ∨ q , donde p y q son las siguientes proposiciones
elementales:
p : Para ser emperador hay que tener el apoyo de la nobleza
q : Para ser emperador hay que tener el apoyo del pueblo

Un ejemplo de disyunción exclusiva es:

El consejero del emperador pertenece a la nobleza o al pueblo (1.2)

donde se interpreta que el consejero no puede pertenecer simultáneamente a las dos clase
sociales. Utilizaremos para este caso el operador discrepancia que simbolizamos como 6≡,
por tanto si llamamos

p : El consejero del emperador pertenece a la nobleza

q : El consejero del emperador pertenece al pueblo

la proposición (1.2) se expresa ası́ : p 6≡ q.

1.2.2: Lectura de Implicación y Equivalencia

La implicación lógica suele representar lo que en el lenguaje natural se expresa mediante la

construcción si . . . entonces . . . . Este es uno de los conectivos sobre los que menos acuerdo
existe y al que más alternativas se han propuesto. Casi todo el mundo acuerda que si

12
Cartilla Herramientas de Lógica Computacional Proposiciones y traducción de textos en lenguaje nat

el antecedente p es verdadero y el consecuente q es falso, entonces p ⇒ q es falso. Por

ejemplo, en la frase

Si se reforman las leyes laborales entonces bajará el desempleo (1.3)

aparecen dos proposiciones elementales

p : Se reforman las leyes laborales
q : Baja el desempleo
Supongamos que las leyes laborales se reforman y no baja el desempleo, entonces la
proposición (1.3) que se expresa como p ⇒ q resulta falsa.
Sin embargo, existen ciertas dudas acerca del valor de verdad (o del significado lógico) de
frases como aquella mencionada en el capı́tulo anterior:

Si dos más dos es cinco, entonces yo soy el Papa

Para la lógica clásica que presentamos aquı́, la frase anterior es verdadera (mirando la
tabla de verdad del operador ⇒), pues ambos antecedente y consecuente son falsos, lo
cual hace verdadera a la proposición.
Normalmente se usa una implicación con un consecuente falso como una manera de negar
el antecedente. Por ejemplo, decir

Si la economı́a mejoró con esos ajustes, yo soy el rey del mundo

es una manera sarcástica de decir que la economı́a no mejoró con los ajustes.
Veamos este ejemplo:

Si Juan no toma la sopa, estará en problemas

usando las variables p y q del siguiente modo

p : Juan toma la sopa
q : Juan estará en problemas
la frase anterior puede traducirse como ¬p ⇒ q. Observemos que esta expresión es ver-
dadera si Juan toma la sopa, pues en ese caso ¬p es falsa y por ende resulta ¬p ⇒ q
verdadera. Este hecho puede parecer extraño en un principio pero las frases
Si Juan toma la sopa, estará en problemas
Juan toma la sopa o estará en problemas
tienen el mismo significado. Por lo tanto, como la segunda frase es verdadera si Juan toma
la sopa, la primera también debe serlo. La equivalencia entre las expresiones ¬p ⇒ q y
p ∨ q se verá en el próximo capı́tulo, pero puede deducirse ahora utilizando tablas de
verdad.

13
Cartilla Herramientas de Lógica Computacional Proposiciones y traducción de textos en lenguaje nat

1.2.3: Condiciones necesarias y suficientes

Otra forma de representar la implicación en el lenguaje natural es a través de las palabras

suficiente y necesario.

Es suficiente que vacune a mi hijo para que no contraiga el sarampión (1.4)

Esta frase puede simbolizarse mediante p ⇒ (¬q) donde

p : Vacuno a mi hijo
q : Mi hijo contrae el sarampión

La proposición (1.4) asegura que vacunar es condición suficiente para no contraer el sa-
rampión, nada dice acerca de aquellos niños que no son vacunados
Otro ejemplo donde aparece la idea de necesidad lógica es:

Para que Juan crezca sano, es necesario que tome la sopa (1.5)

que puede simbolizarse ası́ q ⇒ p o también p ⇐ q, donde

p : Juan toma la sopa

q : Juan crece sano.

La proposición (1.5) establece que tomar la sopa es condición necesaria para que Juan
crezca sano, pero no garantiza que si Juan se toma la sopa crecerá sano. Si formulamos
esta proposición en términos de si . . . entonces. . . , resulta

Si Juan crece sano entonces Juan se tomó la sopa.

1.2.4: La equivalencia en el lenguaje natural

Es un error común interpretar la estructura si . . . entonces . . . en lenguaje natural como

si y sólo si que corresponde a una equivalencia y no a una implicación. Por ejemplo la
frase
f es biyectiva si y sólo si f es inyectiva y sobreyectiva
puede expresarse como p ≡ q ∧ r, donde

p : f es biyectiva
q : f es inyectiva
r : f es sobreyectiva

De todos modos no existe ninguna construcción en el lenguaje corriente que represente

fielmente a la equivalencia lógica. Es ésta la razón quizá por la cual la equivalencia suele

14
Cartilla Herramientas de Lógica Computacional Proposiciones y traducción de textos en lenguaje nat

tener un lugar secundario en los libros de lógica. Nosotros no seguiremos esa tradición,
dado que el uso de la lógica en el desarrollo de programas, la equivalencia tiene un rol
fundamental. Como último ejemplo de la inadecuación del lenguaje para parafrasear la
equivalencia, presentamos la frase (verdadera en lenguaje corriente) acerca de las capaci-
dades de Juan.

Juan ve bien si y sólo si Juan es tuerto si y sólo si Juan es ciego

La equivalencia es una operación asociativa (en el capı́tulo 4 se aclarará el significado de

esta propiedad); a grandes rasgos, significa que al escribir la frase anterior como p ≡ q ≡ r
(siendo p, q y r las proposiciones elementales obvias en la frase), cualquiera de las formas
de calcular la expresión parentizando, bien sea (p ≡ q) ≡ r o p ≡ (q ≡ r) produce la
misma respuesta. La siguiente es la tabla de verdad:
p q r p≡q (p ≡ q) ≡ r
1 1 1 1 1
1 1 0 1 0
1 0 1 0 1
1 0 0 0 1
0 1 1 0 0
0 1 0 0 1
0 0 1 1 1
0 0 0 1 0

Observemos que exactamente una de las tres proposiciones p, q y r es verdadera. En la

tabla de verdad, en las filas en donde exactamente una de las proposiciones toma el valor
True, el valor de la expresión booleana p ≡ q ≡ r es también True.

1.2.5: Reglas de precedencia entre conectivos

Una vez presentados todos los operadores lógicos, se tienen unas reglas de precedencia en-
tre ellos, lo cual permitirá eliminar algunos paréntesis en expresiones booleanas y abreviar
ası́ la escritura:

1.2 Definición. Los operadores lógicos tendrán la precedencia que se indica a conti-
nuación, los números señalan la jerarquı́a entre ellos, el primero corresponde a la más
alta, y los siguientes siguen en orden. Cuando dos operadores aparezcan con el mismo
orden de jerarquı́a significa que tienen la misma precedencia respecto de los demás:

1. operador =

2. operador ¬

3. operadores ∧ y ∨

15
Cartilla Herramientas de Lógica Computacional Uso de Tablas de verdad

4. operadores ⇒y ⇐
5. operadores ≡ y 6≡

1.3 Ejemplo. La expresión

((p ∨ q) ⇒ r) ≡ ((p ⇒ r) ∧ (q ⇒ r))
puede simplificarse usando las reglas de precedencia anteriores ası́:
p∨q ⇒r ≡p⇒r∧q ⇒r

Sección 1.3: Uso de Tablas de verdad

Las tablas de verdad serán útiles entre otras cosas para evaluar expresiones booleanas en
cualquier estado. Por ejemplo, la evaluación de la expresión
p ∧ ¬q ⇒ ¬p
en el estado {(p, True) , (q, True)} se calcula ası́: si q es verdadera, de acuerdo a la tabla
del operador ¬, ¬q es falsa, admás cuando uno de los argumentos es falso (en este caso ¬q),
el resultado de la aplicación del operador ∧, es falso. Por último, la columna de la tabla
correspondiente al operador ⇒, nos dice que si el primer argumento es falso, el resultado
es verdadero independientemente del valor del segundo argumento. Observemos que las
operaciones fueron realizadas de acuerdo a las reglas de precedencia citadas anteriormente.
Veamos ahora como evaluar una expresión booleana cualquiera utilizando tablas de ver-
dad. Los posibles valores de las variables booleanas involucradas en la expresión se dis-
ponen en las primeras columnas de la tabla, mientras que en las siguientes columnas se
colocan los valores parciales de los operadores lógicos intervinientes, en orden y de acuerdo
a las reglas de precedencia, hasta colocar en la última columna de la tabla los valores de
verdad asociados a la expresión. Cada fila describe un estado particular de las variables
y la correspondiente evaluación de acuerdo a cada operador en la expresión.
Por ejemplo, queremos evaluar la expresión p∧¬q ⇒ r en todas las combinaciones posibles
de valores de las variables p, q y r, entonces construimos:
p q r ¬q p ∧ ¬q p ∧ ¬q ⇒ r
1 1 1 0 0 1
1 1 0 0 0 1
1 0 1 1 1 1
1 0 0 1 1 0
0 1 1 0 0 1
0 1 0 0 0 1
0 0 1 1 0 1
0 0 0 1 0 1

16
Cartilla Herramientas de Lógica Computacional Diferencias entre igualdad y equivalencia

Una alternativa más simplificada de tabla de verdad (que se puede usar cuando la expre-
sión es muy grande) consiste en colocar debajo de los conectivos el valor de verdad de
la frase que hasta el momento evalúa dicho conectivo. Por ejemplo, si la expresión fuera
(p ∧ ¬q) ⇒ r escribimos en una sola columna dicha expresión, escribiendo debajo de ∧
el valor de p ∧ q y teniendo esa respuesta, junto a r nos permitirá evaluar la expresión
completa, de manera la respuesta final quedará debajo del “conectivo principal” de la
expresión. La siguiente es una versión simplificada de la tabla del ejemplo anterior.

p q r p ∧ ¬q ⇒ r
1 1 1 0 1 1
1 1 0 0 1 0
1 0 1 1 1 1
1 0 0 1 0 0
0 1 1 0 1 1
0 1 0 0 1 0
0 0 1 0 1 1
0 0 0 0 1 0

Sección 1.4: Diferencias entre igualdad y equivalencia

La expresión booleana b ≡ c es evaluada exactamente como b = c, excepto que la equiva-

lencia puede usarse sólo entre expresiones booleanas.
Sin embargo ambos operadores tendrán propiedades distintas. Primero, la igualdad tiene
la precedencia más alta sobre cualquier otro operador, mientras que la equivalencia tiene
la precedencia más baja, lo cual nos permite quitar paréntesis en expresiones como
x·y =0 ≡ x=0∨y =0

Notemos que los espacios que rodean a ≡ son útiles para recordarnos que este operador
tiene la precedencia más baja.
Por otra parte, la igualdad múltiple se interpreta como “conjuntiva”, es decir
a=b=c se interpreta como b = c ∧ c = d,
con lo cual b = c = d y (b = c) = d son diferentes, pues en el estado (b, False), (c, False)
y (d, True), b = c = d es False, mientras que (b = c) = d es True.
La equivalencia es asociativa, es decir b ≡ c ≡ d se usará para referirse tanto a (b ≡ c) ≡ d
como a b ≡ (c ≡ d), con lo cual no puede ser conjuntiva como ocurrió con la igualdad.
Por lo tanto, en fórmulas sin paréntesis, una secuencia de = tendrá un significado distinto
a una de ≡. Veamos algunos ejemplos:

17
Cartilla Herramientas de Lógica Computacional Ejercicios

Queremos evaluar False = False = True y False ≡ False ≡ True

False = False = True False ≡ False ≡ True

= h= es conjuntivai = h≡ es asociativai
(False = False) ∧ (False = True) (False ≡ False) ≡ True
= hevaluación de =i = hevaluación del primer ≡i
True ∧ False True ≡ True
= hevaluación de ∧i = hevaluación de ≡i
False True
Como segundo ejemplo, mostramos como cambiar ocurrencias de = por ocurrencias de ≡
y viceversa. Utilizaremos paréntesis para las operaciones b = c y b ≡ c, antes de efectuar
los reemplazos debido a que estos operadores tiene distinta precedencia y no queremos
cambiar la estructura de las expresiones:

b≡c≡d b=c=d
= h≡ es asociativai = h= es conjuntivai
(b ≡ c) ≡ d (b = c) ∧ (c = d)
= hreemplazo de operadoresi = hreemplazo de operadoresi
(b ≡ c) = d (b ≡ c) ∧ (c ≡ d)
= hreemplazo de operadoresi =
(b = c) = d

Sección 1.5: Ejercicios

1. Escriba una proposición A en términos de las letras proposicionales p, q tal que al

final, su tabla de verdad sea la que muestre la figura. Para ello, sólo puede usar uno
o varios de los conectivos ∨, ∧, ¬ vistos en clase. Explique el procedimiento que lo
llevó a su respuesta (procurando que se pueda generalizar en caso que la columna
de A tuviera otros valores).

p q A
1 1 1
1 0 1
0 1 0
0 0 1

2. Evaluar las siguientes expresiones en el estado {(p, True), (q, False), (r, False)}

a) (p ∨ q) ∧ r

18
Cartilla Herramientas de Lógica Computacional Ejercicios

b) (p ∧ q) ∨ r
c) p ∨ (q ∧ r)
d) p ≡ (q ≡ r)
e) (p ≡ q) ≡ r
f ) (p ⇒ q) ⇒ r
g) (p ∧ q) ⇒ r

3. Escribir las tablas de verdad para las siguientes expresiones, determinando los casos
en los cuales son tautologı́as o contradicciones.

a) (p ∨ q) ∨ ¬q
b) (p ∧ q) ⇐ ¬q
c) (p 6≡ q) ∧ (p ∨ q)
d) p ≡ (q ≡ p)
e) (p 6≡ q) 6≡ p
f ) (p ⇒ q) ⇒ p
g) ¬q ∧ ¬p ≡ (q ⇒ p) ⇒ q
h) (p ≡ p ∨ ¬p) ⇒ p

4. Escribir las expresiones duales PD de cada una de las expresiones booleanas P que
se indican

a) b ∨ c ∨ True
b) b ∧ c ∧ d
c) b ∧ (c ∨ ¬d)
d) b ∨ (c ∧ d)
e) ¬False ⇒ b ∨ c
f ) ¬b ⇐ b ∨ c
g) (¬b ≡ True) ∨ b
h) (b ≡ c) ≡ (b ⇒ c) ∧ (c ⇒ b)

5. Para cada una de las expresiones P ≡ Q que se indican a continuación, escribir la

correspondiente expresión PD ≡ QD .

a) p ≡ q
b) p ∧ p ≡ p
c) p ⇒ p ≡ True

19
Cartilla Herramientas de Lógica Computacional Ejercicios

d) p ⇒ q ≡ ¬p ∨ q
e) True ⇒ p ≡ p
f) False ⇒ p ≡ True
g) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
h) p≡q≡q≡p
6. Traducir las siguientes frases en expresiones booleanas
a) Llueva o no, iré a nadar.
b) Llueve, no iré a nadar.
c) Llueven rayos y centellas.
d) Llueven rayos o centellas.
e) Llueven rayos y centellas pero iré a nadar.
7. Traducir las siguientes frases en expresiones booleanas
a) Ninguno entre p y q es verdadero.
b) Exactamente uno entre p y q es verdadero.
c) Cero, dos o cuatro entre p, q, r o s son verdaderos.
d) Uno o tres entre p, q, r o s son verdaderos.
8. Identificar las proposiciones elementales en las siguientes frases y traducirlas en
expresiones booleanas.
a) x < y o x = y.
b) x < y o x = y o x > y.
c) Si x > y e y > z entonces v = w.
d) Las siguientes expresiones son todas verdaderas: x < y, y < z y v = w.
e) A lo sumo una de las siguientes expresiones es verdadera: x < y, y < z y v = w.
f) Ninguna de las siguientes expresiones es verdadera: x < y, y < z y v = w.
g) Las siguientes expresiones no son todas verdaderas al mismo tiempo: x < y,
y < z y v = w.
h) Cuando x < y entonces y < z; cuando x ≥ y entonces v = w.
i) Cuando x < y entonces y < z significa que v = w, pero si x ≥ y entonces y > z
no ocurre; sin embargo si v = w entonces x < y.
9. Explique por qué el procedimiento del ejercicio 1 se puede adaptar a la tabla de
cualquier conectivo binario. En otras palabras, explique por qué todo conectivo
lógico binario (dentro de los 16 que existen) se puede expresar usando únicamente
los conectivos ∨, ∧, ¬. 1
1
Advertencia: Su explicación no debe ser del estilo: “Ensayando uno por uno con los 16 conectivos,

20
 Cartilla Herramientas de Lógica Computacional Ejercicios

logré expresar a todos en términos de ∨, ∧, ¬, ası́ que se puede con todos”.

21
Cartilla Herramientas de Lógica Computacional Ejercicios

22