Exemplos de lógica proposicional

Neste artigo, vamos mostrar algumas fórmulas e as suas possíveis atribuições por meio da tabela-verdade.

Primeiro exemplo

Vamos tentar descobrir quando esta fórmula é verdadeira: ϕ = (p ∧ q) ∨ ¬q. Escrevemos na tabela as variáveis proposicionais p e q:

$$\begin{array}{cc}p& q\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Depois, acrescentamos à tabela a primeira parte da fórmula: (p ∧ q), a negação ¬q e, por fim, a fórmula inteira:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Agora calculamos os valores da terceira coluna, que é uma conjunção simples, e também da negação; nela, basta colocar os valores invertidos em relação aos da segunda coluna:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}$$

Por fim, calculamos os valores da última coluna. Ela é a fórmula inteira. De acordo com a nossa tabela, calculamos a disjunção “entre a terceira e a quarta coluna”. Resultado:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0& 1\\ 1& 0& 0& 1& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 1\end{array}$$

Segundo exemplo

Mesmo enunciado, outra fórmula: ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q). Vemos que na fórmula aparecem as variáveis proposicionais p e q e as suas negações. Então, primeiro criamos uma tabela com os dois símbolos e as suas negações:

$$\begin{array}{cccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q\\ 1& 1& 0& 0\\ 1& 0& 0& 1\\ 0& 1& 1& 0\\ 0& 0& 1& 1\end{array}$$

Depois, acrescentamos as fórmulas p ∧ ¬q e ¬p ⇒ q, que já sabemos avaliar facilmente, porque temos na tabela tanto as atribuições das proposições individuais quanto as das suas negações. A tabela fica assim:

$$\begin{array}{cccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)\\ 1& 1& 0& 0& 0& 1\\ 1& 0& 0& 1& 1& 1\\ 0& 1& 1& 0& 0& 1\\ 0& 0& 1& 1& 0& 0\end{array}$$

Por último, resta avaliar a fórmula inteira, que é a equivalência entre as duas últimas colunas:

$$\begin{array}{ccccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)& \varphi \\ 1& 1& 0& 0& 0& 1& 0\\ 1& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 0\\ 0& 0& 1& 1& 0& 0& 1\end{array}$$

Terceiro exemplo

O terceiro exemplo será um pouco mais complicado: vamos tentar três variáveis proposicionais, o que torna o cálculo da tabela mais trabalhoso. A fórmula será esta: ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)).

Como temos três variáveis proposicionais, o número total de atribuições possíveis é igual a oito:

$$\begin{array}{ccc}p& q& r\\ 1& 1& 1\\ 1& 1& 0\\ 1& 0& 1\\ 1& 0& 0\\ 0& 1& 1\\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}$$

Daqui em diante, procedemos como no caso anterior: avaliamos cada colunazinha nas oito linhas. A tabela inteira ficará assim:

$$\begin{array}{ccccccccc}p& q& r& \mathrm{\neg }p& (p\Rightarrow q)& (\mathrm{\neg }p\vee q)& \mathrm{\neg }(p\Rightarrow q)& (r\iff (\mathrm{\neg }p\vee q))& \varphi \\ 1& 1& 1& 0& 1& 1& 0& 1& 0\\ 1& 1& 0& 0& 1& 1& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 0& 1& 0\\ 0& 1& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 1& 1& 1& 1& 0& 1& 0\\ 0& 0& 0& 1& 1& 1& 0& 0& 0\end{array}$$

Quarto exemplo

Este exemplo já não será dado como uma fórmula comum, mas como um problema em palavras. Três amigos que querem ir a uma festa animada, onde modelos de topless vão servir petiscos, não gostam muito uns dos outros e impõem condições para ir à festa. Os nomes deles são Marcos, João e Pedro. As regras são as seguintes:

1. Se Marcos for, então João também vai.
2. Na festa aparece Pedro ou, se Marcos for, então João não vai.
3. Pedro aparece se, e somente se, Marcos não aparecer ou João não aparecer.

A pergunta é: todos podem ir à festa? Se não, quem pode ir à festa sem quebrar nenhuma regra?

Primeiro, precisamos reescrever as frases anteriores em variáveis proposicionais e fórmulas. Vamos chamar as variáveis proposicionais de M, J e P (Marcos, João, Pedro), e cada uma sempre significará uma proposição do tipo “Marcos vai à festa”. A primeira regra poderia ser reescrita assim: M ⇒ J — “se M, então J”, ou seja, “se Marcos for à festa, então João vai à festa”.

Reescrevemos a segunda regra assim. A regra começa com a frase “Na festa aparece Pedro ou…”, então evidentemente vamos precisar de uma disjunção. Por enquanto, escrevemos isto: P ∨ … A parte seguinte da frase diz: “se Marcos for, então João não vai”. Isso é uma implicação, em que, do lado direito, ainda precisamos usar uma negação. “João não vai” = ¬J. A implicação inteira ficaria assim: M ⇒ ¬J. Juntamos isso à disjunção anterior: P ∨ (M ⇒ ¬J).

Reescrevemos a terceira regra assim: começamos com “Pedro aparece se, e somente se”. Isso significa uma equivalência: P ⇔ … Depois temos “Marcos não aparece ou João não aparece”, que reescrevemos assim: ¬M ∨ ¬J. Montamos tudo: (P ⇔ (¬M ∨ ¬J)).

Agora colocamos todas as fórmulas na tabela e calculamos os valores:

$$\begin{array}{cccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))\\ 1& 1& 1& 1& 1& 0\\ 1& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 1\\ 1& 0& 0& 0& 1& 0\\ 0& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0\end{array}$$

A pergunta era se os três rapazes podem ir à festa animada. Encontramos a resposta na primeira linha. Ela corresponde ao caso em que todos os rapazes vão — isso é indicado pelos três uns nas três primeiras colunas. Todas as condições são satisfeitas? A primeira sim (quarta coluna), a segunda também (quinta coluna), mas a última não (última coluna), ali há um zero. Isso significa que, se os três forem, a terceira condição não será satisfeita.

Procuramos, então, as linhas em que, nas posições que representam as condições (ou seja, nas três últimas colunas), há só uns. O um significa que a condição é satisfeita. Vemos que isso acontece em dois casos: quando João e Pedro vão, mas Marcos não, e quando vai só Pedro.

Você também pode calcular isso acrescentando à tabela a fórmula ϕ, que será a conjunção das três condições. Assim, ela ficará desta forma: ϕ = ((M ⇒ J) ∧ (P ∨ (M ⇒ ¬J)) ∧ (P ⇔ (¬M ∨ ¬J))). Isso representa o que queremos: que todas as fórmulas (todas as condições) sejam satisfeitas. A tabela ficaria então assim:

$$\begin{array}{ccccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))& \varphi \\ 1& 1& 1& 1& 1& 0& 0\\ 1& 1& 0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1& 1& 0\\ 1& 0& 0& 0& 1& 0& 0\\ 0& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$

Alguns exemplos de tabela-verdade

Como escrevi um programa que sabe montar automaticamente a tabela inteira a partir de uma fórmula dada, preciso aproveitá-lo como se deve, e por isso seguem mais algumas fórmulas resolvidas:

Fórmula: ((a ∧ ¬b) ∨ (b ∧ (b ⇒ a))). Tabela:

$$\begin{array}{ccccc}a& b& (a\wedge \mathrm{\neg }b)& (b\wedge (b\Rightarrow a))& ((a\wedge \mathrm{\neg }b)\vee (b\wedge (b\Rightarrow a)))\\ 1& 1& 0& 1& 1\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}$$

Fórmula: (a ∨ ¬a) ⇔ (b ∧ ¬b). Tabela:

$$\begin{array}{ccccc}a& b& (a\vee \mathrm{\neg }a)& (b\wedge \mathrm{\neg }b)& ((a\vee \mathrm{\neg }a)\iff (b\wedge \mathrm{\neg }b))\\ 1& 1& 1& 0& 0\\ 1& 0& 1& 0& 0\\ 0& 1& 1& 0& 0\\ 0& 0& 1& 0& 0\end{array}$$

Fórmula: ¬(a ∨ b) ⇔ (¬b ∧ ¬a). Tabela:

$$\begin{array}{ccccc}a& b& \mathrm{\neg }(a\vee b)& (\mathrm{\neg }b\wedge \mathrm{\neg }a)& (\mathrm{\neg }(a\vee b)\iff (\mathrm{\neg }b\wedge \mathrm{\neg }a))\\ 1& 1& 0& 0& 1\\ 1& 0& 0& 0& 1\\ 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 1\end{array}$$

Fórmula: ϕ = (¬p ⇔ (q ∧ r)) ⇒ (p ∨ ¬(p ∧ q)). Tabela:

$$\begin{array}{cccccccc}p& q& r& (q\wedge r)& \mathrm{\neg }(p\wedge q)& (\mathrm{\neg }p\iff (q\wedge r))& (p\vee \mathrm{\neg }(p\wedge q))& \varphi \\ 1& 1& 1& 1& 0& 0& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 0& 1& 0& 1& 1& 1& 1\\ 1& 0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 0& 1& 0& 1& 1\\ 0& 0& 1& 0& 1& 0& 1& 1\\ 0& 0& 0& 0& 1& 0& 1& 1\end{array}$$

Fórmula: ϕ = ¬(p ⇔ ¬q) ∧ (r ⇒ ¬p) ∧ (p ∨ r). Tabela:

$$\begin{array}{ccccccc}p& q& r& \mathrm{\neg }(p\iff \mathrm{\neg }q)& (r\Rightarrow \mathrm{\neg }p)& (p\vee r)& \varphi \\ 1& 1& 1& 1& 0& 1& 0\\ 1& 1& 0& 1& 1& 1& 1\\ 1& 0& 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1& 1& 0\\ 0& 1& 1& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$