Logica Proposicional

Tema 2: M´todos de Deducci´n e o para la L´gica Proposicional o

Dpto. Ciencias de la Computaci´n Inteligencia Artificial o Universidad de Sevilla

L´gica y Computabilidad o Curso 2010–11

LC, 2010–11

M´todos de Deducci´n e o

2.1

Contenido
Formas normales Equivalencia Sustituci´n o Formas normales Tableros Fomulas α y β Tableros completos Sistemas deductivos Resoluci´n o Cl´usulasa La regla de resoluci´n o Saturaci´n o Estrategias de resoluci´n o
LC, 2010–11 M´todos de Deducci´n e o 2.2

Equivalencia
Dos f´rmulas F1 , F2 son equivalentes (F1 ≡ F2 ) si, para toda o valoraci´n v , v (F1 ) = v (F2 ). Es decir, F1 ≡ F2 si F1 y F2 tienen o los mismos modelos. F1 ≡ F2 si y s´lo si F1 |= F2 y F2 |= F1 o Ejemplos: Cualesquiera dos f´rmulas insatisfactibles son equivalentes.o Dos tautolog´ cualesquiera son equivalentes. ıas

LC, 2010–11

M´todos de Deducci´n e o

2.3

Equivalencias (I)
Sean A, B ∈ PROP. Se tienen las siguientes equivalencias: Conmutatividad: A ∨ B ≡ B ∨ A Asociatividad: A ∨ (B ∨ C ) ≡ (A ∨ B) ∨ C Distributividad: A ∧ (B ∨ C ) ≡ (A ∧ B) ∨ (A ∧ C ) A ∨ (B ∧ C ) ≡ (A ∨ B) ∧ (A ∨ C ) Doble negaci´n: ¬¬A ≡ A o Leyes de De Morgan: ¬(A ∧ B) ≡ ¬A ∨¬B y ¬(A ∨ B) ≡ ¬A ∧ ¬B y A ∧ (B ∧ C ) ≡ (A ∧ B) ∧ C y A∧B ≡B ∧A

LC, 2010–11

M´todos de Deducci´n e o

2.4

Equivalencias (II)
Idempotencia: A ∨ A ≡ A Absorci´n: A ∨ (A ∧ B) ≡ A o y y A∧A≡A A ∧ (A ∨ B) ≡ A

Leyes de tautolog´ Si A es una tautolog´ entonces ıa: ıa, A∧B ≡B y A∨B ≡A

Leyes de inconsistentes: Si A es insatisfactible, entonces A∧B ≡A y A∨B ≡B

LC, 2010–11

M´todosde Deducci´n e o

2.5

Sustituci´n o
Dadas A, B ∈ PROP si A es una subf´rmula de B y o A ∈ PROP, la sustituci´n de A por A en B es la f´rmula o o que se obtiene al cambiar cada aparici´n de A en B por A . o Usaremos como notaci´n para la sustituci´n: B{A/A }. o o Si A no es una subf´rmula de B, por definici´n B{A/A } es B. o o Ejemplos: Si B es p → q → r ∨ s entonces: B{r ∨ s/p} es p → q → p.B{q ∧ r /q} es p → q → r ∨ s. B{q → r ∨ s/p ∧ r } es p → p ∧ r . B{p → q/p} es p → q → r ∨ s. Si C es la f´rmula (p → q) ∨ (r → p → q), entonces o C {p → q/t} es t ∨ (r → t). C {p → q/t → p → q} es (t → p → q) ∨ (r → (t → p → q))

LC, 2010–11

M´todos de Deducci´n e o

2.6

El Teorema de sustituci´n o
Teorema de Sustituci´n. Sean B ∈ PROP y A, A ∈ PROP tales o que A ≡ A . Entonces B{A/A} ≡ B El teorema de sustituci´n nos permite manipular o “algebraicamente” una f´rmula F para obtener otra f´rmula o o m´s simple y equivalente a F . Este proceso es similar al a empleado en la simplificaci´n de expresiones algebraicas. o Ejemplo: B ∨ (A ∧ (A → B)) ≡ B ∨ (A ∧ (¬A ∨ B)) ≡ B ∨ (A ∧ ¬A) ∨ (A ∧ B) ≡ B ∨ (A ∧ B) ≡ B

LC, 2010–11

M´todos de Deducci´n e o

2.7

Literales
Unaf´rmula F es un literal si es una variable proposicional o o la negaci´n de una variable proposicional. o Dos literales, L1 y L2 , son complementarios (y decimos que uno es el complementario del otro) si L1 es p y L2 es ¬p. Lema 1. Sean L1 , . . . , Ln literales. Son equivalentes:
n

1.
i=1

Li es una tautolog´ ıa.

2. {L1 , . . . , Ln } contiene un par de literales complementarios. Lema 2.Sean L1 , . . . , Ln literales. Son equivalentes:
n

1.
i=1

Li es inconsistente.

2. {L1 , . . . , Ln } contiene un par de literales complementarios.

LC, 2010–11

M´todos de Deducci´n e o

2.8

Formas normales
Una f´rmula est´ en Forma normal conjuntiva (FNC) si es o a una conjunci´n de disyunciones de literales; o  
n mi

F =
i=1


j=1

Li,j 

Una f´rmula est´ enForma normal disjuntiva (FND) si es o a una disyunci´n de conjunciones de literales; o  
n mi

F =
i=1


j=1

Li,j 

LC, 2010–11

M´todos de Deducci´n e o

2.9

Formas normales (II)
Lema: Una f´rmula en forma normal conjuntiva es una tautolog´ o ıa syss cada una de sus disyunciones es una tautolog´ ıa. Una f´rmula en forma normal disjuntiva es insatisfactible syss o cada...