La lógica propositiva es una axiomatización de la lógica booleana. Como tal, la lógica predicada incluye la lógica proposicional. Se sabe que ambos sistemas son consistentes, por ejemplo, exhibiendo modelos en los que se satisfacen los axiomas.
La lógica propositiva se puede decidir, por ejemplo, por el método de las tablas de verdad:
[Tabla de la verdad -- Wikipedia]
y "completo" en el sentido de que toda tautología del cálculo sentencial (básicamente una expresión booleana sobre variables que representan "frases", es decir, que son Verdaderas o Falsas) puede ser probada en la lógica proposicional (y a la inversa).
La lógica de predicados (también llamada cálculo de predicados y lógica de primer orden) es una extensión de la lógica proposicional a las fórmulas que implican términos y predicados. La lógica de predicado completa es indecidible:
[Lógica de primer orden Wikipedia]
Es "completo" en el sentido de que todas las afirmaciones del cálculo del predicado que se satisfacen en cada modelo pueden ser probadas en la "lógica del predicado" y a la inversa. Este es un famoso teorema de Gödel (disertación, 1929):
[Teorema de la integridad de Gödel -- Wikipedia]
Nota: Como comentó Doug Spoonwood, hay formalizaciones tanto de la lógica propositiva como de la lógica predicada que prescinden de axiomas per se y dependen enteramente de reglas de inferencia . Una presentación común sólo invocaría modus ponens como la única regla de inferencia y la múltiple esquemas del axioma . El punto importante para una lógica formal es que debe ser posible reconocer (con pasos finitos) si una afirmación en una prueba está lógicamente justificada, ya sea como un ejemplo de esquemas axiomáticos o por una regla de inferencia a partir de afirmaciones previamente establecidas.
