Fórmula proposicional

En lógica proposicional , una fórmula proposicional es un tipo de fórmula sintáctica bien formada . Si se conocen los valores de todas las variables en una fórmula proposicional, esta determina un único ^valor de verdad . Una fórmula proposicional también puede denominarse expresión proposicional , oración [ ^{1 ]} o fórmula sentencial .

Una fórmula proposicional se construye a partir de proposiciones simples , como "cinco es mayor que tres" o variables proposicionales como p y q , utilizando conectores u operadores lógicos como NOT, AND, OR o IMPLIES; por ejemplo:

( p Y NO q ) IMPLICA ( p O q ).

En matemáticas , una fórmula proposicional suele denominarse simplemente " proposición ", pero, más precisamente, una fórmula proposicional no es una proposición, sino una expresión formal que denota una proposición , un objeto formal en discusión, del mismo modo que una expresión como " x + y " no es un valor, sino que denota un valor. En algunos contextos, mantener esta distinción puede ser importante.

Proposiciones

Para los fines del cálculo proposicional, las proposiciones (enunciados, oraciones, afirmaciones) se consideran simples o compuestas. ^{[ 2 ]} Las proposiciones compuestas se consideran vinculadas por conectores oracionales, algunos de los más comunes son "Y", "O", "SI... ENTONCES...", "NI... NI...", "...ES EQUIVALENTE A...". El punto y coma ";" y el conector "PERO" se consideran expresiones de "Y". Una secuencia de oraciones discretas se considera vinculada por "Y", y el análisis formal aplica una "regla de paréntesis" recursiva con respecto a secuencias de proposiciones simples (véase más abajo sobre fórmulas bien formadas).

Por ejemplo: La afirmación: "Esta vaca es azul. Ese caballo es naranja, pero este caballo de aquí es morado." es en realidad una proposición compuesta vinculada por "Y": ( ("Esta vaca es azul" Y "ese caballo es naranja") Y "este caballo de aquí es morado") .

Las proposiciones simples son declarativas por naturaleza, es decir, hacen afirmaciones sobre la condición o naturaleza de un objeto de sensación particular , por ejemplo, "Esta vaca es azul", "¡Hay un coyote!" ("Ese coyote ESTÁ ahí , detrás de las rocas."). ^{[ 3 ]} Por lo tanto, las afirmaciones simples "primitivas" deben referirse a objetos específicos o estados mentales específicos. Cada una debe tener al menos un sujeto (un objeto inmediato de pensamiento u observación), un verbo (preferiblemente en voz activa y presente) y quizás un adjetivo o adverbio. "¡Perro!" probablemente implica "Veo un perro", pero debe rechazarse por ser demasiado ambiguo.

Ejemplo: "Ese perro morado está corriendo", "Esta vaca es azul", "El interruptor M31 está cerrado", "Esta tapa está quitada", "Mañana es viernes".

A efectos del cálculo proposicional, una proposición compuesta generalmente se puede reformular en una serie de oraciones simples, aunque el resultado probablemente suene forzado.

Relación entre fórmulas proposicionales y de predicados

El cálculo de predicados va un paso más allá que el cálculo proposicional hacia un "análisis de la estructura interna de las proposiciones" ^{[ 4 ].} Descompone una oración simple en dos partes: (i) su sujeto (el objeto ( singular o plural) del discurso) y (ii) un predicado (un verbo o posiblemente una cláusula verbal que afirma una cualidad o atributo del/de los objeto(s)). El cálculo de predicados luego generaliza la forma "sujeto|predicado" (donde | simboliza la concatenación (unión) de símbolos) en una forma con la siguiente estructura de sujeto en blanco " ___|predicado", y el predicado a su vez generalizado a todas las cosas con esa propiedad.

Ejemplo: "Este cerdo azul tiene alas" se convierte en dos oraciones en el cálculo proposicional : "Este cerdo tiene alas" Y "Este cerdo es azul", cuya estructura interna no se considera. En cambio, en el cálculo de predicados, la primera oración se divide en "este cerdo" como sujeto y "tiene alas" como predicado. Así, afirma que el objeto "este cerdo" pertenece a la clase (conjunto, colección) de "cosas aladas". La segunda oración afirma que el objeto "este cerdo" tiene el atributo "azul" y, por lo tanto, pertenece a la clase de "cosas azules". Se podría optar por escribir las dos oraciones conectadas con Y como:

p|W Y p|B

La generalización de "este cerdo" a un miembro (potencial) de dos clases, "cosas aladas" y "cosas azules", significa que tiene una relación de verdad con ambas clases. En otras palabras, dado un dominio de discurso "cosas aladas", se determina que p es miembro de este dominio o no lo es. Por lo tanto, existe una relación W (alaridad) entre p (cerdo) y { V, F }, W(p) se evalúa como { V, F } donde { V, F } es el conjunto de los valores booleanos "verdadero" y "falso". De igual modo para B (azulidad) y p (cerdo) y { V, F }: B(p) se evalúa como { V, F }. Así, ahora se pueden analizar las afirmaciones conectadas "B(p) Y W(p)" para su valor de verdad global, es decir:

( B(p) Y W(p) ) se evalúa como { V, F }

En particular, las oraciones simples que emplean las nociones de "todos", "algunos", "unos pocos", "uno de", etc., denominadas cuantificadores lógicos, son tratadas por el cálculo de predicados. Junto con el nuevo simbolismo de función "F(x)", se introducen dos nuevos símbolos: ∀ (Para todo) y ∃ (Existe ..., Existe al menos uno de ..., etc.). El cálculo de predicados, pero no el cálculo proposicional, puede establecer la validez formal de la siguiente afirmación:

"Todos los cerdos azules tienen alas, pero algunos cerdos no tienen alas; por lo tanto, algunos cerdos no son azules".

Identidad

Tarski afirma que la noción de IDENTIDAD (a diferencia de la EQUIVALENCIA LÓGICA) se encuentra fuera del cálculo proposicional; sin embargo, señala que para que una lógica sea útil para las matemáticas y las ciencias, debe contener una «teoría» de la IDENTIDAD. ^{[ 5 ]} Algunos autores se refieren a la «lógica de predicados con identidad» para enfatizar esta extensión. Véase más adelante.

Un álgebra de proposiciones, el cálculo proposicional

Un álgebra (y existen muchas diferentes), definida de forma general, es un método mediante el cual se manipula un conjunto de símbolos llamados variables, junto con otros símbolos como paréntesis (, ) y un subconjunto de símbolos como *, +, ~, &, ∨ , =, ≡, ∧ , ￢, dentro de un sistema de reglas. Se dice que estos símbolos, y las secuencias bien formadas de ellos, representan objetos, pero en un sistema algebraico específico estos objetos no tienen significado. Por lo tanto, el trabajo dentro del álgebra se convierte en un ejercicio de obediencia a ciertas leyes (reglas) de la sintaxis del álgebra (formación de símbolos) en lugar de en la semántica (significado) de los símbolos. Los significados se encuentran fuera del álgebra.

Para que una secuencia bien formada de símbolos en el álgebra —una fórmula— tenga alguna utilidad fuera del álgebra, a los símbolos se les asignan significados y, finalmente, a las variables se les asignan valores; luego, mediante una serie de reglas, se evalúa la fórmula.

Cuando los valores se restringen a solo dos y se aplican a la noción de oraciones simples (por ejemplo, enunciados orales o afirmaciones escritas) vinculadas por conectores proposicionales, todo este sistema algebraico de símbolos, reglas y métodos de evaluación se denomina habitualmente cálculo proposicional o cálculo sentencial.

Si bien algunas de las reglas familiares del álgebra aritmética siguen siendo válidas en el álgebra de proposiciones (por ejemplo, las leyes conmutativa y asociativa para AND y OR), otras no lo son (por ejemplo, las leyes distributivas para AND, OR y NOT).

Utilidad de las fórmulas proposicionales

Análisis: En el razonamiento deductivo , los filósofos, retóricos y matemáticos reducen los argumentos a fórmulas y luego las estudian (generalmente con tablas de verdad ) para comprobar su corrección (solidez). Por ejemplo: ¿Es sólido el siguiente argumento?

"Dado que la consciencia es suficiente para una inteligencia artificial y que solo las entidades conscientes pueden superar la prueba de Turing , antes de que podamos concluir que un robot es una inteligencia artificial, el robot debe superar la prueba de Turing."

Los ingenieros analizan los circuitos lógicos que han diseñado utilizando técnicas de síntesis y luego aplican diversas técnicas de reducción y minimización para simplificar sus diseños.

Síntesis: Los ingenieros, en particular, sintetizan fórmulas proposicionales (que eventualmente terminan siendo circuitos de símbolos) a partir de tablas de verdad . Por ejemplo, se podría escribir una tabla de verdad sobre cómo debería comportarse la suma binaria dada la suma de las variables "b" y "a" y "carry_in" "ci", y los resultados "carry_out" "co" y "sum" Σ:

Ejemplo: en la fila 5, ( (b+a) + ci ) = ( (1+0) + 1 ) = el número "2". Escrito como un número binario, esto es 10 ₂ , donde "co"=1 y Σ=0 como se muestra en las columnas más a la derecha.

Variables proposicionales

El tipo más simple de fórmula proposicional es una variable proposicional . Las proposiciones que son expresiones simbólicas simples ( atómicas ) a menudo se denotan mediante variables llamadas p , q , o P , Q , etc. Una variable proposicional está destinada a representar una proposición atómica (afirmación), como "Es sábado" = p (aquí el símbolo = significa "... se asigna la variable llamada ...") o "Solo voy al cine los lunes" = q .

Asignaciones de valores de verdad, evaluaciones de fórmulas

La evaluación de una fórmula proposicional comienza con la asignación de un valor de verdad a cada variable. Dado que cada variable representa una oración simple, los valores de verdad se aplican a la "verdad" o "falsedad" de dichas oraciones.

Valores de verdad en retórica, filosofía y matemáticas.

Los valores de verdad son solo dos: { VERDAD "V", FALSEDAD "F" }. Un empirista coloca todas las proposiciones en dos clases amplias: analíticas —verdaderas pase lo que pase (p. ej., tautología ), y sintéticas —derivadas de la experiencia y, por lo tanto, susceptibles de confirmación por terceros (la teoría de verificación del significado). ^{[ 6 ]} Los empiristas sostienen que, en general, para llegar al valor de verdad de una proposición sintética , primero se deben aplicar significados (plantillas de coincidencia de patrones) a las palabras, y luego estas plantillas de significado deben compararse con lo que sea que se esté afirmando. Por ejemplo, mi enunciado "¡Esa vaca es azul !" ¿Es esta afirmación una VERDAD? Ciertamente lo dije. Y tal vez estoy viendo una vaca azul; a menos que esté mintiendo, mi afirmación es una VERDAD relativa al objeto de mi percepción (quizás defectuosa). Pero, ¿está la vaca azul "realmente ahí"? ¿Qué ves cuando miras por la misma ventana? Para proceder con la verificación, necesitará una noción previa (una plantilla) tanto de "vaca" como de " azul ", y la capacidad de hacer coincidir las plantillas con el objeto de la sensación (si es que existe alguno).

Valores de verdad en ingeniería

Los ingenieros intentan evitar las nociones de verdad y falsedad que atormentan a los filósofos, pero en última instancia deben confiar en sus instrumentos de medición. En su búsqueda de robustez , prefieren extraer objetos conocidos de una pequeña biblioteca: objetos con comportamientos bien definidos y predecibles incluso en grandes combinaciones (de ahí el nombre del cálculo proposicional: "lógica combinatoria"). El mínimo de comportamientos de un solo objeto es dos (por ejemplo, {APAGADO, ENCENDIDO}, {abierto, cerrado}, {ARRIBA, ABAJO}, etc.), y estos se corresponden con {0, 1}. Dichos elementos se denominan digitales ; aquellos con un rango continuo de comportamientos se denominan analógicos . Cuando se deben tomar decisiones en un sistema analógico, a menudo un ingeniero convierte un comportamiento analógico (la puerta está 45,32146% ARRIBA) a digital (por ejemplo, ABAJO=0) mediante un comparador . ^{[ 7 ]}

Así, la asignación de significado a las variables y a los dos símbolos de valor {0, 1} proviene de fuera de la fórmula que representa el comportamiento del objeto (generalmente) compuesto. Un ejemplo es una puerta de garaje con dos interruptores de límite, uno para subir (SW_U) y otro para bajar (SW_D), y cualquier otro componente del circuito de la puerta. La inspección del circuito (ya sea el diagrama o los objetos mismos: puerta, interruptores, cables, placa de circuito, etc.) podría revelar que, en la placa de circuito, el nodo 22 alcanza los +0 voltios cuando los contactos del interruptor SW_D están en contacto mecánico ("cerrados") y la puerta está en la posición "abajo" (95% abajo), y el nodo 29 alcanza los +0 voltios cuando la puerta está al 95% arriba y los contactos del interruptor SW_U están en contacto mecánico ("cerrados"). ^{[ 8 ]} El ingeniero debe definir el significado de estos voltajes y todas las combinaciones posibles (las 4), incluidas las "malas" (por ejemplo, los nodos 22 y 29 a 0 voltios, lo que significa que la puerta está abierta y cerrada al mismo tiempo). El circuito responde sin criterio a cualquier voltaje que experimente, sin ninguna conciencia de VERDAD o FALSEDAD, CORRECTO o INCORRECTO, SEGURO o PELIGROSO.

Conectores proposicionales

Las fórmulas proposicionales arbitrarias se construyen a partir de variables proposicionales y otras fórmulas proposicionales utilizando conectores proposicionales . Algunos ejemplos de conectores son:

El conector de negación unaria. Si $\alpha$ es una fórmula, entonces $\lnot \alpha$ es una fórmula.
Los conectores binarios clásicos $\land ,\lor ,\to ,\leftrightarrow$ . Por lo tanto, por ejemplo, si $\alpha$ y $\beta$ son fórmulas, así que es $(\alpha \to \beta )$ .
Otros conectores binarios, como NAND, NOR y XOR.
El conector ternario SI ... ENTONCES ... SI NO ...
Conectivas 0-arias constantes ⊤ y ⊥ (alternativamente, constantes { T, F }, { 1, 0 } etc. )
El conector de "extensión de teoría" ES IGUAL (alternativamente, IDENTIDAD, o el signo " = " como se distingue del "conector lógico" $\leftrightarrow$ )

Conectores de retórica, filosofía y matemáticas

A continuación se presentan los conectores comunes a la retórica, la filosofía y las matemáticas, junto con sus tablas de verdad . Los símbolos utilizados varían según el autor y el campo de estudio. En general, las abreviaturas "V" y "F" representan las evaluaciones VERDAD y FALSEDAD aplicadas a las variables en la fórmula proposicional (por ejemplo, la afirmación: "Esa vaca es azul" tendrá el valor de verdad "V" para Verdad o "F" para False, según corresponda).

Los conectores se expresan mediante diferentes usos de las palabras; por ejemplo, "a IMPLICA b" también se dice "SI a ENTONCES b". Algunos ejemplos se muestran en la tabla.

Conectores de ingeniería

En general, los conectores de ingeniería son iguales a los de matemáticas, salvo que tienden a evaluarse con "1" = "V" y "0" = "F". Esto se hace para el análisis, la minimización y la síntesis de fórmulas mediante el uso de la noción de minitérminos y mapas de Karnaugh (véase más adelante). Los ingenieros también utilizan los términos producto lógico, del concepto de Boole (a*a = a), y suma lógica, del concepto de Jevons (a+a = a). ^{[ 9 ]}

Conectividad CASE: SI ... ENTONCES ... SINO ...

La conectiva IF ... THEN ... ELSE ... aparece como la forma más simple del operador CASE en la teoría de la recursión y la teoría de la computación, y es la responsable de las instrucciones goto condicionales (saltos, bifurcaciones). A partir de esta conectiva se pueden construir todas las demás (véase más abajo). Aunque "IF c THEN b ELSE a" suena como una implicación, en su forma más reducida es una instrucción switch que toma una decisión y ofrece como resultado solo una de dos alternativas: "a" o "b" (de ahí el nombre de instrucción switch en el lenguaje de programación C ). ^{[ 10 ]}

Las siguientes tres proposiciones son equivalentes (como lo indica el signo de equivalencia lógica ≡):

( SI 'el contador es cero' ENTONCES 'ir a la instrucción b ' SINO 'ir a la instrucción a ') ≡
( (c → b) & (~c → a) ) ≡ ( ( SI 'el contador es cero' ENTONCES 'ir a la instrucción b ' ) Y ( SI 'NO es el caso que el contador sea cero' ENTONCES 'ir a la instrucción a ) " ≡
( (c & b) ∨ (~c & a) ) ≡ " ( 'El contador es cero' Y 'ir a la instrucción b ) O ( 'NO es el caso que 'el contador sea cero' Y 'ir a la instrucción a ) "

Por lo tanto, IF ... THEN ... ELSE —a diferencia de la implicación— no se evalúa como una "VERDAD" ambigua cuando la primera proposición es falsa, es decir, c = F en (c → b). Por ejemplo, la mayoría de las personas rechazarían la siguiente proposición compuesta como un non sequitur sin sentido porque la segunda oración no está conectada en significado con la primera. ^{[ 11 ]}

Ejemplo: La proposición " SI 'Winston Churchill era chino' ENTONCES 'El sol sale por el este' " se evalúa como una VERDAD dado que 'Winston Churchill era chino' es una FALSEDAD y 'El sol sale por el este' se evalúa como una VERDAD.

En reconocimiento de este problema, el signo → de implicación formal en el cálculo proposicional se denomina implicación material para distinguirlo de la implicación cotidiana e intuitiva. ^{[ a ]}

El uso de la construcción IF ... THEN ... ELSE evita controversia porque ofrece una elección completamente determinista entre dos alternativas declaradas; ofrece dos "objetos" (las dos alternativas b y a), y selecciona entre ellas de manera exhaustiva y sin ambigüedad. ^{[ 13 ]} En la tabla de verdad a continuación, d1 es la fórmula: ( (IF c THEN b) AND (IF NOT-c THEN a) ). Su forma totalmente reducida d2 es la fórmula: ( (c AND b) OR (NOT-c AND a). Las dos fórmulas son equivalentes como se muestra en las columnas "=d1" y "=d2". Los ingenieros eléctricos llaman a la fórmula totalmente reducida el operador AND-OR-SELECT. El operador CASE (o SWITCH) es una extensión de la misma idea a n resultados posibles, pero mutuamente excluyentes. Los ingenieros eléctricos llaman al operador CASE un multiplexor .

IDENTIDAD y evaluación

La primera tabla de esta sección marca con *** la entrada "equivalencia lógica" para señalar que " equivalencia lógica " no es lo mismo que "identidad". Por ejemplo, la mayoría estaría de acuerdo en que la afirmación "Esa vaca es azul" es idéntica a la afirmación "Esa vaca es azul". Por otro lado, la equivalencia lógica a veces aparece en el habla, como en este ejemplo: "'El sol brilla' significa 'estoy montando en bicicleta'". Traducidas a una fórmula proposicional, las palabras se convierten en: "SI 'el sol brilla' ENTONCES 'estoy montando en bicicleta', Y SI 'estoy montando en bicicleta' ENTONCES 'el sol brilla'": ^{[ 14 ]}

La expresión "SI 's' ENTONCES 'b' Y SI 'b' ENTONCES 's'" se escribe como ((s → b) & (b → s)) o de forma abreviada como (s ↔ b). Dado que la cadena de símbolos situada más a la derecha define un nuevo símbolo en función de los símbolos de la izquierda, resulta apropiado utilizar el signo de identidad =:

((s → b) & (b → s)) = (s ↔ b)

Diferentes autores utilizan distintos signos para la equivalencia lógica: ↔ (p. ej., Suppes, Goodstein, Hamilton), ≡ (p. ej., Robbin), ⇔ (p. ej., Bender y Williamson). Normalmente, la identidad se representa con el signo de igualdad =. Una excepción a esta regla se encuentra en Principia Mathematica . Para más información sobre la filosofía de la noción de IDENTIDAD, véase la ley de Leibniz .

Como se indicó anteriormente, Tarski considera que la IDENTIDAD se encuentra fuera del cálculo proposicional, pero afirma que sin esta noción, la "lógica" es insuficiente para las matemáticas y las ciencias deductivas. De hecho, el signo se incorpora al cálculo proposicional cuando se evalúa una fórmula. ^{[ 15 ]}

En algunos sistemas no hay tablas de verdad, sino solo axiomas formales (por ejemplo, cadenas de símbolos de un conjunto { ~, →, (, ), variables p ₁ , p ₂ , p ₃ , ... } y reglas de formación de fórmulas (reglas sobre cómo crear más cadenas de símbolos a partir de cadenas anteriores mediante el uso de, por ejemplo, sustitución y modus ponens ). El resultado de dicho cálculo será otra fórmula (es decir, una cadena de símbolos bien formada). Sin embargo, si se quiere utilizar el cálculo para estudiar las nociones de validez y verdad, se deben añadir axiomas que definan el comportamiento de los símbolos llamados "valores de verdad" {V, F} (o {1, 0}, etc.) en relación con los demás símbolos.

Por ejemplo, Hamilton utiliza dos símbolos = y ≠ cuando define la noción de una valoración v de cualquier fórmula bien formada (fff) A y B en su "cálculo de enunciados formales" L. Una valoración v es una función de las fff de su sistema L al rango (salida) { V, F }, dado que a cada variable p ₁ , p ₂ , p ₃ en una fff se le asigna un valor de verdad arbitrario { V, F }.

Las dos definiciones ( i ) y ( ii ) definen el equivalente de las tablas de verdad para los conectores ~ (NOT) y → (IMPLICACIÓN) de su sistema. La primera deriva F ≠ T y T ≠ F, es decir, " v ( A ) no significa v (~ A )". La definición ( ii ) especifica la tercera fila de la tabla de verdad, y las otras tres filas provienen de la aplicación de la definición ( i ). En particular, ( ii ) asigna el valor F (o un significado de "F") a toda la expresión. Las definiciones también sirven como reglas de formación que permiten sustituir un valor previamente derivado en una fórmula.

Algunos sistemas formales especifican estos axiomas de valoración desde el principio mediante ciertas fórmulas, como la ley de contradicción o las leyes de identidad y nulidad. La elección de cuáles utilizar, junto con leyes como la conmutación y la distribución, depende del diseñador del sistema, siempre que el conjunto de axiomas sea completo (es decir, suficiente para formular y evaluar cualquier fórmula bien formada creada en el sistema).

Fórmulas más complejas

Como se muestra arriba, el conector CASE (IF c THEN b ELSE a) se construye a partir de los conectores de dos argumentos IF ... THEN ... y AND, o bien a partir de OR y AND y el conector de un argumento NOT. Conectores como AND (a & b & c & ... & n) y OR (a ∨ b ∨ c ∨ ... ∨ n) se construyen a partir de cadenas de AND y OR de dos argumentos y se escriben de forma abreviada sin paréntesis. Estos, y otros conectores, pueden utilizarse como bloques de construcción para otros conectores. Los retóricos, filósofos y matemáticos utilizan tablas de verdad y diversos teoremas para analizar y simplificar sus fórmulas.

La ingeniería eléctrica utiliza símbolos dibujados y los conecta con líneas que representan la operación matemática de sustitución y reemplazo. Luego, verifican sus dibujos con tablas de verdad y simplifican las expresiones, como se muestra a continuación, mediante el uso de mapas de Karnaugh o teoremas. De esta manera, los ingenieros han creado una gran variedad de lógica combinatoria (es decir, conectores sin retroalimentación), como decodificadores, codificadores, compuertas multifunción, lógica de mayoría, sumadores binarios, unidades aritmético-lógicas, etc.

Definiciones

Una definición crea un nuevo símbolo y su comportamiento, a menudo con fines de abreviación. Una vez presentada la definición, se puede utilizar cualquiera de las formas del símbolo o fórmula equivalente. El siguiente simbolismo = _Df sigue la convención de Reichenbach. ^{[ 16 ]} Algunos ejemplos de definiciones convenientes extraídas del conjunto de símbolos { ~, &, (, ) } y variables. Cada definición produce una fórmula lógicamente equivalente que puede utilizarse para sustitución o reemplazo.

definición de una nueva variable: (c & d) = _Df s
O bien: ~(~a & ~b) = _Df (a ∨ b)
IMPLICACIÓN: (~a ∨ b) = _Df (a → b)
XOR: (~a & b) ∨ (a & ~b) = _Df (a ⊕ b)
EQUIVALENCIA LÓGICA: ( (a → b) & (b → a) ) = _Df ( a ≡ b )

Esquemas de axiomas y definiciones

Las definiciones anteriores de OR, IMPLICACIÓN, XOR y equivalencia lógica son en realidad esquemas (o "esquemas"), es decir, son modelos (demostraciones, ejemplos) para un formato de fórmula general , pero mostrados (con fines ilustrativos) con letras específicas a, b, c para las variables, mientras que cualquier letra variable puede ir en sus lugares siempre que las sustituciones de letras sigan la regla de sustitución que se indica a continuación.

Ejemplo: En la definición (~a ∨ b) = _Df (a → b), se podrían usar otros símbolos de variables como "SW2" y "CON1", es decir, formalmente:

a = _Df SW2, b = _Df CON1, por lo que tendríamos como instancia del esquema de definición (~SW2 ∨ CON1) = _Df (SW2 → CON1)

Sustitución versus reemplazo

Sustitución : La variable o subfórmula que se va a sustituir por otra variable, constante o subfórmula debe reemplazarse en todos los casos a lo largo de la fórmula general.

Ejemplo: (c & d) ∨ (p & ~(c & ~d)), pero (q1 & ~q2) ≡ d. Ahora, dondequiera que aparezca la variable "d", sustituya (q ₁ & ~q ₂ ):

(c & (q ₁ & ~q ₂ )) ∨ (p & ~(c & ~(q ₁ & ~q ₂ )))

Reemplazo : (i) la fórmula que se va a reemplazar debe estar dentro de una tautología, es decir, lógicamente equivalente (conectada por ≡ o ↔) a la fórmula que la reemplaza, y (ii) a diferencia de la sustitución, es permisible que el reemplazo ocurra solo en un lugar (es decir, para una fórmula).

Ejemplo: Utilice este conjunto de esquemas/equivalencias de fórmulas:

( (a ∨ 0) ≡ a ).
( (a & ~a) ≡ 0 ).
( (~a ∨ b) = _Df (a → b) ).
( ~(~a) ≡ a )

empezar con "a": a
Use 1 para reemplazar "a" con (a ∨ 0): (a ∨ 0)
Utilice la noción de "esquema" para sustituir b por a en 2: ( (a & ~a) ≡ 0 )
Usa 2 para reemplazar 0 con (b & ~b): ( a ∨ (b & ~b) )
(Véase más abajo cómo distribuir "a ∨ " sobre (b & ~b), etc.)

Definición inductiva

La presentación clásica de la lógica proposicional (véase Enderton 2002) utiliza los conectores. $\lnot ,\land ,\lor ,\to ,\leftrightarrow$ El conjunto de fórmulas sobre un conjunto dado de variables proposicionales se define inductivamente como el conjunto más pequeño de expresiones tales que:

Cada variable proposicional en el conjunto es una fórmula,
$(\lnot \alpha )$ es una fórmula siempre $\alpha$ es, y
$(\alpha \,\Box \,\beta )$ es una fórmula siempre $\alpha$ y $\beta$ son fórmulas y $\Box$ es uno de los conectores binarios $\land ,\lor ,\to ,\leftrightarrow$ .

Esta definición inductiva puede extenderse fácilmente para abarcar conectores adicionales.

La definición inductiva también puede reformularse en términos de una operación de cierre (Enderton 2002). Sea V un conjunto de variables proposicionales y sea X _V el conjunto de todas las cadenas de un alfabeto que incluye símbolos en V , paréntesis izquierdo y derecho, y todos los conectores lógicos considerados. Cada conector lógico corresponde a una operación de construcción de fórmulas, una función de XX _V a XX _V :

Dada una cadena z , la operación ${\mathcal {E}}_{\lnot }(z)$ devoluciones $(\lnot z)$ .
Dadas las cadenas y y z , la operación ${\mathcal {E}}_{\land }(y,z)$ devoluciones $(y\land z)$ Existen operaciones similares ${\mathcal {E}}_{\lor }$ , ${\mathcal {E}}_{\to }$ , y ${\mathcal {E}}_{\leftrightarrow }$ correspondientes a los demás conectores binarios.

El conjunto de fórmulas sobre V se define como el subconjunto más pequeño de XX _V que contiene a V y es cerrado bajo todas las operaciones de construcción de fórmulas.

Analizar fórmulas

Las siguientes «leyes» del cálculo proposicional se utilizan para «reducir» fórmulas complejas. Estas «leyes» se pueden verificar fácilmente con tablas de verdad. Para cada ley, el conector principal (el más externo) se asocia con la equivalencia lógica ≡ o la identidad =. Un análisis completo de todas las 2ⁿ ^{combinaciones} de valores de verdad para sus n variables distintas dará como resultado una columna de 1 (V) debajo de este conector. Este hallazgo convierte a cada ley, por definición, en una tautología. Y, para una ley dada, como sus fórmulas de la izquierda y de la derecha son equivalentes (o idénticas), se pueden sustituir entre sí.

Ejemplo: La siguiente tabla de verdad es la ley de De Morgan para el comportamiento de NOT sobre OR: ~(a ∨ b) ≡ (~a & ~b). A la izquierda del conector principal ≡ (columna amarilla etiquetada como "taut"), la fórmula ~(b ∨ a) se evalúa como (1, 0, 0, 0) bajo la etiqueta "P". A la derecha de "taut", la fórmula (~(b) ∨ ~(a)) también se evalúa como (1, 0, 0, 0) bajo la etiqueta "Q". Como las dos columnas tienen evaluaciones equivalentes, la equivalencia lógica ≡ bajo "taut" se evalúa como (1, 1, 1, 1), es decir, P ≡ Q. Por lo tanto, cualquiera de las fórmulas puede sustituir a la otra si aparece en una fórmula más extensa.

Los lectores emprendedores podrían desafiarse a sí mismos a inventar un "sistema axiomático" que utilice los símbolos { ∨ , &, ~, (, ), las variables a, b, c }, las reglas de formación especificadas anteriormente y la menor cantidad posible de las leyes enumeradas a continuación, y luego derivar como teoremas las demás, así como las valoraciones de la tabla de verdad para ∨ , &, y ~. Un conjunto atribuido a Huntington (1904) (Suppes:204) utiliza ocho de las leyes definidas a continuación.

En un sistema axiomático, los símbolos 1 y 0 (o V y F) se consideran fórmulas bien formadas y, por lo tanto, obedecen las mismas reglas que las variables. Así, las leyes que se enumeran a continuación son esquemas axiomáticos , es decir, representan un número infinito de casos. Por ejemplo, ( x ∨ y ) ≡ ( y ∨ x ) podría usarse en un caso, ( p ∨ 0 ) ≡ ( 0 ∨ p ) y en otro caso ( 1 ∨ q ) ≡ ( q ∨ 1 ), etc.

Antigüedad conectiva (rango de símbolo)

En general, para evitar confusiones durante el análisis y la evaluación de fórmulas proposicionales, se pueden usar paréntesis con frecuencia. Sin embargo, a menudo los autores los omiten. Para analizar una fórmula compleja, primero es necesario conocer la antigüedad o rango que tiene cada uno de los conectores (excepto *) sobre los demás. Para "formatear correctamente" una fórmula, comience con el conector de mayor rango y agregue paréntesis alrededor de sus componentes, luego descienda en rango (prestando mucha atención al ámbito sobre el que opera el conector). De mayor a menor antigüedad, con los signos de predicado ∀x y ∃x, el signo de identidad = y los signos aritméticos añadidos para mayor claridad: ^{[ b ]}

≡: (EQUIVALENCIA LÓGICA)
→: (IMPLICACIÓN)
&: (Y)
∨: (O)
~: (NO)
∀x: (PARA TODOS los x)
∃x: (EXISTE UNA x)
=: (IDENTIDAD)
+: (suma aritmética)
*: (multiplicación aritmética)
': (s, sucesor aritmético).

Por lo tanto, la fórmula se puede analizar, pero como NOT no obedece la ley distributiva, los paréntesis alrededor de la fórmula interna (~c y ~d) son obligatorios:

Ejemplo: " d & c ∨ w " reescrito es ( (d & c) ∨ w )

Ejemplo: " a & a → b ≡ a & ~a ∨ b " reescrito (rigurosamente) es

≡ tiene antigüedad: ( ( a & a → b ) ≡ ( a & ~a ∨ b ) )
→ tiene antigüedad: ( ( a & (a → b) ) ≡ ( a & ~a ∨ b ) )
& tiene antigüedad en ambos lados: ( ( ( (a) & (a → b) ) ) ≡ ( ( (a) & (~a ∨ b) ) )
~ tiene antigüedad: ( ( ( (a) & (a → b) ) ) ≡ ( ( (a) & (~(a) ∨ b) ) )
comprobar 9 ( -paréntesis y 9 ) -paréntesis: ( ( ( (a) & (a → b) ) ) ≡ ( ( (a) & (~(a) ∨ b) ) )

Ejemplo:

d & c ∨ p & ~(c & ~d) ≡ c & d ∨ p & c ∨ p & ~d reescrito es ( ( (d & c) ∨ ( p & ~((c & ~(d)) ) ) ) ≡ ( (c & d) ∨ (p & c) ∨ (p & ~(d)) ) )

Leyes conmutativas y asociativas

Tanto AND como OR obedecen la ley conmutativa y la ley asociativa :

Ley conmutativa para OR: ( a ∨ b ) ≡ ( b ∨ a )
Ley conmutativa para AND: ( a & b ) ≡ ( b & a )
Ley asociativa para OR: (( a ∨ b ) ∨ c ) ≡ ( a ∨ (b ∨ c) )
Ley asociativa para AND: (( a & b ) & c ) ≡ ( a & (b & c) )

Omisión de paréntesis en cadenas de AND y OR : Los conectores se consideran unarios (de una variable, por ejemplo, NOT) y binarios (es decir, de dos variables: AND, OR, IMPLIES). Por ejemplo:

( (c & d) ∨ (p & c) ∨ (p & ~d) ) arriba debería escribirse ( ((c & d) ∨ (p & c)) ∨ (p & ~(d) ) ) o posiblemente ( (c & d) ∨ ( (p & c) ∨ (p & ~(d)) ) )

Sin embargo, una demostración mediante una tabla de verdad muestra que la forma sin los paréntesis adicionales es perfectamente adecuada.

Omisión de paréntesis en una negación de una sola variable : Si bien ~(a), donde a es una sola variable, es perfectamente claro, ~a es suficiente y es la forma habitual en que aparece este literal . Cuando la negación se aplica a una fórmula con más de un símbolo, los paréntesis son obligatorios, por ejemplo, ~(a ∨ b).

Leyes distributivas

OR distribuye sobre AND y AND distribuye sobre OR. NOT no distribuye sobre AND ni sobre OR. Véase a continuación la ley de De Morgan:

Ley distributiva para OR: ( c ∨ ( a & b) ) ≡ ( (c ∨ a) & (c ∨ b) )
Ley distributiva para AND: ( c & ( a ∨ b) ) ≡ ( (c & a) ∨ (c & b) )

Las leyes de De Morgan

Cuando se distribuye sobre OR o AND, NOT hace algo peculiar (de nuevo, esto se puede verificar con una tabla de verdad):

Ley de De Morgan para la disyunción: ¬(a ∨ b) ≡ (¬a & ¬b)
Ley de De Morgan para la conjunción "y": ¬(a & b) ≡ (¬a ∨ ¬b)

Leyes de absorción

La absorción, en particular la primera, provoca que las "leyes" de la lógica difieran de las "leyes" de la aritmética:

Absorción (idempotencia) para OR: (a ∨ a) ≡ a
Absorción (idempotencia) para AND: (a & a) ≡ a

Leyes de evaluación: identidad, nulidad y complemento

El signo "=" (a diferencia de la equivalencia lógica ≡, o alternativamente ↔ o ⇔) simboliza la asignación de valor o significado. Así, la cadena (a & ~(a)) simboliza "0", es decir, significa lo mismo que el símbolo "0". En algunos "sistemas", esto será un axioma (definición) que quizás se muestre como ( (a & ~(a)) = _Df 0 ); en otros sistemas, puede derivarse en la tabla de verdad que se muestra a continuación:

Conmutación de la igualdad: (a = b) ≡ (b = a)
Identidad para OR: (a ∨ 0) = a o (a ∨ F) = a
Identidad para AND: (a & 1) = a o (a & T) = a
Nulidad para OR: (a ∨ 1) = 1 o (a ∨ T) = T
Nulidad para AND: (a & 0) = 0 o (a & F) = F
Complemento para OR: (a ∨ ~a) = 1 o (a ∨ ~a) = T, ley del tercero excluido
Complemento para AND: (a & ~a) = 0 o (a & ~a) = F, ley de contradicción

Doble negación (involución)

¬(¬a) ≡ a

Fórmulas bien formadas (ffs)

Una propiedad clave de las fórmulas es que pueden analizarse de forma unívoca para determinar su estructura en función de sus variables proposicionales y conectores lógicos. Cuando las fórmulas se escriben en notación infija , como se indicó anteriormente, la legibilidad unívoca se garantiza mediante el uso adecuado de paréntesis en su definición. Alternativamente, las fórmulas pueden escribirse en notación polaca o notación polaca inversa , eliminando por completo la necesidad de paréntesis.

La definición inductiva de fórmulas infijas en la sección anterior se puede convertir a una gramática formal en forma de Backus-Naur :

< fórmula > ::= < variable proposicional > | ( ¬ < fórmula > ) | ( < fórmula > ∧ < fórmula > ) | ( < fórmula > ∨ < fórmula > ) | ( < fórmula > → < fórmula > ) | ( < fórmula > ↔ < fórmula > )

Se puede demostrar que cualquier expresión que coincida con la gramática tiene un número equilibrado de paréntesis izquierdos y derechos, y cualquier segmento inicial no vacío de una fórmula tiene más paréntesis izquierdos que derechos. ^{[ 18 ]} Este hecho se puede utilizar para dar un algoritmo para analizar fórmulas. Por ejemplo, supongamos que una expresión x comienza con $(\lnot$ A partir del segundo símbolo, se busca la subexpresión más corta y de x que tenga paréntesis balanceados. Si x es una fórmula, queda exactamente un símbolo después de esta expresión, este símbolo es un paréntesis de cierre, y y es una fórmula. Esta idea se puede utilizar para generar un analizador sintáctico descendente recursivo para fórmulas.

Ejemplo de conteo de paréntesis :

Este método ubica como "1" el conector principal , el conector bajo el cual se realiza la evaluación general de la fórmula para los paréntesis más externos (que a menudo se omiten). ^{[ 19 ]} También ubica el conector más interno donde se comenzaría la evaluación de la fórmula sin el uso de una tabla de verdad, por ejemplo, en el "nivel 6".

Fórmulas bien formadas frente a fórmulas válidas en inferencias

La noción de argumento válido se aplica generalmente a las inferencias en los argumentos, pero los argumentos se reducen a fórmulas proposicionales y pueden evaluarse igual que cualquier otra fórmula proposicional. Aquí, una inferencia válida significa: "La fórmula que representa la inferencia se evalúa como "verdadera" bajo su conector principal, independientemente de los valores de verdad que se asignen a sus variables", es decir, la fórmula es una tautología. ^{[ 20 ]} Es muy posible que una fórmula esté bien formada pero no sea válida. Otra forma de decirlo es: "Estar bien formada es necesario para que una fórmula sea válida, pero no suficiente ". La única forma de averiguar si está bien formada y es válida es someterla a verificación con una tabla de verdad o mediante el uso de las "leyes":

Ejemplo 1: ¿Qué se puede concluir de la siguiente afirmación difícil de entender? ¿Es válida? "Si hace sol, pero si la rana croa, entonces no hace sol, entonces es lo mismo que decir que la rana no croa". Conviértala en una fórmula proposicional de la siguiente manera:
" SI (a Y (SI b ENTONCES NO-a) ENTONCES NO-a" donde "a" representa "hace sol" y "b" representa "la rana está croando":
( ( (a) & ( (b) → ~(a) ) ≡ ~(b) )
Está bien formulado, pero ¿es válido ? En otras palabras, al evaluarlo, ¿resultará una tautología (todo T) bajo el símbolo de equivalencia lógica ≡ ? La respuesta es NO, no es válido. Sin embargo, si se reconstruye como una implicación , entonces el argumento es válido.
"Decir que hace sol, pero si la rana croa entonces no hace sol, implica que la rana no está croando."
Puede que existan otras circunstancias que impidan que la rana croeé: quizás una grulla se la comió.
Ejemplo 2 (de Reichenbach vía Bertrand Russell):
"Si los cerdos tienen alas, algunos animales alados son buenos para comer. Algunos animales alados son buenos para comer, por lo tanto, los cerdos tienen alas."
( ((a) → (b)) & (b) → (a) ) está bien formado, pero es un argumento inválido como lo muestra la evaluación en rojo bajo la implicación principal:

Conjuntos reducidos de conectores

Un conjunto de conectores lógicos se denomina completo si toda fórmula proposicional es tautológicamente equivalente a una fórmula que contenga únicamente los conectores de ese conjunto. Existen muchos conjuntos completos de conectores, entre ellos: $\{\land ,\lnot \}$ , $\{\lor ,\lnot \}$ , y $\{\to ,\lnot \}$ Hay dos conectores binarios que son completos por sí mismos, correspondientes a NAND y NOR, respectivamente. ^{[ 21 ]} Algunos pares no son completos, por ejemplo $\{\land ,\lor \}$ .

El accidente cerebrovascular (NAND)

El conector binario correspondiente a NAND se llama trazo de Sheffer y se escribe con una barra vertical | o una flecha vertical ↑. La completitud de este conector se señaló en Principia Mathematica (1927:xvii). Dado que es completo por sí mismo, todos los demás conectores pueden expresarse utilizando solo el trazo. Por ejemplo, donde el símbolo " ≡ " representa la equivalencia lógica :

~p ≡ p|p

p → q ≡ p|~q

p ∨ q ≡ ~p|~q

p y q ≡ ~(p|q)

En particular, los conectivos cero-arios $\top$ (que representa la verdad) y $\bot$ (que representa la falsedad) se puede expresar usando el trazo:

\top \equiv (a|(a|a))

\bot \equiv (\top |\top )

SI ... ENTONCES ... SI NO

Este conector junto con { 0, 1 }, ( o { F, T } o { $\bot$ , $\top$ } ) forma un conjunto completo. En lo siguiente, la relación IF...THEN...ELSE (c, b, a) = d representa ( (c → b) ∨ (~c → a) ) ≡ ( (c & b) ∨ (~c & a) ) = d

(c, b, a):

(c, 0, 1) ≡ ~c

(c, b, 1) ≡ (c → b)

(c, c, a) ≡ (c ∨ a)

(c, b, c) ≡ (c y b)

Ejemplo: A continuación se muestra cómo se procedería con una demostración basada en teoremas de "(c, b, 1) ≡ (c → b)"; debajo de la demostración se encuentra su verificación mediante tabla de verdad. (Nota: (c → b) se define como (~c ∨ b)):

Comience con la forma reducida: ( (c & b) ∨ (~c & a) )
Sustituye "1" por a: ( (c & b) ∨ (~c & 1) )
Identidad (~c & 1) = ~c: ( (c & b) ∨ (~c) )
Ley de conmutación para V: ( (~c) ∨ (c & b) )
Distribuye "~c V" sobre (c & b): ( ((~c) ∨ c ) & ((~c) ∨ b )
Ley del tercero excluido (((~c) ∨ c ) = 1 ): ( (1) & ((~c) ∨ b ) )
Distribuye "(1) &" sobre ((~c) ∨ b): ( ((1) & (~c)) ∨ ((1) & b )) )
Conmutatividad e identidad (( 1 & ~c) = (~c & 1) = ~c, y (( 1 & b) ≡ (b & 1) ≡ b: ( ~c ∨ b )
( ~c ∨ b ) se define como c → b QED

En la siguiente tabla de verdad, la columna etiquetada como "taut" (tautología) evalúa la equivalencia lógica (simbolizada aquí por ≡) entre las dos columnas etiquetadas como d. Dado que las cuatro filas bajo "taut" son 1, la equivalencia representa efectivamente una tautología.

Formas normales

Una fórmula proposicional arbitraria puede tener una estructura muy compleja. A menudo resulta conveniente trabajar con fórmulas que tengan formas más simples, conocidas como formas normales . Algunas formas normales comunes incluyen la forma normal conjuntiva y la forma normal disyuntiva . Cualquier fórmula proposicional puede reducirse a su forma normal conjuntiva o disyuntiva.

Reducción a la forma normal

Una tabla de verdad contiene 2ⁿ ^filas , donde n es el número de variables (por ejemplo, tres variables "p", "d" y "c" generan 2³ ^filas ). Cada fila representa un minitérmino. Cada minitérmino se puede encontrar en el diagrama de Hasse, en el diagrama de Veitch y en el mapa de Karnaugh. (Las evaluaciones de "p" que se muestran en la tabla de verdad no aparecen en los diagramas de Hasse, Veitch y Karnaugh; estas se muestran en el mapa de Karnaugh de la siguiente sección).

La reducción a la forma normal es relativamente sencilla una vez que se ha preparado una tabla de verdad para la fórmula. Sin embargo, los intentos posteriores para minimizar el número de literales (véase más adelante) requieren algunas herramientas: la reducción mediante las leyes de De Morgan y las tablas de verdad puede resultar engorrosa, pero los mapas de Karnaugh son muy adecuados para un número reducido de variables (5 o menos). Existen algunos métodos tabulares sofisticados para circuitos más complejos con múltiples salidas, pero estos quedan fuera del alcance de este artículo; para más información, véase el algoritmo de Quine-McCluskey .

Literal, término y alterm

En ingeniería eléctrica, una variable x o su negación ~(x) se denomina literal . Una secuencia de literales unidos por operadores AND se llama término. Una secuencia de literales unidos por operadores OR se llama alterm. Normalmente, el literal ~(x) se abrevia como ~x. En ocasiones, el símbolo & se omite por completo, al igual que en la multiplicación algebraica.

Ejemplos
1. a, b, c, d son variables. ((( a & ~(b) ) & ~(c)) & d) es un término. Esto se puede abreviar como (a & ~b & ~c & d), o a~b~cd.
2. p, q, r, s son variables. (((p ∨ ~(q) ) ∨ r) ∨ ~(s) ) es un altérmino. Esto se puede abreviar como (p ∨ ~q ∨ r ∨ ~s).

Minterms

De la misma manera que una tabla de verdad de ²ⁿ filas muestra la evaluación de una fórmula proposicional para todos los 2n ^valores posibles de sus variables, n variables producen un mapa de Karnaugh de 2n ^cuadrados (aunque no podamos dibujarlo en su realización de dimensión completa). Por ejemplo, 3 variables producen 2³ ⁼ 8 filas y 8 cuadrados de Karnaugh; 4 variables producen 16 filas de la tabla de verdad y 16 cuadrados y, por lo tanto, 16 minterms . Cada cuadrado del mapa de Karnaugh y su correspondiente evaluación de la tabla de verdad representan un minterm.

Cualquier fórmula proposicional puede reducirse a la "suma lógica" (OR) de los minterms activos (es decir, con valor "1" o "T"). Cuando se presenta en esta forma, se dice que la fórmula está en forma normal disyuntiva . Sin embargo, aunque se encuentre en esta forma, no necesariamente se minimiza con respecto al número de términos ni al número de literales.

En la siguiente tabla, observe la peculiar numeración de las filas: (0, 1, 3, 2, 6, 7, 5, 4, 0). La primera columna es el equivalente decimal del equivalente binario de los dígitos "cba", es decir:

Ejemplo
cba ₂ = c*2 ² + b*2 ¹ + a*2 ⁰ :
cba = (c=1, b=0, a=1) = 101 ₂ = 1*2 ² + 0*2 ¹ + 1*2 ⁰ = 5 ₁₀

Esta numeración surge porque, al recorrer la tabla fila por fila, solo una variable cambia de valor a la vez. El código Gray se deriva de este concepto. Este concepto se puede extender a hipercubos tridimensionales y cuatridimensionales llamados diagramas de Hasse, donde las variables de cada vértice cambian solo una a la vez al moverse por las aristas del cubo. Los diagramas de Hasse (hipercubos) aplanados en dos dimensiones son diagramas de Veitch o mapas de Karnaugh (que son prácticamente lo mismo).

Al trabajar con diagramas de Karnaugh, siempre hay que tener en cuenta que el borde superior se "envuelve" hasta el borde inferior, y el borde izquierdo se envuelve hasta el borde derecho; el diagrama de Karnaugh es en realidad un objeto aplanado de tres, cuatro o n dimensiones.

Reducción mediante el método del mapa (Veitch, Karnaugh)

Veitch mejoró la noción de diagramas de Venn al convertir los círculos en cuadrados contiguos, y Karnaugh simplificó el diagrama de Veitch al convertir los minitérminos, escritos en su forma literal (por ejemplo, ~abc~d), en números. ^{[ 22 ]} El método procede de la siguiente manera:

Generar la tabla de verdad de la fórmula

Elabore la tabla de verdad de la fórmula. Numere sus filas utilizando los equivalentes binarios de las variables (generalmente de forma secuencial del 0 al n-1) para n variables.

Técnicamente, la función proposicional se ha reducido a su forma normal conjuntiva (no minimizada): cada fila tiene su expresión de minterm y estas se pueden combinar con OR para producir la fórmula en su forma normal conjuntiva (no minimizada).

Ejemplo: ((c & d) ∨ (p & ~(c & (~d)))) = q en forma normal conjuntiva es:

( (~p & d & c ) ∨ (p & d & c) ∨ (p & d & ~c) ∨ (p & ~d & ~c) ) = q

Sin embargo, esta fórmula se puede reducir tanto en el número de términos (de 4 a 3) como en el recuento total de sus literales (de 12 a 6).

Crea el mapa de Karnaugh de la fórmula.

Utilice los valores de la fórmula (por ejemplo, "p") obtenidos mediante el método de la tabla de verdad y colóquelos en sus respectivos cuadrados de Karnaugh (numerados según la convención del código Gray). Si aparecen valores "d" (que indican "indiferencia") en la tabla, esto proporciona flexibilidad durante la fase de reducción.

Reducir minterms

Los minterms de cuadrados adyacentes (contiguos) de 1 (cuadrados T) se pueden reducir con respecto al número de sus literales , y los términos numéricos también se reducirán en el proceso. Dos cuadrados contiguos (2 x 1 horizontal o 1 x 2 vertical, incluso los bordes representan cuadrados contiguos) pierden un literal, cuatro cuadrados en un rectángulo de 4 x 1 (horizontal o vertical) o un cuadrado de 2 x 2 (incluso las cuatro esquinas representan cuadrados contiguos) pierden dos literales, ocho cuadrados en un rectángulo pierden 3 literales, etc. (Se busca el cuadrado o rectángulo más grande y se ignoran los cuadrados o rectángulos más pequeños que contiene totalmente). Este proceso continúa hasta que se contabilizan todos los cuadrados contiguos, momento en el que se minimiza la fórmula proposicional.

Por ejemplo, los cuadrados n.° 3 y n.° 7 son contiguos. Estos dos cuadrados contiguos pueden perder un literal (por ejemplo, "p" de los cuadrados n.° 3 y n.° 7), cuatro cuadrados en un rectángulo o cuadrado pierden dos literales, ocho cuadrados en un rectángulo pierden tres literales, etc. (Se busca el cuadrado o rectángulo más grande). Este proceso continúa hasta que se hayan considerado todos los cuadrados contiguos, momento en el que se dice que la fórmula proposicional se ha minimizado.

Ejemplo: El método del mapa generalmente se realiza por inspección. El siguiente ejemplo amplía el método algebraico para mostrar el "truco" que hay detrás de la combinación de términos en un mapa de Karnaugh:

Los minterms n.° 3 y n.° 7 son contiguos, el n.° 7 y el n.° 6 son contiguos, y el n.° 4 y el n.° 6 son contiguos (porque los bordes de la mesa se curvan). Por lo tanto, cada uno de estos pares se puede reducir.

Obsérvese que, por la ley de idempotencia (A ∨ A) = A, podemos crear más términos. Luego, por las leyes de asociación y distribución, las variables que desaparecen pueden emparejarse y, posteriormente, "desaparecer" con la ley de contradicción (x & ~x)=0. A continuación, se utilizan corchetes [ y ] únicamente para llevar un registro de los términos; no tienen ningún significado especial:

Coloca la fórmula en forma conjuntiva normal con la fórmula que se va a reducir:

q = ( (~p & d & c ) ∨ (p & d & c) ∨ (p & d & ~c) ∨ (p & ~d & ~c) ) = ( #3 ∨ #7 ∨ #6 ∨ #4 )

Idempotencia (absorción) [ A ∨ A) = A:

( #3 ∨ [ #7 ∨ #7 ] ∨ [ #6 ∨ #6 ] ∨ #4 )

Ley asociativa (x ∨ (y ∨ z)) = ( (x ∨ y) ∨ z )

( [ #3 ∨ #7 ] ∨ [ #7 ∨ #6 ] ∨ [ #6 ∨ #4] )

[ (~p & d & c ) ∨ (p & d & c) ] ∨ [ (p & d & c) ∨ (p & d & ~c) ] ∨ [ (p & d & ~c) ∨ (p & ~d & ~c) ] .

Ley distributiva ( x & (y ∨ z) ) = ( (x & y) ∨ (x & z) ) :

( [ (d & c) ∨ (~p & p) ] ∨ [ (p & d) ∨ (~c & c) ] ∨ [ (p & ~c) ∨ (c & ~c) ] )

Ley conmutativa y ley de contradicción (x & ~x) = (~x & x) = 0:

( [ (d & c) ∨ (0) ] ∨ [ (p & d) ∨ (0) ] ∨ [ (p & ~c) ∨ (0) ] )

Ley de identidad ( x ∨ 0 ) = x que conduce a la forma reducida de la fórmula:

q = ( (d & c) ∨ (p & d) ∨ (p & ~c) )

Verificar la reducción con una tabla de verdad

Proposiciones impredicativas

Dados los siguientes ejemplos-como-definiciones, ¿qué se puede deducir del razonamiento subsiguiente?

(1) "Esta oración es simple." (2) "Esta oración es compleja y está unida por la conjunción 'y'."

Luego, asigne la variable "s" a la oración más a la izquierda: "Esta oración es simple". Defina "compuesta" c = "no simple" ~s, y asigne c = ~s a "Esta oración es compuesta"; asigne "j" a "Esta [oración] está unida por AND". La segunda oración se puede expresar como:

(NO(s) Y j)

Si se asignan valores de verdad a las oraciones c = ~s y j, entonces todas son claramente FALSAS: por ejemplo, "Esta oración es compleja" es una FALSA (es simple , por definición). Por lo tanto, su conjunción (Y) es una falsedad. Pero cuando se toma en su forma ensamblada, la oración es una VERDAD.

Este es un ejemplo de las paradojas que resultan de una definición impredicativa ; es decir, cuando un objeto m tiene una propiedad P, pero el objeto m se define en términos de la propiedad P. ^{[ 23 ]} El mejor consejo para un retórico o alguien involucrado en el análisis deductivo es evitar las definiciones impredicativas, pero al mismo tiempo estar atento a ellas, ya que pueden generar paradojas. Los ingenieros, por otro lado, las utilizan en forma de fórmulas proposicionales con retroalimentación.

Fórmula proposicional con "retroalimentación"

La noción de que una fórmula proposicional aparezca como una de sus propias variables requiere una regla de formación que permita la asignación de la fórmula a una variable. En general, no existe ninguna estipulación (ni axiomática ni de sistemas de tablas de verdad de objetos y relaciones) que prohíba que esto ocurra. ^{[ 24 ]}

El caso más simple ocurre cuando una fórmula OR se convierte en una de sus propias entradas, por ejemplo, p = q. Comencemos con (p ∨ s) = q, luego sea p = q. Observe que la "definición" de q depende de sí misma "q" así como de "s" y del conector OR; esta definición de q es, por lo tanto, impredicativa. Cualquiera de dos condiciones puede resultar: ^{[ 25 ]} oscilación o memoria.

Resulta útil pensar en la fórmula como una caja negra . Sin saber qué ocurre dentro de la fórmula, desde fuera parecería que el resultado ya no depende únicamente de las entradas. Es decir, a veces se observa q y se obtiene 0, y otras veces 1. Para evitar este problema, es necesario conocer el estado (condición) de la variable "oculta" p dentro de la caja (es decir, el valor de q que se retroalimenta y se asigna a p). Cuando se conoce este estado, la aparente inconsistencia desaparece.

Para comprender [predecir] el comportamiento de las fórmulas con retroalimentación se requiere un análisis más sofisticado de los circuitos secuenciales . Las fórmulas proposicionales con retroalimentación, en su forma más simple, dan lugar a máquinas de estados; también dan lugar a memorias en forma de cintas de Turing y contadores de máquinas de contadores. A partir de combinaciones de estos elementos se puede construir cualquier tipo de modelo computacional acotado (por ejemplo, máquinas de Turing , máquinas de contadores , máquinas de registros , ordenadores Macintosh , etc.).

Oscilación

En el caso abstracto (ideal), la fórmula oscilante más simple es una NOT que se retroalimenta a sí misma: ~(~(p=q)) = q. El análisis de una fórmula proposicional abstracta (ideal) en una tabla de verdad revela una inconsistencia para los casos p=1 y p=0: cuando p=1, q=0, esto no puede ser porque p=q; lo mismo ocurre cuando p=0 y q=1.

Oscilación con retardo : Si se inserta un retardo ^{[ 26 ]} (ideal o no ideal) en la fórmula abstracta entre p y q, entonces p oscilará entre 1 y 0: 101010...101... ad infinitum . Si el retardo o NOT no son abstractos (es decir, no son ideales), el tipo de análisis que se utilizará dependerá de la naturaleza exacta de los objetos que componen el oscilador; tales cosas quedan fuera de las matemáticas y pertenecen a la ingeniería.

El análisis requiere insertar un retardo y luego cortar el bucle entre el retardo y la entrada "p". El retardo debe considerarse como una proposición que tiene como salida "qd" (q-retardo) para la entrada "q". Esta nueva proposición añade otra columna a la tabla de verdad. La inconsistencia se encuentra ahora entre "qd" y "p", como se muestra en rojo; resultando en dos estados estables:

Memoria

Sin demora, las inconsistencias deben eliminarse de un análisis de tabla de verdad. Con la noción de "retraso", esta condición se presenta como una inconsistencia momentánea entre la variable de salida retroalimentada q y p = q _retrasada .

Una tabla de verdad revela las filas donde ocurren inconsistencias entre p = q _retardado en la entrada y q en la salida. Después de "romper" la retroalimentación, ^{[ 27 ]} la construcción de la tabla de verdad procede de la manera convencional. Pero luego, en cada fila la salida q se compara con la entrada p ahora independiente y se anotan las inconsistencias entre p y q (es decir, p=0 junto con q=1, o p=1 y q=0); cuando la "línea" se "rehace", ambas se vuelven imposibles por la Ley de contradicción ~(p & ~p)). Las filas que revelan inconsistencias se consideran estados transitorios o simplemente se eliminan como inconsistentes y, por lo tanto, "imposibles".

Memoria de un solo giro

El ejemplo más sencillo de memoria se da cuando la salida de una compuerta OR retroalimenta una de sus entradas; en este caso, la salida "q" retroalimenta "p". Dado que la fórmula se evalúa (inicializa) inicialmente con p=0 y q=0, se producirá un cambio de estado al establecerse mediante s=1. Posteriormente, la salida "q" se mantendrá en el estado de cambio (estado q=1). Este comportamiento, ahora dependiente del tiempo, se muestra en el diagrama de estados a la derecha del cambio de estado.

Memoria biestable

El siguiente caso más simple es el flip-flop "set-reset" que se muestra debajo del flip-flop de un solo uso. Dado que r=0 y s=0 y q=0 al inicio, se "set" (s=1) de manera similar al flip-flop de un solo uso. Sin embargo, tiene una disposición para "reset" q=0 cuando "r"=1. Y surge una complicación adicional si tanto set=1 como reset=1. En esta fórmula, set=1 fuerza la salida q=1, por lo que cuando y si (s=0 y r=1) el flip-flop se reiniciará. O, si (s=1 y r=0) el flip-flop se establecerá. En el caso abstracto (ideal) en el que s=1 ⇒ s=0 y r=1 ⇒ r=0 simultáneamente, la fórmula q será indeterminada (indecidible). Debido a los retrasos en OR, AND y NOT "reales", el resultado será desconocido al principio, pero posteriormente predecible.

Memoria de biestable sincronizada

La fórmula conocida como memoria de "flip-flop sincronizado" ("c" es el "reloj" y "d" son los "datos") se muestra a continuación. Su funcionamiento es el siguiente: Cuando c = 0, los datos d (ya sean 0 o 1) no pueden "transmitirse" para afectar la salida q. Cuando c = 1, los datos d "transmiten" y la salida q "sigue" el valor de d. Cuando c cambia de 1 a 0, el último valor de los datos queda "atrapado" en la salida "q". Mientras c = 0, d puede cambiar de valor sin que q cambie.

Ejemplos
1. ( ( c & d ) ∨ ( p & ( ~( c & ~( d ) ) ) ) = q , pero ahora sea p = q:
2. ( ( c & d ) ∨ ( q & ( ~( c & ~( d ) ) ) ) = q

El diagrama de estados tiene una forma similar al diagrama de estados del flip-flop, pero con un etiquetado diferente en las transiciones.

Desarrollo histórico

Bertrand Russell (1912:74) enumera tres leyes del pensamiento que derivan de Aristóteles : (1) La ley de identidad : "Lo que es, es.", (2) La ley de no contradicción : "Nada puede ser y no ser a la vez", y (3) La ley del tercero excluido : "Todo debe ser o no ser".

Ejemplo: Aquí O es una expresión sobre el SER o la CUALIDAD de un objeto:
1. Ley de identidad: O = O
2. Ley de contradicción: ~(O & ~(O))
3. Ley del tercero excluido: (O ∨ ~(O))

El uso de la palabra "todo" en la ley del tercero excluido hace que la formulación de esta ley por parte de Russell sea objeto de debate. Si se restringe a una expresión sobre SER o CUALIDAD con referencia a una colección finita de objetos (un "universo de discurso" finito) —cuyos miembros pueden investigarse uno tras otro para determinar la presencia o ausencia de la afirmación—, entonces la ley se considera apropiada desde un punto de vista intuicionista. Así, una afirmación como: "Este objeto debe SER o NO SER (en la colección)", o "Este objeto debe tener esta CUALIDAD o NO tener esta CUALIDAD (en relación con los objetos de la colección)" es aceptable. Véase más en el diagrama de Venn .

Aunque el cálculo proposicional se originó con Aristóteles, la noción de un álgebra aplicada a las proposiciones no surgió hasta principios del siglo XIX. Como reacción (adversa) a la tradición de 2000 años de los silogismos aristotélicos , el Ensayo sobre el entendimiento humano (1690) de John Locke empleó el término semiótica (teoría del uso de símbolos). En 1826, Richard Whately analizó críticamente la lógica silogística con cierta simpatía hacia la semiótica de Locke. La obra de George Bentham (1827) dio lugar a la noción de "cuantificación del predicado" (1827) (actualmente simbolizada como ∀ ≡ "para todo"). Una "disputa" instigada por William Hamilton sobre una controversia de prioridad con Augustus De Morgan "inspiró a George Boole a escribir sus ideas sobre lógica y a publicarlas como MAL [Análisis Matemático de la Lógica] en 1847" (Grattin-Guinness y Bornet 1997:xxviii).

Sobre su contribución, Grattin-Guinness y Bornet comentan:

«La principal innovación de Boole fue la ley [x ⁿ = x] para la lógica: establecía que los actos mentales de elegir la propiedad x y elegir x repetidamente son lo mismo que elegir x una sola vez... Como consecuencia de ello, formuló las ecuaciones x•(1-x)=0 y x+(1-x)=1, que para él expresaban respectivamente la ley de la contradicción y la ley del tercero excluido» (p. xxviiff). Para Boole, «1» era el universo del discurso y «0» era la nada.

La monumental obra de Gottlob Frege (1879) dio como resultado un cálculo formal de proposiciones, pero su simbolismo es tan complejo que tuvo escasa influencia, salvo en una persona: Bertrand Russell . Primero como alumno de Alfred North Whitehead, estudió la obra de Frege y propuso una enmienda (famosa y controvertida) al respecto (1904) en torno al problema de una antinomia que descubrió en el tratamiento de Frege (véase la paradoja de Russell ). El trabajo de Russell propició una colaboración con Whitehead que, en 1912, dio lugar al primer volumen de Principia Mathematica (PM). Es aquí donde apareció por primera vez lo que consideramos lógica proposicional "moderna". En particular, PM introduce NOT y OR y el símbolo de aserción ⊦ como primitivos. En términos de estas nociones definen IMPLICACIÓN → ( def. *1.01: ~p ∨ q ), luego Y ( def. *3.01: ~(~p ∨ ~q) ), luego EQUIVALENCIA p ←→ q (*4.01: (p → q) & ( q → p ) ).

Henry M. Sheffer (1921) y Jean Nicod demuestran que un solo conector, el "trazo" |, es suficiente para expresar todas las fórmulas proposicionales.
Emil Post (1921) desarrolla el método de tablas de verdad para el análisis en su "Introducción a una teoría general de las proposiciones elementales". Menciona el golpe de Nicod | .
Whitehead y Russell añaden una introducción a su reedición de PM de 1927, agregando, en parte, un tratamiento favorable del "ictus".

Lógica de cálculo y conmutación :

William Eccles y FW Jordan (1919) describen un "relé de disparo" fabricado con un tubo de vacío.
George Stibitz (1937) inventa el sumador binario utilizando relés mecánicos. Lo construye en la mesa de su cocina.

Ejemplo: Dados los bits binarios a _i y b _i y el acarreo de entrada ( c_in _i ), su suma Σ _i y el acarreo de salida ( c_out _i ) son:

( ( a _i XOR b _i ) XOR c_in _i )= Σ _i
( a _i & b _i ) ∨ c_in _i ) = c_out _i ;

Alan Turing construyó un multiplicador utilizando relés (1937-1938). Para ello, tuvo que bobinar a mano las bobinas de sus propios relés.
Los primeros libros de texto sobre "circuitos de conmutación" aparecieron a principios de la década de 1950.
Willard Quine ( 1952 y 1955), EW Veitch (1952) y M. Karnaugh (1953) desarrollaron métodos de mapeo para simplificar funciones proposicionales.
George H. Mealy (1955) y Edward F. Moore (1956) abordan la teoría de las "máquinas" secuenciales (es decir, de circuitos de conmutación).
EJ McCluskey y H. Shorr desarrollan un método para simplificar circuitos proposicionales (de conmutación) (1962).

Notas a pie de página

↑ Rosenbloom analiza este problema de implicación con cierto detalle. La mayoría de los filósofos y matemáticos simplemente aceptan la definición material dada anteriormente. Pero algunos no lo hacen, incluidos los intuicionistas ; la consideran una forma de la ley del tercero excluido mal aplicada.^{[ 12 ]}
↑ Rosenbloom^{[ 17 ]} y Kleene 1952:73-74 clasifican los 11 símbolos.

Citas

↑ Kao, Eric J.; Genesereth, Michael (2017). «Lógica proposicional» . Introducción a la lógica . Synthesis Lectures on Computer Science (3.ª ed.). doi : 10.1007/978-3-031-01801-5 . ISBN 9783031018015.
↑ Hamilton 1978:1
↑ Principia Mathematica (PM) pág. 91 evita "el" porque requiere un "objeto de sensación" bien definido; estipula el uso de "este".
↑ (cursiva añadida) Reichenbachp.80.
↑ Tarski págs. 54-68. Suppes denomina a IDENTIDAD una «regla de inferencia adicional» y la desarrolla brevemente; Robbin, Bender y Williamson, y Goodstein introducen el signo y su uso sin comentarios ni explicaciones. Hamilton, pág. 37, emplea dos signos, ≠ y =, con respecto a la valoración de una fórmula en un cálculo formal. Kleene, pág. 70, y Hamilton, pág. 52, lo ubican en el cálculo de predicados, en particular con respecto a la aritmética de los números naturales.
↑ Los empiristas rechazan la noción de conocimiento a priori (innato, inherente). Los "reduccionistas radicales", como John Locke y David Hume, "sostenían que toda idea debía originarse directamente en la experiencia sensorial o bien estar compuesta de ideas que se originaran de esta manera"; citado de Quine, reimpreso en 1996, The Emergence of Logical Empiricism , Garland Publishing Inc. http://www.marxists.org/reference/subject/philosophy/works/us/quine.htm
↑ El modelado de redes neuronales ofrece un buen modelo matemático para un comparador de la siguiente manera: Dado una señal S y un umbral "thr", reste "thr" de S y sustituya esta diferencia d en una función sigmoide : Para grandes "ganancias" k, por ejemplo k=100, 1/( 1 + e^−k*d ) = 1/( 1 + e^−k*(S-thr) ) = { ≃0, ≃1 }.Por ejemplo, si "La puerta está BAJA" significa "La puerta está a menos del 50% de su recorrido", entonces se podría aplicar un umbral thr=0,5 correspondiente a 0,5*5,0 = +2,50 voltios a un dispositivo de medición "lineal" con una salida de 0 voltios cuando está completamente cerrado y +5,0 voltios cuando está completamente abierto.
↑ En realidad, los valores digitales 1 y 0 se definen en rangos que no se superponen, por ejemplo, { "1" = +5/+0,2/−1,0 voltios, 0 = +0,5/−0,2 voltios }. Cuando un valor cae fuera del rango o rangos definidos, el valor se convierte en "u" (desconocido); por ejemplo, +2,3 sería "u".
↑ Si bien la noción de producto lógico no es tan peculiar (por ejemplo, 0*0=0, 0*1=0, 1*0=0, 1*1=1), la noción de (1+1=1) sí lo es ; de hecho, (a "+" b) = (a + (b - a*b)), donde "+" es la "suma lógica", pero + y - son sus contrapartes aritméticas reales. Ocasionalmente, las cuatro nociones aparecen en una fórmula: A AND B = 1/2*( A plus B minus ( A XOR B ) ] (cf. pág. 146 en John Wakerly 1978, Error Detecting Codes, Self-Checking Circuits and Applications , North-Holland, Nueva York, ISBN 0-444-00259-6pbk.)
↑ Una mirada atenta a su mapa de Karnaugh muestra que IF...THEN...ELSE también puede expresarse, de una manera bastante indirecta, en términos de dos OR exclusivos: ( (b AND (c XOR a)) OR (a AND (c XOR b)) ) = d.
↑ Robbin pág. 3.
↑ Rosenbloom 1950 , págs. 30 y 54 y siguientes.
↑ De hecho, la definición que Kleene da al operador CASE exigeuna selección exhaustiva entre alternativas ( exclusión mutua ) (Kleene 1952229).
↑ El uso de comillas alrededor de las expresiones no es accidental. Tarski comenta sobre el uso de las comillas en su artículo "18. Identidad de las cosas e identidad de sus designaciones; uso de comillas" pág. 58 y siguientes.
↑ Hamilton, pág. 37. Bender y Williamson, pág. 29, afirman: «En lo que sigue, reemplazaremos "igual" por el símbolo "⇔" (equivalencia), que se usa habitualmente en lógica. Usamos el más familiar "=" para asignar significado y valores».
↑ Reichenbach págs. 20-22 y sigue las convenciones de PM. El símbolo =_Df está en el metalenguaje y no es un símbolo formal con el siguiente significado: "por símbolo 's' debe tener el mismo significado que la fórmula '(c & d)'".
↑ Rosenbloom 1950 , pág. 32.
↑ cf Minsky 1967:75, sección 4.2.3 «El método de conteo de paréntesis». Minsky presenta una máquina de estados que realiza la tarea y, mediante inducción (definición recursiva), demuestra el «método» y presenta un teorema como resultado. Una «gramática de paréntesis» completamente generalizada requiere una máquina de estados infinita (por ejemplo, una máquina de Turing) para realizar el conteo.
↑ Robbin pág. 7
↑ cf Reichenbach p. 68 para una discusión más detallada: "Si la inferencia es válida y las premisas son verdaderas, la inferencia se denomina concluyente .
↑ Además de las tres primeras, Hamilton pp.19-22 analiza lógicas construidas únicamente a partir de | (NAND) y ↓ (NOR).
↑ Wickes 1967:36 y ss. Wickes ofrece un buen ejemplo de 8 de los mapas de 2 x 4 (3 variables) y 16 de los mapas de 4 x 4 (4 variables). Como un mapa arbitrario de 3 variables podría representar cualquiera de 2⁸⁼ 256 mapas de 2 x 4, y un mapa arbitrario de 4 variables podría representar cualquiera de^2¹⁶ = 65 536 evaluaciones de fórmulas diferentes, escribirlas todas es inviable.
↑ Esta definición la da Stephen Kleene . Tanto Kurt Gödel como Kleene creían que las paradojas clásicas son ejemplos uniformes de este tipo de definición. Pero Kleene afirmó que el problema no se ha resuelto satisfactoriamente y que se pueden encontrar definiciones impredicativas en el análisis . Da como ejemplo la definición de la cota superior mínima (lub) u de M. Dada una sección de Dedekind de la recta numérica C y las dos partes en las que se divide la recta numérica, es decir, M y ( C - M ), lub = u se define en términos de la noción M , mientras que M se define en términos de C. Por lo tanto, la definición de u , un elemento de C , se define en términos de la totalidad C , lo que hace que su definición sea impredicativa. Kleene afirma que los intentos de refutar esto pueden usarse para sostener las definiciones impredicativas en las paradojas (Kleene 1952:43).
↑ McCluskey comenta que "podría argumentarse que el análisis aún está incompleto porque no se ha obtenido la declaración verbal 'Las salidas son iguales a los valores anteriores de las entradas'"; luego descarta tales preocupaciones porque "el inglés no es un lenguaje formal en un sentido matemático, [y] realmente no es posible tener un procedimiento formal para obtener declaraciones verbales" (p. 185).
↑ Más precisamente, con una ganancia de bucle suficiente, se producirá oscilación o memoria (cf. McCluskey, págs. 191-192). En sistemas matemáticos abstractos (idealizados), una ganancia de bucle adecuada no representa un problema.
↑ La noción de retardo y el principio de causalidad local, causados en última instancia por la velocidad de la luz, aparecen en Robin Gandy (1980), «La tesis de Church y los principios para los mecanismos», en J. Barwise, H.J. Keisler y K. Kunen (eds.), The Kleene Symposium , North-Holland Publishing Company (1980), págs. 123-148. Gandy consideraba que este era el más importante de sus principios: «La física contemporánea rechaza la posibilidad de una acción instantánea a distancia» (pág. 135). Gandy fuealumno y amigo íntimo de Alan Turing .
↑ McKlusky (págs. 194-195) analiza cómo "romper el bucle" e inserta "amplificadores" para lograrlo; Wickes (págs. 118-121) analiza la inserción de retardos. McClusky (págs. 195 y siguientes) analiza el problema de las "carreras" causadas por los retardos.

Referencias

Rosenbloom, Paul (1950). Los elementos de la lógica matemática . Mineola, Nueva York: Dover Publications, Inc. ISBN 0-486-44617-4.{{cite book}}: Incompatibilidad de ISBN/Fecha ( ayuda )
Kleene, Stephen (1952). Introducción a la metamatemática . Ámsterdam: North-Holland Publishing Company.
Bender, Edward A. y Williamson, S. Gill , 2005, Un curso breve de matemáticas discretas , Dover Publications, Mineola, NY, ISBN 0-486-43946-1Este texto se utiliza en un curso de dos trimestres de nivel básico de informática en la UC San Diego.
Enderton, HB , 2002, Introducción matemática a la lógica. Harcourt/Academic Press. ISBN 0-12-238452-0
Goodstein, RL , (Pergamon Press 1963), 1966, (edición Dover 2007), Álgebra booleana , Dover Publications, Inc. Minola, Nueva York, ISBN 0-486-45894-6Se hace hincapié en la noción de "álgebra de clases" con símbolos de teoría de conjuntos como ∩, ∪, ' (NOT), ⊂ (IMPLIES). Más adelante, Goldstein los reemplaza por &, ∨, ￢, → (respectivamente) en su análisis de "Sentence Logic" (pp. 76-93).
Ivor Grattan-Guinness y Gérard Bornet 1997, George Boole: Manuscritos seleccionados sobre lógica y su filosofía , Birkhäuser Verlag, Basilea, ISBN 978-0-8176-5456-6(Bostón).
AG Hamilton 1978, Lógica para matemáticos , Cambridge University Press, Cambridge, Reino Unido, ISBN 0-521-21838-1.
E.J. McCluskey, 1965, Introducción a la teoría de los circuitos de conmutación , McGraw-Hill Book Company, Nueva York. Sin ISBN. Número de catálogo de la Biblioteca del Congreso: 65-17394. McCluskey fue alumno de Willard Quine y desarrolló algunos teoremas importantes con él y por su cuenta. Para quienes estén interesados en la historia, el libro contiene numerosas referencias.
Marvin L. Minsky, 1967, Computación: Máquinas finitas e infinitas , Prentice-Hall, Inc., Englewood Cliffs, NJ. Sin ISBN. Número de catálogo de la Biblioteca del Congreso: 67-12342. Útil especialmente para la computabilidad, además de buenas fuentes.
Joel W. Robbin 1969, 1997, Lógica matemática: Un primer curso , Dover Publications, Inc., Mineola, Nueva York, ISBN 0-486-45018-X(pbk.).
Patrick Suppes 1957 (edición Dover de 1999), Introducción a la lógica , Dover Publications, Inc., Mineola, Nueva York. ISBN 0-486-40687-3(rústica). Este libro está impreso y disponible fácilmente.
En la página 204, en una nota al pie, hace referencia a su conjunto de axiomas en EV Huntington , "Sets of Independent Postulates for the Algebra of Logic", Transactions of the American Mathematical Society , Vol. 5 91904) pp. 288-309.
Alfred Tarski 1941 (edición Dover de 1995), Introducción a la lógica y a la metodología de las ciencias deductivas , Dover Publications, Inc., Mineola, Nueva York. ISBN 0-486-28462-X(rústica). Este libro está impreso y disponible fácilmente.
Jean van Heijenoort 1967, 3.ª edición con enmiendas de 1976, De Frege a Gödel: Un libro de referencia en lógica matemática, 1879-1931 , Harvard University Press, Cambridge, Massachusetts. ISBN 0-674-32449-8(pbk.) Las traducciones/reimpresiones de Frege (1879), la carta de Russell a Frege (1902) y la carta de Frege a Russell (1902), la paradoja de Richard (1905) y Post (1921) se pueden encontrar aquí.
Alfred North Whitehead y Bertrand Russell 1927 2.ª edición, edición de bolsillo hasta *53 1962, Principia Mathematica , Cambridge University Press, sin ISBN. En los años entre la primera edición de 1912 y la 2.ª edición de 1927, HM Sheffer 1921 y M. Jean Nicod (sin año citado) señalaron a Russell y Whitehead que lo que consideraban sus proposiciones primitivas (conectivas) podían reducirse a una sola |, conocida hoy en día como el "trazo" o NAND (NOT-AND, NEITHER ... NOR...). Russell-Whitehead discuten esto en su "Introducción a la segunda edición" y hacen las definiciones como se discutió anteriormente.
William E. Wickes, 1968, Diseño lógico con circuitos integrados , John Wiley & Sons, Inc., Nueva York. Sin ISBN. Número de catálogo de la Biblioteca del Congreso: 68-21185. Presentación concisa de los métodos de análisis y síntesis de la ingeniería, con referencias a McCluskey (1965). A diferencia de Suppes, la presentación del "álgebra booleana" de Wickes comienza con un conjunto de postulados de naturaleza de tabla de verdad y luego deriva los teoremas habituales (pág. 18 y ss.).

Enlaces externos

Contenido multimedia relacionado con la fórmula proposicional en Wikimedia Commons.

[13] Rosenbloom analiza este problema de implicación con cierto detalle. La mayoría de los filósofos y matemáticos simplemente aceptan la definición material dada anteriormente. Pero algunos no lo hacen, incluidos los intuicionistas ; la consideran una forma de la ley del tercero excluido mal aplicada.^{[ 12 ]}

[19] Rosenbloom^{[ 17 ]} y Kleene 1952:73-74 clasifican los 11 símbolos.

[1] Kao, Eric J.; Genesereth, Michael (2017). «Lógica proposicional» . Introducción a la lógica . Synthesis Lectures on Computer Science (3.ª ed.). doi : 10.1007/978-3-031-01801-5 . ISBN 9783031018015.

[2] Hamilton 1978:1

[3] Principia Mathematica (PM) pág. 91 evita "el" porque requiere un "objeto de sensación" bien definido; estipula el uso de "este".

[4] (cursiva añadida) Reichenbachp.80.

[5] Tarski págs. 54-68. Suppes denomina a IDENTIDAD una «regla de inferencia adicional» y la desarrolla brevemente; Robbin, Bender y Williamson, y Goodstein introducen el signo y su uso sin comentarios ni explicaciones. Hamilton, pág. 37, emplea dos signos, ≠ y =, con respecto a la valoración de una fórmula en un cálculo formal. Kleene, pág. 70, y Hamilton, pág. 52, lo ubican en el cálculo de predicados, en particular con respecto a la aritmética de los números naturales.

[6] Los empiristas rechazan la noción de conocimiento a priori (innato, inherente). Los "reduccionistas radicales", como John Locke y David Hume, "sostenían que toda idea debía originarse directamente en la experiencia sensorial o bien estar compuesta de ideas que se originaran de esta manera"; citado de Quine, reimpreso en 1996, The Emergence of Logical Empiricism , Garland Publishing Inc. http://www.marxists.org/reference/subject/philosophy/works/us/quine.htm

[7] El modelado de redes neuronales ofrece un buen modelo matemático para un comparador de la siguiente manera: Dado una señal S y un umbral "thr", reste "thr" de S y sustituya esta diferencia d en una función sigmoide : Para grandes "ganancias" k, por ejemplo k=100, 1/( 1 + e^−k*d ) = 1/( 1 + e^−k*(S-thr) ) = { ≃0, ≃1 }.Por ejemplo, si "La puerta está BAJA" significa "La puerta está a menos del 50% de su recorrido", entonces se podría aplicar un umbral thr=0,5 correspondiente a 0,5*5,0 = +2,50 voltios a un dispositivo de medición "lineal" con una salida de 0 voltios cuando está completamente cerrado y +5,0 voltios cuando está completamente abierto.

[8] En realidad, los valores digitales 1 y 0 se definen en rangos que no se superponen, por ejemplo, { "1" = +5/+0,2/−1,0 voltios, 0 = +0,5/−0,2 voltios }. Cuando un valor cae fuera del rango o rangos definidos, el valor se convierte en "u" (desconocido); por ejemplo, +2,3 sería "u".

[9] Si bien la noción de producto lógico no es tan peculiar (por ejemplo, 0*0=0, 0*1=0, 1*0=0, 1*1=1), la noción de (1+1=1) sí lo es ; de hecho, (a "+" b) = (a + (b - a*b)), donde "+" es la "suma lógica", pero + y - son sus contrapartes aritméticas reales. Ocasionalmente, las cuatro nociones aparecen en una fórmula: A AND B = 1/2*( A plus B minus ( A XOR B ) ] (cf. pág. 146 en John Wakerly 1978, Error Detecting Codes, Self-Checking Circuits and Applications , North-Holland, Nueva York, ISBN 0-444-00259-6pbk.)

[10] Una mirada atenta a su mapa de Karnaugh muestra que IF...THEN...ELSE también puede expresarse, de una manera bastante indirecta, en términos de dos OR exclusivos: ( (b AND (c XOR a)) OR (a AND (c XOR b)) ) = d.

[11] Robbin pág. 3.

[FOOTNOTERosenbloom195030_and_54ff-12] Rosenbloom 1950 , págs. 30 y 54 y siguientes.

[14] De hecho, la definición que Kleene da al operador CASE exigeuna selección exhaustiva entre alternativas ( exclusión mutua ) (Kleene 1952229).

[15] El uso de comillas alrededor de las expresiones no es accidental. Tarski comenta sobre el uso de las comillas en su artículo "18. Identidad de las cosas e identidad de sus designaciones; uso de comillas" pág. 58 y siguientes.

[16] Hamilton, pág. 37. Bender y Williamson, pág. 29, afirman: «En lo que sigue, reemplazaremos "igual" por el símbolo "⇔" (equivalencia), que se usa habitualmente en lógica. Usamos el más familiar "=" para asignar significado y valores».

[17] Reichenbach págs. 20-22 y sigue las convenciones de PM. El símbolo =_Df está en el metalenguaje y no es un símbolo formal con el siguiente significado: "por símbolo 's' debe tener el mismo significado que la fórmula '(c & d)'".

[FOOTNOTERosenbloom195032-18] Rosenbloom 1950 , pág. 32.

[20] Minsky 1967:75, sección 4.2.3 «El método de conteo de paréntesis». Minsky presenta una máquina de estados que realiza la tarea y, mediante inducción (definición recursiva), demuestra el «método» y presenta un teorema como resultado. Una «gramática de paréntesis» completamente generalizada requiere una máquina de estados infinita (por ejemplo, una máquina de Turing) para realizar el conteo.

[21] Robbin pág. 7

[22] Reichenbach p. 68 para una discusión más detallada: "Si la inferencia es válida y las premisas son verdaderas, la inferencia se denomina concluyente .

[23] Además de las tres primeras, Hamilton pp.19-22 analiza lógicas construidas únicamente a partir de | (NAND) y ↓ (NOR).

[24] Wickes 1967:36 y ss. Wickes ofrece un buen ejemplo de 8 de los mapas de 2 x 4 (3 variables) y 16 de los mapas de 4 x 4 (4 variables). Como un mapa arbitrario de 3 variables podría representar cualquiera de 2⁸⁼ 256 mapas de 2 x 4, y un mapa arbitrario de 4 variables podría representar cualquiera de^2¹⁶ = 65 536 evaluaciones de fórmulas diferentes, escribirlas todas es inviable.

[25] Esta definición la da Stephen Kleene . Tanto Kurt Gödel como Kleene creían que las paradojas clásicas son ejemplos uniformes de este tipo de definición. Pero Kleene afirmó que el problema no se ha resuelto satisfactoriamente y que se pueden encontrar definiciones impredicativas en el análisis . Da como ejemplo la definición de la cota superior mínima (lub) u de M. Dada una sección de Dedekind de la recta numérica C y las dos partes en las que se divide la recta numérica, es decir, M y ( C - M ), lub = u se define en términos de la noción M , mientras que M se define en términos de C. Por lo tanto, la definición de u , un elemento de C , se define en términos de la totalidad C , lo que hace que su definición sea impredicativa. Kleene afirma que los intentos de refutar esto pueden usarse para sostener las definiciones impredicativas en las paradojas (Kleene 1952:43).

[26] McCluskey comenta que "podría argumentarse que el análisis aún está incompleto porque no se ha obtenido la declaración verbal 'Las salidas son iguales a los valores anteriores de las entradas'"; luego descarta tales preocupaciones porque "el inglés no es un lenguaje formal en un sentido matemático, [y] realmente no es posible tener un procedimiento formal para obtener declaraciones verbales" (p. 185).

[27] Más precisamente, con una ganancia de bucle suficiente, se producirá oscilación o memoria (cf. McCluskey, págs. 191-192). En sistemas matemáticos abstractos (idealizados), una ganancia de bucle adecuada no representa un problema.

[28] La noción de retardo y el principio de causalidad local, causados en última instancia por la velocidad de la luz, aparecen en Robin Gandy (1980), «La tesis de Church y los principios para los mecanismos», en J. Barwise, H.J. Keisler y K. Kunen (eds.), The Kleene Symposium , North-Holland Publishing Company (1980), págs. 123-148. Gandy consideraba que este era el más importante de sus principios: «La física contemporánea rechaza la posibilidad de una acción instantánea a distancia» (pág. 135). Gandy fuealumno y amigo íntimo de Alan Turing .

[29] McKlusky (págs. 194-195) analiza cómo "romper el bucle" e inserta "amplificadores" para lograrlo; Wickes (págs. 118-121) analiza la inserción de retardos. McClusky (págs. 195 y siguientes) analiza el problema de las "carreras" causadas por los retardos.

valor

[ 2 ]

[ 3 ]

[ 4 ].

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ a ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ b ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 12 ]

[ 17 ]