Exercício 11. O conector NAND (não-e) é definido por : \mathrm{pNANDq} \Leftrightarrow \neg(\mathrm{p} \wedge \mathrm{q}). Dar a sua tabela de verdade. Ele corresponde a um conjunto?
O que se pode dizer de pNANDp ? Podem-se definir os 3 conectores principais em função unicamente do NAND?
O conector NOR (não-ou) é definido por \neg(p \vee q). Dar a sua tabela de verdade. Ele corresponde a um conjunto?
Podem-se definir os 3 conectores principais unicamente em função do NOR ?
Observação: O conector NAND é também denotado \uparrow. Este operador é de extrema importância em informática e em eletrônica, pois ele permite, sozinho, representar o conjunto das funções lógicas, necessário para a execução dos circuitos dos computadores.

Passo 1

O enunciado pede quatro coisas: a tabela de verdade de p NAND q, mostrar que o conjunto \{\text{NAND}\} é funcionalmente completo (isto é, permite definir \neg, \land, \lor só com NAND) e exponha como fazer isso, e em seguida repita tudo para o conector NOR. Vamos usar lógica proposicional, tabelas de verdade e as identidades básicas de negação e De Morgan.

Passo 2

Definimos o NAND por
p \uparrow q \;\equiv\;\neg\bigl(p\land q\bigr).
A tabela de verdade de p\uparrow q (onde representamos falso por 0 e verdadeiro por 1) é
\begin{array}{c c | c} p & q & p \uparrow q\\hline 0 & 0 & 1\\\\ 0 & 1 & 1\\\\ 1 & 0 & 1\\\\ 1 & 1 & 0 \end{array}

Passo 3

Para ver que \{\uparrow\} é funcionalmente completo, notamos primeiro que
p\uparrow p \;=\;\neg\bigl(p\land p\bigr)\;=\;\neg p,
ou seja, usando apenas NAND podemos obter a negação. A partir daí:
p\land q =\neg\bigl(p\uparrow q\bigr) =(p\uparrow q)\uparrow(p\uparrow q),
p\lor q =\neg p\land\neg q =(p\uparrow p)\land(q\uparrow q) =\bigl(p\uparrow p\bigr)\uparrow\bigl(q\uparrow q\bigr).
Portanto com NAND só conseguimos \neg, \land e \lor.

Passo 4

Definimos o NOR por
p \downarrow q \;\equiv\;\neg\bigl(p\lor q\bigr).
A tabela de verdade de p\downarrow q é
\begin{array}{c c | c} p & q & p \downarrow q\\hline 0 & 0 & 1\\\\ 0 & 1 & 0\\\\ 1 & 0 & 0\\\\ 1 & 1 & 0 \end{array}

Passo 5

Para ver que \{\downarrow\} é funcionalmente completo, notamos que
p\downarrow p \;=\;\neg\bigl(p\lor p\bigr)\;=\;\neg p.
Em seguida
p\lor q =\neg\bigl(p\downarrow q\bigr) =(p\downarrow q)\downarrow(p\downarrow q),
p\land q =\neg p\lor\neg q =(p\downarrow p)\lor(q\downarrow q) =\bigl(p\downarrow p\bigr)\downarrow\bigl(q\downarrow q\bigr).
Logo com NOR só construímos \neg, \lor e \land.

Resposta

Tabela de verdade de p\uparrow q:
\begin{array}{c c | c} p & q & p \uparrow q\\hline 0 & 0 & 1\\\\ 0 & 1 & 1\\\\ 1 & 0 & 1\\\\ 1 & 1 & 0 \end{array} \{\,\uparrow\} é funcionalmente completo. p\uparrow p=\neg p, \;p\land q=(p\uparrow q)\uparrow(p\uparrow q), \;p\lor q=(p\uparrow p)\uparrow(q\uparrow q). Tabela de verdade de p\downarrow q:
\begin{array}{c c | c} p & q & p \downarrow q\\hline 0 & 0 & 1\\\\ 0 & 1 & 0\\\\ 1 & 0 & 0\\\\ 1 & 1 & 0 \end{array} \{\,\downarrow\} é funcionalmente completo. p\downarrow p=\neg p, \;p\lor q=(p\downarrow q)\downarrow(p\downarrow q), \;p\land q=(p\downarrow p)\downarrow(q\downarrow q).

Exercícios relacionados