Download Tema 3. Semántica de la lógica proposicional

Tema 3. Semántica de la lógica
proposicional
3b Conceptos clave
TAUTOLOGÍA
CONTRADICCIÓN
CONTINGENCIA
SATISFACIBILIDAD
-Estás triste -le dijo con voz inquieta el Caballero-: para alegrarte voy
a cantar una canción.
-¿Es muy larga? -le preguntó Alicia.
-Es larga -dijo el Caballero- pero muy muy hermosa. A todo aquel
que me la oye cantar… o se le saltan las lágrimas o si no…
-O si no, ¿qué? -dijo Alicia, pues el Caballero se había quedado
cortado de golpe.
-… pues no se le saltan.
Lewis Carroll, A través del espejo
Tautología, contradicción, contingencia
• Considera las siguientes fórmulas:
p p
1 1 1
0 1 0
p
1
0
1
0

1
1
1
1
(q
1
1
0
0

1
0
1
1
p)
1
0
1
0
p
1
0
1
0

1
1
1
1
(¬
0
1
0
1
p
1
0
1
0

1
1
1
0
q)
1
1
0
0
Este tipo de fórmulas, verdaderas para cualquier posible
asignación de valores de verdad de sus constituyentes, se
denominan TAUTOLOGÍAS
Tautología, contradicción, contingencia
• Considera las siguientes fórmulas:
p  ¬ p
1 0 0 1
0 0 1 0
q
1
 ¬
0 0
(p  q)
1 1 1
(p 
q)  ¬
q
1
1
1 0
0
1
0
1
0
0
0
0
1
0
1
1
0
1
0
0
1 0
0
1
1
0
0 0
1
0
0
0
1
0
0
0
0
0
0 0
1
0
Este tipo de fórmulas, falsas para cualquier posible
asignación de valores de verdad de sus constituyentes, se
denominan CONTRADICCIONES
Tautología, contradicción, contingencia
• La negación de una contradicción siempre será una
tautología, y la negación de una tautología será una
contradicción:
¬
0
0
0
0
[p
1
0
1
0
 (¬ p
1
0 1
1
1 0
1
0 1
1
1 0
 q)]
1
1
1
1
1
0
0
0
¬
1
1
1
1
[(p 
1
0
1
0
1
0
0
0
q)
1
1
0
0

0
0
0
0
¬ q)]
0 1
0 1
1 0
1 0
Tautología, contradicción, contingencia
• Considera estas otras fórmulas:
p  p
1 1 1
0 0 0
(p
1
0
1
0
 q)  q)
1 1 1 1
1 1 1 1
1 0 0 0
0 0 1 0
p
1
0
1
0

0
1
1
1
(p
1
0
1
0

0
1
1
1
¬ q)
0 1
0 1
1 0
1 0
Este tipo de fórmulas, verdaderas en algunas
interpretaciones y falsas en otras, se denominan
CONTINGENCIAS
Tautología, contradicción, contingencia
• La negación de una contingencia será siempre una
contingencia, puesto que los valores 1 pasarán a 0, y
los 0 pasarán a 1, y seguirá habiendo tanto
interpretaciones verdaderas como falsas:
¬
0
0
1
0
[(p
 q)  q)]
1
0
1
0
1
1
1
0
1
1
0
0
1
1
0
1
1
1
0
0
Satisfacibilidad
Considera estos 2 pares de fórmulas:
p
¬p
¿crees que es posible que sean verdaderas a la vez?
Obviamente no: cuando una es verdadera, la otra es
falsa.
Satisfacibilidad
¿Y estas otras 2, pueden ser verdaderas a la vez?
p q
¬(p  q)
Tampoco, aunque este caso no es tan obvio como
el anterior. Para verlo habrá que comparar sus
tablas de verdad:
p
 q
¬
(p  q)
1
0
1
0
1
0
0
0
0
0
0
1
1
0
1
0
1
1
0
0
1
1
1
0
1
1
0
0
En los casos en que una es verdadera, la otra resulta ser falsa.
No hay ningún caso en que ambas
sean verdaderas a la vez.
Satisfacibilidad
¿Y estas otras 2, pueden ser verdaderas a la vez?
pq
¬(p  q)
En este caso sí. Comparemos sus tablas de verdad:
p
 q
¬
(p  q)
1
0
1
0
1
1
1
0
0
0
1
0
1
0
1
0
1
1
0
0
1
1
0
1
1
1
0
0
Hay al menos una fila en la que
ambas son verdaderas, la fila 3.
Basta con eso para decir que este
par de fórmulas es
SATISFACIBLE
Satisfacibilidad de una fórmula
• Una fórmula es satisfacible si y sólo si tiene al
menos una interpretación verdadera, i.e., al
menos una fila con un 1 bajo alguna
interpretación de sus atómicas.
• Por tanto, una fórmula será satisfacible si es una
tautología o una contingencia.
• Una fórmula insatisfacible es contradictoria
Satisfacibilidad de un conjunto
de fórmulas
• Un conjunto de fórmulas es satisfacible ssi hay
alguna interpretación en que cada una de ellas es
satisfacible a la vez. Es decir, cuando
encontramos al menos una fila con todo 1s bajo
la conectiva dominante de cada fórmula.
• Esto equivale a decir que un conjunto de
fórmulas 1, … n es satisfacible ssi es
satisfacible la fórmula que obtenemos al unirlas
por conyuntores: (1  …  n)
¿Es satisfacible este conjunto de fórmulas?
pq
¬(r  ¬q)
¬p  r
Para saberlo, podemos unirlas en una única fórmula:
(p  q)  ¬(r  ¬q)  (¬p  r)
y a continuación resolvemos la tabla de verdad de esta
fórmula. Si hay al menos un caso en que esta conyunción
es verdadera, este conjunto de fórmulas es satisfacible.
Esto equivale a decir que debemos encontrar al menos una
fila en que debajo de la conectiva dominante de cada
fórmula aparezca un 1
¿Es satisfacible este conjunto de fórmulas?
pq
( p
1
0
1
0
1
0
1
0

1
0
0
0
1
0
0
0
¬(r  ¬q)
q )
1
1
0
0
1
1
0
0

0
0
0
0
1
0
0
0
¬
0
0
0
0
1
1
0
0
( r
1
1
1
1
0
0
0
0
¬p  r

1
1
1
1
0
0
1
1
¬
0
0
1
1
0
0
1
1
q )
1
1
0
0
1
1
0
0

0
0
0
0
1
0
0
0
( ¬
0
1
0
1
0
1
0
1
p
1
0
1
0
1
0
1
0
r )
1 1
1 1
1 1
1 1
1 0
0 0
1 0
0 0
Observando la 5ª fila comprobamos que este conjunto de fórmulas
sí es satisfacible
¿Es satisfacible este otro conjunto?
pq
¬(q  ¬r)
r  ¬p
( p  q )  ¬ ( q  ¬ r )
 ( r ¬ p )
1 1 1
0 0
1 1 0 1
0
1 0 0 1
0 0 1
0 0
1 1 0 1
0
1 1 1 0
1 0 0
0 1
0 0 0 1
0
1 0 0 1
0 0 0
0 1
0 0 0 1
0
1 1 1 0
1 1 1
0 0
1 1 1 0
0
0 1 0 1
0 0 1
0 0
1 1 1 0
0
0 1 1 0
1 0 0
0 0
0 1 1 0
0
0 1 0 1
0 0 0
0 0
0 1 1 0
0
0 1 1 0
No es satisfacible: no hay ninguna fila en que bajo cada conectiva
dominante (, ¬, , respectivamente) encontremos un 1
Satisfacibilidad
• Lo que buscamos al comprobar si un conjunto de
fórmulas es satisfacible o no, es poder determinar
si las condiciones establecidas por las fórmulas
pueden cumplirse conjuntamente o no.
• Si el conjunto de fórmulas es satisfacible, plantea
condiciones consistentes, y si no es satisfacible,
plantea condiciones inconsistentes o
contradictorias.
Satisfacibilidad
Fefa: Quiero un marido rico y guapo.
Fufa: ¿Preferirías uno que fuese guapo y fiel?
Fefa: Ni hablar. Y si es infiel, que no sea rico.
¿habrá marido para Fefa?
p  es rico q  es guapo
r  es fiel
Condiciones del marido:
pq
¬(q  r)
¬r  ¬p
(p
1
0
1
0
1
0
1
0

1
0
0
0
1
0
0
0
q)
1
1
0
0
1
1
0
0

0
0
0
0
0
0
0
0
¬
0
0
1
1
1
1
1
1
(q
1
1
0
0
1
1
0
0

1
1
0
0
0
0
0
0
r)
1
1
1
1
0
0
0
0
¡Pobre Fefa!
 (¬ r  ¬ p)
0 0 1 1 0 1
0 0 1 1 1 0
0 0 1 1 0 1
0 0 1 1 1 0
0 1 0 0 0 1
0 1 0 1 1 0
0 1 0 0 0 1
0 1 0 1 1 0
Sus condiciones son inconsistentes
CONSECUENCIA LÓGICA
VERDAD LÓGICA
EQUIVALENCIA
-Sé lo que estás pensando -dijo Tweedledumpero no es eso, de ninguna manera.
-Por el contrario -continuó Tweedledee-, si lo
hubiera sido, lo habría sido; y si lo fuera, lo
sería; pero como no lo es, no lo es. Eso es
lógica.
Lewis Carroll, A través del espejo
Consecuencia lógica
• En un argumento válido, la conclusión se sigue de
las premisas.
• Esto ocurre cuando no es posible que las premisas
sean verdaderas y la conclusión falsa.
• Diremos entonces que la conclusión es
consecuencia lógica de las premisas.
• Por tanto, también una fórmula ß será
consecuencia lógica de una fórmula , cuando no
pueda ocurrir que  es verdadera y ß falsa
Consecuencia lógica
• ¿Cómo saber cuándo una fórmula ß es
consecuencia lógica de una fórmula  ?
• Habrá que disponerlas de tal manera que podamos
observar si ocurre que  sea verdadera y ß falsa
• Hay una conectiva cuya tabla de verdad se
corresponde con esta situación:
EL CONDICIONAL

Consecuencia lógica
• Una fórmula ß es consecuencia lógica de una fórmula 
cuando el condicional (  ß) no es falso en ningún caso,
i.e., cuando (  ß) es una tautología.
• Cuando ß es consecuencia lógica de , escribimos:

ß
y cuando no lo es:

ß
Consecuencia lógica
Sean   p  q
ßpq
¿es ß consecuencia lógica de  ?
(p  q)  (p  q)
1
0
1
0
1
0
0
0
1
1
0
0
1
1
1
1
1
0
1
0
1
1
1
0
1
1
0
0
Efectivamente, no hay
ningún caso en que ocurra
que  sea verdadera y ß sea
falsa.
Es decir, no hay ningún caso
en el que el condicional que
hemos construido sea falso.
Consecuencia lógica
• La idea de consecuencia lógica se puede generalizar a
conjuntos de fórmulas: Una fórmula ß es consecuencia
lógica de un conjunto de fórmulas 1 … n ssi no puede
ocurrir que 1 … n sean verdaderas y ß sea falsa, es decir,
cuando el condicional (1  …  n)  ß sea una
tautología.
• Cuando ß es consecuencia lógica de , escribimos:
{1 … n}
ß
{1 … n}
ß
y cuando no lo es:
Consecuencia lógica
Sean 1  (p  q)
2  (r  ¬p)
ßrq
¿es ß consecuencia lógica de 1 y 2?
[(p  q)  (r  ¬ p)]  (r  q)
1 1 1 0 1 0 0 1 1 1 1 1
0 1 1 1 1 1 1 0 1 1 1 1
1
0
1
0
1
0
1
1
0
0
1
1
0
0
1
0
1
1
0
0
0
1
1
0
0
1
0
1
1
0
1
0
1
1
1
1
1
1
0
0
0
0
1
1
0
0
1
1
1
0
1 0
0 0
1
0
0
0
1
0
0 1
1 0
1
1
0
0
1
1
0
0
Efectivamente, no hay
ningún caso en el que
el condicional que
hemos construido sea
falso
Consecuencia lógica: cómo evaluar argumentos
• Tenemos, por tanto, un método para determinar
cuándo un argumento es válido.
• 1º) Identificamos las premisas y conclusión, y las
traducimos a fórmulas de L0
• 2º) Construimos un condicional, cuyo antecedente
es una conyunción de todas las fórmulas de las
premisas, y su consecuente es la fórmula de la
conclusión
• 3º) Evaluamos si el condicional es tautológico:
- si lo es, el argumento es válido
- si no lo es, el argumento no es válido: hay al
menos un caso en que las premisas son verdaderas
y la conclusión falsa
Consecuencia lógica: cómo evaluar argumentos
EJEMPLO 1: Una condición necesaria para que la humanidad sea
libre es que los seres humanos no estén ligados a una esencia. Si
Dios creó a los humanos, entonces estamos ligados a una
esencia. Claramente, los humanos somos libres. Por tanto, Dios
no creó a los humanos.
1º) Identificar y traducir:
p  humanos son libres
r  D crea humanos
q  humanos ligados a esencia
Premisas: (p  ¬q) ; (r  q) ; p
Conclusión:  ¬r
Consecuencia lógica: cómo evaluar argumentos
EJEMPLO 1: Una condición necesaria para que la humanidad sea
libre es que los seres humanos no estén ligados a una esencia. Si
Dios creó a los humanos, entonces estamos ligados a una
esencia. Claramente, los humanos somos libres. Por tanto, Dios
no creó a los humanos.
2º) Construir condicional:
[(p  ¬q)  (r  q)  p]  ¬r
Consecuencia lógica: cómo evaluar argumentos
EJEMPLO 1: Una condición necesaria para que la humanidad sea libre es que
los seres humanos no estén ligados a una esencia. Si Dios creó a los humanos,
entonces estamos ligados a una esencia. Claramente, los humanos somos
libres. Por tanto, Dios no creó a los humanos.
3º) Evaluar condicional:
[(p  ¬ q)  (r
1 0 0 1 0 1
 q) 
1 1 0
p]  ¬
1 1 0
r
1
0
1
0
1
1
1
1
0
0
1
1
0
1
0
0
1
0
0
0
0
1
1
1
0
1
0
0
1
1
0
0
1
0
0
0
0
0
1
0
1
1
1
1
1
0
0
0
1
1
1
1
0
0
1
0
1
1
1
0 1
1 0
1 0
0
1
0
0
0
0
1
1
1
1
0
0
0
1
0
0 1
1 1
0 1
1
1
1
0
0
0
Consecuencia lógica: cómo evaluar argumentos
EJEMPLO 1: Una condición necesaria para que la
humanidad sea libre es que los seres humanos no estén
ligados a una esencia. Si Dios creó a los humanos,
entonces estamos ligados a una esencia. Claramente, los
humanos somos libres. Por tanto, Dios no creó a los
humanos.
La fórmula [(p  ¬q)  (r  q)  p]  ¬r ,
correspondiente a dicho argumento, es tautológica. Por
tanto, el argumento es VÁLIDO.
Consecuencia lógica: cómo evaluar argumentos
EJEMPLO 2: Si la señora White lo hizo, lo hizo con la
llave inglesa o con la cuerda. Pero lo hizo con la cuerda
si y sólo si el asesinato se cometió en el vestíbulo. El
asesinato se cometió en la cocina. Por lo tanto, si la
señora White lo hizo, lo hizo con la llave inglesa.
p  W lo hizo q  W lo hizo con llave r  W lo hizo con cuerda
s  asesinato en vestíbulo t  asesinato en cocina
La fórmula a evaluar es:
([p  (q  r)]  (r  s)  t)  (p  q)
cuya tabla de verdad necesitaría 32 filas
El método “abreviado”
• Para evaluar fórmulas con más de 3 constantes,
la tabla de verdad resulta un método demasiado
engorroso.
• Podemos explotar las propiedades de las
conectivas lógicas para obtener métodos
abreviados de evaluación de fórmulas.
• La idea general es: podemos determinar que una
fórmula NO es tautológica, si encontramos al
menos una fila en la que la fórmula es falsa; y
podemos determinar que NO es contradictoria,
si encontramos al menos una fila en la que la
fórmula es verdadera.
Explotar las propiedades de las conectivas
• En ocasiones, conocer el valor de verdad de una
fórmula molecular nos permite conocer el valor de
verdad de sus componentes:
Supongamos que el valor de (  ß) es 1 ¿Podemos
saber algo sobre los valores respectivos de  y de ß?
En efecto, tanto  como ß deben tener valor 1
Supongamos que el valor de (  ß) es 0 ¿Podemos
saber algo sobre los valores respectivos de  y de ß?
Ahora ya no: tanto  como ß pueden tener valor
1ó0
Explotar las propiedades de las conectivas
• Considera ahora las fórmulas (  ß) y (  ß).
Si (  ß) vale 0,  debe valer 1 y ß debe valer 0
Si (  ß). vale 0, tanto  como ß deben valer 0
Si (  ß) o (  ß) valen 1, no sabemos los
valores de  y ß
Si contamos con más información, los dos
últimos casos también ayudan. Por ejemplo:
Si (  ß) vale 1 y  vale 1, ß debe valer 1
Si (  ß) vale 1 y  vale 0, ß debe valer 1
El método “abreviado”
1º Determinamos qué queremos saber de la
fórmula, si es tautológica o contradictoria
2º Asignamos como valor inicial el contrario al
que queremos obtener. A partir de éste vamos
llenando aquellos otros valores “obligados” por
las tablas de las conectivas lógicas
3ºComprobamos si por el camino topamos con
una contradicción.
El método “abreviado”
1º Determinamos qué queremos saber de la fórmula:
A) queremos saber si es tautológica: intentamos que la
fórmula sea falsa; si lo conseguimos, entonces no es
tautológica; si no lo conseguimos, entonces es
tautológica.
Esto es lo que nos interesa cuando queremos saber si
un argumento es válido.
B) queremos saber si es contradictoria; intentamos que
la fórmula sea verdadera; si lo conseguimos, entonces
no es contradictoria; si no lo conseguimos, entonces es
contradictoria.
Esto es lo que nos interesa cuando queremos saber si
una o más fórmulas son satisfacibles.
El método “abreviado”
2º Fijamos los valores de verdad de la fórmula:
A) queremos saber si el argumento del ejemplo 2 es
válido, i.e., si su fórmula es tautológica:
([p  (q  r)]  (r  s)  t)  (p  q)
1
1
0
1
1
1
1
0
0
i)
0
1
Intentamos conseguir un caso en la fórmula es falsa, así que
ponemos 0 bajo el condicional
ii) Para que el condicional sea 0, el antecedente debe ser 1 y el
consecuente 0. Estos valores van bajo las respectivas dominantes
iii) Una vez fijados estos valores, nos obligan a fijar otros valores de
las fórmulas, de acuerdo a la tabla de cada conectiva
El método “abreviado”
Fijémonos en (p  q): como es un condicional que debe tener valor 0,
ello obliga a fijar los valores de su antecedente y consecuente en 1
y 0, respectivamente. Fijémonos en t: como es una fórmula unida
por un conyuntor con valor 1, debe tener valor 1.
([p  (q  r)]  (r  s)  t)  (p  q)
1
0
1
1
1
1
1
0
1
1
1
1
1
0
0
iv) Trasladamos los valores obtenidos para esas constantes a sus otras
ocurrencias dentro de la fórmula
Fijémonos en [p  (q  r)]: es un condicional que debe tener valor 1
y cuyo antecedente es 1, por tanto su consecuente (q  r) debe ser
1 también. Dado que q tiene valor 1, el único modo posible es que
r tenga valor 1. Fijamos este nuevo valor.
v) Comprobamos si es posible rellenar el último valor de verdad sin
contradicción. En nuestro ejemplo sí lo es: s puede tener valor 1
El método “abreviado”
3º Comprobamos si por el camino topamos con una
contradicción.
([p  (q  r)]  (r  s)  t)  (p  q)
1 1 0
1 1 1 1 1 1 1 0 1 0 0
1
No hemos encontrado contradicción. Eso quiere decir que hay al
menos un caso en que la fórmula es falsa.
Nuestra fórmula NO ES UNA TAUTOLOGÍA y, por tanto, el
argumento al que corresponde NO ES VÁLIDO
La fórmula sería tautológica y, en consecuencia, el argumento válido,
SI NO HUBIÉSEMOS CONSEGUIDO HACERLA FALSA.
Es decir, si a lo largo del proceso nos hubiésemos encontrado con que
nos vemos obligados a hacer asignaciones contradictorias
Explotar las conectivas: tipos de fórmulas
• Las propiedades de las conectivas se pueden explotar también
para saber algo sobre el tipo de fórmula
• Sean dos fórmulas  y ß de las que sabemos:
 es tautología
ß es contradicción
Considera estas fórmulas:
ß
ß
ß
¿podemos saber qué tipo de fórmulas son?
  ß es una contradicción
  ß es una contradicción
  ß es tautológica
  ß es una contradicción
ß
Explotar las conectivas: tipos de fórmulas
• Sean dos fórmulas  y ß de las que sabemos:
 es tautología
ß es contingencia
Considera estas fórmulas:
ß
ß
ß
¿podemos saber qué tipo de fórmulas son?
  ß es una contingencia
  ß es una contingencia
  ß es tautológica
  ß es una contingencia
ß
Explotar las conectivas: tipos de fórmulas
• Sean dos fórmulas  y ß de las que sabemos:
 es contradicción
ß es contingencia
Considera estas fórmulas:
ß
ß
ß
¿podemos saber qué tipo de fórmulas son?
  ß es una contradicción
  ß es una tautología
  ß es contingencia
  ß es una contingencia
ß
Explotar las conectivas: tipos de fórmulas
• Sean dos fórmulas  y ß de las que sabemos:
 es tautología
(  ß) es tautología
¿podemos saber qué tipo de fórmula es ß?
ß tiene que ser una tautología
• Si ß fuese contradicción,   ß sería contradicción
• Si ß fuese contingencia,   ß sería contingencia
Explotar las conectivas: tipos de fórmulas
• Sean dos fórmulas  y ß de las que sabemos:
 es contradicción
(  ß) es contradicción
¿podemos saber qué tipo de fórmula es ß?
LAS CONDICIONES DEL EJERCICIO NO SE
PUEDEN CUMPLIR
Si  es una contradicción, (  ß) necesariamente
debe ser una tautología
Tautología, contradicción y consecuencia lógica
El caso del condicional es particularmente
interesante:   ß
-si ß es una tautología, el condicional   ß es
tautológico, independientemente de lo que sea 
-si  es una contradicción, el condicional   ß
también es una tautología, independientemente
de lo que sea ß
Esto significa que una tautología es consecuencia
lógica de cualquier cosa y que cualquier cosa es
consecuencia lógica de una contradicción
Verdad lógica
• Cuando una fórmula es verdadera en todas las
interpretaciones posibles de sus constantes, se
trata de una verdad lógica
• Por tanto, una fórmula es verdad lógica ssi es
tautológica
• Y dado que una tautología es consecuencia
lógica de cualquier cosa, podemos expresar una
verdad lógica con el símbolo de la
consecuencia:
ß
para toda ß que sea tautología
Equivalencia lógica
• Consideremos las siguientes fórmulas:
p  q ¬(¬p  ¬q)
¬(p  ¬q)
¬(q  ¬p)
Si hacemos sus tablas de verdad, veremos que obtenemos
columnas idénticas: 1
0
0
0
• Decimos en ese caso que las fórmulas son lógicamente
equivalentes, es decir, para cualquier interpretación
(cualquier fila) de la fórmula obtenemos el mismo
valor de verdad en las demás
Equivalencia lógica
• Eso significa que todas las tautologías son
lógicamente equivalentes entre sí y que lo
mismo ocurre entre las contradicciones
• Y supongamos que  y ß sean dos fórmulas
lógicamente equivalentes: ¿qué podemos decir
de la fórmula   ß ?
• Se trata de una tautología, dado que, en cada
fila, a cada valor de  le corresponderá
exactamente el mismo valor de ß, con lo que se
cumplen las condiciones de verdad del 
Equivalencia lógica
• Así mismo, podemos decir que cuando dos
fórmulas  y ß son lógicamente equivalentes, 
es consecuencia lógica de ß, y ß a su vez es
consecuencia lógica de 
• Por tanto, toda tautología tiene como
consecuencia lógica a cualquier otra tautología
¿Cuántas conectivas hay?
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16
p q ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0
1 0 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
Esta tabla recoge todas las posibles conectivas. Comencemos por
identificar las 5 que ya conocemos: ¬, , , , 
¿A qué columnas corresponden?
¿Cuántas conectivas hay?
1
2
3
4
5
6
7
8
9
10 11
12 13
14 15
16
pq?
  ?
? ?   ? ? ¬p ? ¬q ? ?
?
111
1
1
1
1 1 1 1 0 0 0
0 0
0 0
0
011
1
1
1
0 0 0 0 1 1 1
1 0
0 0
0
101
1
0
0
1 1 0 0 1 1 0
0 1
1 0
0
001
0
1
0
1 0 1 0 1 0 1
0 1
0 1
0
Las columnas 11 y 12 se limitan a negar los valores de p y q, respectivamente. ¿Qué conectivas se esconden en las demás columnas?
Centrémonos en 1, 4, 5 y 6
¿Cuántas conectivas hay?
1
2
3
4
5
6
7
8
9
10 11
12 13
14 15
16
pq   q
 p   ? ? ¬p ? ¬q ? ?
?
111
1
1
1
1 1 1 1 0 0 0
0 0
0 0
0
011
1
1
1
0 0 0 0 1 1 1
1 0
0 0
0
101
1
0
0
1 1 0 0 1 1 0
0 1
1 0
0
001
0
1
0
1 0 1 0 1 0 1
0 1
0 1
0
4 y 6 se limitan a reproducir los valores de q y p, respectivamente.
1 es la columna de una tautología y 5 hace lo mismo que el condicional, pero en sentido inverso, o sea, equivale a q  p
¿Cuántas conectivas hay?
1
2
3
4
5
6
7
8
9
10 11
12 13
14 15
16
pq   q
 p   ? ? ¬p ? ¬q ? ?
?
111
1
1
1
1 1 1 1 0 0 0
0 0
0 0
0
011
1
1
1
0 0 0 0 1 1 1
1 0
0 0
0
101
1
0
0
1 1 0 0 1 1 0
0 1
1 0
0
001
0
1
0
1 0 1 0 1 0 1
0 1
0 1
0
De modo que podemos prescindir de todas esas columnas: podemos
realizar sus funciones mediante nuestras conectivas. Si miramos las
columnas 9-16, vemos que son una imagen espejo de 1-8.
¿Cuántas conectivas hay?
1
2
3
4
5
6
7
8 9
10
11
12 13
14 15
16
¬p >– ¬q –< 

pq   q
p  
111
1
1
1
1 1 1 1 0 0 0
0 0
0 0
0
011
1
1
1
0 0 0 0 1 1 1
1 0
0 0
0
101
1
0
0
1 1 0 0 1 1 0
0 1
1 0
0
001
0
1
0
1 0 1 0 1 0 1
0 1
0 1
0
>–<
Por tanto, para expresar las conectivas 9-16 nos basta con tener las
conectivas 1-8, más el negador ¬
¿Cuántas conectivas hay?
Resumiendo, podemos establecer las siguientes
equivalencias:
p  q equivale a q  p
pq  ¬ (p  q)
p >–< q  ¬ (p  q)
p >– q  ¬ (q  p)
p –< q  ¬ (p  p)
p  q  ¬ (p  q)
De ahí que podamos prescindir de todas esas conectivas
¿Cuántas conectivas hay?
¿Es posible reducir aún más el número de conectivas?
Recordemos estas equivalencias lógicas:
pq
¬(¬p  ¬q)
¬(p  ¬q)
¬(q  ¬p)
Esto indica que la función del conyuntor puede realizarse
por medio del disyuntor + el negador, o del condicional +
el negador.
En realidad, cualquiera de estos pares de conectivas:
{¬, }, {¬, }, {¬, }
es suficiente para cubrir todas las combinaciones de
nuestro cuadro general de conectivas
¿Cuántas conectivas hay?
De hecho, podríamos reducir nuestras conectivas a una
sola: pq (o también p  q)
¬p  pp
(p  q)  (pq)( pq)
(p  q)  (pp)(qq)
(p  q)  [p(qq)] o también: [p(pq)]
Pero reducir demasiado el número de conectivas resulta
engorroso. Lo que se intenta es encontrar un número
equilibrado que (a) capte nuestras intuiciones más típicas
del lenguaje natural y (b) resulte en fórmulas manejables