AVC Sheffer - Sheffer stroke

AVC Sheffer
NAND
Definição
Mesa da verdade
Portão lógico
Formas normais
Disjuntivo
Conjuntivo
Polinômio de Zhegalkin
Treliça do Post
0-preservação	não
1-preservando	não
Monotone	não
Afim	não
	v; t; e;

Em funções booleanas e cálculo proposicional , o traço de Sheffer denota uma operação lógica que é equivalente à negação da operação de conjunção , expressa em linguagem comum como "não ambos". Também é chamado de nand ("não e") ou a negação alternativa , uma vez que diz com efeito que pelo menos um de seus operandos é falso. Na eletrônica digital , corresponde à porta NAND . É nomeado após Henry M. Sheffer e escrito como ↑ ou como | (mas não como ||, freqüentemente usado para representar disjunção ). Na notação Bocheński , pode ser escrito como D pq .

Seu dual é o operador NOR (também conhecido como flecha de Peirce ou punhal Quine ). Como seu dual, NAND pode ser usado sozinho, sem qualquer outro operador lógico, para constituir um sistema formal lógico (tornando NAND funcionalmente completo ). Essa propriedade torna o NAND gate crucial para a eletrônica digital moderna , incluindo seu uso no projeto de processadores de computador .

Definição

A operação NAND é uma operação lógica em dois valores lógicos . Ele produz um valor de verdadeiro, se - e somente se - pelo menos uma das proposições for falsa.

Mesa da verdade

A tabela verdade de (também escrita como , ou D pq ) é a seguinte ${\ displaystyle P \ uparrow Q}$ ${\ displaystyle P \ mathop {|} Q}$

${\ displaystyle P}$	${\ displaystyle Q}$	${\ displaystyle P \ uparrow Q}$
T	T	F
T	F	T
F	T	T
F	F	T

Equivalências lógicas

O golpe Sheffer de e é a negação de sua conjunção ${\ displaystyle P}$ ${\ displaystyle Q}$

${\ displaystyle P \ uparrow Q}$	${\ displaystyle \ Leftrightarrow}$	${\ displaystyle \ neg (P \ land Q)}$
	${\ displaystyle \ Leftrightarrow}$	${\ displaystyle \ neg}$

Pelas Leis de De Morgan , isso também é equivalente à disjunção das negações de e ${\ displaystyle P}$ ${\ displaystyle Q}$

${\ displaystyle P \ uparrow Q}$	${\ displaystyle \ Leftrightarrow}$	${\ displaystyle \ neg P}$	${\ displaystyle \ lor}$	${\ displaystyle \ neg Q}$
	${\ displaystyle \ Leftrightarrow}$		${\ displaystyle \ lor}$

História

O acidente vascular cerebral tem o nome de Henry M. Sheffer , que em 1913 publicou um artigo no Transactions of the American Mathematical Society fornecendo uma axiomatização de álgebras booleanas usando o acidente vascular cerebral, e provou sua equivalência a uma formulação padrão por Huntington empregando os operadores familiares de lógica proposicional ( e , ou , não ). Por causa da autodualidade das álgebras booleanas, os axiomas de Sheffer são igualmente válidos para as operações NAND ou NOR no lugar do traço. Sheffer interpretou o traço como um sinal de não disjunção ( NOR ) em seu artigo, mencionando a não conjunção apenas em uma nota de rodapé e sem um sinal especial para isso. Foi Jean Nicod quem primeiro usou o traço como um sinal de não conjunção (NAND) em um artigo de 1917 e que desde então se tornou prática corrente. Russell e Whitehead usaram o traço de Sheffer na segunda edição de 1927 do Principia Mathematica e o sugeriram como um substituto para as operações "ou" e "não" da primeira edição.

Charles Sanders Peirce (1880) havia descoberto a integridade funcional do NAND ou NOR mais de 30 anos antes, usando o termo ampheck (para 'cortar nos dois sentidos'), mas ele nunca publicou sua descoberta.

Propriedades

NAND não possui nenhuma das cinco propriedades a seguir, cada uma das quais deve estar ausente, e a ausência de todas é suficiente para, pelo menos, um membro de um conjunto de operadores funcionalmente completos : verdade-preservação, falsidade- preservação, linearidade , monotonicidade , autodualidade . (Um operador é verdade- (falsidade-) preservando se seu valor é verdade (falsidade) sempre que todos os seus argumentos são verdade (falsidade).) Portanto, {NAND} é um conjunto funcionalmente completo.

Isso também pode ser realizado da seguinte maneira: Todos os três elementos do conjunto funcionalmente completo {AND, OR, NOT} podem ser construídos usando apenas NAND . Portanto, o conjunto {NAND} deve ser funcionalmente completo também.

Outras operações booleanas em termos de traço de Sheffer

Expresso em termos de NAND , os operadores usuais da lógica proposicional são: ${\ displaystyle \ uparrow}$

${\ displaystyle \ neg P}$	${\ displaystyle \ Leftrightarrow}$	${\ displaystyle P}$	${\ displaystyle \ uparrow}$	${\ displaystyle P}$
	${\ displaystyle \ Leftrightarrow}$		${\ displaystyle \ uparrow}$

${\ displaystyle P \ rightarrow Q}$	${\ displaystyle \ Leftrightarrow}$	${\ displaystyle ~ P}$	${\ displaystyle \ uparrow}$	${\ displaystyle (Q \ uparrow Q)}$	${\ displaystyle \ Leftrightarrow}$	${\ displaystyle ~ P}$	${\ displaystyle \ uparrow}$	${\ displaystyle (P \ uparrow Q)}$
	${\ displaystyle \ Leftrightarrow}$		${\ displaystyle \ uparrow}$		${\ displaystyle \ Leftrightarrow}$		${\ displaystyle \ uparrow}$

${\ displaystyle P \ leftrightarrow Q}$	${\ displaystyle \ Leftrightarrow}$	${\ displaystyle (P \ uparrow Q)}$	${\ displaystyle \ uparrow}$	${\ displaystyle ((P \ uparrow P) \ uparrow (Q \ uparrow Q))}$
	${\ displaystyle \ Leftrightarrow}$		${\ displaystyle \ uparrow}$

${\ displaystyle P \ land Q}$	${\ displaystyle \ Leftrightarrow}$	${\ displaystyle (P \ uparrow Q)}$	${\ displaystyle \ uparrow}$	${\ displaystyle (P \ uparrow Q)}$
	${\ displaystyle \ Leftrightarrow}$		${\ displaystyle \ uparrow}$

${\ displaystyle P \ lor Q}$	${\ displaystyle \ Leftrightarrow}$	${\ displaystyle (P \ uparrow P)}$	${\ displaystyle \ uparrow}$	${\ displaystyle (Q \ uparrow Q)}$
	${\ displaystyle \ Leftrightarrow}$		${\ displaystyle \ uparrow}$

Sistema formal baseado no AVC Sheffer

A seguir está um exemplo de um sistema formal baseado inteiramente no traço de Sheffer, mas tendo a expressividade funcional da lógica proposicional :

Símbolos

p _n para números naturais n :

(|)

O traço de Sheffer comuta, mas não se associa (por exemplo, $(T | T) | F = T$ , mas $T | (T | F) = F$ ). Portanto, qualquer sistema formal que inclua o traço de Sheffer como um símbolo infixo também deve incluir um meio de indicar agrupamento (o agrupamento é automático se o traço for usado como um prefixo, assim: $|| TTF = T$ e $| T | TF = F$ ). Devemos empregar '(' e ')' para esse efeito.

Também escrevemos p , q , r , ... em vez de p ₀ , p ₁ , p ₂ .

Sintaxe

Regra de construção I: Para cada número natural n , o símbolo p _n é uma fórmula bem formada (wff), chamada de átomo.

Regra de construção II: Se X e Y são wffs, então ( X | Y ) é um wff.

Regra de Fechamento: Quaisquer fórmulas que não podem ser construídas por meio das duas primeiras Regras de Construção não são wffs.

As letras U , V , W , X e Y são metavariáveis que representam wffs.

Um procedimento de decisão para determinar se uma fórmula está bem formada é o seguinte: "desconstrua" a fórmula aplicando as Regras de construção ao contrário, quebrando assim a fórmula em subfórmulas menores. Em seguida, repita esse processo de desconstrução recursiva para cada uma das subfórmulas. Eventualmente, a fórmula deve ser reduzida a seus átomos, mas se alguma subfórmula não puder ser reduzida, então a fórmula não é uma wff.

Cálculo

Todas as wffs do formulário

((U | (V | W)) | ((Y | (Y | Y)) | ((X | V) | ((U | X) | (U | X)))))

são axiomas. Instâncias de

{\ displaystyle (U | (V | W)), U \ vdash W}

são regras de inferência.

Simplificação

Como o único conectivo dessa lógica é |, o símbolo | poderia ser totalmente descartado, deixando apenas os parênteses para agrupar as letras. Um par de parênteses deve sempre incluir um par de wff s. Exemplos de teoremas nesta notação simplificada são

( p ( p ( q ( q (( pq ) ( pq )))))),

( p ( p (( qq ) ( pp )))).

A notação pode ser simplificada ainda mais, permitindo

(U): = (UU)

{\ displaystyle ((U)) \ equiv U}

para qualquer U . Esta simplificação faz com que seja necessário alterar algumas regras:

Mais de duas letras são permitidas entre parênteses.
Letras ou wffs entre parênteses podem comutar.
Letras repetidas ou wffs dentro de um mesmo conjunto de parênteses podem ser eliminados.

O resultado é uma versão entre parênteses dos grafos existenciais de Peirce .

Outra maneira de simplificar a notação é eliminar parênteses usando a notação polonesa . Por exemplo, os exemplos anteriores com apenas parênteses podem ser reescritos usando apenas traços como segue

( p ( p ( q ( q (( pq ) ( pq )))))) torna-se

| p | p | q | q || pq | pq

, e

( p ( p (( qq ) ( pp )))) torna-se,

| p | p || qq | pp

.

Isso segue as mesmas regras da versão entre parênteses, com o parêntese de abertura substituído por um traço de Sheffer e o parêntese de fechamento (redundante) removido.

Ou (para algumas fórmulas) pode-se omitir parênteses e traços e permitir que a ordem dos argumentos determine a ordem de aplicação da função de modo que, por exemplo, aplicando a função da direita para a esquerda (notação polonesa reversa - qualquer outra convenção inequívoca baseada em pedir faria)

{\ displaystyle {\ begin {alinhados} & pqr \ equiv (p \ mid (q \ mid r)), {\ text {considerando}} \\ & rqp \ equiv (r \ mid (q \ mid p)). \ end {alinhado}}}

Veja também

Notas

Referências

Bocheński, Józef Maria (1960), Precis of Mathematical Logic , rev., Albert Menne, editado e traduzido das edições francesa e alemã por Otto Bird, Dordrecht , South Holland : D. Reidel .
Church, Alonzo (1956). Introdução à lógica matemática. Volume 1 . Princeton University Press .
Nicod, Jean GP (1917). "Uma redução no número de proposições primitivas da lógica". Proceedings of the Cambridge Philosophical Society . 19 : 32–41.
Charles Sanders Peirce , 1880, "A Boolian [sic] Algebra with One Constant", em Hartshorne, C. e Weiss, P. , eds., (1931–35) Collected Papers of Charles Sanders Peirce , Vol. 4 : 12-20, Cambridge : Harvard University Press .
Sheffer, HM (1913), "Um conjunto de cinco postulados independentes para álgebras booleanas, com aplicação a constantes lógicas", Transactions of the American Mathematical Society , 14 : 481-488, doi : 10.2307 / 1988701 , JSTOR 1988701

Languages

In other projects