Tabla de verdad

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 que toman 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 el resultado 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.

La tabla de verdad de una proposición es una representación gráfica de su función de verdad . La función de verdad puede ser más útil para fines matemáticos, aunque la misma información está codificada en ambas.

Generalmente se le atribuye a Ludwig Wittgenstein 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 similar también fue propuesto de forma independiente en 1921 por Emil Leon Post . ^{[ 3 ]}

Historia

La investigación de Irving Anellis muestra que C.S. 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 de Russell, junto a la cual se encuentra la matriz para la implicación material escrita por Ludwig Wittgenstein. Se demuestra que un manuscrito inédito, identificado como compuesto por Peirce en 1893, incluye una matriz de tabla de verdad equivalente a la matriz para la implicación material descubierta por John Shosky. Un manuscrito inédito de Peirce, identificado como compuesto entre 1883 y 1884 en relación con la composición de su obra "Sobre el álgebra de la lógica: una contribución a la filosofía de la notación", publicada en el American Journal of Mathematics en 1885, incluye un ejemplo de una tabla de verdad indirecta para el condicional.

Aplicaciones

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 $p\rightarrow q$ es lógicamente equivalente a $\neg p\vee q$ .

Tabla de verdad para compuertas lógicas

Aquí se muestra una tabla de verdad que proporciona definiciones de cada una de las 6 posibles funciones de compuerta lógica de 2 entradas para dos variables booleanas P y Q:

Tablas de verdad condensadas para operadores binarios

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 de tabla de verdad condensada:

Esta notación resulta especialmente útil si las operaciones son conmutativas, aunque también se puede especificar que las filas constituyen el primer operando y las columnas el segundo. Esta notación condensada es particularmente útil al analizar extensiones multivaluadas de la lógica, ya que reduce significativamente la complejidad combinatoria del número de filas necesarias. Además, permite identificar fácilmente la forma característica de la distribución de los valores en la tabla, lo que facilita la comprensión de las reglas.

Tablas de verdad en lógica digital

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}$ Los valores (o filas en el formato tabular anterior) especifican completamente una función booleana para la tabla de búsqueda (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 comovalores enteros en el software de automatización del 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 dado un array 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 $V_{i}=1$ , de lo contrario deja $V_{i}=0$ . Entonces, el k -ésimo bit de la representación binaria de la tabla de verdad es el valor de salida de la LUT, donde $k=V_{0}\times 2^{0}+V_{1}\times 2^{1}+V_{2}\times 2^{2}+\dots +V_{n-1}\times 2^{n-1}.$

Las tablas de verdad son una forma sencilla y directa de codificar funciones booleanas; sin embargo, debido al crecimiento exponencial de su tamaño a medida que aumenta el número de entradas, no son adecuadas para funciones con un gran número de entradas. Otras representaciones más eficientes en cuanto al uso de memoria son las ecuaciones de texto y los diagramas de decisión binarios .

Aplicaciones de las tablas de verdad en la electrónica digital

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 usar para reducir las operaciones booleanas básicas a simples correlaciones de entradas y salidas, sin necesidad de utilizar compuertas lógicas ni 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:

El par de valores (A, B) es igual al par de valores (C, R).
O para este ejemplo, A más B es igual al resultado R, con el acarreo C.

Esta tabla no describe las operaciones lógicas necesarias para implementar esta operación, sino que simplemente especifica la función de las entradas para obtener 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 de disyunción exclusiva (o exclusivo).

En este caso, solo se puede usar 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, el tamaño de la tabla de verdad también aumentará.

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 posibles de estos dos valores es 2 × 2, es decir, cuatro. Por lo tanto, el resultado son cuatro posibles resultados: C y R. Si se utilizara la base 3, el tamaño aumentaría a 3 × 3, o sea, nueve posibles resultados.

El primer ejemplo de "suma" anterior se denomina semisumador. Un sumador completo se produce cuando el acarreo de la operación anterior se utiliza como entrada para el 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* | CR 0 0 0 | 0 0 0 1 0 | 0 1 1 0 0 | 0 1 1 1 0 | 1 0 0 0 1 | 0 1 0 1 1 | 1 0 1 0 1 | 1 0 1 1 1 | 1 1 Igual que antes, pero... C* = Acarreo del sumador anterior

Métodos para escribir tablas de verdad

En cuanto a las columnas de guía ^{[ 5 ]} a la izquierda de una tabla, que representan variables proposicionales , diferentes autores tienen diferentes recomendaciones sobre cómo completarlas, aunque esto no tiene significado lógico. ^{[ 6 ]}

Método alterno

Lee Archie, profesor de la Universidad de Lander , recomienda este procedimiento, que se sigue habitualmente en las tablas de verdad publicadas:

Escribe el número de variables (que corresponde al número de instrucciones) en orden alfabético.
El número de líneas necesarias es 2 ^n, donde n es el número de variables. (Por ejemplo, con tres variables, 2 ³ = 8).
Empiece por la columna de la derecha y alterne las letras T y F hasta que se le acaben las líneas.
Luego, pase a la izquierda, a la siguiente columna, y alterne pares de T y F hasta que se le acaben las líneas.
Luego, continúe con la siguiente columna de la izquierda y duplique la cantidad de T y F hasta completar. ^{[ 5 ]}

Este método da como resultado tablas de verdad como la siguiente tabla para $P \to (Q \lor R \to (R \to \neg P))$ , producida por Stephen Cole Kleene : ^{[ 7 ]}

Método combinatorio

Colin Howson , por otro lado, 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 distintas de la oración, su tabla de verdad tendrá 2 ⁿ 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 ⁿ . ^{[ 6 ]}

Esto da como resultado tablas de verdad como esta tabla "que muestra que $(A \to C)\land(B \to C)$ y $(A \lor B)\to C$ son equivalentes en términos de función de verdad ", modelada a partir de una tabla producida por Howson : ^[⁶^]

Tamaño de las tablas de verdad

Si hay n variables de entrada, entonces hay 2 ⁿ 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 ⁿ} .

Las tablas de verdad para funciones de tres o más variables rara vez se proporcionan.

Tablas de funciones

Puede ser útil expresar la salida de una tabla de verdad como una función de algunos valores de variables, en lugar de simplemente un valor literal verdadero o falso. Estas pueden denominarse "tablas de funciones" para diferenciarlas de las "tablas de verdad" más generales. ^{[ 8 ]} Por ejemplo, un valor, $G$ , puede usarse con una puerta XOR para invertir condicionalmente otro valor, $X$ . En otras palabras, cuando $G$ es falso, la salida es $X$ , y cuando $G$ es verdadero, la salida es ${\textstyle \neg X}$ La tabla de funciones para esto se vería así:

De manera similar, un multiplexor de 4 a 1 con entradas seleccionadas $S_{0}$ y $S_{1}$ Las entradas de datos $A$ , $B$ , $C$ y $D$ , y la salida $Z$ (como se muestra en la imagen) tendrían esta tabla de funciones:

Tablas de verdad de operadores sentenciales

Tabla de resumen

Aquí hay una tabla de verdad extendida que proporciona definiciones de las dieciséis posibles funciones de verdad de dos variables booleanas p y q : ^{[ nota 1 ]}

dónde

T = verdadero.

F = falso.

La fila Com indica si un operador, op , es conmutativo :

P op Q = Q op P.

La fila Assoc indica si un operador, op , es asociativo :

(P op Q) op R = Pop (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 = \neg(P op2 Q)

.

La fila Dual muestra la operación dual que se obtiene al intercambiar T con F, y AND con OR.

La fila L id muestra las identidades izquierdas del operador si tiene algún valor

I

tal que

I op Q = Q

.

La fila R id muestra las identidades derechas del operador si tiene algún valor

I

tal que

P op I = P

. ^{[ nota 2 ]}

Tabla de Wittgenstein

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 agregando 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 se pueden visualizar utilizando diagramas de Venn .

Operaciones nulas

Hay 2 operaciones nulas:

Siempre cierto
Nunca verdadero, falso unario

Verdadero lógico

El valor de salida siempre es verdadero, porque este operador tiene cero operandos y, por lo tanto, ningún valor de entrada.

Falso lógico

El valor de salida nunca es verdadero: es decir, siempre es falso, porque este operador tiene cero operandos y, por lo tanto, ningún valor de entrada.

operaciones unarias

Hay 2 operaciones unarias:

identidad unaria
Negación unaria

Identidad lógica

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:

Negación lógica

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:

Operaciones binarias

Existen 16 posibles funciones de verdad para dos variables binarias ; cada operador tiene su propio nombre.

Conjunción lógica (Y)

La conjunción lógica es una operación que se realiza sobre dos valores lógicos , normalmente los valores de dos proposiciones , y 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 $\cdot$ q ) es la siguiente:

En términos de lenguaje común, si tanto p como q son verdaderas, entonces la conjunción p ∧ q es verdadera. Para cualquier otra asignación 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 .

Disyunción lógica (O)

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:

Dicho en inglés, si p , entonces p ∨ q es p , de lo contrario p ∨ q es q .

Implicación lógica

Tanto la implicación lógica como la condicional material están asociadas 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 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 la condicional material si p entonces q (simbolizada como p → q ) es la siguiente:

p ⇒ q y p → q son equivalentes a ¬p ∨ q .

Igualdad lógica

La igualdad lógica (también conocida como bicondicional o no exclusivo ) 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:

Por lo tanto, p EQ q es verdadero si p y q tienen el mismo valor de verdad (ambos verdaderos o ambos falsos), y falso si tienen valores de verdad diferentes.

disyunción exclusiva

La disyunción exclusiva es una operación sobre dos valores lógicos , normalmente los valores de dos proposiciones , que produce un valor verdadero si uno de sus operandos es verdadero, pero no ambos.

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).

NAND lógica

La operación lógica NAND aplica esta operación a dos valores lógicos , generalmente los valores de dos proposiciones , y 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. 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 la operación lógica NAND, se puede expresar claramente como una combinación 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:

NOR lógica

La NOR lógica 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. 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 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 ) que para (¬ p ) ∨ (¬ q ), y para ¬( p ∨ q ) que 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 .

Véase también

Notas

↑ Se puede encontrar información sobre la notación en ( Bocheński 1959 ) , ( Enderton 2001 ) y ( Quine 1982 ) .
↑ Los operadores con identidades izquierda y derecha iguales (XOR, AND, XNOR y OR) también son monoides conmutativos porque son asociativos . Si bien esta distinción puede ser irrelevante en una discusión simple de lógica, puede ser muy importante en matemáticas más avanzadas. Por ejemplo, en teoría de categorías, una categoría enriquecida se describe como una categoría base enriquecida sobre un monoide, y cualquiera de estos operadores puede usarse para el enriquecimiento.
1 2 Wittgenstein utilizó una asignación diferente. En la proposición 5.101 del Tractatus hay que añadir_{la fila}de valores de verdad a la tabla.
Esto explica por qué _{la fila}Tractatus en la tabla que se muestra aquí no apunta a la misma _filaTruthvalues que en el Tractatus.

Referencias

↑ Enderton 2001
↑ von Wright, Georg Henrik (1955). "Ludwig Wittgenstein, un bosquejo biográfico". The Philosophical Review . 64 (4): 527–545 (p. 532, nota 9). doi : 10.2307/2182631 . JSTOR 2182631 .
↑ Post, Emil (julio de 1921). "Introducción a una teoría general de proposiciones elementales". American Journal of Mathematics . 43 (3): 163– 185. doi : 10.2307/2370324 . hdl : 2027/uiuo.ark:/13960/t9j450f7q . JSTOR 2370324 .
1 2 Anellis, Irving H. (2012). "El análisis veritativo-funcional de Peirce y el origen de la tabla de verdad". Historia y filosofía de la lógica . 33 : 87–97 . doi : 10.1080/01445340.2011.621702 . S2CID 170654885 .
1 2 "Cómo construir una tabla de verdad" . philosophy.lander.edu . Consultado el 5 de abril de 2024 .
1 2 3 Howson, Colin (1997). Lógica con árboles: una introducción a la lógica simbólica . Londres; Nueva York: Routledge. pág. 10. ISBN 978-0-415-13342-5.
↑ Kleene, Stephen Cole (2013). Lógica matemática . Dover Books on Mathematics. Courier Corporation. pág. 11. ISBN 9780486317076.
↑ Mano, M. Morris; Ciletti, Michael (13 de julio de 2018). Diseño digital, edición global (6.ª ed.). Pearson Education, Limited. ISBN 9781292231167.
↑ Wittgenstein, Ludwig (1922). Tractatus Logico-Philosophicus (PDF) . Proposición 5.101.

Obras citadas

Bocheński, Józef María (1959). Un resumen de la lógica matemática . Traducido por Bird, Otto. D. Reidel. doi : 10.1007/978-94-017-0592-9 . ISBN 978-94-017-0592-9.{{cite book}}: Incompatibilidad de ISBN/Fecha ( ayuda )
Enderton, H. (2001). Introducción matemática a la lógica (2.ª ed.). Harcourt Academic Press. ISBN 0-12-238452-0.
Quine, WV (1982). Métodos de lógica (4.ª ed.). Harvard University Press. ISBN 978-0-674-57175-4.

Enlaces externos

"Tabla de verdad" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
Tablas de verdad, tautologías y equivalencia lógica
Conversión de tablas de verdad en expresiones booleanas

[9] Se puede encontrar información sobre la notación en ( Bocheński 1959 ) , ( Enderton 2001 ) y ( Quine 1982 ) .

[10] Los operadores con identidades izquierda y derecha iguales (XOR, AND, XNOR y OR) también son monoides conmutativos porque son asociativos . Si bien esta distinción puede ser irrelevante en una discusión simple de lógica, puede ser muy importante en matemáticas más avanzadas. Por ejemplo, en teoría de categorías, una categoría enriquecida se describe como una categoría base enriquecida sobre un monoide, y cualquiera de estos operadores puede usarse para el enriquecimiento.

[different_mapping-12] 1 2 Wittgenstein utilizó una asignación diferente. En la proposición 5.101 del Tractatus hay que añadir_{la fila}de valores de verdad a la tabla.
Esto explica por qué _{la fila}Tractatus en la tabla que se muestra aquí no apunta a la misma _filaTruthvalues que en el Tractatus.

[1] Enderton 2001

[2] von Wright, Georg Henrik (1955). "Ludwig Wittgenstein, un bosquejo biográfico". The Philosophical Review . 64 (4): 527–545 (p. 532, nota 9). doi : 10.2307/2182631 . JSTOR 2182631 .

[3] Post, Emil (julio de 1921). "Introducción a una teoría general de proposiciones elementales". American Journal of Mathematics . 43 (3): 163– 185. doi : 10.2307/2370324 . hdl : 2027/uiuo.ark:/13960/t9j450f7q . JSTOR 2370324 .

[Peirce-4] 1 2 Anellis, Irving H. (2012). "El análisis veritativo-funcional de Peirce y el origen de la tabla de verdad". Historia y filosofía de la lógica . 33 : 87–97 . doi : 10.1080/01445340.2011.621702 . S2CID 170654885 .

[:0-5] 1 2 "Cómo construir una tabla de verdad" . philosophy.lander.edu . Consultado el 5 de abril de 2024 .

[:13-6] 1 2 3 Howson, Colin (1997). Lógica con árboles: una introducción a la lógica simbólica . Londres; Nueva York: Routledge. pág. 10. ISBN 978-0-415-13342-5.

[7] Kleene, Stephen Cole (2013). Lógica matemática . Dover Books on Mathematics. Courier Corporation. pág. 11. ISBN 9780486317076.

[8] Mano, M. Morris; Ciletti, Michael (13 de julio de 2018). Diseño digital, edición global (6.ª ed.). Pearson Education, Limited. ISBN 9781292231167.

[tlp5.101-11] Wittgenstein, Ludwig (1922). Tractatus Logico-Philosophicus (PDF) . Proposición 5.101.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 7 ]

[ 8 ]

[ nota 1 ]

[ nota 2 ]

[ 9 ]

[