Dualidad conjunción/disyunción

Propiedades que vinculan la conjunción y la disyunción lógicas

En lógica proposicional y álgebra de Boole , existe una dualidad entre conjunción y disyunción , ^{[1] [2] [3]} también llamada principio de dualidad . ^{[4] [5] [6]} Es el ejemplo más conocido de dualidad en lógica. ^[1] La dualidad consiste en estos teoremas metalógicos :

• En la lógica proposicional clásica , los conectivos para la conjunción y la disyunción se pueden definir en términos uno del otro y, en consecuencia, solo uno de ellos debe tomarse como primitivo. ^{[4] [1]}
• Si se utiliza como notación para designar el resultado de reemplazar cada instancia de conjunción con disyunción, y cada instancia de disyunción con conjunción (por ejemplo, con , o viceversa), en una fórmula dada , y si se utiliza como notación para reemplazar cada letra de oración en con su negación (por ejemplo, con ), y si el símbolo se utiliza para consecuencia semántica y ⟚ para equivalencia semántica entre fórmulas lógicas, entonces es demostrable que  ⟚  , ^{[4] [7] [6]} y también que si, y solo si, , ^[7] y además que si  ⟚  entonces  ⟚  . ^[7] (En este contexto, se llama dual de una fórmula .) ^{[4] [5]} ${\displaystyle \varphi ^{D}}$ ${\displaystyle p\land q}$ ${\displaystyle q\lor p}$ ${\displaystyle \varphi }$ ${\displaystyle {\overline {\varphi }}}$ ${\displaystyle \varphi }$ ${\displaystyle p}$ ${\displaystyle \neg p}$ ${\displaystyle \models }$ ${\displaystyle \varphi ^{D}}$ ${\displaystyle \neg {\overline {\varphi }}}$ ${\displaystyle \varphi \models \psi }$ ${\displaystyle \psi ^{D}\models \varphi ^{D}}$ ${\displaystyle \varphi }$ ${\displaystyle \psi }$ ${\displaystyle \varphi ^{D}}$ ${\displaystyle \psi ^{D}}$ ${\displaystyle {\overline {\varphi }}^{D}}$ ${\displaystyle \varphi }$

Definibilidad mutua

${\displaystyle \varphi \lor \psi :\equiv \neg (\neg \varphi \land \neg \psi ).}$(1)

${\displaystyle \varphi \land \psi :\equiv \neg (\neg \varphi \lor \neg \psi ).}$(2)

${\displaystyle \neg (\neg \varphi \lor \neg \psi )\equiv \neg \neg (\neg \varphi \land \neg \psi )\equiv \varphi \land \psi .}$(3)

Completitud funcional

Dado que el Teorema de la Forma Normal Disyuntiva muestra que el conjunto de conectivos es funcionalmente completo , estos resultados muestran que los conjuntos de conectivos y son funcionalmente completos también. ${\displaystyle \{\land ,\lor ,\neg \}}$ ${\displaystyle \{\land ,\neg \}}$ ${\displaystyle \{\lor ,\neg \}}$

Leyes de De Morgan

Las leyes de De Morgan también se derivan de las definiciones de estos conectivos en términos de cada uno de ellos, cualquiera sea la dirección que se tome para hacerlo. ^[1]

${\displaystyle \neg (\varphi \lor \psi )\equiv \neg \varphi \land \neg \psi .}$(4)

${\displaystyle \neg (\varphi \land \psi )\equiv \neg \varphi \lor \neg \psi .}$(5)

Propiedades de dualidad

El dual de una oración es lo que se obtiene intercambiando todas las ocurrencias de ∨ y &, mientras que también se niegan todas las constantes proposicionales. Por ejemplo, el dual de (A & B ∨ C) sería (¬A ∨ ¬B & ¬C). El dual de una fórmula φ se denota como φ*. El principio de dualidad establece que en la lógica proposicional clásica, cualquier oración es equivalente a la negación de su dual. ^{[4] [7]}

Principio de dualidad: Para todo φ, tenemos que φ = ¬(φ*). ^{[4] [7]}

Demostración: Por inducción sobre la complejidad. Para el caso base, consideramos una oración atómica arbitraria A. Como su dual es ¬A, la negación de su dual será ¬¬A, que es de hecho equivalente a A. Para el paso de inducción, consideramos un φ arbitrario y suponemos que el resultado se cumple para todas las oraciones de menor complejidad. Tres casos:

1. Si φ es de la forma ¬ψ para algún ψ, entonces su dual será ¬(ψ*) y la negación de su dual será, por tanto, ¬¬(ψ*). Ahora bien, como ψ es menos complejo que φ, la hipótesis de inducción nos da que ψ = ¬(ψ*). Por sustitución, esto nos da que φ = ¬¬(ψ*), es decir, que φ es equivalente a la negación de su dual.
2. Si φ es de la forma (ψ ∨ χ) para algunos ψ y χ, entonces su dual será (ψ* & χ*), y la negación de su dual será, por lo tanto, ¬(ψ* & χ*). Ahora bien, como ψ y χ son menos complejos que φ, la hipótesis de inducción nos da que ψ = ¬(ψ*) y χ = ¬(χ*). Por sustitución, esto nos da que φ = ¬(ψ*) ∨ ¬(χ*) lo que a su vez nos da que φ = ¬(ψ* & χ*) por la Ley de DeMorgan. Y eso es, una vez más, decir simplemente que φ es equivalente a la negación de su dual.
3. Si φ tiene la forma ψ ∨ χ, el resultado se sigue por razonamiento análogo.

Más teoremas de dualidad

Supóngase . Entonces , por sustitución uniforme de por . Por lo tanto, , por contraposición ; por lo tanto, finalmente, , por la propiedad de que  ⟚  , que se acaba de demostrar arriba. ^[7] Y como , también es cierto que si, y sólo si, . ^[7] Y se sigue, como corolario, que si , entonces . ^[7] ${\displaystyle \phi \models \psi }$ ${\displaystyle {\overline {\phi }}\models {\overline {\psi }}}$ ${\displaystyle \neg P_{i}}$ ${\displaystyle P_{i}}$ ${\displaystyle \neg \psi \models \neg \phi }$ ${\displaystyle \psi ^{D}\models \phi ^{D}}$ ${\displaystyle \varphi ^{D}}$ ${\displaystyle \neg {\overline {\varphi }}}$ ${\displaystyle \varphi ^{DD}=\phi }$ ${\displaystyle \varphi \models \psi }$ ${\displaystyle \psi ^{D}\models \phi ^{D}}$ ${\displaystyle \phi \models \neg \psi }$ ${\displaystyle \phi ^{D}\models \neg \psi ^{D}}$

Formas normales conjuntivas y disyuntivas

Para una fórmula en forma normal disyuntiva , la fórmula estará en forma normal conjuntiva , y dado el resultado de que § La negación es semánticamente equivalente a dual, será semánticamente equivalente a . ^{[8] [9]} Esto proporciona un procedimiento para convertir entre la forma normal conjuntiva y la forma normal disyuntiva. ^[10] Dado que el Teorema de la Forma Normal Disyuntiva muestra que cada fórmula de lógica proposicional es expresable en forma normal disyuntiva, cada fórmula también es expresable en forma normal conjuntiva por medio de efectuar la conversión a su dual. ^[9] ${\displaystyle \varphi }$ ${\displaystyle {\overline {\varphi }}^{D}}$ ${\displaystyle \neg \varphi }$

Referencias

^{[11] [12]}

1. «Dualidad en lógica y lenguaje | Enciclopedia de filosofía en Internet» . Consultado el 10 de junio de 2024 .
2. "1.1 Operaciones lógicas". www.whitman.edu . Consultado el 10 de junio de 2024 .
3. Look, Brandon C. (25 de septiembre de 2014). The Bloomsbury Companion to Leibniz. Bloomsbury Publishing. pág. 127. ISBN 978-1-4725-2485-0.
4. Howson, Colin (1997). Lógica con árboles: una introducción a la lógica simbólica . Londres; Nueva York: Routledge. pp. 41, 44–45. ISBN 978-0-415-13342-5.
5. "Álgebra de Boole, Parte 1 | Repaso de ICS 241". courses.ics.hawaii.edu . Consultado el 10 de junio de 2024 .
6. Kurki-Suonio, R. (20 de julio de 2005). Una teoría práctica de sistemas reactivos: modelado incremental de comportamientos dinámicos. Springer Science & Business Media. págs. 80–81. ISBN 978-3-540-27348-6.
7. Bostock, David (1997). Lógica intermedia . Oxford: Nueva York: Clarendon Press; Oxford University Press. págs. 62–65. ISBN. 978-0-19-875141-0.
8. Robinson, Alan JA; Voronkov, Andrei (21 de junio de 2001). Manual de razonamiento automatizado. Gulf Professional Publishing. pág. 306. ISBN 978-0-444-82949-8.
9. Polkowski, Lech T. (3 de octubre de 2023). Lógica: libro de referencia para científicos informáticos: la segunda edición revisada, modificada y ampliada de "Lógica para las ciencias de la computación y de los datos, y la inteligencia artificial". Springer Nature. pág. 70. ISBN 978-3-031-42034-4.
10. Bagdasar, Ovidiu (28 de octubre de 2013). Matemáticas informáticas concisas: tutoriales sobre teoría y problemas. Springer Science & Business Media. pág. 36. ISBN 978-3-319-01751-8.
11. Makridis, Odysseus (2022). Lógica simbólica . La filosofía de Palgrave hoy. Cham, Suiza: Palgrave Macmillan. p. 133. ISBN 978-3-030-67395-6.
12. Lyons, John (2 de junio de 1977). Semántica: Volumen 1. Cambridge University Press. pág. 145. ISBN 978-0-521-29165-1.