Materia: #algoritmos_y_estructuras_de_datos

Tags:

Lógica

La lógica proposicional es un sistema de lógica basado en fórmulas estructuradas con ciertos simbolos, siguiendo una semantica y una sintactica clara, y que indica el valor de verdad de la misma. El objeto mas basico de la lógica proposicional es una fórmula atomica, que solemos notar con letras.

Por ejemplo, $p$ puede ser un predicado, y puede significar esta lloviendo. En particular, $p$ puede ser cierto o puede no serlo, propiedad que describimos como valor de verdad. Este valor de verdad puede ser o bien $True$ (verdadero, en inglés), o bien $False$ (falso, en inglés). Continuando con el ejemplo, si ahora mismo esta lloviendo, entonces $p$ es verdad, tiene un valor de verdad de $True$. Por otro lado, si no esta lloviendo cuando usted está leyendo esto, entonces $p$ sera falso, y tendria un valor de verdad de $False$.

Nosotros vamos a trabajar con una serie de simbolos que nos van a permitir unir fórmulas atomicas para armar estructuras mas complejas. Especificamente, veremos:

• o lógico (representado como $\vee$)

• y lógico (representado como $\wedge$)

• Negación lógica (representado como $\mathrm{\neg }$)

• Implicacion (representado como $⟹$)

• Doble implicacion (representado como $⟺$)

A su vez, estos operadores tienen una logica muy basica, basada en las tablas de verdad, que nos indican como funcionan y alteran los valores de verdad en cada caso. Las tablas son, dados $p$ y $q$ fórmulas cualesquiera:

Con estas simples reglas, podemos formar fórmulas como $(p\wedge q)⟹r$ (leasé: los valores de verdad de $p$ y $q$ en conjunto, implican la veracidad de $r$).

Nos interesan mucho, en particular, lo que son las equivalencias. En particular, ser capaces de determinar si dos o mas fórmulas son equivalentes entre si. Decimos que esto sucede, cuando tienen exactamente los mismos valores de verdad. La equivalencia se suele notar con la doble implicacion. De este modo, podemos decir cosas como:

• $(p\vee p)⟺p$

• $(p\wedge p)⟺p$

• $p\wedge (q\vee r)⟺(p\wedge q)\vee (p\wedge r)$

• $p\vee (q\wedge r)⟺(p\vee q)\wedge (p\vee r)$

• $(p\vee q)\vee r⟺p\vee (q\vee r)$

• $(p\wedge q)\wedge r⟺p\wedge (q\wedge r)$

• $\mathrm{\neg }(p\vee q)⟺\mathrm{\neg }p\vee \mathrm{\neg }q$

• $\mathrm{\neg }(p\wedge q)⟺\mathrm{\neg }p\wedge \mathrm{\neg }q$

• $(p\vee q)⟺(q\vee p)$

• $(p\wedge q)⟺(q\wedge p)$

• $(p⟹q)⟺(\mathrm{\neg }p\vee q)$

Todas estas son propiedades super utiles y practicas, asi que recomiendo tenerlas a mano.

Existe otra cuestion mas, que son las valuaciones. Una valuacion es una función $v:\nu \to \{T,F\}$, es decir, toma como entrada una fórmula, y devuelve su valor de verdad. Lo notamos $v\models p$, que se leeria como $v(p)=T$. En caso contrario, diriamos $v\cancel{\models }p$, que significa $v(p)=F$.

De aca, las reglas antes mencionadas son deducibles, pero aca estan explicadas para mas accesibilidad:

• $v\models \mathrm{\neg }p⟺v\cancel{\models }p$

• $v\models (p\vee q)⟺v\models p\vee v\models q$

• $v\models (p\wedge q)⟺v\models p\wedge v\models q$

• $v\models (p⟹q)⟺v\cancel{\models }p\vee v\models q$

• $v\models (p⟺q)⟺(v\models p⟺v\models q)$

Llamamos tautologías a aquellas fórmulas lógicas p que para toda valuacion $v$, se cumple $v\models p$. A su vez, existen las contradicciones, las cuales son todas las fórmulas lógicas p para las que todas las valuaciones $v$ se cumple que $v\cancel{\models }p$.

Analogamente, decimos que una fórmula lógica es satisfacible si existe por lo menos una valuacion $v$ tal que $v\models p$. Finalmente, decimos que una formula es insatisfacible, cuando no es satisfacible.

Lógica trivaluada secuencial

Existen ciertas cuestiones que no podemos representar en un modelo de verdadero y falso. Por ejemplo, si tenemos un predicado $P(n)$, que dice que dado un numero $n$, $p$ resulta cierta si y solo si $n=2$.

Existe un problema, y es que no siempre podemos caer en numeros que podamos comparar. Si nos ingresan numeros naturales, o incluso reales, o yendo al caso, hasta complejos, no tendremos ningun problema. También podrian ingresar fórmulas matematicas, y no deberia haber ningun contratiempo a primera vista, pero si que lo hay. Vean en la tabla lo que sucede en el ultimo caso: estamos dividiendo por 0, lo cual esta prohibido en las matematicas. O bueno, mas que prohibido, no definido, porque lleva a contradicciones.

Es para este tipo de casos que necesitamos ampliar nuestro sistema lógico. Evidentemente, no podemos abarcar todas las fórmulas simplemente con verdadero y f also, asi que se creo un sistema nuevo: la lógica trivaluada, que como dice su nombre, tiene tres valores de verdad. Ahora vamos a contar con verdadero y falso, como siempre, pero también con indefinido, notado a veces por el simbolo $\perp$.

Ahora, podemos definir la operacion de antes, resultando en que $P(1/0)$ es indefinido. A causa del nuevo valor, tenemos que actualizar las tablas de verdad, y revisitar las reglas de los simbolos para que todo tenga coherencia con lo antes dicho. Para esto mismo, vamos a introducir el concepto de lógica trivaluada secuencial.

La primera parte ya la conocemos, es la lógica trivaluada de la que venimos hablando. Pero la ultima parte, la de secuencial, es la que mas interesante vuelve todo esto. Ahora ya no evaluaremos las fórmulas de manera conmutativa, de ahora en adelante, el orden de las operaciones nos sera sumamente relevante. Vamos a tener nuevos simbolos que se tengan que leer estrictamente de izquierda a derecha, que notaremos con una $L$ pequeña junto a los simbolos clasicos, y llamaremos luego. Por ejemplo, al o lógico nuevo, lo llamaremos o luego, y lo notaremos ${\vee }_L$.

Las tablas revisitadas quedarian:

Sistema deductivo

Ahora bien, todo excelente con este sistema de lógica y demas, pero no nos sirve de nada si no podemos relacionar fórmulas diferentes. Es decir, si siempre hablamos de cosas independientes, no vamos a llegar muy lejos. Es por eso que existen los sistemas deductivos, en los que buscamos probar una fórmula en particular, a la que llamaremos conclusión, en base a unas otras, a las que llamaremos premisas.

Una forma de notar todo esto es la siguiente:

Donde el conjunto $p_1{p}_2\cdots p_n$ son las $n$ premisas, y $q$ es nuestra conclusión. A su vez, en lugar de regla deductiva, nosotros notariamos el nombre de la regla utilizada. Llamaremos prueba a una secuencia de reglas lógicas aplicadas sucesivamente para llegar a alguna conclusión. En base a esto, deducimos el secuente, que notamos:

Leasé el conjunto de premisas $\{p_1,p_2,\cdots ,p_n\}$ con el que podemos obtener una prueba de $q$. Consideramos valido al secuente si podemos construir de manera satisfactoria esa prueba.

Ahora que aclaramos todo esto, podemos pasar a lo pesado. Resulta que la elección de estas reglas lógicas es muy importante, ya que solo deberiamos ser capaces de construir pruebas validas. Es decir, no podemos permitirnos la posibilidad de satisfacer pruebas a conclusiones erroneas.

En particular, y de forma muy resumida, tenemos las siguientes reglas:

• $\frac{}{p}Hyp$

• $\frac{pq}{p\wedge q}\wedge i$

• $\frac{p\wedge q}{p}\wedge e$

• $\frac{p}{\mathrm{\neg }\mathrm{\neg }p}\mathrm{\neg }\mathrm{\neg }i$

• $\frac{\mathrm{\neg }\mathrm{\neg }p}{p}\mathrm{\neg }\mathrm{\neg }e$

• $\frac{p}{p\vee q}\vee i$

• $\frac{pp⟹q}{q}⟹e$

• $\frac{p_1⟹p_2⟹\cdots ⟹p_n⟹q}{p_1⟹q}⟹i,n$

Donde $i$ significa introduccion y $e$ eliminacion. Estos son solo algunas de las reglas que existen en casi cualquier sistema deductivo. Hay muchas mas que se pueden deducir de estas o incluso crear algunas mas especificas, como el Modus tollens.

Dandole un cierre a todo esto, vamos a definir unos terminos más. Llamaremos teorema a toda fórmula lógica $p$ tal que el secuente $p$ es válido.

Lógica de primer orden

Finalmente, llegamos a la parte final: la lógica de primer orden, o la lógica de predicados. Empecemos por un ejemplo, que va a ser mas fácil. Consideremos la frase:

Si siguieramos con la lógica proposicional seguro llamariamos a la frase $p$, o cualquier otra letra de preferencia, y le asignariamos algun valor de verdad. Pero quizas con eso perdemos informacion, podriamos armar expresiones mas pequeñas, que engloben un concepto muy especifico, y reconstruir la fórmula original mas compleja. Por mencionar una forma de hacerlo, ya que hay infinitas, aca mostramos:

Ser estudiante
Ser profesor
Ser más joven que

Podemos plantearlo como funciones. Vamos a llamar a nuestras variables individuos, es decir, entidades indivisibles y distintiva. En nuestro ejemplo, los individuos serian los estudiantes y los profesores, o las personas
yendo al caso.

A su vez, vamos a tener predicados, que son funciones que toman por entrada individuos, hacen alguna operacion y devuelven el estado de verdad de la operacion hecha. Continuando con la frase, podemos tener
un predicado que sea $E(x)$, que toma individuos $x$ y nos informa si ese individuo es un estudiante o no. Por otro lado, podemos tener un $P(x)$, que de manera semejante nos informa si el individuo $x$ es un profesor. También podemos tener predicados mas complejos, que tomen dos o mas entradas, por ejemplo podriamos definir $J(x,y)$, que dado un individuo $x$ y un individuo $y$, nos indica si $x$ es mas joven que $y$.

Por ultimo, vamos a introducir el concepto de los cuantificadores. Estos son simbolos que nos van a hacer mas facil la escritura de las fórmulas. En particular, tenemos dos: el para todo, que notamos $\mathrm{\forall }$; y el existe
(también llamado para algún), y que notamos $\mathrm{\exists }$.

Con todo esto en la mesa, vamos a poder constuir estructuras complejas como la frase de antes, sin perder ninguna informacion primordial. Utilizando nuestros ejemplos de antes, una fórmula equivalente a la frase podria ser:

Esta no es la unica fórmula que se puede constuir y tener el mismo significado. Podriamos haber usado otros prodicados, o ordenarla de manera diferente, el punto es que ahora la frase es inequivoca y no hay informacion que se pueda perder, que es lo que mas nos interesa.

En general, a la hora de usar cuantificadores, vamos a escribirlos tipados. Esto quiere decir, que vamos a requerir que la variable sea de algun tipo especifico. Lo notamos:

Que se leerian como para todo $x$ del tipo $T$, y existe algún $x$ del tipo $T$, respectivamente. Si llamamos $H$ al tipo humano, la fórmula original podriamos corregirla:

Existen un par de reglas utiles a la hora de trabajar con los cuantificadores. Primero es lo que sucede al usar la negación en los mismos. Resulta que, si negamos un cuantificador universal, obtenemos un cuantificador existencial pero con el predicado negado, y viceversa. Todo esto quiere decir que:

Lo cual es una regla muy util y practica, pero no la unica. También hay formas de generalizar fórmulas: en particular, decimos que un cuantificador universal generaliza la conjunción, y un cuantificador existencial generaliza la disyunción. Es decir:

En el mundo de la lógica de primer orden, existen unas claras reglas sintacticas que todo LPO (lenguaje de primer orden) debe seguir. En particular, requiere:

• Un conjunto $F$ de símbolos de función cada uno con aridad (cantidad de argumentos) $n>0:f_1,f_2,f_3,\cdots ,f_n$

• Un conjunto numberable $C$ de constantes: $c_0,c_1,\cdots$.

• Un conjunto $P$ de símbolos de predicado cada uno con aridad $n\ge 0:p_1,p_2,p_3,\cdots ,p_m,\dot{=}$

El simbolo $\dot{=}$ denotará igualdad.

A su vez, llamamos terminos al conjunto de todas las constantes y variables dentro del LPO. Las fórmulas atomicas son todo símbolo de predicado con aridad 0. Finalmente, les decimos fórmulas a todas las fórmulas atomicas dentro del LPO, y todas las que puedas formar con las operaciones lógicas antes vistas.

Combinando esto con los cuantificadores, tenemos los conceptos de variable libre y variable ligada, que a primera vista no parecen ser de mucho interes pero resultan ser mas que utiles. En particular, llamamos variable ligada a una ocurrencia de $x$ si forma parte de una fórmula del tipo $\mathrm{\forall }x$ o $\mathrm{\exists }x$. Contrariamente, decimos que $x$ es una variable libre si no es ligada.

Existe una operacion mas que todavia no mencionamos: la sustitución. Dada una variable $x$, un término $t$, y una fórmula $p$, notamos $p\{t/x\}$ a la fórmula que se obtiene de reemplazar cada ocurrencia libre de $x$ en $p$ por $t$ (evitando capturas). Por ejemplo, algunas aplicaciones serian:

• $P(x,y)\{x/w\}=P(w,y)$

• $(\mathrm{\exists }z(P(x,y)))\{x/w\}=\mathrm{\exists }z(P(w,y)))$

• $(\mathrm{\exists }x(P(x,y)))\{x/w\}=\mathrm{\exists }x(P(x,y)))$

Ahora bien, dado cualquier lenguaje de primer orden $L$, su estructura, llamemosla $E$ es un par $E=(M,I)$, donde $M$ es un conjunto no vacío al que llamamos universo; e $I$ es la función de interpretación, que es la encargada de asignar funciones y predicados sobre $M$ a símbolos de $L$, siguiendo las siguientes reglas:

• Para toda constante $c$, se tiene que $I(c)\in M$

• Para toda $f$ de aridad $n>0$, se tiene que $I(f):M^n\to M$

• Para todo predicado $P$ de aridad $n\ge 0$, se tiene que $I(P)\subseteq M$

• $I(\dot{=})$ es la relación de identidad sobre $M$

Con esto de la estructura podemos terminar de definir conceptos importantes para mas adelante. En particular, dado un lenguaje $L$ y su estructura $E$, decimos que $s$ es una asignación si $s$ es una función $s:V\to M$. A su vez, notamos como $s\models Ep$ al hecho de que la asignación $s$ satisface la fórmula $p$ bajo la estructura $E$.

Notemos que $p$ podria ser cualquier predicado, es decir, que podemos cambiar en la fórmula anterior cualquier estructura lógica. Podriamos decir $s\models Ep\wedge q$, que significa $s$ satisface tanto $p$ como $q$, bajo la estructura de primer orden $E$.

Finalmente, decimos que una fórmula $p$ es válida o verdadera en $E$ si y solo si se verifica que $s\models E$ p para toda asignación $s$.

Para terminar, mostraremos unas reglas algo complejas pero muy utiles. Las reglas del sistema deductivo para los cuantificadores universales y existenciales. En particular son:

• $\frac{p(x)}{\mathrm{\forall }x(p(x))}\mathrm{\forall }i$

• $\frac{p(x)}{\mathrm{\exists }x(p(x))}\mathrm{\exists }i$

• $\frac{\mathrm{\exists }x(p(x)p_1⟹p_2⟹\cdots ⟹p_n⟹q)}{q}\mathrm{\exists }e$

Teniendo en cuenta que ni en $\mathrm{\forall }i$ ni en $\mathrm{\exists }e$ la variable $x$ debe ocurrir libre en ninguna hipótesis previa.