Lógica

  La lógica proposicional es la más antigua y simple de las formas de lógica. Utilizando una representación primitiva del lenguaje, permite representar y manipular aserciones sobre el mundo que nos rodea. La lógica proposicional permite el razonamiento, a través de un mecanismo que primero evalúa sentencias simples y luego sentencias complejas, formadas mediante el uso de conectivos proposicionales, por ejemplo Y (AND), O (OR). Este mecanismo determina la veracidad de una sentencia compleja, analizando los valores de veracidad asignados a las sentencias simples que la conforman.

Una proposición es una sentencia simple que tiene un valor asociado ya sea de verdadero (V), o falso (F). Por ejemplo:

Hoy es Viernes

Ayer llovió

Hace frío

La lógica proposicional, permite la asignación de un valor verdadero o falso para la sentencia completa, no tiene facilidad par analizar las palabras individuales que componen la sentencia. Por este motivo, la representación de las sentencias del ejemplo, como proposiciones, sería:

hoy_es_Viernes

ayer_llovió

hace_frío

La proposiciones pueden combinarse para expresar conceptos más complejos. Por ejemplo:

hoy_es_Viernes y hace_frío.

En la lógica proposicional, las conectivas lógicas se tratan como funciones de verdad. Es decir, como funciones que toman conjuntos de valores de verdad y devuelven valores de verdad. Por ejemplo, la conectiva lógica «no» es una función que si toma el valor de verdad V, devuelve F, y si toma el valor de verdad F, devuelve V. Por lo tanto, si se aplica la función «no» a una letra que represente una proposición falsa, el resultado será algo verdadero. Si es falso que «está lloviendo», entonces será verdadero que «no está lloviendo».

   A la proposición anterior dada como ejemplo, se la denomina fórmula bien formada (well-formed formula, wff). Una fórmula bien formada puede ser una proposición simple o compuesta que tiene sentido completo y cuyo valor de veracidad, puede ser determinado. La lógica proposicional proporciona un mecanismo para asignar valores de veracidad a la proposición compuesta, basado en los valores de veracidad de las proposiciones simples y en la naturaleza de los conectores lógicos involucrados.

   El significado de las conectivas lógicas no es nada más que su comportamiento como funciones de verdad. Cada conectiva lógica se distingue de las otras por los valores de verdad que devuelve frente a las distintas combinaciones de valores de verdad que puede recibir. Esto quiere decir que el significado de cada conectiva lógica puede ilustrarse mediante una tabla que despliegue los valores de verdad que la función devuelve frente a todas las combinaciones posibles de valores de verdad que puede recibir.

Los conecta dores básicos de la lógica proposicional, se dan en la Tabla 4.1. Las tablas de verdad para las operaciones básicas, se muestran en la Tabla 4.2.

NOMBRE	CONECTOR	SÍMBOLO
Conjunción Disyunción Negación Implicación Equivalencia	AND OR NOT If-Then Igual	^ v ~ => =

Tabla 4.1 Conectores básicos de la lógica proposicional

p	q	Disyunción p v q	Conjunción p ^ q	Negación ~p	Implicación p => q	Equivalencia p = q
V	V	V	V	F	V	V
V	F	V	F	F	F	F
F	V	V	F	V	V	F
F	F	F	F	V	V	V

Tabla 4.2 Tablas de verdad para operadores lógicos

El conectador de implicación, puede ser considerado como un condicional expresado de la siguiente forma:

Si A => B va a ser verdadero,

entonces toda vez que A sea verdadero, B debe ser siempre verdadero. 

Para los casos en los cuales A es falso, la expresión A => B, es siempre verdadera, independientemente de los valores lógicos que tome B, ya que el operador de implicación no puede hacer inferencias acerca de los valores de B. Existen varias equivalencias en lógica proposicional, similares a las del álgebra Booleana.  Estas se dan en la Tabla 4.3.

DENOMINACIÓN	REPRESENTACIÓN LÓGICA
Leyes Equipotenciales	A => B = ~A v B A ^ ~A = F A v ~A = V
Leyes Conmutativas	A ^ B = B ^ A A v B = B v A
Leyes Distributivas	A ^ (B v C) = (A ^ B) v (A ^ C) A v (B ^ C) = (A v B) ^ (A v C)
Leyes Asociativas	A ^ (B ^ C) = (A ^ B) ^ C A v (B v C) = (A v B) v C
Leyes Absortivas	A ^ (A v B) = A A v (A ^ B) = A
Leyes de De Morgan	~(A ^ B) = ~A v ~B ~(A v B) = ~A ^ ~B

Tabla 4.3 Equivalencias en lógica proposicional

Ejercicios

1. Analizar las siguientes expresiones

a) 7 + 5 = 20

b) ¿Eres un estudiante de matemática?

c) X + 5 = 8

d) El día esta frío.

e) ¡cierra la puerta!

Solución

a) 7 + 5 = 20, es una expresión cuyo valor de verdad es falsa. Luego es una proposición.

b) ¿Eres un estudiante de matemática?, es una pregunta que se hace, carece de valor de verdad, es decir, no se puede afirmar si es verdadero o falso, luego no es una proposición.

c) X + 5 = 8, es un enunciado abierto o función proposicional por que tiene variable

d) El día esta frío, es una proposición que puede ser verdadera o falsa

e) ¡cierra la puerta!, es una orden. Luego no es una proposición.

2. Sean las proposiciones p, q, r, cuyos valores de verdad es V, F y F. hallar el valor de verdad de las siguiente proposiciones compuestas:

Lenguaje Formal de la Lógica de Predicados

El lenguaje es el instrumento que se usa para la comunicación entre humanos. El lenguaje está formado por frases, entre ellas podemos distinguir: frases imperativas, frases interrogativas y frases declarativas.

La definición de lógica, disciplina que estudia métodos de formalización del conocimiento humano "de los métodos de formalización de frases declarativas".(Jose Emilio Labra Gayo, Daniel Fernández Lanvin, E.U.I.T.I.O.)

La lógica se clasifica:

•Lógica proposicional o lógica de enunciados:

Se parte de un elemento simple, las frases declarativas simples, las cuales tienen significado ellas mismas o la unión entre ellas,forman una frase. Esto inicia una unidad de comunicación de conocimientos, las cuales se les denomina proposiciones, y toman el valor verdadero o falso.

•Lógica de predicados: Estudia las frases declarativas,teniendo en cuenta la estructura interna de las proposiciones. Los objetos y las relaciones entre los objetos serán los elementos básicos. Podemos distinguir:

- "Qué se afirma: relación

- De quién se afirma: objeto" (Jose Emilio Labra Gayo, Daniel Fernández Lanvin, E.U.I.T.I.O.)

Lógica de Predicados (LP de Orden Cero).

Con la lógica de predicados intentamos conseguir sistemas de demostración automática de teoremas. Partimos de elementos básicos como las frases declarativas simples o proposiciones que son aquellos elementos de una frase que constituyen por sí solos una unidad de comunicación de conocimientos y pueden ser considerados Verdaderos y Falsos. La lógica de predicados estudia las frases declarativas con mayor grado de detalle, considerando la estructura interna de las proposiciones. Se tomarán como elemento básico los objetos y las relaciones entre dichos objetos. Se distingue:

• "Qué se afirma (predicado o relación)

• De quién se afirma (objeto)" (Jose Emilio Labra Gayo, Daniel Fernández Lanvin, E.U.I.T.I.O.)

Definimos a continuación las reglas sintácticas para construir fórmulas:

Definición 1:El alfabeto de la lógica de predicados estará formado por los siguientes conjuntos simbólicos:

•Conjunto de Símbolos de Variables(VAR): Es un conjunto de las últimas letras del alfabeto en minúsculas. Se utilizan subíndices, por ejemplo:


•Conjunto de símbolos de Constantes (CONS): Este conjunto lo forman las primeras letras del alfabeto en minúsculas,también utilizaremos subíndices:

•Conjunto de letras de función(FUNC): Representaremos a este conjunto por las letras f,g,h,L. Incluimos subíndices para poder diferenciar las funciones:

•Conjunto de letras de Predicado (PRED): Se representan mediante letras mayúsculas,

Símbolos de conectivas: ¬ = Negación
∨= Conectiva "o"
∧ = Conectiva "y"
→ = implicación
↔ = Doble implicación o equivalencia

Cuantificadores:

∃=existencial

∀=Universal

Signos de puntuación: Paréntesis ( ) y coma.

Definición 2: Término es una cadena de símbolos que representan a objetos y dependen de las siguientes reglas:

•"Toda variable o constante individual es un término." (Jose Emilio Labra Gayo, Daniel Fernández Lanvin, E.U.I.T.I.O.)

•"Si t1,t2,L,tn son términos y fn es una función de aridad n entonces fn(t1,t2,L,tn) es un término" (Jose Emilio Labra Gayo, Daniel Fernández Lanvin, E.U.I.T.I.O.)

•Todos los términos posibles se generan aplicando únicamente las dos reglas anteriores Cualquier término lo generamos a partir de las dos reglas dichas anteriormente.

Definición 3: Un átomo es una cadena de símbolos de la forma: donde Pn es un predicado de aridad n y sin términos

Definición 4: Definimos el conjunto de fórmulas bien formadas (fbf):

1. "Todo átomo (P,Q,R,S,...) es una fórmula bien formada. (Se denominará fórmula atómica)."

2. "Si es una fórmula bien formada, ¬ A también lo es.

3. Si y son fórmulas bien formadas, también lo son (A ∧ B), (A ∨ B) y (A ⇒ B).

4. No hay más fórmulas." (Jose Emilio Labra Gayo, Daniel Fernández Lanvin, E.U.I.T.I.O.)

Podemos hacer razonamientos con la deducción natural.

Ejemplo: Tenemos la frase “Todos los estudiantes de informática son listos” (Jose Emilio Labra Gayo, Daniel Fernández Lanvin, E.U.I.T.I.O.), lo podemos formalizar de la siguiente manera usando predicados:

I(x)=”x estudia informática” y L(x)=”x es listo” como:

"Existen estructuras deductivas que la lógica de proposiciones no puede formalizar de forma adecuada, por ejemplo, la deducción:

"Todos los informáticos son listos, Pedro es informático, luego Pedro es listo" (Jose Emilio Labra Gayo, Daniel Fernández Lanvin, E.U.I.T.I.O.)

En lógica de predicados de orden cero lo formalizamos con tres proposiciones p,q y r independientes y la fórmula resultante “p∧q→r” no sería válida.
Lógica de primer orden


En lógica de predicados de primer orden "se permite la cuantificación de variables" (Jose Emilio Labra Gayo, Daniel Fernández Lanvin, E.U.I.T.I.O.). Así de esta manera, se formaliza el razonamiento:

En la lógica de predicados de primer orden

(∀x (Informático(x)→Listo(x))∧ Informático (Pedro))→ Listo (Pedro)

La lógica de predicados de primer orden es la más básica, es una extensión de lógica de predicados de orden cero, sólo que admite los cuantificadores ( ∀ y ∃ ), y reglas de deducción natural.

Las variables en lógica de primer orden pertenecen a un dominio, tienen una asignación. Pueden existir constantes y las fórmulas en esta lógica se pueden unificar de formas nuevas que antes no teníamos o podíamos.

La LP1 es suficiente para formalizar la teoría de conjuntos, el problema es que, a diferencia de LP0, la lógica de primer orden no es predecible. No existe un procedimiento de decisión que nos permita decidir si para una fórmula,esta es válida o no. Church y Turing lo demostrando de forma independiente.
Ejemplo sobre lógica de predicados

Dada la siguiente expresión

-La variable x está ligada ya que aparece en el ámbito del cuantificador universal y además la tiene como variable de cuantificación.

-Se dice que la variable y es una variable libre ya que aunque está en el ámbito del cuantificador universal,esta no la tiene como variable de cuantificación.
Sistema deductivo para lógica de primer orden

En lógica de predicados de orden cero,existen una series de expresiones que son siempre verdaderas. A partir de estas expresiones podremos llegar a construir un sistema deductivo con el que podremos llegar a expresiones correctas. Ejemplo:La siguiente expresión es válida: 

|=p(X)->(Q(X)->P(x))

Esta expresión es una instancia de una tautología de lógica de predicados.En general,con cualquier instancia de tautología podremos obtener una fórmula de universalmente. A partir del esquema de axiomas de GILBERT obtenemos:
(p(X)->(Q(Y)->R(z)))->(P(x)->Q(y))->(P(X)->R(z)))