1. lógica simbólica y demostraciones

8/20/2019 1. Lógica Simbólica y Demostraciones

1/194

Introducción Cálculo Proposicional Deducciones Lógicas Cuantificadores Métodos de Demostración

Introducción al CálculoLógica Simbólica y Demostraciones

CNM-107

Departamento de MatemáticasFacultad de Ciencias Exactas y Naturales

Universidad de Antioquia

Copyleft

2009. Reproducción permitida bajo los

términos de la licencia de documentación libre GNU.

http://ciencias.udea.edu.co/http://ciencias.udea.edu.co/http://ciencias.udea.edu.co/


2/194


3/194


Antecedentes históricos de la lógica formal

China

Mozi: fundador de la escuela Mohista (moh́ısmo), sus

principios están relacionados con la inferencia válida y lascondiciones de las conclusiones correctas

Lógicos: escuela que siguió al moh́ısmo, considerada comola primera que investigó la lógica formal.

Mozi

India

Se desarrolló en India sin influencia conocida de la lógicagriega

Nyaya y Vaisheshika: escuelas del pensamientorelacionadas con la lógica

Primeros pasos en el análisis formal de la inferencia

d ´ C´l l l d ´ C f d M´ d d ´

http://es.wikipedia.org/wiki/Mozihttp://en.wikipedia.org/wiki/File:Aristoteles_Logica_1570_Biblioteca_Huelva.jpghttp://en.wikipedia.org/wiki/File:Aristoteles_Logica_1570_Biblioteca_Huelva.jpghttp://es.wikipedia.org/wiki/Omhttp://es.wikipedia.org/wiki/Omhttp://es.wikipedia.org/wiki/Mozihttp://es.wikipedia.org/wiki/Mozi


4/194



China




Mozi

India



Primeros pasos en el análisis formal de la inferencia Om

http://es.wikipedia.org/wiki/Mozihttp://es.wikipedia.org/wiki/Omhttp://en.wikipedia.org/wiki/File:Aristoteles_Logica_1570_Biblioteca_Huelva.jpghttp://en.wikipedia.org/wiki/File:Aristoteles_Logica_1570_Biblioteca_Huelva.jpghttp://es.wikipedia.org/wiki/Omhttp://es.wikipedia.org/wiki/Omhttp://es.wikipedia.org/wiki/Mozihttp://es.wikipedia.org/wiki/Mozi


5/194



6/194

Introduccion Calculo Proposicional Deducciones Logicas Cuantificadores Metodos de Demostracion


China




Mozi

India




Grecia

Lógica estoica: se concentra en la lógica proposicional (lamás próxima a la lógica moderna)

Lógica de Aristóteles: tuvo su origen en el Organon , es la

que más influencia tuvo en occiedenteLógica de Aŕıstoteles


http://es.wikipedia.org/wiki/Mozihttp://es.wikipedia.org/wiki/Omhttp://en.wikipedia.org/wiki/File:Aristoteles_Logica_1570_Biblioteca_Huelva.jpghttp://en.wikipedia.org/wiki/File:Aristoteles_Logica_1570_Biblioteca_Huelva.jpghttp://en.wikipedia.org/wiki/File:Aristoteles_Logica_1570_Biblioteca_Huelva.jpghttp://en.wikipedia.org/wiki/File:Aristoteles_Logica_1570_Biblioteca_Huelva.jpghttp://es.wikipedia.org/wiki/Omhttp://es.wikipedia.org/wiki/Omhttp://es.wikipedia.org/wiki/Mozihttp://es.wikipedia.org/wiki/Mozi


7/194



China




Mozi

India




Grecia

Lógica estoica: se concentra en la lógica proposicional (lamás próxima a la lógica moderna)

Lógica de Aristóteles: tuvo su origen en el Organon , es la

que más influencia tuvo en occiedenteLógica de Aŕıstoteles


http://es.wikipedia.org/wiki/Mozihttp://es.wikipedia.org/wiki/Omhttp://en.wikipedia.org/wiki/File:Aristoteles_Logica_1570_Biblioteca_Huelva.jpghttp://en.wikipedia.org/wiki/File:Aristoteles_Logica_1570_Biblioteca_Huelva.jpghttp://en.wikipedia.org/wiki/File:Aristoteles_Logica_1570_Biblioteca_Huelva.jpghttp://en.wikipedia.org/wiki/File:Aristoteles_Logica_1570_Biblioteca_Huelva.jpghttp://es.wikipedia.org/wiki/Omhttp://es.wikipedia.org/wiki/Omhttp://es.wikipedia.org/wiki/Mozihttp://es.wikipedia.org/wiki/Mozi


8/194


Antecedentes de la lógica formal

Siglo XIX

La lógica pasa a formar parte de las matemáticas: l´ ogica simb´ olica omatem´ atica

Se modelan los métodos argumentativos a partir de un lenguaje básicoque mediante procedimientos “matemáticos”, generan las leyesuniversales del razonamiento

Tipos de lógica

Lógica clásica: fundamento formal de las matemáticas

Tipos no “formales”:

Lógica modal

Lógica difusa

Lógica probabiĺıstica



9/194



Siglo XIX



Tipos de lógica



Lógica modal

Lógica difusa


La lógica simbólica, en principio, se caracteriza por estructurar elrazonamiento desde la sint´ axis , es decir, desde el lenguaje y losprincipios lógicos de forma independiente al significado de las

afirmaciones involucradas.



10/194

p g


Siglo XIX



Tipos de lógica



Lógica modal

Lógica difusa


La lógica simbólica, en principio, se caracteriza por estructurar elrazonamiento desde la sint´ axis , es decir, desde el lenguaje y losprincipios lógicos de forma independiente al significado de las

afirmaciones involucradas.


11/194


12/194



13/194

Śımbolos lógicos

Negación: ¬P : letra predicativa

¬P : la negaci´ on de P

¬P se lee como “no P ” o “negación de P ”.

Para P, Q y R del ejemplo (2.1):

Ejemplo 2.2

¬P representa “ 1 + 1 = 2”¬Q significa “No est´ a lloviendo”¬R significa “las vacas no vuelan”



14/194






Ejemplo 2.2


¬P toma el valor de verdad contrario al que toma P :

¬P toma el valor F si P es V

¬P toma el valor V si P es F

P ¬P V F

F V



15/194






Ejemplo 2.2


¬P toma el valor de verdad contrario al que toma P :

¬P toma el valor F si P es V

¬P toma el valor V si P es F

P ¬P V F

F V



16/194


Disyunción: ∨

P, Q: letras predicativas

P ∨ Q: disyunci´ on entre P y Q

P ∨ Q se lee como “P ó Q”

Ejemplo 2.3

P : 1 + 1 = 2Q : Est´ a lloviendo.R : 1 ∈ ∅S : El ser humano es un mamı́fero.

Ejemplo 2.4

P ∨ R significa “ 1 + 1 = 2 ´ o 1 ∈ ∅”Q ∨ S significa “est´ a lloviendo o el ser humano es un mamı́fero”

¬R significa “las vacas no vuelan”

Q ∨ S es una afirmación verdadera sin importarqué valor de verdad tome Q

Si no está lloviendo, Q ∨ R es una afirmación falsa



17/194


Disyunción: ∨




Ejemplo 2.3


Ejemplo 2.4





P Q P ∨ Q

V V VV F VF V V

F F F



18/194


Disyunción: ∨




Ejemplo 2.3


Ejemplo 2.4





P Q P ∨ Q

V V VV F VF V V

F F F



19/194


Conjunción: ∧


P ∧ Q: conjunci´ on entre P y Q

P ∧ Q se lee como “P y Q”

Ejemplo 2.5


Ejemplo 2.6

P ∧ R significa “ 1 + 1 = 2 y 1 ∈ ∅”P ∧ Q representa “ 1 + 1 = 2 y est´ a lloviendo”

P ∧ S representa “ 1 + 1 = 2 y el ser humano es un mamı́fero”

P ∧ R es falsa ya que 1 ∈ ∅ es falso y, por lo tanto,ambas afirmaciones no son ciertas a la vez

P ∧ Q es verdadera sólo si Q es verdadera

P ∧ S es verdadera



20/194


Conjunción: ∧




Ejemplo 2.5


Ejemplo 2.6






P Q P ∧ Q

V V VV F FF V F

F F F



21/194


Conjunción: ∧




Ejemplo 2.5


Ejemplo 2.6






P Q P ∧ Q

V V VV F FF V F

F F F


22/194



23/194


Implicación ( ⇒ ): expresa relación de causa y efecto entre dos afirmacionesP ⇒ Q: “P implica Q”

P ⇒ Q: “si P , entonces Q”

“P es condición suficiente para Q”

“Q es condición necesaria para P ”

P Q P ⇒ QV V VV F FF V VF F V

Ejemplo 2.7

P : 4 divide a 3Q : 3 es par R : S´ ocrates es hombre

S : S´ ocrates es mortal



24/194







Ejemplo 2.7



R ⇒ S dice que “si Sócrates es hombre, entonces es mortal”(verdadero)



25/194







Ejemplo 2.7



R ⇒ S dice que “si Sócrates es hombre, entonces es mortal”(verdadero)R ⇒ Q significa “si Sócrates es hombre, entonces 3 es par”(falso)


Ś b l l´


26/194







Ejemplo 2.7




Q ⇒ S es verdadera


Ś b l l´ i


27/194







Ejemplo 2.7




Q ⇒ S es verdadera


Ś b l l´ i


28/194


Equivalencia: ⇔

P ⇔ Q: “P equivale a Q”

P ⇔ Q: P y Q tienen el mismo valor de verdad

P ⇔ Q: P y Q tienen el mismo significado

P Q P

⇔ Q

V V VV F FF V FF F V


Ś b l l´ i


29/194

Sımbolos logicos

Equivalencia: ⇔




P Q P

⇔ Q


Ejemplo 2.8

P : 6 es par Q : 6 es divisible por 4R : n es impar S : n deja residuo 1 al dividirse por 2

P ⇔ Q es falsa, pues P es cierta y Q es falsa (no tienen el mismo significado)


30/194




31/194

Sımbolos logicos

Equivalencia: ⇔




P Q P

⇔ Q


Ejemplo 2.8

P : 6 es par Q : 6 es divisible por 4R : n es impar S : n deja residuo 1 al dividirse por 2

P ⇔ Q es falsa, pues P es cierta y Q es falsa (no tienen el mismo significado)

R ⇔ S es verdadera: dependiendo de n, R y S tendrán el mismo valor deverdad V ó F


Ejemplos


32/194

Ejemplos

Tabla de verdad de (¬P ∨ Q) ∧ P :

P Q ¬P ¬P ∨ Q (¬P ∨ Q) ∧ P V V F V VV F F F FF V V V FF F V V F

Tabla de verdad de ((¬P ∨ Q) ∧ P ) ⇔ (P ∧ Q):

P Q (¬P ∨ Q) ∧ P P ∧ Q ((¬P ∨ Q) ∧ P ) ⇔ (P ∧ Q)V V V V VV F F F VF V F F VF F F F V


Ejemplos


33/194

Ejemplos




P Q (¬P ∨ Q) ∧ P P ∧ Q ((¬P ∨ Q) ∧ P ) ⇔ (P ∧ Q)V V V V VV F F F VF V F F VF F F F V

Los valores de verdad de estas afirmaciones no dependen del significadode P ni de Q


Ejemplos


34/194

Ejemplos




P Q (¬P ∨ Q) ∧ P P ∧ Q ((¬P ∨ Q) ∧ P ) ⇔ (P ∧ Q)V V V V VV F F F V

F V F F VF F F F V

Los valores de verdad de estas afirmaciones no dependen del significadode P ni de Q


Tautloǵıas


35/194

Tautlogıas

Definición 2.1 (Tautologı́a, Contradicción)

Una tautoloǵıa es una afirmaci´ on cuya tabla de verdad siempre toma el

valor V. Una contradicci´ on es una afirmaci´ on cuya tabla de verdad siempre toma el valor F.

Ejemplos de tautoloǵıas y contradicciones:

P ¬P P ∨ ¬P P ⇒ P P ⇔ P P ∧ ¬P P ⇔ ¬P V F V V V F FF V V V V F F


Tautloǵıas


36/194

Tautlogıas






P ∧

¬Q no es tautoloǵıa ni contradicción:

P Q ¬Q P ⇒ Q P ∧ ¬Q (P ⇒ Q) ∧ (P ∧ ¬Q)V V F V F FV F V F V FF V F V F FF F V V F F


Tautloǵıas


37/194

aut og as






P ∧

¬Q no es tautoloǵıa ni contradicción:

P Q ¬Q P ⇒ Q P ∧ ¬Q (P ⇒ Q) ∧ (P ∧ ¬Q)V V F V F FV F V F V FF V F V F FF F V V F F


Tautloǵıas


38/194

g

Proposición 2.1

Las siguientes afirmaciones son tautoloǵıas.

1 P ⇒ P 2 P ⇔ P 3 P ∨ ¬P (Tercer exclúıdo)

Las tautoloǵıas son las afirmaciones más importantes en la lógicasimbólica (leyes del razonamiento)


Tautloǵıas


39/194

g

Proposición 2.1




Las contradicciones tienen una importancia equivalente porque toda contradicci´ on equivale a la negaci´ on de una tautoloǵıa.


Tautloǵıas


40/194

g

Proposición 2.1





A cada tautoloǵıa le corresponde una justificaci´ on que verifica suvalidez.


Tautloǵıas


41/194

Proposición 2.1





A cada tautoloǵıa le corresponde una justificaci´ on que verifica suvalidez.


P i i´ 2 2 (P i i l E i l i L´ i )


42/194

Proposición 2.2 (Principales Equivalencias Lógicas)

1 ¬¬P ⇔ P (Doble negaci´ on).

2 (P ∨ Q) ⇔ (Q ∨ P ) (Conmutatividad de la disyunci´ on).

3 (P ∧ Q) ⇔ (Q ∧ P ) (Conmutatividad de la conjunci´ on).

4 ((P ∨ Q) ∨ R) ⇔ (P ∨ (Q ∨ R)) (Asociatividad de la disyunci´ on).

5 ((P ∧ Q) ∧ R) ⇔ (P ∧ (Q ∧ R)) (Asociatividad de la conjunci´ on).

6 (P ∨ (Q ∧ R)) ⇔ ((P ∨ Q) ∧ (P ∨ R)) (Ley distributiva).

7 (P ∧ (Q ∨ R)) ⇔ ((P ∧ Q) ∨ (P ∧ R)) (Ley distributiva).

8 ¬(P ∨ Q) ⇔ (¬P ∧ ¬Q) (ley D’Morgan).

9 ¬(P ∧ Q) ⇔ (¬P ∨ ¬Q) (ley D’Morgan).

10 ¬(P ⇒ Q) ⇔ (P ∧ ¬Q) (Negaci´ on de la implicaci´ on)

11 (P ⇒ Q) ⇔ (¬Q ⇒ ¬P ) (Contrarrecı́proco).

12 (P ⇔ Q) ⇔ ((P ⇒ Q) ∧ (Q ⇒ P )) (Principio de doble implicaci´ on).

13 (P ⇔ Q) ⇔ (Q ⇔ P ) (Conmutatividad de la equivalencia).

14 (P ⇒ Q) ⇔ (¬P ∨ Q).

15 (P ∧ Q) ⇔ ¬(¬P ∨ ¬Q).

16 (P ∨ P ) ⇔ P .

17 (P ∧ P ) ⇔ P .


43/194


Deducciones Lógicas


44/194

El fundamento del razonamiento, en especial en matemáticas, es laforma de efectuar argumentos válidos mediante relaciones de causa y efecto (proposición 2.3)

Forma de las reglas de inferencia:

(H 1 ∧ H 2 ∧ · · · ∧ H n)

| {z } antecedente (hipótesis)=⇒ C

|{z} consecuente(conlusión)(1)




45/194



(H 1 ∧ H 2 ∧ · · · ∧ H n)



Forma esquemática para representar (1):

H 1

H 2···

H n

9>>>>>>=>>>>>>;

Hipótesis

C Conclusión.




46/194



(H 1 ∧ H 2 ∧ · · · ∧ H n)



Forma esquemática para representar (1):

H 1

H 2···

H n

9>>>>>>=>>>>>>;

Hipótesis

C Conclusión.


Forma esquemática de algunas proposiciones


47/194

((P ⇒ Q) ∧ P ) ⇒ Q:

P ⇒ QP

Q

((P ⇒ Q) ∧ ¬Q) ⇒ ¬P :

P ⇒ Q¬Q¬P




48/194

((P ⇒ Q) ∧ P ) ⇒ Q:

P ⇒ QP

Q

((P ⇒ Q) ∧ ¬Q) ⇒ ¬P :

P ⇒ Q¬Q¬P

(P ∧ Q) ⇒ P :

P ∧ Q

P




49/194

((P ⇒ Q) ∧ P ) ⇒ Q:

P ⇒ QP

Q

((P ⇒ Q) ∧ ¬Q) ⇒ ¬P :

P ⇒ Q¬Q¬P

(P ∧ Q) ⇒ P :

P ∧ Q

P

(P ∧ Q) ⇒ (P ∧ Q):

P

Q

P ∧ Q


50/194


Deducciones lógicas


51/194

Proposición 3.1 (Método de la Deducción)

Si se toman H 1, H 2, . . . , H n como hip´ otesis y, mediante reglas de inferencia

y equivalencias se concluye C , entonces H 1 ∧ H 2 ∧ · · · ∧ H n implica a C ,es decir,

H 1H 2·

··H n

9>>>>>>=>>>>>>;

Hip´ otesis

C Conclusi´ on.

Para efectuar una deducción lógica tendremos en cuenta las siguientes

instrucciones:

1. Enunciar las hipótesis




52/194




H 1H 2·

··H n

9>>>>>>=>>>>>>;

Hip´ otesis

C Conclusi´ on.


instrucciones:


2. Justificar, mediante reglas de inferencia, una nueva afirmación en base alas anteriores de la lista


53/194




54/194




H 1H 2·

··H n

9>>>>>>=>>>>>>;

Hip´ otesis

C Conclusi´ on.


instrucciones:


2. Justificar, mediante reglas de inferencia, una nueva afirmación en base alas anteriores de la lista

3. Mediante la instrucción (2), llegar finalmente a la conclusión




55/194

Ejemplo 3.1

Demuestre que ((P ⇔ Q) ∧

(Q ⇔ R)) ⇒ (P ⇔ R) es una tautoloǵıa, i.e,P ⇔ QQ ⇔ RP ⇔ R

Solución




56/194

Ejemplo 3.1



Solución

1. P ⇔ Q Hipótesis




57/194

Ejemplo 3.1



Solución

1. P ⇔ Q Hipótesis2. Q ⇔ R Hipótesis




58/194

Ejemplo 3.1



Solución

1. P ⇔ Q Hipótesis2. Q ⇔ R Hipótesis3. P ⇒ Q 1, descomposición de ⇔4. Q

⇒ P 1, desc. de

⇔5. Q ⇒ R 2, desc. de ⇔6. R ⇒ Q 2, desc. de ⇔7. P ⇒ R 3,5, transitividad de ⇒8. R ⇒ P 4,6, transitividad de ⇒9. P ⇔ R 7,8, composición de ⇔




59/194

Ejemplo 3.1



Solución

1. P ⇔ Q Hipótesis2. Q ⇔ R Hipótesis3. P ⇒ Q 1, descomposición de ⇔4. Q

⇒ P 1, desc. de

⇔5. Q ⇒ R 2, desc. de ⇔6. R ⇒ Q 2, desc. de ⇔7. P ⇒ R 3,5, transitividad de ⇒8. R ⇒ P 4,6, transitividad de ⇒9. P ⇔ R 7,8, composición de ⇔


Ejemplos

Ejemplo 3 2


60/194

Ejemplo 3.2

Determine la validez de la siguiente deducci´ on: “Si la m´ aquina es barata ´ o consume mucha enerǵıa, entonces no es productiva. Si la m´ aquina es roja,entonces es productiva. Pero la m´ aquina es barata. Por lo tanto, la m´ aquina no es roja.”

Solución

Asignamos letras a las frases que componen el razonamiento:


Ejemplos

Ejemplo 3 2


61/194

Ejemplo 3.2


Solución


B : La máquina es barata. E : La máquina consume mucha enerǵıa.P : La máquina es productiva. R : La máquina es roja.


Ejemplos

Ejemplo 3 2


62/194

Ejemplo 3.2


Solución



Forma esquemática:

(B ∨ E ) ⇒ ¬P R ⇒ P B

¬R


Ejemplos

Ejemplo 3 2


63/194

Ejemplo 3.2


Solución




(B ∨ E ) ⇒ ¬P R ⇒ P B

¬R

Razonamiento de inferencia:


Ejemplos

Ejemplo 3.2


64/194

Ejemplo 3.2


Solución




(B ∨ E ) ⇒ ¬P R ⇒ P B

¬R


1. (B ∨

E ) ⇒ ¬P Hipótesis2. R ⇒ P Hipótesis3. B Hipótesis4. B ∨ E 3, adición5. ¬P 1,4, modus ponens6. ¬P ⇒ ¬R 2, contrarrećıproco7. ¬R 5,6, modus ponens.


Ejemplos

Ejemplo 3.2


65/194

Ejemplo 3.2


Solución




(B ∨ E ) ⇒ ¬P R ⇒ P B

¬R


1.

(B ∨ E

) ⇒ ¬P

Hipótesis2. R ⇒ P Hipótesis3. B Hipótesis4. B ∨ E 3, adición5. ¬P 1,4, modus ponens6. ¬P ⇒ ¬R 2, contrarrećıproco7. ¬R 5,6, modus ponens.


Ejemplos


66/194

Ejemplo 3.3

Utilice las reglas de inferencia para justificar la siguiente deducci´ on:

S ⇒ (P ∨ Q)S

¬P Q

Solución

1. S ⇒ (P ∨ Q) Hipótesis


Ejemplos


67/194

Ejemplo 3.3


S ⇒ (P ∨ Q)S

¬P Q

Solución

1. S ⇒ (P ∨ Q) Hipótesis2. S Hipótesis


Ejemplos


68/194

Ejemplo 3.3


S ⇒ (P ∨ Q)S

¬P Q

Solución

1. S ⇒ (P ∨ Q) Hipótesis2. S Hipótesis3. ¬P Hipótesis


Ejemplos


69/194

Ejemplo 3.3


S ⇒ (P ∨ Q)S

¬P Q

Solución

1. S ⇒ (P ∨ Q) Hipótesis2. S Hipótesis3. ¬P Hipótesis4. P ∨ Q 1,2, modus ponens5. Q 3,4, eliminación de falsa en ∨ .


Ejemplos


70/194

Ejemplo 3.3


S ⇒ (P ∨ Q)S

¬P Q

Solución

1. S ⇒ (P ∨ Q) Hipótesis2. S Hipótesis3. ¬P Hipótesis4. P ∨ Q 1,2, modus ponens5. Q 3,4, eliminación de falsa en ∨ .


71/194


Ejemplos

Ejemplo 3.4


72/194

j p


P ∨ (Q ∧ P )S ∨ T

S ⇒ ¬(P ∨ Q)P ∧ T

Solución

1. P ∨ (Q ∧ P ) Hipótesis2. S ∨ T Hipótesis


73/194


74/194


Ejemplos

Ejemplo 3.4


75/194


P ∨ (Q ∧ P )S ∨ T

S ⇒ ¬(P ∨ Q)P ∧ T

Solución

1. P ∨ (Q ∧ P ) Hipótesis2. S ∨ T Hipótesis3. S ⇒ ¬(P ∨ Q) Hipótesis4. (P ∨ Q) ∧ (P ∨ P ) 1, distributiva5. P ∨ Q 4, simplificación

6. ¬¬(P ∨ Q) ⇒ ¬S 3, contrarrećıproco7. (P ∨ Q) ⇒ ¬S 6, doble negación8. ¬S 5,7, modus ponenes9. T 2,8, eliminación de la falsa en ∨

10. P ∨ P 4, simplificación11. P 10, equivalencia (P ∨ P ) ⇔ P 12. P ∧ T 9,11, simultaneidad.


Ejemplos

Ejemplo 3.5


76/194


¬(P ∨ ¬R)Q ∨ P

R ⇒ S (Q ∧ S ) ⇒ (T ∧ S )T

Solución

1. ¬(P ∨ ¬R) Hipótesis


Ejemplos

Ejemplo 3.5


77/194


¬(P ∨ ¬R)Q ∨ P

R ⇒ S (Q ∧ S ) ⇒ (T ∧ S )T

Solución

1. ¬(P ∨ ¬R) Hipótesis2. Q ∨ P Hipótesis


78/194


Ejemplos

Ejemplo 3.5


79/194


¬(P ∨ ¬R)Q ∨ P

R ⇒ S (Q ∧ S ) ⇒ (T ∧ S )T

Solución

1. ¬(P ∨ ¬R) Hipótesis2. Q ∨ P Hipótesis3. R ⇒ S Hipótesis4. (Q ∧ S ) ⇒ (T ∧ S ) Hipótesis


Ejemplos

Ejemplo 3.5


80/194


¬(P ∨ ¬R)Q ∨ P

R ⇒ S (Q ∧ S ) ⇒ (T ∧ S )T

Solución

1. ¬(P ∨ ¬R) Hipótesis2. Q ∨ P Hipótesis3. R ⇒ S Hipótesis4. (Q ∧ S ) ⇒ (T ∧ S ) Hipótesis5. ¬P ∧ ¬¬R 1, Ley D’Morgan

6. ¬P 5, simplificación7. ¬¬R 5, simplificación8. R 7, doble negación9. Q 2,6, eliminación de la falsa en ∨

10. S 3,8, modus ponens11. Q ∧ S 9,10, simultaneidad12. T ∧ S 4,11, modus ponens

13. T

12 simplificación Introducción Cálculo Proposicional Deducciones Lógicas Cuantificadores Métodos de Demostración

Ejemplos

Ejemplo 3.5


81/194


¬(P ∨ ¬R)Q ∨ P

R ⇒ S (Q ∧ S ) ⇒ (T ∧ S )T

Solución

1. ¬(P ∨ ¬R) Hipótesis2. Q ∨ P Hipótesis3. R ⇒ S Hipótesis4. (Q ∧ S ) ⇒ (T ∧ S ) Hipótesis5. ¬P ∧ ¬¬R 1, Ley D’Morgan

6. ¬P 5, simplificación7. ¬¬R 5, simplificación8. R 7, doble negación9. Q 2,6, eliminación de la falsa en ∨

10. S 3,8, modus ponens11. Q ∧ S 9,10, simultaneidad12. T ∧ S 4,11, modus ponens

13. T

12 simplificación Introducción Cálculo Proposicional Deducciones Lógicas Cuantificadores Métodos de Demostración

Simboloǵıa

2


82/194

La afirmación “x2 ≤ 3” depende de una variable x:

P : x2 ≤ 3

La asignación tendrá en cuenta la(s) variable(s) involucrada(s):

P (x) : x2

≤ 3


Simboloǵıa

2


83/194


P : x2 ≤ 3


P (x) : x2

≤ 3

Cada valor de x conduce a una proposición:


Simboloǵıa

L fi i´ “ 2 3” d d d i bl


84/194


P : x2 ≤ 3


P (x) : x2

≤ 3


P (3) representa 32 ≤ 3 ( falsa )


Simboloǵıa

L fi i´ “ 2 ≤ 3” d d d i bl


85/194


P : x2 ≤ 3


P (x) : x2

≤ 3



P (−1) representa (−1)2 ≤ 3 (verdadera )


Simboloǵıa

L fi i´ “ 2 ≤ 3” d d d i bl


86/194


P : x2 ≤ 3


P (x) : x2

≤ 3




P (y + 1) es (y + 1)2 ≤ 3 (depende del valor de y )


Simboloǵıa

La afirmación “x2 ≤ 3” depende de una ariable x


87/194

La afirmacion “x2 ≤ 3” depende de una variable x:

P : x2 ≤ 3


P (x) : x2

≤ 3




P (y + 1) es (y + 1)2 ≤ 3 (depende del valor de y )


Ejemplos

Ejemplo 4.1 (Ejemplos de afirmaciones dependientes variables)

P ( ) di i ibl 3


88/194

P (n) : n es divisible por 3.Q

(n

) : n

es divisible por 6.R(x) : la persona x vive en Medel ĺın.S (x) : la persona x conoce el pueblito paisa.

Q(n) ⇒ P (n) representa

“si n es divisible por 6, entonces es divisible por 3”


Ejemplos


P ( ) di i ibl 3


89/194

P (n) : n es divisible por 3.Q(n) : n es divisible por 6.R(x) : la persona x vive en Medel ĺın.S (x) : la persona x conoce el pueblito paisa.



P (n) ∧ ¬Q(n) representa“n es divisible por 3 pero no por 6”

P (9) ∧ ¬Q(9) es verdadero

P (18) ∧ ¬Q(18) es falsa


Ejemplos


P (n) n di i ibl 3


90/194






P (18) ∧ ¬Q(18) es falsa

R(x) ⇔ S (x) significa“la persona x vive en Medelĺın si, y sólo si, conoce el pueblito paisa”


Ejemplos


P (n) : n es divisible por 3


91/194






P (18) ∧ ¬Q(18) es falsa

R(x) ⇔ S (x) significa“la persona x vive en Medelĺın si, y sólo si, conoce el pueblito paisa”


Cuantificadores

Definición 4.1 (Cuantificadores)

Introducimos los siguientes śımbolos l´ ogicos


92/194

∀ el cuantificador universal.

∃ el cuantificador existencial.Dada una afirmaci´ on P (x) que depende de la variable x, utilizamos los cuantificadores para abreviar las siguientes afirmaciones

∀xP (x) todos los objetos cumplen P (x).

∃xP (x) existe un objeto que cumple P (x).Otra forma de leer ∃xP (x) es “alg´ un objeto cumple P (x)”.

∀n(Q(n) ⇒ P (n)) significa

“todo número entero divisible por 6 es divisible por 3”


Cuantificadores




93/194






“todo número entero divisible por 6 es divisible por 3”∃n(P (n) ∧ ¬Q(n)) significa

“existe un entero divisible por 3 y no divisible por 6”


Cuantificadores




94/194








∀x(R(x) ⇔ S (x)) significa“toda persona vive en Medelĺın si, y sólo si, conoce el pueblito paisa”


Cuantificadores




95/194








∀x(R(x) ⇔ S (x)) significa“toda persona vive en Medelĺın si, y sólo si, conoce el pueblito paisa”


Cuantificadores

Definición 4.2 (Cuantificadores acotados)

Dado un conjunto U y una afirmaci´ on P (x), introducimos la siguiente


96/194

( )notaci´ on

∀x∈U P (x) todos los objetos de U cumplen P (x).∃x∈U P (x) existe un objeto en U que cumple P (x).

∀x∈U y ∃x∈U se llaman cuantificadores acotados.

∀n∈Z(Q(n) ⇒ P (n)) significa“todo número entero divisible por 6 es divisible por 3”


Cuantificadores




97/194

notaci´ on




∃n∈Z(P (n) ∧ ¬Q(n)) significa“existe un número entero divisible por 3 pero que no es divisible por 6 ”


Cuantificadores




98/194

notaci´ on





∀x∈U (R(x) ⇔ S (x)) significa“toda persona vive en Medelĺın si y solo si conoce el pueblito paisa ”


Cuantificadores




99/194

notaci´ on





∀x∈U (R(x) ⇔ S (x)) significa“toda persona vive en Medelĺın si y solo si conoce el pueblito paisa ”


Cuantificadores

Definición 4.3 (Existencia única)

Dada una afirmaci´ on P (x) y un conjunto U , denotamos por


100/194

∃!xP (x) existe un ´ unico objeto que cumple P (x).∃!x∈U P (x) existe un ´ unico objeto en U que cumple P (x).∃! se denomina el cuantificador de existencia ´ unica y ∃!x∈U es el cuantificador acotado de existencia ´ unica.

Ejemplo:U es el conjunto de los seres humanos

P (x, y) : “y es la madre de x”


101/194


Cuantificadores




102/194

∃!xP

(x

) existe un ´ unico objeto que cumple P

(x

).∃!x∈U P (x) existe un ´ unico objeto en U que cumple P (x).∃! se denomina el cuantificador de existencia ´ unica y ∃!x∈U es el cuantificador acotado de existencia ´ unica.



∀x∈U ∃!y∈U P (x, y) significa“todo ser humano tiene una única madre”

“Existe un único numero real tal que al sumarse con cualquier otro reales igual a éste último”:

∃!z∈R∀x∈R(x + z = x)


Cuantificadores




103/194

∃!xP

(x

) existe un ´ unico objeto que cumple P

(x

).∃!x∈U P (x) existe un ´ unico objeto en U que cumple P (x).∃! se denomina el cuantificador de existencia ´ unica y ∃!x∈U es el cuantificador acotado de existencia ´ unica.



∀x∈U ∃!y∈U P (x, y) significa“todo ser humano tiene una única madre”

“Existe un único numero real tal que al sumarse con cualquier otro reales igual a éste último”:

∃!z∈R∀x∈R(x + z = x)


Cálculo de Predicados

Definición 4.4 (Cálculo de Predicados)

El Cálculo de Predicados es la extensi´ on del C´ alculo Propocisional al lenguaje con variables y cuantificadores Llamaremos Teorema a una


104/194

lenguaje con variables y cuantificadores. Llamaremos Teorema a una

afirmaci´ on que es verdadera (ya sea en el C´ alculo de Predicados y en las matem´ aticas).

Todas las tautoloǵıas son teoremas del Cálculo de Predicados




El Cálculo de Predicados es la extensi´ on del C´ alculo Propocisional al lenguaje con variables y cuantificadores Llamaremos Teorema a una


105/194




Proposici´ on : con esta palabra enunciamos teoremas y propiedades

generales del cálculo de predicados


106/194




El Cálculo de Predicados es la extensi´ on del C´ alculo Propocisional al lenguaje con variables y cuantificadores. Llamaremos Teorema a una


107/194




Proposici´ on : con esta palabra enunciamos teoremas y propiedades

generales del cálculo de predicados

Proposición 4.1

Los siguientes son teoremas del C´ alculo de Predicados.

(a) (

∀x∈U P (x))

⇔ ∀x(x

∈ U

⇒ P (x)).

(b) (∃x∈U P (x)) ⇔ ∃x(x ∈ U ∧ P (x)).(c) (∃!xP (x)) ⇔

`(∃xP (x)) ∧ ∀x∀y((P (x) ∧ P (y)) ⇒ x = y)

´.

(d) (∃!x∈U P (x)) ⇔`

(∃x∈U P (x)) ∧ ∀x∈U ∀y∈U ((P (x) ∧ P (y)) ⇒ x = y)´

.

(e) (∃!x∈U P (x)) ⇔ ∃!x(x ∈ U ∧ P (x)).


Cuantificadores

Proposición 4.2 (Negación de cuantificadores)



108/194

(a) (¬∀xP (x)) ⇔ ∃x(¬P (x)) (negaci´ on del cuantificador univeral).(b) (¬∃xP (x)) ⇔ ∀x(¬P (x)) (negaci´ on del cuantificador existencial).(c) (¬∀x∈U P (x)) ⇔ ∃x∈U (¬P (x)) (negaci´ on del cuantificador univeral

acotado).

(d) (¬∃x∈U P (x)) ⇔ ∀x∈U (¬P (x)) (negaci´ on del cuantificador existencial acotado).

∃xP (x) equivale a ¬∀x¬P (x)


Cuantificadores




109/194


acotado).



∃ se puede definir en términos de ∀


Cuantificadores




110/194


acotado).




Todo el Cálculo de Predicados se puede construir sólo con los śımbolos

¬ , ∨ , ∀


Cuantificadores




111/194


acotado).




Todo el Cálculo de Predicados se puede construir sólo con los śımbolos

¬ , ∨ , ∀


Ejemplo 4.2

Denotemos por P (x, y) la afirmaci´ on “a la persona x le gusta la fruta y”.

1 ∀x∀yP (x, y) A todas las personas les gusta todas las frutas.


112/194


Ejemplo 4.2


1 ∀x∀yP (x, y) A todas las personas les gusta todas las frutas.2 P (x y)


113/194

2

∀y

∀xP (x, y)


Ejemplo 4.2


1 ∀x∀yP (x, y) A todas las personas les gusta todas las frutas.2 y xP (x y) Todas las frutas les gustan a todas las personas.


114/194

∀y

∀xP (x, y) Todas las frutas les gustan a todas las personas.


Ejemplo 4.2


1 ∀x∀yP (x, y) A todas las personas les gusta todas las frutas.2 y xP (x, y) Todas las frutas les gustan a todas las personas.


115/194

∀y


3 ∃x∀yP (x, y)


116/194


Ejemplo 4.2




117/194

∀y

∀x ( , y) f g p

3 ∃x∀yP (x, y) Hay una persona que le gustan todas las frutas.4 ∀y∃xP (x, y)


Ejemplo 4.2




118/194

∀y

∀( , y) f g p

3 ∃x∀yP (x, y) Hay una persona que le gustan todas las frutas.4 ∀y∃xP (x, y) Cualquier fruta le gusta al menos a una persona.


Ejemplo 4.2




119/194

∀ ∀3 ∃x∀yP (x, y) Hay una persona que le gustan todas las frutas.4 ∀y∃xP (x, y) Cualquier fruta le gusta al menos a una persona.5 ∃y∀xP (x, y)


Ejemplo 4.2




120/194

∀ ∀3 ∃x∀yP (x, y) Hay una persona que le gustan todas las frutas.4 ∀y∃xP (x, y) Cualquier fruta le gusta al menos a una persona.5 ∃y∀xP (x, y) Hay una fruta que le gusta a todas las personas.


Ejemplo 4.2




121/194

∀ ∀3 ∃x∀yP (x, y) Hay una persona que le gustan todas las frutas.4 ∀y∃xP (x, y) Cualquier fruta le gusta al menos a una persona.5 ∃y∀xP (x, y) Hay una fruta que le gusta a todas las personas.6

∀x

∃yP (x, y)


Ejemplo 4.2




122/194


∀x

∃yP (x, y) A cualquier persona le gusta al menos una fruta.


Ejemplo 4.2




123/194


∀x


7 ∃x∃yP (x, y)


Ejemplo 4.2


1 ∀x∀yP (x, y) A todas las personas les gusta todas las frutas.2

∀y



124/194


∀x


7 ∃x∃yP (x, y) Hay una persona a la que le gusta alguna fruta.


Ejemplo 4.2



∀y



125/194


∀x


7 ∃x∃yP (x, y) Hay una persona a la que le gusta alguna fruta.8 ∃y∃xP (x, y)


Ejemplo 4.2



∀y



126/194

∀ ∀3 ∃x∀yP (x, y) Hay una persona que le gustan todas

1. lógica simbólica y demostraciones

Documents