Logica Proposicional Distrittal

UNIDAD 2: LÓGICA PROPOSICIONAL INTRODUCCIÓN Uno de los procesos por los cuales adquirimos conocimiento es el proceso de razonamiento. A su vez, hay una variedad de modos o formas mediante las cuales razonamos o argumentamos a favor de una conclusión. Ciertas formas de razonamiento parecen mostrar que si se suponen ciertas premisas, entonces la conclusión se sigue necesariamente. A tales razonamientos se los ha denominado deductivos y forman el objetivo central de lo que clásicamente se ha denominado lógica. En un sentido amplio, el término lógico hace referencia al estudio de todos los razonamientos, y en un sentido estricto ha estado circunscrito al estudio del razonamiento deductivo. Cierto tipo de razonamiento deductivo se basa en la lógica proposicional. Lo que caracteriza a la lógica proposicional es que toma como unidades básicas a las proposiciones y que tiene en cuenta como se combinan entre ellas por medio de conectivos lógicos para formar argumentos válidos. 2.1. PROPOSICIONES Una proposición es una sentencia declarativa que puede ser verdadera o falsa, pero no ambas a la vez. También podríamos decir que una proposición es una sentencia que expresa una propiedad para un individuo o ente, o que expresa la validez de una relación entre individuos o entes. Por ejemplo: Hoy es sábado. Los triángulos tienen cuatro vértices. 25 + 24 = 49. Juan va al trabajo en bus . Las sentencias exclamativas, las interrogativas y las imperativas tales como: ¡Viva la familia!, ¿Está lloviendo? no son proposiciones puesto que no pueden ser declaradas como verdaderas o falsas. La veracidad (V) o falsedad (F) de una proposición se llama valor de verdad y viene dada por algún criterio independiente de la proposición. Algunas proposiciones parecieran tener distintos valores de verdad según el caso. Por ejemplo, si decimos: Hoy es sábado, es falsa de domingo a viernes y es verdadera los sábados. En nuestro lenguaje coloquial hay una gran parte de la información que está implícita. La palabra hoy está indicando una fecha particular, aunque no se esté diciendo explícitamente cual. 2.2. TIPOS DE PROPOSICIONES 18

Formalmente, se define una proposición como un enunciado declarativo que puede ser verdadero o falso, pero no ambos a la vez. Las proposiciones se representan mediante variables proposicionales simbolizadas mediante letras minúsculas p, q, r,......que se denomina letras proposicionales. Con la combinación de variables proposicionales y conjunciones se obtienen fórmulas sentenciales o sentencias. Una proposición que tenga como único valor (F) se le denomina proposición lógicamente falsa, y a la que tenga como único valor (V), se le denomina lógicamente verdadera Las proposiciones pueden constar de un solo enunciado o de varios, en el primer caso las denominamos proposiciones atómicas y en segundo moleculares. Las proposiciones moleculares se obtienen de las atómicas mediante determinadas leyes de composición denominadas conectivos y se estudiará más adelante En resumen las proposiciones se clasifican en: • • •

Tautología: es la sentencia que es verdadera ( I ) Contradicción: es la sentencia que es falsa. ( O ) Indeterminación: es la sentencia que ni es verdadera ni falsa.

2.3 CONECTIVOS Y OPERADORES LÓGICOS En el cálculo proposicional se suelen utilizar letras minúsculas como p, q, r,... para simbolizar las proposiciones. Estos símbolos pueden modificarse o combinarse mediante conectivos lógicos dando lugar a proposiciones compuestas, como las mostradas en la siguiente tabla.

¬ ∧ ∨ ⊕ → ↔

NO Y O

Negación Conjunción Disyunción inclusiva O..O Disyunción exclusiva SI..ENTONCE Condicional S SI Y SOLO SI Bicondicional

18

2.3.1 Conjunción o Producto Lógico ( ∧ ) La conjunción es un conectivo que permite formar proposiciones compuestas a partir de dos o más proposiciones. Una conjunción de proposiciones es verdadera si y sólo si cada una de ellas es verdadera. Basta que un solo término de la conjunción sea falso para que toda la conjunción sea falsa. En castellano, normalmente la conjunción se expresa por medio de la ’y’, de comas o de una combinación de estas, o palabras como ’pero’. Así, por ejemplo, la proposición compuesta Mérida tiene sierras y tiene ríos es verdadera porque cada parte de la conjunción es verdadera. No ocurre lo mismo con la proposición Mérida tiene sierras y tiene mar. Esta proposición es falsa porque Mérida no tiene mar. La siguiente tabla corresponde a la tabla de verdad de la conjunción: Es una conectiva definida por: p  q  ¬ ( ¬p ∨ ¬q ) La sentencia será verdadera sólo cuando ambas variables proposicionales sean verdaderas. p q pq ========== V V V V F F F V F F F F EJEMPLO . Si p es “algunas aves vuelan” y q es “el gato es un ave”, entonces p ∧ q expresa “algunas aves vuelan y el gato es un ave”, que es obviamente falsa pues los gatos no son aves. Por otro lado la proposición p ∧ ¬q que dice “algunas aves vuelan y el gato no es un ave” es verdadera pues es la conjunción de dos proposiciones verdaderas. El producto lógico así definido tiene las siguientes propiedades a) Conmutativa p  q ≡ q  p , en efecto se cumple que: p V V F F

q V F V F

p ∧q V F F F

q ∧p V F F F

b) Asociativa ( p  q )  r ≡ p ∧( q ∧r ) , en efecto su tabla de verdad 18

p V V V V F F F F

q V V F F V V F F

r V F V F V F V F

p ∧q V V F F F F F F

( p  q ) ∧r q ∧r V V F F F F F F F V F F F F F F

p ∧( q ∧r ) V F F F F F F F

c) Identidad p ∧I  p p V F

I V V

p I V F

d) Complemento p ∧ p ≡ 0 ¬ p p V F F V

O F F

p∧  p F F

2.3.2 Disyunción Existen dos operadores de disyunción: La disyunción exclusiva o excluyente y la disyunción inclusiva o incluyente. La disyunción exclusiva de dos proposiciones es verdadera si solo una de las proposiciones es verdadera, y la indicamos con el símbolo  La disyunción inclusiva entre dos proposiciones es falsa solo si ambas proposiciones son falsas y se indica con el símbolo  . En el lenguaje coloquial y en matemática es más frecuente el uso de la disyunción inclusiva, también llamada el “o inclusivo”. A veces el contexto de una frase indica si la disyunción es excluyente o incluyente. Un ejemplo de disyunción de tipo inclusivo es: “Los alumnos regularizan la materia si aprueban tres parciales o si aprueban dos parciales y tienen un 80% de asistencia.” 18

En este caso, los alumnos pueden cumplir cualquiera de los dos requisitos, o también cumplir los dos. Pero por ejemplo, si en un restaurante con menú fijo se nos dice que tenemos como postre ’helado o flan’ normalmente no significa que podamos pedir ambos, siendo en este caso la disyunción exclusiva. Frecuentemente y cuando no es claro en el contexto de la oración se indica que una disyunción es incluyente (excluyente respectivamente) terminando la frase con o ambas (respectivamente pero no ambas). A continuación se presentan las tablas de verdad Disyunción exclusiva (  ,  ) Es una conectiva definida por: p  q  ¬( p ↔q ) La sentencia será verdadera sólo cuando una de las dos variables proposicionales sea verdadera. p q p⊕q ============= V V F V F V F V V F F F Disyunción inclusiva o suma lógica (  ) La sentencia será verdadera cuando una o ambas variables proposicionales sean verdaderas. p q p ∨q ========== V V V V F V F V V F F F La suma lógica así definida tiene las siguientes propiedades: a)Conmutativa p ∨q  q ∨p p V V

q p  q q ∨p V V V F V V 18

F F

V F

V F

V F

b) Asociativa ( p  q )  r ≡ p ∨( q ∨r )

p V V V V F F F F

q V V F F V V F F

r p ∨q V V F V V V F V V V F V V F F F

(p q) r V V V V V V V F

q  rp  V V V F V V V F

( q ∨r ) V V V V V V V F

c) Identidad p ∨O  p p O V F F F

p ∨O V F

d) Complemento p ∨ p ≡ I p ¬p I V F V F V V

p ∨¬ p V V

2.3.3 Condicional ( → ) El conectivo condicional nos da, pues una proposición que es falsa cuando sea verdadera el antecedente y falso el consecuente, cuya tabla de verdad se muestra a continuación: p q p →q ================= V V V V F F F V V F F V

18

Este conectivo lógico tiene la siguiente propiedad distributiva respecto a la suma lógica

p V V V V F F F F

q V V F F V V F F

r V F V F V F V F

q ∨r V V V F V V V F

p (p r p q V V V V V F F F V V V V V V V V

p →r V F V F V V V V

(p  r )  (p →r ) V V V F V V V V

2.3.4 Bicondicional (  ) La sentencia será verdadera cuando ambas variables proposicionales sean iguales. p q p ↔q ============== V V V V F F F V F F F V Esta conectiva tiene las siguientes propiedades:

a) Conmutativa p ↔ q  q  p p V V F F

p q q V V F F V F F V

q↔p V F F V

b) Asociativa ( p ↔ q )  r ≡ p ↔ (q  r ) p

q

r p q (p q)↔r q ↔r

p↔(q 18

r ) V V V V F F F F

V V F F V V F F

V F V F V F V F

V V F F F F V V

V F F V F V V F

V F F V V F F V

V F F V F V V F

c) Ser la conjunción de un par de condicionales en que se intercambian el antecedente y el consecuente p  q ≡ (p → q ) ∧ ( q → p )

p V V F F

q V F V F

p →q q →p V V F V V F V V

(p  q ) ∧ ( q → p) V F F V

p↔q V F F V

2.3.5 Negación (  , ∼ ) Si p es una proposición, simbolizamos con ¬p a su negación. La negación es una operación unitaria que se aplica a una proposición y tiene el efecto de revertir el valor de verdad. Esto es, si p es verdadera entonces ¬p es falsa, y si p es falsa entonces ¬p es verdadera. EJEMPLO 1. Si p simboliza la proposición estamos en la clase de “Razonamiento”, entonces ¬p es no estamos en la clase de “Razonamiento”. En la siguiente tabla mostramos la relación entre los valores de verdad de p y ¬p: p ¬p ===== V F F V

18

Una tabla de este tipo, en la que se listan simultáneamente los valores de verdad de la proposición p y la que resulta de aplicar un conectivo se llama tabla de verdad. EJEMPLO 2. Consideremos la proposición p: “10 es múltiplo de 5”. Entonces el valor de p es V . Su negación debe ser una proposición que es falsa siempre que p sea verdadera, por lo tanto ¬p debe expresar exactamente lo contrario a lo que expresa p: ¬p: “10 no es múltiplo de 5”. Implicación lógica Se dice que una proposición P(p,q,...) implica lógicamente una proposición Q(p,q,...), lo que se escribe: P(p,q,...) --> Q(p,q,...) si se verifica una de las siguientes condiciones: 1. ~P(p,q,...) v Q(p,q,...) es una tautología. 2. P(p,q,...) ^ ~Q(p,q,...) es una contradicción. 3. P(p,q,...) --> Q(p,q,...) es una tautología. La proposición ya antes vista: [(p --> q) ^ (q --> r)] --> (p --> r) vimos que es una tautología, de acuerdo a la definición anterior, la proposición (p --> q) ^ (q --> r) implica lógicamente a la proposición (p -->r), es decir: [(p --> q) ^ (q -->r)] --> (q -->r) Consideremos ahora la proposición: (p ^ q) ^ ~(p v q), cuya tabla de verdad es la siguiente: (p ^ q) ^ ~(p v q) p V V F F

q V F V F

(p V V F F

^ V F F F

q) V F V F

^ F F F F

~ F F F V

(p V V F F

v V V V F

q) V F V F

Se observa de la tabla que la proposición: (p ^ q) ^ ~(p v q) es una contradicción, por tanto por la definición anterior: p ^ q --> p v q

18

EQUIVALENCIA DE FORMULAS Definición: Dos fórmulas lógicas son equivalentes si tienen los mismos valores de verdad para todos los posibles valores de verdad de sus componentes atómicos. Diremos que dos proposiciones P y Q son lógicamente equivalentes si es una tautología, es decir, si las tablas de verdad de P y Q son iguales.

Equivalencia lógica en la ley asociativa de la conjunción A modo ilustrativo demostraremos, a continuación, que, en virtud de la ley asociativa de la conjunción, la fórmula p(qr) es lógicamente equivalente a (pq)r. Para ello no hay más que hacer la tabla de verdad de cada una de esas expresiones y comprobar si, en efecto, todas sus interpretaciones son iguales para la conectiva dominante. Equivalencia lógica en la ley asociativa de la disyunción Te proponemos que rellenes la siguiente tabla con “Vs” y “Fs” donde proceda para comprobar que, en virtud de la ley asociativa de la disyunción, la fórmula p(qr) es equivalente a (pq)r. Ejemplo: Las dos fórmulas siguientes son equivalentes: (p → ¬q) ∨ (¬p ∨ r)

¬p ∨ ¬q ∨ r

p q r ¬q ¬p p → ¬q V V V V F F F F

V V F F V V F F

V F V F V F V F

F F V V F F V V

F F F F V V V V

F F V V V V V V

¬p ∨ (p → ¬q) ∨ (¬p ∨ ¬ p ∨ ¬p ∨ ¬q ∨ r r) ¬q r V V F V F F F F V V V V F V V V V V V V V V V V V V V V V V V V

donde se puede observar que la última yla antepenúltima columnas son iguales. Las equivalencias se relacionan con las tautologías de la siguiente forma. Teorema: 18

Si dos fórmulas lógicas son eqivalentes entonces la fórmula que se obtiene al operarlas con la bicondiconal es una tautología.

La expresión p → q es equivalente a ¬p ∨ q pues p V V F F

q V F V F

p→q V F V V

¬p F F V V

¬p ∨ q V F V V

Falta hablar de formas normales, utilizar las identidades para llegar a la forma normal conjuntiva. Equivalencias Logicas Dos fórmulas lógicas son equivalentes si tienen los mismos valores de verdad para todos los posibles valores de verdad de sus componentes atómicos. Teorema: Si dos fórmulas lógicas son eqivalentes entonces la fórmula que se obtiene al operarlas con la bicondiconal es una tautología. Pasos para la realizacion de equivalencias 1.- Numerar los operadores de la primer formula p v ¬q v ¬r , p v (q → ¬r) 2.- Primeramente los parentesis internos, seguido de las negaciones, posteriormente los operadores siguientes. 3.- Realizar el arbol. (IMG ARBOL) 4.- Se numeran las hojas del arbol de abajo haca arriba de forma alfaberica, se hace esto para las dos formulas. primero la de la izquierda. 5.- Una vez terminado el árbol, proceder a hacer la tabla. 6.- Poner los encabezados de la tabla usando los numeros del arbol. 7.- Acomodar los valores de las hojas, siempre siguiendo el mismo orden. 8.- Poner los demas valores de la tabla utilizando las tablas de verdad. 1 2 3 4 5 p q r ¬q ¬r V V V V F F F

V V F F V V F

V F V F V F V

F F V V F F V

F V F V F V F

6 ¬q v ¬r F V V V F V V

7 p v ¬q v ¬r V V V V F V V

8 q→ ¬r F V V V F V V

9 p v (q → ¬r) V V V V F V V 18

F F F V V

V

V

V

V

9.- Si las tablas no. 7 y no. 9 son exactamente iguales, se concluye que son equivalentes las dos.

ANALISIS DE INFERENCIAS Leyes Lógicas •

Asociativas

•

Distributivas

•

Leyes de De Morgan

•

De idempotencia

•

De identidad

•

De dominación

•

Inversas

•

De absorción

Reglas de Sustitución •

Sea P una tautología y q una variable de P. Si sustituimos cada aparición de q por cualquier otra proposición Q entonces la proposición resultante es también una tautología.

•

Sea P una tautología y Q una proposición que aparece en P. Si reemplazamos Q por una proposición lógicamente a Q obtendremos una nueva proposición lógicamente equivalente a P.

•

Cualquier proposición es lógicamente equivalente a otra que contiene sólamente los conectivos lógicos -, v,and.

Reglas de Inferencia Dadas dos proposiciones P y Q diremos que P implica lógicamente Q , y escribiremos P \Rightarrow Q si P rightarrow Q es una tautología. Si P es falso, entonces la proposición P, Q es verdadera independientemente del valor de Q. Por tanto, P si los valores de las variables que hacen a P verdadero también hacen verdadero a Q. De manera equivalente P Q significa que P y Q no tienen nunca de manera simultánea los valores de verdad 1 y 0 respectivamente. Como hemos dicho, las proposiciones pueden tomar dos valores, verdadero o falso, que representaremos respectivamente con los números 1 y 0. Por tanto, cuando digamos que una proposición toma valor 1 estaremos diciendo que es verdadera. 18

El valor de verdad de una proposición compuesta queda determinado por los valores de las proposiciones simples que la forman. Las tablas de verdad nos indican los valores de verdad de una proposición para cada posible combinación de los valores de las proposiciones simples. !!!Tautologías fundamentales Ley del medio excluido p ∨ ¬p Ley de no contradicción ¬(p ^ ¬p) Modus ponendo ponens ((p → q)^p) → q Modus tollendo tollens ((p → q)^ ¬ q) → ¬ p Silogismo Disyuntivo ((p ∨ q)^ ¬p) → q La comprobación de cualquiera de las tautologías anteriores es directa, es suficiente hacer la tabla de verdad y se obtendrá la columna correspondiente a la fórmula con valores de verdaderos únicamente. !!!Equivalencias Doble negación ¬(¬p) ↔ p Implicación y disyunción p → q ≡ ¬p ∨ q Contrapositiva p → q ≡ ¬q → ¬p Negaci’on de la Implicación ¬(p → q) ≡ p ^ ¬q Leyes de De Morgan ¬(p ∨ q) ≡ ¬p ^ ¬q ¬(p ^q) ≡ ¬p ∨ ¬q

19