Antes de entrar en esa especificación, aclaremos que si de lo que se trata es de diseñar un algoritmo que dé los mismos resultados que un proceso de demostración, en lógica de proposiciones puede aplicarse un procedimiento trivial basado en las tablas de verdad (Apartado 3.3.1) y que no precisa de ninguna «simulación» del proceso de demostración. Basta construir la tabla de verdad de la conjunción de las premisas y de la conclusión; si para todas las interpretaciones en que la conjunción se evalúa como «1» (se satisface) la conclusión también se evalúa como «1» entonces las premisas implican la conclusión. Es una aplicación directa de la definición de «implicación lógica» (Apartado 3.4.1).
Por ejemplo, para el razonamiento de la página anterior la tabla de verdad resultante sería:
P1 | P2: | P3: | P1P2P3 | C | ||||||
p | q | r | s | p q | q (¬s r) | ¬(s) | p r | |||
I0: | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | |
I1: | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | |
I2: | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | |
I3: | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | |
I4: | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | |
I5: | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | |
I6: | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | |
I7: | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | |
I8: | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | |
I9: | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |
I10: | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | |
I11: | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | |
I12: | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | |
I13: | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | |
I14: | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | |
I15: | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | |
Como se puede comprobar, las cuatro clases de interpretaciones que satisfacen a las tres premisas también satisfacen a la conclusión, luego las premisas implican la conclusión.
Es más, podemos caracterizar todas las posibles conclusiones implicadas por las premisas. En efecto, como hemos visto en el Apartado 3.4.2, con cuatro variables proposicionales las infinitas sentencias que pueden formarse con ellas se clasifican en 216 clases de equivalencia. De ellas, las que se satisfacen para las cuatro clases de interpretaciones I0, I2, I6 e I14 sin importar si se satisfacen o no para las demás (212 clases) engloban a sentencias equivalentes implicadas por las premisas.
Todo esto debe resultar familiar para el lector que conoce el álgebra de Boole y su aplicación a circuitos digitales, pero para nuestro propósito tiene poco interés. La razón es que, como ya hemos dicho en la introducción a este Capítulo, el principal motivo para estudiar la lógica de proposiciones es su utilidad para presentar de manera simplificada conceptos que en lógica de predicados resultan más difíciles de entender. Pero en lógica de predicados es imposible aplicar estos procedimientos algebraicos. Volvamos, por tanto, al enfoque inicial: ¿cómo podemos diseñar un algoritmo que haga demostraciones (Apartado3.6.2)?