Definimos o conectivo de Sheffer (Sheffer stroke) p \mid q dizendo que p \mid q é verdadeira se e somente se ao menos uma das proposições p, q for falsa. Justifique que
a) p \mid q \Longleftrightarrow \neg(p \wedge q) (por isto esta operação também é conhecida como NAND)
b) Cada uma das operações lógicas \neg, \wedge, \vee, \rightarrow \mathrm{e} \leftrightarrow é logicamente equivalente a uma proposição envolvendo somente o conectivo \mid. Por exemplo, \neg p é equivalente a p \mid p. p \wedge q é equivalente a \neg(p \mid q), que por sua vez é equivalente a (p \mid q) \mid(p \mid q). Portanto, toda proposição envolvendo os conectivos \neg, \vee, \wedge, \rightarrow \mathrm{e} \leftrightarrow é logicamente equivalente a uma proposição envolvendo somente o conectivo | .
OBS. Sheffer (1882-1964) em 1913 provou que todas as expressões lógicas poderiam ser escritas em função de uma única operação lógica, no caso |

Passo 1

O enunciado define o conectivo de Sheffer, escrito p \mid q, que vale verdadeira exatamente quando pelo menos uma das proposições p,q é falsa. Queremos (a) mostrar que
p\mid q \Longleftrightarrow \neg(p\wedge q)
e (b) exibir como qualquer conector lógico pode ser expressado usando só \mid, provando a completude funcional de Sheffer.

Passo 2

Vamos comparar as colunas de p\mid q e de \neg(p\wedge q) numa tabela-verdade:
\begin{array}{c c \,\big|\, c \,\big|\, c \,\big|\, c} p & q & p\wedge q & \neg(p\wedge q) & p\mid q \\\ \hline V & V & V & F & F \\\ V & F & F & V & V \\\ F & V & F & V & V \\\ F & F & F & V & V \end{array}
Como ambas as colunas coincidem em todos os casos, concluímos
p\mid q \Longleftrightarrow \neg(p\wedge q).

Passo 3

Para mostrar a completude funcional, primeiro expressamos negação e conjunção usando \mid:
\neg p \equiv p\mid p,
pois p\mid p é verdadeiro sempre que p for falso.
Em seguida,
p\wedge q \equiv \neg(p\mid q) \equiv (p\mid q)\mid(p\mid q).

Passo 4

Agora derivamos os demais conectivos:
p\vee q \equiv \neg p\wedge \neg q \equiv (p\mid p)\mid(q\mid q),
p\to q \equiv \neg p\vee q \equiv (p\mid p)\mid q,
p\leftrightarrow q \equiv (p\to q)\wedge(q\to p),
e cada \wedge e cada \to aí já foi traduzido em termos de \mid. Logo, \vee,\to,\leftrightarrow também se escrevem só com \mid.

Resposta

a) Pela tabela-verdade mostrou-se que p\mid q e \neg(p\wedge q) têm exatamente os mesmos valores, logo
p\mid q \Longleftrightarrow \neg(p\wedge q).
b) Mostrou-se explicitamente que
\neg p\equiv p\mid p,\quad p\wedge q\equiv (p\mid q)\mid(p\mid q),
e a partir delas construiu-se \vee,\to,\leftrightarrow usando apenas \mid. Portanto, toda operação lógica é funcionalmente completa com o conectivo de Sheffer.

Exercícios relacionados