Trazo de Sheffer - Sheffer stroke

Trazo de sheffer
NAND
Diagrama de Venn del trazo de Sheffer
Definición
Mesa de la verdad
Puerta lógica NAND ANSI.svg
Formas normales
Disyuntivo
Conjuntivo
Polinomio de Zhegalkin
Celosías de correos
0-conservando no
1-conservando no
Monótono no
Afín no

En funciones booleanas y cálculo proposicional , el trazo de Sheffer denota una operación lógica que es equivalente a la negación de la operación de conjunción , expresada en lenguaje ordinario como "no ambos". También se le llama nand ("no y") o la negación alternativa , ya que en efecto dice que al menos uno de sus operandos es falso. En electrónica digital , corresponde a la puerta NAND . Lleva el nombre de Henry M. Sheffer y está escrito como ↑ o como | (pero no como ||, a menudo utilizado para representar la disyunción ). En la notación de Bocheński se puede escribir como D pq .

Su dual es el operador NOR (también conocido como la flecha de Peirce o la daga de Quine ). Al igual que su dual, NAND puede usarse por sí mismo, sin ningún otro operador lógico, para constituir un sistema lógico formal (haciendo que NAND sea funcionalmente completo ). Esta propiedad hace que la puerta NAND sea crucial para la electrónica digital moderna , incluido su uso en el diseño de procesadores de computadora .

Definición

La operación NAND es una operación lógica en dos valores lógicos . Produce un valor de verdadero, si - y solo si - al menos una de las proposiciones es falsa.

Mesa de la verdad

La tabla de verdad de (también escrita como , o D pq ) es la siguiente

T
T
F
T
F
T
F
T
T
F
F
T

Equivalencias lógicas

El trazo de Sheffer de y es la negación de su conjunción

    
Venn1110.svg      Venn0001.svg

Según las leyes de De Morgan , esto también equivale a la disyunción de las negaciones de y

    
Venn1110.svg      Venn1010.svg Venn1100.svg

Historia

El trazo lleva el nombre de Henry M. Sheffer , quien en 1913 publicó un artículo en Transactions of the American Mathematical Society proporcionando una axiomatización de álgebras booleanas usando el trazo, y demostró su equivalencia con una formulación estándar del mismo por Huntington empleando los conocidos operadores de la lógica de proposiciones ( y , o , no ). Debido a la autodualidad de las álgebras booleanas, los axiomas de Sheffer son igualmente válidos para las operaciones NAND o NOR en lugar del trazo. Sheffer interpretó el trazo como un signo de no disyunción ( NOR ) en su artículo, mencionando la no conjunción solo en una nota al pie y sin un signo especial para ello. Fue Jean Nicod quien utilizó por primera vez el trazo como signo de no conjunción (NAND) en un artículo de 1917 y que desde entonces se ha convertido en una práctica corriente. Russell y Whitehead utilizaron el trazo de Sheffer en la segunda edición de Principia Mathematica de 1927 y lo sugirieron como reemplazo de las operaciones "o" y "no" de la primera edición.

Charles Sanders Peirce (1880) había descubierto la integridad funcional de NAND o NOR más de 30 años antes, utilizando el término ampheck (para "cortar en ambos sentidos"), pero nunca publicó su hallazgo.

Propiedades

NAND no posee ninguna de las siguientes cinco propiedades, cada una de las cuales debe estar ausente y la ausencia de todas es suficiente para al menos un miembro de un conjunto de operadores funcionalmente completos : verdad-preservación, falsedad- preservación, linealidad , monotonicidad , auto-dualidad . (Un operador es verdad- (falsedad-) preservando si su valor es verdad (falsedad) siempre que todos sus argumentos sean verdad (falsedad).) Por lo tanto, {NAND} es un conjunto funcionalmente completo.

Esto también se puede realizar de la siguiente manera: Los tres elementos del conjunto funcionalmente completo {Y, O, NO} se pueden construir usando solo NAND . Por tanto, el conjunto {NAND} también debe ser funcionalmente completo.

Otras operaciones booleanas en términos del trazo de Sheffer

Expresado en términos de NAND , los operadores habituales de la lógica proposicional son:

        
Venn10.svg          Venn01.svg Venn01.svg
   
                 
Venn1011.svg          Venn0101.svg Venn1100.svg          Venn0101.svg Venn1110.svg
   
        
Venn1001.svg          Venn1110.svg Venn0111.svg
 
        
Venn0001.svg          Venn1110.svg Venn1110.svg
   
        
Venn0111.svg          Venn1010.svg Venn1100.svg

Sistema formal basado en el trazo de Sheffer

El siguiente es un ejemplo de un sistema formal basado enteramente en el trazo de Sheffer, pero que tiene la expresividad funcional de la lógica proposicional :

Simbolos

p n para números naturales n :

(|)

El trazo de Sheffer conmuta pero no se asocia (por ejemplo, (T | T) | F = T , pero T | (T | F) = F ). Por lo tanto, cualquier sistema formal que incluya el trazo de Sheffer como símbolo infijo también debe incluir un medio para indicar agrupamiento (el agrupamiento es automático si el trazo se usa como prefijo, por lo tanto: || TTF = T y | T | TF = F ). Emplearemos '(' y ')' a este efecto.

También escribimos p , q , r ,… en lugar de p 0 , p 1 , p 2 .

Sintaxis

Regla de construcción I: para cada número natural n , el símbolo p n es una fórmula bien formada (wff), llamada átomo.

Regla de construcción II: Si X e Y son wff, entonces ( X  |  Y ) es un wff.

Regla de cierre: Cualquier fórmula que no se pueda construir por medio de las dos primeras Reglas de construcción no es wffs.

Las letras U , V , W , X e Y son metavariables que representan wffs.

Un procedimiento de decisión para determinar si una fórmula está bien formada es el siguiente: "deconstruye" la fórmula aplicando las Reglas de construcción al revés, dividiendo así la fórmula en subfórmulas más pequeñas. Luego repita este proceso de deconstrucción recursivo para cada una de las subfórmulas. Eventualmente, la fórmula debería reducirse a sus átomos, pero si alguna subfórmula no puede reducirse así, entonces la fórmula no es una fbf.

Cálculo

Todas las wffs de la forma

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

son axiomas. Instancias de

son reglas de inferencia.

Simplificación

Dado que la única conectiva de esta lógica es |, el símbolo | podría descartarse por completo, dejando solo los paréntesis para agrupar las letras. Un par de paréntesis siempre debe incluir un par de wff . Ejemplos de teoremas en esta notación simplificada son

( p ( p ( q ( q (( pq ) ( pq )))))),
( p ( p (( qq ) ( pp )))).

La notación se puede simplificar aún más, dejando

( U ): = ( UU )

para cualquier T . Esta simplificación provoca la necesidad de cambiar algunas reglas:

  1. Se permiten más de dos letras entre paréntesis.
  2. Las letras o wffs entre paréntesis pueden conmutar.
  3. Se pueden eliminar las letras repetidas o wffs dentro de un mismo paréntesis.

El resultado es una versión entre paréntesis de los gráficos existenciales de Peirce .

Otra forma de simplificar la notación es eliminar los paréntesis utilizando la notación polaca . Por ejemplo, los ejemplos anteriores con solo paréntesis podrían reescribirse usando solo trazos de la siguiente manera

( p ( p ( q ( q (( pq ) ( pq )))))) se convierte en
| p | p | q | q || pq | pq , y
( p ( p (( qq ) ( pp )))) se convierte en,
| p | p || qq | págs .

Esto sigue las mismas reglas que la versión de paréntesis, con el paréntesis de apertura reemplazado por un trazo de Sheffer y el paréntesis de cierre (redundante) eliminado.

O (para algunas fórmulas) se pueden omitir tanto los paréntesis como los trazos y permitir que el orden de los argumentos determine el orden de aplicación de la función de modo que, por ejemplo, aplicar la función de derecha a izquierda (notación polaca inversa - cualquier otra convención inequívoca basada en ordenar haría)

Ver también

Notas

Referencias

  • Bocheński, Józef Maria (1960), Precis of Mathematical Logic , rev., Albert Menne, editado y traducido de las ediciones francesa y alemana por Otto Bird, Dordrecht , South Holland : D. Reidel .
  • Iglesia, Alonzo (1956). Introducción a la lógica matemática. Volumen 1 . Prensa de la Universidad de Princeton .
  • Nicod, Jean GP (1917). "Una reducción en el número de proposiciones primitivas de la lógica". Actas de la Sociedad Filosófica de Cambridge . 19 : 32–41.
  • Charles Sanders Peirce , 1880, "Un álgebra booliana [sic] con una constante", en Hartshorne, C. y Weiss, P. , eds., (1931–35) Documentos recopilados de Charles Sanders Peirce , vol. 4 : 12-20, Cambridge : Harvard University Press .
  • Sheffer, HM (1913), "Un conjunto de cinco postulados independientes para álgebras booleanas, con aplicación a constantes lógicas", Transactions of the American Mathematical Society , 14 : 481–488, doi : 10.2307 / 1988701 , JSTOR  1988701

enlaces externos