función de verdad

Una función en lógica clásica

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 todas valores de verdad; una función de verdad siempre generará exactamente un valor de verdad, y al ingresar los mismos valores de verdad siempre se generará 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 conectivos lógicos ; Si el valor de verdad del enunciado compuesto está completamente determinado por el valor de verdad del enunciado constituyente, el enunciado compuesto se llama función de verdad y cualquier conectivo lógico utilizado se dice que es funcional de verdad . ^[2]

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

Descripción general

Un conectivo lógico es funcional de verdad si el valor de verdad de una oración compuesta es función del valor de verdad de sus suboraciones. Una clase de conectivos es verdaderamente funcional si cada uno de sus miembros lo es. Por ejemplo, el conectivo " y " es funcional de verdad ya que una oración como " Las manzanas son frutas y las zanahorias son verduras " es verdadera si, y sólo 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 una lengua natural, como el inglés, no son verdaderamente funcionales.

Los conectivos de la forma "x cree que ..." son ejemplos típicos de conectivos que no son verdaderamente funcionales. 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 frase

" Mary cree que Al Gore era presidente de 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 EE. UU. el 20 de abril de 2000 " y " la luna está hecha de queso verde ") es falsa, pero cada oración compuesta se forma con el prefijo " Mary cree que "difiere en el 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 la oración que la compone y, por lo tanto, por el operador conectivo (unario) (o simplemente, ya que es unario). ) no es funcional a la verdad.

La clase de conectivos de lógica clásica (p. ej., & , → ) utilizados en la construcción de fórmulas es funcional de verdad. Sus valores para diversos valores de verdad como argumento suelen estar dados por tablas de verdad . El cálculo proposicional funcional de verdad es un sistema formal cuyas fórmulas pueden interpretarse como verdaderas o falsas.

Tabla de funciones de verdad binarias

En lógica de dos valores , 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 la 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 indican como 1 y 0, respectivamente, en las siguientes tablas de verdad en aras de la brevedad.

Completitud funcional

Debido a que una función puede expresarse como una composición , un cálculo lógico funcional de verdad 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 ciertos enunciados compuestos. 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 clásico si "¬" (no) y "∨" (o) ya están en uso.

Un conjunto mínimo de operadores que pueden expresar cada enunciado expresable en el cálculo proposicional se denomina conjunto mínimo funcionalmente completo . 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 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 \}}$

Propiedades algebraicas

Algunas funciones de verdad poseen propiedades que pueden expresarse en los 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 conectivos asociativos iguales seguidos, el orden de las operaciones no importa siempre que no se cambie la secuencia de los operandos.
• conmutatividad : Los operandos del conectivo se pueden intercambiar 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 son iguales, el conectivo da el operando como resultado. En otras palabras, la operación preserva la verdad y preserva 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 cinco propiedades siguientes contiene al menos un miembro que carece de ella:

• monótono : 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 . P.ej,. ${\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. P.ej,, . ${\displaystyle \neg ,\leftrightarrow }$ ${\displaystyle \not \leftrightarrow ,\top ,\bot }$
• self dual : 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 hacia arriba; en otras palabras, f (¬ a ₁ , ..., ¬ a _n ) = ¬ f ( a ₁ , ..., a _n ). P.ej, . ${\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. P.ej, . (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. P.ej, . (ver validez ) ${\displaystyle \vee ,\wedge ,\nleftrightarrow ,\bot ,\not \subset ,\not \supset }$

arity

Una función concreta también puede denominarse operador . En la lógica de dos valores hay 2 operadores nulares (constantes), 4 operadores unarios , 16 operadores binarios , 256 operadores ternarios y operadores n -arios. En lógica de tres valores hay 3 operadores nulares (constantes), 27 operadores unarios , 19683 operadores binarios , 7625597484987 operadores ternarios y operadores n -arios. En lógica con valores k , hay k operadores nulos, operadores unarios, operadores binarios, operadores ternarios y operadores n -arios. Un operador n -ario en lógica con valores k 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 menor aridad en algunas de las entradas e ignoran el resto de las entradas. De los 256 operadores booleanos ternarios citados anteriormente, se encuentran formas degeneradas de operadores binarios o de menor aridad, que utilizan el principio de inclusión-exclusión . El operador ternario es uno de esos operadores que en realidad es un operador unario que se aplica 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}$

"Not" es un operador unario , necesita un solo término (¬ P ). El resto son operadores binarios , que toman dos términos para formar una declaració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 operadores de aridad j . ${\displaystyle \Omega _{j}}$

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

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

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

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

Principio de composicionalidad

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 lo detalla 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 _n y definase como:

• f _{n y} (T,T) = F; f _ny (T,F) = f _ny (F,T) = f _ny (F,F) = T

Entonces, por conveniencia, f _not , f _o f _y así sucesivamente se definen mediante f _nand :

• f _no ( x ) = f _{n y} ( 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 _not , 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

• Yo (~) = Yo ( ) = f _no ${\displaystyle \neg }$
• Yo (&) = Yo ( ) = f _y ${\displaystyle \wedge }$
• I ( v ) = I ( ) = f _o ${\displaystyle \lor }$
• I (~ Φ ) = I ( Φ ) = I ( )( I ( Φ )) = f _no ( I ( Φ )) ${\displaystyle \neg }$ ${\displaystyle \neg }$
• I ( Φ Ψ ) = I ( )( I ( Φ ), I ( Ψ )) = f _y ( I ( Φ ), I ( Ψ )) ${\displaystyle \wedge }$ ${\displaystyle \wedge }$

etc.

Por lo tanto, 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 conectivos lógicos y símbolos no lógicos c ₁ ... c _n , entonces si y solo si I ( v ₁ ) ... A I ( v _n ) se le ha proporcionado la interpretación de v ₁ a v _n mediante f _nand (o cualquier otro conjunto de funciones de verdad funcionales completas), entonces el valor de verdad de está determinado completamente por los valores de verdad de c ₁ ... cn _, es decir de I ( c ₁ )... I ( cn ) _. En otras palabras, como se esperaba y se requería, S es verdadero o falso sólo bajo una interpretación de todos sus símbolos no lógicos. ${\displaystyle I(s)}$

Ciencias de la Computación

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 ) se construyen a partir de NAND , NOR , NOT y puertas 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 lógicamente son equivalentes a una cascada de puertas de 2 entradas. Todos los demás operadores se implementan dividié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 sola", "NOR sola" y "NOT y AND" es similar a la equivalencia de Turing .

El hecho de que todas las funciones de verdad se pueden expresar sólo con NOR lo demuestra la computadora de guía Apollo .

Ver también

• Portal de filosofía
• Portal de psicología

• Bertrand Russell y Alfred North Whitehead ,
  Principia Mathematica , 2.ª edición
• Ludwig Wittgenstein ,
  Tractatus Logico-Philosophicus , Proposición 5.101
• Operación bit a bit
• función binaria
• dominio booleano
• lógica booleana
• Función con valor booleano
• Lista de temas de álgebra booleana
• Constante lógica
• operador modal
• Cálculo proposicional
• Lógica proposicional funcional de verdad

Notas

1. Roy T. Cook (2009). Diccionario de lógica filosófica , p. 294: Función de verdad. Prensa de la Universidad de Edimburgo.
2. Roy T. Cook (2009). Diccionario de lógica filosófica , p. 295: Verdad Funcional. Prensa de la Universidad de Edimburgo.
3. Enciclopedia de Filosofía de Internet: lógica proposicional, por Kevin C. Klement
4. Roy T. Cook (2009). Diccionario de lógica filosófica , p. 47: Lógica clásica. Prensa de la Universidad de Edimburgo.
5. Wernick, William (1942) "Conjuntos completos de funciones lógicas", Transactions of the American Mathematical Society 51 : 117–32. En su lista de la última página del artículo, Wernick no distingue entre ← y →, ni entre y . ${\displaystyle \nleftarrow }$ ${\displaystyle \nrightarrow }$

Referencias

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

Otras lecturas

• 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, Nueva Jersey: Princeton University Press. Consulte la Introducción para conocer la historia del concepto de función de verdad.