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 único valor de verdad 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 o valores de verdad, siempre se obtendrá el mismo valor de verdad. El ejemplo típico se encuentra en la lógica proposicional , donde una proposición compuesta se construye utilizando proposiciones individuales conectadas por conectores lógicos ; si el valor de verdad de la proposición compuesta está completamente determinado por el o los valores de verdad de las proposiciones constituyentes, la proposición compuesta se denomina función de verdad, y cualquier conector lógico utilizado se denomina veritativo-funcional . ^{[ 2 ]}

La lógica proposicional clásica es una lógica veritativo-funcional, ^{[ 3 ]} ya que cada enunciado tiene exactamente un valor de verdad que es verdadero o falso, y cada conector 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 conector lógico es veritativo-funcional si el valor de verdad de una oración compuesta es función del valor de verdad de sus suboraciones. Una clase de conectores es veritativo-funcional si cada uno de sus miembros lo es. Por ejemplo, el conector " y " es veritativo-funcional 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 conectores de un lenguaje natural, como el inglés, no son veritativo-funcionales.

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

" Mary cree que Al Gore era presidente de los Estados Unidos el 20 de abril de 2000. "

es cierto mientras

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

es falso. En ambos casos, cada oración componente (es decir, " Al Gore fue presidente de los Estados Unidos el 20 de abril de 2000 " y " la luna está hecha de queso verde ") es falsa, pero cada oración compuesta formada al anteponer la frase " Mary cree que " difiere en valor de verdad. Es decir, el valor de verdad de una oración de la forma " Mary cree que... " no está determinado únicamente por el valor de verdad de su oración componente, y por lo tanto el conector (unario) (o simplemente operador, ya que es unario) no es veritativo-funcional.

La clase de conectores lógicos clásicos (por ejemplo , & , → ) utilizados en la construcción de fórmulas es veritativo-funcional. Sus valores para distintos valores de verdad como argumentos suelen venir dados por 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 binaria, existen dieciséis funciones de verdad posibles, también llamadas funciones booleanas , para dos entradas P y Q. Cualquiera de estas funciones corresponde a una tabla de verdad de un conectivo lógico determinado en lógica clásica, incluyendo varios casos degenerados, como una función que no depende de uno o ambos argumentos. Para mayor brevedad, en las siguientes tablas de verdad se denotan la verdad y la falsedad como 1 y 0, respectivamente.

Dado que una función puede expresarse como una composición , un cálculo lógico veritativo-funcional no necesita símbolos específicos para todas las funciones mencionadas anteriormente para ser funcionalmente completo . Esto se expresa en un cálculo proposicional como la equivalencia lógica de ciertas proposiciones 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 lógica clásica si ya se utilizan "¬" (negación) y "∨" (disyunción).

Un conjunto mínimo de operadores que puede expresar cualquier enunciado expresable en el cálculo proposicional se denomina conjunto funcionalmente completo mínimo . Un conjunto funcionalmente completo mínimo se logra utilizando únicamente la operación NAND {↑} y únicamente la operación NOR {↓}.

Los siguientes son los conjuntos mínimos funcionalmente completos de operadores cuyas aridades no superan 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 \{\a ,\nleftrightarrow \}}$,${\displaystyle \{\gets ,\nleftrightarrow \}}$,${\displaystyle \{\a ,\nrightarrow \}}$,${\displaystyle \{\a ,\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 los teoremas que contienen el conector correspondiente. Algunas de esas propiedades que puede tener una función de verdad binaria (o un conector lógico correspondiente) son:

• Asociatividad : Dentro de una expresión que contiene dos o más conectores asociativos iguales en una fila, el orden de las operaciones no importa siempre que no se cambie la secuencia de los operandos.
• Conmutatividad : Los operandos del conector pueden intercambiarse sin afectar el valor de verdad de la expresión.
• Distributividad : Un conector denotado por · distribuye sobre otro conector denotado por +, si a · ( b + c ) = ( a · b ) + ( a · c ) para todos los operandos a , b , c .
• Idempotencia : Cuando los operandos de la operación son iguales, el conector proporciona el operando como resultado. En otras palabras, la operación preserva tanto la verdad como la falsedad (véase más abajo).
• absorción : Un par de conectores${\displaystyle \land ,\lor }$satisface la ley de absorción si${\displaystyle a\land (a\lor b)=a\lor (a\land b)=a}$para todos los operandos a , b .

Un conjunto de funciones de verdad es funcionalmente completo si y solo 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 }$.
• autodual : leer las asignaciones de valores de verdad para la operación de arriba a abajo en su tabla de verdad es lo mismo que tomar el complemento de leerla de abajo a arriba; en otras palabras, f (¬ a ₁ , ..., ¬ a _n ) = ¬ f ( a ₁ , ..., a _n ). Por ejemplo,${\displaystyle \neg }$.
• que preserva la verdad : La interpretación bajo 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,${\displaystyle \vee ,\wedge ,\top ,\rightarrow ,\leftrightarrow ,\subset }$(Ver validez )
• Preservación de la falsedad : La interpretación bajo 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,${\displaystyle \vee ,\wedge ,\nleftrightarrow ,\bot ,\not \subset ,\not \supset }$(Ver validez )

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 Φ y Ψ dos oraciones cualesquiera y sea la función de verdad f _nand definida como:

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

Entonces, por conveniencia, f _no , f _o f _y así sucesivamente se definen por medio de f _nand :

• f _no ( x ) = f _nand ( x , x )
• f _o ( x , y ) = f _nand ( 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 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.

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

Utilizando las funciones definidas anteriormente, podemos dar una definición formal de la función de verdad de una proposición. ^{[ 6 ]}

Sea PROP el conjunto de todas las variables proposicionales,

${\displaystyle PROP=\{p_{1},p_{2},\dots \}}$

Definimos una asignación de verdad como cualquier función${\displaystyle \phi :PROP\to \{T,F\}}$Por lo tanto, una asignación de verdad es la asociación de cada variable proposicional con un valor de verdad específico. Esto equivale, en esencia, a una fila concreta de la tabla de verdad de una proposición.

Para una tarea de verdad,${\displaystyle \phi }$, definimos su asignación de verdad extendida ,${\displaystyle {\overline {\phi }}}$, como sigue. Esto se extiende${\displaystyle \phi }$a una nueva función${\displaystyle {\overline {\phi }}}$cuyo dominio es igual al conjunto de todas las fórmulas proposicionales. El rango de${\displaystyle {\overline {\phi }}}$todavía${\displaystyle \{T,F\}}$.

1. Si${\displaystyle A\in PROP}$entonces${\displaystyle {\overline {\phi }}(A)=\phi (A)}$.
2. Si A y B son fórmulas proposicionales cualesquiera, entonces
   1. ${\displaystyle {\overline {\phi }}(\neg A)=f_{\text{not}}({\overline {\phi }}(A))}$.
   2. ${\displaystyle {\overline {\phi }}(A\land B)=f_{\text{and}}({\overline {\phi }}(A),{\overline {\phi }}(B))}$.
   3. ${\displaystyle {\overline {\phi }}(A\lor B)=f_{\text{or}}({\overline {\phi }}(A),{\overline {\phi }}(B))}$.
   4. ${\displaystyle {\overline {\phi }}(A\to B)={\overline {\phi }}(\neg A\lor B)}$.
   5. ${\displaystyle {\overline {\phi }}(A\leftrightarrow B)={\overline {\phi }}((A\to B)\land (B\to A))}$.

Finalmente, ahora que hemos definido la asignación de verdad extendida, podemos usarla para definir la función de verdad de una proposición. Para una proposición, A , su función de verdad ,${\displaystyle f_{A}}$, tiene dominio igual al conjunto de todas las asignaciones de verdad y rango igual a${\displaystyle \{T,F\}}$.

Se define, para cada asignación de verdad${\displaystyle \phi }$, por${\displaystyle f_{A}(\phi )={\overline {\phi }}(A)}$. El valor dado por${\displaystyle {\overline {\phi }}(A)}$es la misma que la que se muestra en la última columna de la tabla de verdad de A , en la fila identificada con${\displaystyle \phi }$.

Los operadores lógicos se implementan como compuertas lógicas en los circuitos digitales . Prácticamente todos los circuitos digitales (la principal excepción es la DRAM ) se construyen a partir de compuertas NAND , NOR , NOT y de transmisión . Las compuertas NAND y NOR con 3 o más entradas, en lugar de las 2 habituales, son bastante comunes, aunque son lógicamente equivalentes a una cascada de compuertas 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 compuertas lógicas mencionadas.

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

El hecho de que todas las funciones de verdad puedan expresarse únicamente con la operación NOR queda demostrado por el ordenador de guiado del Apolo .

• Este artículo incorpora material de TruthFunction en PlanetMath , que está bajo la licencia Creative Commons Attribution/Share-Alike License .

• 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 una historia del concepto de función de verdad.