NOU

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde Outubro de 2012).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.

NOU 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. Corresponde à palavra NAND do idioma inglês.

No âmbito da álgebra booleana e na eletrônica digital é conhecido como NOU ("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 NOU 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 NOU. Charles Sanders Peirce (1880) descobriu esse fato mais de 30 anos antes, mas nunca publicou sua descoberta.

Definição[editar | editar código-fonte]

O NOU é 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 NOU produz um valor verdadeiro se, e somente se pelo menos um de seus operandos for falso.

Tabela Verdade[editar | editar código-fonte]

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

NAND
p q  p \mid q
V V F
V F V
F V V
F F V

Uma maneira usual de se expressar p NOU 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 NOU 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 NOU: Nós morreremos certamente se tivermos água “nou” 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[editar | editar código-fonte]

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

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

Descrição do Hardware[editar | editar código-fonte]

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

Esse diagrama esquemático mostra como as portas NAND estão arranjadas na parte interna de um circuito integrado CMOS 4011.
  1. Entrada A1
  2. Entrada B1
  3. Saída Q1
  4. Saída Q2
  5. Entrada B2
  6. Entrada A2
  7. VSS
  8. Entrada A3
  9. Entrada B3
  10. Saída Q3
  11. Saída Q4
  12. Entrada B4
  13. Entrada A4
  14. VDD

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 NOU. 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 NOU 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[editar | editar código-fonte]

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

Símbolos[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]