Cálculo proposicional

Lógica proposicional

De Wikipedia, la enciclopedia libre

(Redirigido desde Cálculo proposicional)

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 Proposiciones
2 Estado de proposiciones
3 Sintaxis y notación
- 3.1 Lenguaje formal del cálculo de proposiciones
4 Tablas de verdad
5 Axiomas y reglas
6 Lógica de predicados o de cuantificadores
7 Aristóteles con respecto al estudio de la lógica
8 Véase también
9 Enlaces externos

[editar] Proposiciones

Una Proposicion, para los fines de esta discusion, es una declaracion la cual puede ser verdadera o falsa, por ejemplo: 5 > 4, 2+2=5, "Pedro comio a las 3", "Me gusta la sopa". Algunas veces es mas dificil que otras el determinar si la declaracion (o proposicion) es verdadera o falsa, en otras palabras, si toma el valor de verdad o falsedad, sin embargo eso no cambia el hecho de que existe solo una posibilidad, ya sea que la propuesta sea cierta o sea falsa. Algunas declaraciones que no califican con este criterio son "Tu sweater es bonito", ×² = 9, "¿ Como dijiste?".

Esta definicion de propuesta es una definicion formal, lo cual quiere decir que es una defincion que se ha hecho cuidadosamente de tal manera que todas las posibilidades han sido cubiertas, y que se ha hecho de tal manera que no existan ambiguedades ni malentendidos. En muchas ocasiones se utilizan letras para representar las proposiciones. Se dice que una proposicion es simple o atomica, si no esta compuesta por otra proposicion. Proposiciones compuestas se pueden crear al combinar connectores con proposiciones simples.

Definiciones:

Dadas las proposiciones P y Q La conjuncion de P y Q, cuya notacion es P $\wedge$ Q, es la proposicion P y Q. P $\wedge$ Q es verdadera unicamente cuando ambas P y Q son verdaderas.

La disjuncion de P y Q, cuya notacion es P $\vee$ Q, es la proposicion P o Q. P $\vee$ Q es verdadera unicamente cuando al menos una de las proposiciones P y Q es verdadera.

La negacion de P, cuya notacion es $\neg$ P, es la proposicion NO P. $\neg$ P es verdadera unicamente cuando P es falsa.

[editar] Estado de proposiciones

Segun el valor de verdad las proposiciones pueden estar en tres estados: o Tautología o validez: es una proposición que siempre es verdadera. o Contradicción: es una proposición que siempre es falsa. o Contingencia: es una proposición que puede ser verdadera o falsa

[editar] Sintaxis y notación

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: $\top$ para verdadero y $\bot$ para falso. Alternativamente se pueden usar $V$ para verdadero y $F$ para falso.
Símbolos de variables: $p$ , $q$ , ... , $z$
Símbolos de conectivas: $\neg$ , $\wedge$ , $\vee$ , $\rightarrow$ , $\leftrightarrow$
Símbolos de puntuación: paréntesis (), corchetes [] y llaves {} 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 (también llamada fórmula) 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.

[editar] Lenguaje formal del cálculo de proposiciones

El lenguaje formal de la lógica proposicional se puede generar con la gramática formal descrita usando la notación BNF como sigue:

$\begin{array}{rcl} \left\langle \mbox{Bicondicional}\right\rangle & ::= & \left\langle \mbox{Condicional}\right\rangle \leftrightarrow\left\langle \mbox{Bicondicional}\right\rangle \mid\left\langle \mbox{Condicional}\right\rangle \\ \left\langle \mbox{Condicional}\right\rangle & ::= & \left\langle \mbox{Conjuncion}\right\rangle \rightarrow\left\langle \mbox{Condicional}\right\rangle \mid\left\langle \mbox{Conjuncion}\right\rangle \\ \left\langle \mbox{Conjuncion}\right\rangle & ::= & \left\langle \mbox{Disyuncion}\right\rangle \vee \left\langle \mbox{Conjuncion}\right\rangle \mid\left\langle \mbox{Disyuncion}\right\rangle \\ \left\langle \mbox{Disyuncion}\right\rangle & ::= & \left\langle \mbox{Literal}\right\rangle \wedge\left\langle \mbox{Disyuncion}\right\rangle \mid\left\langle \mbox{Literal}\right\rangle \\ \left\langle \mbox{Literal}\right\rangle & ::= & \left\langle \mbox{Atomo}\right\rangle \mid\neg\left\langle \mbox{Atomo}\right\rangle \\ \left\langle \mbox{Atomo}\right\rangle & ::= & \top\mid\bot\mid\left\langle \mbox{Letra}\right\rangle \mid\left\langle \mbox{Agrupacion}\right\rangle\\ \left\langle \mbox{Agrupacion}\right\rangle & ::= & (\left\langle \mbox{Bicondicional}\right\rangle )\mid[\left\langle \mbox{Bicondicional}\right\rangle ]\mid\{\left\langle \mbox{Bicondicional}\right\rangle \} \end{array}$

La gramática anterior define la precedencia de operadores de la siguiente manera:

Negación ( $\neg$ )
Conjunción ( $\wedge$ )
Disyunción ( $\vee$ )
Implicación ( $\rightarrow$ )
Coimplicación ( $\leftrightarrow$ )

[editar] Tablas de verdad

Artículo principal: 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 ( $\neg$ )

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

$p$	$\neg p$
$V$	$F$
$F$	$V$

Disyunción ( $\vee$ )

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

$p$	$q$	$p\vee q$
$V$	$V$	$V$
$V$	$F$	$V$
$F$	$V$	$V$
$F$	$F$	$F$

Conjunción ( $\wedge$ )

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

$p$	$q$	$p\wedge q$
$V$	$V$	$V$
$V$	$F$	$F$
$F$	$V$	$F$
$F$	$F$	$F$

Condicional ( $\rightarrow$ )

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

$p$	$q$	$p \rightarrow q$
$V$	$V$	$V$
$V$	$F$	$F$
$F$	$V$	$V$
$F$	$F$	$V$

Bicondicional ( $\leftrightarrow$ )

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

$p$	$q$	$p\leftrightarrow q$
$V$	$V$	$V$
$V$	$F$	$F$
$F$	$V$	$F$
$F$	$F$	$V$

Disyunción exclusiva ( $\otimes$ )

Es una conectiva definida por:

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

$p$	$q$	$p\otimes 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

Artículo principal: Lógica de primer orden

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] Aristóteles con respecto al estudio de la lógica

La lógica es conocida como una de las ciencias más antiguas, tanto es así que se le atribuye a Aristóteles la paternidad de esta disciplina Partiendo de que corresponde a Aristóteles haber sido el primero en tratar con todo detalle la lógica, se le considera pues ser su fundador. En un principio se llamó Analítica, en virtud del titulo de las obras en que trató los problemas lógicos. Más tarde los escritos de Aristóteles relativos a estos eventos fueron recopilados por sus discípulos con el titulo de Organon, por considerar que la lógica era un instrumento para el conocimiento de la verdad. Aristóteles se planteo como es posible probar y demostrar que un conocimiento es verdadero, es decir, que tiene una validez universal. Aristóteles encuentra el fundamento de la demostración en la deducción, procedimiento que consiste en derivar un hecho particular de algo universal. La forma en que se afecta esa derivación es el silogismo, por cuya razón la silogística llega a ser el centro de la lógica aristotélica.

[editar] Véase también

[editar] Enlaces externos

Introducción a la lógica proposicional

El contenido de esta página (o parte de ella) fue extraído de wikipedia y puede redistribuirse libremente bajo la licencia de documentación libre GNU

Esta página

Publicidad

Colabora

Teorema gráfico del día

Imágen espacio diaria