Lógica Proposicional

Definición. (Tautología)

Una tautología o ley lógica es una proposición que es siempre verdadera sin importar los valores de verdad que tengan las proposiciones que la componen.

Teorema. (Tautologías importantes)

• Doble negación:

• Tercero excluido: (verdadero o falso, no hay tercera opción)

• No contradicción: (base de las demostraciones sobre “reducción al absurdo”)

• Idempotencia:

• Conmutatividad:

• Asociatividad:

• Distributividad:

• Leyes de Morgan¹

• Transitividad impl. (silogismo hipotético)

• Implicación material:

• Contraposición:

• Más tautologías importantes:

Proof.

Usamos que si y sólo si y tienen siempre el mismo valor de verdad.

1. Doble negación. Si es V, ent. es F y es V; si es F, ent. es V y es F. En ambos casos y tienen el mismo valor de verdad.
2. Tercero excluido. Si es V, es V. Si es F, ent. es V y es V. Así, siempre es V.
3. No contradicción. (ver Leyes de DeMorgan)

que es siempre V por el tercero excluido.
4. Idempotencia. es V sii y son V, i.e. sii es V. Análogamente, es F sii es F.
5. Conmutatividad. es V sii ambas son V, lo cual no depende del orden, ent. . Análogamente, es F sii ambas son F.
6. Asociatividad. es V sii y son V, sii , y son V, sii y son V, sii es V. Para es lo mismo cambiando “V” por “F”.
7. Distributividad. Por casos sobre :
- Si es F: es F, y , son F, ent. es F.
- Si es V: tiene el valor de , y también tiene el valor de .

La segunda es análoga: si $p$ es V, ambos lados son V; si $p$ es F, ambos lados tienen el valor de $q \land r$.

8. Transitividad impl. P.D. que no puede pasar que el antecedente sea V y el consecuente F. Sup. que es V y que es F, i.e. es V y es F. Como es V y es V, ent. es V. Como es V, ent. es V, lo cual contradice que es F.
9. Implicación material. es F sólo cuando es V y es F; es F sólo cuando y son F, i.e. cuando es V y es F. Coinciden, ent. . Para la negación:

10. Contraposición.

11. Más tautologías.

Observación.

significa que es una tautología. Es decir, es un conectivo (forma una nueva proposición), mientras que es una relación entre proposiciones (dice que siempre tienen el mismo valor de verdad).

Notas

1. Leyes de DeMorgan ↩