Lógica Matematica

Competencia específica a desarrollar: Analizar y resolver problemas computacionales utilizando las técnicas básicas de lógica e inducción matemática

3.1 Lógica proposicional.

Lo más importante en matemáticas y computación es conocer la veracidad de una aseveración.

La palabra lógica viene del griego y significa, razón, tratado o ciencia. Y en computación es la ciencia que estudia la forma de razonar correctamente, la que nos indica la forma correcta de obtener conclusiones y los métodos conocidos para lograrlo.

La lógica como cualquier ciencia y como la filosofía busca la verdad y es la que establece las reglas para hacer un razonamiento correcto. Aquí debemos distinguir entre pensamiento correcto y verdadero, la lógica proporciona una herramienta para saber si un desarrollo es correcto, pero la veracidad del mismo dependerá de las premisas o sea las condiciones de las que se parte.

Por ejemplo, si el maestro dice que todos los alumnos que traigan la tarea tendrán un punto extra en el examen. Si Juan me dice que llevó la tarea se puede concluir correctamente que obtuvo un punto más. Este es un razonamiento correcto, sin embargo la veracidad de la conclusión depende de la veracidad de las dos premisas. Si por ejemplo Juan me dijo mentiras y no entregó la tarea, ya no podemos estar seguros de que la conclusión es verdad. Lo mismo sucede si el maestro no cumple su promesa y cambia de opinión acerca de subir un punto, o si el maestro no ha estudiado lógica.

Resumiendo: Si las condiciones dadas (premisas) son verdaderas, la lógica nos enseña métodos de razonamiento o inferencia correctos para saber en qué casos la conclusión es también verdadera.

La Lógica es importante para los estudiantes de computación primeramente porque proporciona una forma de saber si un desarrollo es correcto, tanto en matemáticas como en otras materias de ciencias; pero también es importante porque nos presenta el lenguaje de expresiones booleanas que utilizamos en los diferentes lenguajes de Programación, en Bases de Datos, y cualquier otra materia de computación que utilice conceptos lógicos.

3.1.1 Concepto de proposición

En computación frecuentemente se usan estructuras que dependen solamente de dos valores, así por ejemplo tenemos el sistema numérico binario que se utiliza para representar los números utilizando solamente 0 y 1.

El trabajar con sólo 2 opciones facilita la implementación de los conceptos y simplifica su manejo. Así una teoría resulta mucho más fácil de establecer y de justificar si tiene sólo dos valores asociados, que otra por ejemplo una estructura de álgebra de números que tiene una cantidad infinita.

Otro tipo de entes que se utilizan en computación que también está asociado a “dos” opciones, es lo que se conoce como expresiones booleanas. Estas expresiones, que deben su nombre a George Boole, se pueden ver caracterizadas como verdaderas ó falsas y de acuerdo a esta condición se desarrolla el estudio sobre dichos conceptos. Este tema se conoce como cálculo de proposiciones.

Los argumentos son una de las formas más comunes en matemáticas, en lógica y en computación de establecer razonamientos para llegar a la verdad. Si tenemos un conectivo lógico OR de dos valores de entrada y después un inversor, cuál es la salida. O si en un programa con una instrucción tipo if se tiene la condición X > 3 and X < 10 cómo se sabe si se ejecutó el comando.

Podemos tener también situaciones como:

Todos los hombres son mortales. Sócrates es hombre.

Por lo tanto: Sócrates es mortal.

Si lo comparamos con:

Todos lo árboles son verdes.

Todos lo pericos son verdes.

Por lo tanto: Todos los árboles son pericos.

Una pregunta importante es, ¿cómo saber si un razonamiento es válido? En general, la lógica proporciona los métodos para saber si un argumento es correcto y poder obtener conclusiones.

Un argumento es un conjunto de premisas, condiciones dadas, junto con una conclusión. Y decimos que un argumento es válido si la conclusión es verdadera siempre que las premisas lo son.

Uno de los principales propósitos de la lógica es por lo tanto encontrar la forma de poder saber si un argumento es válido o no. A esto le llamamos inferencia y está en la sección de Reglas de Inferencia.

Antes de poder decidir un argumento es válido o no, debemos de empezar por estudiar sus componentes, los elementos más simples que componen un argumento se llaman elementos atómicos.

Empezaremos por decir que en lógica proposicional utilizaremos dos valores asociados llamados valores de verdad, que son verdadero (V) y falso (F), y en computación a las expresiones que se les asocia uno de estos dos valores se les llama expresiones booleanas.

Los enunciados o expresiones del lenguaje se pueden clasificar en: Proposiciones lógicas, Proposiciones abiertas y Frases o expresiones indeterminadas.

Proposición lógica. Expresiones que pueden ser verdaderas o falsas pero no ambas.

Proposición abierta. Una expresión que contiene una o más variables y al sustituir las variables por valores específicos se obtiene una proposición lógica.

Frases. Todas las expresiones que no cumplen alguna de las dos definiciones anteriores.

Expresiones Booleanas. Proposiciones lógicas y proposiciones abiertas.

Ejemplos

i) México está en América Proposición Lógica

ii) 1 < 2 Proposición Lógica

iii) Hoy es lunes Proposición Abierta

iv) x + 3 = 5 Proposición Abierta

v) Ecosistemas Frase

vi) Buenos días Frase

vii) El 3 de abril de 1970 fue domingo Proposición Lógica

viii) Los cocodrilos pueden volar Proposición Lógica

ix) Las matemáticas son agradables Proposición Abierta

x) Esta expresión es falsa Frase

Combinando dos o más proposiciones se pueden formar expresiones compuestas con los operadores, estos operadores también se llaman conectivos lógicos y se presentan en la siguiente sección.

3.1.2 Proposiciones compuestas (Disyunción, Conjunción, Negación, Condicional, Bicondicional)

Como se mencionó en el tema de argumentos para formar expresiones compuestas necesitamos conectivos lógicos, empezaremos por un conectivo unitario; esto es, se aplica a una proposición sola.

La Negación

La operación unitaria de negación, no es cierto que se representa por “¬” y tiene la siguiente tabla de verdad de verdad

p ¬ p

V F

F V

Ejemplo. Encuentre la negación de las expresiones siguientes:

i) Júpiter es un planeta ii) El pizarrón es verde iii) El número real x es negativo iv) Algún elefante es de color rosa

v) Ningún pez respira fuera del agua

vi) Todos los leones son feroces Solución:

i) Júpiter no es un planeta ii) El pizarrón no es verde iii) El número real x no es negativo o también El número real x es positivo ó cero iv) Ningún elefante es de color rosa v) Algún pez respira fuera del agua vi) Algún león no es feroz

En la siguiente sección veremos operadores binarios, con esto será suficiente para construir cualquier fórmula válida en lógica de proposiciones. La jerarquía que utilizaremos es que la negación se efectúa primero que los demás operadores, aparte de esta no imponemos ninguna otra, esto con el fin de que se acostumbren a la utilización de paréntesis. Posteriormente es posible adoptar cualquiera de las jerarquías usuales, una vez que ya se entendió y practicó suficiente con las fórmulas lógicas establecidas de esta manera.

Conjunción

La conjunción de las proposiciones p, q es la operación binaria que tiene por resultado p y q, se representa por p ^ q, y su tabla de verdad es:

p Q p ^ q

V V V

V F F

F V F

F F F

La conjunción nos sirve para indicar que se cumplen dos condiciones simultáneamente, así por ejemplo si tenemos:

La función es creciente y está definida para los números positivos, utilizamos p ^ q, donde p: la función es creciente

q: la función está definida para los números positivos

Así también: p ^ q, donde p: el número es divisible por 3 q: el número está representado en base 2 se lee: El número es divisible entre 3 y está representado en base 2.

Nota: Observamos que para la conjunción p ^ q será verdadera si las dos expresiones que intervienen deben ser verdaderas y sólo en ese caso como se indica por su tabla de verdad.

Disyunción

La disyunción de dos proposiciones p, q es la operación binaria que da por resultado p ó q, notación p v q, y tiene la siguiente tabla:

p Q p v q

V V V

V F V

F V V

F F F

Con la disyunción a diferencia de la conjunción, representamos dos expresiones y que afirman que una de las dos es verdadera, por lo que basta con que una de ellas sea verdadera para que la expresión p v q sea verdadera.

Así por ejemplo la expresión: el libro se le entregará a Juan o el libro se le entregará a Luis significa que si va uno de los dos, el libro se le entrega, si van los dos también se entrega y solamente en caso de que no vaya ninguno de los dos no se debe entregar.

Aquí debemos tener cuidado, porque en el idioma español muchas veces utilizamos la disyunción para representar otros operadores que aparentemente son lo mismo, pero que tienen diferente significado.

En español tenemos tres casos de disyunción:

La llamada y/o bancaria, lógica o matemática, que es la misma y se utiliza en computación como el operador OR, este operador corresponde al mencionado anteriormente p v q y ya se mostró su tabla de verdad.

La o excluyente, que algunos también le llaman o exclusiva, y que indica que una de las dos proposiciones se cumple, pero no las dos. Este caso corresponde por ejemplo a: Hoy compraré un libro o iré al cine; se sobrentiende que una de las dos debe ser verdadera, pero no la dos. Se representa por p XOR q y su tabla de verdad es:

p Q p XOR q

V V F

V F V

F V V

F F F

Por último, también es muy común utilizar una disyunción como la siguiente: El menú incluye café o té. En este caso se está dando una disyuntiva diferente pues no se pueden las dos simultáneamente como en el caso anterior, pero aquí si es válido el caso donde las dos son falsas. Es el caso “no ambas”, se puede representar por p § q y su tablas es

p Q p § q

V V F

V F V

F V V

F F V

Nota: El último símbolo no es estándar y puede haber varias formas de representarlo.

Un buen ejercicio consiste en enunciar varias expresiones del español que utilizando los conectivos y o para analizar cuál de los operadores es.

Hay que tener mucho cuidado cuando se traduce del lenguaje usual por las costumbres, muchas veces depende del contexto o de la situación específica en la que se usan los conectivos, por ejemplo si decimos: Se pueden estacionar alumnos y maestros, en realidad se está queriendo decir un operador disyuntivo, en este caso la o matemática, o sea el primer operador que corresponde a la primera tabla de esta sección.

Condicional

La condicional de dos proposiciones p, q da lugar a la proposición; si p entonces q, se representa por p → q, y su tabla de verdad está dada por:

P Q p → q

V V V

V F F

F V V

F F V

Con respecto a este operador binario, lo primero que hay que destacar es que no es conmutativo, a diferencia de los dos anteriores la conjunción y la disyunción. El único caso que resulta falso es cuando el primero es verdadero y el segundo falso.

Por ejemplo, si p es llueve y q es hay nubes entonces: p → q es, si llueve entonces hay nubes.

También cabe señalar que este viene a ser el operador más importante en el proceso deductivo y que la mayoría de las leyes de inferencia y las propiedades en matemáticas se pueden enunciar utilizando este operador.

Bicondicional

La bicondicional de dos proposiciones p, q da lugar a la proposición; p si y sólo si q, se representa por p ↔ q su tabla de verdad está dada por:

p q p ↔ q

V V V

V F F

F V F

F F V

Jerarquía de Operadores.

Combinando los operadores anteriores podemos formar nuevas expresiones.

En términos formales la negación de p, deberá ser ( ¬ p), así como la conjunción de p y q sería (p ^ q). Con el uso de paréntesis evitamos la ambigüedad, por ejemplo ¬ p ^ q podría significar dos cosas distintas

Por un lado podría significar: (( ¬ p) ^ q) O también: ( ¬ (p ^ q)).

En la práctica para no usar tantos paréntesis se considera que el operador ¬ tiene jerarquía sobre ^, v, →, ↔. Así ¬ p ^ q significa (( ¬ p)^ q).

En algunos casos se considera ^, v tienen mayor jerarquía que ↔ por lo que p ↔ q v r sería (p ↔ (q v r)) y también que ^ tiene prioridad sobre v, por lo que p ^ q v r sería (p ^ q) v r.

Así por ejemplo, en electrónica, para representar circuitos lógicos se utiliza + en lugar de v y • en lugar de ^.

Por lo que p • q + r es ((p ^ q) v r).

En estos apuntes no se considerará jerarquía en ninguno de los operadores binarios ^, v,

→, ↔ por lo que utilizaremos paréntesis. Sólo ¬ tiene prioridad sobre los demás operadores. Esto nos ahorra algunos paréntesis, por ejemplo: ((( ¬ p) ^ q) v r) se representa por ( ¬ p ^ q) v r.

3.1.3 Tablas de verdad

Como ya sabemos la sintaxis en lógica es la forma correcta de escribir una fórmula y la semántica es lo que significa. Como en lógica solamente tenemos dos valores una fórmula solamente puede ser verdadera o falsa. Para determinar su valor seguimos las reglas simples que dimos en las definiciones básicas de acuerdo a su tabla de verdad. Esto lo hacemos mediante interpretaciones. Una interpretación de una fórmula es un conjunto de valores que se les asignan a sus proposiciones atómicas.

Al interpretar una fórmula lo que finalmente vamos a obtener es un valor de verdad, bien sea verdadero o falso. Pero para poder encontrarlo muchas veces el proceso es laborioso porque puede estar formada por varias proposiciones atómicas. Primeramente se le asignan valores de verdad a los átomos y se puede encontrar el valor de la expresión.

Si deseamos hacerlo en general, debemos analizar todas las posibilidades, esto se puede hacer construyendo una tabla de verdad. Para fines prácticos cuando se tienen varios átomos las tablas de verdad no resultan prácticas por lo que analizaremos solamente expresiones con tres átomos como máximo.

Por supuesto que se puede construir una tabla para un número mayor de átomos, pero notemos que por cada átomo que se aumente el número de renglones se duplica. Esto es, para un átomos son dos renglones, para dos átomos son cuatro, para tres átomos son ocho, para cuatro dieciséis, etc.

Algoritmo para construir una tabla de verdad de una fórmula en lógica de proposiciones.

1. Escribir la fórmula con un número arriba de cada operador que indique su jerarquía. Se escriben los enteros positivos en orden, donde el número 1 corresponde al operador de mayor jerarquía. Cuando dos operadores tengan la misma jerarquía, se le asigna el número menor al de la izquierda.

2. Construir el árbol sintáctico empezando con la fórmula en la raíz y utilizando en cada caso el operador de menor jerarquía. O sea, del número mayor al menor.

3. Numerar las ramas del árbol en forma secuencial empezando por las hojas hacia la raíz, con la única condición de que una rama se puede numerar hasta que estén numerados los hijos. Para empezar con la numeración de las hojas es buena idea hacerlo en orden alfabético, así todos obtienen los renglones de la tabla en el mismo orden para poder comparar resultados.

4. Escribir los encabezados de la tabla con las fórmulas siguiendo la numeración que se le dio a las ramas en el árbol sintáctico.

5. Asignarle a los átomos, las hojas del árbol, todos los posibles valores de verdad de acuerdo al orden establecido. Por supuesto que el orden es arbitrario, pero como el número de permutaciones es n!, conviene establecer un orden para poder comparar resultados fácilmente.

6. Asignar valor de verdad a cada una de las columnas restantes de acuerdo al operador indicado en el árbol sintáctico utilizando la tabla de verdad correspondiente del Tema de Conexiones Lógicas y Jerarquías. Conviene aprenderse de memoria las tablas de los operadores, al principio pueden tener un resumen con todas las tablas mientras se memorizan.

7. La última columna, correspondiente a la fórmula original, es la que indica los valores de verdad posibles de la fórmula para cada caso.

Ejemplo. Construya la tabla de verdad de las siguientes expresiones lógicas: i) (p → ¬ q) v (¬ p v r) ii) p → (q ^ r) iii) (p → ¬ r) ↔ (q v p) iv) ¬ (p ¬ q) → ¬ r

v) (¬ p ^ q) → ¬ (q v ¬ r)

Solución:

i) Seguimos los pasos del algoritmo con la fórmula (p → ¬ q) v (¬ p v r)

1. Vemos que los operadores de los paréntesis tienen mayor jerarquía, empezamos por el paréntesis izquierdo por lo que la fórmula con jerarquías marcadas sería:

2. Construir el árbol Sintáctico empezando a descomponer por el operador con el número mayor, seguir en orden descendiente hasta el último que es el que tiene el número 1.

3. Numerar las ramas del árbol

4. Escribir los encabezados de la tabla utilizando las fórmulas en el árbol siguiendo la numeración del paso 3.

5. Asignar valores de verdad a los átomos, en este caso, las tres primeras columnas.

6. Completar el resto de las columnas utilizando las definiciones de los operadores.

...