Considere a proposição composta f(p, q, r) definida pela tabela abaixo.
Mostre que f(p, q, r) é logicamente equivalente à proposição (p \wedge q \wedge \neg r) \vee(p \wedge \neg q \wedge r) \vee(\neg p \wedge \neg q \wedge \neg r). Compare essa proposição com as três linhas da tabela que terminam com V. Utilize a mesma ideia para justificar que qualquer tabela verdade em um número qualquer de proposições p_{1}, p_{2}, \ldots, p_{n} é a tabela verdade de alguma proposição composta envolvendo as p_{i} e usando apenas os conectivos \neg, \vee, \wedge. Consequentemente qualquer proposição composta (envolvendo os conectivos usuais ou algum outro que venha a ser inventado) é equivalente a uma proposição que utiliza somente esses três conectivos.
p q r f(p, q, r)
V V V F
V V F V
V F V V
V F F F
F V V F
F V F F
F F V F
F F F V

Passo 1

O enunciado nos dá a tabela de verdade de f(p,q,r) e pede para mostrar que ela é equivalente à proposição
(p \wedge q \wedge \neg r)\;\vee\;(p \wedge \neg q \wedge r)\;\vee\;(\neg p \wedge \neg q \wedge \neg r).
Estamos, portanto, trabalhando com a construção de uma forma normal disjuntiva (DNF) de uma função booleana. Para isso, basta olhar para cada linha em que f é verdadeira e montar uma conjunção que seja verdadeira só nessa linha.

Passo 2

Da tabela, f(p,q,r)=V exatamente nas linhas
  1. p=V,\;q=V,\;r=F
  2. p=V,\;q=F,\;r=V
  3. p=F,\;q=F,\;r=F
Para cada uma, construímos uma conjunção que valide cada variável na forma correta:
  • Na linha 1: (p\wedge q\wedge \neg r).
  • Na linha 2: (p\wedge \neg q\wedge r).
  • Na linha 3: (\neg p\wedge \neg q\wedge \neg r).

Passo 3

Agora juntamos essas três conjunções com uma disjunção para obter uma fórmula que seja verdadeira exatamente nessas e somente nessas linhas. Assim,
f(p,q,r)\;\equiv\;(p \wedge q \wedge \neg r)\;\vee\;(p \wedge \neg q \wedge r)\;\vee\;(\neg p \wedge \neg q \wedge \neg r).
Comparando com a tabela, cada linha que dá V em f corresponde a uma das conjunções, e em todas as outras linhas todas as conjunções dão F, logo o disjuntor geral também dá F. Isso prova a equivalência.

Passo 4

O mesmo procedimento vale para qualquer número n de proposições p_{1},p_{2},\dots,p_{n}. Dada qualquer tabela verdade, basta:
  1. Enumerar as linhas em que a função booleana f(p_{1},\dots,p_{n}) vale V.
  2. Para cada linha i, montar a conjunção \bigwedge_{j=1}^{n}s_{ij}, onde s_{ij} = \begin{cases} p_{j}, & \text{se na linha }i\text{ a variável }p_{j}=V,\\\ \neg p_{j}, & \text{se na linha }i\text{ a variável }p_{j}=F. \end{cases}áá
  3. Fazer a disjunção de todas essas conjunções:
f(p_{1},\dots,p_{n})\;\equiv\;\bigvee_{i\colon f=V}\;\bigwedge_{j=1}^{n}s_{ij}.

Passo 5

Como qualquer proposição composta pode ser vista como uma função booleana por sua tabela-verdade, concluímos que ela é sempre equivalente a uma DNF que usa apenas os conectivos \neg, \wedge e \vee. Isso mostra que esses três conectivos são suficientes (formam um conjunto funcionalmente completo) para expressar qualquer proposição.

Resposta

f(p,q,r)\;\equiv\;(p \wedge q \wedge \neg r)\;\vee\;(p \wedge \neg q \wedge r)\;\vee\;(\neg p \wedge \neg q \wedge \neg r),
e, em geral, qualquer tabela verdade em n variáveis tem uma DNF da forma
\bigvee_{i\colon f=V}\;\bigwedge_{j=1}^{n} \begin{cases} p_{j}, & \text{se na linha }i\colon p_{j}=V,\\\ \neg p_{j}, & \text{se na linha }i\colon p_{j}=F. \end{cases}

Exercícios relacionados