Lógica proposicional e demonstrações: exercícios com soluções passo a passo
Exercícios grátis de Lógica proposicional e demonstrações com diagramas, dicas e soluções completas resolvidas. Valores novos a cada vez, em três níveis: tabelas-verdade, equivalências e métodos de demonstração, quantificadores e argumentos.
Exercício gratuitoFácil
Complete a tabela-verdade (1 = verdadeiro, 0 = falso). Em quantas linhas N é (p → r) ↔ (r ∨ q) verdadeira?
(p → r) ↔ (r ∨ q)
Resposta exata: um número inteiro, sem arredondar.
Aprenda Lógica proposicional e demonstrações do zero
1Proposições e conectivos
Uma proposição é uma afirmação que é verdadeira ou falsa, como “7 é primo”. Escrevemos uma proposição com uma letra, p ou q, e seu valor lógico como 1 (verdadeiro) ou 0 (falso).
Os conectivos constroem fórmulas maiores a partir de fórmulas menores:
¬p (não p) inverte o valor.
p ∧ q (e) vale 1 somente quando ambos valem 1.
p ∨ q (ou) vale 0 somente quando ambos valem 0. É o ou inclusivo: ambos podem ser verdadeiros.
p → q (se p então q) vale 0 somente quando p = 1 e q = 0.
p ↔ q (se e somente se) vale 1 quando p e q têm o mesmo valor.
A implicação surpreende muitos estudantes: quando p é falsa, p → q é verdadeira seja qual for q. Uma promessa “se chover, levo um guarda-chuva” só é quebrada num dia de chuva sem guarda-chuva.
Autoavaliação p = 0 e q = 1. Qual é o valor de p → q?
0
1
Depende do contexto
Indefinido
Resposta: 1. Uma implicação só é falsa quando a condição vale e a conclusão falha (p = 1, q = 0). Com p = 0 ela é verdadeira, seja qual for q.
2Tabelas-verdade
Uma tabela-verdade lista todas as combinações de valores lógicos das variáveis. Com n variáveis diferentes há 2ⁿ linhas: 4 para duas variáveis, 8 para três, 16 para quatro. Uma variável que aparece duas vezes conta apenas uma vez.
Trabalhe de dentro para fora. Dê a cada subfórmula a sua própria coluna, de modo que cada nova coluna precise aplicar apenas um conectivo a colunas que você já tem.
Liste as variáveis e escreva todas as 2ⁿ combinações, começando com todos os 1.
Acrescente uma coluna para cada subfórmula, começando pela mais interna.
Preencha cada coluna usando a regra do seu conectivo principal.
Leia a resposta na última coluna: conte os 1s ou encontre a linha pedida.
Autoavaliação Quantas linhas tem a tabela-verdade de (p ∧ q) → (r ∨ p)?
16
4
6
8
Resposta: 8. A fórmula tem três variáveis diferentes, p, q e r, então 2³ = 8 linhas. A variável p aparece duas vezes, mas é uma só; 16 seria 2⁴ para quatro ocorrências.
3Um exemplo resolvido
Acompanhe cada passo. Tente prever o próximo antes de abri-lo.
Exemplo resolvido
Em quantas linhas da sua tabela-verdade (p → q) ∧ ¬q é verdadeira?
1
Variáveis e linhas
Duas variáveis, p e q, então 4 linhas: (1, 1), (1, 0), (0, 1), (0, 0).
2
Coluna p → q
Ela vale 0 somente na linha p = 1, q = 0:
p → q: 1, 0, 1, 1
3
Coluna ¬q
¬q: 0, 1, 0, 1
4
A conjunção
As duas colunas devem valer 1. Isso acontece somente na última linha, p = 0 e q = 0.
(p → q) ∧ ¬q: 0, 0, 0, 1
Resposta
A fórmula é verdadeira em 1 linha, a linha p = 0, q = 0. Por isso p → q e ¬q juntas dão ¬p (modus tollens).
4Equivalências e métodos de demonstração
Duas fórmulas são equivalentes (≡) quando suas colunas na tabela-verdade são idênticas. Uma tautologia vale 1 em todas as linhas, uma contradição vale 0 em todas as linhas, e uma contingência não é nenhuma das duas.
As leis que você mais usa:
¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q
p → q ≡ ¬p ∨ q ≡ ¬q → ¬p ¬(p → q) ≡ p ∧ ¬q
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Essas leis são a base dos métodos de demonstração. Uma demonstração por contraposição de p → q demonstra ¬q → ¬p, que é equivalente. Uma demonstração por absurdo supõe p ∧ ¬q, a única maneira de a implicação falhar, e deriva algo impossível.
Cuidado: a recíproca q → p e a inversa ¬p → ¬q não são equivalentes a p → q.
Autoavaliação Qual fórmula é equivalente a ¬(p ∧ q)?
p ∨ q
¬p ∧ q
¬p ∧ ¬q
¬p ∨ ¬q
Resposta: ¬p ∨ ¬q. Por De Morgan, o ∧ vira ∨ e as duas partes são negadas. ¬p ∧ ¬q é a negação de p ∨ q, uma afirmação diferente: ela é falsa quando exatamente uma entre p e q é verdadeira, caso em que ¬(p ∧ q) é verdadeira.
5Quantificadores e argumentos válidos
Com variáveis sobre um domínio, ∀x P(x) diz “P vale para todo x” e ∃x P(x) diz “P vale para pelo menos um x”. Uma negação troca o quantificador:
¬∀x P(x) ≡ ∃x ¬P(x) ¬∃x P(x) ≡ ∀x ¬P(x)
Mova a negação para dentro um passo de cada vez; lá dentro, use as leis proposicionais. Por exemplo, ¬∀x (P(x) → Q(x)) ≡ ∃x (P(x) ∧ ¬Q(x)): “nem todo P é um Q” significa “algum P não é um Q”.
Um argumento é válido quando a conclusão vale 1 em toda linha em que todas as premissas valem 1. As formas válidas clássicas são o modus ponens (p → q, p, logo q), o modus tollens (p → q, ¬q, logo ¬p) e o silogismo hipotético (p → q, q → r, logo p → r).
Uma linha com todas as premissas 1 e a conclusão 0 é um contraexemplo. Afirmar o consequente (p → q, q, logo p) é inválido: a linha p = 0, q = 1 é um contraexemplo.
Autoavaliação Qual é a negação de “todo estudante foi aprovado”, ∀x P(x)?
¬P(x) para um estudante x fixo
∀x ¬P(x): nenhum estudante foi aprovado
∃x P(x): algum estudante foi aprovado
∃x ¬P(x): algum estudante não foi aprovado
Resposta: ∃x ¬P(x): algum estudante não foi aprovado. Um estudante reprovado basta para tornar falso “todo estudante foi aprovado”. “Nenhum estudante foi aprovado” é muito mais forte do que a negação.
6Erros comuns
Tratar p → q como falsa quando p é falsa. Ela só é falsa quando p = 1 e q = 0.
Contar uma variável repetida duas vezes ao calcular o número de linhas.
Confundir a contrapositiva ¬q → ¬p com a recíproca q → p ou com a inversa ¬p → ¬q.
Negar ∀x P(x) como ∀x ¬P(x): o quantificador deve mudar para ∃.
Escrever ¬(p ∧ q) como ¬p ∧ ¬q: De Morgan também troca o conectivo.
Autoavaliação Qual afirmação é a contrapositiva de “se n² é par, então n é par”?
Se n é par, então n² é par
Se n é ímpar, então n² é ímpar
Se n² é ímpar, então n é ímpar
n² é par e n é ímpar
Resposta: Se n é ímpar, então n² é ímpar. Troque as duas partes e negue ambas: não (n par) → não (n² par). “Se n é par, então n² é par” é a recíproca; a última opção é o que uma demonstração por absurdo supõe.
7Como são as questões de prova
Fácil: tabelas-verdade. Você encontra o número de linhas, conta as linhas em que uma fórmula é verdadeira ou clica na única linha que torna uma fórmula verdadeira ou falsa.
Médio: equivalências e métodos de demonstração. Você decide se uma fórmula é uma tautologia, uma contradição ou uma contingência, escolhe a fórmula equivalente ou a afirmação a demonstrar numa demonstração por contraposição ou por absurdo.
Difícil: quantificadores e argumentos. Você nega afirmações quantificadas, escolhe a conclusão que decorre das premissas, clica na linha do contraexemplo de um argumento inválido ou conta as linhas verdadeiras de uma tabela de quatro variáveis.
Exatamente uma linha da tabela-verdade torna ¬(p ∨ q) → q falsa. Clique nessa linha.
¬(p ∨ q) → q
1p = 1, q = 1
2p = 1, q = 0
3p = 0, q = 1
4p = 0, q = 0
Mostrar dicas
a → b vale 0 somente quando a = 1 e b = 0. ¬a inverte o valor. a ∨ b vale 0 somente quando ambos valem 0.
Descubra primeiro o conectivo principal: como devem ser seus dois lados para que a fórmula inteira seja 0?
Dê a cada parte a sua própria coluna: p ∨ q; ¬(p ∨ q); ¬(p ∨ q) → q.
Mostrar a resposta e a explicação
Tabelas-verdade: uma fórmula com n variáveis diferentes tem 2ⁿ linhas, uma para cada combinação de valores lógicos (1 = verdadeiro, 0 = falso). Trabalhe de dentro para fora e dê a cada subfórmula a sua própria coluna. ¬a inverte o valor; a ∧ b vale 1 somente quando ambos valem 1; a ∨ b vale 0 somente quando ambos valem 0; a → b vale 0 somente quando a = 1 e b = 0; a ↔ b vale 1 quando os dois lados são iguais.
Qual fórmula é logicamente equivalente a (b ∧ c) → a? Clique nela.
(b ∧ c) → a
1(b → a) ∧ (c → a)
2b → (c → a)
3b ∧ (c → a)
4(b → c) → a
Mostrar dicas
Fórmulas equivalentes concordam em todas as linhas da tabela-verdade. Uma linha em que elas diferem descarta uma alternativa.
Experimente uma linha que torne (b ∧ c) → a igual a 0 e veja quais alternativas também valem 0 nela.
Exportação: (a ∧ b) → c ≡ a → (b → c). Ambas valem 0 somente quando a = 1, b = 1 e c = 0.
Mostrar a resposta e a explicação
Equivalência lógica: duas fórmulas são equivalentes (≡) quando têm o mesmo valor em todas as linhas da tabela-verdade. Uma tautologia vale 1 em todas as linhas, uma contradição vale 0 em todas as linhas, e uma contingência não é nenhuma das duas. Leis úteis: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b e ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (contrapositiva); ¬(a → b) ≡ a ∧ ¬b; e as leis distributivas, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
A lei
Exportação: (a ∧ b) → c ≡ a → (b → c). Ambas valem 0 somente quando a = 1, b = 1 e c = 0.
(b ∧ c) → a ≡ b → (c → a)
Confira com a tabela-verdade
a = 1, b = 1, c = 1: 1 | 1 1 1 1
a = 1, b = 1, c = 0: 1 | 1 1 1 1
a = 1, b = 0, c = 1: 1 | 1 1 0 1
a = 1, b = 0, c = 0: 1 | 1 1 0 1
a = 0, b = 1, c = 1: 0 | 0 0 0 0
a = 0, b = 1, c = 0: 1 | 0 1 1 1
a = 0, b = 0, c = 1: 1 | 0 1 0 0
a = 0, b = 0, c = 0: 1 | 1 1 0 0
Resposta
b → (c → a)
As colunas depois da barra são as alternativas na ordem mostrada.
Exemplo 3Difícil
São dadas as premissas (q ∧ p) → r; q; ¬r. Qual conclusão decorre delas? Clique nela.
(q ∧ p) → rq¬r
1p
2p ∧ ¬r
3¬p
4r
Mostrar dicas
Uma conclusão decorre quando vale 1 em toda linha em que todas as premissas valem 1.
Encontre as linhas que tornam todas as premissas 1 e depois teste cada alternativa nessas linhas.
Esta é uma regra padrão: modus tollens com uma conjunção.
Mostrar a resposta e a explicação
Quantificadores e argumentos: ¬∀x P(x) ≡ ∃x ¬P(x) e ¬∃x P(x) ≡ ∀x ¬P(x). Mova a negação para dentro, troque todo quantificador que ela atravessa e negue a fórmula interna com as leis proposicionais, como ¬(a → b) ≡ a ∧ ¬b. Um argumento é válido quando a conclusão vale 1 em toda linha em que todas as premissas valem 1. Uma única linha com premissas verdadeiras e conclusão falsa é um contraexemplo e mostra que o argumento é inválido.
Linhas com todas as premissas verdadeiras
p = 0, q = 1, r = 0: p = 0, p ∧ ¬r = 0, ¬p = 1, r = 0
Conclusão
¬p (modus tollens com uma conjunção)
Resposta
¬p
Perguntas e respostas
Lógica proposicional e demonstrações: o que é?
Uma proposição é uma afirmação que é verdadeira ou falsa, como “7 é primo”. Escrevemos uma proposição com uma letra, p ou q, e seu valor lógico como 1 (verdadeiro) ou 0 (falso).
Os conectivos constroem fórmulas maiores a partir de fórmulas menores:
Lógica proposicional e demonstrações: como resolver os exercícios passo a passo?
Conte as variáveis diferentes: a tabela-verdade tem 2ⁿ linhas, começando com todas elas iguais a 1.
Dê a cada subfórmula a sua própria coluna e preencha as colunas de dentro para fora.
Aplique a regra de cada conectivo: → só é 0 para 1 → 0, ↔ vale 1 quando os dois lados coincidem.
Para equivalências, compare as colunas finais linha a linha; para um argumento, olhe apenas as linhas em que todas as premissas valem 1.
Para negar uma afirmação quantificada, mova ¬ para dentro, troque ∀ e ∃ e negue a fórmula interna.
Lógica proposicional e demonstrações: quais são os erros mais comuns?
Tratar p → q como falsa quando p é falsa.
Contar uma variável repetida duas vezes ao calcular o número de linhas.
Confundir a contrapositiva ¬q → ¬p com a recíproca q → p.
Negar ∀x P(x) como ∀x ¬P(x) em vez de ∃x ¬P(x).
Aplicar De Morgan sem trocar ∧ e ∨.
Lógica proposicional e demonstrações: o que se pratica?
Fácil: tabelas-verdade
Média: equivalências e métodos de demonstração
Difícil: quantificadores e argumentos
Cada exercício tem valores novos, então você aprende o método em vez de decorar uma resposta. Travou? Abra primeiro uma dica pequena, e a explicação completa só quando precisar.
Como a prática funciona
Cada exercício tem valores novos, então você aprende o método em vez de decorar uma resposta.
Travou? Abra primeiro uma dica pequena, e a explicação completa só quando precisar.
Seu progresso, seus erros e seus exercícios salvos ficam guardados, para você revisar antes da prova.