Miguel Rebollo

Abr 28

Lógica proposicional

Empecemos por el principio. La lógica proposicional es la más sencilla. El lenguaje está basado en proposiciones o enunciados declarativos que son enunciados que pueden evaluarse como ciertos o falsos. Normalmente, se emplean símbolos distintos p, q, r,… para cada enunciado y a partir de ellos se pueden generar expresiones más complejas con operadores lógicos de la forma habitual, usando $\land, \lor, \neg, \to$ . Por ejemplo, $(p \land q) \to (\neg r \lor q)$ . Una fórmula bien formada (f.b.f.) se construye empleando exclusivamente las reglas siguientes:

cualquier átomo $p, q, r, \ldots$ es una f.b.f.
si $\phi$ es una f.b.f., también lo es $(\neg\phi)$
si $\phi, \psi$ son f.b.f., también lo es $(\phi \land \psi )$
si $\phi, \psi$ son f.b.f., también lo es $(\phi \lor \psi )$
si $\phi, \psi$ son f.b.f., también lo es $(\phi \to \psi )$

Otra forma de indicar estas reglas de construcción es usar una gramática BNF, de la forma

$\phi ::= p \mid (\neg \phi) \mid (\phi \land \phi) \mid (\phi \lor \phi)\mid (\phi \to \phi)$

La semántica de las expresiones anteriores viene dada por la tabla de verdad correspondiente, que examina el valor de verdad de la expresión $\phi$ a partir de todas las combinaciones posibles de los valores de verdad de las proposiciones atómicas. Por ejemplo, para la expresión anterior $(p \land q) \to (\neg r \lor q)$ , la tabla de verdad equivalente sería

Tabla de verdad

p	q	r	¬r	p∧q	¬r∨q	(p∧q)→(¬r∨q)
T	T	T	F	T	T	T
T	T	F	T	T	T	T
T	F	T	F	F	F	T
T	F	F	T	F	T	T
F	T	T	F	F	T	T
F	T	F	T	F	T	T
F	F	T	F	F	F	T
F	F	F	T	F	T	T

Las reglas de deducción nos permiten construir sistemas de argumentación basados en la lógica, de modo que podemos llegar a una conclusión $\psi$ (podemos deducir $\psi$ ) a partir de una serie de proposiones $\phi_1, \phi_2,\ldots,\phi_n$ . Lo representaremos como

$\phi_1, \phi_2,\ldots,\phi_n \vdash \psi$

Por otro lado, si además para todas las valuaciones en las que las proposiciones $\phi_1, \phi_2,\ldots,\phi_n$ se evalúan a T, $\psi$ también se evalúa a T, entonces se cumple

$\phi_1, \phi_2,\ldots,\phi_n \models \psi$

donde $\models$ es la relación de equivalencia semántica. A partir de estos dos conceptos, deducción y equivalencia semántica, puede estudiarse la corrección (soundness) y la completitud (completeness) de la lógica proposicional. Suelen definirse a partir de estos teoremas

Teorema 1 (corrección). Sean $\phi_1, \phi_2,\ldots,\phi_n$ y $\psi$ fórmulas proposicionales. Si $\phi_1, \phi_2,\ldots,\phi_n \vdash \psi$ es válido entonces se cumple $\phi_1, \phi_2,\ldots,\phi_n \models \psi$ .

Básicamente, el Teorema 1 quiere decir que todo aquello que se puede deducir a partir de las proposiciones utilizando las reglas de inferencia mantiene el valor de verdad de las proposiciones. O dicho de otra manera, todo lo que se puede deducir es cierto.

Teorema 2 (completitud). Sean $\phi_1, \phi_2,\ldots,\phi_n$ y $\psi$ fórmulas proposicionales. Si se cumple $\phi_1, \phi_2,\ldots,\phi_n \models \psi$ entonces existe una prueba que permite deducir $\phi_1, \phi_2,\ldots,\phi_n \vdash \psi$ .

De la misma forma, el Teorema 2 quiere decir que si dos expresiones tienen el mismo valor de verdad, podríamos encontrar una argumentación que nos permita deducir una de la otra. O dicho de otra forma, todo lo que es cierto puede deducirse.

Post relacionados

One Response to “Lógica proposicional”

Miguel Rebollo » Blog Archive » Lógica de predicados Says:
Abril 30th, 2009 at 12.26
[...] lógica proposicional falla cuando desaeamos expresar cosas como todos…, sólo…, existe… La lógica de [...]

Lógica proposicional

Tabla de verdad

Post relacionados

One Response to “Lógica proposicional”

Leave a Reply

Qué hago ahora...

Categorías

Enlaces - Sitios relacionados

Blogroll - Sitios que leo

Otros sitios de interés

Archivos

Últimas anotaciones

Comentarios recientes

Contacto