La estrecha relaci´on existente entre la matem´atica moderna y la l´ogica formal es una de sus caracter´ısticas fundamentales. La l´ogica aristot´elica era insuficiente para la creaci´on matem´atica ya que la mayor parte de los argumentos utilizados en ´esta contienen enunciados del tipo “si, entonces”, absolutamente extra˜nos en aquella. En esta primera lecci´on de l´ogica estudiaremos uno de los dos niveles en los que se desenvuelve la moderna l´ogica formal: la l´ogica de enunciados o de proposiciones. 1.1 Proposiciones y Tablas de Verdad En el desarrollo de cualquier teor´ıa matem´atica se hacen afirmaciones en forma de frases y que tienen un sentido pleno. Tales afirmaciones, verbales o escritas, las denominaremos enunciados o proposiciones. 1.1.1 Proposici´on Llamaremos de esta forma a cualquier afirmaci´on que sea verdadera o falsa, pero no ambas cosas a la vez. Ejemplo 1.1 Las siguientes afirmaciones son proposiciones. (a) Gabriel Garc´ıa M´arquez escribi´o Cien a˜nos de soledad. (b) 6 es un n´umero primo. (c) 3+2=6 (d) 1 es un n´umero entero, pero 2 no lo es. Nota 1.1 Las proposiciones se notan con letras min´usculas, p, q, r . . . . . . La notaci´on p :Tres m´as cuatro es igual a siete se utiliza para definir que p es la proposici´on “tres m´as cuatro es igual a siete”. Este tipo de proposiciones se llaman simples, ya que no pueden descomponerse en otras. Ejemplo 1.2 Las siguientes no son proposiciones. (a) x + y > 5 (b) ¿Te vas? (c) Compra cinco azules y cuatro rojas. (d) x = 2 Soluci´on En efecto, (a) es una afirmaci´on pero no es una proposici´on ya que ser´a verdadera o falsa dependiendo de los valores de x e y e igual ocurre con la afirmaci´on (d). Los ejemplos (b) y (c) no son afirmaciones, por lo tanto no son proposiciones. Desde el punto de vista l´ogico carece de importancia cual sea el contenido material de los enunciados, solamente interesa su valor de verdad. 2 L´ogica Matem´atica Francisco Jos´e Gonz´alez Guti´errez 1.1.2 Valor de Verdad Llamaremos valor verdadero o de verdad de una proposici´on a su veracidad o falsedad. El valor de verdad de una proposici´on verdadera es verdad y el de una proposici´on falsa es falso. Ejemplo 1.3 D´ıgase cu´ales de las siguientes afirmaciones son proposiciones y determinar el valor de verdad de aquellas que lo sean. (a) p: Existe Premio Nobel de inform´atica. (b) q: La tierra es el ´unico planeta del Universo que tiene vida. (c) r: Teclee Escape para salir de la aplicaci´on. (d) s: Cinco m´as siete es grande. Soluci´on (a) p es una proposici´on falsa, es decir su valor de verdad es Falso. (b) No sabemos si q es una proposici´on ya que desconocemos si esta afirmaci´on es verdadera o falsa. (c) r no es una proposici´on ya que no es verdadera ni es falsa. Es un mandato. (d) s no es una proposici´on ya que su enunciado, al carecer de contexto, es ambiguo. En efecto, cinco ni˜nas m´as siete ni˜nos es un n´umero grande de hijos en una familia, sin embargo cinco monedas de cinco cinco c´entimos m´as siete monedas de un c´entimo no constituyen una cantidad de dinero grande. 1.1.3 Proposici´on Compuesta Si las proposiciones simples p1, p2, . . . , pn se combinan para formar la proposici´on P, diremos que P la es una proposici´on compuesta de p1, p2, . . . , pn. Ejemplo 1.4 “La Matem´atica Discreta es mi asignatura preferida y Mozart fue un gran compositor” es una proposici´on compuesta por las proposiciones “La Matem´atica Discreta es mi asignatura preferida” y “Mozart fue un gran compositor”. “El es inteligente o estudia todos los d´ıas” es una proposici´on compuesta por dos proposiciones: “El es inteligente” y “El estudia todos los d´ıas”. Nota 1.2 La propiedad fundamental de una proposici´on compuesta es que su valor de verdad est´a completamente determinado por los valores de verdad de las proposiciones que la componen junto con la forma en que est´an conectadas. 1.1.4 Variables de Enunciado Es una proposici´on arbitraria con un valor de verdad no especificado, es decir, puede ser verdad o falsa. En el c´alculo l´ogico, prescindiremos de los contenidos de los enunciados y los sustituiremos por variables de enunciado. Toda variable de enunciado p, puede ser sustituida por cualquier enunciado siendo sus posibles estados, verdadero o falso. El conjunto de los posibles valores de una proposici´on p, los representaremos en las llamadas tablas de verdad, ideadas por L.Wittgenstein1. 1Ludwig Wittgenstein (Viena 1889-Cambridge 1951), nacionalizado brit´anico en 1938. Estudi´o Ingenier´ıa Mec´anica en 3 Universidad de C´adiz Departamento de Matem´aticas 1.1.5 Tablas de Verdad La tabla de verdad de una proposici´on compuesta P enumera todas las posibles combinaciones de los valores de verdad para las proposiciones p1, p2, . . . , pn. Ejemplo 1.5 Por ejemplo, si P es una proposici´on compuesta por las proposiciones simples p1, p2 y p3, entonces la tabla de verdad de P deber´a recoger los siguientes valores de verdad. p1 p2 p3 V V V V V F V F V V F F F V V F V F F F V F F F 1.2 Conexi´on entre Proposiciones Estudiamos en este apartado las distintas formas de conectar proposiciones entre s´ı. Prestaremos especial atenci´on a las tablas de verdad de las proposiciones compuestas que pueden formarse utilizando las distintas conexiones. 1.2.1 Conjunci´on Dadas dos proposiciones cualesquiera p y q, llamaremos conjunci´on de ambas a la proposici´on compuesta “p y q” y la notaremos p ^ q. Esta proposici´on ser´a verdadera ´unicamente en el caso de que ambas proposiciones lo sean. Obs´ervese que de la definici´on dada se sigue directamente que si p y q son, ambas, verdaderas entonces p ^ q es verdad y que si al menos una de las dos es falsa, entonces p ^ q es falsa. Por lo tanto su tabla de verdad vendr´a dada por p q V V V F F V F F p ^ q V F F F Obs´ervese tambi´en que el razonamiento puede hacerse a la inversa, es decir si p ^ q es verdad, entonces p y q son, ambas, verdad y que si p ^ q es falsa, entonces una de las dos ha de ser falsa. Berlin, posteriormente investig´o Aeron´autica en Manchester. La necesidad de entender mejor las matem´aticas lo llev´o a estudiar sus fundamentos. Dej´o Manchester en 1811 para estudiar l´ogica matem´atica con Russell en Cambridge. Escribi´o su primer gran trabajo en l´ogica, Tractatus logico-philosophicus, durante la primera guerra mundial, primero en el frente ruso y luego en el norte de Italia. Envi´o el manuscrito a Russell desde un campo de prisioneros en Italia. Liberado en 1919, regal´o la fortuna que hab´ıa heredado de su familia y trabaj´o en Austria como profesor en una escuela primaria. Volvi´o a Cambridge en 1929 y fue profesor en esta universidad hasta 1947, a˜no en que renunci´o. Su segundo gran trabajo, Investigaciones filos´oficas fue publicado en 1953, es decir, dos a˜nos despu´es de su muerte. Otras obras p´ostumas de Wittgenstein son: Observaciones filos´oficas sobre los principios de la matem´atica(1956), Cuadernos azul y marr´on(1958) y Lecciones y conversaciones sobre est´etica, sicolog´ıa y fe religiosa(1966). 4 L´ogica Matem´atica Francisco Jos´e Gonz´alez Guti´errez 1.2.2 Disyunci´on Dadas dos proposiciones cualesquiera p y q, llamaremos disyunci´on de ambas a la proposici´on compuesta “p ´o q” y la notaremos p _ q. Esta proposici´on ser´a verdadera si al menos una de las dos p ´o q lo es. De acuerdo con la definici´on dada se sigue que si una de las dos, p ´o q, es verdad entonces p_q es verdad y que p _ q ser´a falsa, ´unicamente si ambas lo son. Su tabla de verdad ser´a, por tanto, p q V V V F F V F F p _ q V V V F Al igual que en la conjunci´on, podemos razonar en sentido inverso. En efecto, si p_q es verdad, entonces una de las dos, al menos, ha de ser verdad y si p _ q es falsa, entonces ambas han de ser falsas. La palabra “o” se usa en el lenguaje ordinario de dos formas distintas. A veces se utiliza en el sentido de “p ´o q, ´o ambos”, es decir, al menos una de las dos alternativas ocurre y, a veces es usada en el sentido de “p ´o q, pero no ambos” es decir, ocurre exactamente una de de las dos alternativas. Por ejemplo, la proposici´on “El ir´a a Madrid o a Bilbao” usa “o” con el ´ultimo sentido. A este tipo de disyunci´on la llamaremos disyunci´on exclusiva. 1.2.3 Disyunci´on Exclusiva Dadas dos proposiciones cualesquiera p y q, llamaremos disyunci´on exclusiva de ambas a la proposici´on compuesta “p ´o q pero no ambos” y la notaremos p Y q. Esta proposici´on ser´a verdadera si una u otra, pero no ambas son verdaderas. Seg´un esta definici´on una disyunci´on exclusiva de dos proposiciones p y q ser´a verdadera cuando tengan distintos valores de verdad y falsa cuando sus valores de verdad sean iguales. Su tabla de verdad es, por tanto, p q V V V F F V F F p Y q F V V F Haciendo el razonamiento contrario si p Y q es verdad, ´unicamente podemos asegurar que una de las dos es verdad y si p Y q es falsa, s´olo podemos deducir que ambas tienen el mismo valor de verdad. Nota 1.3 Salvo que especifiquemos lo contrario, “o” ser´a usado en el primero de los sentidos. Esta discusi´on pone de manifiesto la precisi´on que ganamos con el lenguaje simb´olico: p _ q est´a definida por su tabla de verdad y siempre significa p y/´o q. 1.2.4 Negaci´on Dada una proposici´on cualquiera, p, llamaremos “negaci´on de p” a la proposici´on “no p” y la notaremos ¬p. Ser´a verdadera cuando p sea falsa y falsa cuando p sea verdadera. 5 Universidad de C´adiz Departamento de Matem´aticas La tabla de verdad de esta nueva proposici´on, ¬p, es: p V F ¬p F V De esta forma, el valor verdadero de la negaci´on de cualquier proposici´on es siempre opuesto al valor verdadero de la afirmaci´on original. Ejemplo 1.6 Estudiar la veracidad o falsedad de las siguientes proposiciones: p1: El Pentium es un microprocesador. p2: Es falso que el Pentium sea un microprocesador. p3: El Pentium no es un microprocesador. p4: 2 + 2 = 5 p5: Es falso que 2 + 2 = 5 p6: 2 + 2 = 4 Soluci´on X p2 y p3 son, cada una, la negaci´on de p1. X p5 y p6 son, cada una, la negaci´on de p4. Pues bien, de acuerdo con la tabla de verdad para la negaci´on, tendremos: X p1 es verdad, luego p2 y p3 son falsas. X p4 es falsa, luego p5 y p6 son verdad. Ejemplo 1.7 Construir la tabla de verdad de la proposici´on ¬(p ^ ¬q). Soluci´on p q ¬q p ^ ¬q V V F F V F V V F V F F F F V F ¬(p ^ ¬q) V F V V Existen proposiciones que son verdaderas (falsas) simplemente por su forma l´ogica y no por su contenido. 6 L´ogica Matem´atica Francisco Jos´e Gonz´alez Guti´errez 1.2.5 Tautolog´ıas y Contradicciones Sea P una proposici´on compuesta de las proposiciones simples p1, p2, . . . , pn P es una Tautolog´ıa si es verdadera para todos los valores de verdad que se asignen a p1, p2, . . . , pn. P es una Contradicci´on si es falsa para todos los valores de verdad que se asignen a p1, p2, . . . , pn. En adelante, notaremos por “C” a una contradicci´on y por “T” a una tautolog´ıa. Una proposici´on P que no es tautolog´ıa ni contradicci´on se llama, usualmente, Contingencia. Ejemplo 1.8 Probar que la proposici´on compuesta p _ ¬p es una tautolog´ıa y la p ^ ¬p es una contradicci ´on. Soluci´on En efecto: p ¬p V F F V p _ ¬p V V p ^ ¬p F F Obs´ervese que p _ ¬p es verdad, independientemente de quienes sean las variables de enunciado, p y ¬p y lo mismo ocurre con la falsedad de p ^ ¬p. 1.2.6 Proposici´on Condicional Dadas dos proposiciones p y q, a la proposici´on compuesta “si p, entonces q” se le llama “proposici´on condicional” y se nota por p −! q A la proposici´on “p” se le llama hip´otesis, antecedente, premisa o condici´on suficiente y a la “q” tesis, consecuente, conclusi´on o condici´on necesaria del condicional. Una proposici´on condicional es falsa ´unicamente cuando siendo verdad la hip´otesis, la conclusi´on es falsa (no se debe deducir una conclusi´on falsa de una hip´otesis verdadera). De acuerdo con esta definici´on su tabla de verdad es, p q V V V F F V F F p −! q V F V V Obs´ervese que si p −! q es verdad no puede deducirse pr´acticamente nada sobre los valores de verdad de p y q ya que pueden ser ambas verdad, ambas falsas o la primera falsa y la segunda verdad. Ahora bien, si el condicional p −! q es falso, entonces podemos asegurar que p es verdadera y q falsa. Otras formulaciones equivalentes de la proposici´on condicional p −! q son: 7 Universidad de C´adiz Departamento de Matem´aticas “p s´olo si q”. “q si p”. “p es una condici´on suficiente para q”. “q es una condici´on necesaria para p”. “q se sigue de p”. “q a condici´on de p”. “q es una consecuencia l´ogica de p” . “q cuando p”. Analizaremos con detalle cada uno de los cuatro casos que se presentan en la tabla de verdad. 1. Antecedente y consecuente verdaderos. En este caso parece evidente que el condicional “si p, entonces q” se eval´ue como verdadero. Por ejemplo, “Si como mucho, entonces engordo” es una sentencia que se eval´ua como verdadera en el caso de que tanto el antecedente como el consecuente sean verdaderos. Ahora bien, obs´ervese que ha de evaluarse tambi´en como verdadero un condicional en el que no exista una relaci´on de causa entre el antecedente y el consecuente. Por ejemplo, el condicional “Si Garc´ıa Lorca fue un poeta, entonces Gauss fue un matem´atico” ha de evaluarse como verdadero y no existe relaci´on causal entre el antecedente y el consecuente. Es por esta raz´on que no hay que confundir el condicional con la implicaci´on l´ogica. “Garc´ıa Lorca fue un poeta implica que Gauss fue un matem´atico” Es una implicaci´on falsa desde el punto de vista l´ogico. M´as adelante estudiaremos la implicaci´on l´ogica. 2. Antecedente verdadero y consecuente falso. En este caso parece natural decir que el condicional se eval´ua como falso. Por ejemplo, supongamos que un pol´ıtico aspirante a Presidente del Gobierno promete: “Si gano las elecciones, entonces bajar´e los impuestos” Este condicional ser´a falso s´olo si ganando las elecciones, el pol´ıtico no baja los impuestos. A nadie se le ocurrir´ıa reprochar al pol´ıtico que no ha bajado los impuestos si no ha ganado las elecciones. Obs´ervese que el hecho de que p sea verdadero y, sin embargo, q sea falso viene, en realidad, a refutar la sentencia p −! q, es decir la hace falsa. 3. Antecedente falso y consecuente verdadero. Nuestro sentido com´un nos indica que el condicional p −! q no es, en este caso, ni verdadero ni falso. Parece il´ogico preguntarse por la veracidad o falsedad de un condicional cuando la condici´on expresada por el antecedente no se cumple. Sin embargo, esta respuesta del sentido com´un no nos sirve, estamos en l´ogica binaria y todo ha de evaluarse bien como verdadero, bien como falso, es decir, si una sentencia no es verdadera, entonces es falsa y viceversa. Veamos que en el caso que nos ocupa, podemos asegurar que el condicional no es falso. En efecto, como dijimos anteriormente, p −! q es lo mismo que afirmar que 8 L´ogica Matem´atica Francisco Jos´e Gonz´alez Guti´errez “p es una condici´on suficiente para q” es decir, p no es la ´unica condici´on posible, por lo cual puede darse el caso de que q sea verdadero siendo p falso. O sea, la falsedad del antecedente no hace falso al condicional y si no lo hace falso, entonces lo hace verdadero. Por ejemplo, “Si estudio mucho, entonces me canso” ¿Qu´e ocurrir´ıa si no estudio y, sin embargo, me cansara? Pues que la sentencia no ser´ıa inv´alida, ya que no se dice que no pueda haber otros motivos que me puedan producir cansancio. 4. Antecedente y consecuente falsos. La situaci´on es parecida a la anterior. La condici´on p no se verifica, es decir, es falsa, por lo que el consecuente q puede ser tanto verdadero como falso y el condicional, al no ser falso, ser´a verdadero. Obs´ervese, anecd´oticamente, que es muy frecuente el uso de este condicional en el lenguaje coloquial, cuando se quiere se˜nalar que, ante un dislate, cualquier otro est´a justificado. “Si t´u eres programador, entonces yo soy el due˜no de Microsoft” Ejemplo 1.9 Sean p, q y r las proposiciones “El n´umero N es par”, “La salida va a la pantalla” y “Los resultados se dirigen a la impresora”, respectivamente. Enunciar las formulaciones equivalentes de las siguientes proposiciones. (a) q −! p. (b) ¬q −! r. (c) r −! (p _ q). Soluci´on (a) q −! p. − Si la salida va a la pantalla, entonces el n´umero N es par. − La salida ir´a a la pantalla, s´olo si el n´umero N es par. − El n´umero N es par si la salida va a la pantalla. − Una condici´on suficiente para que el n´umero N sea par es que la salida vaya a la pantalla. − Una condici´on necesaria para que la salida vaya a la pantalla es que el n´umero N sea par. (b) ¬q −! r. − Si la salida no va a la pantalla, entonces los resultados se dirigen a la impresora. − La salida no va a la pantalla s´olo si los resultados se dirigen a la impresora. − Los resultados se dirigen a la impresora si la salida no va a la pantalla. − Una condici´on suficiente para que los resultados se dirijan a la impresora es que la salida no vaya a la pantalla. − Una condici´on necesaria para que la salida no vaya a la pantalla es que los resultados se dirijan a la impresora. (c) r −! (p _ q). − Si los resultados se dirigen a la impresora, entonces el n´umero N es par o la salida va a la pantalla. − Los resultados se dirigen a la impresora s´olo si el n´umero N es par o la salida vaya a la pantalla. 9 Universidad de C´adiz Departamento de Matem´aticas − El n´umero N es par o la salida va a la pantalla si los resultados se dirigen a la impresora. − Una condici´on suficiente para que el n´umero N sea par o la salida vaya a la pantalla es que los resultados se dirijan a la impresora. − Una condici´on necesaria para que los resultados se dirijan a la impresora es que el n´umero N sea par o que la salida vaya a la pantalla. Ejemplo 1.10 Sean las proposiciones p : Est´a nevando. q : Ir´e a la ciudad. r : Tengo tiempo. (a) Escribir, usando conectivos l´ogicos, una proposici´on que simbolice cada una de las afirmaciones siguientes: (a.1) Si no est´a nevando y tengo tiempo, entonces ir´e a la ciudad. (a.2) Ir´e a la ciudad s´olo si tengo tiempo. (a.3) No est´a nevando. (a.4) Est´a nevando, y no ir´e a la ciudad. (b) Enunciar las afirmaciones que se corresponden con cada una de las proposiciones siguientes: (b.1) q ! (r ^ ¬p) (b.2) r ^ q (b.3) (q −! r) ^ (r −! q) (b.4) ¬(r _ q) Soluci´on (a) Escribimos en forma simb´olica las afirmaciones propuestas. (a.1) (¬p ^ r) −! q (a.2) q −! r (a.3) ¬p (a.4) p ^ ¬q (b) Escribimos en forma de afirmaciones las proposiciones. (b.1) Ir´e a la ciudad si, y s´olo si tengo tiempo y no est´a nevando. (b.2) Tengo tiempo e ir´e a la ciudad. (b.3) Ir´e a la ciudad si y s´olo si tengo tiempo. (b.4) Ni tengo tiempo, ni ir´e a la ciudad. 1.2.7 Proposici´on Rec´ıproca Dada la proposici´on condicional p −! q, su rec´ıproca es la proposici´on, tambi´en condicional, q −! p. Por ejemplo, la rec´ıproca de “Si la salida no va a la pantalla, entonces los resultados se dirigen a la impresora” ser´a “Si los resultados se dirigen a la impresora, entonces la salida no va a la pantalla”. 10 L´ogica Matem´atica Francisco Jos´e Gonz´alez Guti´errez 1.2.8 Proposici´on Contrarrec´ıproca Dada la proposici´on condicional p −! q, su contrarrec´ıproca es la proposici´on, tambi´en condicional, ¬q −! ¬p. Por ejemplo, la contrarrec´ıproca de la proposici´on “Si Mar´ıa estudia mucho, entonces es buena estudiante” es “Si Mar´ıa no es buena estudiante, entonces no estudia mucho”. Ejemplo 1.11 Escribir la rec´ıproca y la contrarrec´ıproca de cada una de las afirmaciones siguientes: (a) Si llueve, no voy. (b) Me quedar´e, s´olo si t´u te vas. (c) Si tienes cien pesetas, entonces puedes comprar un helado. (d) No puedo completar la respuesta si no me ayudas. Soluci´on Escribiremos la rec´ıproca y la contrarrec´ıproca de varias formas. (a) Si llueve, no voy. Rec´ıproca. − Si no voy, entonces llueve. − Llueve si no voy. − Una condici´on necesaria para no ir es que llueva. − Una condici´on suficiente para que llueva es no ir. Contrarrec´ıproca. − Si voy, entonces no llueve. − Voy s´olo si no llueve. − Es necesario que no llueva, para que vaya. − Es suficiente que vaya para que no llueva. (b) Me quedar´e s´olo si te vas. Rec´ıproca. − Si te vas, entonces me quedar´e. − Me quedar´e, si te vas. − Una condici´on necesaria para que te vayas, es quedarme. − Una condici´on suficiente para quedarme es que te vayas. Contrarrec´ıproca. − Si no te vas, entonces no me quedar´e. − No me quedar´e si no te vas. − Es suficiente que no te vayas, para no quedarme. (c) No puedo completar la respuesta si no me ayudas. Rec´ıproca. − Si no puedo completar la respuesta, entonces no me ayudas. Contrarrec´ıproca. − Si puedo completar la respuesta, entonces me ayudas. − Puedo completar la respuesta s´olo si me ayudas. − Es necesario que ayudes para poder completar la respuesta. 11 Universidad de C´adiz Departamento de Matem´aticas 1.2.9 Proposici´on bicondicional Dadas dos proposiciones p y q, a la proposici´on compuesta “p si y s´olo si q” se le llama “proposici´on bicondicional” y se nota por p ! q La interpretaci´on del enunciado es: p s´olo si q y p si q o lo que es igual si p, entonces q y si q, entonces p es decir, (p −! q) ^ (q −! p) Por tanto, su tabla de verdad es: p q p −! q q −! p V V V V V F F V F V V F F F V V p ! q V F F V Luego la proposici´on bicondicional p ! q es verdadera ´unicamente en caso de que ambas proposiciones, p y q, tengan los mismos valores de verdad. Nota 1.4 Obs´ervese que la proposici´on condicional p −! q, se enunciaba Si p, entonces q siendo una formulaci´on equivalente, Una condici´on necesaria para p es q y la proposici´on condicional q −! p, se enunciaba Si q, entonces p siendo una formulaci´on equivalente, Una condici´on suficiente para p es q Por tanto, una formulaci´on equivalente de la proposici´on bicondicional en estos t´erminos, ser´ıa: Una condici´on necesaria y suficiente para p es q 12 L´ogica Matem´atica Francisco Jos´e Gonz´alez Guti´errez Ejemplo 1.12 Sean a, b y c las longitudes de los lados de un tri´angulo T siendo c la longitud mayor. El enunciado T es rect´angulo si, y s´olo si a2 + b2 = c2 puede expresarse simb´olicamente como p ! q donde p es la proposici´on “T es rect´angulo” y q la proposici´on “a2 + b2 = c2”. Observemos lo siguiente: La proposici´on anterior afirma dos cosas 1. Si T es rect´angulo, entonces a2 + b2 = c2 o tambi´en, Una condici´on necesaria para que T sea rect´angulo es que a2 + b2 = c2 2. Si a2 + b2 = c2, entonces T es rect´angulo o tambi´en, Una condici´on suficiente para que T sea rect´angulo es que a2 + b2 = c2 Consecuentemente, una forma alternativa de formular la proposici´on dada es Una condici´on necesaria y suficiente para que T sea rect´angulo es que a2 + b2 = c2 Nota 1.5 Los valores de verdad de una proposici´on compuesta, pueden determinarse a menudo, construyendo una tabla de verdad abreviada. Por ejemplo, si queremos probar que una proposici´on es una contingencia, es suficiente con que consideremos dos l´ıneas de su tabla de verdad, una que haga que la proposici´on sea verdad y otra que la haga falsa. Para determinar si una proposici´on es una tautolog´ıa, bastar´ıa considerar, ´unicamente, aquellas l´ıneas para las cuales la proposici´on pueda ser falsa. Ejemplo 1.13 Consideremos el problema de determinar si la proposici´on (p^q) −! p es una tautolog´ıa. Soluci´on Construimos su tabla de verdad. p q p ^ q V V V V F F F V F F F F (p ^ q) −! p V V V V Luego, en efecto, (p ^ q) −! p es una tautolog´ıa. Observemos ahora lo siguiente: Una proposici´on condicional s´olo puede ser falsa en caso de que siendo la hip´otesis verdadera, la conclusi´on sea falsa, por tanto si queremos ver si (p ^ q) −! p es una tautolog´ıa, bastar´ıa comprobar los casos en que p ^q sea verdad, ya que si es falsa, entonces (p ^q) −! p es verdad, consecuentemente una tabla de verdad abreviada para este ejercicio ser´ıa: p q p ^ q V V V (p ^ q) −! p V 13 Universidad de C´adiz Departamento de Matem´aticas Ejemplo 1.14 Establecer si las siguientes proposiciones son tautolog´ıas, contingencias o contradicciones. (a) (p −! q) ^ (q −! p) (b) [p ^ (q _ r)] −! [(p ^ q) _ (p ^ r)] (c) (p _ ¬q) −! q (d) p −! (p _ q) (e) (p ^ q) −! p (f) [(p ^ q) ! p] −! (p ! q) (g) [(p −! q) _ (r −! s)] −! [(p _ r) −! (q _ s)] Soluci´on (a) (p −! q) ^ (q −! p) p q p −! q q −! p V V V V V F F V F V V F F F V V (p −! q) ^ (q −! p) V F F V Luego es una contingencia. (b) [p ^ (q _ r)] −! [(p ^ q) _ (p ^ r)] Haremos una tabla de verdad abreviada. La proposici´on condicional s´olo es falsa cuando siendo verdad la hip´otesis, la conclusi´on es falsa. Ahora bien, la hip´otesis es verdad cuando lo sean, a un tiempo, p y q _ r y ´esta es verdad si, al menos, una de las dos q o r lo es, entonces p q r q _ r p ^ (q _ r) p ^ q p ^ r (p ^ q) _ (p ^ r) V V F V V V F V V F V V V F V V V V V V V V V V −! V V V Por tanto, la proposici´on es una tautolog´ıa. (c) (p _ ¬q) −! q p q ¬q p _ ¬q V V F V V F V V F V F F F F V V (p _ ¬q) −! q V F V F luego la proposici´on es una contingencia. (d) p −! (p _ q) Esta proposici´on ser´a falsa ´unicamente cuando siendo verdad p, p _ q sea falsa, pero si p es verdad, entonces p _ q es verdad independientemente del valor de verdad de q, luego una tabla de verdad abreviada ser´a 14 L´ogica Matem´atica Francisco Jos´e Gonz´alez Guti´errez p p _ q V V p −! (p _ q) V y la proposici´on es una tautolog´ıa. (e) (p ^ q) −! p Haremos una tabla de verdad abreviada. la proposici´on condicional, ´unicamente, es falsa cuando siendo p ^ q verdad, la conclusi´on p es falsa, pero p ^ q es verdad, ´unicamente, cuando ambas, p y q, lo son, luego, p q p ^ q V V V (p ^ q) −! p V es decir, la proposici´on es una tautolog´ıa. (f) [(p ^ q) ! p] −! (p ! q) p q p ^ q (p ^ q) ! p p ! q V V V V V V F F F F F V F V F F F F V V [(p ^ q) ! p] −! (p ! q) V V F V luego la proposici´on es una contingencia. (g) [(p −! q) _ (r −! s)] −! [(p _ r) −! (q _ s)] La proposici´on condicional ´unicamente es falsa cuando siendo verdad la hip´otesis es falsa la conclusi ´on. Por el mismo argumento (p _ r) −! (q _ s) es falsa cuando siendo p _ r verdad sea q _ s sea falsa, y ´esta es falsa cuando ambas, q y s, lo son. Ahora bien, para que la conclusi´on (p _ r) −! (q _ s) sea falsa, y utilizando el mismo argumento, p_r ha de ser verdad y q _s falsa, luego p y r han de ser una de las dos, al menos, verdad mientras q y s han de ser, las dos, falsas. Haremos, pues, una tabla de verdad abreviada que recoja ´unicamente estos casos. p q r s (p −! q) _ (r −! s) (p _ r) −! (q _ s) V F V F (F) F (F) (V ) F (F) V F F F (F) V (V ) (V ) F (F) F F V F (V ) V (F) (V ) F (F) −! V F F y, consecuentemente, la proposici´on es una contingencia. 1.3 Implicaci´on Estudiamos en este apartado la implicaci´on l´ogica entre dos proposiciones. 1.3.1 Implicaci´on L´ogica Se dice que la proposici´on P implica l´ogicamente la proposici´on Q, y se escribe P =) Q, si Q es verdad cuando P es verdad. Obs´ervese que esto es equivalente a decir que P =) Q es falso si P es falso cuando Q es falso, ya que si P es verdad siendo Q falso, no se cumplir´ıa la definici´on anterior. 15 Universidad de C´adiz Departamento de Matem´aticas Ejemplo 1.15 Dadas las proposiciones p y q, demostrar que la negaci´on de p ´o q implica l´ogicamente la negaci´on de p. Soluci´on Lo que se pide es probar que ¬(p _ q) =) ¬p, es decir si cada vez que ¬(p _ q) es verdad, ¬p tambi´en lo es. En efecto, si ¬(p _ q) es verdad, entonces p _ q es falso, de aqu´ı que p sea falso y, consecuentemente, ¬p sea verdad. Tambi´en podemos decir que si ¬p es falso, entonces p es verdad, luego p _ q es verdad (cualquiera que sea el valor de verdad de q) y, por lo tanto, ¬(p _ q) es falso. Nota 1.6 Ahora podremos entender algo mejor lo que coment´abamos en 1. de 1.2.6. En efecto, de que “Garc´ıa Lorca fue un poeta” sea verdad no puede deducirse que Gauss fuera matem´atico, aunque lo fue y muy bueno. De todas formas, es cierto que existe una semejanza entre el s´ımbolo =) para la implicaci´on l´ogica y el s´ımbolo −! para la proposici´on condicional. Esta semejanza es intencionada y debido a la manera en que se usa el t´ermino implica, en el lenguaje ordinario es natural leer p −! q como “p implica q”. El siguiente teorema justifica este proceder. 1.3.2 Implicaci´on L´ogica y Proposici´on Condicional La proposici´on P implica l´ogicamente la proposici´on Q si, y s´olo si la proposici´on condicional P −! Q es una tautolog´ıa. Demostraci´on Veamos que P =) Q s´olo si P −! Q es una tautolog´ıa. En efecto, supongamos que P implica l´ogicamente Q. Entonces, de acuerdo con la definici´on, cuando P es verdad, Q tambi´en lo es y cuando Q es falso, P es falso, por tanto, la tabla de verdad de P −! Q conteniendo ´unicamente estas opciones es: P Q V V F F P −! Q V V es decir, P −! Q es una tautolog´ıa. Rec´ıprocamente, veamos que P =) Q si P −! Q es una tautolog´ıa. En efecto, si P es verdad y P −! Q es una tautolog´ıa entonces Q ha de ser verdad. Tambi´en podr´ıamos haber dicho que si Q es falso y P −! Q es una tautolog´ıa, entonces P ha de ser falso. Debido a este teorema, los l´ogicos prefieren adoptar el lenguaje com´un como el lenguaje de la l´ogica y leen p −! q como “p implica q”. En este caso, ellos utilizan la palabra implica como el nombre de un conectivo l´ogico y como el nombre de una relaci´on paralela entre proposiciones. Nota 1.7 Resolvemos ahora el ejemplo anterior viendo que ¬(p_q) −! ¬p es una tautolog´ıa. Su tabla de verdad es: 16 L´ogica Matem´atica Francisco Jos´e Gonz´alez Guti´errez p q p _ q ¬(p _ q) ¬p V V V F F V F V F F F V V F V F F F V V ¬(p _ q) −! ¬p V V V V luego, ¬(p _ q) −! ¬p es, efectivamente, una tautolog´ıa. 1.3.3 Implicaciones L´ogicas m´as Comunes La tabla siguiente presenta algunas implicaciones l´ogicas con los nombres que usualmente reciben. X Adici´on. P =) (P _ Q) X Simplif icaci´on. (P ^ Q) =) P X Ley del Modus Ponendo Ponens (Modus Ponens). Dado un condicional y af irmando (“Ponendo”) el antecedente, se puede af irmar (“Ponens”) el consecuente. [(P −! Q) ^ P] =) Q X Ley del Modus Tollendo Tollens (Modus Tollens). Dado un condicional y negando (“Tollendo”) el consecuente, se puede negar (“Tollens”) el antecedente. [(P −! Q) ^ ¬Q] =) ¬P X Leyes de los Silogismos Hipot´eticos. [(P −! Q) ^ (Q −! R)] =) (P −! R) [(P ! Q) ^ (Q ! R)] =) (P ! R) X Leyes de los silogismos disyuntivos. [¬P ^ (P _ Q)] =) Q [P ^ (¬P _ ¬Q] =) ¬Q X Ley del Dilema Constructivo. [(P −! Q) ^ (R −! S) ^ (P _ R)] =) (Q _ S) X Contradicci´on. (P −! C) =) ¬P Ejemplo 1.16 Verificar las leyes de los silogismos disyuntivos. Soluci´on (a) ¬P ^ (P _ Q) =) Q. En efecto, si ¬P ^ (P _ Q) es verdad, entonces ¬P es verdad y P _ Q es verdad, de aqu´ı que P sea falso y P _ Q verdad, por lo tanto, Q ha de ser verdad. Tambi´en, si hacemos la tabla de verdad del condicional ¬P ^ (P _ Q) −! Q, 17 Universidad de C´adiz Departamento de Matem´aticas P Q P _ Q ¬P ¬P ^ (P _ Q) V V V F F V F V F F F V V V V F F F V F ¬P ^ (P _ Q) −! Q V V V V observamos que es una tautolog´ıa luego por el teorema 1.3.2 ¬P ^(P _Q) implica l´ogicamente ¬Q. (b) [P ^ (¬P _ ¬Q)] =) ¬Q. En efecto, si P ^ (¬P _ ¬Q) es verdad, entonces P y ¬P _ ¬Q son verdad, luego ¬P es falso y ¬P _ ¬Q verdad, por lo tanto, ¬Q es verdad. Tambi´en, haciendo una tabla de verdad igual que en el apartado anterior. P Q ¬P ¬Q ¬P _ ¬Q P ^ (¬P _ ¬Q) V V F F F F V F F V V V F V V F V F F F V V V F P ^ (¬P _ ¬Q) −! Q V V V V se observa que P ^(¬P _¬Q) −! ¬Q es una tautolog´ıa luego, por 1.3.2, P ^(¬P _¬Q) =) ¬Q Ejemplo 1.17 Demostrar la implicaci´on l´ogica (P −! Q) ^ ¬Q =) ¬P (Ley del Modus Tollendo Tollens). Soluci´on Veamos que ¬P es verdad cuando (P −! Q) ^ ¬Q es verdad. En efecto, si (P −! Q)^¬Q es verdad, entonces P −! Q ha se ser verdad y ¬Q tambi´en, luego P −! Q es verdad y Q es falso de aqu´ı que P tenga que ser falso y, consecuentemente, ¬P verdad. Otra forma de hacerlo ser´ıa razonar en la forma siguiente: si ¬P es falso, entonces P es verdad y pueden ocurrir dos cosas, − si Q es verdad, entonces P −! Q es verdad, ¬Q falso y, por lo tanto, (P −! Q) ^ ¬Q es falso. − si Q es falso, entonces P −! Q es falso, ¬Q verdad y, por lo tanto, (P −! Q) ^ ¬Q es falso. Es decir, en ambos casos, (P −! Q) ^ ¬Q es falso. 1.4 Equivalencia L´ogica 1.4.1 Proposiciones L´ogicamente Equivalentes Las proposiciones compuestas P y Q son l´ogicamente equivalentes y se escribe P Q ´o P () Q cuando ambas tienen los mismos valores de verdad. Obs´ervese que de esta definici´on se sigue que para probar que dos proposiciones son l´ogicamente equivalentes hay que probar que si P es verdad, Q tambi´en ha de serlo y que si P es falso, Q tiene que ser falso. Obs´ervese tambi´en que otra forma de demostrar lo mismo es probar que P es verdad partiendo de que Q lo es y probar que si Q es falso, entonces P tambi´en lo es. 18 L´ogica Matem´atica Francisco Jos´e Gonz´alez Guti´errez Ejemplo 1.18 Demostrar las Leyes de De Morgan. 2 (a) ¬(p _ q) () ¬p ^ ¬q (b) ¬(p ^ q) () ¬p _ ¬q Soluci´on (a) ¬(p _ q) () ¬p _ ¬q. En efecto, si ¬(p _ q) es verdad, entonces p _ q es falso luego p y q son, ambas, falsas y, por lo tanto, ¬p es verdad y ¬q es verdad. Consecuentemente, ¬p ^ ¬q es verdad. Por otra parte, si ¬(p _ q) es falso, entonces p _ q es verdad luego una de las dos proposiciones ha de ser verdad y su negaci´on falsa, luego ¬p ^ ¬q es, en cualquier caso, falso. (b) ¬(p ^ q) () ¬p _ ¬q En efecto, si ¬(p ^ q) es verdad, entonces p ^ q es falso luego una de las dos proposiciones ha de ser falsa y su negaci´on verdad, luego ¬p _ ¬q es verdad en cualquiera de los casos. Por otra parte, si ¬(p ^ q) es falso, entonces p ^ q es verdad, luego p es verdad y q es verdad, de aqu´ı que ¬p y ¬q sean, ambas, falsas y, consecuentemente, ¬p _ ¬q sea falso. 1.4.2 Equivalencia L´ogica y Proposici´on Bicondicional La proposici´on P es l´ogicamente equivalente a la proposici´on Q si, y s´olo si la proposici´on bicondicional P ! Q es una tautolog´ıa. Demostraci´on Veamos que P () Q s´olo si P ! Q es una tautolog´ıa. En efecto, si P () Q, entonces tienen los mismos valores de verdad, es decir P y Q son, ambos, verdaderos o falsos, de aqu´ı que el valor de verdad de P ! Q sea siempre verdadero, es decir es una tautolog´ıa. Rec´ıprocamente, probemos que P () Q si P ! Q es una tautolog´ıa. Efectivamente, si la proposici´on bicondicional P ! Q es siempre verdadera, entonces de acuerdo con su definici´on, P y Q son, ambas, falsas o verdaderas, es decir tienen los mismos valores de verdad y, por tanto, P es l´ogicamente equivalente a Q. 2Augustus De Morgan (Madras 1806-Londres 1871). Naci´o en la India, donde su padre trabajaba en la East India Company, aunque realiz´o sus estudios en el Trinity College, donde obtuvo el grado de cuarto wrangler. Al negarse a pasar el indispensable examen religioso no consigui´o plaza en Cambridge ni en Oxford, a pesar de haber sido educado en la Iglesia de Inglaterra, en la que su madre esperaba que se hiciese pastor. A consecuencia de ello, De Morgan se vio nombrado profesor de matem´aticas, a la temprana edad de 22 a˜nos, en la reci´en creada Universidad de Londres, m´as tarde University College de la misma universidad, donde ense˜no de manera continua, excepto durante breves per´ıodos a consecuencias de sucesivas dimisiones provocadas por casos de reducci´on de la libertad acad´emica. De Morgan fue siempre un defensor de la tolerancia intelectual y religiosa, as´ı como un profesor y escritor excepcional. Era ciego de un ojo, de nacimiento, lo cual puede explicar algunas de sus inofensivas excentricidades, tales como su odio a la vida rural, su negativa a votar en las elecciones y su renuncia a solicitar el ingreso en la Royal Society. A De Morgan le encantaban los acertijos, rompecabezas y problemas ingeniosos, muchos de los cuales aparecen coleccionados en su libro Budget of Paradoxes, que es una deliciosa s´atira sobre los cuadradores del c´ırculo publicada despu´es de su muerte por su viuda. De Morgan fue uno de los precursores de la l´ogica matem´atica y en 1847 public´o L´ogica formal o el c´alculo de inferencia. 19 Universidad de C´adiz Departamento de Matem´aticas Nota 1.8 En el ejemplo anterior vimos que ¬(p ^ q) () ¬p _ ¬q, luego este teorema afirma que la proposici´on bicondicional ¬(p ^ q) ! ¬p _ ¬q es una tautolog´ıa. Veamos que es cierto. En efecto, p q p ^ q ¬p ¬q ¬(p ^ q) ¬p _ ¬q V V V F F F F V F F F V V V F V F V F V V F F F V V V V ¬(p ^ q) ! (¬p _ ¬q) V V V V 20 iversidad de C´adiz Departamento de Matem´aticas Nota 1.8 En el ejemplo anterior vimos que ¬(p ^ q) () ¬p _ ¬q, luego este teorema afirma que la proposici´on bicondicional ¬(p ^ q) ! ¬p _ ¬q es una tautolog´ıa. Veamos que es cierto. En efecto, p q p ^ q ¬p ¬q ¬(p ^ q) ¬p _ ¬q V V V F F F F V F F F V V V F V F V F V V F F F V V V V ¬(p ^ q) ! (¬p _ ¬q) V V V V 20 L´ogica Matem´atica Francisco Jos´e Gonz´alez Guti´errez 1.4.3 Equivalencias L´ogicas m´as Comunes Al igual que en la implicaci´on l´ogica, veamos una tabla con las equivalencias l´ogicas m´as ´utiles junto con los nombres que reciben. X Idempotencia de la conjunci´on y la disyunci´on. (P ^ P) () P (P _ P) () P X Conmutatividad de la conjunci´on y la disyunci´on. (P ^ Q) () (Q ^ P) (P _ Q) () (Q _ P) X Asociatividad de la conjunci´on y la disyunci´on. . [(P ^ Q) ^ R] () [P ^ (Q ^ R)] [(P _ Q) _ R] () [P _ (Q _ R)] X Distributividad de ^ respecto de _ y de _ respecto de ^. [P ^ (Q _ R)] () [(P ^ Q) _ (P ^ R)] [P _ (Q ^ R)] () [(P _ Q) ^ (P _ R)] X Leyes de De Morgan. ¬(P _ Q) () (¬P ^ ¬Q) ¬(P ^ Q) () (¬P _ ¬Q) X Leyes de dominaci´on. P _ T () T P ^ C () C X Leyes de identidad. P ^ T () P P _ C () P X Doble negaci´on. ¬¬P () P X Implicaci´on. (P −! Q) () (¬P _ Q) X Exportaci´on. [P −! (Q −! R)] () [(P ^ Q) −! R] X Contrarrec´ıproca. (P −! Q) () (¬Q −! ¬P) X Reducci´on al absurdo. (P −! Q) () [(P ^ ¬Q) −! C] Ejemplo 1.19 Probar que la proposici´on condicional P −! Q es l´ogicamente equivalente a su contrarrec ´ıproca ¬Q −! ¬P. Soluci´on 21 Universidad de C´adiz Departamento de Matem´aticas Veamos que ambos condicionales tienen los mismos valores de verdad. En efecto, si P −! Q es verdad, entonces P puede ser verdad o falso. Pues bien, − si P es verdad, q ha de ser verdad, luego ¬P y ¬Q son, ambas, falsas y, consecuentemente, ¬Q −! ¬P es verdad. − si P es falso, entonces ¬P es verdad y ¬Q −! ¬P es verdad, cualquiera que sea el valor de verdad de Q. Por lo tanto, en cualquier caso, ¬Q −! ¬P es verdad. Por otra parte, si P −! Q es falso, entonces P es verdad y Q es falso, luego ¬Q es verdad y ¬P es falso y, por lo tanto, ¬Q −! ¬P es falso. Tambi´en podemos hacerlo escribiendo su tabla de verdad. P Q P −! Q ¬Q ¬P ¬Q −! ¬P V V V F F V V F F V F F F V V F V V F F V V V V (P −! Q) ! (¬Q −! ¬P) V V V V Entonces, el bicondicional (P −! Q) ! (¬Q −! ¬P) es una tautolog´ıa y por 1.4.2 es una equivalencia l´ogica. Ejemplo 1.20 Probar la equivalencia l´ogica conocida como reducci´on al absurdo. Soluci´on Lo demostraremos partiendo de la segunda proposici´on, el razonamiento es m´as sencillo y r´apido. En efecto, si (P ^ ¬Q) −! C es verdad, entonces P ^ ¬Q ha de ser falso luego P y ¬Q son, ambas, falsas de aqu´ı que Q sea verdad y P −! Q tambi´en. Por otra parte, si (P ^ ¬Q) −! C es falso, entonces P ^ ¬Q ha de ser verdad (C siempre es falso) luego P es verdad y ¬Q tambi´en, de aqu´ı que Q sea falso y P −! Q sea falso. Ahora lo haremos comprobando, mediante su tabla de verdad, que la proposici´on bicondicional correspondiente, (P −! Q) ! [(P ^ ¬Q) −! C], es una tautolog´ıa. En efecto, P Q P −! Q ¬Q P ^ ¬Q C (P ^ ¬Q) −! C V V V F F F V V F F V V F F F V V F F F V F F V V F F V (P −! Q) ! [(P ^ ¬Q) −! C] V V V V Por tanto, y seg´un 1.4.2, (P −! Q) () [(P ^ ¬Q) −! C] Ejemplo 1.21 Demostrar que ¬(p ^ q) () (p ^ ¬q) _ (¬p ^ q) _ (¬p ^ ¬q). 22 L´ogica Matem´atica Francisco Jos´e Gonz´alez Guti´errez Soluci´on En efecto, ¬(p ^ q) () ¬p _ ¬q {De Morgan} () (¬p ^ T) _ (¬q ^ T) {Identidad} () (¬p ^ (q _ ¬q)) _ (¬q ^ (p _ ¬p)) {Tautolog´ıa} () (¬p ^ q) _ (¬p ^ ¬q) _ (¬q ^ p) _ (¬q ^ ¬p) {Distributividad} () (p ^ ¬q) _ (¬p ^ q) _ (¬p ^ ¬q) _ (¬p ^ ¬q) {Commutatividad} () (p ^ ¬q) _ (¬p ^ q) _ (¬p ^ ¬q) {Idempotencia} Ejemplo 1.22 Establecer las siguientes equivalencias simplificando las proposiciones del lado izquierdo. (a) [(p ^ q) −! p] () T (b) ¬(¬(p _ q) −! ¬p) () C (c) [(q −! p) ^ (¬p −! q) ^ (q −! q)] () p (d) [(p −! ¬p) ^ (¬p −! p)] () C siendo C una contradicci´on y T una tautolog´ıa. Soluci´on (a) [(p ^ q) −! p] () T [(p ^ q) −! p] () ¬(p ^ q) _ p {Implicaci´on} () (¬p _ ¬q) _ p {De Morgan} () p _ (¬p _ ¬q) {Conmutatividad de _} () (p _ ¬p) _ ¬q {Asociatividad de _} () T _ ¬q {Leyes de dominaci´on} () T (b) ¬(¬(p _ q) −! ¬p) () C ¬(¬(p _ q) −! ¬p) () ¬(¬¬(p _ q) _ ¬p) {Implicaci´on} () ¬((p _ q) _ ¬p) {Doble negaci´on} () ¬(p _ q) ^ ¬¬p {De Morgan} () (¬p ^ ¬q) ^ p {Doble Negaci´on y De Morgan} () (¬q ^ ¬p) ^ p {Conmutatividad de ^} () ¬q ^ (¬p ^ p) {Asociatividad de ^} () ¬q ^ C {Leyes de dominaci´on} () C 23 Universidad de C´adiz Departamento de Matem´aticas (c) [(q −! p) ^ (¬p −! q) ^ (q −! q)] () p [(q −! p) ^ (¬p −! q) ^ (q −! q)] () (¬q _ p) ^ (¬¬p _ q) ^ (¬q _ q) {Implicaci´on} () (¬q _ p) ^ (p _ q) ^ T {Tautolog´ıa} () (p _ ¬q) ^ (p _ q) {Conmutatividad} () p _ (¬q ^ q) {Distributividad} () p _ C {Identidad} () p (d) [(p −! ¬p) ^ (¬p −! p)] () C [(p −! ¬p) ^ (¬p −! p)] () (¬p _ ¬p) ^ (¬¬p _ p) {Implicaci´on} () ¬p ^ p {Idempotencia y doble negaci´on} () C {Contradicci´on} Ejemplo 1.23 Si 4 y son dos operadores l´ogicos, se dice que 4 es distributivo respecto de si las proposiciones p4(q r) y (p4q) (p4r) son l´ogicamente equivalentes. Probar, usando tablas de verdad, que ^ y _ son, cada uno, distributivos respecto del otro y que −! es distributivo sobre s´ı mismo. Soluci´on (a) Probaremos que p^(q_r) () (p^q)_(p^r), para lo cual veremos que la proposici´on bicondicional correspondiente es una tautolog´ıa. En efecto, p q r q _ r p ^ (q _ r) p ^ q p ^ r (p ^ q) _ (p ^ r) V V V V V V V V V V F V V V F V V F V V V F V V V F F F F F F F F V V V F F F F F V F V F F F F F F V V F F F F F F F F F F F F ! V V V V V V V V Por tanto, p _ (q ^ r) () (p _ q) ^ (p _ r) (b) Probaremos ahora que p _ (q ^ r) () (p _ q) ^ (p _ r), para lo cual veremos que la proposici´on bicondicional correspondiente es una tautolog´ıa. En efecto, p q r q ^ r p _ (q ^ r) p _ q p _ r (p _ q) ^ (p _ r) V V V V V V V V V V F F V V V V V F V F V V V V V F F F V V V V F V V V V V V V F V F F F V F F F F V F F F V F F F F F F F F F ! V V V V V V V V Por tanto, p _ (q ^ r) () (p _ q) ^ (p _ r) 24 L´ogica Matem´atica Francisco Jos´e Gonz´alez Guti´errez (c) Probaremos, finalmente, p −! (q −! r) () (p −! q) −! (p −! r), para lo cual veremos que la proposici´on bicondicional correspondiente es una tautolog´ıa. En efecto, p q r q −! r p −! (q −! r) p −! q p −! r (p −! q) −! (p −! r) V V V V V V V V V V F F F V F F V F V V V F V V V F F V V F F V F V V V V V V V F V F F V V V V F F V V V V V V F F F V V V V V ! V V V V V V V V Por tanto, p −! (q −! r) () (p −! q) −! (p −! r)