En lógica proposicional , una fórmula proposicional es un tipo de fórmula sintáctica que está bien formada y tiene un valor de verdad . Si se dan los valores de todas las variables en una fórmula proposicional, se determina un valor de verdad único. Una fórmula proposicional también puede denominarse expresión proposicional , oración o fórmula proposicional .
Una fórmula proposicional se construye a partir de proposiciones simples , como "cinco es mayor que tres" o variables proposicionales como P y Q , usando conectivos u operadores lógicos como NOT, AND, OR o IMPLIES; por ejemplo:
- ( P Y NO Q ) IMPLICA ( P OR Q ).
En matemáticas , una fórmula proposicional a menudo se conoce más brevemente como una " 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, al igual que una expresión tal ya que " x + y " no es un valor, pero denota un valor. En algunos contextos, mantener la distinción puede ser importante.
Proposiciones
Para los propósitos del cálculo proposicional, las proposiciones (enunciados, oraciones, afirmaciones) se consideran simples o compuestas . [1] Se considera que las proposiciones compuestas están vinculadas por conectivos oracionales , algunos de los más comunes son "Y", "O", "SI ... ENTONCES ...", "NI ... NI ...", "... ES EQUIVALENTE A ... ". El punto y coma de enlace ";" y el conector "BUT" se consideran expresiones de "Y". Se considera que una secuencia de oraciones discretas está unida por "Y", y el análisis formal aplica una "regla de paréntesis" recursiva con respecto a secuencias de proposiciones simples (ver más abajo sobre fórmulas bien formadas).
- Por ejemplo: La afirmación: "Esta vaca es azul. Ese caballo es naranja, pero este caballo aquí es morado". es en realidad una proposición compuesta vinculada por "Y" s: (("Esta vaca es azul" Y "ese caballo es naranja") Y "este caballo aquí es morado").
Las proposiciones simples son de naturaleza declarativa, es decir, hacen afirmaciones sobre la condición o naturaleza de un objeto particular de sensación, por ejemplo, "Esta vaca es azul", "¡Hay un coyote!" ("Ese coyote ESTÁ ahí , detrás de las rocas"). [2] Por lo tanto, las afirmaciones "primitivas" simples deben referirse a objetos específicos o estados mentales específicos. Cada uno debe tener al menos un sujeto (un objeto inmediato de pensamiento u observación), un verbo (en la voz activa y el tiempo presente preferido), y tal vez un adjetivo o adverbio. "¡Perro!" probablemente implica "Veo un perro", pero debería rechazarse por ser demasiado ambiguo.
- Ejemplo: "Ese perro morado está corriendo", "Esta vaca es azul", "El interruptor M31 está cerrado", "Esta gorra está apagada", "Mañana es viernes".
Para los propósitos del cálculo proposicional, una proposición compuesta generalmente puede reformularse en una serie de oraciones simples, aunque el resultado probablemente suene forzado.
Relación entre fórmulas proposicionales y predicativas
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" [3] Divide 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 objeto (s)). El cálculo de predicados luego generaliza la forma "sujeto | predicado" (donde | simboliza la concatenación (encadenamiento) 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. Por el contrario, en el cálculo de predicados, la primera oración se divide en "este cerdo" como sujeto y "tiene alas" como predicado. Por lo tanto, afirma que el objeto "este cerdo" es un miembro de la clase (conjunto, colección) de "cosas aladas". La segunda oración afirma que el objeto "este cerdo" tiene un atributo "azul" y, por lo tanto, es miembro de la clase de "cosas azules". Uno podría optar por escribir las dos oraciones conectadas con AND 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 encuentra que p es miembro de este dominio o no. Por lo tanto, existe una relación W (alas) entre p (cerdo) y {T, F}, W (p) se evalúa como {T, F} donde {T, F} es el conjunto de los valores booleanos "verdadero" y " falso". Del mismo modo, para B (azul) yp (cerdo) y {T, F}: B (p) se evalúa como {T, F}. Entonces, uno ahora puede analizar las afirmaciones conectadas "B (p) Y W (p)" para su valor de verdad general, es decir:
- (B (p) AND W (p)) se evalúa como {T, F}
En particular, las oraciones simples que emplean nociones de "todos", "algunos", "algunos", "uno de", etc. 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 todos), y ∃ (Existe ..., Al menos uno de ... existe, etc.). El cálculo de predicados, pero no el cálculo proposicional, puede establecer la validez formal del siguiente enunciado:
- "Todos los cerdos azules tienen alas, pero algunos cerdos no tienen alas, por lo que algunos cerdos no son azules".
Identidad
Tarski afirma que la noción de IDENTIDAD (a diferencia de EQUIVALENCIA LÓGICA) se encuentra fuera del cálculo proposicional; sin embargo, señala que si una lógica va a ser útil para las matemáticas y las ciencias, debe contener una "teoría" de la IDENTIDAD. [4] Algunos autores se refieren a la "lógica de predicados con identidad" para enfatizar esta extensión. Vea más sobre esto a continuación.
Un álgebra de proposiciones, el cálculo proposicional
Un álgebra (y hay muchos diferentes), vagamente definido, es un método mediante el cual una colección de símbolos llamados variables junto con algunos otros símbolos como paréntesis (,) y algún subconjunto de símbolos como *, +, ~ , &, ∨, =, ≡, ∧, ¬ se manipulan dentro de un sistema de reglas. Se dice que estos símbolos, y las cadenas bien formadas de ellos, representan objetos , pero en un sistema algebraico específico estos objetos no tienen significados . Así, el trabajo dentro del álgebra se convierte en un ejercicio de obedecer 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 de símbolos bien formada 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 hablados o afirmaciones escritas) vinculadas por conectivos proposicionales, todo este sistema algebraico de símbolos y reglas y métodos de evaluación se suele llamar cálculo proposicional o cálculo oracional. .
Si bien algunas de las reglas familiares del álgebra aritmética continúan siendo válidas en el álgebra de proposiciones (por ejemplo, las leyes conmutativas y asociativas para Y y O), algunas no (por ejemplo, las leyes distributivas para Y, O y NO).
Utilidad de 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 los estudian (generalmente con tablas de verdad ) para verificar su corrección (solidez). Por ejemplo: ¿Es correcto el siguiente argumento?
- "Dado que la conciencia es suficiente para una inteligencia artificial y solo las entidades conscientes pueden pasar la prueba de Turing , antes de que podamos concluir que un robot es una inteligencia artificial, el robot debe pasar la prueba de Turing".
Los ingenieros analizan los circuitos lógicos que han diseñado utilizando técnicas de síntesis y luego aplican varias 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 como 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 es 10 2 , donde "co" = 1 y Σ = 0 como se muestra en las columnas de la derecha.
fila | B | a | ci | (b + a) + ci | co | Σ | |
---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | |
1 | 0 | 0 | 1 | 1 | 0 | 1 | |
2 | 0 | 1 | 0 | 1 | 0 | 1 | |
3 | 0 | 1 | 1 | 2 | 1 | 0 | |
4 | 1 | 0 | 0 | 1 | 0 | 1 | |
5 | 1 | 0 | 1 | 2 | 1 | 0 | |
6 | 1 | 1 | 0 | 2 | 1 | 0 | |
7 | 1 | 1 | 1 | 3 | 1 | 1 |
Variables proposicionales
El tipo más simple de fórmula proposicional es una variable proposicional . Las proposiciones que son simples ( atómicas ), las expresiones simbólicas a menudo se denotan por 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 le asigna la variable llamada ...") o "Solo voy al cine los lunes" = q .
Asignaciones de valor 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. Debido a que cada variable representa una oración simple, los valores de verdad se aplican a la "verdad" o "falsedad" de estas oraciones simples.
Valores de verdad en retórica, filosofía y matemáticas : Los valores de verdad son solo dos: {VERDAD "T", FALSIDAD "F"}. Un empirista clasifica todas las proposiciones en dos grandes clases: analíticas —verdaderas sin importar qué (por ejemplo, tautología ) y sintéticas — derivadas de la experiencia y, por lo tanto, susceptibles de confirmación por parte de terceros (la teoría de la verificación del significado). [5] Los empíricos 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 declaración una VERDAD? De verdad lo dije. Y tal vez estoy viendo una vaca azul, a menos que esté mintiendo, mi declaración es una VERDAD en relación con el objeto de mi percepción (quizás defectuosa). Pero, ¿la vaca azul está "realmente ahí"? ¿Qué ves cuando miras por la misma ventana? Para proceder con una 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 sensación (si es que hay uno). [ cita requerida ]
Los valores de la verdad en la ingeniería : los ingenieros tratan de evitar las nociones de verdad y falsedad que atormentan a los filósofos, pero en el análisis final los ingenieros deben confiar en sus instrumentos de medición. En su búsqueda de robustez , los ingenieros prefieren extraer objetos conocidos de una biblioteca pequeña, objetos que tienen comportamientos predecibles bien definidos incluso en grandes combinaciones (de ahí su nombre para el cálculo proposicional: "lógica combinatoria"). La menor cantidad de comportamientos de un solo objeto son dos (por ejemplo, {OFF, ON}, {open, shut}, {UP, DOWN}, etc.), y estos se ponen en correspondencia con {0, 1}. Estos elementos se denominan digitales ; aquellos con una gama continua de comportamientos se denominan analógicos . Siempre que deban tomarse decisiones en un sistema analógico, muy a menudo un ingeniero convertirá un comportamiento analógico (la puerta es 45,32146% ARRIBA) a digital (por ejemplo, ABAJO = 0) mediante el uso de un comparador . [6]
Por lo tanto, una asignación de significado de las variables y los dos símbolos de valor {0, 1} proviene "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 ARRIBA con la etiqueta SW_U y otro para ABAJO con la etiqueta SW_D, y cualquier otra cosa que se encuentre en el circuito de la puerta. La inspección del circuito (ya sea el diagrama o los objetos reales en sí mismos: puerta, interruptores, cables, placa de circuito, etc.) puede revelar que, en la placa de circuito, el "nodo 22" pasa a +0 voltios cuando los contactos del interruptor "SW_D "están mecánicamente en contacto (" cerrados ") y la puerta está en la posición" abajo "(95% abajo), y" nodo 29 "pasa a +0 voltios cuando la puerta está 95% ARRIBA y los contactos del interruptor SW_U están en contacto mecánico ("cerrado"). [7] El ingeniero debe definir el significado de estos voltajes y todas las combinaciones posibles (las 4), incluidas las "malas" (por ejemplo, ambos nodos 22 y 29 a 0 voltios, lo que significa que la puerta está abierta y cerrada en el Mismo tiempo). El circuito responde sin pensar a los voltajes que experimenta sin ninguna conciencia de VERDAD o FALSEDAD, CORRECTO o INCORRECTO, SEGURO o PELIGROSO. [ cita requerida ]
Conectivos proposicionales
Las fórmulas proposicionales arbitrarias se construyen a partir de variables proposicionales y otras fórmulas proposicionales utilizando conectivos proposicionales . Ejemplos de conectivos incluyen:
- La negación unaria conectiva. Si es una fórmula, entonces es una fórmula.
- Las conectivas binarias clásicas . Así, por ejemplo, si y son fórmulas, también lo es .
- Otros conectivos binarios, como NAND, NOR y XOR
- El conectivo ternario SI ... ENTONCES ... ELSE ...
- Conectivos 0-arios constantes ⊤ y ⊥ (alternativamente, constantes {T, F}, {1, 0} etc.)
- El conectivo "teoría-extensión" es IGUAL (alternativamente, IDENTIDAD, o el signo "=" a diferencia del "conectivo lógico" )
Conectividad de retórica, filosofía y matemáticas
Los siguientes son los conectivos comunes a la retórica, la filosofía y las matemáticas junto con sus tablas de verdad . Los símbolos utilizados variarán de un autor a otro y entre los campos de actividad. En general, las abreviaturas "T" y "F" representan las evaluaciones VERDAD y FALSIDAD aplicadas a las variables en la fórmula proposicional (por ejemplo, la afirmación: "Esa vaca es azul" tendrá el valor de verdad "T" para Verdad o " F "de falsedad, según sea el caso).
Los conectivos tienen varios usos de palabras diferentes, por ejemplo, "a IMPLICA b" también se dice "SI a ENTONCES b". Algunos de estos se muestran en la tabla.
b solo si un | |||||||||||
b ES SUFICIENTE PARA a | b PRECISAMENTE CUANDO a | ||||||||||
a ES NECESARIO PARA b | b SI Y SOLO SI a; b IFF a | ||||||||||
inclusive O | SI b ENTONCES a | b ES NECESARIO Y SUFICIENTE PARA | |||||||||
negación | negación | conjunción | disyunción | implicación | bicondicional | ||||||
variables | No es b | No un | by a | b O a | b IMPLICA a | b ES lógicamente equivalente a a *** | f ES una tautología | Ni a ni B | b trazo a | exclusivo o | |
---|---|---|---|---|---|---|---|---|---|---|---|
B | a | ¬ (b) | ¬ (a) | (b ∧ a) | (b ∨ a) | (b → a) | (b ↔ a) | (f = fórmula) | (a NOR b) | (b | a) | varios |
F | F | T | T | F | F | T | T | T | T | T | F |
F | T | T | F | F | T | T | F | T | F | T | T |
T | F | F | T | F | T | F | F | T | F | T | T |
T | T | F | F | T | T | T | T | T | F | F | F |
Conectivos de ingeniería
En general, las conexiones de ingeniería son las mismas que las matemáticas, excepto que tienden a evaluar con "1" = "T" y "0" = "F". Esto se hace con fines de análisis / minimización y síntesis de fórmulas mediante el uso de la noción de minitérminos y mapas de Karnaugh (ver más abajo). Los ingenieros también usan las palabras producto lógico de la noción de Boole (a * a = a) y suma lógica de la noción de Jevons (a + a = a). [8]
producto lógico | suma lógica | medio sumador (sin acarreo) | |||||||
---|---|---|---|---|---|---|---|---|---|
exclusivo o | |||||||||
numero de fila | variables | NO | NO | Y | O | NAND | NI | XOR | |
b * 2 1 + a * 2 0 | B | a | ~ (b) | ~ (a) | (b & a) | (b ∨ a) | ~ (by a) | ~ (b ∨ a) | ⊕ |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
2 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
3 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
Conectivo CASE: SI ... ENTONCES ... ELSE ...
El conectivo IF ... THEN ... ELSE ... aparece como la forma más simple de operador CASE de la teoría de recursividad y la teoría de la computación y es el conectivo responsable de goto condicional (saltos, ramas). A partir de este conectivo se pueden construir todos los demás conectivos (ver más abajo). Aunque "SI c ENTONCES b ELSE a" suena como una implicación, es, en su forma más reducida, un cambio que toma una decisión y ofrece como resultado solo una de las dos alternativas "a" o "b" (de ahí la declaración de cambio de nombre en el lenguaje de programación C ). [9]
Las siguientes tres proposiciones son equivalentes (como lo indica el signo de equivalencia lógica ≡):
- (SI 'el contador es cero' ENTONCES 'vaya a la instrucción b ' ELSE 'vaya a la instrucción a ') ≡
- ((c → b) & (~ c → a)) ≡ (((SI 'el contador es cero' ENTONCES 'vaya a la instrucción b ') Y (SI 'NO es el caso de que el contador sea cero' ENTONCES 'vaya a la instrucción a ) "≡
- ((c & b) ∨ (~ c & a)) ≡ "('El contador es cero' Y 'vaya a la instrucción b ) O (' NO es el caso que 'el contador es cero' Y 'vaya a la instrucción a ) "
Por lo tanto, SI ... ENTONCES ... ELSE, a diferencia de la implicación, no evalúa una "VERDAD" ambigua cuando la primera proposición es falsa, es decir, c = F en (c → b). Por ejemplo, la mayoría de la gente rechazaría la siguiente proposición compuesta como un non sequitur sin sentido porque la segunda oración no está conectada en significado con la primera. [10]
- Ejemplo: La proposición "SI 'Winston Churchill era chino' ENTONCES 'El sol sale por el este'" se evalúa como VERDAD dado que 'Winston Churchill era chino' es una FALSEDAD y 'El sol sale por el este' se evalúa como VERDAD .
En reconocimiento de este problema, el signo → de implicación formal en el cálculo proposicional se llama implicación material para distinguirlo de la implicación intuitiva cotidiana. [11]
El uso de la construcción SI ... ENTONCES ... ELSE evita la controversia porque ofrece una elección completamente determinista entre dos alternativas declaradas; ofrece dos "objetos" (las dos alternativas by a), y selecciona entre ellos de forma exhaustiva e inequívoca. [12] En la siguiente tabla de verdad, d1 es la fórmula: ((SI c ENTONCES b) Y (SI NO-c ENTONCES a)). Su forma completamente reducida d2 es la fórmula: ((c Y b) O (NO-c Y a). Las dos fórmulas son equivalentes como se muestra en las columnas "= d1" y "= d2". Los ingenieros eléctricos llaman a la formula 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 .
d1 | d2 | ||||||||||||||||||||||||||||||||||||||
fila | C | B | a | ( | ( | C | → | B | ) | Y | ( | ~ | ( | C | ) | → | a | ) | ) | = d1 | ( | ( | C | Y | B | ) | ∨ | ( | ~ | ( | C | ) | Y | a | ) | ) | = d2 | ||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | ||||||||||||||||||
1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | ||||||||||||||||||
2 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | ||||||||||||||||||
3 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | ||||||||||||||||||
4 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | ||||||||||||||||||
5 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | ||||||||||||||||||
6 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | ||||||||||||||||||
7 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
IDENTIDAD y evaluación
La primera tabla de esta sección protagoniza *** la entrada equivalencia lógica para señalar el hecho de 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 está brillando' significa 'estoy en bicicleta'" Traducido a una fórmula proposicional, las palabras se convierten en: "SI 'el sol está brillando' ENTONCES ' Estoy en bicicleta ', Y SI' estoy en bicicleta 'ENTONCES' el sol está brillando '": [13]
- "SI 'es' ENTONCES 'b' Y SI 'b' ENTONCES '" se escribe como ((s → b) & (b → s)) o en forma abreviada como (s ↔ b). Como la cadena de símbolos más a la derecha es una definición para un nuevo símbolo en términos de los símbolos de la izquierda, el uso del signo de IDENTIDAD = es apropiado:
- ((s → b) y (b → s)) = (s ↔ b)
Diferentes autores utilizan diferentes signos para la equivalencia lógica: ↔ (por ejemplo, Suppes, Goodstein, Hamilton), ≡ (por ejemplo, Robbin), ⇔ (por ejemplo, Bender y Williamson). Normalmente, la identidad se escribe con el signo igual =. Una excepción a esta regla se encuentra en Principia Mathematica . Para obtener más información sobre la filosofía de la noción de IDENTIDAD, consulte la ley de Leibniz .
Como se señaló anteriormente, Tarski considera que la IDENTIDAD se encuentra fuera del cálculo proposicional, pero afirma que sin la noción, la "lógica" es insuficiente para las matemáticas y las ciencias deductivas. De hecho, el signo entra en el cálculo proposicional cuando se va a evaluar una fórmula. [14]
En algunos sistemas no hay tablas de verdad, sino solo axiomas formales (por ejemplo, cadenas de símbolos de un conjunto {~, →, (,), variables p 1 , p 2 , p 3 , ...} y reglas de formación de fórmulas (reglas sobre cómo hacer 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). Eventualmente, sin embargo, si uno quiere Para utilizar el cálculo para estudiar las nociones de validez y verdad, se deben agregar axiomas que definan el comportamiento de los símbolos llamados "los valores de verdad" {T, F} (o {1, 0}, etc.) en relación con los otros símbolos.
Por ejemplo, Hamilton usa dos símbolos = y ≠ cuando define la noción de una valoración v de cualquier fórmula bien formada (wffs) A y B en su "cálculo de enunciados formales" L. Una valoración v es una función de las wffs de su sistema L al rango (salida) {T, F}, dado que a cada variable p 1 , p 2 , p 3 en una wff se le asigna un valor de verdad arbitrario {T, F}.
- v ( A ) ≠ v (~ A )
( i )
- v ( A → B ) = F si y solo si v ( A ) = T yv ( B ) = F
( ii )
Las dos definiciones ( i ) y ( ii ) definen el equivalente de las tablas de verdad para las conectivas ~ (NOT) y → (IMPLICACIÓN) de su sistema. El primero deriva F ≠ T y T ≠ F, en otras palabras " v ( A ) no significa v (~ A )". La definición ( ii ) especifica la tercera fila en la tabla de verdad, y las otras tres filas provienen de una aplicación de la definición ( i ). En particular ( ii ) asigna el valor F (o el significado de "F") a toda la expresión. Las definiciones también sirven como reglas de formación que permiten la sustitución de un valor previamente derivado en una fórmula:
v (A → B) | ||||
( | Virginia) | → | v (B) | ) |
F | T | F | ||
F | T | T | ||
T | F | F | ||
T | T | T |
Algunos sistemas formales especifican estos axiomas de valoración desde el principio en forma de ciertas fórmulas como la ley de contradicción o las leyes de identidad y nulidad. La elección de cuáles usar, 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 formar y evaluar cualquier fórmula bien formada creada en el sistema). .
Fórmulas más complejas
Como se muestra arriba, la conectiva CASE (IF c THEN b ELSE a) se construye a partir de las conectivas de 2 argumentos IF ... THEN ... y AND o de OR y AND y el argumento 1 NOT. Conectivos como el argumento n AND (a & b & c & ... & n), OR (a ∨ b ∨ c ∨ ... ∨ n) se construyen a partir de cadenas de AND y OR de dos argumentos y se escriben en forma abreviada sin paréntesis. Estos, y otros conectivos también, se pueden usar como bloques de construcción para aún más conectivos. Los retóricos, filósofos y matemáticos utilizan tablas de verdad y los 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 el acto matemático 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 los teoremas. De esta manera, los ingenieros han creado una gran cantidad de "lógica combinatoria" (es decir, conectivos sin retroalimentación) como "decodificadores", "codificadores", "puertas multifunción", "lógica mayoritaria", "sumadores binarios", "unidades lógicas aritméticas", etc.
Definiciones
Una definición crea un nuevo símbolo y su comportamiento, a menudo con el propósito de abreviar. Una vez que se presenta la definición, se puede utilizar cualquier forma del símbolo o fórmula equivalente. El siguiente simbolismo = Df sigue la convención de Reichenbach. [15] 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 usarse para sustitución o reemplazo.
- definición de una nueva variable: (c & d) = Df s
- O: ~ (~ a & ~ b) = Df (a ∨ b)
- IMPLICACIÓN: (~ a ∨ b) = Df (a → b)
- XOR: (~ a y b) ∨ (a y ~ b) = Df (a ⊕ b)
- EQUIVALENCIA LÓGICA: ((a → b) & (b → a)) = Df (a ≡ b)
Esquemas de axioma y definición
Las definiciones anteriores para 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 que se muestran (con fines ilustrativos) con letras específicas a , b, c para las variables, mientras que las letras de cualquier variable pueden ir en su lugar siempre que las sustituciones de letras sigan la regla de sustitución a continuación.
- Ejemplo: En la definición (~ a ∨ b) = Df (a → b), se pueden usar otros símbolos de variable 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 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 1 & ~ q 2 ):
- (c & (q 1 & ~ q 2 )) ∨ (p & ~ (c & ~ (q 1 & ~ q 2 )))
Reemplazo : (i) la fórmula 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, está permitido 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)
- Use 2 para reemplazar 0 con (b & ~ b): (a ∨ (b & ~ b))
- (vea a continuación cómo distribuir "a ∨" sobre (b & ~ b), etc.)
Definición inductiva
La presentación clásica de la lógica proposicional (ver Enderton 2002) usa las conectivas. 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 del conjunto es una fórmula,
- es una fórmula siempre que es y
- es una fórmula siempre que y son fórmulas y es uno de los conectivos binarios .
Esta definición inductiva se puede ampliar fácilmente para cubrir 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 X V el conjunto de todas las cadenas de un alfabeto, incluidos los símbolos en V , los paréntesis izquierdo y derecho y todas las conectivas lógicas consideradas. Cada conectivo 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 devoluciones .
- Dadas las cadenas y y z , la operación devoluciones . Hay operaciones similares, , y correspondiente a los otros conectivos binarios.
El conjunto de fórmulas sobre V se define como el subconjunto más pequeño de XX V que contiene V y cerrado en 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. Las "leyes" se pueden verificar fácilmente con tablas de verdad. Para cada ley, la conectiva principal (más externa) está asociada con la equivalencia lógica ≡ o identidad =. Un análisis completo de las 2 n combinaciones de valores de verdad para sus n variables distintas dará como resultado una columna de 1 (T) debajo de esta conectiva. Este hallazgo convierte a cada ley, por definición, en una tautología. Y, para una ley dada, debido a que su fórmula a la izquierda y a la derecha son equivalentes (o idénticas), pueden sustituirse 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 conectivo principal ≡ (columna amarilla etiquetada como "tensa") la fórmula ~ (b ∨ a) se evalúa como (1, 0, 0, 0) bajo la etiqueta "P". A la derecha de "tenso", 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 ≡ debajo de "tenso" se evalúa como (1, 1, 1, 1), es decir, P ≡ Q. Por lo tanto, cualquiera de las fórmulas puede sustituirse por la otra si aparece en una fórmula más grande.
PAG | tenso | Q | ||||||||||||||||||||
B | a | ( | ~ | ( | B | V | a | ) | ≡ | ( | ~ | ( | B | ) | Y | ~ | ( | a | ) | ) | ) | |
0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | |||||||||||
0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | |||||||||||
1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | |||||||||||
1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
Los lectores emprendedores pueden desafiarse a sí mismos para 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 los otros, así como las valoraciones de la tabla de verdad para ∨, & y ~. Un conjunto atribuido a Huntington (1904) (Suppes: 204) utiliza ocho de las leyes que se definen a continuación.
Si se usa en un sistema axiomático, los símbolos 1 y 0 (o T y F) se consideran fórmulas bien formadas y, por lo tanto, obedecen las mismas reglas que las variables. Por lo tanto, las leyes enumeradas a continuación son en realidad esquemas de axiomas , es decir, están en lugar de un número infinito de instancias. Por lo tanto, (x ∨ y) ≡ (y) x) podría usarse en una instancia, (p ∨ 0) ≡ (0 ∨ p) y en otra instancia (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, utilice paréntesis de forma liberal. Sin embargo, a menudo los autores los omiten. Para analizar una fórmula complicada, primero se necesita conocer la antigüedad , o rango , que cada uno de los conectivos (excepto *) tiene sobre los otros conectivos. Para "formar bien" una fórmula, comience con el conectivo con el rango más alto y agregue paréntesis alrededor de sus componentes, luego baje en el rango (prestando mucha atención al alcance del conectivo sobre el cual está trabajando). De mayor a menor, con los signos de predicado ∀x y ∃x, la IDENTIDAD = y los signos aritméticos añadidos para completar: [16]
- ≡
- (EQUIVALENCIA LÓGICA)
- →
- (IMPLICACIÓN)
- Y
- (Y)
- ∨
- (O)
- ~
- (NO)
- ∀x
- (PARA TODOS x)
- ∃x
- (EXISTE UNA x)
- =
- (IDENTIDAD)
- +
- (suma aritmética)
- *
- (multiplicar aritmética)
- '
- (s, sucesor aritmético).
Por lo tanto, la fórmula se puede analizar, pero debido a que NOT no obedece a la ley distributiva, los paréntesis alrededor de la fórmula interna (~ c & ~ 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 Y como O 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))
Omitir paréntesis en cadenas de Y y O : Los conectivos se consideran unarios (una variable, por ejemplo, NOT) y binarios (es decir, dos variables Y, O, IMPLÍCITA). Por ejemplo:
- ((c & d) ∨ (p & c) ∨ (p & ~ d)) arriba debe escribirse (((c & d) ∨ (p & c)) ∨ (p & ~ (d))) o posiblemente ((c & d) ∨ ((p & c) ∨ (p & ~ (d))))
Sin embargo, una demostración de la tabla de verdad muestra que la forma sin los paréntesis adicionales es perfectamente adecuada.
Omitir paréntesis con respecto a una variable única NOT : Mientras que ~ (a) donde a es una sola variable es perfectamente claro, ~ a es adecuado y es la forma habitual en que aparecería este literal . Cuando el NOT está sobre una fórmula con más de un símbolo, los paréntesis son obligatorios, por ejemplo, ~ (a ∨ b).
Leyes distributivas
O distribuye sobre Y y Y distribuye sobre OR. NOT no distribuye sobre AND u OR. Vea a continuación sobre 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))
Leyes de de Morgan
NOT, cuando se distribuye sobre OR o AND, hace algo peculiar (nuevamente, esto se puede verificar con una tabla de verdad):
- Ley de De Morgan para OR: ¬ (a ∨ b) ≡ (¬a ^ ¬b)
- Ley de De Morgan para AND: ¬ (a ^ b) ≡ (¬a ∨ ¬b)
Leyes de absorción
La absorción, en particular la primera, hace 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 ≡, alternativamente ↔ o ⇔) simboliza la asignación de valor o significado. Por lo tanto, 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) tal vez mostrado como ((a & ~ (a)) = Df 0); en otros sistemas, puede derivarse en la siguiente tabla de verdad:
C | tenso | C | |||||||||||
a | ( | ( | a | Y | ~ | ( | a | ) | ) | ≡ | 0 | ) | |
0 | 0 | 0 | 1 | 0 | 1 | 0 | |||||||
1 | 1 | 0 | 0 | 1 | 1 | 0 |
- Conmutación de 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 centro excluido
- Complemento para AND: (a & ~ a) = 0 o (a & ~ a) = F, ley de contradicción
Doble negativo (involución)
- ¬ (¬a) ≡ a
Fórmulas bien formadas (wffs)
Una propiedad clave de las fórmulas es que se pueden analizar de forma única para determinar la estructura de la fórmula en términos de sus variables proposicionales y conectivos lógicos. Cuando las fórmulas se escriben en notación infija , como se indicó anteriormente, se garantiza una legibilidad única mediante el uso apropiado de paréntesis en la definición de fórmulas. Alternativamente, las fórmulas se pueden escribir en notación polaca o en notación polaca inversa , eliminando por completo la necesidad de usar 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 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 izquierdo y derecho, y cualquier segmento inicial no vacío de una fórmula tiene más paréntesis izquierdos que derechos. [17] Este hecho se puede utilizar para proporcionar un algoritmo para analizar fórmulas. Por ejemplo, suponga que una expresión x comienza con. Comenzando después del segundo símbolo, haga coincidir la subexpresión más corta y de x que tenga paréntesis equilibrados. 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 e y en sí mismo es una fórmula. Esta idea se puede utilizar para generar un analizador de descenso recursivo para fórmulas.
Ejemplo de recuento de paréntesis :
Este método ubica como "1" el conector principal , el conector bajo el cual ocurre la evaluación general de la fórmula para los paréntesis más externos (que a menudo se omiten). [18] También ubica el conectivo 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".
comienzo | ( | ( | ( | C | Y | D | ) | V | ( | pag | Y | ~ | ( | ( | C | Y | ~ | ( | D | ) | ) | ) | ) | ) | = | ( | ( | ( | C | Y | D | ) | V | ( | pag | Y | D | ) | ) | V | ( | pag | Y | ~ | ( | C | ) | ) | ) | ) | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
contar | 0 | 1 | 2 | 3 | 3 | 3 | 3 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | 5 | 5 | 5 | 5 | 6 | 6 | 5 | 4 | 3 | 3 | 1 | 1 | 2 | 3 | 4 | 4 | 4 | 4 | 3 | 3 | 4 | 4 | 4 | 4 | 3 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 1 | 0 |
Fórmulas bien formadas versus fórmulas válidas en inferencias
La noción de argumento válido se aplica generalmente a inferencias en argumentos, pero los argumentos se reducen a fórmulas proposicionales y pueden evaluarse de la misma manera que cualquier otra fórmula proposicional. Aquí una inferencia válida significa: "La fórmula que representa la inferencia se evalúa como" verdad "debajo de su conectivo principal, sin importar qué valores de verdad se asignen a sus variables", es decir, la fórmula es una tautología. [19] Es muy posible que una fórmula esté bien formada pero no sea válida . Otra forma de decirlo es: "Estar bien formado es necesario para que una fórmula sea válida, pero no es suficiente ". La única manera de saber si es tanto bien formado y válido es para enviarlo a verificación con una tabla de verdad o por el uso de las "leyes":
- Ejemplo 1: ¿Qué opina uno de la siguiente afirmación difícil de seguir? Es valido? "Si hace sol, pero si la rana croa, entonces no hace sol, entonces es lo mismo que decir que la rana no croa". Convierta esto 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) y ((b) → ~ (a)) ≡ ~ (b))
- Esto está bien formado, pero ¿es válido ? En otras palabras, cuando se evalúe, ¿esto producirá una tautología (todo T) debajo del símbolo de equivalencia lógica ≡? La respuesta es NO, no es válida. Sin embargo, si se reconstruye como una implicación , el argumento es válido.
- "Decir que hace sol, pero si la rana croa, entonces no hace sol, implica que la rana no croa".
- Otras circunstancias pueden estar impidiendo que la rana croe: tal vez una grulla se la comió.
- Ejemplo 2 (de Reichenbach a través de Bertrand Russell):
- "Si los cerdos tienen alas, algunos animales alados son buenos para comer. Algunos animales alados son buenos para comer, así que los cerdos tienen alas".
- (((a) → (b)) & (b) → (a)) está bien formado, pero es un argumento inválido como lo muestra la evaluación roja bajo la implicación principal:
W | GRAMO | arg | |||||||||||||
a | B | ( | ( | ( | a | -> | B | ) | Y | B | ) | -> | a | ) | |
0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | |||||||
0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | |||||||
1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | |||||||
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Conjuntos reducidos de conectivos
Un conjunto de conectivos lógicos se llama completo si cada fórmula proposicional es tautológicamente equivalente a una fórmula con solo los conectivos en ese conjunto. Hay muchos conjuntos completos de conectivos, incluidos, , y . Hay dos conectivos binarios que están completos por sí mismos, correspondientes a NAND y NOR, respectivamente. [20] Algunos pares no están completos, por ejemplo.
El trazo (NAND)
El conectivo binario correspondiente a NAND se llama trazo de Sheffer y se escribe con una barra vertical | o flecha vertical ↑. La integridad de este conectivo se observó en Principia Mathematica (1927: xvii). Dado que está completo por sí solo, todos los demás conectivos se pueden expresar 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 & q ≡ ~ (p | q)
En particular, las conectivas cero-arias (que representa la verdad) y (que representa la falsedad) se puede expresar mediante el trazo:
SI ... ENTONCES ... MÁS
Este conectivo junto con {0, 1}, (o {F, T} o { , }) forma un conjunto completo. A continuación, la IF ... THEN ... ELSE relación (c, b, a) = d representa ((c → b) ∨ (~ c → a)) ≡ ((c y 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: Lo siguiente muestra cómo procedería una demostración basada en un teorema de "(c, b, 1) ≡ (c → b)", debajo de la prueba está su verificación de 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))
- Distribuya "~ c V" sobre (c & b): (((~ c) ∨ c) & ((~ c) ∨ b)
- Ley de la mitad excluida (((~ c) ∨ c) = 1): ((1) & ((~ c) ∨ b))
- Distribuir "(1) &" sobre ((~ c) ∨ b): (((1) & (~ c)) ∨ ((1) & b)))
- Comutividad 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 "tensa" para tautología evalúa la equivalencia lógica (aquí simbolizada por ≡) entre las dos columnas etiquetadas como d. Debido a que las cuatro filas debajo de "tenso" son unos, la equivalencia de hecho representa una tautología.
D | tenso | D | |||||||||||||||||||||||||||||
filas | C | B | a | ( | ( | ( | C | Y | B | ) | V | ( | ~ | ( | C | ) | Y | a | ) | ) | ≡ | ( | ~ | ( | C | ) | V | B | ) | ) | |
0,1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | |||||||||||||||
2,3 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | |||||||||||||||
4,5 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | |||||||||||||||
6,7 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
Formas normales
Una fórmula proposicional arbitraria puede tener una estructura muy complicada. A menudo es conveniente trabajar con fórmulas que tienen 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 forma normal
La reducción a la forma normal es relativamente simple una vez que se prepara una tabla de verdad para la fórmula. Pero los intentos posteriores de minimizar el número de literales (ver más abajo) requieren algunas herramientas: la reducción por las leyes de De Morgan y las tablas de verdad puede ser difícil de manejar, pero los mapas de Karnaugh son muy adecuados para una pequeña cantidad de variables (5 o menos). Existen algunos métodos tabulares sofisticados para circuitos más complejos con múltiples salidas, pero estos están más allá del alcance de este artículo; para obtener más información, consulte el algoritmo de Quine-McCluskey .
Literal, término y alterm
En ingeniería eléctrica, una variable x o su negación ~ (x) se agrupa en una sola noción llamada literal . Una cadena de literales conectados por AND se llama término . Una cadena de literales conectados por OR se llama alterm . Normalmente, el literal ~ (x) se abrevia ~ x. A veces, el símbolo & se omite por completo a la manera de la multiplicación algebraica.
- Ejemplos de
- 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.
- p, q, r, s son variables. (((p & ~ (q)) & r) & ~ (s)) es un altermo. Esto se puede abreviar como (p ∨ ~ q ∨ r ∨ ~ s).
Minterms
De la misma manera que una tabla de verdad de 2 n filas muestra la evaluación de una fórmula proposicional para los 2 n valores posibles de sus variables, n variables produce un mapa de Karnaugh de 2 n- cuadrados (aunque no podamos dibujarlo en su totalidad) realización dimensional). Por ejemplo, 3 variables producen 2 3 = 8 filas y 8 cuadrados de Karnaugh; 4 variables produce 16 filas de tabla de verdad y 16 cuadrados y, por lo tanto, 16 minitérminos . Cada cuadrado del mapa de Karnaugh y su correspondiente evaluación de la tabla de verdad representa un minitérmino.
Cualquier fórmula proposicional se puede reducir a la "suma lógica" (OR) de los minitérminos activos (es decir, "1" o "T"). Cuando está en esta forma, se dice que la fórmula está en forma normal disyuntiva . Pero aunque tiene esta forma, no se minimiza necesariamente con respecto al número de términos o 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", en otras palabras:
- Ejemplo
- cba 2 = c * 2 2 + b * 2 1 + a * 2 0 :
- cba = (c = 1, b = 0, a = 0) = 101 2 = 1 * 2 2 + 0 * 2 1 + 1 * 2 0 = 5 10
Esta numeración se produce porque a medida que uno se mueve hacia abajo en la tabla de una fila a otra, solo una variable a la vez cambia su valor. El código Gray se deriva de esta noción. Esta noción se puede extender a hipercubos tridimensionales y tetradimensionales llamados diagramas de Hasse, donde las variables de cada esquina cambian solo una a la vez a medida que uno se mueve alrededor de los bordes del cubo. Los diagramas de Hasse (hipercubos) aplanados en dos dimensiones son diagramas de Veitch o mapas de Karnaugh (estos son prácticamente lo mismo).
Cuando se trabaja con mapas de Karnaugh, siempre se debe tener en cuenta que el borde superior se "envuelve" con el borde inferior y el borde izquierdo se envuelve alrededor del borde derecho; el diagrama de Karnaugh es en realidad tridimensional o cuatridimensional. objeto aplanado.
equivalente decimal de (c, b, a) | C | B | a | minterm |
---|---|---|---|---|
0 | 0 | 0 | 0 | (~ c & ~ b & ~ a) |
1 | 0 | 0 | 1 | (~ c & ~ b & a) |
3 | 0 | 1 | 1 | (~ c & b & a) |
2 | 0 | 1 | 0 | (~ c & b & ~ a) |
6 | 1 | 1 | 0 | (c & b & ~ a) |
7 | 1 | 1 | 1 | (c & b & a) |
5 | 1 | 0 | 1 | (c & ~ b & a) |
4 | 1 | 0 | 0 | (c & ~ b & ~ a) |
0 | 0 | 0 | 0 | (~ a & ~ b & ~ c) |
Reducción mediante el uso del método del mapa (Veitch, Karnaugh)
Veitch mejoró la noción de diagramas de Venn convirtiendo los círculos en cuadrados contiguos, y Karnaugh simplificó el diagrama de Veitch convirtiendo los minitérminos, escritos en su forma literal (por ejemplo, ~ abc ~ d) en números. [21] El método procede de la siguiente manera:
Producir la tabla de verdad de la fórmula
Genere la tabla de verdad de la fórmula. Numere sus filas usando los equivalentes binarios de las variables (generalmente solo secuencialmente de 0 a 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 minitérmino y estos pueden ser 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 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).
fila | Minterms | pag | D | C | ( | ( | C | Y | D | ) | ∨ | ( | pag | Y | ~ | ( | ( | C | Y | ~ | ( | D | ) | ) | ) | ) | ) | Minitérminos activos | Fórmula en forma conjuntiva normal |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | (~ p & ~ d & ~ c) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | ||||||||||||||
1 | (~ p & ~ d & c) | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | ||||||||||||||
2 | (~ p & d & ~ c) | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | ||||||||||||||
3 | (~ p & d & c) | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | (~ p & d & c) | |||||||||||||
4 | (p & ~ d & ~ c) | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | (~ p & d & c) | |||||||||||||
5 | (p & ~ d & c) | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | ||||||||||||||
6 | (p & d & ~ c) | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | (p & d & ~ c) | |||||||||||||
7 | (p & d & c) | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | (p & d & c) | |||||||||||||
q | = (~ p & d & c) ∨ (~ p & d & c) ∨ (p & d & ~ c) ∨ (p & d & c) |
Crea el mapa de Karnaugh de la fórmula
Use los valores de la fórmula (por ejemplo, "p") encontrados por el método de la tabla de verdad y colóquelos en sus respectivos cuadrados de Karnaugh (asociados) (estos están numerados según la convención del código Gray). Si los valores de "d" para "no importa" aparecen en la tabla, esto agrega flexibilidad durante la fase de reducción.
Reducir minitérminos
Los términos mínimos de 1-cuadrados adyacentes (contiguos) (T-cuadrados) 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 cuadrado de 2 x 2 (incluso las cuatro esquinas representan contiguos cuadrados) pierden dos literales, ocho cuadrados en un rectángulo pierden 3 literales, etc. (Uno busca el cuadrado o rectángulos más grandes e ignora los cuadrados o rectángulos más pequeños contenidos totalmente dentro de él). Este proceso continúa hasta que se tienen en cuenta todos los cuadrados contiguos, momento en el que se minimiza la fórmula proposicional.
Por ejemplo, los cuadrados n. ° 3 y n. ° 7 lindan. Estos dos cuadrados contiguos pueden perder un literal (por ejemplo, "p" de los cuadrados 3 y 7), cuatro cuadrados de un rectángulo o cuadrado pierden dos literales, ocho cuadrados de un rectángulo pierden 3 literales, etc. cuadrado o rectángulos). Este proceso continúa hasta que se tienen en cuenta todos los cuadrados contiguos, momento en el que se dice que la fórmula proposicional se minimiza.
Ejemplo: el método del mapa generalmente se realiza mediante inspección. El siguiente ejemplo expande el método algebraico para mostrar el "truco" detrás de la combinación de términos en un mapa de Karnaugh:
- Los términos mínimos # 3 y # 7 lindan, # 7 y # 6 lindan, y # 4 y # 6 lindan (porque los bordes de la mesa se envuelven alrededor). Entonces cada uno de estos pares se puede reducir.
Observe que por la ley de idempotencia (A ∨ A) = A, podemos crear más términos. Luego, por asociación y leyes distributivas, las variables a desaparecer pueden emparejarse y luego "desaparecer" con la Ley de contradicción (x & ~ x) = 0. A continuación se utilizan corchetes [y] solo para realizar un seguimiento de los términos; no tienen un significado especial:
- Ponga la fórmula en forma conjuntiva normal con la fórmula 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))
Verifique la reducción con una tabla de verdad
fila | Minterms | pag | D | C | ( | ( | D | Y | C | ) | ∨ | ( | pag | Y | D | ) | ∨ | ( | pag | Y | ~ | ( | C | ) | ) |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | (~ p & ~ d & ~ c) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | |||||||||
1 | (~ p & ~ d & c) | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | |||||||||
2 | (~ p & d & ~ c) | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | |||||||||
3 | (~ p & d & c) | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | |||||||||
4 | (p & ~ d & ~ c) | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | |||||||||
5 | (p & ~ d & c) | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | |||||||||
6 | (p & d & ~ c) | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | |||||||||
7 | (p & d & c) | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | |||||||||
q |
Proposiciones impredicativas
Dados los siguientes ejemplos como definiciones, ¿qué se hace con el razonamiento posterior?
- (1) "Esta oración es simple". (2) "Esta oración es compleja y está unida por AND".
Luego asigne la variable "s" a la oración más a la izquierda "Esta oración es simple". Defina "compuesto" c = "no simple" ~ s, y asigne c = ~ s a "Esta oración es compuesta"; asigne "j" a "Es [esta oración] unida por AND". La segunda oración se puede expresar como:
- (NO (s) Yj)
Si los valores de verdad deben colocarse en las oraciones c = ~ syj, entonces todas son claramente FALSEDADES: por ejemplo, "Esta oración es compleja" es una FALSEDAD (es simple , por definición). Entonces 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 propiedad P. [22] El mejor consejo para un retórico o uno involucrado en el análisis deductivo es evitar las definiciones impredicativas pero al mismo tiempo estar atento a ellas porque de hecho pueden crear paradojas. Los ingenieros, por otro lado, los ponen a trabajar en forma de fórmulas proposicionales con retroalimentación.
Fórmula proposicional con "retroalimentación"
La noción de una fórmula proposicional que aparece 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 hay ninguna estipulación (ya sea sistemas axiomáticos o de tablas de verdad de objetos y relaciones) que prohíba que esto suceda. [23]
El caso más simple ocurre cuando una fórmula OR se convierte en una de sus propias entradas, por ejemplo, p = q. Comience 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 conectivo OR; esta definición de q es, por tanto, impredicativa . Cualquiera de dos condiciones puede resultar: [24] oscilación o memoria.
Ayuda pensar en la fórmula como una caja negra . Sin conocimiento de lo que está sucediendo "dentro" de la fórmula - "caja" desde el exterior, parecería que la salida ya no es una función únicamente de las entradas. Es decir, a veces uno mira q y ve 0 y otras veces 1. Para evitar este problema hay que conocer el estado (condición) de la variable "oculta" p dentro de la caja (es decir, el valor de q realimentada y asignada pag). Cuando esto se conoce, la aparente inconsistencia desaparece.
Para comprender [predecir] el comportamiento de fórmulas con retroalimentación se requiere el análisis más sofisticado de circuitos secuenciales . Las fórmulas proposicionales con retroalimentación conducen, en su forma más simple, a máquinas de estados; también conducen a recuerdos en forma de cintas de Turing y contadores de contra-máquinas. A partir de combinaciones de estos elementos, se puede construir cualquier tipo de modelo computacional acotado (por ejemplo , máquinas de Turing , máquinas contadoras , máquinas registradoras , computadoras Macintosh , etc.).
Oscilación
En el caso abstracto (ideal), la fórmula oscilante más simple es un NO realimentado a sí mismo: ~ (~ (p = q)) = q. El análisis de una fórmula proposicional abstracta (ideal) en una tabla de verdad revela una inconsistencia tanto para los casos p = 1 como para p = 0: cuando p = 1, q = 0, esto no puede ser porque p = q; lo mismo para cuando p = 0 y q = 1.
q | |||||||
---|---|---|---|---|---|---|---|
pag | ~ | ( | pag | ) | = q | ||
0 | 1 | 0 | 1 | q & p inconsistente | |||
1 | 0 | 1 | 0 | q & p inconsistente |
Oscilación con retardo : Si se inserta un retardo [25] (ideal o no ideal) en la fórmula abstracta entre pyq, entonces p oscilará entre 1 y 0: 101010 ... 101 ... ad infinitum . Si cualquiera de los retardos y 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 caen fuera de las matemáticas y en la ingeniería.
El análisis requiere que se inserte un retardo y luego se corte el bucle entre el retardo y la entrada "p". El retardo debe verse como una especie de proposición que tiene "qd" (q-retardado) como salida para "q" como entrada. Esta nueva propuesta agrega otra columna a la tabla de verdad. La inconsistencia está ahora entre "qd" y "p" como se muestra en rojo; dos estados estables resultantes:
q | ||||||||
---|---|---|---|---|---|---|---|---|
qd | pag | ( | ~ | ( | pag | ) | = q | |
0 | 0 | 1 | 0 | 1 | estado 1 | |||
0 | 1 | 0 | 1 | 0 | qd & p inconsistente | |||
1 | 0 | 1 | 0 | 1 | qd & p inconsistente | |||
1 | 1 | 0 | 1 | 0 | estado 0 |
Memoria
Sin demora, las inconsistencias deben eliminarse de un análisis de tabla de verdad. Con la noción de "retardo", esta condición se presenta como una inconsistencia momentánea entre la variable de salida de realimentación q y p = q retardada .
Una tabla de verdad revela las filas donde ocurren inconsistencias entre p = q retrasado en la entrada yq en la salida. Después de "romper" la retroalimentación, [26] 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 ahora independiente py se anotan las inconsistencias entre pyq (es decir, p = 0 junto con q = 1, o p = 1 yq = 0); cuando la "línea" se "rehace", ambos 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 una vez invertida
Acerca de los resultados de memoria más simple cuando la salida de un OR se retroalimenta a una de sus entradas, en este caso la salida "q" retroalimenta a "p". Dado que la fórmula se evalúa (inicializa) primero con p = 0 & q = 0, se "volteará" una vez cuando se "establezca" por s = 1. A partir de entonces, la salida "q" mantendrá "q" en la condición "invertida" (estado q = 1). Este comportamiento, ahora dependiente del tiempo, se muestra en el diagrama de estado a la derecha del cambio único .
q | ||||||||
---|---|---|---|---|---|---|---|---|
pag | s | ( | s | ∨ | pag | ) | = q | |
0 | 0 | 0 | 0 | 0 | 0 | estado 0, s = 0 | ||
0 | 1 | 1 | 1 | 0 | q & p inconsistente | |||
1 | 0 | 0 | 1 | 1 | 1 | estado 1 con s = 0 | ||
1 | 1 | 1 | 1 | 1 | 1 | estado 1 con s = 1 |
Memoria flip-flop
El siguiente caso más simple es el flip-flop "set-reset" que se muestra debajo del flip-flip único. Dado que r = 0 & s = 0 y q = 0 al principio, se "establece" (s = 1) de una manera similar a la de una sola vez. Sin embargo, tiene una disposición para "restablecer" q = 0 cuando "r" = 1. Y ocurre una complicación adicional si ambos set = 1 y reset = 1. En esta fórmula, el conjunto = 1 fuerza la salida q = 1 por lo que cuando y si (s = 0 & r = 1) el flip-flop se reiniciará. O, si (s = 1 & r = 0) se establecerá el flip-flop. En el caso abstracto (ideal) en el que s = 1 ⇒ s = 0 & r = 1 ⇒ r = 0 simultáneamente, la fórmula q será indeterminada (indecidible). Debido a retrasos en "real" OR, AND y NOT, el resultado será desconocido al principio, pero a partir de entonces predecible.
q | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
pag | s | r | ( | s | ∨ | ( | pag | Y | ~ | ( | r | ) | ) | ) | = q | |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | estado 0 con (s = 0 & r = 0) | ||||||
0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | estado 0 con (s = 0 & r = 1) | ||||||
0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | q & p inconsistente | |||||||
0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | q & p inconsistente | |||||||
1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | estado 1 con (s = 0 & r = 0) | ||||||
1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | q & p inconsistente | |||||||
1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | estado 1 con (s = 1 & r = 0) | ||||||
1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | estado 1 con s & r simultáneamente 1 |
Memoria flip-flop sincronizada
La fórmula conocida como memoria "flip-flop sincronizado" ("c" es el "reloj" y "d" es los "datos") se da a continuación. Funciona de la siguiente manera: Cuando c = 0, los datos d (0 o 1) no pueden "pasar" para afectar la salida q. Cuando c = 1, los datos d "pasan" y la salida q "sigue" el valor de d. Cuando c pasa de 1 a 0, el último valor de los datos permanece "atrapado" en la salida "q". Siempre que c = 0, d puede cambiar el valor sin que q cambie.
- Ejemplos de
- ((c & d) ∨ ( p & (~ (c & ~ (d)))) = q , pero ahora sea p = q:
- ((c & d) ∨ ( q & (~ (c & ~ (d)))) = q
El diagrama de estado tiene una forma similar al diagrama de estado del flip-flop, pero con un etiquetado diferente en las transiciones .
s | q | w | v | r | tu | |||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
fila | q | D | C | ( | ( | C | Y | D | ) | ∨ | ( | q | Y | ~ | ( | ( | C | Y | ~ | ( | D | ) | ) | ) | ) | ) | = q | Descripción |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | estado 0 con (s = 0 & r = 0), 0 está atrapado | ||||||||||||
1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | estado 0 con (d = 0 & c = 1): q = 0 sigue a d = 0 | ||||||||||||
2 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | estado 0 con (d = 1 & r = 0), 0 está atrapado | ||||||||||||
3 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | q & p inconsistente | |||||||||||||
4 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | estado 1 con (d = 0 & c = 0), 1 está atrapado | ||||||||||||
5 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | q & p inconsistente | |||||||||||||
6 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | estado 1 con (d = 1 & c = 0), 1 está atrapado | ||||||||||||
7 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | estado 1 con (d = 1 & c = 1): q = 1 sigue a d = 1 |
Desarrollo historico
Bertrand Russell (1912: 74) enumera tres leyes del pensamiento que se derivan de Aristóteles : (1) La ley de la identidad : "Todo lo que es, es", (2) La ley de la no contradicción : "Nada puede ser y no ser al mismo tiempo". , y (3) La ley del medio excluido : "Todo debe ser o no ser".
- Ejemplo: Aquí O es una expresión sobre el SER o CALIDAD de un objeto:
- Ley de identidad: O = O
- Ley de contradicción: ~ (O & ~ (O))
- Ley del medio excluido: (O ∨ ~ (O))
El uso de la palabra "todo" en la ley de los medios excluidos hace que la expresión de Russell de esta ley esté abierta al debate. Si se restringe a una expresión sobre SER o CALIDAD con referencia a una colección finita de objetos (un "universo de discurso" finito) - cuyos miembros pueden ser investigados uno tras otro por la presencia o ausencia de la aserción - entonces la ley se considera intuicionistamente apropiado. Por lo tanto, una afirmación como: "Este objeto debe SER o NO SER (en la colección)", o "Este objeto debe tener esta CALIDAD o NO tener esta CALIDAD (en relación con los objetos de la colección)" es aceptable. Vea más en el diagrama de Venn .
Aunque un cálculo proposicional se originó con Aristóteles, la noción de álgebra aplicada a proposiciones tuvo que esperar hasta principios del siglo XIX. En una reacción (adversa) a la tradición de 2000 años de los silogismos de Aristóteles , el Ensayo de John Locke sobre la comprensión humana (1690) utilizó la palabra semiótica (teoría del uso de símbolos). En 1826, Richard Whately había analizado críticamente la lógica silogística con simpatía hacia la semiótica de Locke. El trabajo de George Bentham (1827) resultó en la noción de "cuantificación del predicado" (1827) (hoy en día simbolizado como ∀ for "para todos"). Una "disputa" instigada por William Hamilton sobre una disputa de prioridad con Augustus De Morgan "inspiró a George Boole a escribir sus ideas sobre lógica y 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 única de Boole fue [la] ley [x n = x] para la lógica: declaró que los actos mentales de elegir la propiedad x y elegir x una y otra vez es lo mismo que elegir x una vez ... Como consecuencia de ello formó las ecuaciones x • (1-x) = 0 yx + (1-x) = 1 que para él expresaban respectivamente la ley de la contradicción y la ley del medio excluido "(p. xxviiff). Para Boole, "1" era el universo del discurso y "0" no era nada.
La empresa masiva de Gottlob Frege (1879) resultó en un cálculo formal de proposiciones, pero su simbolismo es tan desalentador que tuvo poca influencia excepto en una persona: Bertrand Russell . Primero, como alumno de Alfred North Whitehead , estudió el trabajo de Frege y sugirió una enmienda (famosa y notoria) al respecto (1904) en torno al problema de una antinomia que descubrió en el tratamiento de Frege (cf. la paradoja de Russell ). El trabajo de Russell condujo a una colaboración con Whitehead que, en el año 1912, produjo el 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 primitivas. En términos de estas nociones, definen IMPLICACIÓN → (def. * 1.01: ~ p ∨ q), luego AND (def. * 3.01: ~ (~ p ∨ ~ q)), luego EQUIVALENCIA p ← → q (* 4.01: ( p → q) y (q → p)).
- Henry M. Sheffer (1921) y Jean Nicod demuestran que sólo un conectivo, el "trazo" | es suficiente para expresar todas las fórmulas proposicionales.
- Emil Post (1921) desarrolla el método de análisis de la tabla de verdad en su "Introducción a una teoría general de proposiciones elementales". Observa el derrame cerebral de Nicod | .
- Whitehead y Russell agregan una introducción a su re-publicación de 1927 de PM agregando, en parte, un tratamiento favorable del "derrame cerebral".
Lógica de cálculo y conmutación :
- William Eccles y FW Jordan (1919) describen un "relé de disparo" hecho de un tubo de vacío.
- George Stibitz (1937) inventa el sumador binario utilizando relés mecánicos. Construye esto en la mesa de su cocina.
- Ejemplo: Dados los bits binarios a i y b i y el arrastre (c_in i ), su suma Σ i y el arrastre (c_out i ) son:
- ((a yo XOR b yo ) XOR c_en yo ) = Σ yo
- (a i & b i ) ∨ c_in i ) = c_out i ;
- Alan Turing construye un multiplicador mediante relés (1937-1938). Tiene que enrollar manualmente sus propias bobinas de relé para hacer esto.
- Los libros de texto sobre "circuitos de conmutación" aparecen a principios de la década de 1950.
- Willard Quine 1952 y 1955, EW Veitch 1952 y M. Karnaugh (1953) desarrollan métodos de mapas 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 al pie
- ↑ Hamilton 1978: 1
- ^ Principia Mathematica (PM) p. 91 evita "el" porque requieren un "objeto de sensación" bien definido; estipulan el uso de "esto"
- ^ (cursiva agregada) Reichenbach [ aclaración necesaria ] p.80.
- ^ Tarski p.54-68. Suppes llama a la IDENTIDAD una "nueva regla de inferencia" y tiene un breve desarrollo en torno a ella; Robbin, Bender y Williamson y Goodstein presentan el signo y su uso sin comentarios ni explicaciones. Hamilton p. 37 emplea dos signos ≠ y = con respecto a la valoración de una fórmula en un cálculo formal. Kleene p. 70 y Hamilton p. 52 ubicarlo en el cálculo de predicados, en particular con respecto a la aritmética de números naturales.
- ↑ Los empíricos evitan la noción deconocimiento a priori (incorporado, nacido con). Los "reduccionistas radicales" como John Locke y David Hume "sostenían que toda idea debe originarse directamente en la experiencia sensorial o bien estar compuesta de ideas que se originan de esta manera"; citado de Quine reimpreso en 1996 The Emergence of Logical Empriricism , 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: Dada una señal S y un umbral "thr", reste "thr" de S y sustituya esta diferencia d por una función sigmoidea : Para grandes "ganancias" k, p. Ej. k = 100, 1 / (1 + e −k * d ) = 1 / (1 + e −k * (S-thr) ) = {≃0, ≃1}. [ aclaración necesaria ] Por ejemplo, si "La puerta está ABAJO" significa "La puerta está a menos del 50% del camino hacia arriba", 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, el 1 y el 0 digitales se definen en rangos que no se superponen, por ejemplo, {"1" = + 5 / + 0,2 / −1,0 voltios, 0 = + 0,5 / −0,2 voltios} [ aclaración necesaria ] . Cuando un valor cae fuera del rango (s) definido (s), 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 es peculiar; de hecho (a "+" b) = (a + (b - a * b)) donde "+" es la "suma lógica" pero + y - son las verdaderas contrapartes aritméticas. Ocasionalmente, las cuatro nociones aparecen en una fórmula : A Y B = 1/2 * (A más B menos (A XOR B)] (cf p. 146 en John Wakerly 1978, Códigos de detección de errores, Circuitos y aplicaciones de autocomprobación , North-Holland, Nueva York, ISBN 0 -444-00259-6 pbk.)
- ^ Una mirada cuidadosa a su mapa de Karnaugh muestra que SI ... ENTONCES ... ELSE también se puede expresar, de una manera bastante indirecta, en términos de dos OR exclusivos: ((b AND (c XOR a)) O (a Y (c XOR b))) = d.
- ^ Robbin p. 3.
- ^ Rosenbloom p. 30 y p. 54ff discute este problema de implicación con cierta extensión. La mayoría de los filósofos y matemáticos simplemente aceptan la definición material como se dio anteriormente. Pero algunos no, incluidos los intuicionistas ; lo consideran una forma de la ley del medio excluido mal aplicada.
- ↑ De hecho,la definición que Kleene da al operador CASE requiere unaselecció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 citas en su "18. Identidad de las cosas e identidad de sus designaciones; uso de comillas" p. 58ff.
- ^ Hamilton p. 37. Bender y Williamson p. 29 dice "En lo que sigue, reemplazaremos" igual "con el símbolo" ⇔ "(equivalencia) que se usa generalmente en lógica. Usamos el más familiar" = "para asignar significado y valores".
- ^ Reichenbach p. 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' tiene el mismo significado que la fórmula '(c & d)'".
- ^ Rosenbloom 1950: 32. Kleene 1952: 73-74 clasifica los 11 símbolos.
- ^ cf Minsky 1967: 75, sección 4.2.3 "El método de recuento de paréntesis". Minsky presenta una máquina de estados que hará el trabajo, y mediante el uso de inducción (definición recursiva) Minsky demuestra el "método" y presenta un teorema como resultado. Una "gramática de paréntesis" completamente generalizada requiere una máquina de estados infinitos (por ejemplo, una máquina de Turing) para hacer el conteo.
- ^ Robbin p. 7
- ^ cf Reichenbach p. 68 para una discusión más complicada: "Si la inferencia es válida y las premisas son verdaderas, la inferencia se llama concluyente .
- ^ Además de los tres primeros, Hamilton pp.19-22 analiza las lógicas construidas a partir de sólo | (NAND) y ↓ (NOR).
- ^ Wickes 1967: 36 y siguientes. Wickes ofrece un buen ejemplo de 8 de los mapas de 2 x 4 (mapas de 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 8 = 256 mapas 2x4, y un mapa arbitrario de 4 variables podría representar cualquiera de 2 16 = 65,536 evaluaciones de fórmulas diferentes, escribir cada una 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 continuó afirmando 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 del extremo superior (lub) u de M . Dado un corte de Dedekind de la recta numérica C y las dos partes en las que se corta 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 . Así, la definición de u , un elemento de C , se define en términos de la totalidad C y esto hace que su definición sea impredicativa. Kleene afirma que los intentos de argumentar esto se pueden utilizar para mantener las definiciones impredicativas en las paradojas (Kleene 1952: 43).
- ^ McCluskey comenta que "se podría argumentar que el análisis aún está incompleto porque no se ha obtenido la palabra declaración" Las salidas son iguales a los valores anteriores de las entradas "; continúa descartando tales preocupaciones porque "el inglés no es un idioma formal en un sentido matemático, [y] no es realmente posible tener unprocedimiento formal para obtener declaraciones de palabras" (p. 185).
- ^ Más precisamente, dada suficiente "ganancia de bucle",se producirá oscilación o memoria (cf. McCluskey p. 191-2). En sistemas matemáticos abstractos (idealizados), la ganancia de bucle adecuada no es un problema.
- ↑ La noción de retraso y el principio de causalidad local causada en última instancia por la velocidad de la luz aparece en Robin Gandy (1980), "Church's thesis and Principles for Mechanisms", en J. Barwise, HJ Keisler y K. Kunen, eds. , The Kleene Symposium , North-Holland Publishing Company (1980) 123-148. Gandy consideró que éste 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. 135). Gandy eraalumno y amigo cercano de Alan Turing .
- ^ McKlusky p. 194-5 discute "romper el bucle" e inserta "amplificadores" para hacer esto; Wickes (p. 118-121) analiza la inserción de retrasos. McCluskey pág. 195ff discute el problema de las "carreras" causadas por retrasos.
Referencias
- Bender, Edward A. y Williamson, S. Gill , 2005, Un curso corto en matemáticas discretas , Publicaciones de Dover, Mineola NY, ISBN 0-486-43946-1 . Este texto se utiliza en un "curso de dos trimestres [ciencias de la computación] de división inferior" en UC San Diego.
- Enderton, HB , 2002, Una introducción matemática a la lógica. Harcourt / Academic Press. ISBN 0-12-238452-0
- Goodstein, RL , (Pergamon Press 1963), 1966, (Dover edition 2007), Boolean Algebra , Dover Publications, Inc. Minola, Nueva York, ISBN 0-486-45894-6 . Énfasis en la noción de "álgebra de clases" con símbolos de la teoría de conjuntos como ∩, ∪, '(NOT), ⊂ (IMPLIES). Posteriormente Goldstein los reemplaza con &, ∨, ¬, → (respectivamente) en su tratamiento de "Lógica de oraciones" 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, Basil, ISBN 978-0-8176-5456-6 (Boston).
- AG Hamilton 1978, Lógica para matemáticos , Cambridge University Press, Cambridge Reino Unido, ISBN 0-521-21838-1 .
- EJ 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 tarjeta de catálogo de la Biblioteca del Congreso 65-17394. McCluskey fue alumno de Willard Quine y desarrolló algunos teoremas notables con Quine y por su cuenta. Para aquellos interesados en la historia, el libro contiene una gran cantidad de referencias.
- Marvin L. Minsky 1967, Computación: Máquinas finitas e infinitas , Prentice-Hall, Inc, Englewood Cliffs, Nueva Jersey. Sin ISBN. Número de tarjeta de catálogo de la Biblioteca del Congreso 67-12342. Útil especialmente para la computabilidad, además de buenas fuentes.
- Paul C. Rosenbloom 1950, Dover edition 2005, The Elements of Mathematical Logic , Dover Publications, Inc., Mineola, Nueva York, ISBN 0-486-44617-4 .
- 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 de Dover de 1999), Introducción a la lógica , Publicaciones de Dover, Inc., Mineola, Nueva York. ISBN 0-486-40687-3 (pbk.). Este libro está impreso y disponible.
- En su página 204, en una nota al pie, hace referencia a su conjunto de axiomas a EV Huntington , "Conjuntos de postulados independientes para el álgebra de la lógica", Transactions of the American Mathematical Society, vol. 5 91904) págs.288-309.
- Alfred Tarski 1941 (edición de 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 (pbk.). Este libro está impreso y disponible.
- Jean van Heijenoort 1967, tercera impresión con enmiendas 1976, From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 , Harvard University Press, Cambridge, Massachusetts. ISBN 0-674-32449-8 (pbk.) Se pueden encontrar 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), Post (1921) aquí.
- Alfred North Whitehead y Bertrand Russell 1927 2a 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 segunda edición de 1927, HM Sheffer 1921 y M. Jean Nicod (sin año citado) llamaron la atención de Russell y Whitehead que lo que ellos consideraban sus proposiciones primitivas (conectivas) podrían reducirse a un single |, hoy en día conocido como el "trazo" o NAND (NO-Y, NI ... NI ...). Russell-Whitehead discute esto en su "Introducción a la Segunda Edición" y hace 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 tarjeta de catálogo de la Biblioteca del Congreso: 68-21185. La presentación rigurosa de los métodos de análisis y síntesis de la ingeniería, hace referencia a McCluskey 1965. A diferencia de Suppes, la presentación de Wickes del "álgebra booleana" comienza con un conjunto de postulados de naturaleza de tabla de verdad y luego deriva los teoremas habituales de ellos (p. 18ss).
enlaces externos
- Medios relacionados con la fórmula proposicional en Wikimedia Commons