Introdução a Lógica
46 pág.

Introdução a Lógica

Disciplina:Elementos de Lógica13 materiais100 seguidores
Pré-visualização7 páginas
α ∧ β ⇒ α ∨ β
(e) α ∧ β ⇒ α↔ β
(f) α↔ β ⇒ α → β
(g) α↔ β ⇒ β → α
(h) α → β ⇒ (α ∧ γ)→ β
(i) α → β⇔ (α ∨ β)→ β
(j) (α → β) ∧ (α → ¬β)⇔ ¬α
(k) (α → β) ∧ (γ → β)⇔ (α ∨ γ)→ β
(l) (α → β) ∨ (α → γ)⇔ α → (β ∨ γ)

(m) (α → β) ∨ (γ → δ)⇔ (α ∧ γ)→ (β ∨ δ)
3. Responda, usando as regras.

(a) α ∧ ¬α⇒ β
(b) (α ∨ β)⇒ ¬α
(c) α ∧ β ⇒ α ∨ β
(d) ¬α → α⇔ α
(e) α → (α ∧ β)⇔ α → β
(f) (α → β)→ β⇔ α ∨ β
(g) (α → γ) ∨ (β → γ)⇔ (α ∧ β)→ γ
(h) (α → β) ∧ (α → γ)⇔ α → (β ∧ γ)

4. Simplifique as fo´rmulas.

(a) ¬(¬α → ¬β)
(b) ¬(α ∨ ¬β)
(c) ¬(¬α ∧ β)
(d) ¬(¬α ∨ ¬β)
(e) (α ∨ β) ∧ ¬α)
(f) (α → β) ∧ (¬α → β)

6

1.2 Ca´lculo Proposicional

(g) ¬(α ∨ β) ∨ (¬α ∧ β)
(h) (α ∧ (α ∨ β))↔ α
(i) α ∧ ((α ∨ β)↔ α)
(j) (α ∨ (α ∧ β))↔ α
(k) α ∨ ((α ∧ β)↔ α)
(l) α ∧ (α → β) ∧ (α → ¬β)

1.2.2 Formas Normais

Dentre os conectivos lo´gicos ¬,∧,∨,→ e ↔, treˆs exprimem-se em termos de apenas dois,{¬,∧}, {¬,∨} e {¬,→}, denominados conjuntos completos de conectivos.
Considere o conjunto {¬,∧}, temos:

α ∨ β ⇔ ¬(¬α ∧ ¬β) (1.1)
α → β ⇔ ¬(α ∧ ¬β) (1.2)
α↔ β ⇔ ¬(α ∧ ¬β) ∧ ¬(β ∧ ¬α) (1.3)
α ∨ β ⇔ ¬(¬α ∧ ¬β) ∧ ¬(α ∧ β) (1.4)

Para o conjunto {¬,∨}, temos:
α ∧ β ⇔ ¬(¬α ∨ ¬β) (1.5)
α → β ⇔ ¬α ∨ β (1.6)
α↔ β ⇔ ¬(¬(¬α ∨ β) ∨ ¬(¬β ∨ α)) (1.7)
α ∨ β ⇔ ¬(¬α ∨ β) ∨ ¬(α ∨ ¬β) (1.8)

E, para {¬,→}, temos:
α ∧ β ⇔ ¬(α → ¬β) (1.9)
α ∨ β ⇔ ¬α → β (1.10)
α↔ β ⇔ ¬((α → β)→ ¬(β → α)) (1.11)
α ∨ β ⇔ (α → β)→ ¬(β → α) (1.12)

Diz-se que uma wff esta´ na forma normal (FN) quando contem somente os conectivos ¬,∧
e ∨. Toda wff e´ logicamente equivalente a um wff na forma normal.
Exemplo 1.2.2 A wff ¬((α → β) → ¬(β → α)) na˜o esta´ na forma normal. Observe que, e´
poss´ıvel obter pelo menos treˆs formas normais equivalentes a` wff dada.

wff ∶ ¬((α → β)→ ¬(β → α)) ⇔ (fdc)
FN ∶ ¬(¬(¬α ∨ β) ∨ ¬(¬β ∨ α)) ⇔ (dm)
FN ∶ ¬¬(¬α ∨ β) ∧ ¬¬(¬β ∨ α) ⇔ (dn)
FN ∶ (¬α ∨ β) ∧ (¬β ∨ α)

7

1.2 Ca´lculo Proposicional

Forma Normal Conjuntiva (FNC)

Uma wff esta´ na FNC quando:

1. Esta´ na forma normal.

2. Na˜o existem dupla negac¸o˜es.

Uma negac¸a˜o na˜o tem alcance sobre uma conjunc¸a˜o nem sobre uma disjunc¸a˜o.

3. Uma disjunc¸a˜o na˜o tem alcance sobre uma conjunc¸a˜o.

Dada uma wfff qualquer e´ sempre poss´ıvel obter uma wff logicamente equivalente na FNC,
bastando seguir os seguintes passos.

Fnc1. Eliminar os conectivos → e ↔ usando as regras de equivaleˆncia Forma Disjuntiva do
Condicional e Forma Conjuntiva do Bicondicional.

Fnc2. Aplicar as regras de Dupla Negac¸a˜o e de De Morgan.

Fnc3. Usar a regra Distributiva (α ∧ β) ∨ γ⇔ (α ∨ γ) ∧ (β ∨ γ).
Forma Normal Disjuntiva (FND)

Analogamente, uma wff esta´ na FND quando: Uma wff esta´ na FNC quando:

1. Esta´ na forma normal.

2. Na˜o existem dupla negac¸o˜es.

Uma negac¸a˜o na˜o tem alcance sobre uma conjunc¸a˜o nem sobre uma disjunc¸a˜o.

3. Uma conjunc¸a˜o na˜o tem alcance sobre uma disjunc¸a˜o.

Obtendo a FND:

Fnd1. Eliminar os conectivos → e ↔ usando as regras de equivaleˆncia Forma Disjuntiva do
Condicional e Forma Conjuntiva do Bicondicional.

Fnd2. Aplicar as regras de Dupla Negac¸a˜o e de De Morgan.

Fnd3. Usar a regra Distributiva (α ∨ β) ∧ γ⇔ (α ∧ γ) ∨ (β ∧ γ).

8

1.2 Ca´lculo Proposicional

Exerc´ıcios 1.2.3

1. Reescreva as fo´rmulas do item 4 do Exerc´ıcio 1.2.1 usando:

(a) {¬,∧}
(b) {¬,∨}
(c) {¬,→}

2. Determine a Forma Normal Conjuntiva das fo´rmulas.

(a) α ∧ β ∧ γ
(b) α ∨ β ∨ γ
(c) α → (β → γ)
(d) ¬(¬α → ¬β)
(e) ¬(α ∨ ¬β)
(f) ¬(¬α ∧ β)
(g) ¬(¬α ∨ ¬β)
(h) (α ∨ β) ∧ ¬α)
(i) (α → β) ∧ (¬α → β)
(j) ¬(α ∨ β) ∨ (¬α ∧ β)
(k) α ∧ (α ∨ β)↔ α
(l) α ∨ (α ∧ β)↔ α

(m) α ∧ (α → β) ∧ (α → ¬β)
(n) α ∨ β
(o) α → β
(p) α↔ β
(q) (α ∨ β)↔ α
(r) (¬α ∧ β) ∨ β
(s) ¬(¬α ∨ ¬β)
(t) (α → β) ∧ ¬α
(u) (α → β) ∨ ¬α
(v) α ∨ (β ∨ γ)
(w) α↔ ¬α
(x) (α → β)→ β → (α ∨ β)
(y) (α → γ) ∧ (β ∨ γ) ∧ α ∧ β ∧ γ
(z) (¬(¬α → ¬γ)) ∨ (β → ¬γ)

3. Determine a Forma Normal Disjuntiva para as fo´rmulas do item anterior.

9

1.2 Ca´lculo Proposicional

1.2.3 Demonstrac¸o˜es: Direta, Condicional e Reduc¸a˜o ao Absurdo

Agora, estamos interessados em como chegar a concluso˜es a partir de um conjunto de wff
dadas. Considere um conjunto de wff Γ = {γ1, . . . , γn}, n ⩾ 1, e uma wff β. Denomina-se
argumento toda afirmac¸a˜o de que o conjunto Γ tem como consequeˆncia ou acarreta a wff
β, denotamos por Γ ⊢ β. Diz-se tambe´m que β se deduz, se infere ou decorre de Γ. Assim, Γ
e´ denominado conjunto de hipo´teses ou premissas do argumento e a wff β e´ denominada
tese ou conclusa˜o do argumento.

Um argumento Γ ⊢ β e´ va´lido quando (γ1 ∧ ⋅ ⋅ ⋅ ∧ γn) ⇒ β, isto e´, quando a wff(γ1 ∧ ⋅ ⋅ ⋅ ∧ γn)→ β e´ uma tautologia. Um argumento na˜o va´lido e´ um sofisma ou fala´cia.
Assim, a validade de um argumento pode ser feita mediante o uso de tabelas verdade,

como foi visto anteriormente. Uma abordagem mais eficiente para verificar a validade de um
argumento consiste em deduzir ou demonstrar a conclusa˜o a partir do conjunto de premissas.
Uma deduc¸a˜o ou demonstrac¸a˜o direta da wff β a partir do conjunto de wff Γ e´ uma
sequeˆncia finita de wff (α1, . . . , αm) tal que:

1. Para todo i = 1, . . . ,m,
(a) αi ∈ Γ ou
(b) αi foi obtida por aplicac¸a˜o de alguma das regras de infereˆncia ou equivaleˆncia em

certas fo´rmulas αj, 1 ⩽ j < i, anteriores.
2. αm = β.

Exemplo 1.2.4 Uma demonstrac¸a˜o do argumento {α → ¬β, β} ⊢ ¬α e´:
α1 α → ¬β
α2 β
α3 ¬¬β → ¬α CP1
α4 β → ¬α DN3
α5 ¬α MP2,4

Outro me´todo para demonstrar a validade de argumentos do tipo Γ ⊢ β → γ e´ a de-
monstrac¸a˜o condicional, onde o enunciado e´ modificado para depois apresentarmos uma
demonstrac¸a˜o direta. Observe que, Γ ⊢ β → γ so´ e´ va´lido quando Γ → (β → γ)⇔ V, que,
pelo Fortalecimento da Hipo´tese, e´ equivalente a (Γ ∧ β) → γ ⇔ V. Assim, o argumento
dado Γ ⊢ β → γ e´ va´lido quando Γ ∪ {β} ⊢ γ e´ va´lido.
Exemplo 1.2.5 Considere o argumento {α ∨ (β → γ),¬γ} ⊢ β → α. Usando demonstrac¸a˜o
condicional, rescrevemos o enunciado para {α ∨ (β → γ),¬γ, β} ⊢ α e apresentamos a de-
monstrac¸a˜o para o enunciado fortalecido.

10

1.2 Ca´lculo Proposicional

α1 α ∨ (β → γ)
α2 ¬γ
α3 β
α4 α ∨ (¬β ∨ γ) FDC1
α5 (α ∨ ¬β) ∨ γ AssocC4
α6 α ∨ ¬β SD2,5
α7 ¬¬β DN3
α8 α SD6,7

Finalmente, temos o me´todo da demostrac¸a˜o por reduc¸a˜o ao absurdo ou por con-
tradic¸a˜o, que tambe´m faz uma modificac¸a˜o no enunciado dado antes de apresentar uma
demonstrac¸a˜o direta. O argumento Γ ⊢ β so´ e´ va´lido quando Γ→ β⇔V, que, pela Reduc¸a˜o
ao Absurdo, e´ equivalente a (Γ ∧ ¬β) → F ⇔ V. Assim, o argumento dado Γ ⊢ β e´ va´lido
quando Γ ∪ {¬β} ⊢ F e´ va´lido.
Exemplo 1.2.6 Considere o argumento {α → ¬β, γ → β} ⊢ ¬(α∧γ). Usando demonstrac¸a˜o
por reduc¸a˜o ao absurdo, rescrevemos o enunciado para {α → ¬β, γ → β,¬¬(α ∧ γ)} ⊢ F e
apresentamos a demonstrac¸a˜o para o enunciado modificado.

α1 α → ¬β
α2 γ → β
α3 ¬¬(α ∧ γ)
α4 α ∧ γ DN3
α5 α Simpl4
α6 ¬β MP1,5
α7 γ Simpl4
α8 β MP2,7
α9 ¬β ∧ β Conj6,8
α10 F PNC9

Exerc´ıcios 1.2.7

1. Verifique a validade dos argumentos apresentando demonstrac¸o˜es.

(a) {γ → (α ∨ β), γ, ¬α} ⊢ β
(b) {α → ¬β, ¬¬β, ¬α → γ} ⊢ γ
(c) {α ∧ β, α → γ, β → δ} ⊢ γ ∧ δ
(d) {α → β, β → ¬γ, α} ⊢ ¬γ
(e) {α → β, ¬β, ¬α → γ} ⊢ γ
(f) {α → β, α → γ, α} ⊢ β ∧ γ
(g) {α → β, ¬β, α ∨ γ} ⊢ γ
(h) {α ∨ ¬β, γ → ¬α, γ} ⊢ ¬β
(i) {¬α ∨ ¬β, ¬¬β, γ → α} ⊢ ¬γ

11

1.2 Ca´lculo Proposicional

(j) {α → β, α ∧ γ} ⊢ β
(k) {α ∧ β, (α ∨ γ)→ δ} ⊢ α ∧ δ
(l) {α → (β → γ), α → β, α} ⊢ γ

(m) {α → β, (α ∧ β)→ γ, ¬(α ∧ γ)} ⊢ ¬α
(n) {(α ∨ β)→ γ, (γ ∨ β)→ (α → (δ↔ ϕ)), α ∧ δ} ⊢ δ↔ ϕ
(o) {α → ¬β, ¬α → (γ → ¬β), (¬δ ∨ ¬γ)→ ¬¬β, ¬δ} ⊢ ¬γ
(p) {(α ∧ β)→ γ, γ → δ, ϕ→ ¬ψ, ϕ, ¬δ ∨ ψ} ⊢ ¬(α ∧ β)
(q) {α → β, β → γ, δ → ϕ, α ∨ δ} ⊢ γ ∨ ϕ
(r) {α → β, ¬γ → (δ → ϕ), γ ∨ (α ∨ δ), ¬γ} ⊢ β ∨ ϕ
(s) {α → β, (α → γ)→ (δ ∨ β), (α ∧ β)→ γ, ¬δ} ⊢ β
(t) {α → β, α ∨ (¬¬γ ∧ ¬¬β), δ → ¬γ, ¬(α ∧ β)} ⊢ ¬δ ∨ ¬β
(u) {α → γ, β → δ, ¬γ, (α ∨ β) ∧ (γ ∨ δ)} ⊢ δ
(v) {α → β, β → γ, γ → δ, ¬δ, α ∨ ϕ} ⊢ ϕ
(w) {(α → β) ∧ (γ → δ), ϕ→ ψ, ψ → σ, ¬β ∨ ¬σ} ⊢ ¬α ∨ ¬ϕ
(x) {α → β, β → γ, δ → ¬γ, α} ⊢ ¬δ
(y) {α → β, β → γ, α ∨ δ, δ → ϕ, ¬ϕ} ⊢ γ
(z) {α → β, ¬α → γ, ¬γ ∨ δ, ϕ ∧ ¬β} ⊢ δ

2. Use demonstrac¸a˜o condicional para demonstrar a validade dos argumentos.

(a) {α → (β ∨ γ),¬γ} ⊢ α → β
(b)