Bloque de Colores

Lógica – Definiciones y Formulas Básicas

Icono de Post June 19 2008 :: Lógica ::

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

Una curiosidad de Haskell

Icono de Post June 17 2008 :: Haskell, Lógica, Programación Funcional ::

En el ejemplo del capitulo 2.8 de The Haskell Road To Logic, Math and Programming, la formula:

∀x ∈ {1,2,3} ∃y ∈ {1,4,9} x = y2

Se codifica como:


every, some :: [a] -> (a -> Bool) -> Bool
every xs p = all p xs
some xs p = any p xs
every [1,4,9] (x -> some [1,2,3] (y -> x = y^2))

Después en el Ej 2.51 se propone definir una función unique :: (a -> Bool) -> [a] -> Bool
que retorne True para unique p xs solo cuando haya un solo elemento de xs que cumpla con p.

La forma obvia de resolverlo es:


unique :: (a -> Bool) -> [a] -> Bool
unique p [] = False
unique p xs = length(filter p xs) == 1

Que se puede testear con:


unique (x -> x>4) [1,2,3,4,5]
True
unique (x -> x>4) [1,2,3,4,5,6]
False

Sin embargo es interesante pensarlo en la formula de Russell para Unicidad: ∃x ( Φ(x) ∧ ∀y ( Φ(y) => x=y ) ) . Que se puede hacer como:


unique1 :: (Eq a) => (a -> Bool) -> [a] -> Bool
unique1 p xs = some xs (x -> p x && every xs (y -> p y ==> x == y))
unique1 (x -> x>4) [1,2,3,4,5]
True
unique1 (x -> x>4) [1,2,3,4,5,6]
False

Lo interesante es que usando expresiones lambda llegamos a una formula que expresa prácticamente idéntica la original.

Autor: Emiliano Martínez Luque.

Comments Off on Una curiosidad de Haskell