1

Lógica 2013

Interdefinibilidad de conectivos y conjuntos adecuados.

Miguel Molina

A esta altura del curso hemos presentado un lenguaje formal que hemos

construido con el propósito de representar proposiciones. Vimos que además de

esa dimensión representacional de nuestro lenguaje, debimos considerar una

dimensión semántica, para poder estudiar la corrección de los argumentos. Como

la corrección de los argumentos es algo que depende de los valores de verdad de

las proposiciones, esa semántica consistió en la asignación de valores de verdad a

las fórmulas del lenguaje formal de modo que se respetara el comportamiento

esperado de los conectivos. Ahora bien, en nuestro lenguaje formal existen cinco

conectivos, que de alguna manera, hemos “abstraído” del lenguaje natural. Sin

embargo, cabe hacerse una pregunta: ¿Serán suficientes estos conectivos para

nuestros propósitos?

Es muy fácil pensar alternativas en las que esto no hubiera sido cumplido. Por

ejemplo, si el único conectivo que hubiésemos considerado en nuestro lenguaje

fuese la conjunción, sería imposible construir una fórmula que se comportara

desde el punto de vista semántico igual que (p1 p2). Esto es así porque al solo

tener la conjunción, cualquier fórmula, bajo una interpretación donde todas las

letras proposicionales sean verdaderas, será verdadera, y la fórmula que acabamos

de escribir es falsa bajo una interpretación así. Es decir, imaginemos que tenemos

una tabla de verdad de esta forma:

p1 p2 A V V F V F V F V V F F F

Se nos pide hallar una fórmula A de nuestro lenguaje que tenga ese

comportamiento semántico. Si solo tuviésemos la conjunción, resultaría imposible.

Con nuestra batería de conectivos sí es posible, la fórmula (p1 p2) responde a

esa tabla.

¿No podrá suceder que estemos en esa situación, es decir, que para tablas

suficientemente complejas, no existan fórmulas en nuestro lenguaje que se

comporten desde el punto de vista semántico como indica la tabla? Si así fuese,

tendríamos que intentar ampliar nuestro lenguaje agregándole conectivos.

2

Para nuestra tranquilidad, la respuesta a esta pregunta es: no solo tenemos los

conectivos suficientes como para hallar una fórmula que se comporte

semánticamente como indique cualquier tabla dada, sino que para eso nos sobran

conectivos. Veámoslo con un ejemplo, que se puede generalizar en forma obvia.

Supongamos que nos dan la tabla:

Debemos hallar una fórmula A que sea verdadera si p, q y r son verdaderas (caso 1,

primer renglón); o si p y r son verdaderas y q es falsa (caso 2, tercer renglón); o si

p, q, y r son falsas (caso 3, octavo renglón). Obsérvese que si se da el caso 1 o se da

el caso 2 o se da el caso 3, la fórmula será verdadera, y será falsa solo cuando no se

dé ninguno de los tres casos. Supongamos entonces que encontrásemos una

fórmula que represente el caso 1, es decir, sea verdadera si y solo si tanto p como q

como r sean verdaderas, a la que llamaremos C1, una fórmula que represente el

caso 2, o sea, que sea verdadera si y solo si p y r son verdaderas y q falsa, a la que

llamaremos C2, y una fórmula que represente el caso 3, es decir, que sea verdadera

si y solo si tanto p como q como r son falsas. Si esto fuese posible, es trivial

observar que la fórmula

C1˅C2˅C3

tendrá el mismo comportamiento semántico que el que le pedimos a A, o sea,

responderá a esa tabla de verdad. Entonces, el problema se reduce a encontrar C1,

C2 y C3.

Para hallar C1 debemos preguntarnos por una fórmula que solo sea verdadera en

un caso, a saber, cuando p, q y r son verdaderas. Es obvio, a partir del

comportamiento de la conjunción, que la fórmula (p˄q˄r) satisface lo pedido.

Para hallar C2 debemos preguntarnos por una fórmula que sea verdadera también

en un único caso, cuando p y r sean verdaderas y q falsa. El hecho de que sea

verdadera en un único caso nos hace pensar en la conjunción como un conectivo a

utilizar, pero obviamente, debemos hacer que esa conjunción sea verdadera

cuando q sea falsa, que es lo mismo que decir que será verdadera cuando p sea

p q r A V V V V V V F F V F V V V F F F F V V F F V F F F F V F F F F V

3

verdadera, la negación de q sea verdadera, y r sea verdadera. Por eso hallamos que

la fórmula (p˄¬q ˄ r) se comporta como esperamos que se comporte C2.

Para hallar C3 razonamos análogamente y concluimos que la fórmula (¬p˄¬q˄¬r)

se comporta como esperamos que lo haga C3.

Por lo tanto, la fórmula

(p˄q˄r)˅ (p˄¬q˄r)˅(¬p˄¬q˄¬r)

tiene la tabla de verdad, o sea el comportamiento semántico dado.

Es claro que el procedimiento se puede generalizar para tablas de cualquier

cantidad de variables, y también es claro que solo hemos utilizado 3 conectivos.

Solo queda un detalle. Si en la tabla de verdad no apareciera ninguna fila con valor

de verdad V (o sea, la fórmula buscada fuese una contradicción) el procedimiento

no sería aplicable. Pero en ese caso, cualquier contradicción nos sirve. Un conjunto

de conectivos que permite expresar el comportamiento semántico de cualquier

tabla se llama conjunto adecuado de conectivos. Acabamos de mostrar que {¬, ˅, ˄}

es un conjunto adecuado de conectivos.

Ejercicio: expresar los conectivos → y ↔ con el conjunto {¬, ˅, ˄}, o sea, hallar

fórmulas que solo usen estos tres últimos conectivos y tengan estas tablas:

p q A V V V V F F F V V F F V

p q A V V V V F F F V F F F V

Hay más: Es posible expresar la conjunción utilizando solo la disyunción y la

negación, como muestra la siguiente equivalencia que lleva el nombre del lógico De

Morgan

(pq) (pq)

4

Esto muestra que el conjunto {¬, ˅} es adecuado (toda conjunción puede

sustituirse por una expresión en la que solo aparecen la negación y la disyunción

sin alterar el comportamiento semántico).

Por ejemplo, podemos encontrar una fórmula equivalente a (p(qr)) usando

solo negación y disyunción a través de la siguiente cadena de equivalencias:

(p(qr))

(¬p˅(qr))

(¬p˅((qr)(rq)))

(¬p˅((qr)(rq)))

(¬p˅((qr)(rq))).

Encarecemos al lector verificar cada una de las equivalencias establecidas.

También es adecuado el conjunto {¬, ˄} (Demostrarlo).

Hay otros conjuntos adecuados, de los cuales {¬, →} es bastante usado en los textos

de lógica. (Para probarlo, basta demostrar que se puede hallar una expresión con

esos dos conectivos que se comporte igual que la conjunción o una que se

comporte igual que la disyunción. Es su deber moral resolver este ejercicio, si no lo

hace, su conciencia lo atormentará hasta el momento de salir del segundo parcial

de lógica).

Tal vez lo más curioso de todo sea que hay conjuntos adecuados de conectivos que

tienen un solo elemento. O sea, un solo conectivo que es capaz de producir

fórmulas con cualquier comportamiento semántico. Observe la siguiente tabla:

A B 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 V V V V V V F F F F V F V F V F V F V F V F F F F V V V V F F V V F V F F V V F V F F V F V F V V F V F F V F F F F V V V V F F F V F V V F V F

5

En ella tenemos representados todos los conectivos binarios posibles. Las

columnas en gris indican los que conocemos y a los que les hemos dado nombre.

Observe el lector la columna 5. En ella se representa un conectivo binario que tiene

este comportamiento y al que asignaremos el símbolo ↓:

p q p↓q V V F V F F F V F F F V

Este conectivo traduce bien al expresión “Tanto p como q son falsas” o “Ni p ni q”.

Lo llamaremos Nor (expresión inglesa que viene de que se puede expresar como la

negación de la disyunción). Pues bien, resulta ser que el conjunto {↓} es adecuado.

Para mostrarlo, basta demostrar que podemos expresar ¬ y ˅ solo con ↓.

Veámoslo:

Hagamos la tabla de p↓p:

p ↓ P V F V F V F

Esto muestra que ¬p es equivalente a p↓p.

Consideremos ahora la tabla de (p↓q)↓(p↓q)

(p ↓ q) ↓ (p ↓ q) V F V V V F V V F F V V F F F F V V F F V F V F F F V F

Esto muestra que p˅q es equivalente a (p↓q)↓(p↓q), y así, el conjunto {↓} es

suficiente.

Hay otro conjunto unitario suficiente, el formado por el conectivo que corresponde

a la columna 6 de la tabla donde se mostraban todos los conectivos binarios

posibles. Su símbolo es ∣ (la “barra de Scheffer”). Su tabla es

6

p q p∣q V V F V F V F V V F F V

Ejercicio: a) ¿A qué expresión del lenguaje corresponde? b) Demuestre que {∣} es

adecuado.

Una pregunta obvia es: ¿Por qué trabajamos con cinco conectivos si con uno solo

tendríamos la misma capacidad expresiva? La respuesta es también obvia: El uso

exclusivo de un único conectivo como el Nor resultaría en traducciones de

expresiones del lenguaje natural al lenguaje formal muy alejadas de nuestra

intuición, y sumamente largas, en general. Por ejemplo, para expresar la fórmula

(pq) con el Nor tendríamos:

q (q↓q), y

(pq) ((p↓q)↓(p↓q)) por lo que, finalmente

(pq) ((p↓(q↓q))↓(p↓(q↓q)))

La fórmula que hemos obtenido es muy poco legible, no tenemos intuición alguna

acerca de su comportamiento semántico y hasta podemos tener problemas para

reconocer de un vistazo su estructura sintáctica. Imagine el lector qué clase de

objeto inmanejable para seres humanos puede resultar al intentar expresar solo

con este conectivo una fórmula equivalente a otra que sea medianamente compleja

en nuestro lenguaje. Por lo tanto, restringirse a un único conectivo es una pésima

opción si uno quiere trabajar dentro del sistema –que es lo que deseamos hacer en

este curso-, pero puede ser una muy buena opción si lo que se desea es estudiar

resultados acerca del sistema. (Por ejemplo, las reglas de las interpretaciones, que

con nuestro lenguaje formal requieren de cinco incisos, si optásemos por hacer un

lenguaje con un único conectivo, solo requerirían un inciso. Por contrapartida,

representar un argumento dado en lenguaje natural en ese lenguaje de un solo

conectivo sería una tarea engorrosísima, así como la evaluación de la corrección

del argumento).

Se puede demostrar que esos dos son los únicos conjuntos adecuados de

conectivos binarios que tienen un solo elemento, pero para sentir el placer de ver

la demostración tienen dos opciones y media: o leen un libro de lógica que la

traiga, como Mendelson, o esperan a cursar Lógica 2 o, si están muy ansiosos, le

pueden preguntar a algún docente (que seguramente les responda que es un lindo

ejercicio para que lo piensen).

7

Ejercicios. (tomados de Logical Labyrinths, de R. Smullyan)

Una isla se llama isla booleana (en honor al matemático decimonónico George

Boole, que descubrió sus principios) si y solo si en ella se cumplen las siguientes

tres leyes:

N: Para todo habitante A hay un habitante que dice la verdad en aquellos días en

que A miente y solo en ellos.

C: Para todo par de habitantes A y B existe un habitante C que dice la verdad en

aquellos días en que tanto A como B dicen la verdad y solo en ellos.

D: Para todo par de habitantes A y B existe un habitante C que dice la verdad en

aquellos días en que o bien A dice la verdad, o bien B dice la verdad, o bien tanto A

como B dicen la verdad, y solo en esos días. (En otras palabras, C miente en

aquellos días en que tanto A como B mienten y solo en ellos).

1. ¿Puede existir una isla en la que se cumplan N y C pero no se cumpla D?

2. Si una isla cumple N y D, ¿es necesariamente booleana?

3. Hay una isla en la que se cumple N y se cumple además la condición

I: Para todo par de habitantes A y B existe un habitante C que dice la verdad en

aquellos días en que o bien A miente o bien dice la verdad, o se dan ambas cosas, y

solo en esos días.

¿Es esta isla booleana?

4. ¿Todas las islas booleanas cumplen la condición I?

5. Hay una isla en la que se cumplen las condiciones C, D, I, y además la condición

siguiente:

E: Para todo par de habitantes A y B existe un habitante que dice la verdad todos

los días en que A y B se comportan de la misma manera –es decir, ambos dicen la

verdad o ambos mienten- y solo en esos días.

¿Es necesariamente esta isla una isla booleana? ¿Se puede definir a partir de

, , , y ?

6. De una isla solo se sabe que se cumple la condición

J: Para todo par de habitantes A y B, existe un habitante C que dice la verdad en

aquellos días en que tanto A como B mienten y solo en ellos.

¿Es necesariamente booleana esta isla?

7. ¿Qué tiene que ver este ejercicio con conjuntos suficientes de conectivas y con

interdefinibilidad de conectivos?