Capítulo 2

Expresiones booleanas

Índice del Capítulo

2.1. Sintaxis y evaluación de expresiones booleanas . . . . . . . . . . . . . . . 36
2.2. Usando Tablas de verdad para evaluar expresiones booleanas . . . . . . . 38
2.3. Satisfabilidad y validez . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.4. Lenguaje y Lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.4.1. Proposiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.4.2. La Negación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.4.3. La Conjunción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.4.4. La disyunción y la discrepancia . . . . . . . . . . . . . . . . . . . . 42
2.4.5. La Implicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
a) Construcción Si . . . , entonces . . . . . . . . . . . . . . . . . . . . . 43
b) Construcción Si . . . , . . . . . . . . . . . . . . . . . . . . . . . . . . 44
c) Construcción . . . si, . . . . . . . . . . . . . . . . . . . . . . . . . . 44
d) Construcción . . . sólo si, . . . . . . . . . . . . . . . . . . . . . . . . 45
e) Construcción cuando . . . , . . . . . . . . . . . . . . . . . . . . . . . 46
f) Condición Necesaria y Suficiente . . . . . . . . . . . . . . . . . . 46
f) El condicional contrafáctico . . . . . . . . . . . . . . . . . . . . . 47
2.4.6. La Equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Propiedad de las secuencias de equivalencias . . . . . . . . . . . . . 48
2.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.5.1. Ejercicios sobre Expresiones Booleanas . . . . . . . . . . . . . . . . 49
2.5.2. Ejercicios de Traducción . . . . . . . . . . . . . . . . . . . . . . . . 51
2.6. Tablas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

35
36 2. Expresiones booleanas

n este capítulo trabajaremos sobre las expresiones booleanas, cuyo nombre se debe a George
E Boole (1815–1864). Las expresiones booleanas son utilizadas con frecuencia en distintos
lenguajes de programación, por lo tanto el material de éste capítulo será familiar para aquellos
que tengan alguna noción de Pascal, C, FORTRAN o algún otro lenguaje. Aquí también veremos
cómo expresar frases en español a través de expresiones booleanas.

2.1. Sintaxis y evaluación de expresiones booleanas

Ya vimos en el capítulo anterior algunos ejemplos de expresiones booleanas construídos a
partir de expresiones aritméticas. El proceso de construcción de expresiones booleanas es análo-
go al que vimos 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 ≡, ., ∧, ∨, ⇒ y ⇐.
Dado que los operadores lógicos actúan sobre constantes o variables booleanas que sólo
asumen los valores true o false, pueden enumerarse los distintos valores que toman de acuerdo
a cada posible combinación de los valores de sus argumentos.
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, f alse} en el conjunto {true, f alse}. Aquellas funciones que asumen valores en el conjunto
{true, f alse} se conocen como funciones booleanas.
Si consideramos las funciones booleanas de un argumento definidas sobre el conjunto {true,
f alse}, entonces tenemos un total de cuatro funciones como aparecen en la siguiente tabla:

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 [Link] = true y id. f alse = f alse, 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 ¬ f alse = true.
Si ahora consideramos todas las funciones booleanas de dos argumentos, es decir definidas
sobre el conjunto

{(true, true) , (true, f alse) , ( f alse, true) , ( f alse, f alse)} ,

§Versión 2015.1
2.1. Sintaxis y evaluación de expresiones booleanas 37

se obtienen dieciseis posibles funciones que se muestran en la siguiente tabla de verdad:

≡ n .
a n
n o
∨ ⇐ ⇒ = ∧ d , r
t t t t t t t t t t f f f f f f f f
t f t t t t f f f f t t t t f f f f
f t t t f f t t f f t t f f t t f f
f f t f t f t f t f t f t f t f t f

Observemos que en la tabla hemos abreviado true con la letra t y false con la letra f.
Sólo ocho de las funciones que aparecen en la tabla anterior son suficientemente útiles como
para ser conocidas por un nombre particular, y son llamadas operadores booleanos o conectores.
Por ejemplo la aplicación de las funciones correspondientes a la segunda y tercer columna se
denota b ∨ c y x ⇐ y respectivamente. A continuación daremos un detalle de cada uno de los
operadores.
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.
El operador , es la desigualdad habitual. La expresión b , c se lee “b es distinto de c”. El
operador , satisface (b , c) = ¬ (b = c). Al operador booleano desigualdad también se le da
el nombre de discrepancia y se lo nota con un segundo símbolo, .. 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.
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.
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.
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 antecedente es falso, el resultado
de la expresión b ⇒ c será verdadero, sin importar el valor del consecuente, esto es consistente
con la interpretación en español de frases como “Si la economía mejoró con esos ajustes, yo soy
Gardel”. En este sentido la frase representa una proposición verdadera simplemente porque la
economía no mejoró con esos ajustes y de este modo, falso implica cualquier situación posible
o imposible. Veremos con más detalle la implicación en secciones posteriores.
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.
Los nombres de los operadores “nand” y “nor” siguen de “not and”(no y) y “not or”( no o)

§Versión 2015.1
38 2. Expresiones booleanas

en inglés respectivamente. La expresion b nand c es igual a ¬ (b ∧ c), mientras que b nor c es

igual a ¬ (b ∨ c).
Una vez presentados todos los operadores lógicos, vamos a definir una precedencia entre
ellos, lo cual nos permitirá eliminar paréntesis en expresiones booleanas y abreviar escritura:
(2.1) Definición. Los operadores lógicos tendrán la precedencia que se indica a continuació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 ∨

4. operadores ⇒y ⇐

5. operadores ≡ y .

(2.2) 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

2.2. Usando Tablas de verdad para evaluar expresiones boo-

leanas
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 opera-
dor ¬, ¬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 independien-
temente 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 verdad.
Los posibles valores de las variables booleanas involucradas en la expresión se disponen en las
primeras columnas de la tabla, mientras que en las siguientes columnas se colocan los valores

§Versión 2015.1
2.4. Lenguaje y Lógica 39

parciales de los operadores lógicos intervinientes, en orden y de acuerdo a las reglas de pre-
cedencia, 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 evalua-
ció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
true true true false false true
true true false false false true
true false true true true true
true false false true true false
false true true false false true
false true false false false true
false false true true false true
false false false true false true

2.3. Satisfabilidad y validez

(2.3) Definición. Una expresión booleana P se satisface en un estado de las variables que
aparecen en ella, si su valor es true en ese estado; P se dice satisfactible si existe algún
estado en el cual P se satisface y P se dice válida si se satisface en cualquier estado.
Una expresión booleana válida se llama tautología.

Es fácil reconocer una tautología, pues en su correspondiente tabla de verdad aparecerá

siempre el valor true en la última columna. Por ejemplo, p ⇒ p y p ∧ p ≡ p son tautologías.

p p⇒p p p∧p p∧ p≡ p
true true true true true
false true false false true
La expresión booleana p ∨ q se satisface en cualquier estado (p, true), por lo tanto es satis-
factible, sin embargo no es válida pues no se satisface en el estado (p, f alse), es decir, no es una
tautología.
(2.4) Definición. Una contradicción es una expresión booleana cuya evaluación en cualquier
estado es siempre f alse.

Observemos que la negación de una tautología es entonces una contradicción, son ejemplos
de contradicción p . p o también p ∧ ¬p.

p p .p p ¬p p ∧ ¬p
true false true false false
false false false true false

§Versión 2015.1
40 2. Expresiones booleanas

2.4. Lenguaje y Lógica

La lógica simbólica surgió como una manera de analizar los razonamientos escritos en len-
guaje natural. Los operadores presentados en la sección anterior fueron pensados como contra-
partidas 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 per-
mitirá dos cosas: por un lado resolver ambigüedades 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.

2.4.1. Proposiciones
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 ope-
radores 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)

(2.5) Observación. La palabra “pero” se traduce como una conjunción, puesto que afirma
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.

2.4.2. La Negación
La operación de negación aparece usualmente en el lenguaje insertando un “no” en la po-
sició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”.

§Versión 2015.1
2.4. Lenguaje y Lógica 41

Por ejemplo el enunciado:

Todos los unicornios son azules (2.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 (2.1), cualquiera de las variantes de negación propuestas

se simbolizan mediante el operador lógico de negación y se expresan ¬p.
En resumen, algunas traducciones para este operador son:

Expresiones Operador
No “p”
Es falso “p”
No es cierto “p” ¬
No es el caso “p”
No se da el caso que “p”

2.4.3. La Conjunción
La conjunción aparece en el lenguaje con la palabra “y”, uniendo dos proposiciones. Tam-
bié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

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.
En resumen, algunas de las traducciones para este operador son:

§Versión 2015.1
42 2. Expresiones booleanas

Expresiones Operador
“p” y “q”
“p” pero “q”
“p” aunque “q”
“p” sin embargo “q” ∧
“p” no obstante “q”
“p” a pesar de “q”
“p” a menos “q”
“p” igualmente “q”

(2.6) Ejemplo. Algunos ejemplos para los conectores anteriores son:

• En Argentina hay inflación y no hay crecimiento económico.

• El gobernador tiene buenas intenciones sin embargo no tiene presupuesto.
• La oferta es alta no obstante la demanda es muy poca.
• El Barcelona ganó a pesar de la poca asistencia de hinchas.
• Aunque esta nevando es posible conducir.
• Esta granizando pero es posible navegar.

2.4.4. La disyunción y la discrepancia

La palabra usual que corresponde a la disyunción es “o”, también la variante “o bien”. El ca-
so 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 elemen-
tales:
p : Para ser emperador hay que tener el apoyo de la nobleza
q : Para ser emperador hay que tener el apoyo del pueblo
Otros ejemplos podrían ser:

El parcial era difícil o había estudiado poco

Un ejemplo de disyunción exclusiva es:

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

§Versión 2015.1
2.4. Lenguaje y Lógica 43

donde se interpreta que el consejero no puede pertenecer simultáneamente a las dos clase socia-
les. Utilizaremos para este caso el operador discrepancia que simbolizamos como ., por tanto
si llamamos
p : El consejero del emperador pertenece a la nobleza
q : El consejero del emperador pertenece al pueblo
la proposición (2.2) se expresa así : p . q.
En latín existen palabras diferentes para la disyunción inclusiva y exclusiva. La palabra “vel”
se usa para la primera y la palabra “aut” para la segunda. El símbolo utilizado en lógica para la
disyunción proviene precisamente de la palabra latina.
En resumen, algunos conectores que podemos traducir como disyunciones son:

Expresiones Operador
“p” o “q”
“p” o “q” o ambas/pero no ambas
al menos “p” o “q” ∨, .
mínimo “p” o “q”
“p” o bien “q”

(2.7) Ejemplo. Ejemplos de traducciones para la disyunción inclusiva son:

• El parcial era difícil o había estudiado poco.

• Hizo frío o la persona estaba nerviosa.
• El Parque Urquiza es grande o había demasiado tráfico.
• Para pagar el crédito se debe tener cuenta corriente o cuenta de ahorro.

(2.8) Ejemplo. Ejemplos de traducciones para la disyunción exclusiva o discrepancia son:

• El consejero del emperador pertenece al pueblo o a la nobleza.

• El número “x” es par o impar.
• El número “y” es primo o compuesto.
• Esteban juega el partido de futbol o va a la casa de su abuela.
• Luis se fue de vacaciones a Quito o decidio quedarse en Rosario.

2.4.5. La Implicación
a) Construcción Si . . . , entonces . . .
La implicación lógica suele representar lo que en el lenguaje natural se expresa mediante la
construcción: si. . . ,entonces . . . . Por ejemplo, la siguiente proposición compuesta

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

§Versión 2015.1
44 2. Expresiones booleanas

donde aparecen las proposiciones elementales:

p : Se reforman las leyes laborales

q : Baja el desempleo
es una proposición condicional, o también llamada implicancia material. La conectiva si-entonces
relaciona las proposiciones simples, p y q, donde la proposición que sigue a la conectiva “si”
recibe el nombre de antecedente, y la proposición que sigue a la palabra “entonces” se llama
consecuente. El símbolo que se utiliza para representar esta conectiva lógica es: ⇒. Por lo tanto,
la frase 2.3 la modelizaríamos como p ⇒ q.
La implicancia es uno de los conectivos sobre los que menos acuerdo existe y al que más
alternativas se han propuesto. Veremos a continuación cuáles son las condiciones que hacen que
una implicancia sea verdadera. Analizaremos cada caso.
Consideremos el ejemplo inicial, 2.3, casi todo el mundo acuerda que si el antecedente p
es verdadero y el consecuente q es falso, entonces p ⇒ q es falso. Esto correspondería a que,
las leyes laborales se reforman y no baja el desempleo, entonces la proposición (2.3) (p ⇒ q)
resulta falsa. En cambio, si es verdad que se reforman las leyes laborales , y también lo es que,
baja el desempleo, diremos que la proposición (2.3) es verdadera. Los casos que nos quedan
por analizar, corresponden al antecedente falso. Estos casos, difícilmente se presentan en el uso
del lenguaje coloquial, por lo que resulta difícil inferir que valores de verdad le corresponden.
La lógica resuelve considerar entonces estos casos como verdaderos, no de una forma arbitaria,
sino contemplando lo que se deja sin decidir en el consecuente.
Luego, la construcción “si p , entonces q ” la simbolizaremos como p ⇒ q. Existen otras
construcciones que modelizaremos mediante la implicancia las cuáles analizaremos a continua-
ción.

b) Construcción Si . . . , . . .
En la construcción si. . . , . . . es similar a la anterior, sólo que se ha omitido la palabra
“entonces”, y en este caso aparece el símbolo de puntuación “,” (la coma). Por ejemplo,

Si viajamos en tren, sacaremos los pasajes con anticipación (2.4)

donde aparecen las proposiciones elementales:

p : Viajamos en tren
q : Sacaremos los pasajes con anticipación
y simbolizaremos como p ⇒ q.

c) Construcción . . . si, . . .
En este caso, la construcción “q , si p ”, el orden del antecedente y del consecuente se ha
invertido: primero esta dado el consecuente, y luego a continuación de la palabra “si” sigue el
antecedente. Por ejemplo, en la proposición:

§Versión 2015.1
2.4. Lenguaje y Lógica 45

Saldré a jugar, si vienes a buscarme temprano (2.5)

donde aparecen las proposiciones elementales:

q: Saldré a jugar (consecuente)

p: Vienes a buscarme temprano (antecedente)
será simbolizada como q ⇐ p, dada la inversión natural de la expresión coloquial.
Decimos entonces que la palabra “si” introduce al antecedente, y modelamos la construcción
“q , si p ” como q ⇐ p. Por supuesto que es lícito traducir la misma como p ⇒ q, pero dado
que el consecuente esta dado primero y contamos con un operador lógico para estos casos,
preferimos la traducción con el operador ⇐, “ser consecuencia de”, o “sigue de”.

d) Construcción . . . sólo si, . . .

En este caso, la construcción “p sólo si q ”, coincide con la construcción “ si p entonces q
”. Por ejemplo, la proposición:

El seguro pagará sólo si se produce un incendio (2.6)

donde aparecen las proposiciones elementales:

p : El seguro pagará
q : Se produce un incendio
es equivalente a,

Si el seguro paga, entonces es porque se ha producido un incendio (2.7)

la cual será simbolizada como p ⇒ q.
Decimos entonces que la palabra “sólo si” introduce al consecuente, y modelaremos la cons-
trucción “p sólo si q ” como p ⇒ q. Observemos también que la construcción: “Sólo p si q ”
significa también “Si p ,entonces q ”, y por lo tanto, también la simbolizaremos como p ⇒ q.
Por ejemplo,

Sólo voy al dentista, si me duelen las muelas (2.8)

significa que

Voy al dentista, sólo si me duelen las muelas (2.9)

o

Si voy al dentista, entonces me duelen las muelas (2.10)

§Versión 2015.1
46 2. Expresiones booleanas

e) Construcción cuando . . . , . . .
En este caso analizaremos la construcción “cuando p , q ”. La palabra “cuando” reemplaza
usualmente al “si” como por ejemplo en la siguiente proposición:

Cuando hay tormentas, se interrumpen las comunicaciones satelitales (2.11)

cuyo significado corresponde a,

Si hay tormentas, entonces se interrumpen las comunicaciones satelitales (2.12)

donde aparecen las proposiciones elementales:

p: Hay tormentas
q: Se interrumpen las comunicaciones satelitales
la cual simbolizaremos como p ⇒ q.
Observemos que el matiz temporal de la palabra “cuando” la lógica proposicional no lo
tiene en cuenta. La construcción “cuando p , q”, equivale a “si p , entonces q”, y por lo tanto
la simbolizaremos como p ⇒ q. De igual modo, la construcción “q cuando p ” equivale a “q si
p ” que simbolizaremos como q ⇐ p.

f) Condición Necesaria y Suficiente

Otra forma de representar la implicación en el lenguaje natural es a través de las palabras
suficiente y necesario. Lo que es suficiente corresponde al antecedente de la implicancia, y lo
que es necesario corresponde al consecuente. La relación entonces es:

su f iciente ⇒ necesario

Veamos algunos ejemplos de traducciones para frases que contienen las expresiones ante-
riores.

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

donde
p: Vacuno a mi hijo
q: Mi hijo contrae el sarampión
La proposición que es suficiente (¿Qué es suficiente?) corresponde al antecedente, y la otra pro-
posición elemental corresponde al consecuente. La frase anterior puede simbolizarse mediante
p ⇒ (¬q) La proposición (2.13) asegura que vacunar es condición suficiente para no contraer
el sarampión, nada dice acerca de aquellos niños que no son vacunados
Otro ejemplo donde ahora aparece la idea de necesidad lógica sería,

§Versión 2015.1
2.4. Lenguaje y Lógica 47

Para obtener una beca es necesario tener un buen promedio en la carrera (2.14)

, considerando las proposiciones elementales como:

p : Tener un buen promedio

q : Obtener una beca.

y analizando ahora cuál es la condición necesaria (¿Qué es necesario?) para identificar al

consecuente, la proposición (2.14) puede simbolizarse así q ⇒ p o también p ⇐ q
La proposición (2.14) establece que tener un buen promedio es condición necesaria para
conseguir una beca y no garantiza que todo alumno con buen promedio la obtendrá.
Si formulamos esta proposición en términos de si. . . entonces. . . , resulta

Si obtiene una beca entonces tiene un buen promedio en la carrera

f) El condicional contrafáctico
Existen ciertas dudas acerca del valor de verdad (o del significado lógico) de frases como

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 elíptica de
negar el antecedente. Por ejemplo, decir

Si la economía mejoró con esos ajustes, yo soy Gardel

es una manera elegante de decir que la economía no mejoró con los ajustes.

2.4.6. La Equivalencia
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 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 capacidades de Juan.

Juan ve bien si y sólo si Juan es tuerto si y sólo si Juan es ciego (2.15)

§Versión 2015.1
48 2. Expresiones booleanas

La equivalencia es asociativa, por tanto, la frase anterior puede representarte así: p ≡ q ≡ r,

donde p, q y r son las proposiciones elementales obvias en la frase. Veamos la tabla de verdad
correspondiente:
p q r p ≡ q (p ≡ q) ≡ r
true true true true true
true true false true false
true false true false false
true false false false true
false true true false false
false true false false true
false false true true true
false false false true false
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.
Muchas veces 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 implicancia. 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

Otra de las formas de traducción para la equivalencia, es la frase, “p es necesario y su-

ficiente para q”. Esta construcción del lenguaje tiene el significado de una equivalencia y la
simbolizaremos como p ≡ q. Un ejemplo podría ser:

D = 0 es una condición necesaria y suficiente para que el polinomio admita una raíz doble

Propiedad de las secuencias de equivalencias

Podemos notar una interesante y útil propiedad sobre secuencias de equivalencias a partir del
ejemplo (2.15). Analicemos en general este tipo de expresión booleana. La expresión booleana

P0 ≡ P1 ≡ · · · ≡ Pn

es verdadera (true) cuando exactamente un número par de Pi es falso ( f alse).

La demostración de esta propiedad no la veremos en este capítulo, ya que necesitamos do-
minar ciertas técnicas que aún no conocemos, pero intuitivamente, podemos justificar la validez

§Versión 2015.1
2.5. Ejercicios 49

de la misma considerando que cada subexpresión f alse ≡ f alse en la secuencia puede ser re-
emplazada por true, hasta que se consiga o bien una expresión falsa o ninguna, en cuyo caso
la secuencia es falsa o verdadera. Estos reemplazo de valores, corresponden a la asignación de
valores de verdad que dimos para la tabla de verdad del operador ≡.
Veamos algunos ejemplos de aplicación de esta propiedad: podemos determinar sin ninguna
manipulación formal que
f alse ≡ f alse ≡ f alse ≡ true
es f alse, porque tres de sus expresiones son falsas. Del mismo modo que

f alse ≡ f alse ≡ true

es true, porque dos de sus subexpresiones son falsas.
También utilizaremos esta propiedad sobre secuencias de equivalencias para formalizar fra-
ses en lenguaje corriente, como se indican a continuación:

• Ninguno o los dos, entre p y q son verdaderos: p ≡ q

• Exactamente uno entre p y q es verdadero: ¬ (p ≡ q), o p . q

• Cero, dos o cuatro entre p, q, r y s son verdaderos: p ≡ q ≡ r ≡ s

• Uno o tres entre p, q, r y s son verdaderos: ¬ (p ≡ q ≡ r ≡ s)

2.5. Ejercicios
2.5.1. Ejercicios sobre Expresiones Booleanas
2.1 Evaluar las siguientes expresiones en el estado {(p, true), (q, f alse), (r, f alse)}

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

2.2 Utilizando la tabla de precedencia de las operaciones booleanas y las propiedades de aso-
ciatividad de cada operación booleana elimine los paréntesis innecesarios de las siguientes
expresiones:

a) ((((a = b) ∧ (b = c)) ⇒ (a = c)) ≡ true)

b) (((p ⇒ q) ∧ (q ⇒ p)) ⇒ (p ≡ q))
c) (((p ∧ q) ∨ (¬r)) ⇒ (p ∧ (q ∨ r)))
d) (((true ∧ f alse) ⇒ p) ≡ (true ≡ true))

§Versión 2015.1
50 2. Expresiones booleanas

e) (((p ≡ q) . (r ∨ s)) ≡ (t ⇒ p))

f) ((p ⇒ (p ∨ q)) ⇐ (r ∧ (p ∨ s)))

2.3 Utilizando la tabla de precedencia y las propiedades de asociatividad de cada operación

booleana agregue los paréntesis correspondientes a la forma de evaluación de la las si-
guientes expresiones:

a) p ∨ q ⇒ r ≡ (p ⇒ r) ∧ (q ⇒ r) d) (p ∧ q) ∨ r ∨ t ⇒ p ∨ q
b) p ⇒ q ≡ p ∨ q ≡ q e) (p ⇒ q ∨ s ⇒ t) ∧ r ⇐ s ∧ q
c) p ⇒ q ≡ ¬p ∨ q f) p . (q ≡ r) ⇒ (t ⇐ r) ⇒ s

2.4 Realice las siguientes sustituciones sobre expresiones booleanas.

a) (p ∨ q ≡ q ∨ p)[p, q := p ∧ q, p ∨ q]
b) (p ∨ q ≡ q ∨ p)[q, p := p ∨ q, p ∨ q]
c) (p ∨ q ≡ p ≡ q ≡ p ∧ q)[q, p := p, q ∨ q]
d) ((p ∨ q ≡ q) ≡ p ⇒ q)[p, q := p ≡ r, q ⇒ ¬r]
e) (p ∧ (q ∧ p) ≡ p ∧ q)[q, p := p ∧ (q ∨ p), r ∨ ¬r]
f) (true ∨ r . f alse)[p := true][r := f alse]
g) (true ∨ t ⇒ ( f alse ≡ r ≡ p ≡ t ∧ s)[t, s := true])[r := t][t := f alse]

2.5 Completar utilizando la Regla de Leibniz. En cada caso decidir cuales son las expresiones
E, X e Y. Dar todas las respuestas posibles.

(p ∨ q) ∧ p = p
a)
? = p ⇒ (q ∨ r)
(p ∨ q ≡ q) = (p ⇒ q)
b)
((p ∨ q ≡ q) ∧ s) ∨ (p ∨ q ≡ q) = ?
(q ⇒ p) = (p ∧ q ≡ q)
c)
(r ⇒ (q ⇒ p) ≡ p ∧ q ⇒ p) = ?
p = ¬p
d)
p⇒p = ?
(p . q) = (¬p ≡ q)
e)
((p . q) ⇐ (r ≡ (p . q))) = ?

2.6 Escribir las tablas de verdad para las siguientes expresiones, determinando los casos en
los cuales son tautologías, contradicciones o contingencias.

§Versión 2015.1
2.5. Ejercicios 51

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

2.5.2. Ejercicios de Traducción

2.7 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.

2.8 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.

2.9 Identificar las proposiciones elementales en las siguientes frases y traducirlas en expresio-
nes 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.

§Versión 2015.1
52 2. Expresiones booleanas

j) Si la ejecución del programa P comenzó con x < y, entonces la ejecución termina con
y = 2x .
k) La ejecución del programa P que comenzó con x < 0 no terminará.

2.10 Decir en cada caso si la condición p es necesaria, suficiente o ambas para la condición q.

1) p : x es un número entero, cuya última cifra es cero. q : x es divisible por 10.

2) p : x es un número entero. q : x es divisible por 4.
3) p : x e y son números impares. q : x + y es un número par.
4) p : x e y son números positivos. q : x × y es un número positivo.
5) p : x es un número positivo e y es un numero negativo. q : x×y es un número negativo.
6) p : x = 3 × y, donde y es un número entero. q : x es divisible por 3

2.11 Formalice las siguientes oraciones, en cada caso detalle cuales son las variables proposi-
cionales que utiliza.

a) Pedro y Carolina están casados.

b) Pedro y Carolina cantan bien.
c) María será una buena alumna si estudia mucho.
d) Juan asiste a las clases de cálculo matemático solo si esta cursando primero, segundo
y tercer año de la carrera.
d) Cuando canta Esteban me duelen los oídos.
e) Una condición necesaria para que el equipo C gané la Copa Libertadores es que con-
traten un buen arquero.
f) Una condición suficiente para que María visite Francia es ir a la Torre Eiffel.
g) Para que Fernando compre una computadora es necesario que gane $2000 por quin-
cena.
h) Una condición suficiente para que Carolina tome el curso de Algoritmos es que aprue-
be Matemática I.
i) El programa es legible sólo si esta bien estructurado.
j) Si no arreglas bien mi lavarropas no te pagaré los $300 del presupuesto.
k) No es verdad que Andres haya recibido un telegrama de la empresa o que no sea
honesto.
l) Si Alexis no esta equivocado, Beatriz conducía un coche rojo y había un hombre
sentado a su lado.
m) Si el programa esta bien escrito y documentado entonces es muy probable que satis-
faga las normas de calidad.

§Versión 2015.1
2.6. Tablas 53

2.12 Interpretando a las variables r y s como

r : Esta lloviendo
s : Esta nevando
formalice las siguientes oraciones:

1) Esta lloviendo o nevando.

2) Esta lloviendo o esta nevando o ambas cosas.
3) Esta lloviendo, pero no esta nevando.
4) No esta lloviendo ni nevando.
5) Si no esta lloviendo, entonces esta nevando.
6) No es el caso que este lloviendo y no este nevando.
7) No es el caso que si esta nevando no este lloviendo.
8) Esta lloviendo si y sólo si no esta nevando.
9) O no esta lloviendo o no esta nevando.
10) Si esta lloviendo y esta nevando entonces esta nevando.
11) Si no esta lloviendo, entonces no esta ni nevando ni lloviendo.
12) O esta lloviendo, o esta nevando y lloviendo al mismo tiempo.
13) O esta lloviendo y nevando al mismo tiempo o esta nevando pero no esta lloviendo.

2.6. Tablas
Niveles de precedencia
1 E[x := Y] sustitución textual
2 f.E aplicación de función
3 (−√ (¬ 2·)
·), signo, negación
4 (·), (·) raíces y potencias
5 ×, / producto y división
6 mı́n, máx mínimo y máximo
7 +, − suma y resta
8 =, ≤, <, ≥, > operadores relacionales
9 ∧, ∨ disyunción y conjunción
10 ⇒, ⇐ implicancia y consecuencia
11 ≡, . equivalencia y discrepancia
Nota: la negación de los operadores en los niveles 6 y 9 tienen el mismo nivel de precedencia que
cada uno de ellos respectivamente.

§Versión 2015.1
54 2. Expresiones booleanas

Asociatividades
E[x := Y] Asociativo a izquierda
f.E Asociativo a izquierda
(−√·), (¬ 2·) Asociativo a derecha
(·), (·) Asociativo a derecha
× Asociativo
/ Asociativo a izquierda
mı́n, máx Asociativos
+ Asociativa
− Asociativa a izquierda
=, ≤, <, ≥, > No son asociativos, son conjuntivos
∧, ∨ Asociativos
⇒ Asociativa a derecha
⇐ Asociativo a izquierda
≡, . Asociativos

§Versión 2015.1