¿Por qué necesitamos la integridad funcional de verdad?

Question

Esto puede sonar un poco demasiado básico, tal vez demasiado básico para la mayoría de la gente a hablar. La pregunta parece vagamente estructurado - no estoy seguro de cómo decirlo mejor.

Pregunta: ¿por Qué necesitamos la verdad, la plenitud funcional en la lógica? Una razón que se me ocurre es que permite describir como muchas de las propiedades de un modelo como existen (por una propiedad me refiero a una fórmula). Así que en lugar de la caracterización de un modelo de una propiedad, usted es capaz de enumerar todas las posibles propiedades que pueden caracterizar. Esto debería permitir derivar teoremas más que si se tratara de las conectivas que no eran verdad funcionalmente completo, en el que caso de que usted podría ser capaz de enumerar menos propiedades. Es mi razonamiento correcto? Es que todo lo que hay?

EDIT: Vamos a definir un conjunto de conectivos lógicos como la verdad funcionalmente completa iff estas conectivas puede generar cada verdad de la función (finito de arity) a través de la composición (versión informal de la uno en la Wikipedia).

Answer 1

Su razonamiento parece correcto.

Sin embargo, me gustaría añadir que si un conjunto de conectivas califica como verdad-funcional completa, que nos dice que todas las funciones con la misma entrada y de salida de los juegos pueden obtener calculada. La verdad funcionalmente conjunto incompleto de las conectivas tiene algunas funciones en el conjunto de valores de verdad que no se puede conseguir calculada. Esto no es sólo acerca de los teoremas, sino también sobre el contingente de las proposiciones y las contradicciones. Pensemos en el conjunto de Una de 1-ary, 2-ary, ... la verdad de las funciones que para cada función devuelve Verdadero no importa lo que se de entrada. Una tiene el mismo conjunto de tautologías como de costumbre axioma conjunto (bajo el uniforme de sustitución y desprendimiento) para el cálculo proposicional, tales como {CCpqCCqrCpr, CCNppp, CpCNpq}. Sin embargo, que el conjunto de verdad de las funciones no es verdad-funcionalmente completa, a diferencia de {C, N} en {True, False}, ya que todas las fórmulas que puede ser expresada con las conectivas de Un son tautologías.

La verdad-la plenitud funcional también nos ayuda a comparar la expresión de suficiencia de idiomas. Si un idioma no es verdad-funcionalmente completo, entonces no es tan potente como un lenguaje que es expresamente completa (poderoso en términos de expresar los estados que corresponden a la verdad de las funciones). Por ejemplo, supongamos que queremos diseñar una máquina que calcula la suma de los positivos números naturales utilizando las puertas de la lógica y la aritmética binaria desarrollado a partir de puertas lógicas. Si utilizamos la verdad funcionalmente completo conjunto de primitivas puertas de la lógica, que probablemente puede hacer esto mucho más fácil que si utilizamos la verdad funcionalmente conjunto incompleto de las primitivas puertas de la lógica (si podemos hacer tal a todos el uso de una verdad-funcionalmente conjunto incompleto de las primitivas puertas de la lógica).

Así que, la verdad-la plenitud funcional, en efecto, nos dice que no podemos obtener de una manera más expresiva conjunto de conectivas (o las puertas de la lógica), utilizando el mismo conjunto de entradas (aunque si cambiamos la entrada y salida de conjunto a partir de {True, False}, {0, 1, 2}, entonces tenemos más poder expresivo). O en otras palabras, la verdad-funcional de la integridad nos dice que nosotros tenemos una de las posibilidades para la máxima potencia en términos de expresividad con el conjunto actual de las conectivas y la misma entrada y salida de los conjuntos.