Una tabla de verdad es una tabla matemática utilizada en lógica —específicamente en conexión con el álgebra de Boole , las funciones booleanas y el cálculo proposicional— que establece los valores funcionales de 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 utilizar 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, A y B) y una columna final que muestra todos los resultados posibles de la operación lógica que representa la tabla (por ejemplo, A XOR B). Cada fila de la tabla de verdad contiene una configuración posible de las variables de entrada (por ejemplo, A=verdadero, B=falso) y el resultado de la operación para esos valores.
Una tabla de verdad es una representación estructurada que presenta todas las combinaciones posibles de valores de verdad para las variables de entrada de una función booleana y sus valores de salida correspondientes. Una función f de A a F es una relación especial , un subconjunto de A×F, lo que simplemente significa que f puede enumerarse como una lista de pares de entrada-salida. Claramente, para las funciones booleanas, la salida pertenece a un conjunto binario, es decir, F = {0, 1}. Para una función booleana n-aria, las entradas provienen de un dominio que es en sí mismo un producto cartesiano de conjuntos binarios correspondientes a las variables booleanas de entrada. Por ejemplo, para una función binaria, f (A, B), el dominio de f es A×B, que puede enumerarse como: A×B = {(A = 0, B = 0), (A = 0, B = 1), (A = 1, B = 0), (A = 1, B = 1)}. Cada elemento del dominio representa una combinación de valores de entrada para las variables A y B. Estas combinaciones ahora se pueden combinar con la salida de la función correspondiente a esa combinación, formando así el conjunto de pares de entrada-salida como una relación especial que es un subconjunto de A×F. Para que una relación sea una función, el requisito especial es que cada elemento del dominio de la función debe asignarse a uno y solo un miembro del codominio. Por lo tanto, la función f en sí misma se puede enumerar como: f = {((0, 0), f 0 ), ((0, 1), f 1 ), ((1, 0), f 2 ), ((1, 1), f 3 )}, donde f 0 , f 1 , f 2 y f 3 son cada uno valores booleanos, 0 o 1, como miembros del codominio {0, 1}, como las salidas correspondientes al miembro del dominio, respectivamente. En lugar de una lista (conjunto) dada anteriormente, la tabla de verdad presenta entonces estos pares de entrada-salida en un formato tabular, en el que cada fila corresponde a un miembro del dominio emparejado con su valor de salida correspondiente, 0 o 1. Por supuesto, para las funciones booleanas, no tenemos que enumerar todos los miembros del dominio con sus imágenes en el codominio ; simplemente podemos enumerar las asignaciones que asignan el miembro a "1", porque todas las demás tendrán que asignarse a "0" automáticamente (eso nos lleva a la idea de los minterms ).
A Ludwig Wittgenstein se le atribuye generalmente la invención y popularización de la tabla de verdad en su Tractatus Logico-Philosophicus , que se completó en 1918 y se publicó en 1921. [2] Un sistema de este tipo también fue propuesto de forma independiente en 1921 por Emil Leon Post . [3]
La investigación de Irving Anellis muestra que CS Peirce parece ser el primer lógico (en 1883) en idear una matriz de tabla de verdad. [4]
Del resumen del artículo de Anellis: [4]
En 1997, John Shosky descubrió, en el reverso de una página de la transcripción mecanografiada de la conferencia de Bertrand Russell de 1912 sobre "La filosofía del atomismo lógico", matrices de tablas de verdad. La matriz para la negación es la de Russell, junto a la cual se encuentra la matriz para 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 para la implicación material descubierta por John Shosky. Un manuscrito inédito de Peirce identificado como compuesto en 1883-84 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.
Las tablas de verdad se pueden utilizar para demostrar muchas otras equivalencias lógicas . Por ejemplo, considere la siguiente tabla de verdad:
Esto demuestra el hecho de que es lógicamente equivalente a .
A continuación se muestra una tabla de verdad que proporciona definiciones de las 7 funciones de verdad más utilizadas de las 16 posibles de dos variables booleanas P y Q:
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 utiliza esta notación condensada de tabla de verdad:
Esta notación es útil especialmente si las operaciones son conmutativas, aunque se puede especificar además que las filas son el primer operando y las columnas son el segundo operando. Esta notación condensada es particularmente útil al analizar extensiones de lógica multivaluadas, ya que reduce significativamente la explosión combinatoria del número de filas que de otro modo serían necesarias. También proporciona una "forma" característica rápidamente reconocible de la distribución de los valores en la tabla, lo que puede ayudar al lector a comprender las reglas más rápidamente.
Las tablas de verdad también se utilizan para especificar la función de las tablas de búsqueda de hardware (LUT) en 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), lo que especifica por completo 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 utiliza 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 bit del valor de salida de la tabla de verdad se puede calcular de la siguiente manera: si la i -ésima entrada es verdadera, sea , de lo contrario sea . 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 sencilla y directa de codificar funciones booleanas; sin embargo, dado el crecimiento exponencial del 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 el uso de la memoria son las ecuaciones de texto y los diagramas de decisión binarios .
En electrónica digital y ciencias de la computación (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:
donde A es el primer operando, B es el segundo operando, C es el dígito de acarreo y R es el resultado.
Esta tabla de verdad se lee de izquierda a derecha:
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 módulo 2, y como lógicamente equivalente a la operación lógica binaria exclusiva-o (disyunción exclusiva).
En este caso, se puede utilizar solo para entradas y salidas muy simples, como 1 y 0. Sin embargo, si aumenta la cantidad 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. Por lo tanto, el resultado son cuatro posibles salidas de C y R. Si se utilizara la base 3, el tamaño aumentaría a 3×3, o nueve posibles salidas.
El primer ejemplo de "suma" anterior se denomina semisumador. Un sumador completo es aquel en el que 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* = Acarreo del sumador anterior
Respecto a las columnas guía [5] a la izquierda de una tabla, que representan variables proposicionales , diferentes autores tienen diferentes recomendaciones sobre cómo llenarlas, aunque esto no tiene importancia lógica. [6]
Lee Archie, profesor de la Universidad Lander , recomienda este procedimiento, que se sigue habitualmente en las tablas de verdad publicadas:
Este método da como resultado tablas de verdad como la siguiente tabla para " P ⊃ (Q ∨ R ⊃ (R ⊃ ¬P)) ", producida por Stephen Cole Kleene : [7]
Colin Howson , por su parte, cree que "es una buena regla práctica" hacer lo siguiente:
para empezar con todas las T, luego todas las formas (tres) en que dos T se pueden combinar con una F, luego todas las formas (tres) en que una T se puede combinar con dos F, y luego terminar con todas las F. Si un compuesto se construye a partir de n letras de oraciones distintas, su tabla de verdad tendrá 2 n filas, ya que hay dos formas de asignar T o F a la primera letra, y para cada una de estas habrá dos formas de asignar T o F a la segunda, y para cada una de estas habrá dos formas de asignar T o F a la tercera, y así sucesivamente, dando 2.2.2. …, n veces, que es igual a 2 n . [6]
Esto da como resultado tablas de verdad como esta tabla "que muestra que (A→C)∧(B→C) y (A∨B)→C son funcionalmente equivalentes en términos de verdad ", modelada a partir de una tabla producida por Howson : [6]
Si hay n variables de entrada, entonces hay 2 n combinaciones posibles de sus valores de verdad. Una función dada puede producir verdadero o falso para cada combinación, por lo que el número de funciones diferentes de n variables es el exponencial doble 2 2 n .
Rara vez se dan tablas de verdad para funciones de tres o más variables.
Puede resultar útil tener la salida de una tabla de verdad expresada como una función de algunos valores de variables, en lugar de solo un valor literal de verdad o de falsedad. Estas pueden llamarse "tablas de funciones" para diferenciarlas de las "tablas de verdad" más generales. [8] Por ejemplo, un valor, , puede usarse con una compuerta XOR para invertir condicionalmente otro valor, . En otras palabras, cuando es falso, la salida es , y cuando es verdadero, la salida es . La tabla de funciones para esto se vería así:
De manera similar, un multiplexor de 4 a 1 con entradas de selección y , entradas de datos , , y , y salida (como se muestra en la imagen) tendría esta tabla de funciones:
A continuación se muestra una tabla de verdad extendida que proporciona definiciones de las dieciséis funciones de verdad posibles de dos variables booleanas p y q : [nota 1]
dónde
En la proposición 5.101 del Tractatus Logico-Philosophicus , [9] Wittgenstein enumeró la tabla anterior de la siguiente manera:
La tabla de verdad representada por cada fila se obtiene añadiendo la secuencia dada en la fila Valores de verdad a la tabla [nota 3]
Por ejemplo, la tabla
representa la tabla de verdad para la implicación material . Los operadores lógicos también pueden visualizarse mediante diagramas de Venn .
Existen 2 operaciones nularias:
El valor de salida siempre es verdadero, porque este operador tiene cero operandos y, por lo tanto, no tiene valores de entrada.
El valor de salida nunca es verdadero: es decir, siempre falso, porque este operador tiene cero operandos y, por lo tanto, no tiene valores de entrada.
Hay 2 operaciones unarias:
La identidad lógica es una operación sobre un valor lógico p, para la cual el valor de salida sigue siendo p.
La tabla de verdad para el operador de identidad lógica es la siguiente:
La negación lógica es una operación sobre un valor lógico , normalmente 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 escrito como ¬p , Np , Fpq o ~p ) es la siguiente:
Hay 16 funciones de verdad posibles de dos variables binarias , cada operador tiene su propio nombre.
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 AND q (también escrita como p ∧ q , Kpq , p & q , o p q ) es la siguiente:
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 a p y a 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 .
La disyunción lógica es una operación sobre dos valores lógicos , normalmente 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 O q (también escrita como p ∨ q , Apq , p || q o p + q ) es la siguiente:
Expresado en español, si p , entonces p ∨ q es p , de lo contrario p ∨ q es q .
Tanto la implicación lógica como el condicional material están asociados a una operación sobre dos valores lógicos , normalmente los valores de dos proposiciones , 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:
La tabla de verdad asociada con el condicional material si p entonces q (simbolizado como p → q ) es la siguiente:
p ⇒ q y p → q son equivalentes a ¬p ∨ q .
La igualdad lógica (también conocida como bicondicional o ni exclusiva ) es una operación sobre dos valores lógicos , típicamente 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:
Entonces, p EQ q es verdadero si p y q tienen el mismo valor de verdad (ambos verdaderos o ambos falsos), y falso si tienen diferentes valores de verdad.
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 pero no ambos de sus operandos es verdadero.
La tabla de verdad para p XOR q (también escrita como Jpq o p ⊕ q ) es la siguiente:
Para dos proposiciones, XOR también se puede escribir como (p ∧ ¬q) ∨ (¬p ∧ q).
La función 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:
Con frecuencia resulta útil expresar una operación lógica como una operación compuesta , es decir, como una operación que se construye o se compone a partir de otras operaciones. Son posibles muchas composiciones de este tipo, dependiendo de las operaciones que se tomen como básicas o "primitivas" y de las operaciones que se tomen como compuestas o "derivadas".
En el caso de NAND lógico, 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:
La operación NOR 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 falsos. En otras palabras, produce un valor falso si al menos uno de sus operandos es verdadero. ↓ también se conoce como 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:
La negación de una disyunción ¬( p ∨ q ), y la conjunción de negaciones (¬ p ) ∧ (¬ q ) se pueden tabular de la siguiente manera:
La 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 patrones idénticos de valores funcionales para ¬( p ∧ q ) como para (¬ p ) ∨ (¬ q ), y para ¬( p ∨ q ) como para (¬ p ) ∧ (¬ q ). Por lo tanto, la primera y la segunda expresión en 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 .
Esto explica por qué la fila del Tractatus en la tabla que se presenta aquí no apunta a la misma fila de Valores de verdad que en el Tractatus.
