Porta NAND

NAND ou Conectivo de Sheffer é um conectivo utilizado em lógica. Esse conectivo equivale à negação da conjunção, expressa usualmente como "não (algo)... e (algo)... ". Também conhecido como conectivo da negação alternativa, é verdadeiro se pelo menos um dos operandos for falso.

No âmbito da álgebra booleana e na eletrônica digital é conhecido como NAND ("não...e..."). É um dos operadores que, por si só, pode ser usado para expressar todas as funções booleanas que podem ser escritas na lógica proposicional. Juntamente com o NEM, é um dos dois operadores unários funcionalmente completos da lógica proposicional.

O conectivo NAND foi inventado por Henry M. Sheffer, que provou (Sheffer 1913) que todos os operadores comuns da lógica proposicional (não (not), e (and), ou (or), implicação, e os demais), podem ser expressos em termos do NAND. Charles Sanders Peirce (1880) descobriu esse fato mais de 30 anos antes, mas nunca publicou sua descoberta.

Definição

O NAND é uma operação lógica binária, através da qual normalmente, os valores de duas proposições produzem um valor falso se e somente se ambos seus operandos forem verdadeiros. Ou seja, o NAND produz um valor verdadeiro se, e somente se pelo menos um de seus operandos for falso.

Tabela Verdade

A tabela verdade de p NAND q (escrito também como $p\mid q$ ou $p\uparrow q$ ) é como segue:

**NAND**
A	B	S
0	0	1
0	1	1
1	0	1
1	1	0

Uma maneira usual de se expressar p NAND q é ${\overline {p\cdot q}}$ , onde o símbolo $\cdot$ significa E a linha sobre a expressão significa NÃO, ou seja, se trata da negação lógica dessa expressão.

O NAND não é usado em sentenças do dia a dia porque gera uma confusão relacionada com uma dupla negação. Está aqui um exemplo do uso da sentença:

Operador NAND: Nós morreremos certamente se tivermos água “NAND” comida.

Termos comuns: Nós morreremos certamente se não tivermos comida e água.

ou ainda: Nós morreremos certamente se não tivermos comida e/ou água. (Este é mais comum em textos que na vida real)

Expressões equivalentes

Em termos de NAND, os outros operadores lógicos podem ser expressos como:

"não p" é equivalente a "p NAND p"	$\neg P\equiv P\|P,$
"p e q" é equivalente a "(p NAND q) NAND (p NAND q)"	$P\wedge Q\equiv (P\|Q)\|(P\|Q),$
"p ou q" é equivalente a "(p NAND p) NAND (q NAND q)"	$P\vee Q\equiv (P\|P)\|(Q\|Q),$
"p implica q" é equivalente a "(p NAND q) NAND p"	$P\rightarrow Q\equiv P\|(Q\|Q)\equiv P\|(P\|Q)$

Descrição do Hardware

As portas NAND são portas lógicas básicas que são reconhecidas na TTL e circuitos integrados CMOS.

Entrada A1
Entrada B1
Saída Q1
Saída Q2
Entrada B2
Entrada A2
V_SS
Entrada A3
Entrada B3
Saída Q3
Saída Q4
Entrada B4
Entrada A4
V_DD

Os sistemas digitais que empregam circuitos lógicos utilizam a propriedade de que todas as operações booleanas podem ser escritas através da porta NAND. Em algumas expressões lógicas mais complexas, normalmente escritas em função de outras funções lógicas tais como E(AND), OU (OR), e NÃO (NOT), se escritas em função de NAND têm um menor custo, porque a implementação desses circuitos usando essa porta gera um resultado mais compacto que as implementações normais.

Sistema Formal Baseado no Conectivo de Sheffer

Este é um exemplo de um sistema formal baseado inteiramente no conectivo de Sheffer, contudo tem expressividade funcional da lógica proposicional.

Símbolos

A B C D E F G '

( | )

O Conectivo de Sheffer possui a propriedade da comutatividade, porém não goza da associatividade. Todo o sistema formal que o inclui deve incluir também como estão agrupados os símbolos. Será empregado “(” e ”)” para representar esse agrupamento.

Gramática

As letras A, B, C, D, E, F e G são átomos. Quaisquer das letras que apareceram uma vez ou diversas vezes também são átomos (por exemplo, de A', B', C', D' são átomos).

Regra de Construção: Um átomo é uma fórmula bem formada (fbf).

Regra de Construção 2: Se X e Y são fórmulas bem formadas, então $X\mid Y$ também o é.

Regra de Fechamento: Se uma fórmula não puder ser construída usando as definições da regra de Construção 1 e 2, ela não é uma fórmula bem formada.

Um procedimento da decisão para determinar se uma fórmula é bem formada pode ser descrito assim: "Decompõe-se" a fórmula, aplicando as regras de construção para trás, desse modo a fórmula é quebrada em subfórmulas menores; e repetir esse processo de decomposição a cada uma das subfórmulas; nota-se que esse passo é feito de maneira recursiva. Eventualmente, a fórmula deve ser reduzida aos seus átomos, porém, se alguma dessas subfórmulas não puder ser reduzida a um átomo, então não é uma fórmula bem formada.

Axiomas

Considere o seguinte axioma esquemático, no qual todas as metavariáveis são substituídas por fórmulas bem formadas:

   $(U\mid (U\mid (V\mid (U\mid U))))$

Regras de Inferência

Substituição dos equivalentes: A fbf (fórmula bem formada) X contém uma ou mais instancias da subfórmula U. Se $U=V$ , então substituir uma ou mais instancias de U em X por V não altera o valor verdade de X. Em particular, se $X=Y$ for um teorema, esse fato permanece após qualquer substituição de V por U.

Comutatividade: $(X\mid Y)=(Y\mid X)$

Dualidade: Se as fórmulas $X$ e $(X\mid X)$ aparecerem em um teorema, então se forem substituídas uma pela outra em todas as vezes que aparecerem, o resultado disso também será um teorema.

Mimese: $(U\mid (X\mid X))=(U\mid (U\mid X))$

Dupla Negação: $((X\mid X)\mid (X\mid X))=X$

$(U\mid (U\mid (V\mid (V\mid X))))=(V\mid (V\mid (U\mid (U\mid X))))$

MP-1: $U,(U\mid (V\mid X))\mid -V$

MP-2: $U,(U\mid (V\mid X))\mid -X$

Nota: A fórmula $(U\mid (V\mid X))$ tem a interpretação de $U\to V\land X$ . Modus Ponens é um caso especial de MP-1 e MP-2 quando V e X são idênticos.

Simplificação

Como o único conectivo desta lógica é "|", o símbolo poderia ser descartado completamente, deixando somente os parênteses para agrupar as letras. Um par dos parênteses deve sempre incluir um par das fbfs (fórmulas bem formadas). Exemplos nesta notação simplificada são:

(A(A(B(B((AB)(AB)))))) e (A(A((BB)(AA)))).

A notação pode ser simplificada ainda mais, deixando:

(U):= (UU)

((U)) := U

equivalente a qualquer U. Essa simplificação implica mudar algumas regras:

1. Mais de duas letras são permitidas entre parênteses.

2. Para letras ou fbfs entre parênteses é permitida a comutação.

3. Letras ou fbfs repetidas entre os mesmos conjuntos de parênteses podem ser eliminadas.

Ver também