Exercícios - Lógica Para Computação

Prévia do material em texto

1. Prove que para todo n ≥1, tem-se que 
 
1 + 2 + ... + n = n(n + 1) 
 2 
Fazendo a prova por indução: 
 
Fazendo o caso base: para n = 1, 
 
 1 = 1 . (1+1) ⟹ 1 = 2 ⇒ 1 = 1 
 2 2 
 
Passo Indutivo: devemos provar que: 
 
1 + 2 + ... + n + (n+1) = (n+1).(n + 1) 
 2 
1 + 2 + ... + n + (n+1) = (n+1)2 + (n + 1) 
 2 
1 + 2 + ... + n + (n+1) = n2 + 2n + 1 + n + 1 = n2 + 3n + 2 ( I ) 
 2 2 
Por hipótese temos: 
1 + 2 + ... + n = n(n + 1) 
 2 
 
Somando n+1 em ambos os lados: 
 
1 + 2 + ... + n + (n+1) = n(n + 1) + (n+1) 
 2 
 1 + 2 + ... + n + (n+1) = n2 + n + (n+1) 
 2 
 1 + 2 + ... + n + (n+1) = n2 + n + 2n + 2 = n2 + 3n +2 ( II ) 
 2 2 
 
Como I e II são iguais, conseguimos provar. 
 
2. Prove que para todo n ≥ 1, tem-se que 
 
 12 + 22 + ... + n2 = n(n + 1)(2n + 1) 
 6 
Fazendo a prova por indução: 
 
Fazendo o caso base: para n = 1, 
 
 12 = (1.(1+1).(2.1+1)) ⇒ 1 = (1.2.3) = 1 
 6 6 
 
Passo Indutivo: devemos provar que: 
 
 12 + 22 + ... + n2 + (n+1)2 = (n+1).((n+1) + 1).(2(n+1) + 1) 
 6 
 12 + 22 + ... + n2 + (n+1)2 = ((n+1)2 + (n+1)).((2n+2) + 1)) 
 6 
 12 + 22 + ... + n2 + (n+1)2 = (n2 + 3n + 2).(2n+3) 
 6 
 12 + 22 + ... + n2 + (n+1)2 = (2n3 + 9n2 + 13n+6) ( I ) 
 6 
 
 
Por hipótese temos: 
 12 + 22 + ... + n2 = n.(n + 1).(2n + 1) , somando-se (n+1)2, em ambos os lados, temos: 
 6 
 12 + 22 + ... + n2 + (n+1)2= n.(n + 1).(2n + 1) + (n+1)2 
 6 
 12 + 22 + ... + n2 + (n+1)2= (n2 + n).(2n + 1) + 6.(n+1)2 
 6 
 12 + 22 + ... + n2 + (n+1)2= (2n3 + 9n2 + 13n+6) ( II ) 
 6 
 
Como I e II são iguais, conseguimos provar. 
 
 
3. Prove que para todo n ≥ 4, tem-se que 
 
 2n < n! 
 
Fazendo a prova por indução: 
 
Fazendo o caso base: para n = 4, 
 
 24 < 4! ⇒ 16 < 24 
 
Passo Indutivo: devemos provar que: 
 
 2(n+1) < (n+1)! 
 1 < (n+1)! ( I ) 
 2(n+1) 
Por hipótese temos: 
 
 2n < n! , multiplicando ambos os lados por 2(n+1), temos: 
 2(n+1). 2n < 2(n+1) . n! 
 (n+1) < 2(n+1) . n! 
 2n+1 
 n+1 < (n+1)! ( II ) 
 2 2n+1 
 
Como o lado direito de I é igual ao lado direito de II, temos que provar que ((n+1)/2) é maior que 1, mas 
como n ≥ 4, por definição, estão temos que ((n+1)/2) é sempre maior que 1 e assim provamos que 2n < 
n!. 
 
4. Determine o tamanho das fórmulas abaixo e o conjunto de subfórmulas. 
 
O tamanho ou complexidade das fórmulas é dado por: 
 
 |�| = 1 para � atômico 
 |(¬�)| = |�| + 1 
 |�⎕�| = |�|+ |�| + 1 
 
O conjunto de subfórmulas de � é definido por: 
 
 Subf (�) = { � }, para � atômico 
 Subf ((¬�)) = Subf (�) ∪ {(¬�)} 
 Subf ((�⎕�)) = Subf (�) ∪ Subf (�) ∪ {(�⎕�)} 
 
(a) (A → (B → A)) 
 
O tamanho da fórmula (A → (B → A)) fica: 
 
|(A → (B → A))| = | A | + | (B → A) | + 1 
 = | A | + | B | + | A | + 1 +1 
 = 1 + 1 + 1 + 1 +1 = 5 
 
O conjunto de subfómulas de (A → (B → A)) fica: 
 
Subf ((A → (B → A))) = Subf (A) ∪ Subf ((B → A)) ∪ {(A → (B → A))} 
 ={(A)} ∪ Subf (B) ∪ Subf (A) ∪ {(B → A)} ∪ {(A → (B → A))} 
 ={(A)} ∪ {(B)} ∪ {(A)} ∪ {(B → A)} ∪ {(A → (B → A))} 
 ={A, B, (B → A), (A → (B → A))} 
 
(b) (A ∨ (B ∧ C)) 
 
O tamanho da fórmula (A ∨ (B ∧ C)) fica: 
 
|(A ∨ (B ∧ C))| = | A | + | (B ∧ C) | + 1 
 = | A | + | B | + | C | + 1 +1 
 = 1 + 1 + 1 + 1 +1 = 5 
 
O conjunto de subfómulas de (A ∨ (B ∧ C)) fica: 
 
Subf ((A ∨ (B ∧ C))) = Subf (A) ∪ Subf ((B ∧ C)) ∪ {(A ∨ (B ∧ C))} 
 = {(A)} ∪ Subf (B) ∪ Subf (C) ∪ { (B ∧ C)} ∪ {(A ∨ (B ∧ C))} 
 = {(A)} ∪ {(B)} ∪ {(C)} ∪ {( B ∧ C)} ∪ {(A ∨ (B ∧ C))} 
 = {A, B, C, (B ∧ C), (A ∨ (B ∧ C))} 
 
(c) ((A ∨ B) ∧ (A ∨ C)) 
 
O tamanho da fórmula ((A ∨ B) ∧ (A ∨ C)) fica: 
 
|((A ∨ B) ∧ (A ∨ C))| = | (A ∨ B) | + | (A ∨ C) | + 1 
 = | A | + | B | + 1 + | A | + | C | + 1 +1 
 = 1 + 1 + 1 + 1 +1+1+1 = 7 
 
O conjunto de subfómulas de ((A ∨ B) ∧ (A ∨ C)) fica: 
 
Subf (((A ∨ B) ∧ (A ∨ C))) = 
 = Subf ((A ∨ B)) ∪ Subf ((A ∨ C)) ∪ {((A ∨ B) ∧ (A ∨ C))} 
 = Subf(A) ∪ Subf (B) ∪ Subf (A) ∪ Subf (C) ∪ {(A ∨ B)}∪{(A ∨ C)} ∪ {((A ∨ B) ∧ (A ∨ C))} 
 ={(A)} ∪ {(B)} ∪ {(A)} ∪ {(C)} ∪ {(A ∨ B)}∪{(A ∨ C)} ∪ {((A ∨ B) ∧ (A ∨ C))} 
 ={A, B, C, (A ∨ B), (A ∨ C), ((A ∨ B) ∧ (A ∨ C))} 
 
 
 
 
(d) (¬ ((¬A) ∧ (¬B))) 
O tamanho da fórmula (¬ ((¬A) ∧ (¬B))) fica: 
 
|(¬ ((¬A) ∧ (¬B)))| = | ((¬A) ∧ (¬B)) || + 1 
 = | (¬A) | + | (¬B) | + 1 +1 
 = | A | + | B | + 1 + 1 + 1 + 1 
 = 1 + 1 + 1 + 1 + 1 + 1 = 6 
O conjunto de subfómulas de (¬ ((¬A) ∧ (¬B))) fica: 
 
Subf ((¬ ((¬A) ∧ (¬B)))) = 
= Subf (((¬A) ∧ (¬B))) ∪ {(¬ ((¬A) ∧ (¬B)))} 
= Subf ((¬A)) ∪ Subf ((¬B)) ∪ {((¬A) ∧ (¬B))} ∪ {(¬ ((¬A) ∧ (¬B)))} 
 = Subf (A) ∪ Subf (B) ∪ {(¬A)} ∪ {(¬B)} ∪ {((¬A) ∧ (¬B))} ∪ {(¬ ((¬A) ∧ (¬B)))} 
 = {(A)} ∪ {(B)} ∪ {(¬A)} ∪ {(¬B)} ∪ {((¬A) ∧ (¬B))} ∪ {(¬ ((¬A) ∧ (¬B)))} 
 = {A, B, (¬A), (¬B),�(¬A) ∧ (¬B)�, (¬ ((¬A) ∧ (¬B)))} 
 
5. Prove que os itens da questão anterior são fórmulas. 
 
6. Prove que ((→ não é uma fórmula de LLP . 
 
7. Defina uma função c¬ : LLP → ℕ que calcula o número de ocorrências do conectivo unário ¬ em 
uma fórmula. Por exemplo, a fórmula (¬(A → (¬ B))) tem duas ocorrências da proposição ¬, ou 
seja, c¬ (( ¬ (A → (¬B)))) = 2. 
 
Seja c¬ uma função que contabiliza o número de ocorrências do conectivo unário ¬ em uma fórmula. 
Assim temos: 
 
 c¬ |�| = 0, para � atômico 
 c¬ |(¬�)| = |�| + 1 
 c¬|�⎕�| = |�|+ |�| + 0 = |�|+ |�|, onde ⎕ ∈ {∧, ∨, ⟶, ⟷} 
 
Aplicando na fórmula dada, temos: 
 
 | (¬(A → (¬ B))) | = |(A → (¬ B)) | + 1 
 = |A| + | (¬ B) | + 1 + 0 
 = |B| + 1 + 0 + 1 
 = 1 + 0 + 1 = 2 
 
8. Defina uma função c⎕ : LLP → ℕ que calcula o número de ocorrências de conectivos binários (∧, 
∨, ⟶, ⟷) em uma fórmula. Por exemplo, a fórmula (C ∨ (A ⟶ (¬A))) tem duas ocorrências de 
conectivos binários, ou seja, c⎕ ((C ∨ (A ⟶ (¬A)))) = 2. 
 
Seja c⎕ uma função que contabiliza o número de ocorrências do conectivos binários (∧, ∨, ⟶, ⟷) em 
uma fórmula. Assim temos: 
 
 c⎕ |�| = 0, para � atômico 
 c⎕ |(¬�)| = |�| + 0 = |�| 
 c⎕ �⎕�| = |�|+ |�| + 1, onde ⎕ ∈ {∧, ∨, ⟶, ⟷} 
 
 
Aplicando na fórmula dada, temos: 
 
 | (C ∨ (A ⟶ (¬A))) | = |C| + |(A → (¬ A)) | + 1 
 = |A| + |¬ A| + 1 + 0 + 1 
 = 0 + 0 + 1 + 1 
 = 2 
 
9. Defina uma função c : LLP → ℕ que calcula o número de ocorrências de conectivos (¬, ∧, ∨, ⟶, 
⟷) em uma fórmula. Por exemplo, a fórmula (C ∨ (A ⟶ (¬A))) tem três ocorrências de conectivos, 
ou seja, c((C ∨ (A ⟶ (¬A)))) = 3. 
 
Seja c uma função que contabiliza o número de ocorrências do conectivos (¬, ∧, ∨, ⟶, ⟷) em uma 
fórmula. Assim temos: 
 
 c |�| = 0, para � atômico 
 c |(¬�)| = |�| + 1 
 c �⎕�| = |�|+ |�| + 1, onde ⎕ ∈ {∧, ∨, ⟶, ⟷} 
 
 
Aplicando na fórmula dada, temos: 
 
 | (C ∨ (A ⟶ (¬A))) | = |C| + |(A → (¬ A)) | + 1 
 = |A| + |¬ A| + 1 + 0 + 1 
 = 0 + 1 + 1 + 1 
 = 3 
 
10. Defina uma função s : LLP → ℕ que calcula o número de ocorrências de proposições atômicas 
em uma fórmula. Por exemplo, a fórmula (A → (B → A)) tem três ocorrências, ou seja, s((A → (B → 
A)) , A) = 3. 
 
Seja s uma função que calcula o número de ocorrências de proposições atômicas em uma fórmula. Assim 
temos: 
 
 s |�| = 1, para � atômico 
 s |(¬�)| = |�| + 0 = |�| 
 s �⎕�| = |�|+ |�| + 0 = |�|+ |�|, onde ⎕ ∈ {∧, ∨, ⟶, ⟷} 
 
 
Aplicando na fórmula dada, temos: 
 
 | (A → (B → A))| = |A| + |(B→A)| + 0 
 = 1 + |B| + |A| + 0 
 = 1 + 1 + 1 
 = 3 
 
 
 
 
 
 
 
 
11. Defina uma função sp : LLP x P → ℕ que calcula o número de ocorrências de um átomo em uma 
fórmula. Por exemplo, a fórmula (A → (B → A)) tem duas ocorrências do átomo A, ou seja, s((A → 
(B → A)) , A) = 2. 
 
Seja sp uma função que calcula o número de ocorrências de um átomo |�| em uma fórmula. Assim temos: 
 
 s |�| = 1, para � atômico 
 s |�| = 0, para � atômico 
 s |(¬�)| = |�| + 0 = |�| 
 s �⎕�| = |�|+ |�| + 0 = |�|+ |�|, onde ⎕ ∈ {∧, ∨, ⟶, ⟷} 
 
 
Aplicando na fórmula dada, para contar o número de átomos A, temos: 
 
 | (A → (B → A))| = |A| + |(B→A)| + 0 
 = 1 + |B| + |A| + 0 
 = 1 + 0 + 1 
 = 2 
 
12. Defina uma função ||s : LLP → ℕ que calcula o tamanho do conjunto de subfórmulas de uma 
dada fórmula. Por exemplo, a fórmula (A → (B → A)) tem quatro subfórmulas, ou seja, |((A → (B → 
A))|
 s = 4. 
 
Seja ||s uma função que calcula o tamanho de subfórmulas de uma dada fórmula. Assim temos: 
 
 ||s |�| = 1, para � atômico 
 ||s | |�| + |�| | = 1, para � atômico 
 ||s |(¬�)| = |�| + 1 
 ||s |�⎕�| = |�|+ |�| + 1, onde ⎕ ∈ {∧, ∨, ⟶, ⟷} 
 
Aplicando na fórmula dada, temos: 
 
 | (A → (B → A))| = |A| + |(B→A)| + 1 
 = |A| + |B| + |A| + 1 + 1 
 = |A| + |A| + 1 + 1 +1 
 = 1 + 1 + 1 + 1 
 = 4 
 
13. Demonstre que, para todas as fórmulas, o número de ocorrências de um dado átomo é sempre 
menor ou igual ao número de átomos da fórmula. 
 
Caso base (� atômico) 
Seja q um átomo qualquer. O número de ocorrência de q em � é menor ou igual ao número de átomos em 
�, pois no pior caso p = �. 
 
Por hipótese indutiva: Seja � uma fórmula com | � | = K, e q um átomo qualquer. Temos que o número 
de ocorrência de q em um � é menor ou igual a K. 
 
Passo Indutivo: Seja P um átomo qualquer. 
 
1: ¬� , o resultado segue, pois | ¬� | = | � | 
2: (�⎕�) 
 Caso I: n (P) = | � | 
 n (P) + 1 ≤ | � | + 1 
 
 Caso II: n (P) < | � | + 1 
 
14. Sejam � uma fórmula, c⎕ o número de ocorrências de conectivos binários (∧, ∨, ⟶, ⟷) em �, e 
s o número de ocorrências de átomos em �. Por exemplo, se � é (A ⟶ (¬A)) então c⎕(�)= 1 e s(�) 
= 2. Mostre usando indução que s(�) = c⎕(�) + 1 para toda fórmula. 
 
Seja c⎕ uma função que contabiliza o número de ocorrências do conectivos binários (∧, ∨, ⟶, ⟷) em 
uma fórmula. Assim temos: 
 
 c⎕ |�| = 0, para � atômico 
 c⎕ |(¬�)| = |�| + 0 = |�| 
 c⎕ |�⎕�| = |�|+ |�| + 1, onde ⎕ ∈ {∧, ∨, ⟶, ⟷} 
 
Seja sp uma função que calcula o número de ocorrências de um átomo |�| em uma fórmula. Assim temos: 
 
 s |�| = 1, para � atômico 
 s |�| = 0, para � atômico 
 s |(¬�)| = |�| + 0 = |�| 
 s �⎕�| = |�|+ |�| + 0 = |�|+ |�|, onde ⎕ ∈ {∧, ∨, ⟶, ⟷} 
 
Queremos demonstrar que s(�) = c⎕(�) + 1, assim temos: 
 
Para o caso base: � atômico 
 
 s(�) = c⎕(�) + 1 
 1 = 0 + 1 
 1 = 1 
Para ¬� temos: 
 s(¬�) = c⎕(¬�) + 1 
 s(�) + 0 = c⎕(�) + 0 +1 
 s(�) = c⎕(�) + 1 
 
Para o caso geral |�⎕�|, onde ⎕ ∈ {∧, ∨, ⟶, ⟷}, temos: 
 
 s (�⎕�) = c⎕(�⎕�) + 1 
 s(�)+ s(�) + 0 = c⎕(�) + c⎕ (�) + 1 
 s(�)+ s(�) = c⎕(�) + c⎕ (�) + 1 
 
Por hipótese temos: 
 s(�) = c⎕(�) + 1s(�) = c⎕ (�) + 1 
 
Efetuando-se a soma das sentenças, temos: 
 
 s(�)+ s(�) = c⎕(�) + 1 + c⎕ (�) + 1 
 s(�)+ s(�) = c⎕(�) + c⎕ (�) + 2 
 
 
 
 
 
 
 
 
15. Sejam � uma fórmula, c⎕ o número de ocorrências de conectivos binários (∧, ∨, ⟶, ⟷) em �, e 
s o número de ocorrências de átomos em �. Por exemplo, se � é (A ⟶ (¬A)) então c⎕(�)= 1 e s(�) 
= 2. Mostre usando indução que s(�) ≤ c⎕(�) + 2 para toda fórmula. 
 
Seja c⎕ uma função que contabiliza o número de ocorrências do conectivos binários (∧, ∨, ⟶, ⟷) em 
uma fórmula. Assim temos: 
 
 c⎕ |�| = 0, para � atômico 
 c⎕ |(¬�)| = |�| + 0 = |�| 
 c⎕ |�⎕�| = |�|+ |�| + 1, onde ⎕ ∈ {∧, ∨, ⟶, ⟷} 
 
Seja sp uma função que calcula o número de ocorrências de um átomo |�| em uma fórmula. Assim temos: 
 
 s |�| = 1, para � atômico 
 s |�| = 0, para � atômico 
 s |(¬�)| = |�| + 0 = |�| 
 s �⎕�| = |�|+ |�| + 0 = |�|+ |�|, onde ⎕ ∈ {∧, ∨, ⟶, ⟷} 
 
Queremos demonstrar que s(�) = c⎕(�) + 1, assim temos: 
 
Para o caso base: � atômico 
 
 s(�) = c⎕(�) + 1 
 1 = 0 + 1 
 1 = 1 
Para ¬� temos: 
 s(¬�) = c⎕(¬�) + 1 
 s(�) + 0 = c⎕(�) + 0 +1 
 s(�) = c⎕(�) + 1 
 
 
 
16. Sejam � uma fórmula, c⎕ o número de ocorrências de conectivos binários (∧, ∨, ⟶, ⟷) em �, e 
s o número de ocorrências de átomos em �. Por exemplo, se � é (A ⟶ (¬A)) então c⎕(�)= 1 e s(�) 
= 2. Mostre usando indução que s(�) - 1= c⎕(�) para toda fórmula. 
 
Seja c⎕ uma função que contabiliza o número de ocorrências do conectivos binários (∧, ∨, ⟶, ⟷) em 
uma fórmula. Assim temos: 
 
 c⎕ |�| = 0, para � atômico 
 c⎕ |(¬�)| = |�| + 0 = |�| 
 c⎕ |�⎕�| = |�|+ |�| + 1, onde ⎕ ∈ {∧, ∨, ⟶, ⟷} 
 
Seja sp uma função que calcula o número de ocorrências de um átomo |�| em uma fórmula. Assim temos: 
 
 s |�| = 1, para � atômico 
 s |�| = 0, para � atômico 
 s |(¬�)| = |�| + 0 = |�| 
 s �⎕�| = |�|+ |�| + 0 = |�|+ |�|, onde ⎕ ∈ {∧, ∨, ⟶, ⟷} 
 
Queremos demonstrar que s(�) = c⎕(�) + 1, assim temos: 
 
Para o caso base: � atômico 
 
 s(�) = c⎕(�) + 1 
 1 = 0 + 1 
 1 = 1 
Para ¬� temos: 
 s(¬�) = c⎕(¬�) + 1 
 s(�) + 0 = c⎕(�) + 0 +1 
 s(�) = c⎕(�) + 1 
 
 
 
 
17. Seja � uma fórmula que não contenha o símbolo ¬. Mostre que o tamanho de � é ímpar. 
 
18. Prove que uma fórmula com n conectivos tem tamanho de no máximo 2n + 1. 
 
Temos que provar que n conectivos tem tamanho ≤ 2n + 1. 
Caso Base ( � atômico) 
Se � é um átomo, então o número de conectivos é zero e o tamanho de | � | = 1, então logo: n ≤ 2n + 1. 
 0 ≤ 1. 
Por hipótese de indução: Seja � uma fórmula com k < n conectivos, então k ≤ 2k + 1. 
Passo indutivo: ¬� 
 Seja p o número de conectivos em �. Pela hipótese de indução em �: p ≤ 2p + 1. 
 Em ¬� temos: p ≤ 2p + 1 
 p +1 ≤ 2p + 2 
 p + 1 ≤ 2(p + 1) 
 �⎕�, ⎕ ∈ {∧, ∨, ⟶, ⟷} 
Sejam m e n o número de conectivos em � e �, pela hipótese de indução, temos: 
 m ≤ 2m + 1 (em � ) 
 p ≤ 2p + 1 (em � ) 
 m + p ≤ 2m + 2p + 2 
 m + p ≤ 2 (m + p + 1) 
 m + p +1 ≤ 2(m + p + 1) +1 
 n ≤ 2n + 1 
19. Prove os itens abaixo sem utilizar o método da tabela da verdade. 
(a) ⊨ (A → B) ↔ (¬A ∨ B) 
 
Suponha v uma função de valoração qualquer, tal que (A → B) ↔ (¬A ∨ B) é uma tautologia, assim 
devemos demonstrar que ∇ ((A → B) ↔ (¬A ∨ B)) = 1, para isso, basta mostrar que ∇ (A → B) = ∇ ((¬A 
∨ B)), então temos: 
 
∇ (A → B) = 1 ⇒ ∇ (A) = 0 ou ∇ (B) = 1 
 ⇒ ∇(¬A) = 1 ou ∇ (B) = 1 
 ⇒ ∇ (¬A ∨ B ) = 1 
 
∇ (A → B) = 0 ⇒ ∇ (A) = 1 e ∇ (B) = 0 
 ⇒ ∇(¬A) = 0 e ∇ (B) = 0 
 ⇒ ∇(¬A ∨ B ) = 0 
 
 
(b) ⊨ ( A ∨ B ) ↔ (¬A → B) 
 
Para provar que a equação ( A ∨ B ) ↔ (¬A → B) é uma tautologia, temos que provar que ( A ∨ B) = 
( ¬A → B), então temos: 
 
(¬A → B) = 1 ⇒ ¬A = 0 ou B = 1 
 ⇒ A = 1 ou B = 1 
 ⇒ ( A ∨ B ) = 1 
 
(¬A → B) = 0 ⇒ ¬A = 1 e B = 0 
 ⇒ A = 0 e B = 0 
 ⇒ ( A ∨ B ) = 0 
 
(c) ⊨ ¬¬A ↔ A 
 
Para provar que a equação ¬¬A ↔ A é uma tautologia, temos que provar que ¬¬A = A, então temos: 
 
¬¬A = 1 ⇒ ¬A = 0 ⇒ A = 1 
 
¬¬A = 0 ⇒ ¬A = 1 ⇒ A = 0 
 
 
(d) ⊨ A → (B → A) 
 
Para provar que a equação A → (B → A) é uma tautologia, temos que provar que (A → (B → A)) = 1, 
então temos que: 
 
 ⇒ A = 0 ou B → A = 1 
 ⇒ A = 0 ou B = 0 ou A = 1 
 ⇒ A = 0 ou B = 0 ou A = 1 
 
Assim podemos ver que o valor de B é irrelevante e que, como A = 0 ou A = 1, a equação é sempre 
verdadeira. 
(e) ⊨ (A ∨ (B ∧ C)) ↔ ((A ∨ B) ∧ (A ∨ C)) 
Para provar que a equação (A ∨ (B ∧ C)) ↔ ((A ∨ B) ∧ (A ∨ C)) é uma tautologia, temos que provar que 
(A ∨ (B ∧ C)) = ((A ∨ B) ∧ (A ∨ C)), então temos: 
 
(A ∨ (B ∧ C)) = 1 ⇒ A = 1 ou (B = 1 e C = 1) 
 ⇒ ((A ∨ B) ∧ (A ∨ C)) = 1 
 
(A ∨ (B ∧ C)) = 0 ⇒ A = 0 e B = 0 e C = 0 
 ⇒ ((A ∨ B) ∧ (A ∨ C)) = 0 
 
(f) ⊨ (A ∧ ( B ∨ C )) ↔ ((A ∧ B) ∨ (A ∧ C)) 
 
Para provar que a equação (A ∧ ( B ∨ C )) ↔ ((A ∧ B) ∨ (A ∧ C)) é uma tautologia, temos que provar que 
(A ∧ ( B ∨ C )) = ((A ∧ B) ∨ (A ∧ C)) então temos: 
 
(A ∧ ( B ∨ C )) = 1 ⇒ A = 1 e (B = 1 ou C = 1) 
 ⇒ ((A ∧ B) ∨ (A ∧ C)) = 1 
 
(A ∧ ( B ∨ C )) = 0 ⇒ A = 0 ou (B = 0 e C = 0) 
 ⇒ ((A ∧ B) ∨ (A ∧ C)) = 0 
 
 
(g) { A ∨ B, A → C, B → C} ⊨ C 
 
Temos que provar que C = 1 e por definição temos que: 
 I - A ∨ B = 1 II - A → C = 1 III - B → C 
 I - A = 1 ou B = 1 II - A = 0 ou C=1 III - B = 0 ou C = 1 
Em I temos que, se A = 1, então em II obrigatoriamente C=1 e se, em I, B=1, então em III 
obrigatoriamente C = 1, assim, para tornar I, II e III verdadeiras, então obrigatoriamente C = 1. 
 
(h) {A ∨ B, ¬B} ⊨ A 
Temos que provar que A = 1 e por definição temos que: 
 I - A ∨ B = 1 II - ¬B = 1 
 I - A = 1 ou B = 1 II - B = 0 
Como em II temos que B=0, então em I temos obrigatoriamente que A=1. 
 
 
 
 
20. Prove utilizando o método da tabela da verdade a questão anterior. 
(a) ⊨ (A → B) ↔ (¬A ∨ B) 
 
A B ¬A A → B ¬A ∨ B (A → B) ↔ (¬A ∨ B)0 0 1 1 1 1 
0 1 1 1 1 1 
1 0 0 0 0 1 
1 1 0 1 1 1 
 
(b) ⊨ ( A ∨ B ) ↔ (¬A → B) 
 
A B ¬A A ∨ B ¬A → B ( A ∨ B ) ↔ (¬A → B) 
0 0 1 0 0 1 
0 1 1 1 1 1 
1 0 0 1 1 1 
1 1 0 1 1 1 
 
(c) ⊨ ¬¬A ↔ A 
 
A ¬A ¬¬A ¬¬A ↔ A 
0 1 0 1 
0 1 0 1 
1 0 1 1 
1 0 1 1 
 
(d) ⊨ A → (B → A) 
 
A B B → A A → (B → A) 
0 0 1 1 
0 1 0 1 
1 0 1 1 
1 1 1 1 
 
 (e) ⊨ (A ∨ (B ∧ C)) ↔ ((A ∨ B) ∧ (A ∨ C)) 
 
(f) ⊨ (A ∧ ( B ∨ C )) ↔ ((A ∧ B) ∨ (A ∧ C)) 
 
A B C B ∨ C A ∧ (B ∨ C) A ∧ B A ∧ C (A ∧ B) ∨ (A ∧ C) (A ∧ ( B ∨ C )) ↔ ((A ∧ B) ∨ (A ∧ C)) 
0 0 0 0 0 0 0 0 1 
A B C B ∧ C A ∨ (B ∧ C) A ∨ B A ∨ C (A ∨ B) ∧ (A ∨ C) (A ∨ (B ∧ C)) ↔ ((A ∨ B) ∧ (A ∨ C)) 
0 0 0 0 0 0 0 0 1 
0 0 1 0 0 0 1 0 1 
0 1 0 0 0 1 0 0 1 
0 1 1 1 1 1 1 1 1 
1 0 0 0 1 1 1 1 1 
1 0 1 0 1 1 1 1 1 
1 1 0 0 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 
0 0 1 1 0 0 0 0 1 
0 1 0 1 0 0 0 0 1 
0 1 1 1 0 0 0 0 1 
1 0 0 0 0 0 0 0 1 
1 0 1 1 1 0 1 1 1 
1 1 0 1 1 1 0 1 1 
1 1 1 1 1 1 1 1 1 
 
 
(g) { A ∨ B, A → C, B → C} ⊨ C 
 
A B C A ∨ B A → C B → C) 
0 0 0 0 1 1 
0 0 1 0 1 1 
0 1 0 1 1 0 
0 1 1 1 1 1 
1 0 0 1 0 1 
1 0 1 1 1 1 
1 1 0 1 0 0 
1 1 1 1 1 1 
 
(h) {A ∨ B, ¬B} ⊨ A 
A B ¬B A ∨ B 
0 0 1 0 
0 1 0 1 
1 0 1 1 
1 1 0 1