Guia De Referencia

Guia de Referˆ encia (v.

2)

L´ ogica para Ciˆ encias da Computa¸ c˜ ao
Professor: Jomi Fred H¨ ubner Leituras dos s´ımbolos

Defini¸ c˜ oes

¬
∧
∨
→
↔

nega¸c˜ao e (conjun¸c˜ao) ou (disjun¸c˜ao) implica bi-implica¸c˜ao

P, Q, ... φ, ψ, γ, ...
Γ

s´ımbolos proposicionais f´ormulas conjunto de f´ormulas

≡
|=

equivalˆencia implica¸c˜ao l´ogica consequˆencia l´ogica

φ ≡ ψ sss para qualquer interpreta¸c˜ao I, I[φ] = I[ψ]. φ |= ψ sss sempre que I[φ] = v ent˜ao I[ψ] = v.
|= φ sss qualquer interpreta¸c˜ao I, I[φ] = v (tautologia). φ sss qualquer interpreta¸c˜ao I, I[φ] = f (contradi¸ca
˜o).
|=I φ sss existe I tal que I[φ] = v (satisfat´ıvel ).
Γ
φ sss existe uma prova para φ a partir das premissas contidas em Γ.
Γ φ ≡ Γ |= φ se uma f´ormula ´e consequˆencia l´ogica de um conjunto de premissas, ent˜ao tamb´em ´e implica¸c˜ao l´ogica. φ sss existe uma prova para φ a partir de um conjunto vazio de premissas (teorema). φ ≡ |= φ todo teorema ´e uma tautologia.

Interpreta¸ c˜ ao dos conectivos
P

Q

¬P

P ∧Q

P ∨Q

P →Q

P ↔Q

v v f f v f v f f f v v v f f f v v v f v f v v v f f v Principais equivalˆ encias l´ ogicas Regras de inferˆ encia da Dedu¸ c˜ ao Natural φ ψ
I∧
φ ∧ ψ φ I∨ φ ∨ ψ

φ ∧ ψ
E∧
φ φ ∨ ψ

φ→γ γ φ ∧ ψ
E∧
ψ ψ→γ E∨

φ ∨ ψ ¬φ E∨ ψ (resolu¸c˜ao) φ→ψ ψ→φ
I↔
φ ↔ ψ
[φ]
..
.
ψ φ → ψ

φ ↔ ψ
E↔
φ → ψ

φ ↔ ψ
E↔
ψ → φ

φ

I→

φ→ψ
E→
ψ
(modus ponens) φ → ψ ¬ψ
E→
¬φ
(modus tolens)

φ
I¬¬
¬¬φ
[φ]
..
.
f alse
¬φ

I¬

φ ¬φ
If alse f alse

¬¬φ
E¬¬
φ
[¬φ]
..
.

E¬ f alse φ (refuta¸c˜ao)

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.

φ↔ψ φ∧ψ φ∨ψ
(φ ↔ ψ) ↔ γ
(φ ∧ ψ) ∧ γ
(φ ∨ ψ) ∨ γ φ ∧ (ψ ∨ γ) φ ∨ (ψ ∧ γ)
¬(φ ∨ ψ)
¬(φ ∧ ψ) φ→ψ φ → (ψ → γ) φ→ψ φ↔ψ
¬(φ ↔ ψ) φ (φ ∧ ψ) ∨ ¬ψ
(φ ∨ ψ) ∧ ¬ψ φ ∨ (φ ∧ ψ) φ ∧ (φ ∨ ψ) φ ∨ ¬φ φ ∧ ¬φ φ ∨ true φ ∨ f alse φ ∧ true φ ∧ f alse

ψ↔φ ψ∧φ ψ∨φ φ ↔ (ψ ↔ γ) φ ∧ (ψ ∧ γ) φ ∨ (ψ ∨ γ)
(φ ∧ ψ) ∨ (φ ∧ γ)
(φ ∨ ψ) ∧ (φ ∨ γ)
¬φ ∧ ¬ψ
¬φ ∨ ¬ψ
¬φ ∨ ψ
(φ ∧ ψ) → γ
¬ψ → ¬φ
(φ ∧ ψ) ∨ (¬φ ∧ ¬ψ) φ ↔ ¬ψ
¬¬φ
φ