Lógica proposicional/Deducciones directas

Lección 10

Deducciones directas

La lógica proposicional nos permite derivar información nueva a partir de la que conocemos usando diferentes técnicas. La forma más sencilla de hacerlo es construyendo una tabla de verdad con todos los posibles valores para las proposiciones atómicas, las premisas y la conclusión que queremos lograr. Si la conclusión es verdadera en todas las filas de la tabla en que las premisas son verdaderas, podemos decir que la conclusión es una consecuencia lógica de las premisas. Este método garantiza que siempre encontraremos una respuesta, sin embargo las tablas de verdad aumentan de tamaño de forma exponencial y pueden llegar a ser muy grandes incluso al tratar con problemas de tamaño moderado. Por ejemplo, una tabla con 8 proposiciones atómicas necesitará 256 filas para registrar todas las combinaciones posibles de valores de verdad de las variables.^[1]

Como una alternativa al procedimiento anterior, podemos intentar determinar la validez de un argumento al reducir el proceso de razonamiento a una serie de pasos, cada uno de los cuales está justificado por las premisas o por los pasos anteriores y que consiste en la aplicación de una forma de razonamiento sencilla y reconocida universalmente como válida. Este método de razonamiento se conoce como deducción natural y en el caso de la lógica proposicional consiste en la aplicación de las equivalencias lógicas y de las reglas de inferencia sobre las premisas y sobre proposiciones derivadas en pasos anteriores.^[2]

Existen diferentes técnicas de deducción natural y una de ellas es la deducción directa. Una deducción directa de una conclusión a partir de una lista de premisas consiste en una lista ordenada de fórmulas bien formadas, donde la conclusión es el miembro final de la lista y cada miembro de la secuencia cumple una de las siguientes condiciones:^[2]

Es una premisa.
Es derivado a partir de miembros anteriores en la secuencia usando reglas de inferencia.
Es derivado a partir de un miembro anterior en la secuencia al reemplazarlo con una proposición lógicamente equivalente.

Procedimiento

Las demostraciones por deducción directa tienen los siguientes elementos básicos:^[2]

Un identificador único para cada proposición en la secuencia.
La lista de proposiciones que forman la secuencia.
La descripción de la equivalencia lógica o regla de equivalencia aplicadas en cada caso para generar la siguiente proposición en la secuencia, o la indicación de que se trata de una premisa.
Los indicadores de las proposiciones anteriores en la secuencia sobre las que se aplican las reglas de inferencia o las equivalencias lógicas para obtener la proposición actual (dependencias).

Esta información se puede organizar en forma de tabla para facilitar su visualización. Por ejemplo, si nos piden verificar si una proposición $M$ es una consecuencia lógica de las siguientes premisas:

$C\lor D$
$C\Rightarrow O$
$D\Rightarrow M$
$\neg O$

Podemos crear la siguiente tabla:

Identificador	Proposición	Regla	Dependencias
1	$C\lor D$	Premisa	n/a
2	$C\Rightarrow O$	Premisa	n/a
3	$D\Rightarrow M$	Premisa	n/a
4	$\neg O$	Premisa	n/a
...	...	...	...
?	$M$	Conclusión	?

El siguiente paso es agregar filas adicionales para reemplazar la fila con puntos suspensivos con proposiciones derivadas de las premisas hasta llegar a la conclusión. La siguiente tabla muestra el proceso completo de razonamiento:

Identificador	Proposición	Regla	Dependencias
1	$C\lor D$	Premisa	n/a
2	$C\Rightarrow O$	Premisa	n/a
3	$D\Rightarrow M$	Premisa	n/a
4	$\neg O$	Premisa	n/a
5	$\neg C$	Modus tollens (MT)	2, 4
6	$D$	Silogismo disyuntivo (SD)	1, 5
7	$M$	Modus ponens (MP)	3, 6

Por lo anterior podemos decir que la proposición $M$ es una consecuencia lógica de las premisas, a través de la aplicación de las reglas de inferencia modus tollens, silogismo disyuntivo y modus ponens.

Un ejemplo completo

Considere el siguiente argumento:

Si Juan obtiene el puesto de gerente y trabaja mucho, entonces recibirá un aumento. Si recibe el aumento entonces comprará una casa. Juan no ha comprado una casa. Por lo tanto, no ha obtenido el puesto de gerente o no ha trabajado mucho.

Lo primero que se debe hacer es expresar las afirmaciones de forma simbólica:

A: Juan obtiene el puesto de gerente.
B: Juan trabaja mucho.
C: Juan recibe un aumento.
D: Juan compra una casa.

Luego se deben identificar las premisas y la conclusión y escribirlas en forma proposicional:

Premisa: Si Juan obtiene el puesto de gerente y trabaja mucho, entonces obtendrá un aumento.

(A\land B)\Rightarrow C

Premisa: Si recibe el aumento entonces comprará una casa.

C\Rightarrow D

Premisa: Juan no ha comprado una casa.

\neg D

Conclusión: Juan no ha obtenido el puesto de gerente o no ha trabajado mucho.

\neg A\lor \neg B

Finalmente organizamos las premisas en una tabla y aplicamos las equivalencias lógicas y las reglas de inferencia para determinar si la conclusión es una consecuencia lógica de las premisas proporcionadas en la definición del problema.

Identificador	Proposición	Regla	Dependencias
1	$(A\land B)\Rightarrow C$	Premisa	n/a
2	$C\Rightarrow D$	Premisa	n/a
3	$\neg D$	Premisa	n/a
4	$\neg C$	Modus tollens (MT)	2, 3
5	$\neg (A\land B)$	Modus tollens (MT)	1, 4
6	$\neg A\lor \neg B$	Ley de De Morgan para la conjunción	5

Resumen de la lección

La lógica proposicional nos permite derivar información nueva a partir de la que conocemos.
Las demostraciones usando tablas de verdad pueden requerir tablas de verdad significativamente grandes.
La deducción natural permite validar si una conclusión es una consecuencia lógica de las premisas.
La deducción directa consiste en la aplicación de reglas de inferencia y equivalencias lógicas sobre una secuencia de proposiciones para llegar de las premisas a la conclusión.
Cada miembro de una secuencia de proposiciones en una deducción directa debe ser una premisa o una consecuencia de las proposiciones anteriores.

Términos clave

Bibliografía

↑ Aho, Alfred V.; Ullman, Jeffrey D. (1994). Foundations of Computer Science: C Edition (en inglés) (1.ª edición). Estados Unidos: W. H. Freeman. p. 786. ISBN 978-071-67-8284-1.
↑ ^2,0 ^2,1 ^2,2 Klement, Kevin. «Propositional Logic». The Internet Encyclopedia of Philosophy (en inglés). Massachusetts, Estados Unidos. Consultado el 11 de diciembre de 2015.

Proyecto: Lógica proposicional

Anterior: Tercera evaluación parcial — Deducciones directas — Siguiente: Evaluación de la lección 10

[aho1994-1] Aho, Alfred V.; Ullman, Jeffrey D. (1994). Foundations of Computer Science: C Edition (en inglés) (1.ª edición). Estados Unidos: W. H. Freeman. p. 786. ISBN 978-071-67-8284-1.

[klement-2] 2,0 ^2,1 ^2,2 Klement, Kevin. «Propositional Logic». The Internet Encyclopedia of Philosophy (en inglés). Massachusetts, Estados Unidos. Consultado el 11 de diciembre de 2015.

[1]

[2]