Una tabla de verdad es una tabla matemática utilizada en lógica, específicamente en relación con el álgebra booleana , las funciones booleanas y el cálculo proposicional, que establece los valores funcionales de las expresiones lógicas en cada uno de sus argumentos funcionales, es decir, para cada combinación de valores tomados. por sus variables lógicas . [1] En particular, las tablas de verdad se pueden usar para mostrar si una expresión proposicional es verdadera para todos los valores de entrada legítimos, es decir, lógicamente válida .
Una tabla de verdad tiene una columna para cada variable de entrada (por ejemplo, P y Q) y una columna final que muestra todos los resultados posibles de la operación lógica que representa la tabla (por ejemplo, P XOR Q). Cada fila de la tabla de verdad contiene una posible configuración de las variables de entrada (por ejemplo, P = verdadero Q = falso) y el resultado de la operación para esos valores. Consulte los ejemplos a continuación para obtener más aclaraciones. A Ludwig Wittgenstein se le atribuye generalmente el mérito de haber inventado y popularizado la tabla de verdad en su Tractatus Logico-Philosophicus , que se completó en 1918 y se publicó en 1921. [2] Este sistema también fue propuesto independientemente en 1921 por Emil Leon Post . [3]También se ha encontrado una iteración incluso anterior de la tabla de verdad en manuscritos inéditos de Charles Sanders Peirce de 1893, que anteceden a ambas publicaciones en casi 30 años. [4]
Operaciones unarias [ editar ]
Hay 4 operaciones unarias:
- Siempre cierto
- Nunca es cierto, unario falsum
- Identidad unaria
- Negación unaria
Lógico verdadero [ editar ]
El valor de salida es siempre verdadero, independientemente del valor de entrada de p
| pag | T |
|---|---|
| T | T |
| F | T |
Falso lógico [ editar ]
El valor de salida nunca es verdadero: es decir, siempre falso, independientemente del valor de entrada de p
| pag | F |
|---|---|
| T | F |
| F | F |
Identidad lógica [ editar ]
La identidad lógica es una operación sobre un valor lógico p, para el cual el valor de salida sigue siendo p.
La tabla de verdad para el operador de identidad lógica es la siguiente:
| pag | pag |
|---|---|
| T | T |
| F | F |
Negación lógica [ editar ]
La negación lógica es una operación sobre un valor lógico , típicamente el valor de una proposición , que produce un valor verdadero si su operando es falso y un valor falso si su operando es verdadero.
La tabla de verdad para NOT p (también escrita como ¬p , Np , Fpq o ~ p ) es la siguiente:
| pag | ¬p |
|---|---|
| T | F |
| F | T |
Operaciones binarias [ editar ]
Hay 16 posibles funciones de verdad de dos variables binarias :
Tabla de verdad para todos los operadores lógicos binarios [ editar ]
Aquí hay una tabla de verdad ampliada que ofrece definiciones de todas las posibles funciones de verdad de dos variables booleanas P y Q: [nota 1]
| pag | q | F 0 | NOR 1 | ↚ 2 | ¬p 3 | ↛ 4 | ¬q 5 | XOR 6 | NAND 7 | Y 8 | XNOR 9 | q 10 | → 11 | p. 12 | ← 13 | O 14 | T 15 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| T | T | F | F | F | F | F | F | F | F | T | T | T | T | T | T | T | T | ||
| T | F | F | F | F | F | T | T | T | T | F | F | F | F | T | T | T | T | ||
| F | T | F | F | T | T | F | F | T | T | F | F | T | T | F | F | T | T | ||
| F | F | F | T | F | T | F | T | F | T | F | T | F | T | F | T | F | T | ||
| Com | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | |||||||||||
| Assoc | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | |||||||||||
| Adj. | F 0 | NOR 1 | ↛ 4 | ¬q 5 | ↚ 2 | ¬p 3 | XOR 6 | NAND 7 | Y 8 | XNOR 9 | p. 12 | ← 13 | q 10 | → 11 | O 14 | T 15 | |||
| Neg | T 15 | O 14 | ← 13 | p. 12 | → 11 | q 10 | XNOR 9 | Y 8 | NAND 7 | XOR 6 | ¬q 5 | ↛ 4 | ¬p 3 | ↚ 2 | NOR 1 | F 0 | |||
| Doble | T 15 | NAND 7 | → 11 | ¬p 3 | ← 13 | ¬q 5 | XNOR 9 | NOR 1 | O 14 | XOR 6 | q 10 | ↚ 2 | p. 12 | ↛ 4 | Y 8 | F 0 | |||
| L id | F | F | T | T | T, F | T | F | ||||||||||||
| Deshacerse | F | F | T | T | T, F | T | F | ||||||||||||
dónde
- T = verdadero.
- F = falso.
- El Com fila indica si un operador, op , es conmutativa - P op Q = Q op P .
- La fila Assoc indica si un operador, op , es asociativo - (P op Q) op R = P op (Q op R) .
- La fila Adj muestra el operador op2 tal que P op Q = Q op2 P
- La fila Neg muestra el operador op2 tal que P op Q = ¬ (Q op2 P)
- La fila Dual muestra la operación dual obtenida al intercambiar T con F y AND con OR.
- Los L id fila muestra del operador identidades izquierda si tiene algún valores - I tal que me op Q = Q .
- El ID R fila muestra del operador identidades correctas si tiene algún valores - I tal que P op i = P . [nota 2]
Las cuatro combinaciones de valores de entrada para p, q, se leen por fila en la tabla anterior. La función de salida para cada combinación p, q, se puede leer, por fila, en la tabla.
Clave:
La siguiente tabla está orientada por columnas, en lugar de por filas. Hay cuatro columnas en lugar de cuatro filas, para mostrar las cuatro combinaciones de p, q, como entrada.
p : TTFF
q : TFTF
Hay 16 filas en esta clave, una fila para cada función binaria de las dos variables binarias, p, q. Por ejemplo, en la fila 2 de esta Clave, el valor de la no implicación inversa (' ') es únicamente T, para la columna denotada por la combinación única p = F, q = T; mientras que en la fila 2, el valor de esa ' ' operación es F para las tres columnas restantes de p, q. La fila de salida para es entonces
2: FFTF
y la tecla de 16 filas [5] es
| [5] | operador | Nombre de la operación | ||
|---|---|---|---|---|
| 0 | (FFFF) (p, q) | ⊥ | falso , Opq | Contradicción |
| 1 | (FFFT) (p, q) | NI | p ↓ q , Xpq | NOR lógico |
| 2 | (FFTF) (p, q) | ↚ | p ↚ q , Mpq | No implicación inversa |
| 3 | (FFTT) (p, q) | ¬p , ~ p | ¬p , Np , Fpq | Negación |
| 4 | (FTFF) (p, q) | ↛ | p ↛ q , Lpq | No implicación material |
| 5 | (FTFT) (p, q) | ¬q , ~ q | ¬Q , Nq , GPQ | Negación |
| 6 | (FTTF) (p, q) | XOR | p ⊕ q , Jpq | Disyunción exclusiva |
| 7 | (FTTT) (p, q) | NAND | p ↑ q , Dpq | NAND lógica |
| 8 | (TFFF) (p, q) | Y | p ∧ q , Kpq | Conjunción lógica |
| 9 | (TFFT) (p, q) | XNOR | p Si y solo si q , Epq | Bicondicional lógico |
| 10 | (TFTF) (p, q) | q | q , Hpq | Función de proyección |
| 11 | (TFTT) (p, q) | p → q | si p entonces q , Cpq | Implicación material |
| 12 | (TTFF) (p, q) | pag | p , Ipq | Función de proyección |
| 13 | (TTFT) (p, q) | p ← q | p si q , Bpq | Implicación inversa |
| 14 | (TTTF) (p, q) | O | p ∨ q , Apq | Disyunción lógica |
| 15 | (TTTT) (p, q) | ⊤ | cierto , Vpq | Tautología |
Los operadores lógicos también se pueden visualizar mediante diagramas de Venn .
Conjunción lógica (Y) [ editar ]
La conjunción lógica es una operación sobre dos valores lógicos , normalmente los valores de dos proposiciones , que produce un valor verdadero si ambos operandos son verdaderos.
La tabla de verdad para p Y q (también escrita como p ∧ q , Kpq , p & q o p q ) es la siguiente:
| pag | q | p ∧ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
En términos del lenguaje ordinario, si tanto p como q son verdaderas, entonces la conjunción p ∧ q es verdadera. Para todas las demás asignaciones de valores lógicos ap y q, la conjunción p ∧ q es falsa.
También se puede decir que si p , entonces p ∧ q es q , de lo contrario p ∧ q es p .
Disyunción lógica (OR) [ editar ]
La disyunción lógica es una operación sobre dos valores lógicos , típicamente los valores de dos proposiciones , que produce un valor verdadero si al menos uno de sus operandos es verdadero.
La tabla de verdad para p OR q (también escrita como p ∨ q , Apq , p || q , o p + q ) es la siguiente:
| pag | q | p ∨ q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Dicho en inglés, si p , entonces p ∨ q es p , de lo contrario p ∨ q es q .
Implicación lógica [ editar ]
La implicación lógica y el condicional material están asociados con una operación en dos valores lógicos , típicamente los valores de dos proposiciones , lo que produce un valor falso si el primer operando es verdadero y el segundo operando es falso, y un valor verdadero en caso contrario.
La tabla de verdad asociada con la implicación lógica p implica q (simbolizada como p ⇒ q , o más raramente Cpq ) es la siguiente:
| pag | q | p ⇒ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
La tabla de verdad asociada con el material condicional si p entonces q (simbolizado como p → q ) es la siguiente:
| pag | q | p → q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
También puede ser útil notar que p ⇒ q y p → q son equivalentes a ¬p ∨ q .
Igualdad lógica [ editar ]
La igualdad lógica (también conocida como bicondicional o exclusiva nor ) es una operación sobre dos valores lógicos , normalmente los valores de dos proposiciones , que produce un valor verdadero si ambos operandos son falsos o ambos operandos son verdaderos.
La tabla de verdad para p XNOR q (también escrita como p ↔ q , Epq , p = q , o p ≡ q ) es la siguiente:
| pag | q | p ↔ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
Entonces p EQ q es verdadero si pyq tienen el mismo valor de verdad (ambos verdaderos o ambos falsos), y falso si tienen diferentes valores de verdad.
Disyunción exclusiva [ editar ]
La disyunción exclusiva es una operación sobre dos valores lógicos , típicamente los valores de dos proposiciones , que produce un valor verdadero si uno de sus operandos, pero no ambos, es verdadero.
La tabla de verdad para p XOR q (también escrita como Jpq , o p ⊕ q ) es la siguiente:
| pag | q | p ⊕ q |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
Para dos proposiciones, XOR también se puede escribir como (p ∧ ¬q) ∨ (¬p ∧ q).
NAND lógica [ editar ]
La NAND lógica es una operación sobre dos valores lógicos , normalmente los valores de dos proposiciones , que produce un valor falso si ambos operandos son verdaderos. En otras palabras, produce un valor verdadero si al menos uno de sus operandos es falso.
La tabla de verdad para p NAND q (también escrita como p ↑ q , Dpq o p | q ) es la siguiente:
| pag | q | p ↑ q |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | T |
Con frecuencia es útil expresar una operación lógica como una operación compuesta, es decir, como una operación que se construye o se compone de otras operaciones. Muchas de estas composiciones son posibles, dependiendo de las operaciones que se toman como básicas o "primitivas" y las operaciones que se toman como compuestas o "derivadas".
En el caso de la NAND lógica, se puede expresar claramente como un compuesto de NOT y AND.
La negación de una conjunción: ¬ ( p ∧ q ), y la disyunción de negaciones: (¬ p ) ∨ (¬ q ) se pueden tabular de la siguiente manera:
| pag | q | p ∧ q | ¬ ( p ∧ q ) | ¬ p | ¬ q | (¬ p ) ∨ (¬ q ) |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F |
| T | F | F | T | F | T | T |
| F | T | F | T | T | F | T |
| F | F | F | T | T | T | T |
NOR lógico [ editar ]
El NOR lógico es una operación sobre dos valores lógicos , normalmente los valores de dos proposiciones , que produce un valor verdadero si ambos operandos son falsos. En otras palabras, produce un valor falso si al menos uno de sus operandos es verdadero. ↓ también se conoce como la flecha de Peirce en honor a su inventor, Charles Sanders Peirce , y es un operador único suficiente .
La tabla de verdad para p NOR q (también escrita como p ↓ q , o Xpq ) es la siguiente:
| pag | q | p ↓ q |
|---|---|---|
| T | T | F |
| T | F | F |
| F | T | F |
| F | F | T |
La negación de una disyunción ¬ ( p ∨ q ) y la conjunción de negaciones (¬ p ) ∧ (¬ q ) se pueden tabular de la siguiente manera:
| pag | q | p ∨ q | ¬ ( p ∨ q ) | ¬ p | ¬ q | (¬ p ) ∧ (¬ q ) |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F |
| T | F | T | F | F | T | F |
| F | T | T | F | T | F | F |
| F | F | F | T | T | T | T |
Inspección de las derivaciones tabulares para NAND y NOR, bajo cada asignación de valores lógicos a los argumentos funcionales p y q , produce los patrones idénticos de valores funcionales para ¬ ( p ∧ q ) como para (¬ p ) ∨ (¬ q ), y para ¬ ( p ∨ q ) como para (¬ p ) ∧ (¬ q ). Por tanto, la primera y la segunda expresión de cada par son lógicamente equivalentes y pueden sustituirse entre sí en todos los contextos que pertenecen únicamente a sus valores lógicos.
Esta equivalencia es una de las leyes de De Morgan .
Aplicaciones [ editar ]
Las tablas de verdad se pueden utilizar para probar muchas otras equivalencias lógicas . Por ejemplo, considere la siguiente tabla de verdad:
| T | T | F | T | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
Esto demuestra el hecho de que es lógicamente equivalente a .
Tabla de verdad para los operadores lógicos más utilizados [ editar ]
Aquí hay una tabla de verdad que proporciona definiciones de las 6 más comúnmente utilizadas de las 16 posibles funciones de verdad de dos variables booleanas P y Q :
| PAG | Q | |||||||
|---|---|---|---|---|---|---|---|---|
| T | T | T | T | F | T | T | T | T |
| T | F | F | T | T | F | F | T | F |
| F | T | F | T | T | F | T | F | F |
| F | F | F | F | F | T | T | T | T |
dónde
- T
- cierto
- F
- falso
- Y (conjunción lógica)
- O (disyunción lógica)
- XOR (exclusivo o)
- XNOR (exclusivo ni)
- condicional "si-entonces"
- condicional "entonces-si"
- bicondicional "si-y-solo-si" .
Tablas de verdad condensadas para operadores binarios [ editar ]
Para los operadores binarios, también se utiliza una forma condensada de tabla de verdad, donde los encabezados de fila y de columna especifican los operandos y las celdas de la tabla especifican el resultado. Por ejemplo, la lógica booleana usa esta notación de tabla de verdad condensada:
|
|
Esta notación es útil especialmente si las operaciones son conmutativas, aunque también se puede especificar que las filas son el primer operando y las columnas son el segundo operando. Esta notación condensada es particularmente útil al discutir extensiones de lógica de valores múltiples, ya que reduce significativamente la explosión combinatoria del número de filas que de otro modo se necesitarían. También proporciona una "forma" característica rápidamente reconocible de la distribución de los valores en la tabla que puede ayudar al lector a comprender las reglas más rápidamente.
Tablas de verdad en lógica digital [ editar ]
Las tablas de verdad también se utilizan para especificar la función de las tablas de búsqueda de hardware (LUT) en los circuitos lógicos digitales . Para una LUT de n entradas, la tabla de verdad tendrá 2 ^ n valores (o filas en el formato tabular anterior), especificando completamente una función booleana para la LUT. Al representar cada valor booleano como un bit en un número binario , los valores de la tabla de verdad se pueden codificar de manera eficiente como valores enteros en el software de automatización de diseño electrónico (EDA) . Por ejemplo, un entero de 32 bits puede codificar la tabla de verdad para una LUT con hasta 5 entradas.
Cuando se usa una representación entera de una tabla de verdad, el valor de salida de la LUT se puede obtener calculando un índice de bit k basado en los valores de entrada de la LUT, en cuyo caso el valor de salida de la LUT es el k- ésimo bit del entero. Por ejemplo, para evaluar el valor de salida de una LUT dada una matriz de n valores de entrada booleanos, el índice de bits del valor de salida de la tabla de verdad se puede calcular de la siguiente manera: si la i- ésima entrada es verdadera, déjelo , de lo contrario déjelo . Entonces, el k- ésimo bit de la representación binaria de la tabla de verdad es el valor de salida de la LUT, donde .
Las tablas de verdad son una forma simple y directa de codificar funciones booleanas; sin embargo, dado el crecimiento exponencial en tamaño a medida que aumenta el número de entradas, no son adecuadas para funciones con una gran cantidad de entradas. Otras representaciones que son más eficientes en memoria son las ecuaciones de texto y los diagramas de decisión binarios .
Aplicaciones de tablas de verdad en electrónica digital [ editar ]
En electrónica digital e informática (campos de la ingeniería lógica aplicada y las matemáticas), las tablas de verdad se pueden utilizar para reducir las operaciones booleanas básicas a correlaciones simples de entradas y salidas, sin el uso de puertas lógicas o código. Por ejemplo, una suma binaria se puede representar con la tabla de verdad:
AB | CR1 1 | 1 01 0 | 0 10 1 | 0 10 0 | 0 0dóndeA = primer operandoB = segundo operandoC = llevarR = Resultado
Esta tabla de verdad se lee de izquierda a derecha:
- El par de valores (A, B) es igual al par de valores (C, R).
- O para este ejemplo, A más B igual resultado R, con el Carry C.
Tenga en cuenta que esta tabla no describe las operaciones lógicas necesarias para implementar esta operación, sino que simplemente especifica la función de las entradas a los valores de salida.
Con respecto al resultado, este ejemplo puede verse aritméticamente como una suma binaria de módulo 2 y como lógicamente equivalente a la operación lógica binaria exclusiva o (disyunción exclusiva).
En este caso, solo se puede utilizar para entradas y salidas muy simples, como unos y ceros. Sin embargo, si aumenta el número de tipos de valores que se pueden tener en las entradas, aumentará el tamaño de la tabla de verdad.
Por ejemplo, en una operación de suma, se necesitan dos operandos, A y B. Cada uno puede tener uno de dos valores, cero o uno. El número de combinaciones de estos dos valores es 2 × 2 o cuatro. Entonces, el resultado son cuatro posibles salidas de C y R. Si se usara la base 3, el tamaño aumentaría a 3 × 3, o nueve posibles salidas.
El primer ejemplo de "adición" anterior se llama medio sumador. Un sumador completo es cuando el acarreo de la operación anterior se proporciona como entrada al siguiente sumador. Por lo tanto, se necesitaría una tabla de verdad de ocho filas para describir la lógica de un sumador completo :
ABC * | CR0 0 0 | 0 00 1 0 | 0 11 0 0 | 0 11 1 0 | 1 00 0 1 | 0 10 1 1 | 1 01 0 1 | 1 01 1 1 | 1 1Igual que el anterior, pero ...C * = Llevar del sumador anterior
Historia [ editar ]
La investigación de Irving Anellis muestra que CS Peirce parece ser el primer lógico (en 1893) en diseñar una matriz de tabla de verdad. [4] [6] Del resumen de su artículo:
En 1997, John Shosky descubrió, en el reverso de una página de la transcripción mecanografiada de la conferencia de 1912 de Bertrand Russell sobre "La filosofía del atomismo lógico", las matrices de tablas de verdad. La matriz de la negación es la de Russell, junto a la cual está la matriz de la implicación material de la mano de Ludwig Wittgenstein. Se muestra que un manuscrito inédito identificado como compuesto por Peirce en 1893 incluye una matriz de tabla de verdad que es equivalente a la matriz de implicación material descubierta por John Shosky. Un manuscrito inédito de Peirce identificado como compuesto en 1883-1884 en relación con la composición de "Sobre el álgebra de la lógica: una contribución a la filosofía de la notación" de Peirce que apareció en el American Journal of Mathematics en 1885 incluye un ejemplo de una tabla de verdad indirecta para el condicional.
Notas [ editar ]
- ↑ Se puede encontrar información sobre la notación en Bocheński (1959), Enderton (2001) y Quine (1982).
- ^ Los operadores aquí con identidades iguales de izquierda y derecha (XOR, AND, XNOR y OR) también son monoides conmutativos porque también son asociativos . Si bien esta distinción puede ser irrelevante en una simple discusión de lógica, puede ser bastante importante en matemáticas más avanzadas. Por ejemplo, en la teoría de categorías, una categoría enriquecida se describe como una categoría baseenriquecida sobre un monoide, y cualquiera de estos operadores se puede utilizar para el enriquecimiento.
Ver también [ editar ]
- Dominio booleano
- Función con valor booleano
- Minimizador de lógica heurística de espresso
- Mesa de excitación
- Lógica de primer orden
- Integridad funcional
- Mapas de Karnaugh
- Puerta lógica
- Conectivo lógico
- Gráfico lógico
- Método de cuadros analíticos
- Cálculo proposicional
- Función de la verdad
Referencias [ editar ]
- ^ Enderton , 2001
- ^ Georg Henrik von Wright (1955). "Ludwig Wittgenstein, un bosquejo biográfico". La revisión filosófica . 64 (4): 527–545 (pág. 532, nota 9). doi : 10.2307 / 2182631 . JSTOR 2182631 .
- ^ Emil Post (julio de 1921). "Introducción a una teoría general de proposiciones elementales". Revista Estadounidense de Matemáticas . 43 (3): 163–185. doi : 10.2307 / 2370324 . hdl : 2027 / uiuo.ark: / 13960 / t9j450f7q . JSTOR 2370324 .
- ↑ a b Anellis, Irving H. (2012). "Análisis funcional de la verdad de Peirce y el origen de la tabla de la verdad". Historia y Filosofía de la Lógica . 33 : 87–97. doi : 10.1080 / 01445340.2011.621702 .
- ↑ a b Ludwig Wittgenstein (1922) Tractatus Logico-Philosophicus Proposition 5.101
- ↑ La publicación de Peirce incluyó el trabajo de Christine Ladd (1881) : Ph.D. de Peirce. La estudiante Christine Ladd-Franklin encontró la tabla de verdad en laProposición 5.101 del Tractatus Logico-Philosophicus , 40 años antes que Wittgenstein. Christine Ladd (1881), "Sobre el álgebra de la lógica", p.62 , Estudios de lógica , CS Peirce ed., 1883
Obras citadas [ editar ]
- Bocheński, Józef Maria (1959), A Précis of Mathematical Logic , traducido de las ediciones francesa y alemana por Otto Bird, Dordrecht, Holanda Meridional: D. Reidel.
- Enderton, H. (2001). Una introducción matemática a la lógica , segunda edición, Nueva York: Harcourt Academic Press. ISBN 0-12-238452-0
- Quine, WV (1982), Methods of Logic , 4ª edición, Cambridge, MA: Harvard University Press.
Enlaces externos [ editar ]
 | Wikimedia Commons tiene medios relacionados con tablas de verdad . |
- "Tabla de la verdad" , Enciclopedia de las matemáticas , EMS Press , 2001 [1994]
- Tablas de verdad, tautologías y equivalencia lógica
- EL ANÁLISIS VERDAD-FUNCIONAL DE PEIRCE Y EL ORIGEN DE LAS TABLAS DE LA VERDAD por Irving H. Anellis
- Conversión de tablas de verdad en expresiones booleanas
