Definimos o conectivo de Sheffer (Sheffer stroke)
dizendo que
é verdadeira se e somente se ao menos uma das proposições
for falsa. Justifique que
a)
(por isto esta operação também é conhecida como NAND)
b) Cada uma das operações lógicas
é logicamente equivalente a uma proposição envolvendo somente o conectivo
. Por exemplo,
é equivalente a
.
é equivalente a
, que por sua vez é equivalente a
. Portanto, toda proposição envolvendo os conectivos
é 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 |
a)
b) Cada uma das operações lógicas
Passo 1
O enunciado define o conectivo de Sheffer, escrito
, que vale verdadeira exatamente quando pelo menos uma das proposições
é falsa. Queremos (a) mostrar que
e (b) exibir como qualquer conector lógico pode ser expressado usando só
, provando a completude funcional de Sheffer.
Passo 2
Vamos comparar as colunas de
e de
numa tabela-verdade:
Como ambas as colunas coincidem em todos os casos, concluímos
Passo 3
Para mostrar a completude funcional, primeiro expressamos negação e conjunção usando
:
pois
é verdadeiro sempre que
for falso.
Em seguida,
Em seguida,
Passo 4
Agora derivamos os demais conectivos:
e cada
e cada
aí já foi traduzido em termos de
. Logo,
também se escrevem só com
.
Resposta
a) Pela tabela-verdade mostrou-se que
e
têm exatamente os mesmos valores, logo
b) Mostrou-se explicitamente que
e a partir delas construiu-se
usando apenas
. Portanto, toda operação lógica é funcionalmente completa com o conectivo de Sheffer.