Función de verdad

En lógica , una función de verdad ^[1] es una función que acepta valores de verdad como entrada y produce un valor de verdad único como salida. En otras palabras: la entrada y la salida de una función de verdad son todos valores de verdad; una función de verdad siempre producirá exactamente un valor de verdad, y al introducir el mismo valor de verdad siempre producirá el mismo valor de verdad. El ejemplo típico es la lógica proposicional , en la que un enunciado compuesto se construye utilizando enunciados individuales conectados por conectores lógicos ; si el valor de verdad del enunciado compuesto está completamente determinado por el valor de verdad del enunciado o los enunciados constituyentes, el enunciado compuesto se denomina función de verdad, y se dice que cualquier conector lógico utilizado es funcional de verdad . ^[2]

La lógica proposicional clásica es una lógica veritativo-funcional, ^[3] en la que cada enunciado tiene exactamente un valor de verdad que es verdadero o falso, y cada conectivo lógico es veritativo-funcional (con una tabla de verdad correspondiente ), por lo que cada enunciado compuesto es una función de verdad. ^[4] Por otro lado, la lógica modal no es veritativo-funcional.

Un conectivo lógico es veritativo si el valor de verdad de una oración compuesta es una función del valor de verdad de sus suboraciones. Una clase de conectivos es veritativo si cada uno de sus miembros lo es. Por ejemplo, el conectivo " y " es veritativo ya que una oración como " Las manzanas son frutas y las zanahorias son verduras " es verdadera si, y solo si , cada una de sus suboraciones " las manzanas son frutas " y " las zanahorias son verduras " es verdadera, y es falsa en caso contrario. Algunos conectivos de un lenguaje natural, como el inglés, no son veritativo.

Los conectores de la forma "x cree que ..." son ejemplos típicos de conectores que no son veritativos. Si, por ejemplo, Mary cree erróneamente que Al Gore fue presidente de los EE. UU. el 20 de abril de 2000, pero no cree que la luna esté hecha de queso verde, entonces la oración

" María cree que Al Gore fue presidente de los EE.UU. el 20 de abril de 2000 "

es cierto mientras

" María cree que la luna está hecha de queso verde "

es falsa. En ambos casos, cada oración componente (es decir, " Al Gore fue presidente de los EE. UU. el 20 de abril de 2000 " y " la luna está hecha de queso verde ") es falsa, pero cada oración compuesta formada con el prefijo " María cree que " difiere en valor de verdad. Es decir, el valor de verdad de una oración de la forma " María cree que... " no está determinado únicamente por el valor de verdad de su oración componente y, por lo tanto, el conectivo (unario) (o simplemente operador , ya que es unario) no es veritativo.

La clase de conectores de lógica clásica (por ejemplo , & , → ) que se utiliza en la construcción de fórmulas es veritativo-funcional. Sus valores para diversos valores de verdad como argumento suelen darse mediante tablas de verdad . El cálculo proposicional veritativo-funcional es un sistema formal cuyas fórmulas pueden interpretarse como verdaderas o falsas.

En lógica bivalente, hay dieciséis posibles funciones de verdad, también llamadas funciones booleanas , de dos entradas P y Q. Cualquiera de estas funciones corresponde a una tabla de verdad de un determinado conectivo lógico en lógica clásica, incluidos varios casos degenerados como una función que no depende de uno o ambos argumentos. La verdad y la falsedad se denotan como 1 y 0, respectivamente, en las siguientes tablas de verdad por razones de brevedad.

Debido a que una función puede expresarse como una composición , un cálculo lógico veritativo-funcional no necesita tener símbolos dedicados para que todas las funciones mencionadas anteriormente sean funcionalmente completas . Esto se expresa en un cálculo proposicional como equivalencia lógica de ciertas afirmaciones compuestas. Por ejemplo, la lógica clásica tiene ¬ P  ∨  Q equivalente a P  →  Q. Por lo tanto, el operador condicional "→" no es necesario para un sistema lógico basado en la teoría clásica si "¬" (no) y "∨" (o) ya están en uso.

Un conjunto mínimo de operadores que puede expresar cada enunciado expresable en el cálculo proposicional se denomina conjunto funcionalmente completo mínimo . Un conjunto mínimamente completo de operadores se logra con NAND solo {↑} y NOR solo {↓}.

Los siguientes son los conjuntos mínimos funcionalmente completos de operadores cuyas aridades no exceden de 2: ^[5]

Un elemento

{↑}, {↓}.

Dos elementos

${\displaystyle \{\vee ,\neg \}}$, , , , , , , , , , , , , , , , .​${\displaystyle \{\wedge ,\neg \}}$${\displaystyle \{\to ,\neg \}}$${\displaystyle \{\gets ,\neg \}}$${\displaystyle \{\to ,\bot \}}$${\displaystyle \{\gets ,\bot \}}$${\displaystyle \{\to ,\nleftrightarrow \}}$${\displaystyle \{\gets ,\nleftrightarrow \}}$${\displaystyle \{\to ,\nrightarrow \}}$${\displaystyle \{\to ,\nleftarrow \}}$${\displaystyle \{\gets ,\nrightarrow \}}$${\displaystyle \{\gets ,\nleftarrow \}}$${\displaystyle \{\nrightarrow ,\neg \}}$${\displaystyle \{\nleftarrow ,\neg \}}$${\displaystyle \{\nrightarrow ,\top \}}$${\displaystyle \{\nleftarrow ,\top \}}$${\displaystyle \{\nrightarrow ,\leftrightarrow \}}$${\displaystyle \{\nleftarrow ,\leftrightarrow \}}$

Tres elementos

${\displaystyle \{\lor ,\leftrightarrow ,\bot \}}$, , , , , .${\displaystyle \{\lor ,\leftrightarrow ,\nleftrightarrow \}}$${\displaystyle \{\lor ,\nleftrightarrow ,\top \}}$${\displaystyle \{\land ,\leftrightarrow ,\bot \}}$${\displaystyle \{\land ,\leftrightarrow ,\nleftrightarrow \}}$${\displaystyle \{\land ,\nleftrightarrow ,\top \}}$

Algunas funciones de verdad poseen propiedades que pueden expresarse en teoremas que contienen el conectivo correspondiente. Algunas de esas propiedades que puede tener una función de verdad binaria (o un conectivo lógico correspondiente) son:

• asociatividad : Dentro de una expresión que contiene dos o más de los mismos conectivos asociativos en una fila, el orden de las operaciones no importa siempre y cuando no se modifique la secuencia de los operandos.
• conmutatividad : Los operandos del conectivo pueden intercambiarse sin afectar el valor de verdad de la expresión.
• distributividad : Un conectivo denotado por · se distribuye sobre otro conectivo denotado por +, si a · ( b + c ) = ( a · b ) + ( a · c ) para todos los operandos a , b , c .
• idempotencia : siempre que los operandos de la operación sean los mismos, el conectivo da como resultado el operando. En otras palabras, la operación preserva tanto la verdad como la falsedad (ver más abajo).
• absorción : Un par de conectivossatisface la ley de absorción sipara todos los operandos a , b .${\displaystyle \land ,\lor }$${\displaystyle a\land (a\lor b)=a\lor (a\land b)=a}$

Un conjunto de funciones de verdad es funcionalmente completo si y sólo si para cada una de las siguientes cinco propiedades contiene al menos un miembro que carece de ella:

• monótona : Si f ( a ₁ , ..., a _n ) ≤ f ( b ₁ , ..., b _n ) para todo a ₁ , ..., a _n , b ₁ , ..., b _n ∈ {0,1} tal que a ₁ ≤ b ₁ , a ₂ ≤ b ₂ , ..., a _n ≤ b _n . Por ejemplo,.${\displaystyle \vee ,\wedge ,\top ,\bot }$
• afín : para cada variable, cambiar su valor siempre o nunca cambia el valor de verdad de la operación, para todos los valores fijos de todas las demás variables. Por ejemplo,, .${\displaystyle \neg ,\leftrightarrow }$${\displaystyle \not \leftrightarrow ,\top ,\bot }$
• auto dual : Leer las asignaciones de valores de verdad para la operación de arriba hacia abajo en su tabla de verdad es lo mismo que tomar el complemento de leerla de abajo hacia arriba; en otras palabras, f (¬ a ₁ , ..., ¬ a _n ) = ¬ f ( a ₁ , ..., a _n ). Por ejemplo, .${\displaystyle \neg }$
• preservación de la verdad : la interpretación según la cual a todas las variables se les asigna un valor de verdad verdadero produce un valor de verdad verdadero como resultado de estas operaciones. Por ejemplo, . (ver validez )${\displaystyle \vee ,\wedge ,\top ,\rightarrow ,\leftrightarrow ,\subset }$
• preservación de la falsedad : la interpretación según la cual a todas las variables se les asigna un valor de verdad falso produce un valor de verdad falso como resultado de estas operaciones. Por ejemplo, . (ver validez )${\displaystyle \vee ,\wedge ,\nleftrightarrow ,\bot ,\not \subset ,\not \supset }$

Una función concreta también puede denominarse operador . En la lógica de dos valores hay 2 operadores nulos (constantes), 4 operadores unarios , 16 operadores binarios , 256 operadores ternarios y operadores n -arios. En la lógica de tres valores hay 3 operadores nulos (constantes), 27 operadores unarios , 19683 operadores binarios , 7625597484987 operadores ternarios y operadores n -arios. En la lógica de k valores, hay k operadores nulos, operadores unarios, operadores binarios, operadores ternarios y operadores n -arios. Un operador n -ario en la lógica de k valores es una función de . Por lo tanto, el número de dichos operadores es , que es como se derivaron los números anteriores. ${\displaystyle 2^{2^{n}}}$ ${\displaystyle 3^{3^{n}}}$ ${\displaystyle k^{k}}$${\displaystyle k^{k^{2}}}$${\displaystyle k^{k^{3}}}$${\displaystyle k^{k^{n}}}$ ${\displaystyle \mathbb {Z} _{k}^{n}\to \mathbb {Z} _{k}}$${\displaystyle |\mathbb {Z} _{k}|^{|\mathbb {Z} _{k}^{n}|}=k^{k^{n}}}$

Sin embargo, algunos de los operadores de una aridad particular son en realidad formas degeneradas que realizan una operación de aridad inferior en algunas de las entradas e ignoran el resto de las entradas. De los 256 operadores booleanos ternarios citados anteriormente, de ellos son formas degeneradas de operadores binarios o de aridad inferior, que utilizan el principio de inclusión-exclusión . El operador ternario es uno de esos operadores que en realidad es un operador unario aplicado a una entrada e ignora las otras dos entradas. ${\displaystyle {\binom {3}{2}}\cdot 16-{\binom {3}{1}}\cdot 4+{\binom {3}{0}}\cdot 2}$${\displaystyle f(x,y,z)=\lnot x}$

"No" es un operador unario , que toma un solo término (¬ P ). El resto son operadores binarios , que toman dos términos para formar una proposición compuesta ( P ∧ Q , P ∨ Q , P → Q , P ↔ Q ).

El conjunto de operadores lógicos Ω se puede dividir en subconjuntos disjuntos de la siguiente manera:

${\displaystyle \Omega =\Omega _{0}\cup \Omega _{1}\cup \ldots \cup \Omega _{j}\cup \ldots \cup \Omega _{m}\,.}$

En esta partición, está el conjunto de símbolos de operadores de aridad j . ${\displaystyle \Omega _{j}}$

En los cálculos proposicionales más conocidos, normalmente se divide de la siguiente manera: ${\displaystyle \Omega }$

operadores nulos:${\displaystyle \Omega _{0}=\{\bot ,\top \}}$

operadores unarios:${\displaystyle \Omega _{1}=\{\lnot \}}$

operadores binarios:${\displaystyle \Omega _{2}\supset \{\land ,\lor ,\rightarrow ,\leftrightarrow \}}$

En lugar de utilizar tablas de verdad , los símbolos conectivos lógicos pueden interpretarse mediante una función de interpretación y un conjunto funcionalmente completo de funciones de verdad (Gamut 1991), como se detalla en el principio de composicionalidad del significado. Sea I una función de interpretación, sean Φ , Ψ dos oraciones cualesquiera y sea la función de verdad f _nand definida como:

• f _y (T, T) = F; f _y (T, F) = f _y (F, T) = f _y (F, F) = T

Luego, por conveniencia, f _not , f _o f _y y así sucesivamente se definen por medio de f _nand :

• f _no ( x ) = f _nand ( x , x )
• f _o ( x , y ) = f _{n y} ( f _no ( x ), f _no ( y ))
• f _y ( x , y ) = f _no ( f _{n y} ( x , y ))

o, alternativamente , f _no , f _o f _y y así sucesivamente se definen directamente:

• f _no (T) = F; f _no (F) = T;
• f _o (T,T) = f _o (T,F) = f _o (F,T) = T; f _o (F,F) = F
• f _y (T,T) = T; f _y (T,F) = f _y (F,T) = f _y (F,F) = F

Entonces

etc.

Por lo tanto, si S es una oración que es una cadena de símbolos que consiste en símbolos lógicos v ₁ ... v _n que representan conectivos lógicos, y símbolos no lógicos c ₁ ... c _n , entonces si y solo si I ( v ₁ )... I ( v _n ) han sido proporcionados interpretando v ₁ a v _n por medio de f _nand (o cualquier otro conjunto de funciones de verdad completas funcionales) entonces el valor de verdad de ⁠ ⁠${\displaystyle I(s)}$ está determinado completamente por los valores de verdad de c ₁ ... c _n , es decir, de I ( c ₁ )... I ( c _n ) . En otras palabras, como se esperaba y se requería, S es verdadero o falso solo bajo una interpretación de todos sus símbolos no lógicos.

Los operadores lógicos se implementan como puertas lógicas en circuitos digitales . Prácticamente todos los circuitos digitales (la principal excepción es la DRAM ) están formados por puertas NAND , NOR , NOT y de transmisión . Las puertas NAND y NOR con 3 o más entradas en lugar de las 2 entradas habituales son bastante comunes, aunque son lógicamente equivalentes a una cascada de puertas de 2 entradas. Todos los demás operadores se implementan descomponiéndolos en una combinación lógicamente equivalente de 2 o más de las puertas lógicas anteriores.

La "equivalencia lógica" de "NAND solo", "NOR solo" y "NO y AND" es similar a la equivalencia de Turing .

El hecho de que todas las funciones de verdad se pueden expresar únicamente con NOR queda demostrado por la computadora de guía Apollo .

• Este artículo incorpora material de TruthFunction en PlanetMath , que está licenciado bajo la Licencia Creative Commons Atribución/Compartir-Igual .

• Józef Maria Bocheński (1959), A Précis of Mathematical Logic , traducido de las versiones francesa y alemana por Otto Bird, Dordrecht, Holanda Meridional: D. Reidel.
• Alonzo Church (1944), Introducción a la lógica matemática , Princeton, NJ: Princeton University Press. Véase la Introducción para conocer la historia del concepto de función de verdad.