Del Algebra Booleana

Definiciones

∧ Conjunción, y
∨ Disyunción, o
¬ Negación, no

Equivalencias Basicas

Doble negación
p  ≡ ¬(¬p)

Idempotencia
p∧p ≡ p
p∨p ≡ p

De morgan
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q

Conmutativa
(p ∧ q) ≡ (q ∧ p)
(p ∨ q) ≡ (q ∨ p)

Asociativa
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

Distributiva
p ∧ (q ∨ r) ≡ (p ∨ q) ∧ (p ∨ r)
p ∨ (q ∧ r) ≡ (p ∧ q) ∨ (p ∧ r)

Absorción
p ∧ (p ∨ q) ≡ p
p ∨ (p ∧ q) ≡ p

Tautologia y Contradicción

T Tautologia, Verdad
⊥ Falacia, Contradicción, Falsedad

¬⊥ ≡ T
¬T ≡ ⊥

Dominancia
T ∨ p ≡ T
⊥ ∧ p ≡ ⊥

Identidad
T ∧ p ≡ p
⊥ ∨ p ≡ p

Ley del medio excluido
p ∨ ¬p ≡ T

Contradicción
p ∧ ¬p ≡ ⊥

Implicación, Doble Implicación, Disyunción exclusiva

Definiciones

=> Implicación, Si… Entonces
<=> Doble Implicación, Equivalencia, Si y solo si, iff
⊻ Disyunción exclusiva, xor

Equivalencias

Equiv:
p => q  ≡  q ∨ ¬p  ≡  ¬q => ¬p
p <=> q  ≡ (p => q) ∧ (q => p)  ≡ (p ∧ q) ∨ (¬p ∧ ¬q)  ≡ ¬ (p ⊻ q) ≡  ¬p <=> ¬q
p ⊻ q ≡ (p ∧ ¬q) ∨ (¬p ∧ q)  ≡  ¬( p <=> q)  ≡ ¬p ⊻ ¬q

Condición Necesaria y Suficiente

p => q
p es el antecedente.  Condición suficiente para q.
q es el consecuente. Condición necesaria para p.

Quantificadores

Definiciones

∃ Existe
∀ Para todo
En adelante voy a usar: Φ, Ψ (Phi, Psi) para representar Formulas.
Una estructura (o contexto) para una formula es:
1) Una especificación de un dominio para todos los cuantificadores. (ej: ∀x se especifica que x ∈ R)
2) Un significado para cualquier símbolo no especificado. (ej: xRy se especifica como x < y)

Φ Es valida si es Verdadera para cualquier estructura.
Φ ≡ Ψ <=> si se obtiene el mismo conjunto de valores de verdad en cualquier estructura. (Equivalencia entre formulas)

Equivalencias

∀x∀yΦ(x) ≡ ∀y∀xΦ(x)
∃x∃yΦ(x) ≡ ∃y∃xΦ(x)

¬∀xΦ(x)  ≡ ∃x¬Φ(x)
¬∃xΦ(x)  ≡ ∀x¬Φ(x)
¬∀x¬Φ(x)  ≡ ∃xΦ(x)
¬∃x¬Φ(x)  ≡ ∀xΦ(x)

∀x(Φ(x) ∧ Ψ(x)) ≡ (∀xΦ(x) ∧ ∀xΨ(x))
∃x(Φ(x) ∨ Ψ(x)) ≡ (∃xΦ(x) ∨ ∃xΨ(x))

∀x(Φ(x) ∨ Ψ(x)) ≢ (∀xΦ(x) ∨ ∀xΨ(x))
∃x(Φ(x) ∧ Ψ(x)) ≢ (∃xΦ(x) ∧ ∃xΨ(x))

Equivalencias con respecto al contexto.

∀x∈AΦ(x) ≡ ∀x(x∈A => Φ(x))
∃x∈AΦ(x) ≡ ∃x(x∈A ∧ Φ(x))

Referencias

Capitulo 1,2,3 de The Haskell Road To Logic, Math and Programming; Doets, Van Eijck; King´s College London Publications; 2004

Capitulo 1,2,3 de How to Prove It: A Structured Approach; Velleman, Daniel; Cambridge University Press; 2006