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 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 posible configuración 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 correspondientes valores de salida. 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 se puede enumerar como: A×B = {(A = 0, B = 0), (A = 0, B = 1), (A = 1, B = 0), (A = 1, B = 1)}. Cada elemento en el 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 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 sólo un miembro del codominio. Por lo tanto, la función f en sí 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 valores booleanos, 0 o 1, como miembros del codominio {0, 1}, como las salidas correspondientes al miembro de el dominio, respectivamente. En lugar de una lista (conjunto) proporcionada anteriormente, la tabla de verdad presenta estos pares de entrada-salida en un formato tabular, en el que cada fila corresponde a un miembro del dominio emparejado con su correspondiente valor de salida, 0 o 1. Por supuesto, para las funciones booleanas, no tenemos que listar 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 generalmente se le atribuye 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] Este sistema también fue propuesto de forma independiente en 1921 por Emil Leon Post . [3]
Hay 2 operaciones nulas:
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 es 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 el 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 , 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:
Hay 16 posibles funciones de verdad de dos variables binarias , cada operador tiene su propio nombre.
Aquí hay una tabla de verdad extendida que brinda 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 , [4] Wittgenstein enumeró la tabla anterior de la siguiente manera:
La tabla de verdad representada por cada fila se obtiene agregando la secuencia dada en la fila Valores de verdad a la tabla [nota 3]
Por ejemplo, la mesa
representa la tabla de verdad para la implicación material .
Los operadores lógicos también se pueden visualizar mediante diagramas de Venn .
La conjunció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 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 verdaderos, entonces la conjunción p ∧ q es verdadera. Para todas las demás asignaciones de valores lógicos a p y q, la conjunción p ∧ q es falsa.
También se puede decir que si p , entonces p ∧ q es q , en caso contrario p ∧ q es p .
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:
Dicho en inglés, si p , entonces p ∨ q es p , en caso contrario p ∨ q es q .
La implicación lógica y el condicional material están asociados con una operación sobre dos valores lógicos , típicamente 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 (simbolizada como p → q ) es la siguiente:
También puede ser útil observar que p ⇒ q y p → q son equivalentes a ¬p ∨ q .
La igualdad lógica (también conocida como bicondicional o nor exclusiva ) es una operación sobre dos valores lógicos , generalmente 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 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:
Para dos proposiciones, XOR también se puede escribir como (p ∧ ¬q) ∨ (¬p ∧ q).
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:
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 compone a partir de otras operaciones. Muchas de estas composiciones son posibles, dependiendo de las operaciones que se consideran básicas o "primitivas" y de las operaciones que se consideran compuestas o "derivadas".
En el caso de 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:
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 flecha de Peirce en honor a su inventor, Charles Sanders Peirce , y es un operador suficiente único .
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 de cada par son lógicamente equivalentes y pueden sustituirse entre sí en todos los contextos que se refieren únicamente a sus valores lógicos.
Esta equivalencia es una de las leyes de De Morgan .
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 doble exponencial 2 2 n .
Rara vez se proporcionan tablas de verdad para funciones de tres o más variables.
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 .
Aquí hay una tabla de verdad que brinda definiciones de las 7 funciones de verdad más comúnmente 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 las filas y las columnas especifican los operandos y las celdas de la tabla especifican el resultado. Por ejemplo, la lógica booleana utiliza 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 sean el primer operando y las columnas el segundo operando. Esta notación condensada es particularmente útil al analizar 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 serían necesarias. 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.
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), 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 de 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 bits 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, let , en caso contrario, let . Entonces, el k- ésimo bit de la representación binaria de la tabla de verdad es el valor de salida del LUT, donde .
Las tablas de verdad son una forma sencilla y directa de codificar funciones booleanas; sin embargo, dado el crecimiento exponencial de su 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 binaria .
En electrónica digital e informática (campos de ingeniería lógica aplicada y matemáticas), las tablas de verdad se pueden utilizar para reducir operaciones booleanas básicas a simples correlaciones 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:
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, sólo se puede utilizar para entradas y salidas muy simples, como 1 y 0. Sin embargo, si aumenta el número de tipos de valores que uno puede 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 uno usara la base 3, el tamaño aumentaría a 3×3, o nueve posibles salidas.
El primer ejemplo de "suma" 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 desde el sumador anterior
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. [5]
Del resumen del artículo de Peirce:
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 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.
Esto explica por qué la fila del Tractatus en la tabla proporcionada aquí no apunta a la misma fila de Valores de Verdad que en el Tractatus.
