tab_propriedades (1)

Prévia do material em texto

Introduc¸a˜o a` Lo´gica – Prof. Reneˆ de Souza Pinto
Tabela 1: Leis da negac¸a˜o, conjunc¸a˜o e disjunc¸a˜o
Leis Nome
α ∧ ¬α ≡ falso Lei da contradic¸a˜o
α ∨ ¬α ≡ verdade Lei do meio excluı´do
α ∧ verdade ≡ α
α ∨ falso ≡ α Leis da identidade
α ∧ falso ≡ falso
α ∨ verdade ≡ verdade Leis da dominac¸a˜o
α ∧ α ≡ α
α ∨ α ≡ α Leis idempotentes
¬(¬α) ≡ α Lei da dupla negac¸a˜o
α ∧ β ≡ β ∧ α
α ∨ β ≡ β ∨ α Leis comutativas
(α ∧ β) ∧ γ ≡ α ∧ (β ∧ γ)
(α ∨ β) ∨ γ ≡ α ∨ (β ∨ γ) Leis associativas
α ∧ (β ∨ γ) ≡ (α ∧ β) ∨ (α ∧ γ)
α ∨ (β ∧ γ) ≡ (α ∨ β) ∧ (α ∨ γ) Leis distributivas
¬(α ∧ β) ≡ ¬α ∨ ¬β
¬(α ∨ β) ≡ ¬α ∧ ¬β Leis De Morgan
Equivaleˆncias da condicional e da bicondicional:
(α→ β) ≡ ¬α ∨ β
(α↔ β) ≡ (α→ β) ∧ (β → α)
(α↔ β) ≡ (α→ β) ∧ (β → α)
≡ (¬α ∨ β) ∧ (¬β ∨ α)
Equivaleˆncias importantes:
α ∨ (α ∧ β) ≡ α absorc¸a˜o
α ∧ (α ∨ β) ≡ α absorc¸a˜o
(α ∧ β) ∨ (¬α ∧ β) ≡ β
(α ∨ β) ∧ (¬α ∨ β) ≡ β
Tabela 2: Regras de infereˆncia
Regra Nome
α, α→ β |= β modus ponens
α→ β,¬β |= ¬α modus tollens
α→ β, β → γ |= α→ γ silogismo hipote´tico (regra da cadeia)
α ∨ β,¬α |= β silogismo disjuntivo
α ∨ β,¬β |= α silogismo disjuntivo (variante)
α ∧ β |= α simplificac¸a˜o
α ∧ β |= β simplificac¸a˜o (variante)
α, β |= α ∧ β conjunc¸a˜o (ou combinac¸a˜o)
α→ β,¬α→ β |= β de casos
α |= α ∨ β adic¸a˜o
β |= α ∨ β adic¸a˜o (variante)
α→ β, γ → δ, α ∨ γ |= β ∨ δ dilema construtivo
α→ β, γ → δ,¬β ∨ ¬δ |= ¬α ∨ ¬γ dilema destrutivo
α→ β |= ¬β → ¬α contraposic¸a˜o
α,¬α |= β da inconsisteˆncia
α→ β, β → α |= α↔ β introduc¸a˜o da equivaleˆncia
α↔ β |= α→ β eliminac¸a˜o da equivaleˆncia
α↔ β |= β → α eliminac¸a˜o da equivaleˆncia (variante)
Tabela 3: Regras do Algoritmo de Wang
Regra torna-se
R1 (. . . ,¬α, · · · ⇒ . . . , β) (· · · ⇒ . . . , β, α)
R1 (α, · · · ⇒ . . . ,¬β, . . . ) (β, α, · · · ⇒ . . . )
R2 (. . . , α ∧ β, · · · ⇒ . . . ) (. . . , α, β, · · · ⇒ . . . )
R2 (· · · ⇒ . . . , α ∨ β, . . . ) (· · · ⇒ . . . , α, β, . . . )
R3 (. . . , α ∨ β, · · · ⇒ . . . ) (. . . , α, · · · ⇒ . . . ) e
(. . . , β, · · · ⇒ . . . )
R4 (· · · ⇒ . . . , α ∧ β, . . . ) (· · · ⇒ . . . , α, . . . ) e
(· · · ⇒ . . . , β, . . . )
R5 (· · · ⇒ . . . , α→ β, . . . ) (· · · ⇒ . . . ,¬α ∨ β, . . . )
R5 (. . . , α→ β, · · · ⇒ . . . ) (. . . ,¬α ∨ β, · · · ⇒ . . . )
R6 (. . . , α↔ β, · · · ⇒ . . . ) (. . . , (α→ β) ∧ (β → α), · · · ⇒ . . . )
R6 (· · · ⇒ . . . , α↔ β, . . . ) (· · · ⇒ . . . , (α→ β) ∧ (β → α), . . . )
R7 (. . . , α, · · · ⇒ . . . , α, . . . ) v, ou seja, e´ um teorema