Golpe de sheffer

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 dice en efecto 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 se escribe como ↑ o como | (pero no como ||, a menudo usado para representar la disyunción). En notación Bocheński se puede escribir como Dpq.

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.

Tabla de verdad

La tabla de la verdad P↑ ↑ Q{displaystyle Puparrow Q} (también escrito como PSilencio⁡ ⁡ Q{displaystyle Pmathop ¿Qué?, o Dpq) es como sigue

P{displaystyle P}	Q{displaystyle Q}	P↑ ↑ Q{displaystyle Puparrow Q}
Cierto.	Cierto.	Falso
Cierto.	Falso	Cierto.
Falso	Cierto.	Cierto.
Falso	Falso	Cierto.

Equivalencias lógicas

El derrame de Sheffer P{displaystyle P} y Q{displaystyle Q} es la negación de su conjunción

P↑ ↑ Q{displaystyle Puparrow Q}	.. {displaystyle Leftrightarrow	¬ ¬ ()P∧ ∧ Q){displaystyle neg (Pland Q)}
	.. {displaystyle Leftrightarrow	¬ ¬ {displaystyle neg }

Por las leyes de De Morgan, esto es también equivalente a la disyunción de las negaciones de P{displaystyle P} y Q{displaystyle Q}

P↑ ↑ Q{displaystyle Puparrow Q}	.. {displaystyle Leftrightarrow	¬ ¬ P{displaystyle neg P}	Alternativa Alternativa {displaystyle lor }	¬ ¬ Q{displaystyle neg Q}
	.. {displaystyle Leftrightarrow		Alternativa Alternativa {displaystyle lor }

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 las álgebras booleanas utilizando el trazo, y demostró su equivalencia con un formulación estándar del mismo por Huntington empleando los operadores familiares de la lógica proposicional (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 1927 de Principia Mathematica y lo sugirieron como reemplazo del "o" y "no" operaciones 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 ellas es suficiente para, al menos un miembro de un conjunto de operadores funcionalmente completos: preservación de la verdad, falsedad-preservación, linealidad, monotonicidad, auto-dualidad. (Un operador conserva la verdad (falsedad) 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 {AND, OR, NOT} 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 ↑ ↑ {displaystyle uparrow }, los operadores habituales de la lógica proposicional son:

¬ ¬ P{displaystyle neg P} .. {displaystyle Leftrightarrow P{displaystyle P} ↑ ↑ {displaystyle uparrow } P{displaystyle P} .. {displaystyle Leftrightarrow ↑ ↑ {displaystyle uparrow }		P→ → Q{displaystyle Prightarrow Q} .. {displaystyle Leftrightarrow P{displaystyle ~P} ↑ ↑ {displaystyle uparrow } ()Q↑ ↑ Q){displaystyle (Quparrow Q)} .. {displaystyle Leftrightarrow P{displaystyle ~P} ↑ ↑ {displaystyle uparrow } ()P↑ ↑ Q){displaystyle (Puparrow Q)} .. {displaystyle Leftrightarrow ↑ ↑ {displaystyle uparrow } .. {displaystyle Leftrightarrow ↑ ↑ {displaystyle uparrow }		PAdministración Administración Q{displaystyle Pleftrightarrow Q} .. {displaystyle Leftrightarrow ()P↑ ↑ Q){displaystyle (Puparrow Q)} ↑ ↑ {displaystyle uparrow } ()()P↑ ↑ P)↑ ↑ ()Q↑ ↑ Q)){displaystyle (Puparrow P)uparrow (Quparrow Q)} .. {displaystyle Leftrightarrow ↑ ↑ {displaystyle uparrow }
P∧ ∧ Q{displaystyle Pland Q} .. {displaystyle Leftrightarrow ()P↑ ↑ Q){displaystyle (Puparrow Q)} ↑ ↑ {displaystyle uparrow } ()P↑ ↑ Q){displaystyle (Puparrow Q)} .. {displaystyle Leftrightarrow ↑ ↑ {displaystyle uparrow }		PAlternativa Alternativa Q{displaystyle Plor Q} .. {displaystyle Leftrightarrow ()P↑ ↑ P){displaystyle (Puparrow P)} ↑ ↑ {displaystyle uparrow } ()Q↑ ↑ Q){displaystyle (Quparrow Q)} .. {displaystyle Leftrightarrow ↑ ↑ {displaystyle uparrow }

Sistema formal basado en el trazo de Sheffer

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

Símbolos

p_n para números naturales n:

(en inglés)

El trazo de Sheffer conmuta pero no se asocia (p. ej., (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 la agrupación (la agrupación es automática si el trazo se usa como prefijo, por lo tanto: || TTF = T y | T | TF = F). Emplearemos '(' y ')' para este efecto.

También escribimos p, q, r, … en lugar de p₀, p₁, p₂.

Sintaxis

Regla de construcción I: Para cada número natural n, el símbolo p_n es un bien formado fórmula (wff), llamado átomo.

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

Regla de cierre: Las fórmulas que no se pueden construir mediante las dos primeras reglas de construcción no son wffs.

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

Un procedimiento de decisión para determinar si una fórmula está bien formada es el siguiente: "deconstruir" 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 debe reducirse a sus átomos, pero si alguna subfórmula no puede reducirse así, entonces la fórmula no es un wff.

Cálculo

Todos los wffs del formulario

()U SilencioV Silencio W) Silencio (Y SilencioY Silencio Y) Silencio (X Silencio VSilencio.U Silencio XSilencio.U Silencio X))))

son axiomas. Instancias de

()USilencio()VSilencioW)),U⊢ ⊢ W{displaystyle (U sobreviviente)),Uvdash W}

son reglas de inferencia.

Simplificación

Dado que el único conectivo 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 encerrar un par de wffs. 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)

()()U))↑ ↑ U{displaystyle (U)equiv U}

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

1. Se permiten más de dos cartas dentro de los paréntesis.
2. Se permite que las cartas o las fosas dentro de los paréntesis se comuniquen.
3. Se pueden eliminar las cartas repetidas o wffs dentro de un mismo conjunto de 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 usando 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

Silencio p Silencio p Silencio q Silencio q Silencio pq Silencio pq, y

()p()p()qq)pp)) se convierte,

Silencio p Silencio p Silencio qq Silencio pp.

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) uno podría omitir los trazos de paréntesis y 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 el orden sería suficiente)

pqr↑ ↑ ()p▪ ▪ ()q▪ ▪ r)),mientras querqp↑ ↑ ()r▪ ▪ ()q▪ ▪ p)).{displaystyle {begin{aligned} {pqrequiv (pmid (qmid r)),{text{ whereas}}\\\cH00equiv (rmid (qmid p)).end{aligned}}}}}}}