Lógica proposicional

La lógica proposicional es la más antigua y simple de las formas de lógica. Utilizando una representación primitiva del lenguaje, permite representar y manipular afirmaciones  sobre el mundo que nos rodea.

La lógica proposicional permite el razonamiento, a través de un mecanismo que primero evalúa proposiciones simples y luego proposiciones complejas, formadas mediante el uso de conectores proposicionales. Este mecanismo determina la veracidad de una proposición compuesta, analizando los valores de verdad asignados a las proposiciones simples que la conforman. 

Datos Curiosos

Proposiciones y Conectores

En lógica proposicional, las formulas bien formadas (f.b.f) son proposiciones, los cuales son enunciados que admiten un único valor de verdad, el cual puede ser Verdadero que se denota "V" o Falso y se escribe "F". 

Las proposiciones se pueden denotar ya sea con letras mayúsculas latinas P, Q, R, etc... (Estás son las mas usadas) o colocando indices (indexar) cada una de ellas tales como: P_1, P_2,  P_{3, ....}P_n donde n puede asumir cualquier valor natural. 

Tomando en cuenta que toda proposición tiene una cierta cantidad de posibilidades lógicas; es decir, para 1 proposición existe 2 = 2¹ posibilidades lógicas, para dos proposiciones son 4 = 2², para tres proposiciones 8 =2³ posibilidades lógicas, ed decir la cantidad de posibilidades lógicas crece exponencialmente con base 2, por lo tanto, en el caso que tengo n proposiciones, entonces hay 2^n.
Las proposiciones se pueden clasificar en dos grupos:

1. Proposición simple: es cuando se encuentra solo un proposición.
2. Proposición compuesta: en este se encuentran varias proposiciones unidas o enlazadas por lo menos un conector lógica ( v,  ∧ ,→,  ↔ ).

   ↔↔ ↔

Tautologias, Indeterminaciones y Contradicciones.

Tablas de verdad. 

Estas tablas pueden construirse haciendo una interpretación de los signos lógicos ~, v , ∧, →, ↔, como:  no, o, y, ...entonces, si y sólo si, respectivamente.  La interpretación corresponde al sentido que estas operaciones tienen dentro del razonamiento. 

Debemos tener en cuenta que las tablas de verdad constituyen un método de decisión para chequear si una proposición es o no un teorema. 

Para la construcción de la tabla se asignará el valor 1, o la letra "V" a una proposición cierta y 0 ( cero) o l letra "F" a una proposición falsa.

Al elaborar una tabla de verdad, podemos concluir:




Tautología: Cuando se puede concluir que todo es verdadero.




Contradicción: Cuando se peude concluir que todo es falso.
Indeterminación: Es cuando no se presenta ni una tautología ni una contradicción,. Por lo tanto la "última columna" de su tabla de verdad estará formada tanto por verdades como falsedades. 

1. Sistema formal

Un sistema formal es un lenguaje formal dotado de un mecanismo deductivo. Los sistemas formales induce la creación de teorías científicas o el apoyo para estas.



La construcción de sistemas formales induce la creación de modelos que describen de una mejor forma los fenómenos que aquellos mitos no logran explicar.

El sistema formal se divide entre: 

1. Reglas de Formación

1.1 Todo elemento de P es una formula bien formada ( f.b.f)
1.2 Si α es una fórmula bien formada entonces ~α es una formula bien formada. 
1.3 Si son α,β f.b.f entonces αvβ es una f.b.f
1.4 Solo serán f.b.f las cadenas que se generan al aplicar las primeras tres reglas.

2. Definiciones

 Sean P, Q proposiciones, entonces:

2.1 Definición de la conjunción: 
( P ∧ Q ) ↔ [ ~(~ P v ~ Q) ]

2.2 Definición del condicional: 
(P → Q) ↔ (~P v Q)

2.3 Definición del bicondicional:
     (P ↔ Q) ↔ [( P → Q) ∧ (Q → P) ]
     (P ↔ Q) ↔ [ (~~P v Q) ∧ ( ~ Q v P) ]
     (P ↔ Q) ↔ ~[~(~P v Q) ∧ ~(~Q v P) ]

En el sistema formal igualmente podemos encontrar el mecanismo deductivo, este mecanismo lo veremos en la siguiente entrada. 

1.1 Mecanismo Deductivo

El mecanismo deductivo se divide entre axiomas y reglas de inferencias.

1.Axiomas 

Para la lógica proposicional se establecen cuatro (4) axiomas que son:

1.1 Axioma de idempotencia: Sea P una proposición, entonces: 
( P v P ) → P

1.2  Axioma de adjunción: Sean P y Q proposiciones, entonces:
P → ( P v Q) 

1.3 Axioma de conmutatividad: Sean P y Q  proposiciones, entonces:
(P v Q ) → ( Q v P )

1.4 Axioma de adición a la implicación: Sean P, Q y R proposiciones, entonces: 
( P → Q ) → [ ( R v P ) → ( R v Q )  ] 

Intuitivamente, estos axiomas no sonmás que la expresión del sentido que se atribuye a las palabra o "v" e implica "→" dentro del lenguaje matemático usual. 

2. Reglas de inferencias.

Las reglas de inferencia permiten deducir dichas proposiciones a partir de los axiomas.

2.1 Todo axioma es verdadero y puede figurar en cualquier paso de una deducción o demostración.

2.2 Toda proposición obtenida por la aplicación de un axioma es verdadera y puede figurar en cualquier paso de una deducción. 

2.3 Modus Ponendo Ponens ( MPP)

 P → Q

P       

_________

Q

2.4 Sustitución si P ↔ Q se puede sustituir P por Q o Q por P en cualquier momento de una deducción o demostración. 

Teoremas

Teoremas

Para deducir cada uno de los teoremas de la teoría que se va ha construir no existe un algoritmo, una estrategia o camino único, puesto que la deducción es un acto creativo donde se ponen en juego todas las herramientas que se tienen y la imaginación misma. Esas herramientas de las que se está hablando son las definiciones, axiomas, reglas de inferencia y los teoremas demostrados con anterioridad.

Para construir una deducción de un teorema se puede hacer en Forma de texto, también llamada Prosa o por medio de una estrategia llamada Afirmación - Razón. En el primer caso, la demostración se escribe como una narración en la que a través de las palabras se va hilando el conjunto de argumentos que llevarán a probar la verdad de la proposición a demostrar. En el segundo caso, se hace una lista de las deducciones y se escribe en frente la justificación o razón de lo que se va efectuando, a través de la utilización de los axiomas, definiciones, reglas de inferencia o teoremas ya demostrados.

Cada una de las definiciones, reglas de inferencias, axiomas o teoremas que se utilizan dentro de un sistema deben ser proposiciones que generen tautologías.

Teorema: Transitividad

El teorema de la Transitividad o Silogismo.

Si P →Q      y      Q  → R son proposiciones verdades entonces P  → R es una proposición verdadera. 

P  → Q

Q → R

_______________

P  → R

Demostración en prosa:

Teniendo (1)P→Q y (2)Q→R como hipótesis, aplicamos la definición de condicional en (1), a continuación se aplica la adición entre implicaciones y tendremos (3)(Q→R)→(~PvQ→~PvR) seguido de un Modus Ponendo Ponens (MPP) entre (2) y (3) y dará como resultado: ~PvQ→~PvR, repetimos de nuevo el MPP ; para concluir aplicamos la definición de condicional y tendremos la preposición a demostrar : P→R

Tomado del Reeimpreso. Lógica y teoria de conjuntos. Diana, Juan Carlos.

Teorema: Medio Excluido

Teorema: Medio excluido

Si P es una proposición entonces

       1. P  → P es una proposición verdadera.
       2. ~P v P  es una proposición verdadera.
       3. P v ~P  es una proposición verdadera.

Demostración en prosa: 

Debido a que P es una proposición entonces por el axioma de adjunción se tiene que P  → P v P (1); mientras que por el axioma de idempotencia resulta el condicional P v P  → P (2); haciendo uso del teorema de transitividad entre las implicaciones (1) y (2) se obtiene que P  → P es una proposición verdadera y así el primer literal queda demostrado. Ya que está concluida la veracidad de P  → P, se hace uso de la definición de condicional con la que ~P v P   es una proposición verdadera y el literal 2 esta demostrado. Ahora bien, ya que ~P v P  → P v ~P (3) por el axioma de conmutatividad y ~P v P (4) es verdadera entonces aplicando la regla de inferencia Modus Ponendo Ponens (MPP) entre (3) y (4) se logra que P v ~P es una proposición verdadera. 

Teorema: Doble negación

Teorema: Doble negación

Sea P una proposición entonces
     
      1. P  → ~(~P) es una proposición verdadera.
       2. ~(~P)  → P es una proposición verdadera. 

Demostración en prosa:

Al usar el teorema del medio excluido ~Pv~(~P) aplicamos en este la definición de condicional y tendremos P→~(~P) que es el primer literal a demostrar.

Se usa de nuevo el medio excluido ~(~P)v~(~(~P)) en este aplicamos la definición de condicional, aplicamos  adición a la  implicación y tenemos Pv~P→Pv~(~(~P)). Se usa  medio excluido Pv~P, entre las   dos   afirmaciones anteriores usar   el teorema del MPP. Con el axioma   de   conmutatividad   Pv(~(~P))→~(~(~P))vP  aplicando el MPP se concluye   ~(~(~P))vP, para concluir usamos definición de condicional y  se tendra ~(~P)→P

Teorema: Conjunción

Teorema: Conjunción 


Si P y Q son proposiciones verdaderas entonces P ^ Q es una proposición verdadera. En forma esquemática

P

Q

____________

P ^ Q

Demostración [Prosa]

Las hipótesis en este caso es que tanto P como Q son verdaderas. Por el teorema de doble negación se tiene que P →~ (~ P) es una proposición verdadera que por modus ponendo ponens con P resulta que ~ (~ P) es una proposición verdadera. Con base en el axioma de adjunción se sigue que ~ (~ P) →~ (~ P)v ~ Q y por modus ponendo ponens con ~ (~ P) se obtiene que ~ (~ P)v ~ Q es una proposición verdadera, que por la definición de condicional se escribe como ~ P →~Q (1).

Si al condicional obtenido en (1) se aplica el axioma de adición a la implicación (respecto de la proposición ~ Q) se logra ~Qv ~ P →~ Qv ~ Q (2); como ~ Qv ~ Q →~ Q (3) esto por el axioma de idempotencia, entonces al aplicar la transitividad entre los condicionales dados en (2) y (3) resulta ~ Qv ~ P  → ~ Q (4) . Debido a que ~ Pv ~ Q →~ Qv ~ P esto por el axioma de conmutatividad entonces por el teorema de transitividad ~ Pv ~Q →~Q, que al aplicar la definición de condicional se tiene ~ (~ Pv ~ Q)v ~ Q (5)

La expresión (5) se puede escribir como ~ Qv ~ (~ Pv ~ Q) que por la definición de condicional Q →~ (~ Pv ~ Q), al ser Q una proposición verdadera entonces por un modus ponendo ponens se tiene que ~ (~ Pv ~ Q)  es una proposición verdadera, con base en la definición de conjunción se concluye que P ^ Q es una proposición verdadera, siempre que P y Q sean verdaderas. 

A partir del teorema de conjunción es posible obtener teoremas que hayan uso del bicondicional, ya que de acuerdo con la definición de este conector, P ↔ Q equivale a (P → Q) ^ (Q → P) y asì hacer uso de la regla de inferencia de sustitución. La primer consecuencia es que el teorema de doble negación se puede escribir en términos de un bicondicional.

Teorema: Doble negación-equivalencia

Teorema: Doble Negación-Equivalencia

Sea P una proposición entonces

P ↔~ (~ P)

es una proposición verdadera.

Demostración en prosa.

Al usar el teorema de la doble negación (1)P→~(~P)  y  ("2~(~P)→P  se une a (1) y (2) por medio de la conjunción, usamos la definición de bicondicional y tendremos P←→~(~P).

Teorema: Contrarrecìproco

Teorema: Contrarrecíproco

Sean P y Q  preposiciones entonces

(P → Q) ↔ (~ Q → ~ P) 

es una proposición verdadera.

Demostración [Prosa] 

Por el axioma de conmutatividad se tiene ~ P v Q → Qv ~ P (1), puesto que Q es equivalente a ~ (~ Q) por el teorema de doble negación, así en (1) 

~ P v Q →~ (~ Q)v ~ P

La anterior proposición se escribe como (P → Q) → (∼ Q →∼ P) (2) debido a la definición de condicional. Por un razonamiento análogo Q∨ ∼ P →∼ P ∨ Q es una proposición verdadera por el axioma de conmutatividad y esto conduce al condicional (∼ Q →∼P) → (P → Q) (3) que al aplicar el teorema de conjunción entre las proposición (2) y (3) se escribe 

(P → Q)→ (∼ Q →∼ P)     ∧    (∼ Q →∼ P) → (P → Q) 

Que según la definición del bicondicional se concluye (P → Q)↔ (∼ Q →∼ P).

Teorema: Simplificación

Teorema: Simplificación. 

Si P ∧Q es una proposición verdadera entonces P es una proposición verdadera y Q es una proposición verdadera. Esquemáticamente se escribe 

P ∧ Q 

_________

P

Q

Demostración en prosa: 

Se tiene (1)P∧Q como hipótesis y se busca llegar a P, Q.
Se usa el axioma de adjunción que dice (2)~P→(~Pv~Q) a este le aplicamos el contrarreciproco, aplicamos en este la definición de conjunción: (3)P∧Q→~(~P), usando el MPP entre (1) y (3)  y con la doble negación se concluye P.
Se usa el axioma de adjunción (4)~Q→(~Qv~P), aquí aplicamos el axioma de conmutatividad, seguido del contrarreciproco y quedara (5)~(~Pv~Q)→~(~Q); aplicamos a P∧Q→~(~P) la definición de conjunción , entre (1) y (5) aplicamos el MPP y después aplicando aplicando la doble negación  se concluye Q.

Teorema: Conmutatividad

Teorema: Conmutatividad

Sean P, Q proposiciones entonces

       1. P ∨Q ↔ Q∨P 
       2. P ∧Q ↔ Q∧P

Demostración [Prosa]

Por medio del axioma de conmutatividad se tiene que P ∨ Q → Q ∨ P y Q ∨ P → P ∨ Q, que por el teorema de conjunción se obtiene

P ∨ Q → Q ∨ P     ∧     Q ∨ P → P ∨ Q 

Con base en la definición de bicondicional se sigue que P∨Q ↔ Q∨P con esto se concluye la demostración del literal 1. Por el axioma de conmutatividad ∼ Q∨∼ P →∼ P∨∼ Q, que al aplicar el teorema del contrarrecíproco se tiene ∼ (∼ P∨∼ Q) →∼ (∼ Q∨∼ P) y así por la definición de conjunción resulta P ∧Q → Q∧P (1); un razonamiento análogo conduce a Q∧P → P ∧Q, que por conjunción con (1) se tiene 

P ∧Q → Q∧P ∧ Q∧P → P ∧Q 

De donde se concluye que P ∧Q ↔ Q∧P.

Teorema: Equivalencia

Teorema: Equivalencia 

Sean P, Q proposiciones entonces 

   1. Medio Excluido P ↔ P
   2. Recíproco (P ↔ Q) ↔ (Q ↔ P)
   3. Contrarrecíproco (P ↔ Q) ↔ (∼ Q ↔∼P)

Demostración en prosa: 

Por Medio excluido tenemos que (1)P→P, se usa de nuevo (2)P→P, se hace conjunción entre (1) y(2) ya por definición de bicondicional tenemos que P↔P conmutamos con respecto a la conjunción y tendremos (P→Q∧Q→P)↔(Q→P∧P→Q) usamos la definición de bicondicional luego su contrarreciproco sera (P→Q∧Q→P)↔(~Q→~P∧~P→~Q), para finalizar usamos la definición de bicondicional y se concluira (P↔Q)↔(~Q↔~P)

Teorema: Idempotencia

Teorema: Idempotencia

 Sea P una proposición entonces 
    1. P ∨P ↔ P
    2. P ∧P ↔ P

Demostración [Prosa]


Por el axioma de idempotencia P∨P → P (1), mientras que por el axioma de idempotencia P → P ∨P (2), aplicando una conjunción entre las implicaciones (1) y (2) se tiene 

P ∨P → P ∧ P → P ∨P

En cuyo caso P ∨ P ↔ P por la definición de bicondicional y así se verifica el literal 1. Si se hace uso de lo que se acaba de demostrar respecto de la proposición ∼ P resulta ∼ P∨ ∼ P ↔∼ P (3); como el contrarrecíproco también se satisface con el bicondicional, entonces en (3) ∼ (∼ P) ↔∼ (∼ P∨∼ P), por la doble negación y la definición de conjunción P ↔ P ∧P, al utilizar de nuevo el teorema de equivalencia literal 2 se concluye que P ∧P ↔ P. 

Teorema: Adición entre implicaciones

Teorema: Adición entre implicaciones 

Si P → Q y R → S son proposiciones verdaderas entonces 

    1. P ∨R → Q∨S es una proposición verdadera 

P → Q 

R → S 

_______________

P ∨R → Q∨S 

    2. P ∧R → Q∧S es una proposición verdadera 

P → Q 

R → S 

_______________

P ∧R → Q∧S 

Demostración en prosa: 

Tomando P→Q y R→S como hipótesis  usamos en P→Q la adición a la implicación, luego  aplicamos el axioma de conmutatividad , después aplicamos en R→S la adición a la implicación y tenemos que QvR→QvS, usamos la transitividad  quedando PvR→QvS se aplica el contrarreciproco en P→Q , luego en R→S , despues se usa el literal de este teorema entre ~Q→~P~ y ~S→~R y nos dara como resultado ~Qv~S→~Pv~R aplicamos su contrarreciproco . para finalizar usamos la definición de conjunción  y tendremos P∧R→Q∧S

Teorema: Método de casos

Teorema: Método de casos

Si P → Q, R → S y P ∨R son proposiciones verdaderas entonces Q∨S es una proposición verdadera. Esquemáticamente 

P → Q 

R → S 

P ∨ R 

_________

Q ∨ S

Demostración [Prosa]

Por hipótesis se tienen las implicaciones P → Q y R → S, que al aplicar el teorema de adición entre implicaciones resulta el condicional P ∨R → Q∨S;(1), ya que P ∨R (2) es la otra hipótesis entonces por el modus ponendo ponens entre (1) y (2) se concluye que Q∨S es una proposición verdadera. 

Para la utilización del método de casos se requieren dos condicionales y una disyunción compuesta por los antecedentes de los condicionales. Sin embargo el método de casos se puede reformular también si la tercer premisa se sustituye por P ∧R para concluir Q∧S.

Teorema: Modus Tolendo Ponens

Teorema: Modus Tolendo Ponens

Sean P, Q proposiciones

    1. Si P∨Q y∼ Q son proposiciones verdaderas entonces P es una proposición verdadera. 

P ∨ Q 

∼ Q

_________

 P 

2. Si P∨Q y∼ P son proposiciones verdaderas entonces Q es una proposición verdadera. 

P ∨ Q

∼ P 

_________

Q

DEMOSTRACIÓN EN PROSA:

Tomamos PvQ y ~Q como hipótesis aplicamos la conmutatividad en PvQ y tendremos QvP

aplicamos la doble negación y quedara ~(~Q)vP usando en esta la definición de condicional tenemos que ~Q→P y haciendo MPP con ~Q concluimos P.

Luego usamos PvQ y ~P como hipótesis, aplicamos la doble negación en PvQ y tendremos ~(~P)vQ por definición de condicional tenemos que ~P→Q y aplicanodo  MPP con ~P concluimos  Q

Teorema: Modus Tolendo Tolens

Teorema: Modus Tolendo Tolens

Si P → Q y ∼ Q son proposiciones verdaderas entonces ∼P es una proposición verdadera.

P → Q 

∼ Q 

___________

∼P

Demostración [Prosa]

Por hipótesis P → Q, al aplicar el teorema del contrarrecíproco resulta ∼ Q →∼ P, ya que ∼ Q es hipótesis entonces por un modus ponendo ponens se concluye que ∼ P es una proposición verdadera. 

Teorema: Ley D' Morgan

Teorema: Ley D' Morgan

Sean P, Q proposiciones entonces 

    1. ∼ (P ∧Q)↔ (∼ P∨∼ Q) 
    2. ∼ (P ∨Q)↔ (∼ P∧∼ Q)  
    3. ∼ (P → Q)↔ P∧∼ Q

Demostración en prosa :

Por definición de condicional tenemos que P∧Q↔~(~Pv~Q) aplicamos el teorema de equivalencia,luego se usa la doble negación y tendremos (~Pv~Q)↔~(~P∧Q), después usamos la doble equivalencia y concluimos (~P∧Q)↔(~Pv~Q).

De nuevo se usa la definición de condicional en el literal 2 luego aplicamos la doble negación y  con el teorema de la equivalencia concluimos ~(PvQ)↔ (~P∧~Q).

Por definición de condicional tenemos que (P→Q)↔(~PvQ) aplicando a este el teorema de equivalencia nos dará como resultado ~(~PvQ)↔~(PvQ). El literal
↔ ↔

Teorema: Asociativa

Teorema: Asociativa 

Sean P, Q, R proposiciones entonces

     1. (P ∨Q)∨R ↔ P ∨(Q∨R) 
     2. (P ∧Q)∧R ↔ P ∧(Q∧R)

Demostración [Prosa]

Por el axioma de adjunción Q → Q∨R, que por el axioma de adición a la implicación se escribe P∨Q → P∨(Q∨R) (1). A su vez R → R∨Q que por la conmutatividad R → Q∨R, para lo que P ∨R → P ∨(Q∨R) (2). Como R → R∨P → P ∨R que al aplicar la transitividad con el condicional (2) resulta R → P ∨(Q∨R) (3); por el teorema de adición entre implicaciones en este caso entre (1) y (3) se obtiene (P∨Q)∨R → [P∨(Q∨R)]∨[P∨(Q∨R)] que por el teorema de idempotencia equivale a (P ∨Q)∨R → P ∨(Q∨R) (4).

Con base en el axioma de adjunción resulta que P → P ∨Q, como R → R por el medio excluido entonces al hacer uso de la adición entre implicaciones resulta P ∨R → (P ∨Q)∨ R (5). De igual manera Q → Q∨P → P ∨Q que al adicionarle la proposición R a ambos lados se tiene Q∨R → (P∨Q)∨R (6). Debido a que P → P∨R entonces por transitividad con la expresión (5) resulta P → (P ∨Q)∨R que al aplicar la adición entre implicación con (6) y la propiedad de idempotencia se concluye que P ∨(Q∨R) → (P ∨Q)∨R (7). Aplicando el teorema de conjunción entre (4) y (7) 

[(P ∨Q)∨R → P ∨(Q∨R)]∧[P ∨(Q∨R)→ (P ∨Q)∨R] 

Y así se concluye la propiedad asociativa para la disyunción P ∨(Q∨R) ↔ (P ∨Q)∨R. Para demostrar el literal 2 se sustituye P, Q y R por sus respectivas negaciones ∼ P, ∼ Q y ∼ R para tener (∼ P∨∼ Q)∨∼ R ↔∼ P∨(∼ Q∨∼ R); debido al teorema de equivalencia respecto del contrarrecíproco se obtiene 

∼ [∼ P ∨(∼ Q∨∼ R)] ↔∼ [(∼ P∨∼ Q)∨∼ R] 

Por medio de la ley de D’Morgan se sigue que

∼ (∼ P)∧∼ (∼ Q∨∼ R)↔∼ (∼ P∨∼ Q)∧∼ (∼ R) 

Una doble negación y de nuevo otra ley D’Morgan 

P∧∼ (∼ Q∨∼ R) ↔∼(∼ P∨∼ Q)∧R 

Por la definición de conjunción P ∧(Q∧R) ↔ (P ∧Q)∧R, y el teorema de equivalencia se concluye la propiedad asociativa para la conjunción (P ∧Q)∧R ↔ P ∧(Q∧R).