Exercícios de Lógica Proposicional

Estes exercícios foram copiados e/ou inspirados nas seguintes obras:

Lógica e Aritmética de Augusto Franco de Oliveira.
forallχ de P. D. Magnus.
Logic in Computer Science de Michael Huth e Mark Ryan.
Artificial Intelligence, A Modern Approach de Stuart Russell e Peter Norvig.
Mathematics for Computer Science: Course Textbook de Eric Lehman, F Thomson Leighton e Albert R Meyer.

Sistemas Formais

Exercício 1 O que se passa aqui?

$1 = 1 = (- 1) (- 1) = - 1 - 1 = (- 1)^{2} = i^{2} = - 1$

Identifique rigorosamente e explique os erros nesta prova errada.
- Em que condições é válida a igualdade $n ab = n a n b$ ?
Prove (corretamente) que se $1 = - 1$ então $2 = 1$ .

Exercício 2 O sistema dedutivo $MIU$ (que aparece no livro Gödel, Escher and Bach) é um sistema formal com apenas três símbolos ( $M$ , $I$ , $U$ ) um axioma( $MI$ ) e quatro regras:

$R_{1} : x I ⊢ x IU$ .
$R_{2} : M x ⊢ M xx$ .
$R_{3} : x III y ⊢ x U y$ .
$R_{4} : x UU y ⊢ x y$ .

onde $x$ e $y$ representam expressões arbitrárias.

Uma prova é uma sequência finitas de expressões $x_{1}, x_{2}, \dots, x_{n}$ em que cada $x_{i}$ é ou um axioma ou resulta de alguma expressão anterior $x_{j}, j < i$ por aplicação de uma das regras.

A última expressão de uma prova chama-se teorema.

Mostre que:

A expressão $MUII$ é um teorema.
O número de $I$ de um teorema nunca é múltiplo de três.
A expressão $M I^{2 n}$ , para qualquer $n \geq 0$ , é um teorema.
Se $x III$ é um teorema, então $x$ é um teorema.
Se $n = 2^{m} - 3 k, k \geq 0$ então $M I^{n}$ é teorema.
A expressão $M I^{n}$ é um teorema para qualquer $n$ que não seja múltiplo de três.
Uma expressão $x$ é teorema de $MIU$ se e só se é da forma $M y$ em que $y$ é uma expressão formada só por $I$ e $U$ e onde o número de $I$ não é múltiplo de três.

Formalização de Linguagem Natural

Exercício 3 Quais das seguintes frases são proposições no sentido lógico?

Portugal é mais pequeno que Espanha.
O Porto fica ao sul de Coimbra.
O Porto fica ao sul de Coimbra?
O Porto e Coimbra.
O Porto ou Coimbra, mas Lisboa não.
Chove no Porto ou em Coimbra, mas em Lisboa não.
O número atómico do hélio é 2.
O número atómico do hélio é $π$ .
Aquece o café!
Brrr! Que frio está este café!
Café frio é repugnante.
Demora o tempo que precisares.
Esta é a última alínea.
Esta é a última alínea.

Exercício 4 Use a simbolização dada para traduzir as frases abaixo para a lógica proposicional.

$a$ : O Sr. Aas foi assassinado.
$b$ : O culpado é o mordomo.
$c$ : O culpado é o cozinheiro.
$d$ : A duquesa mente.
$e$ : O Sr. Hoek foi assassinado.
$f$ : A arma do crime é uma frigideira.

Ou o Sr. Aas ou o Sr. Hoek foi assassinado.
Se o Sr. Aas foi assassinado, o culpado é o cozinheiro.
Se o Sr. Hoek foi assassinado, o culpado não é o cozinheiro.
Ou o culpado é o mordomo ou a duquesa mente.
O culpado é o cozinheiro só se a duquesa mente.
Se a arma do crime for uma frigideira, então o crime deve ter sido cometido pelo cozinheiro.
Se a arma do crime não for uma frigideira então o culpado é o cozinheiro ou o mordomo.
O Sr. Aas foi assassinado se e só se o Sr. Hoek não foi assassinado.
A duquesa está a mentir, a não ser que o o Sr. Hoek tenha sido assassinado.
Se o Sr. Aas foi assassinado, a arma do crime foi uma frigideira.
Como o culpado é o cozinheiro, o mordomo está inocente.
Claro que a duquesa está a mentir!

Fórmulas Proposicionais

Exercício 5 Tendo em conta as convenções de escrita, desenhe árvores das seguintes proposições.

$\neg p \land q \to r$
$(p \to q) \land \neg (r \lor p \to q)$
$(p \to q) \to (r \to s \lor t)$
$p \lor (\neg q \to p \land r)$
$p \lor q \to \neg p \land r$
$p \lor p \to \neg q$
$p \lor q \land r$

Dedução Natural

Exercício 6 Faça as seguintes deduções:

$p ⊢ p$
$p \land p ⊢ p$
$p ⊢ p \land p$
$p, p \to q, q \to r ⊢ r$
$p, p \to (q \to r), p \to q ⊢ r$
$p \to q, q \to r ⊢ p \to r$
$p \to q ⊢ (q \to r) \to (p \to r)$
$⊢ (p \to q) \to (q \to r) \to (p \to r)$
$⊢ p \land q \to p$
$⊢ p \land q \to q$
$⊢ p \to (q \to p \land q)$
$⊢ \neg\neg p \to p$
$⊢ p \to (p \to q) \to q$
$p \to q, \neg q ⊢ \neg p$
$p ⊢ \neg (\neg p \land \neg q)$
$p \to q ⊢ \neg q \to \neg p$
$p ⊢ \neg\neg p$
$\neg q \to \neg p ⊢ p \to q$
$p \lor (q \land r) ⊣⊢ (p \lor q) \land (p \lor r)$
$p \to q ⊣⊢ \neg (p \land \neg q)$
$p \land q ⊣⊢ q \land p$
$p \lor q ⊣⊢ q \lor p$
$p \land (q \land r) ⊣⊢ (p \land q) \land r$
$p \lor (q \lor r) ⊣⊢ (p \lor q) \lor r$
$p \land (q \lor r) ⊣⊢ (p \land q) \lor (p \land r)$
$(p \land q) \lor (p \land \neg q) ⊢ p$
$\neg p ⊢ p \to q$
$p ⊢ q \to p$

Consequência Semântica

Exercício 7 Três indivíduos, $A$ , $B$ e $C$ , suspeitos de um crime, prestam os seguintes depoimentos:

$A$ : $B$ é culpado, mas $C$ é inocente.
$B$ : Se $A$ é culpado, então $C$ é culpado.
$C$ : Eu estou inocente, mas um dos outros dois é culpado.

Os três depoimentos são compatíveis (isto é, podem ser todos simultaneamente válidos)?
Algum dos depoimentos é consequência dos outros dois?
Construa provas correspondentes à alínea anterior.
Supondo que os três suspeitos são inocentes, quem mentiu?
Supondo que todos dizem a verdade, quem é inocente e quem é culpado?
Supondo que os inocentes dizem a verdade e os culpados mentem, quem é inocente e quem é culpado?

Exercício 8 Para cada uma das proposições seguintes, indique se é uma tautologia, contradição, contingente ou compatível. Justifique a sua resposta com uma tabela de verdade completa ou parcial, conforme necessário.

$p \to p$ $\neg p \land p$
$p \to \neg p$
$p \lor \neg p$
$(p \leftrightarrow q) \leftrightarrow \neg (p \leftrightarrow \neg q)$
$(p \land q) \lor (q \land p)$
$(p \to q) \lor (q \to p)$
$\neg (p \to (q \to p))$
$(p \land q) \to (q \lor p)$
$p \leftrightarrow (p \to (q \land \neg q))$
$\neg (p \lor q) \leftrightarrow (\neg p \land \neg q)$
$\neg (p \land q) \leftrightarrow p$
$((p \land q) \land \neg (p \land q)) \land r$
$p \to (q \lor r)$
$((p \land q) \land r) \to q$
$(p \land \neg p) \to (q \lor r)$
$\neg ((p \lor q) \lor r)$
$(q \land s) \leftrightarrow (p \leftrightarrow (p \land r))$

Exercício 9 Para cada um dos pares seguintes, indique se as proposições são equivalentes. Justifique a sua resposta com uma tabela de verdade completa ou parcial, conforme necessário.

$p, \neg p$
$p, p \lor p$
$p \to p, p \leftrightarrow p$
$p \lor \neg q, p \to q$
$p \land \neg p, \neg q \leftrightarrow q$
$\neg (p \land q), \neg p \lor \neq = q$
$\neg (p \to q), \neg p \to \neg q$
$p \to q, \neg q \to \neg p$
$p \lor (q \lor r), (p \lor q) \lor r$
$p \lor (q \land r), (p \lor q) \land r$

Exercício 10 Determine quais dos seguintes conjuntos de proposições são consistentes. Justifique a sua resposta com uma tabela de verdade completa ou parcial, conforme necessário.

$p \to p, \neg p \to \neg p, p \land p, p \lor p$
$p \land q, r \to \neg q, r$
$p \lor q, p \to r, q \to r$
$p \to q, q \to r, p, \neg r$
$q \land (r \lor p), p \to q, \neg (q \lor r)$
$p \lor q, q \lor r, r \to \neg p$

Exercício 11 Determine quais das seguintes consequências estão corretas. Justifique a sua resposta com uma tabela de verdade completa ou parcial, conforme necessário.

$p \to p ⊨ p$
$p \lor (p \to (p \leftrightarrow p)) ⊨ p$
$p \to (p \land \neg p) ⊨ \neg p$
$p \leftrightarrow \neg (q \leftrightarrow p) ⊨ p$
$p \lor (q \to p) ⊨ \neg p \to \neg q$
$p \to q, q ⊨ p$
$p \lor q, q \lor r, \neg p ⊨ q \land r$
$p \lor q, q \lor r, \neg q ⊨ p \land r$
$(q \land p) \to r, (r \land p) \to q ⊨ (r \land q) \to p$
$p \leftrightarrow q, q \leftrightarrow r ⊨ p \leftrightarrow r$
$\neg p \equiv p \to ⊥$

Exercício 12 Responda a cada uma das questões seguintes, justificando a sua resposta.

Suponha que $p$ e $q$ são (semanticamente) equivalentes ( $p \equiv q$ ). O que pode dizer sobre $p \leftrightarrow q$ ?
Suponha que $(p \land q) \to r$ é contingente. O que pode dizer sobre $p, q ⊨ r$ ?
Suponha que $p, q, r$ é inconsistente. O que pode dizer sobre $p \land q \land r$ ?
Suponha que $p$ é uma contradição. O que pode dizer sobre $p, q ⊨ r$ ?
Suponha que $r$ é uma tautologia. O que pode dizer sobre $p, q ⊨ r$ ?
Suponha que $p$ e $q$ são equivalentes. O que pode dizer sobre $p \lor q$ ?
Suponha que $p$ e $q$ não são equivalentes. O que pode dizer sobre $p \lor q$ ?

Exercício 13 Quantas operações booleanas com dois argumentos existem? Quais são (construa as respetivas tabelas)? Em geral, quantas operações booleanas com $n$ argumentos existem?

Exercício 14 A linguagem da lógica proposicional usa os conectivos primitivos $\land, \lor, \to$ e $\neg$ e define $⊥, ⊤$ e $\leftrightarrow$ como abreviaturas de certas expressões que usam apenas os conectivos primitivos.

Já foi visto que $p \to q \equiv \neg p \lor q$ pelo que $\to$ pode perder o estatuto de conectivo primitivo e ser definido como uma abreviatura de $\neg p \lor q$ . Como também $p \lor q \equiv \neg (\neg p \land \neg q)$ então os conectivos $\land$ e $\neg$ são suficientes como conectivos primitivos, dispensando $\to$ e $\lor$ .

A tabela abaixo define alguns conectivos menos comuns. Verifique se algum é suficiente para definir todos os conectivos binários como abreviaturas.

$a v v f f b v f v f a \otimes b f v v f a ↓ b f f f v a ↑ b f v v v a \leftarrow b v v f v$

Exercício 15 Verifique que as seguintes conclusões estão erradas, mostrando uma valoração em que as hipóteses são verdadeiras mas a conclusão é falsa.

$\neg p \lor (q \to p) ⊢ \neg p \land q$
$\neg r \to (p \lor q), r \land \neg q ⊢ r \to q$
$p \to (q \to r) ⊢ p \to (r \to q)$
$\neg p, p \lor q ⊢ \neg q$
$p \to (\neg q \lor r), \neg r ⊢ \neg q \to \neg p$

Exercício 16 Para cada uma das seguintes conclusões erradas, encontre uma interpretação em linguagem natural dos símbolos $p, q, r$ onde as premissas são verdadeiras mas as conclusões falsas.

$p \lor q ⊢ p \land q$
$\neg p \to \neg q ⊢ \neg q \to \neg p$
$p \to q ⊢ p \lor q$
$p \to (q \lor r) ⊢ (p \to q) \land (p \to r) .$

Exercício 17 Construa fórmulas para as funções $α, β$ e $γ$ na FNC e na FND com base na seguinte tabela:

$a v f v f v f v f b v v f f v v f f c v v v v f f f f α (a, b) f f f v β (a, b, c) v f f v f f v f γ (a, b, c) f v f f v f f v$

Aplicações

Exercício 18.

$31 21 T_{f} ✓ 11 ✓ 22 12 a_{b} ✓ 13$

Suponha que Teseu percorreu o seguinte caminho $11, 12, 11, 21$ até à situação na figura e recolheu as perceções "nada" em $11$ , uma brisa em $12$ e fedor (mau cheiro) em $21$ . A anotação " $✓$ " significa posição segura (ie Teseu sabe que não tem nem o Minotauro nem um poço). Agora Teseu interroga-se sobre as posições adjacentes $31, 22$ e $13$ .

Construa todos os mundos possíveis para as posições adjacentes, isto é todas as valorações sobre o conteúdo conjunto das posições $31, 22$ e $13$ compatíveis com as regras do Labirinto do Minotauro (deve encontrar 32).
Assinale os casos consistentes com as perceções de Teseu.
Assinale os casos em que são verdadeiras $\neg p_{22}$ e $m_{31}$ .
Conclua que o Minotauro está em $31$ , está um poço em $13$ e que $22$ é segura.

Se representar por $BC$ (Base de Conhecimento) as proposições que descrevem as perceções e os mundos possíveis, mostrou que $BC ⊨ p_{31} \land m_{13} \land \neg m_{22} \land \neg p_{22}$ e portanto descobriu que o Minotauro está em $13$ , um poço em $31$ e que a posição $22$ é segura.

Exercício 19

O Minesweeper é um jogo bem conhecido. O mundo é uma grelha retangular com $n$ casas e $m$ minas espalhadas ao acaso. Cada casa pode ser sondada e o resultado é morte se estiver uma mina nessa casa ou, se não estiver uma mina na casa sondada, o número de minas nas casas adjacentes (incluindo as diagonais).

Represente por $m_{ij}$ o facto "está uma mina na posição $ij$ ". Escreva "estão exatamente duas minas adjacentes a $11$ " usando uma proposição com os conectivos e átomos $m_{ij}$ .
Generalize a alínea anterior para construir uma proposição na FNC que afirme que $k$ (das $n = 3, 5, 8$ ) casas adjacentes têm minas.