Download Auxiliar 1: Lógica - U

Universidad de Chile
Facultad de Ciencias Físicas y Matemáticas
Departamento de Ciencias de la Computación
Semestre Otoño 2009
Matemáticas Discretas
CC3101
Profesor:Pablo Barceló
Auxiliares: Gonzalo Ríos, Juan Reutter
Fecha: 18 de Marzo
Auxiliar 1: Lógica
1
Materia
1. Alfabeto
(a) Variables proposicionales (P): p, q, r ,...
(b) Conectivos lógicos: :; _; ^; !; !
(c) Símbolos de puntuación: (, )
2. Lenguaje de las fórmulas proposicionales
L(P) es el menor conjunto que satisface las siguientes reglas:
(a) P
L(P )
(b) Si ' 2 L(P), entonces (:') 2 L(P).
(c) Si ';
2 L(P), entonces ('
), con
2 f_; ^; !; !g
3. Semántica
(a) Valuación (asignación):
: P ! f0; 1g
(b) Extensión: ^ : L(P ) ! f0; 1g: Dada ' 2 L(P)
i.
ii.
iii.
iv.
v.
si
si
si
si
si
' = p; entonces ^ (') = (p)
' = (: ); entonces ^ (') = 1 ^ (')
' = ( ^ ); entonces ^ (') = min(^ ( ); ^ ( ))
' = ( _ ); entonces ^ (') = max(^ ( ); ^ ( ))
'=(
! ); entonces ^ (') = max(1 ^ ( ); ^ ( ))
1 si ^ ( ) = ^ ( )
vi. si ' = (
! ); entonces ^ (') =
0 si ^ ( ) 6= ^ ( )
4. De…niciones previas
(a) Una fórmula ' es satisfacible si existe
tal que (') = 1
(b) Una fórmula ' es tautología si su negación es insatisfacible.
P
P
P
(c) Para un conjunto de fórmulas
escribimos ( ) = 1 si para toda fórmula ' en
se tiene que (') = 1
5. Consecuencia lógica
La fórmula ' es consecuencia lógica de
Esto lo denotamos
6. Dos fórmulas ' y
,
P
j= '
P
si para toda valuación :
P
( ) = 1 =) (') = 1
son equivalentes, denotado '
; si ' j=
y
j= '. De la misma forma, si para toda valuación
(') = 1 , (') = 1
7. Un conjunto de conectivos lógicos es funcionalmente completo si se puede representar cualquier tabla de verdad usando
solo esos conectivos
Ejemplo: f_; ^; :g
8. Teoremas Importantes de Satisfacibilidad
P
P
(a) (Monotonía) Si
j= '; entonces para cada fórmula se tiene que
[f g j= '
P
P
(b)
j= ' si y solo sí
[f:'g es insatisfacible
P
P
(c) Para todo conjunto …nito de fórmulas
y fórmula existe tal que
j= si y solo
P
P
(d)
es insatisfacible si y solo sí para cada fórmula ;
j=
P
P
(e)
es insatisfacible si y solo sí para cada fórmula insatisfacible ;
j=
es tautología.
9. Predicados
(a) Un predicado es una proposición que además menciona a ciertas variables: x = y + 5
(b) Denotamos los predicados por P (x); Q(x; y); R(x; y; z)::
10. Cuanti…cadores
(a) Un cuanti…cador crea una proposición a partir de una fórmula con variables.
(b) 8xP (x) dice que todo elemento del dominio tiene la propiedad P
(c) 9xP (x) dice que existe un elemento del dominio tiene la propiedad P
(d) Si un cuanti…cador es usado sobre una variable x, entonces decimos que la variable x aparece cuanti…cada o ligada
en la fórmula.
(e) Para que una fórmula tenga un valor de verdad, entonces todas sus variables deben estar ligadas.
11. Dominio de Discurso
(a) Un dominio de discurso es una "estructura" en donde se evalúan las proposiciones
(b) El valor de verdad de una oración ahora depende del dominio de discurso.
(c) Decimos que dos oraciones son equivalentes, si el valor de ambas fórmulas es el mismo, no importa cual sea el
dominio de discurso y como interpretemos los predicados en ese dominio.
12. Reglas de inferencia
(a) Modus Ponens: {p,p! qg j= q
(b) Modus Tollens: {~q; p ! qg j= ~p
(c) Razonamiento Transitivo: {p ! q; q ! rg j= p ! r
(d) Instanciación Universal: {8xP (x)}j= P (c)
(e) Generalización Universal: {P (c); para un c arbitrario}j= 8xP (x)
(f) Generalización Existencial: {P (c); para algun c}j= 9xP (x)
13. Teoremas
(a) Un teorema es una proposición matemática que puede ser demostrada que es verdad.
(b) Se asume que un teorema es una proposición matemática importante, de otra forma se llama simplemente proposición.
(c) Resultados intermedios se llaman lemas.
(d) Un corolario es un teorema que puede ser probado fácilmente de otro teorema probado anteriormente.
(e) Una conjetura es algo que se piensa que es verdadero, pero para lo cual no existe demostración.
14. Demostraciones
(a) Una demostración directa de p ! q se construye de la siguiente forma:
i. Asuma que p es verdadero.
ii. Deduzca otras proposiciones a partir de p utilizando las reglas de inferencias y los axiomas.
iii. Deténgase una vez que haya obtenido la proposición q.
(b) Las demostraciones por contraposición están basadas en que para demostrar p!q basta demostrar ~q! ~p
(c) Una demostración por contradicción es:
i. Asuma que queremos demostrar p.
ii. encontrar una contradicción q tal que ~p ! q es cierto
iii. concluir que p es cierto
2
Ejercicios
1. Formalice el siguiente argumento en el cálculo proposicional:
“Si Superman fuera capaz y deseara prevenir el mal, entonces lo haría. Si Superman fuera incapaz de prevenir el
mal, entonces sería impotente, y si no deseara prevenir el mal, entonces sería malévolo. Si Superman existe, no es ni
impotente ni malévolo. Superman no previene el mal. Entonces, Superman no existe.”
2. Demuestre que existen
;
tal que
2
y
2~
3. Dado ; 2 L(P), demuestre que j= y j= si y sólo si j= ( $ )
P
P
4. P
Dado
L(P) y '; ; 2 L(P), demuestre que si ' !
es tautología, entonces
[f'; g j=
[f'g j=
P
P
5. Dado
= f~p _ q; r _ ~p; r _ qg y = ~p _ (q ^ r); demuestre que
j=
6. Sean
y dos formulas. Demuestre que {8x( ! ); 8x }j= 8x
P
P
7. Dado ={R(a,b),P(a),~P (b); ~R(b,a)} y = 9x9yR(x,y)^P(x)^~P(y), demuestre que
j=
8. Los Axiomas de la teoría de grupos son
(a) 8x8y8z; (x y) z = x (y z)
(b) 8x9y; x y = e
(c) 8x; x e = x
Demuestre que:
(a) 8x9y; y x = x y = e
(b) 8x; e x = x
(c) 8x8y8z; x y = e ^ y z = e ! x = z
Dem
1. Demostración Directa
x y=e
y e=y
y (x y) = y
(y x) y = y
y z=e
((y x) y) z = y z
(y x) (y z) = e
(y x) e = e
(y x) = e
2. Demostración Directa
x e=x
y x=x y=e
x (y x) = x e
(x y) x = x
e x=x
3. Demostración por contradicción
x y = e ^ y z = e ^ x 6= z
x y=e
y z=e
x 6= z
x 6= e z
x 6= (x y) z
x 6= x (y z)
x 6= x e
x 6= x
si y solo si