PDF de programación - Bloque I: Preliminares Tema 1: Introducción

BLOQUE I: PRELIMINARES

Tema 1: INTRODUCCIÓN

Lógica

Grado en Ingeniería Informática

Alessandra Gallinari

URJC

Contenido

Introducción

El lenguaje de la lógica

Lenguaje natural, lenguaje formal y metalenguaje
Estructura del lenguaje formal
Niveles de la lógica formal

Resumen de la historia de la lógica

Lógica y filosofía
Lógica y matemáticas
Lógica e informática

1

2

Introducción

El lenguaje natural

El contenido de este primer capítulo es una breve introducción a los
conceptos generales que se desarrollarán en esta publicación.

La lógica formal es la ciencia que estudia las leyes de inferencia en los
razonamientos.

FORMALIZACIÓN

LENGUAJE NATURAL −→ LENGUAJE FORMAL+
REGLAS DE LA LÓGICA

⇓

APLICACIONES

Álgebra, Cálculo, Matemática Discreta, Electrónica Digital, Teoría de
Autómatas y Lenguajes Formales, Programación, Bases de Datos, etc.

El lenguaje natural que utilizamos en la comunicación humana permite
un alto grado de flexibilidad.
Su gramática, permite determinar si una cierta frase (una combinación
de palabras) es válida:
“La mesa habla suavemente” es una frase válida.

La sintaxis de un lenguaje (las reglas de formación de frases correctas)
nos permite afirmar si una cierta combinación de palabras es válida. No
se ocupa del sentido de las frase, sólo determina su validez.
La semántica de un lenguaje trata el estudio de los sentidos de las frases
sintácticamente válidas.
Así, la frase “La mesa habla suavemente” es sintácticamente correcta,
pero falta de sentido semántico.

3

4

El lenguaje formal

El lenguaje formal

La flexibilidad de los lenguajes naturales se basa en la complejidad de sus
gramáticas. Es muy complicado, si no imposible, dar una representación
completa de las reglas sintácticas de los lenguajes hablados.
Si queremos poder formular sólo afirmaciones que se puedan definir
correctas (sintácticamente) o verdaderas (semánticamente) sin ningún
grado de ambigüedad, tendremos que definir un lenguaje más preciso, un
lenguaje formal.
Sin un lenguaje formal sería imposible estudiar las matemáticas,
programar un ordenador y, en general, desarrollar razonamientos
científicamente irrefutables.

El siguiente ejemplo ilustra como en el lenguaje natural, en este caso en
español, existen oraciones para las cuales ni siquiera tiene sentido
preguntarse si son verdaderas o falsas.
Ejemplo
Las frases “¿Cómo te llamas?” y “Por favor, dame tu libro” son dos
ejemplos de oraciones a las cuales no podemos asociar un valor de verdad
verdadero o falso.

5

6

El lenguaje formal

Proposiciones

El lenguaje formal de la lógica se construye a partir de unos
elementos básicos (atómicos) llamados
proposiciones: oraciones declarativas (apofánticas) simples, a
las cuales se pueden asociar valores de verdad sin ninguna
ambigüedad.
“¿Cómo te llamas?” y “Por favor, dame tu libro” no son
proposiciones, sin embargo las frases “Hoy llueve” o “Estudio
mucho” lo son.

Metalenguaje

Definimos metalenguaje al lenguaje, en nuestro caso el español, que
vamos a usar para definir un lenguaje formal.

Por ejemplo, en la frase “
√
cuadrado es igual a 2” se usa el metalenguaje español para definir el
símbolo matemático

2, que pertenece a un lenguaje formal.

√

2 es el número real positivo tal que su

7

8

Estructura del lenguaje formal

Estructura del lenguaje formal

En la lógica clásica las definiciones básicas de razonamiento y de validez
son las siguientes:
Razonamiento (deducción, inferencia, argumento): es la obtención
de un nuevo conocimiento (conclusión) a partir de una serie de
conocimientos (premisas).
Validez formal de un razonamiento: un razonamiento es formalmente
válido si la conclusión es necesariamente verdadera, siendo las premisas
verdaderas.

Ejemplo
Razonamiento válido:
Premisa 1: Si estudio todo el temario, entonces apruebo la asignatura.
Premisa 2: No he aprobado la asignatura.

Conclusión: No he estudiado todo el temario.

Razonamiento no válido:
Premisa 1: Si estudio todo el temario, entonces apruebo la asignatura.
Premisa 2: No he estudiado todo el temario.

Conclusión: No apruebo la asignatura.

9

10

Estructura del lenguaje formal

Estructura del lenguaje formal

En las matemáticas es necesario aprender a distinguir entre
razonamientos que son matemáticamente correctos (las demostraciones)
y razonamientos que no lo son. Además, para poder resolver problemas
concretos es necesario desarrollar la habilidad de construir razonamientos
matemáticos originales.
La lógica proporciona las herramientas necesarias para el razonamiento
matemático, pero también para muchas otras aplicaciones.
El diseño de circuitos de un ordenador y la verificación de la validez de un
programa son sólo dos ejemplos de estas aplicaciones en el contexto de la
informática.

Resumiendo, la estructura de todo lenguaje formal viene definida por su
sintaxis, semántica y sistemas de demostración:
Sintaxis (reglas de formación, gramática): es la definición axiomática de
los elementos básicos del lenguaje y de las reglas que permiten obtener
nuevas expresiones correctas a partir de aquellos. Las expresiones
admitidas por el lenguaje se denominan fórmulas.
Semántica (relación entre el lenguaje y su significado): es la definición
de un conjunto de significados (generalmente verdadero o falso) que se
puedan asociar a una fórmula. Permite definir la validez de una fórmula o
de un razonamiento.
Sistemas de demostración: son sistemas formales que permiten
averiguar cuándo una fórmula o un razonamiento son válidos. En el
contexto de la sintaxis se denominan teoría de la demostración. En el
caso de la semántica se denominan teoría interpretativa.

11

12

Niveles de la lógica formal

Niveles de la lógica formal

Lógica proposicional (lógica de proposiciones, LP): en la lógica
proposicional se estudian las fórmulas proposicionales construidas a partir
de fórmulas atómicas (proposiciones declarativas simples) y conectivos
lógicos (y, o, implica, etc.).
Ejemplo
1) Formalización de frases:
Estudio todo el temario (e);
No estudio todo el temario(¬(e));
Apruebo la asignatura (a);
Estudio todo el temario y apruebo la asignatura (e ∧ a);
Si estudio todo el temario, entonces apruebo la asignatura (e −→ a).

Ejemplo
2) Formalización de razonamientos:

Razonamiento válido:
Premisa 1: Si estudio todo el temario, entonces apruebo la asignatura
(e −→ a).
Premisa 2: No he aprobado la asignatura (¬(a))
Conclusión: No he estudiado todo el temario (¬(e))

Razonamiento no válido:
Premisa 1: Si estudio todo el temario, entonces apruebo la asignatura
(e −→ a).
Premisa 2: No he estudiado todo el temario (¬(e))
Conclusión: No apruebo la asignatura (¬(a))

13

14

Niveles de la lógica formal

Niveles de la lógica formal

Lógica de predicados de primer orden, (LPO): la lógica de primer
orden es una generalización de la lógica de proposiciones.
Distingue entre los objetos del discursos y sus propiedades o posibles
relaciones entre ellos.
Además, introduciendo nuevos elementos como los cuantificadores
existenciales y universales (∃ : existe un, ∀ : para todo), permite
estudiar la estructura interna de los enunciados.

Ejemplo
1) Formalización de una frase:
“El cuadrado de todo número real es no negativo.”
Sean R el conjunto de los números reales y P(x) : x es un número no
negativo. La formalización de nuestra frase es:

(∀x(P(x 2)).

15

16

Niveles de la lógica formal

Niveles de la lógica formal

Ejemplo
2) Formalización de un razonamiento (válido):
Sean D el conjunto de los seres, P(x) : x es una persona, M(x) : x es
mortal y s el símbolo constante “Socrates.”
Entonces podemos formalizar el siguiente razonamiento:
Premisa 1: Todas las personas son mortales (∀x(P(x) −→ M(x)))
Premisa 2: Sócrates es una persona (P(s))
Conclusión: Sócrates es mortal (M(s))

Lógicas de orden superior: son extensiones de la lógica proposicional y
de predicados de primer orden que amplían el uso de los cuantificadores a
las propiedades y a las relaciones entre los objetos.
Notar que en la lógica de primer orden los cuantificadores se refieren sólo
a los objetos.

17

18

Resumen de la historia de la lógica

Lógica y filosofía

La definición de lógica como ciencia formal en la cultura occidental es el
resultado de un largo desarrollo histórico que empieza con las obras de
algunos filósofos griegos y llega hasta la actualidad.
Históricamente las áreas de aplicación más importantes de la lógica son
la filosofía, las matemáticas y la informática.
A continuación se presenta un resumen muy reducido de los principales
pasos que han llevado a la formulación de la lógica formal.

Siglo IV a.C.: En el siglo cuarto antes de nuestra era Aristóteles
fue el primero en tratar de formalizar el razonamiento humano para
poder discernir en la discusiones filosóficas. Aristóteles se puede
considerar el fundador de la denominada lógica clásica.

Edad Media: Durante la Edad Media el proceso de sistematización
de la lógica fue desarrollado por los filósofos árabes y los escolásticos.

Siglo XIII:En el siglo XIII Santo Tomás de Aquino empleó la

lógica en el contexto de las discusiones teológicas.

Siglo XVII: Fue Leibniz, en el siglo XVII, el primero a formular la
lógica como base del razonamiento matemático, pero sus estudios
fueron abandonados hasta el siglo XIX, cuando finalmente se fundóla
lógica matemática como ciencia.

19

20

Lógica y matemáticas

Lógica y matemáticas

1854: A mediados del siglo XIX, en el 1854, el inglés George Boole

publicó el libro The Laws of Thought (Las leyes del pensamiento).
Influenciado por las teorías de los matemáticos De Morgan y
Hamilton, Boole definióla lógica como sistema formal dirigido no
sólo al estudio del lenguaje natural. Su obra proporciona un modelo
algebraico de la lógica de proposiciones. El modelo matemático
conocido como álgebra de Boole es otro ejemplo muy importante en
informática usado para el diseño de circuitos lógicos y las búsquedas
booleanas en grandes colecciones de datos (indices de páginas Web,
datos genéticos, etc.).