Departamento de Computação FLIA-PPG-CC Semestre 1 de 2007

Lucia Helena Machado Rino

1

PROPs-LPO

PROPRIEDADES

Cálculo de Predicados

Na lista de propriedades abaixo, relações de equivalência ou implicação lógica demonstram relações entre

interpretações e, portanto, significados, das fbfs envolvidas. Relações de igualdade indicam igualdade entre valores semânticos no domínio do CalcPropos. Fbfs equivalentes terão mesmos valores semânticos.

1. Definições

a. ¬v = f b. ¬f = v (a) e (b) indicam o conjunto fechado da lógica bivalente c. ¬α ∧ α = f (contradição) d. ¬α ∨ α = v (tautologia)

2. Equivalências lógicas a. α � β ⇔ ¬α ∨ β b. α ↔ β ⇔ (α � β) ∧ (β � α) c. ¬¬α ⇔ α

3. EN a. EN1: α ∧ β ⇔ β, para α = tautologia

b. EN2: α ∨ β ⇔ β, para α = contradição

Em outras palavras: c. EN1: v ∧ β ⇔ β d. EN2: f ∨ β ⇔ β

4. Distributiva a. D1: α ∧ (β ∨ γ) ⇔ (α ∧ β) ∨ (α ∧ γ) b. Vale a dual (D2)

5. Associativa a. A1: α ∧ (β ∧ γ) ⇔ (α ∧ β) ∧ γ b. Vale a dual (A2)

6. Idempotência a. I1: α ∨ α ⇔ α b. Vale a dual (I2)

7. Comutativa a. C1: α ∨ β ⇔ β ∨ α

b. Vale a dual (C2) 8. de Morgan

a. M1: ¬(α ∧ β) ⇔ ¬ α ∨ ¬ β b. Vale a dual (M2)

9. Universal a. U1: β ∧ f = f b. Vale a dual (U2)

10. Absorção simples a. Abs1: α ∨ (α ∧ β) ⇔ α b. Vale a dual (Abs2)

11. Absorção elaborada a. p � p ∧ q ⇔ p � q

12. Simplificação (S): α ∧ β ⇒ α 13. Adição (A): α ⇒ α ∨ β

14. Silogismo hipotético (cadeia): (α � β) ∧ (β � γ) ⇒ α � γ

15. Silogismo disjuntivo: (α ∨ β) ∧ ¬α ⇒ β 16. MP (modus ponens): α ∧ (α � β) ⇒ β 17. MT (modus tollens): (α � β) ∧ ¬ β ⇒ ¬α 18. Contrapositiva (DEF): α � β ⇒ ¬β � ¬α 19. Recíproca de α � β (DEF): β � α

20. Contrária de α � β (DEF): ¬α � ¬β 21. Condicional ⇔ contrapositiva

a. α � β ⇔ ¬β � ¬α 22. Contrária ⇔ recíproca

a. ¬α � ¬β ⇔ β � α 23. Exportação: α � (β � γ) ⇒ α ∧ β � γ 24. Importação: α ∧ β � γ ⇒ α � (β � γ) 25. Exportação-Importação-: α � (β � γ) ⇔ α

∧ β � γ 26. Princípio da inconsistência: α ∧ ¬α ⇒ β

Outras propriedades deriváveis 27. se α � β, então

a. α ∧ γ � β ∧ γ (conjunção de ambos os lados)

b. α ∨ γ � β ∨ γ (disjunção de ambos os lados)

28. α � β ∧ γ ⇔ (α � β) ∧ (α � γ)

Departamento de Computação FLIA-PPG-CC Semestre 1 de 2007

Lucia Helena Machado Rino

2

PROPs-LPO

Wang

� R1: Caso 1 � p1, p2,…, pj-1,¬¬¬¬X, pj+1,..., pn ⇒ c1,

c2,..., cm � p1, p2,…, pj-1, pj+1,..., pn ⇒ c1,

c2,..., cm, X

� Caso 2

� p1, p2,…, pn ⇒ c1, c2,..., cj-1,¬¬¬¬X, cj+1,..., cm

� p1, p2,…, pn, X ⇒ c1, c2 ,..., cj-1,cj+1,..., cm

� R2: Caso 1

� p1, p2,…, pj-1, X∧∧∧∧Y, pj+1,..., pn ⇒ c1, c2,..., cm

� p1, p2,…, pj-1, X,Y, pj+1,..., pn ⇒ c1,

c2,..., cm

� Caso 2

� p1, p2,…, pn ⇒ c1, c2,..., cj-1, X∨∨∨∨Y, cj+1,..., cm

� p1, p2,…, pn ⇒ c1, c2 ,..., cj-1, X,Y,

cj+1,..., cm

� R3: p1, X∨∨∨∨Y, p2 ⇒ c1, c2 � p1, X, p2⇒ c1, c2 � p1, Y, p2 ⇒ c1, c2

� R4: p1, p2 ⇒ c1, X∧∧∧∧Y, c2

� p1, p2 ⇒ c1, X, c2 � p1, p2 ⇒ c1, Y, c2

� R5: X � Y ⇔ ¬X ∨ Y

� R6: X ↔ Y ⇔ (X�Y)∧(Y�X)

Princípios

Satisfatibilidade ou consistência lógica α = v para ALGUMA interpretação I ⇒ α é satisfatível ou consistente

Validade (semântica) α é tautologia ⇒ α é válida

Insatisfatibilidade ou inconsistência lógica α = f para TODA interpretação I ⇒ α é insatisfatível ou inconsistente α = contradição ⇒ α é insatisfatível

Inválida α = f para ALGUMA interpretação I⇒ α é inválida (α ∨ β)

Departamento de Computação FLIA-PPG-CC Semestre 1 de 2007

Lucia Helena Machado Rino

3

PROPs-LPO

Calc. de Predicados

As propriedades do Calc. Proposicional valem também para o Calc. de Predicados. Porém, veremos os casos especiais em que as fbfs são quantificadas. Em primeiro lugar, a prioridade dos conectivos deve prever, agora, a inclusão dos quantificadores, que é a seguinte (maior-menor): ~, ∀, ∃, ∧, ∨, �, ↔.

Fecho universal de F: ∀F; Fecho existencial de F: ∃F

Equivalências lógicas

1. ∃x [lingProgram(x) ∧ fornece(softline,x)] não é equivalente a ∃x lingProgram(x) ∧ ∃x fornece(softline,x) � RENOMEAR:

a. ∃x lingProgram(x) ∧ ∃y fornece(softline,y) ⇔ ∃x ∃y [lingProgram(x) ∧ fornece(softline,y)] 2. Paráfrases úteis

a. (P1)Todo elemento de D satisfaz p. – ∀x p(x) b. (P2) Algum elemento de D satisfaz p. - ∃x p(x) c. (P3) Nenhum elemento de D satisfaz p. - ~∃x p(x) d. (P4) Todo elemento de D não satisfaz p. - ∀x [~p(x)]

e. (P5) Algum elemento de D não satisfaz p. - ∃x [~p(x)] f. (P6) Não é para todo elemento de D que p vale. - ~∀x [p(x)] g. (P7) Não existe nenhum elemento de D que não satisfaça p. - ~∃x [~p(x)] h. (P8) Não é para todo elemento de D que p é falsa. - ~∀x [~p(x)]

3. P3 é equivalente a P4

a. ~∃x p(x) ⇔ ∀x [~p(x)] 4. P5 é equivalente a P6

a. ∃x [~p(x)] ⇔ ~∀x [p(x)] b. Não é para todo x que p(x) vale, ou seja, existe pelo menos um x tal que p(x) não vale.

5. P1 é equivalente a P7 a. ∀x p(x) ⇔ ~∃x [~p(x)] b. Se nao existem elementos que não satisfaçam p, então todo elemento satisfaz p.

6. P2 é equivalente a P8 a. ∃x p(x) ⇔ ~∀x [~p(x)] b. Se algum elemento de D satisfaz p(x), não é para todo elemento de D que p é falsa.

Implicações lógicas válidas

1. ∀x p(x) ⇒ ∃x p(x) 2. ∀x [p(x) � c] ⇒ ∃x [p(x) � c]

3. ∀x p(x) ∨ ∀x q(x) ⇒ ∀x [p(x) ∨ q(x)] a. sejam α = ∀x p(x) ∨ ∀x q(x) e β = ∀x [p(x) ∨ q(x)] b. se x que torna α = v não satisfizer p e q ao mesmo tempo, poderíamos renomear as variáveis

em α: ∀x p(x) ∨ ∀y q(y) e poderíamos ter p(x) diferente de q(y) em uma dada interpretação

c. neste caso, β continua sendo satisfatível para a interpretação em x: teríamos um ou exclusivo.

d. Entretanto, vale lembrar que, se p e q são v para quaisquer x no domínio, certamente as disjunções para x coincidente se aplicarão de qualquer modo.

4. Para x coincidente em p e q a. ∃x [p(x) ∧ q(x)] ⇒ ∃x p(x) ∧ ∃x q(x) b. ∀x [p(x) � q(x)] ⇒ ∀x p(x) � ∀x q(x)

fbfs equivalentes

5. Desde que x não ocorra em α a. α ∧ ∀x β ⇔ ∀x (α ∧ β )

Departamento de Computação FLIA-PPG-CC Semestre 1 de 2007

Lucia Helena Machado Rino

4

PROPs-LPO

b. α ∧ ∃x β ⇔ ∃x (α∧ β ) 6. ∀x α ∧ ∀x β ⇔ ∀x (α ∧ β) 7. ∃x α ∨ ∃x β ⇔ ∃x (α ∨ β)

a. Para os casos em que x não satisfaz α e β ao mesmo tempo, a disjunção será exclusiva b. Caso contrário, será inclusiva e α ∨ β será verdadeira exatamente para o mesmo valor de x

(α e β serão v) c. Podemos dizer isso de outra forma

i. ∃x (α(x) ∨ β(x)) ⇔ ∃x α(x) ∨ ∃y β(y) ii. x = y ou x ≠ y

Obtenção de uma forma clausal ���� Cláusula de Horn

1. Passo 1: Eliminar variáveis livres de F a. F quantificada em x: ∃x F b. Não usar mesmo nome de variável

2. Passo 2: Eliminar quantificadores redundantes c. ∀x ou ∃x d. Desde que eles não tenham um escopo envolvendo ocorrências livres de x

3. Passo 3: Renomear variáveis quantificadas mais do que uma vez

e. ∀x (p(x) → ∃x q(x)) � ∀x (p(x) → ∃y q(y)) 4. Passo 4: Remover condicionais e bicondicionais

f. α → β ⇔ (~α ∨ β) g. α ↔ β ⇔ (~α ∨ β) ∧ (~β ∨ α)

5. Passo 5: Diminuir o escopo do símbolo de negação

h. ~(∀x)(p(x)) ⇔ (∃x)(~p(x)) i. ~(∃x)(p(x)) ⇔ (∀x)(~p(x)) j. Lei de De Morgan

a. ~(α ∧ β) ⇔ ~α ∨ ~β b. ~(α ∨ β) ⇔ ~α ∧ ~β

k. ~~α ⇔ α 6. Passo 6: Skolemização

l. α = ∀y (∃x p(x,y)) e x = g(y) � α = ∀y p(g(y),y) m. Se ∃ não estiver no escopo de nenhum ∀ � ∃x p(x) = p(a), a constante

7. Passo 7: Obtenção da forma normal prenex n. Todos os quantificadores universais para a frente da fbf

8. Passo 8: Remoção dos quantificadores universais 9. Passo 9: Colocar a fbf na forma prenex na FNC

o. (α ∧ β) ∨ γ ⇔ (α ∨ γ) ∧ (β ∨ γ)

p. α ∨ (β ∧ γ) ⇔ (α ∨ β) ∧ (α ∨ γ)