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?

$$ \begin{gathered} 1 = \sqrt{1} = \sqrt{\del{-1} \del{-1}} = \sqrt{-1} \sqrt{-1} \cr = \del{\sqrt{-1}}^2 = i^2 = -1 \end{gathered} $$

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

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

$R_1: x\lit{I} \vdash x\lit{IU}$.
$R_2: \lit{M}x \vdash \lit{M}xx$.
$R_3: x\lit{III}y \vdash x\lit{U}y$.
$R_4: x\lit{UU}y \vdash xy$.

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

Uma prova é uma sequência finitas de expressões $x_1, x_2, \ldots, 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 $\lit{MUII}$ é um teorema.
O número de $\lit{I}$ de um teorema nunca é múltiplo de três.
A expressão $\lit{M} \lit{I}^{2n}$, para qualquer $n \geq 0$, é um teorema.
Se $x\lit{III}$ é um teorema, então $x$ é um teorema.
Se $n = 2^m - 3k, k \geq 0$ então $\lit{M} \lit{I}^n$ é teorema.
A expressão $\lit{M} \lit{I}^n$ é um teorema para qualquer $n$ que não seja múltiplo de três.
Uma expressão $x$ é teorema de $\lit{MIU}$ se e só se é da forma $\lit{M}y$ em que $y$ é uma expressão formada só por $\lit{I}$ e $\lit{U}$ e onde o número de $\lit{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 é $\pi$.
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$
$\del{p \to q} \land \neg\del{r \lor p \to q}$
$\del{p \to q} \to \del{r \to s \lor t}$
$p \lor \del{\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 \vdash p$
$p \land p \vdash p$
$p \vdash p \land p$
$p, p \to q, q \to r \vdash r$
$p, p \to \del{q \to r}, p \to q \vdash r$
$p \to q, q \to r \vdash p \to r$
$p \to q \vdash \del{q \to r} \to \del{p \to r}$
$\vdash \del{p \to q} \to \del{q \to r} \to \del{p \to r}$
$\vdash p \land q \to p$
$\vdash p \land q \to q$
$\vdash p \to \del{q \to p \land q}$
$\vdash \neg\neg p \to p$
$\vdash p \to \del{p \to q} \to q$
$p \to q, \neg q \vdash \neg p$
$p \vdash \neg\del{\neg p \land \neg q}$
$p \to q \vdash \neg q \to \neg p$
$p \vdash \neg \neg p$
$\neg q \to \neg p \vdash p \to q$
$p \lor \del{q \land r} \dashv\vdash \del{p \lor q} \land \del{p \lor r}$
$p \to q \dashv\vdash \neg\del{p \land \neg q}$
$p \land q \dashv\vdash q \land p$
$p \lor q \dashv\vdash q \lor p$
$p \land \del{q \land r} \dashv\vdash \del{p \land q} \land r$
$p \lor \del{q \lor r} \dashv\vdash \del{p \lor q} \lor r$
$p \land \del{q \lor r} \dashv\vdash \del{p \land q} \lor \del{p \land r}$
$\del{p \land q} \lor \del{p \land \neg q} \vdash p$
$\neg p \vdash p \to q$
$p \vdash 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$
$\del{p \liff q} \liff \neg\del{p \liff \neg q}$
$\del{p \land q} \lor \del{q \land p}$
$\del{p \to q} \lor \del{q \to p}$
$\neg\del{p \to \del{q \to p}}$
$\del{p \land q} \to \del{q \lor p}$
$p \liff \del{p \to \del{q \land \neg q}}$
$\neg\del{p \lor q} \liff \del{\neg p \land \neg q}$
$\neg\del{p \land q} \liff p$
$\del{\del{p \land q} \land \neg\del{p \land q}} \land r$
$p\to \del{q \lor r}$
$\del{\del{p \land q} \land r} \to q$
$\del{p \land \neg p} \to \del{q \lor r}$
$\neg\del{\del{p \lor q} \lor r}$
$\del{q \land s} \liff \del{p \liff \del{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 \liff p$
$p \lor \neg q, p \to q$
$p \land \neg p, \neg q \liff q$
$\neg\del{p \land q}, \neg p \to \neg q$
$\neg\del{p \to q}, \neg p \to \neg q$
$p \to q, \neg q \to \neg p$
$p \lor \del{q \lor r}, \del{p \lor q} \lor r$
$p \lor \del{q \land r}, \del{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 \del{r \lor p}, p \to q, \neg\del{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 \models p$
$p \lor\del{p \to \del{p \liff p}} \models p$
$p \to \del{p \land \neg p} \models \neg p$
$p \liff \neg\del{q \liff p} \models p$
$p \lor \del{q \to p} \models \neg p \to \neg q$
$p \to q, q \models p$
$p \lor q, q \lor r, \neg p \models q \land r$
$p \lor q, q \lor r, \neg q \models p \land r$
$\del{q \land p} \to r, \del{r \land p} \to q \models \del{r \land q} \to p$
$p \liff q, q \liff r \models p \liff r$
$\neg p \equiv p \to \bot$

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 \liff q$?
Suponha que $\del{p \land q} \to r$ é contingente. O que pode dizer sobre $p, q \models 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 \models r$?
Suponha que $r$ é uma tautologia. O que pode dizer sobre $p, q \models 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 $\bot, \top$ e $\liff$ 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\del{\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.

$$ \begin{array}{cc|cccc} a & b & a \otimes b & a \downarrow b & a \uparrow b & a \gets b\cr \hline \ndT & \ndT & \ndF & \ndF & \ndF & \ndT \cr \ndT & \ndF & \ndT & \ndF & \ndT & \ndT \cr \ndF & \ndT & \ndT & \ndF & \ndT & \ndF \cr \ndF & \ndF & \ndF & \ndT & \ndT & \ndT \end{array} $$

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 \del{q \to p} \vdash \neg p \land q$
$\neg r \to \del{p \lor q}, r \land \neg q \vdash r \to q$
$p \to \del{q \to r} \vdash p \to \del{r \to q}$
$\neg p, p \lor q \vdash \neg q$
$p \to \del{\neg q \lor r}, \neg r \vdash \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 \vdash p \land q$
$\neg p \to \neg q \vdash \neg q \to \neg p$
$p \to q \vdash p \lor q$
$p \to \del{q \lor r} \vdash \del{p \to q} \land \del{p \to r}.$

Exercício 17 Construa fórmulas para as funções $\alpha, \beta$ e $\gamma$ na FNC e na FND com base na seguinte tabela:

$$ \begin{array}{ccc|ccc} a & b & c & \alpha\at{a,b} & \beta\at{a,b,c} & \gamma\at{a,b,c} \cr \hline \ndT & \ndT & \ndT & \ndF & \ndT & \ndF \cr \ndF & \ndT & \ndT & \ndF & \ndF & \ndT \cr \ndT & \ndF & \ndT & \ndF & \ndF & \ndF \cr \ndF & \ndF & \ndT & \ndT & \ndT & \ndF \cr \ndT & \ndT & \ndF & & \ndF & \ndT \cr \ndF & \ndT & \ndF & & \ndF & \ndF \cr \ndT & \ndF & \ndF & & \ndT & \ndF \cr \ndF & \ndF & \ndF & & \ndF & \ndT \end{array} $$

Aplicações

Exercício 18.

$$ \begin{array}{:c:c:c:c:} \hdashline \cr \hdashline 31 \cr \hdashline 21~\cvT_{\cvPerM}\checkmark & 22 & \cr \hdashline 11\checkmark &12~\phantom{a}_{\cvPerP}\checkmark & 13 & \cr \hdashline \end{array} $$

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 “$\checkmark$” 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 \models 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.

Keyboard shortcuts