06psfi-icla3
Post on 14-Apr-2015
22 Views
Preview:
TRANSCRIPT
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 1
Fundamentos de Informática 1
Cálculo Proposicional
Dr. Gonzalo Hernández Oliva
Universidad Técnica Federico Santa MaríaDepartamento de Informática
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 2
Cálculo Proposicional:1) Motivación2) Introducción3) Argumentos y Proposiciones Lógicas4) Conectivos Lógicos5) Estudio Proposiciones6) Tautología, Contradicción y Argumento
Válido7) Leyes Álgebra Proposicional8) Formas Normales9) Implicaciones y Derivaciones Lógicas
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 3
Problema NP: Problema SAT
Enumerar (Hacer una lista) todos los
valores de verdad de una proposición
lógica.
Algoritmo Backtracking
1) Motivación:Cálculo Proposicional:
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 4
Cálculo Proposicional:2) IntroducciónLa Lógica resulta esencial para construir, diseñar, implementar y probar correctitud en algoritmos y programas.Es necesario estudiar las Leyes Fundamentales de las Derivaciones Lógicas para estudiar la validez de las afirmaciones realizadasLas Proposiciones forman las Derivaciones y sus Operaciones el Cálculo Proposicional
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 5
Cálculo Proposicional: 3) Argumentos y Props. Lógicas
Argumentos (Afirmaciones, Conclusiones, Demostraciones) son Válidos o No Lógicamente: V ó F
Proposiciones forman los Argumentos
Proposiciones Atómicas son aquellas proposiciones que no pueden subdividirse y pueden unirse por conexiones lógicas
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 6
Cálculo Proposicional: 3) Argumentos y Props. LógicasEjemplos:
1) P: Si la demanda crece entonces las compañias se expanden.
P: Si las compañias se expanden entonces contratan trabajadores.
C: Si la demanda crece entonces las compañías contratan trabajadores.
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 7
2) Este programa de computadora tiene un error, o el input es erróneo. El input no es erróneo. El programa de computadora tiene un error.
3) Una universidad es de prestigio si los académicos que la forman realizan docencia e investigación de gran calidad.
Cálculo Proposicional: 3) Argumentos y Props. Lógicas
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 8
4) La extracción de mineral es rentable si la concentración es alta, pero solamente si la distancia al mercado es pequeña.
5) Si llueve con frecuencia los agricultores se quejan. Si no llueve con frecuencia los agricultores se quejan. Luego, los agricultores se quejan.
Cálculo Proposicional: 3) Argumentos y Props. Lógicas
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 9
De manera formal: (Aristóteles)Una proposición es una afirmación que es o bien verdadera o bien falsa.Elementos de una proposición:
Variables Proposicionales: Asignación de Valor Lógico Binario: V ó FConstantes Proposicionales: V , FConectivos u Operaciones Lógicas
Cálculo Proposicional: 3) Argumentos y Props. Lógicas
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 10
Proposición Atómica:Una proposición atómica es una proposición que tiene una única variable o constante proposicional.Las proposiciones no atómicas se denominan compuestas.Todas las proposiciones compuestas tienen al menos una conexión lógica
Cálculo Proposicional: 3) Argumentos y Props. Lógicas
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 11
Cálculo Proposicional: 4) Conectivos Lógicos
Los conectivos lógicos son operadores entre props. que permiten construir proposiciones complejas en base a proposiciones más simples o atómicas. Los conectivos lógicos básicos son:
Negación: ∼ PConjunción: P ∧ QDisyunción: P ∨ QCondicional: P ⇒ QBicondicional o Equivalencia: P ⇔ Q
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 12
Los conectivos lógicos se definen mediante su tabla de verdad:
Para su operación se ha definido un orden en base a su prioridad:
Alta (∼) → (∧) → (∨) → (⇒) → (⇔) Baja
P Q ∼ P ∼ Q P ∨ Q P ∧ Q P ⇒ Q P ⇔ Q V V F F V V V V V F F V V F F F F V V F V F V F F F V V F F V V
Cálculo Proposicional: 4) Conectivos Lógicos
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 13
Para estudiar proposiciones lógicas o expresiones más complejas se tienen 2 herramientas fundamentales:
Tablas de Verdad: Obtenido en base a las expresiones más simples y proposiciones atómicas que las forman Árbol de Análisis Sintáctico: Descomposición de la expresión en base a sus proposiciones atómicas.
Cálculo Proposicional: 5) Estudio Proposiciones
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 14
Dada una proposición es posible estudiar su validez asignando valores de verdad a sus proposiciones atómicas y calcular los valores de verdad de las proposiciones compuestas que la forman en base a las definiciones de los conectivos lógicos. Todas las posibilidades de este cálculo lógico se resumen en una Tabla de Verdad
Cálculo Proposicional: 5) Estudio Proposiciones: TV
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 15
Ejemplos:1) P ⇒ (Q ∧ R) ∧ (∼ P ⇒ R)2) (P ∨ R) ∧ ∼ (P ∨ Q) ⇒ Q ∨ R3) (P ∨ (Q ⇒(R ∧ ∼P ))) ⇔ (Q ∧ R)4) (P ∧ Q) ∨ (∼P ∧ Q ) ∨ (P ∧ ∼Q )∨ ∼Q 5) Si Micaela gana en las Olimpiadas, todos la
admirarán y ella será muy feliz, pero si no gana, todo su esfuerzo fue en vano
Cálculo Proposicional: 5) Estudio Proposiciones TV
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 16
6) La extracción de minerales es provechosa si la concentración de mineral es alta pero sólo si la distancia al mercado es corta
7) Si p es un número primo entonces para los enteros pares (np–n) es divisible por p
8) Los productos comprados en esta tienda pueden ser devueltos sólo si están en buenas condiciones y el cliente trae la boleta
Cálculo Proposicional: 5) Estudio Proposiciones
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 17
Una Expresión Lógica es una Tautología si es Verdadera para todas las asignaciones posibles de valores de verdad. En este caso se antepondrá el símbolo Una Expresión Lógica es una Contradicciónsi es Falsa para todas las asignaciones posibles de valores de verdad.Una Expresión Lógica que no es una tautología ni una contradicción es una Contingencia (Causalidad/Eventualidad).
|=
Cálculo Proposicional: 6) Tautología y Contradicción
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 18
Cálculo Proposicional: 6) TautologíasEjemplo tautología: Ley del Medio Excluido:
|= P ∨ ∼PTeorema: Sea A una expresión tautológica y sean P1 ... Pn sus variables proposicionales. Suponga que B1 ... Bn son expresiones arbitrarias. La expresión obtenida al reemplazar Pi por Bi es una esquema y toda particularización (ejemplo) de este esquema es una tautología.
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 19
Tipos de Tautologías:
Implicaciones Lógicas: |= A ⇒ B (A ≡ > B)
Equivalencias Lógicas: |= A ⇔ B (A ≡ B)
Este tipo de tautología se utiliza para demostrar y construir nuevas leyes (Álgebra de Proposiciones) Cabe hacer notar que: A ⇔ B ≠ A ≡ B
Cálculo Proposicional: 6) Tautologías
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 20
Diremos que un argumento lógico es válido si la conclusión se deduce lógicamente de las premisas: Si todas las premisas son verdaderas entonces también lo es la conclusión.Luego, si A es la conjunción de todas las premisas y C la conclusión, entonces: |= A ⇒ C . Ejemplo: Silogismo Disjuntivo:
|= (P ∨ Q) ∧ ∼P ⇒ Q
Cálculo Proposicional: 6) Argumento Válido
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 21
Cálculo Proposicional: 7) Leyes Álgebra Proposicional1) Medio Excluido: (P ∨ ∼ P) ≡ V2) Contradicción: ( P ∧ ∼ P) ≡ F3) Identidad: (P ∨ F) ≡ P , (P ∧ V) ≡ P 4) Dominación: (P ∨ V) ≡ V , (P ∧ F) ≡ F5) Idempotencia: (P ∨ P) ≡ P , (P ∧ P) ≡ P6) Doble Negación: ∼ (∼ P ) ≡ P7) Absorción: P ∧ (P ∨ Q) ≡ P
P ∨ (P ∧ Q) ≡ P
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 22
8) Conmutatividad : P ∨ Q ≡ Q ∨ P P ∧ Q ≡ Q ∧ P
9) Asociatividad: (P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R)(P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R)
10) Distributividad: P ∨ (Q ∧ R) ≡ (P ∨ Q ) ∧ (P ∨ R )P ∧ (Q ∨ R) ≡ (P ∧ Q )∨ (P ∧ R )
Cálculo Proposicional: 7) Leyes Álgebra Proposicional
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 23
11) Leyes de DeMorgan: ∼ ( P ∨ Q ) ≡ (∼ P ∧ ∼ Q ) ∼ ( P ∧ Q ) ≡ (∼ P ∨ ∼ Q )
12) Implica: P ⇒ Q ≡ (∼ P ∨ Q )
13) Contrarecíproca:P ⇒ Q ≡ (∼ Q ⇒ ∼ P)
14) Equivalencia: P ⇔ Q ≡ (∼ P ∨ Q ) ∧ ( P ∨ ∼ Q ) P ⇔ Q ≡ ( P ⇒ Q ) ∧ ( Q ⇒ P )
Cálculo Proposicional: 7) Leyes Álgebra Proposicional
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 24
Ejercicios:Expresar las siguientes proposiciones en base a los conectivos: ∨ ∧ ∼
1) P ⇒ Q ∨ ∼ (P ⇒ Q)2) P ⇔ (Q ∧ P) ⇒ Q3) P ∧ (P ⇒ Q) ⇒ Q4) P ⇒ (Q ∧ R) ⇒ ∼ (P ⇒ F)5) ∼ (P ⇒ Q) ∧ ( P ⇔ R ) ∨ ( Q ⇒ V )
Cálculo Proposicional: 7) Leyes Algebra Proposicional
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 25
Una Expresión Lógica está en forma normal disyuntiva si está escrita como una disyunción de términos que son conjunciones de variables lógicas o de negaciones de variables lógicas.Análogamente se define forma normal conjuntiva. Ejemplos:P ∨ (∼ Q ∧ R ) , (P ∨ Q ∨ R) ∧ (∼ Q ∨ R) ∧ R
Cálculo Proposicional: 8) Formas Normales
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 26
Pasos para obtener la forma normal conjuntiva (disyuntiva) de una proposición lógica PL mediante la aplicación de las leyes del álgebra proposicional:
1o) Eliminar en PL todos los conectivos ⇔ y ⇒2o) Eliminar subexpresiones de PL que están
negadas. Por ejemplo: ∼ (P ∨ R)3o) Aplicar las leyes de distributividad4o) Ordenar la expresión
Cálculo Proposicional: 8) Formas Normales
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 27
Ejercicio: Obtener la forma normal conjuntiva (disyuntiva) de:
a) (P∨ Q) ∧ (P ∧ (Q ∨ R)) ∨ ∼ ( P ∨ (R∧ Q ))b) (P ⇒ Q) ∧ ∼((P ⇔ R) ∨ ∼(R ∧ Q))
Podemos construir una forma normal disyuntiva a partir de la tabla de verdad de una expresión lógica.Aprendamos cómo mediante un ejemplo …
Cálculo Proposicional: 8) Formas Normales
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 28
Cálculo Proposicional: 8) Formas Normales
PLRQPVVVVVFVVVVFVFFFV
FFFFFVFFFFVFVVVF
Obtenemos la proposición lógica PL(P,Q,R) en forma normal disyuntiva partir de su tabla de verdad:
PL(P,Q,R) = …
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 29
Un término mínimo (minterm) es una conjunción de literales en los cuales cada variable o su negación se representa una única vez y cada término será verdadero para sólo una asignación de valores de verdad. Si una expresión lógica esta expresada como una disyunción de términos mínimos se denomina forma normal disjuntiva completa
Cálculo Proposicional: 8) Formas Normales
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 30
Pasos para obtener la forma normal conjuntiva de una proposición lógica PL mediante su tabla de verdad de:
1o) Obtener formal normal disyuntiva de ∼PL
2o) Negar formal normal disyuntiva de ∼PL aplicando leyes del álgebra proposicional
Veamos un ejemplo …
Cálculo Proposicional: 8) Formas Normales
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 31
Cálculo Proposicional: 8) Formas Normales
PLRQPVVVVVFVVVVFVFFFV
VFFFFVFFFFVFVVVF
Obtenemos la proposición lógica PL(P,Q,R) en forma normal conjuntiva partir de su tabla de verdad:
PL(P,Q,R) = …
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 32
Diremos que un argumento lógico es válidosi la conclusión se deduce lógicamente de las premisas.Si A es la conjunción de todas las premisas y C la conclusión, entonces: |= A ⇒ CA continuación veremos herramientas = Implicancias Lógicas para demostrar si un argumento es válido – Razonamiento Válido.Un argumento no válido es una falacia
Cálculo Proposicional: 9) Implicaciones y Deriv. Lógicas
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 33
Un ejemplo de razonamiento válido es el:P ≡ V P⇒ Q ≡ VQ ≡ V
Esta conclusión se denota: P , P⇒ Q |= QOtro ejemplo:
(P ∨ Q) ≡ V∼P ≡ VQ ≡ V
Cálculo Proposicional: 9) Implicaciones y Deriv. Lógicas
Modus Ponens
Silogismo Disjuntivo|= (P ∨ Q) ∧ ∼P ⇒ Q
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 34
Reglas de Inferencia:
1) Leyes de Combinación: A , B |= A
2) L. de Simplificación: A ∧ B |= A A ∧ B |= B
3) Leyes de Adición: A |= A ∨ B B |= A ∨ B
4) Modus Ponens: A , A ⇒ B |= B
5) Modus Tollens: ∼ B , A ⇒ B |= ∼ A
6) Silog. Hipotético: A ⇒ B , B⇒ C |= A⇒ C
Cálculo Proposicional: 9) Implicaciones y Deriv. Lógicas
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 35
Reglas de Inferencia:7) Silog. Disyuntivo: A∨ B ,∼ A |= B
A∨ B ,∼ B |= A8) Ley de Casos: A ⇒ B , ∼ A ⇒ B |= B9) Eliminación de Equivalencias:
A ⇔ B |= A ⇒ B A ⇔ B |= B ⇒ A10) Introducción de la Equivalencia:
A ⇒ B , B ⇒ A |= A ⇔ B
Cálculo Proposicional: 9) Implicaciones y Deriv. Lógicas
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 36
Reglas de Inferencia:11) Ley de Inconsistencia: A , ∼ A |= B
Estas reglas de inferencia se utilizan para realizar derivaciones o demostraciones formales.
Veamos un ejemplo de derivación lógica
Cálculo Proposicional: 9) Implicaciones y Deriv. Lógicas
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 37
“Y ahora llegamos a la gran pregunta del
porqué. El robo no ha sido el objeto del
asesinato, puesto que nada desapareció.
¿ Fue por motivos políticos, o fue una mujer ?
Esta es la pregunta con que me enfrento.
Desde el principio me he inclinado hacia esta
última suposición …
Cálculo Proposicional: 9) Implicaciones y Deriv. Lógicas
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 38
Los asesinos políticos se complacen
demasiado en hacer sólo su trabajo y huir.
Este asesinato, por el contrario ha sido
realizado muy deliberadamente, y quien lo
perpetró ha dejado huellas por toda la
habitación, mostrando que estuvo ahí todo el
tiempo”
Cálculo Proposicional: 9) Implicaciones y Deriv. Lógicas
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 39
Análisis de la derivación lógica:
P1 : Fue un robo
P2 : Algo desapareció
P3 : Fue un asesinato político
P4 : El asesinato lo cometió una mujer
P5 : El asesino huyó inmediatamente
P6 : El asesino dejó huellas por la habitación
Cálculo Proposicional: 9) Implicaciones y Deriv. Lógicas
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 40
Derivación lógica:1) P1 ⇒ P2 (Premisa)2) ∼ P2 (Premisa)3) ∼ P1 (1 y 2 + MT)4) ∼ P1 ⇒ P3 ∨ P4 (Premisa)5) P3 ∨ P4 (3 y 4 + MP)6) P3 ⇒ P5 (Premisa)7) P6 ⇒ ∼ P5 (Premisa)
Cálculo Proposicional: 9) Implicaciones y Deriv. Lógicas
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 41
Derivación lógica:8) P6 (Premisa)9) ∼ P5 (7 y 8 + MP)10) ∼ P3 (6 y 9 + MT)11) Ergo : P4 (5 y 10 + MT)
Cálculo Proposicional: 9) Implicaciones y Deriv. Lógicas
Dr. Gonzalo Hernández USM FI-1 Cálculo Proposicional 42
1) Matemáticas Discreta y Lógica, W. K. Grassmann & J. P. Tremblay, Prentice Hall, 1998.
2) R.P. Grimaldi, Discrete and Combinatorial Mathematics, Addison Wesley,1998.
Cálculo Proposicional: 10) Bibliografía
top related