Lógica proposicional

De Wikipedia, la enciclopedia libre

La lógica proposicional es una rama de la Lógica clásica que estudia las proposiciones o sentencias lógicas, sus posibles evaluaciones de verdad y en el caso ideal, su nivel absoluto de verdad.

Tabla de contenidos

1 Lógica proposicional
2 Lógica de predicados o de cuantificadores
3 Definición
4 Notación
5 Definiciones
6 Teoría
7 Operadores Lógicos
8 Véase también

[editar] Lógica proposicional

Proposiciones. Formalmente hablando, se define una proposición como un enunciado declarativo que puede ser verdadero o falso, pero no ambos a la vez. Las proposiciones se representan mediante variables proposicionales simbolizadas mediantes letras. Con la combinación de variables proposicionales y conjunciones, definidas como functores o funciones de verdad, se obtienen fórmulas sentenciales o sentencias. Estas pueden ser, según su tabla de verdad:

Tautología: es la sentencia que es necesariamente verdadera.
Contradicción: es la sentencia que es necesariamente falsa.
Contingencia: es la sentencia que puede ser verdadera o falsa.

[editar] Lenguaje formal del cálculo de proposiciones

Sintaxis: El primer paso en el estudio de un lenguaje es definir los símbolos básicos que lo constituyen (alfabeto) y cómo se combinan para formar sentencias. Está constituido por:

Símbolos de veracidad: V para verdadero y F para falso.
Símbolos de variables: p, q, r, s, ...
Símbolos de conectivas: ¬, ∧, ∨, XOR, →, ↔
Símbolos de puntuación: ( , ), para evitar ambigüedades.

Reglas de formación. Las clases de sentencias bien formadas se definen por reglas puramente sintácticas, llamadas reglas de formación, y que son:

Una variable proposicional es una sentencia bien formada.
Una sentencia bien formada precedida de la negación es una sentencia bien formada.
Dos sentencias bien formadas unidas por una de las partículas conectivas binarias constituye una sentencia bien formada.
Se pueden omitir los paréntesis que encierran una sentencia completa.
El estilo tipográfico de los paréntesis se puede variar para hacerlos más evidentes usando corchetes y llaves.
A las conjunciones y disyunciones se les puede permitir tener más de dos argumentos.

Conectivas. Las conectivas se dividen por su aplicación en:

Singulares: se aplican a una única sentencia.
Binarias: se aplican a dos sentencias.

Por su definición, también se pueden dividir en:

Primitivas: las variables proposicionales, los paréntesis y las conectivas ¬ y ∨.
Definidas: las conectivas ∧, →, ↔, y XOR.

[editar] Tablas de verdad

La tabla de verdad de una sentencia es una tabla en la que se presentan todas las posibles interpretaciones de las variables proposicionales que constituyen la sentencia y el valor de verdad de la sentencia para cada interpretación.

Semántica

Negación (¬)

Consiste en cambiar el valor de verdad de una variable proposicional.

p	¬ p
V	F
F	V

Disyunción (∨)

La sentencia será verdadera cuando una o ambas variables proposicionales sean verdaderas.

p	q	p ∨ q
V	V	V
V	F	V
F	V	V
F	F	F

Conjunción (∧)

Es una conectiva que puede definirse como la composición:

p ∧ q = ¬(¬p ∨ ¬q)

La sentencia será verdadera sólo cuando ambas variables proposicionales sean verdaderas.

p	q	p ∧ q
V	V	V
V	F	F
F	V	F
F	F	F

Condicional (→)

Es una conectiva definida por:

p → q = ¬p ∨ q

La sentencia será verdadera cuando se cumpla si es válido p entonces lo es q.

p	q	p → q
V	V	V
V	F	F
F	V	V
F	F	V

Bicondicional (↔, si y sólo si)

Es una conectiva definida por:

p ↔ q = ((p → q) ∧ (q → p))

La sentencia será verdadera cuando ambas variables proposicionales sean iguales.

p	q	p ↔ q
V	V	V
V	F	F
F	V	F
F	F	V

Disyunción exclusiva (XOR)

Es una conectiva definida por:

p XOR q = ¬(p ↔ q)

La sentencia será verdadera sólo cuando una de las dos variables proposicionales sea verdadera.

p	q	p XOR q
V	V	F
V	F	V
F	V	V
F	F	F

[editar] Axiomas y reglas

Los axiomas para el cálculo proposicional son:

(p ∨ p) → p
q → (p ∨ q)
(p ∨ q) → (q ∨ p)
(p → q) → [ (r ∨ p) → (r ∨ q) ]

A partir de estos axiomas y aplicando las dos reglas de transformación siguientes se puede demostrar cualquier teorema:

Regla de sustitución: el resultado de reemplazar cualquier variable en un teorema por una sentencia bien formada es un teorema.
Regla de separación: si S y (S → R) son teoremas, entonces R es un teorema.

Relativo a un criterio de validación, un sistema axiomático debería cumplir las siguientes propiedades para ser un sistema perfecto:

Debe ser lógico o razonable: en el sentido de que todo teorema o es un axioma o la última secuencia de una deducción que se sigue de operaciones lógicas deductivas según las reglas especificadas.
Completo: toda sentencia bien formada válida es un teorema y se debe poder demostrar a partir de los axiomas.
Consistente: no se pueden demostrar como teoremas, sentencias bien formadas que no sean tautologías.
Deben ser independientes: ningún axioma debe ser derivable a partir de los otros.

Sin embargo, el teorema de Gödel demuestra que tal sistema perfecto no es posible.

[editar] Lógica de predicados o de cuantificadores

Cuando las proposiciones son analizadas respecto a los cuantificadores, el cálculo lógico se llama cuantificacional, como aplicación del álgebra de Boole, también entendida como lógica de clases. Con esta lógica se interpreta actualmente la lógica clásica aristotélica, o silogística.

Debido a que los computadores trabajan con información binaria, la herramienta matemática adecuada para el análisis y diseño de su funcionamiento es el Álgebra de Boole. El Algebra de Boole fue desarrollada inicialmente para el estudio de la lógica. Ha sido a partir de 1938, fecha en que Claude Shannon publicó un libro llamado "Análisis simbólico de circuitos con relés", estableciendo los primeros conceptos de la actual teoría de la conmutación, cuando se ha producido un aumento considerable en el número de trabajos de aplicación del Algebra de Boole a los computadores digitales. Hoy en día, esta herramienta resulta fundamental para el desarrollo de los computadores ya que, con su ayuda, el análisis y síntesis de combinaciones complejas de circuitos lógicos puede realizarse con rapidez.

[editar] Definición

Como la lógica proposicional es un Sistema formal primitivo, es necesario primero contar con una metateoría para definirlo; en este caso se utiliza la Teoría de conjuntos de Georg Cantor y la notación de Backus Näur para las definiciones.

Son necesarias las siguientes herramientas lógicas:

[editar] Notación

El conjunto de los Booleanos (por George Boole) denotado por la letra B, representa a 2 de los números naturales.
⊤ := 1
⊥ := 0

Observación: De esta manera, B = {⊤, ⊥}

[editar] Definiciones

Var := a | b | c | ... | x | y | z | Var_N
$\mbox{FLP := } \bot | \top | \mbox{Var} | (\mbox{FLP} \rightarrow \mbox{FLP})$
f es una evaluación si y sólo si $f\subseteq\mbox{Var}\times\mbox{B}$ y $(a,b)\in f \ni(a,c)\rightarrow b=c$ .
Sea f una evaluación y sea ; (se lee 'f' satisface 'alpha') si y sólo si:
1. $\alpha \in \mbox{Var y } f(\alpha) = \top$
2. $\beta,\gamma \in \mbox{FLP, }\alpha=(\beta\rightarrow\gamma) \mbox{ tal que }\neg f\vDash\beta \mbox{ o }f\vDash\gamma$

[editar] Teoría

Con las herramientas anteriores, es posible definir formalmente ya la Lógica proposicional.

La Lógica Proposicional o LP es una estructura $\langle\mbox{FLP,}\vDash\rangle$ con los siguientes axiomas:

Sean $\alpha,\beta,\gamma\in\mbox{FLP}\mbox{ y }f$ una función de evaluación.

$f\vDash\top \mbox{ y analogamente }\neg(f\vDash\bot)$
$f\vDash(\alpha\rightarrow(\beta\rightarrow\alpha))$ Si algo es verdadero, cualquier cosa lo implica
$f\vDash((\alpha\rightarrow(\beta\rightarrow\gamma))\rightarrow((\alpha\rightarrow\beta)\rightarrow(\alpha\rightarrow\gamma)))$ Distributibidad de la implicación sobre sí misma.
$f\vDash(((\beta\rightarrow\bot)\rightarrow(\alpha\rightarrow\bot))\rightarrow(((\beta\rightarrow\bot)\rightarrow\alpha)\rightarrow\beta))$ Reducción al absurdo

Y una Regla válida de inferencia

Modus ponens: $\frac{\alpha,(\alpha\rightarrow\beta)}{\beta}$

[editar] Operadores Lógicos

A partir de la implicación $\rightarrow$ y la constante $\bot$ es posible definir los demás operadores lógicos conocidos. Sean $\alpha,\beta\in\mbox{FLP}$

$\neg \alpha := (\alpha\rightarrow\bot)$
$(\alpha\land\beta) := \neg(\alpha\rightarrow\neg\beta)$
$(\alpha\vee\beta) := (\neg\alpha\rightarrow\beta)$
$(\alpha\leftrightarrow\beta) := ((\alpha\rightarrow\beta)\land(\beta\rightarrow\alpha))$