M1

MATEMÁTICAS 1. BLOQUE LÓGICA

LÓGICA

La Lógica se ha convertido en uno de los fundamentos matemáticos y en una base formal indispensable para todo informático. La formalización del
conocimiento y la automatización de las formas de razonamiento son primordiales en muchas áreas de la Informática. La importancia de la Lógica
en los currículos de Informática va tomando cuerpo propio debido a sus aplicaciones en contextos específicos tales como la Programación, la
Ingeniería del Software, el Diseño de Sistemas de Bases de Datos y la Inteligencia Artificial. En los últimos años han ido surgiendo libros de texto
de lógica escritos específicamente para estudiantes de Ingeniería Informática, que abordan la Lógica desde una perspectiva de aplicación a la
computación (ver los libros recomendados al final del documento).

Empleada como un lenguaje de programación, la lógica representa un formalismo de nivel superior que está más orientado a la persona que
otros lenguajes de programación clásicos, y por ello se ha convertido en el pilar del paradigma de la Programación Lógica cuyo representante,
Prolog (“PROgrammation en LOGique “), basado en la lógica de predicados de primer orden, es muy utilizado en investigaciones de Inteligencia
Artificial.

La idea central se resume en la ecuación de Kowalski algoritmo = lógica + control, de manera que el control, que es la estrategia para
encontrar la solución, lo dejamos en manos de la máquina y sólo nos preocupamos de la lógica de problema, es decir de la representación de la
información que aporte.

Nuestra presuposición de partida es que el lector, y todos, sabemos ya de antemano una

cantidad considerable de lógica. Si no fuera así, no podríamos siquiera hablar, menos aún
manejarnos por el mundo. Así que nuestro primer objetivo es hacer ese conocimiento suyo
explícito, sistemático y preciso.
Tom Tymoczko y Jim Henle,
Razón, dulce razón
GII- GI2A
2020-21 1
 M1
TEMAS DE LÓGICA
LÓGICA

T1: Razonar con Lógica de Primer Orden T3: Semántica lógica

- Concepto de razonamiento deductivo válido. - Interpretación de fórmulas lógicas.
- El Sistema de la Lógica de Primer Orden. - Tautologías.
- Esquema general de un razonamiento. - Tablas de verdad.
- Método del contraejemplo.
- Interpretación de estructuras lógicas.
T2: Formalización de razonamientos usando el lenguaje lógico
- Lenguaje proposicional y predicativo.
T4: Deducción Natural
- Obtención de fórmulas y estructuras lógicas.
- Reglas de inferencia.
- Estrategias para hacer deducciones.
- Subdeducciones.

Propósito : Desarrollar destrezas de razonamiento a través del aprendizaje sistemático de procesos deductivos del sistema formal de la
Lógica de Primer Orden. Será necesario:
- Determinar qué problemas requieren de razonamiento.
- Obtener la estructura de los razonamientos deductivos (diremos sólo razonamiento).
- Utilizar el sistema formal de la Lógica de Primer Orden para demostrar la validez de los razonamientos.

GII- GI2A
2020-21
 M1
T1: Razonar con Lógica de Primer Orden
LÓGICA

Razonamiento: Proceso que permite obtener, en sucesivos pasos y por aplicación de reglas, proposiciones llamadas conclusiones a partir de un
conjunto de proposiciones, llamadas premisas. Si el proceso es deductivo se dice que el razonamiento es válido si de la verdad de las premisas se
sigue la verdad de la conclusión. En informática es fundamental en la resolución de problemas de computación, en el desarrollo de sistemas
inteligentes y para verificación de programas.

Lógica de Primer Orden (lpo): Ciencia que estudia las reglas que permiten demostrar la validez de los razonamientos. Le concierne el análisis y
la codificación del razonamiento ya que se interesa por la estructura y la transformación de los enunciados que lo definen. Cuenta con un lenguaje
artificial, con modelos matemáticos para dar significado a los enunciados y con un cálculo basado en reglas de inferencia que permiten demostrar
mecánicamente la validez de los razonamientos.

ESQUEMA GENERAL DE UN PROBLEMA DE RAZONAMIENTO

Si es cierto P entonces es cierto Q.
Si P = { P1, P2,…Pn }
Es cierto P, por lo tanto, es cierto Q
PQ Esquema: P1, P2,… Pn  Q

P: conjunto de proposiciones premisas

El símbolo  se llama deductor
Q: proposición objetivo o conclusión

Proposición (en lpo): enunciado que puede ser verdadero o falso. Según su complejidad puede ser:
Atómica: enunciado simple. Ej. Ana estudia lógica.
Molecular: enunciado formado por la conexión de varias proposiciones atómicas. Ej. Ana estudia lógica y física.
“Ana estudia lógica” se conecta con “Ana estudia física” mediante la conectiva “y”.

GII- GI2A
2020-21 3
 M1
T1: Razonar con Lógica de Primer Orden
LÓGICA

Razonamiento válido Razonamiento no válido

P1, P2,· · · Pn  Q

Si todas las Pi son verdaderas y Q es verdadera

Si todas las Pi son verdaderas y Q es falsa

Si al menos una Pi es falsa y Q verdadera

Si al menos una Pi es falsa y Q es falsa

- En lpo sólo interesa la estructura lógica del razonamiento cuya validez se debe demostrar no la información que aporte el problema.

- En todo razonamiento válido la verdad de la conclusión se deduce de la verdad de las premisas.

- Se averigua si siempre que las premisas son ciertas la conclusión también lo es.

- Si se demuestra que siendo las premisas ciertas la conclusión es falsa, entonces el razonamiento no es correcto.

- La demostración tendrá éxito dependiendo de la habilidad que el usuario tenga en la aplicación de las reglas.

- Una conclusión no se ve modificada por aportación de nuevas premisas al problema (monotonía en lpo).

GII- GI2A
2020-21 3
 M1
T1: Razonar con Lógica de Primer Orden
LÓGICA

Niveles de abstracción en lpo para demostrar la validez de los razonamientos:

Lógica Proposicional y Lógica de Predicados de Primer Orden.

Cada nivel cuenta con los siguientes elementos:

Lenguaje : alfabeto y reglas sintácticas para la formalización de razonamientos y obtención de su estructura lógica.

Semántica: métodos semánticos para estudiar la verdad de la estructura.

Proceso deductivo: conjunto de reglas de inferencia para la obtención de conclusiones.

SE GENERA UN CÁLCULO LÓGICO

CON LOS SIGUIENTES PASOS:

Paso 1: Se formaliza el problema con el lenguaje lógico obteniendo expresiones, llamadas fórmulas lógicas, que conforman la

estructura lógica del problema.

Paso 2: Se interpreta cada fórmula y se demuestra la validez semántica de la estructura.

Paso 3: Se aplican reglas de inferencia para obtener resultados o conclusiones.

GII- GI2A
2020-21 3
 M1
T1: Razonar con Lógica de Primer Orden
LÓGICA

EJEMPLO 1: PROBLEMA DE RAZONAMIENTO

P1: Si estoy contento entonces canto.
P2: No canto.
Por lo tanto, Q: No estoy contento
P = {P1, P2}: premisas
Q : conclusión
P1, P2  Q

ESTRUCTURA LÓGICA DEL RAZONAMIENTO

Paso 1: Fórmulas lógicas: P1: A → B; P2: ¬B; Q: ¬A
Estructura lógica: A → B, ¬B  ¬A (1)
Paso 2: Se estudia si (1) es una estructura lógica válida interpretando cada fórmula de la estructura.
Paso 3: Si (1) es válida se obtiene ¬A aplicando reglas de inferencia a las premisas (deducción).

Idea de: INTERPRETACIÓN Idea de: DEDUCCIÓN

Es cierta? A → B, (premisa) y A → B, (premisa)

Es cierta? ¬B (premisa) ¬B (premisa)

ENTONCES … se aplican reglas de inferencia

Es cierta? ¬A (conclusión) …
Se obtiene ¬A (conclusión)
Regla de inferencia: razonamiento propuesto por
el sistema cuya validez ha sido comprobada.
Ej: La regla MT (modus tollens): A → B, ¬B  ¬A,
permite obtener la conclusión ¬A a partir de las
GII- GI2A premisas: A → B, ¬B
2020-21 3
 Paso 1 del cálculo lógico
M1
Tema 2: Formalización de razonamientos
LÓGICA Propósito: Obtener la estructura lógica
del problema formalizado

Lenguaje Proposicional: Simboliza las proposiciones atómicas con símbolos llamados variables proposicionales y las conexiones entre ellas
con símbolos llamados conectivas.

Alfabeto:

Variable proposicional: a, b, A, B, A1,…(cualquier identificador formado por letras, números,…)

Conectivas: Sean A, B proposiciones cualesquiera.

Negador (¬): se usa para formalizar expresiones : No A, es falso A. Se escribe: ¬A.

Conjunción (): se usa para formalizar : A y B, A pero B, A aunque B,… Se escribe: A  B

Disyunción (v): se usa para formalizar : A o B, al menos A o B. Se escribe: A v B

Condicional (→): se usa para formalizar : Si A entonces B, A es suficiente para B, B es necesario para A, A sólo si B…. Se escribe: A → B

Bicondicional (): se usa para formalizar :A si, y sólo si B, A es equivalente a B,… .Se escribe: A  B

REGLAS: Toda variable proposicional es una fórmula bien formada (en adelante, para referirnos a una fórmula lógica escribiremos para abreviar fbf).
Si A y B son fbfs entonces ¬A, A  B, A  B, A → B, A  B también son fbfs.
Prioridad en las conectivas para el cálculo: 1º: ¬; 2º:  , ; 3º: →, . Una fbf se define por la conectiva de mayor jerarquía.

PASOS PARA FORMALIZAR:

1º Detectar las proposiciones atómicas diferentes que aparecen en cada proposición. Elegir variable proposicional que las represente y escribirlas
en un conjunto llamado marco conceptual (MC) junto con breve enunciado de lo que significan.
2º Si es el caso, determinar las conexiones entre las proposiciones atómicas. Elegir símbolo para formalizarlas según alfabeto del lenguaje.
3º Formalizar cada proposición y obtener una fórmula lógica. Escribir Fbf-P para señalar la fórmula bien formada de la proposición P.
4º Mostrar la estructura lógica del razonamiento usando el deductor () para separar las premisas de la conclusión.

Con esta representación del lenguaje se construye un cálculo lógico proposicional con aplicaciones en:
• Análisis de circuitos y confiabilidad de sistemas mediante árboles lógicos.
GII- GI2A
2020-21 • Aplicaciones a problemas de planificación,... 5
 M1
Tema 2: Formalización de razonamientos
LÓGICA
Lenguaje Predicativo: Introduce un conjunto de símbolos que permiten simbolizar los sujetos, sus propiedades (acciones, cualidades) y relaciones
con otros sujetos. El conjunto de estos objetos se conoce como universo o dominio de discurso (D).

Alfabeto: proposicional + símbolos de:

Predicado: Partícula de la proposición que define las propiedades y relaciones entre sujetos.
- Predicados: P(Arg1,…Argn)
Se formaliza con un identificador (letra(s)) y con términos encerrados entre paréntesis, a los
- Arg constantes: a,b,c…
que llamaremos argumentos. Éstos identifican a los sujetos de la proposición afectados por el
- Arg variables: x,y,z…
predicado. Los argumentos pueden ser: constantes o variables.
- Cuantificador universal: 
Algunos casos:
- Cuantificador universal: 
Predicado de propiedad con sujeto constante :
Cualidad, atributo que identifica a un sujeto (pueden ser varios)
Ej: P1: “Luis es guapo” Predicado de propiedad con sujeto variable:
Predicado: es guapo; sujeto : Luis; Cualidad que se le atribuye a un conjunto de sujetos
MC={Guapo(x): x es guapo} Fbf-P1: Guapo(luis) (fbf atómica) Ej: P3:”Todos son guapos”.
Ej: P2: “Luis y Juan son guapos” MC={Guapo(x): x es guapo}
sujetos : Luis, Juan; Fbf-P3: x Guapo(x) (fbf molecular)
Fbf-P2: Guapo(luis)  Guapo(juan) (fbf molecular)

Predicado de relación con sujetos constantes: Predicado de relación con sujetos constantes y/o variables:

Relación entre varios sujetos Relación entre varios sujetos

Ej: P4: “Luis es novio de María”. Ej: P6: “Luis es novio de alguien”.

Predicado: es novio; sujetos: Luis, María; MC={Novio(x,y): x es novio de y}

MC={Novio(x,y): x es novio de y} Fbf-P6: x Novio(luis, x) (fbf molecular).

Fbf-P4: Novio(luis, maria) (fbf atómica). Ej: P7: “Todos son novios de María”.

Ej: P5: “Luis es novio de María y de Ana”. Fbf-P7: x Novio(x, maria) (fbf molecular)

sujetos: Luis, María, Ana; Ej: P8: “Todos los que son novios de María lo son de Ana”

Fbf-P5: Novio(luis, maria)  Novio(luis,ana) (fbf molecular) Fbf-P8: x [ Novio(x, maria) → Novio(x, ana) ] (fbf molecular)
GII- GI2A
2020-21 6
 M1
Tema 2: Formalización de razonamientos
LÓGICA

Equivalencias lógicas: Cualquier fbf se puede escribir de manera equivalente usando reglas de equivalencia.

Condicional y sus formas equivalentes:

A→B  ¬A  B (DI)  ¬(A  ¬B) (DI)  ¬B → ¬A (Contrapositivo)

Ej: “Si cantas, bailas”  “O no cantas o bailas“  “Es falso que cantes y no bailes“  “Si no bailas, no cantas.

El negador, conjunción y disyunción se relacionan con las leyes de De Morgan:

¬A  ¬B  ¬(A  B); Ej: “O no estás contento o no bailas“  “Es falso que estés contento y que bailes“.

¬A  ¬B  ¬(A  B); Ej: “Ni estás contento ni bailas“  “Es falso que estés contento o que bailes“

Bicondicional y su forma equivalente: A  B  (A → B)  (B → A) (ECO)

Ej: “Cantas si, y sólo si, bailas”  “Si cantas, bailas y si bailas, cantas”.

Para fórmulas cuantificadas: ¬xP(x)  x¬P(x) (¬U); x¬P(x)  ¬xP(x) (U¬); ¬x¬P(x)  xP(x) (¬E); ¬x¬P(x)  xP(x) (E¬).

Resumen: pasos para formalizar razonamientos en lpo

- Elegir nivel del lenguaje de formalización adecuado, proposicional o predicativo.

- Localizar cada proposición atómica diferente que aparece en cada proposición que define el problema.

- Para lenguaje predicativo, localizar predicados y elegir número de argumentos.

- Construir MC con las variables proposicionales y/o predicados con sus argumentos elegidos en la formalización.

- Escribir la fbf de cada proposición formalizada.

- Escribir la estructura lógica del problema formalizado.

GII- GI2A
2020-21 7
 Paso 2 del cálculo lógico
M1
Tema 3: Semántica lógica
LÓGICA Demostrar la validez de una estructura interpretando sus fbfs
componentes.
Pruebas: Tabla de Verdad y Método del Contraejemplo

- Sea R: P1, P2, …Pn  Q la estructura lógica de un razonamiento con n proposiciones premisas Pi (i=1…n) y una proposición conclusión Q.

- R es semánticamente válido o, simplemente, válido o correcto, si se demuestra que siempre que las premisas Pi son verdaderas la conclusión Q

también lo es.

- Si un razonamiento es válido se dice que la proposición conclusión Q es consecuencia lógica de las premisas Pi.

- Se trata de demostrar cuándo un conjunto de proposiciones es verdadero o falso. Consideramos:

- Toda proposición se interpreta como verdadera (V) o falsa (F). Valores de verdad de la lógica bivalente.

- Axioma de bivalencia o tercero excluso” : “Toda proposición es cierta o falsa, pero no ambas cosas”.

- El valor de verdad que tome una fbf dependerá de su estructura lógica.

- Dicho valor se obtiene aplicando las siguientes reglas semánticas de las conectivas que aparecen en la tabla, llamada tabla de verdad:

A B ¬A AB AB A→B AB

V V F V V V V
F F V F F
F V V F V V F
F F F V V

- Nos interesa estudiar si es posible interpretar todas las fbfs premisas con el valor V y si es así, estudiar cómo se interpreta la conclusión.

GII- GI2A
2020-21 8
 M1
Tema 3: Semántica lógica
LÓGICA

- Para una fbf de n-componentes atómicas diferentes tendremos del orden de 2n formas de interpretarse como V o F.

- Todas las posibles combinaciones de valores V, F de una fbf se escribirán en una tabla de verdad.

Construcción de una tabla de verdad para fbfs proposicionales:

1º Se dibujan tantas filas como interpretaciones tenga la fbf. Cada fila se corresponde con una interpretación que denotaremos por .

2º Se dibuja una columna para cada variable proposicional diferente;

3º Según la jerarquía de las conectivas que aparecen en la fbf, se escribe una columna para cada una de las conectivas en el orden conveniente.

4º Se aplican reglas semánticas para interpretar las conectivas y se van rellenando las columnas con valores V o F.

5º La columna de la conectiva principal de la fbf determinará la evaluación semántica de la fbf.

EJEMPLO 2: Tabla de verdad de la fbf: p → q  ¬p

Prioridad en conectivas: (p → (q  (¬p)))

p q ¬p q  ¬p p → q  ¬p
4 interpretaciones
1 V V F F F 1 = {p=V, q=V}; Para cada i la fbf tomará un
2 V F F F F 2 = {p=V, q=F}; valor de verdad, V o F.
3 F V V V V 3 = {p=F, q=V};
4 F F V F V 4 = {p=F, q=F}

GII- GI2A
2020-21 9
 M1
Tema 3: Semántica lógica
LÓGICA

-  es una Interpretación modelo de una fbf-P, si P se interpreta como V para los valores de .

Ej. La Fbf: p  q se interpreta como V según la interpretación 1 = {p=V, q=V}. 1 es una interpretación modelo de la fbf.

-  es una Interpretación contramodelo o contraejemplo de una fbf-P, si P se interpreta como F para los valores de .

Ej. La Fbf: p  q se interpreta como F según la interpretación 2 = {p=F, q=V}. 2 es un contraejemplo de la fbf.

- Sea una fbf-P con 2n interpretaciones. La fbf-P se interpreta , evalúa o clasifica semánticamente para las 2n interpretaciones como:

Tautología: si toda  es un modelo de la fbf-P.

Contradicción: si toda  es un contramodelo de la fbf-P.

Contingencia: si existen interpretaciones modelo y contramodelo de la fbf-P.

EJEMPLO 3: Interpretar la fbf: p → q  ¬p EJEMPLO 4: Clasificar semánticamente la fbf: p → q v ¬q

Prioridad: (p → (q  (¬p))) Prioridad: (p → (q v (¬q)))

p q ¬p q  ¬p p → q  ¬p 4 interpretaciones p q ¬q q v ¬q p → q v ¬q
1 = {p=V,q=V}; Contramodelo
1 V V F F F 1 V V F V V
2 V F F F F 2 = {p=V,q=F}; Contramodelo 2 V F V V V
3 F V V V V 3 = {p=F,q=V}; Modelo 3 F V F V V
4 F F V F V 4 = {p=F,q=F} Modelo 4 F F V V V

La fbf es una contingencia ya que tiene interpretaciones La fbf es una tautología ya que todas sus
modelo (filas 3 y 4) y contramodelo (filas 1 y 2) interpretaciones i (i = 1,…4) son modelo.

GII- GI2A
2020-21 10
 M1
Tema 3: Semántica lógica
LÓGICA
MÉTODOS PARA ESTUDIAR LA VALIDEZ DE RAZONAMIENTOS

La validez de un razonamiento se puede determinar a partir del siguiente resultado:

“Un razonamiento es válido si, y sólo si, su fórmula asociada es una tautología”

Fórmula asociada a un razonamiento: Un razonamiento con estructura R: P1,…Pn  Q se corresponde con la fórmula condicional

Fbf-R: P1  P2  …  Pn → Q (y sus formas equivalentes) siendo n un entero positivo. Se dice que fbf-R es la fórmula asociada al

razonamiento R.

Se estudia si la fbf-R es una tautología usando una de las dos opciones de demostración siguientes:

- Tablas de verdad: se escribe la fbf -R en una tabla de verdad y se estudia si es una tautología. (ver Ejemplo-5)

- Método del contraejemplo: se supone que la fbf-R es falsa, es decir, admite al menos una interpretación contraejemplo. Se

comprueba si esta suposición lleva a contradicción buscando los valores de verdad de sus componentes atómicas. Si aparece

contradicción la fbf-R es tautología y por tanto R es correcto. (ver Ejemplo-6)

GII- GI2A
2020-21 13
 M1
Tema 3: Semántica lógica
LÓGICA
MÉTODOS PARA ESTUDIAR LA VALIDEZ DE RAZONAMIENTOS

En los ejemplos, 5 y 6 se estudia la validez del razonamiento R: P1: p → q; P2: q → r; Q: p → r, a partir del estudio semántico de
una de sus fbfs asociadas, por ejemplo, Fbf-R : (p → q)  (q → r) → (p → r)

EJEMPLO 5 En una tabla de verdad se estudia el valor semántico de la fbf-R

A B C Fbf-R
p q r p→q q→ r p→ r A B AB→C
En la columna Fbf-R se determina el valor semántico de la fórmula
1 V V V V V V V V
2 V V F V F F F V asociada al razonamiento R.

3 V F V F V V F V Como todas las interpretaciones  son modelo, la Fbf-R es una tautología,

4 V F F F V F F V
luego el razonamiento R es correcto
5 F V V V V V V V
6 F V F V F V F V
7 F F V V V V V V
8 F F F F F F F V

EJEMPLO 6 Aplicamos el método del contraejemplo a la Fbf-R

Suponemos que la Fbf-R es falsa. Esto significa que (p → q)  (q → r) = V (1) y (p → r) = F (2)

De (1) se deduce que: (p → q) = V y (q → r ) = V

De (2) se deduce que: p = V y r = F.

Si p = V y (p → q) = V entonces q = V.

Si q = V y (q → r) = V, entonces r = V. Este valor se contradice con el que se deduce en (2).

GII- GI2A Luego la fbf -Rno puede ser falsa, no tiene ninguna interpretación contraejemplo, es decir, es una tautologia.
2020-21 14
 M1
Tema 3: Semántica lógica
LÓGICA
MÉTODOS PARA ESTUDIAR LA VALIDEZ DE RAZONAMIENTOS

La validez de un razonamiento se puede determinar estudiando la interpretación de su estructura lógica.

Una estructura es válida si siempre que las premisas se interpreten como verdaderas la conclusión también sea
interpretada como verdadera

Dada R: P1, P2, …Pn  Q, se estudia si la estructura R es válida usando una de las dos opciones de demostración siguientes

- Tablas de verdad: se construye una tabla de verdad con todas las fbfs de la estructura. Se buscan las filas en las que las

premisas son verdaderas y se observa cuál es el valor de la conclusión. Si en todos los casos las premisas y la conclusión son

verdaderas el razonamiento es válido (ver Ejemplo 7 y Ejemplo 8).

- Método del contraejemplo: se supone que la estructura tiene una interpretación contraejemplo. Para ello se interpretan las premisas

como verdaderas y la conclusión falsa y se comprueba si esta suposición nos lleva a contradicción buscando los valores de verdad de las

componentes atómicas de cada fbf. Si la suposición lleva a contradicción, la estructura no admite la interpretación contraejemplo supuesta y

entonces la estructura es válida; si no encontramos contradicción la estructura no es válida ya que admite contraejemplo (ver Ejemplo 9).

GII- GI2A
2020-21 15
 M1
Tema 3: Semántica lógica
LÓGICA
MÉTODOS PARA ESTUDIAR LA VALIDEZ DE RAZONAMIENTOS

Usando tablas de verdad

En los ejemplos 7 y 8 se estudia la validez de los razonamientos R1 y R2 interpretando cada fbf de su estructura en una tabla de verdad.
Se construye la tabla de verdad poniendo todas las fbf que conforman el razonamiento y estudiando semánticamente cada una de dichas fbfs.
Se buscan las filas en las cuales las fbfs premisas Pi son V y se observa cómo se interpreta la fbf conclusión Q.
Si en todos los casos en los que las fbfs Pi son V la conclusión Q también lo es, el razonamiento es válido. Es suficiente que existe una
interpretación en la cual las fbfs Pi se interpreten como verdaderas y Q falsa para indicar que el razonamiento no es correcto.
A esta interpretación se le llama contraejemplo del razonamiento.

EJEMPLO 7 R1: ¬A → B, ¬B  A EJEMPLO 8 R2: ¬A → B, B  ¬A

P1: P2: P1: P2:

A B ¬A ¬B Q: A A B ¬A Q: ¬A
¬A → B ¬B ¬A → B B
V V F F V F V V V F V V F
V F F V V V V V F F V F F
F V V F V F F F V V V V V
F F V V F V F F F V F F V

R1 es válido ya que en la fila 2 las premisas P1 y P2 R2 NO es válido ya que en la fila 1 las premisas P1 y P2 son V y Q es F.
son V y Q también. En la fila 3 P1, P2 y Q son V , pero la interpretación que determina la
Las demás filas no nos interesan. validez de R2 es la de la fila 1.

! OjO !: Si se demuestra que Q es consecuencia lógica de las premisas Pi, podemos asegurar que no lo es ¬Q
Comprobarlo con los ejemplos 7 y 8
GII- GI2A
2020-21 11
 M1
Tema 3: Semántica lógica
LÓGICA
ESTUDIO DE LA VALIDEZ DE RAZONAMIENTOS USANDO TABLAS DE VERDAD

Usando método del contraejemplo

Método del contraejemplo: Dado R: P1, P2, …Pn  Q, una interpretación contraejemplo de R es aquella que hace que todas las fbfs-Pi se
interpreten como ciertas y Q como falsa. Si dicha interpretación existe, el razonamiento no es válido, si no existe, el razonamiento sí es válido.
Vemos, con el Ejemplo 9, cómo buscar un contraejemplo en un razonamiento:

EJEMPLO 9 Sea el razonamiento: R: P1: A, P2: ¬B → A, Q: ¬B. Se debe demostrar la validez de R aplicando el método del contraejemplo.

Para ello se comprueba si R tiene, al menos, una interpretación contraejemplo.

1º Suponemos que R admite una interpretación contraejemplo. Esto significa que se pueden interpretar las premisas P1, P2 como
verdaderas (V) y la conclusión Q falsa (F).

P1: A P2: ¬B → A Q: ¬ B
V V F

2º Se demuestra su existencia. Se debe comprobar si la hipótesis 1) es cierta. Para ello, y teniendo en cuenta las reglas semánticas de
las conectivas, se calculan los valores de verdad de las fbfs atómicas que conforman las premisas y la conclusión, teniendo en cuenta la
existencia del contraejemplo.

En el ejemplo tenemos que Q = F, es decir, ¬B = F.

Con esta hipótesis, P2 = V siempre, independientemente de que A = V o A = F (un implicador con antecedente F es siempre V).

Por hipótesis P1 = V, es decir, A = V. Luego para A = V, P1 y P2 son ciertas.

Luego existe interpretación contraejemplo de R dada por el conjunto I = { A=V, B=V}.

El razonamiento R no es válido.

GII- GI2A¡OjO!: Es suficiente que exista una (pueden existir más) interpretación contraejemplo en un razonamiento para asegurar que no es correcto.
2020-21 13
 M1 Paso 3 del cálculo lógico
Tema 4: Deducción Natural
LÓGICA Aprender a obtener conclusiones manipulando
sintácticamente las premisas
Prueba: Deducción Natural
R: P1, P2, …Pn  Q

Se debe obtener la fbf-Q a partir de las fbfs premisas Pi aplicando reglas de inferencia del sistema. El proceso de cálculo es el de deducción
natural (en prácticas se verá la deducción automática).

En general, una deducción o inferencia es el proceso que, en una secuencia de pasos, permite obtener fbfs a partir de otras aplicando reglas.

La deducción natural es el sistema formal que a partir de unas premisas y con aplicación de reglas básicas, obtiene determinadas conclusiones.
Éstas se dicen que son derivadas de las premisas.

Usaremos el sistema de reglas propuesto por Gentzen (1934) (ver Hojas de reglas), que propone dos reglas (una de introducción y otra de
eliminación) para cada conectiva y cuantificador. Si la regla básica introduce en su conclusión una conectiva que no aparece en sus premisas
será una regla de introducción; si elimina de su conclusión una conectiva que aparece en sus premisas será una regla de eliminación.
Este proceso que se basa en la aplicación de reglas a una fbf permite añadir o quitar símbolos lógicos de la fbf y así, por pura manipulación
sintáctica, la fbf se desmonta hasta obtener sus componentes básicas (fórmulas atómicas) que se vuelven a montar en la configuración
adecuada (fórmula lógica que queremos obtener como conclusión).

Tendremos una deducción correcta cuando consigamos una secuencia finita de fórmulas donde cada una de ellas se ha obtenido mediante la
aplicación de alguna regla de inferencia. Todas las fórmulas que aparecen en la deducción deben estar justificadas.

Regla de inferencia básica: razonamiento propuesto por el

sistema cuya validez ya ha sido comprobada.
Ej: La regla MT (modus tollens): A → B, ¬B  ¬A, permite
obtener la conclusión ¬A a partir de las premisas: A → B, ¬B

GII- GI2A
2020-21 14
 M1
Tema 4: Deducción Natural
LÓGICA
R: P1, P2, …Pn  Q

Supuesto provisional: En cualquier paso de una deducción se puede introducir un supuesto que resulta ser una sub-deducción de la deducción
en la que se añade. Es una herramienta muy potente que permite modularizar las deducciones y obtener un sub-objetivo más sencillo que el
objetivo final pero que nos lleva a él. La fbf con la que comienza el supuesto es una premisa de la sub-deducción que abre. Las fbfs que
aparecen en el supuesto son inaccesibles fuera de él, sólo es válida la fbf que se deduce del mismo. Para finalizar una deducción todos los
supuestos abiertos en ella deben estar cerrados.

Componentes de una deducción natural: Fórmulas premisas, fórmulas deducidas de otras, supuestos provisionales y reglas de inferencia.
1º Cada fórmula debe aparecer en una línea numerada en orden correlativo y debe estar justificada. Veamos cómo:
- Si la fórmula es una premisa se escribe una raya antes del número de línea donde aparece dicha fórmula.
- Si la fórmula ha sido deducida de otra(s) por aplicación de alguna regla se escribe a la derecha de dicha fórmula el nombre de la
regla que se ha aplicado para obtenerla y el número de la línea(s) de las fórmulas que han intervenido en la deducción de ella.
- Si la fórmula es una premisa de un supuesto se identa quedando esta sangría hasta que se cierra dicha suposición. La deducción
prosigue con la sangría inicial.
2º La deducción finaliza con la fórmula conclusión, ésta se justifica de la misma manera que la de una fórmula deducida.

Dos estrategias para hacer una deducción:

- Prueba Directa: Si la fbf conclusión que se quiere obtener es de la forma: A → B, se abre un supuesto provisional suponiendo cierta la fbf A
y se aplican reglas hasta obtener la fbf B. El supuesto se cierra con la fbf B. En la siguiente línea se introduce la fbf A → B, con el nombre de la
regla TD y las líneas donde aparecen A y B.
- Reducción al absurdo: Se abre un supuesto suponiendo que es cierta la fbf negada que se quiere obtener. Se aplican reglas hasta obtener
una contradicción. Se cierra el supuesto con dicha contradicción. Del supuesto se deduce la negación de la fbf premisa que se escribe en la
siguiente línea junto con la regla IN, y las líneas donde empieza y se cierra el supuesto.

GII- GI2A
2020-21 15
 M1
Tema 4: Deducción Natural
LÓGICA

¿Cómo se hace una deducción? Lo vemos con ejemplos

1º Se escriben las fbfs premisas poniendo un guion delante del número de línea en la que se encuentran.
2º Se escriben las fbfs deducidas y/o las premisas de supuestos justificando cada una.
3º Se finaliza cuando se obtiene la fbf conclusión.

EJEMPLO 10 Se demuestra por deducción natural que la fbf: ¬ma → lo es una conclusión de las siguientes premisas:

P1: (fa  ca)  ¬(fa  ca), P2: fa → ma, P3: ca → lo

Como la conclusión tiene el implicador como conectiva principal, se realiza la deducción usando la estrategia de la prueba directa

-1 (fa  ca)  ¬(fa  ca)

-2 fa → ma
-3 ca → lo
4 ¬ma (supuesto cuya premisa es el antecedente de la implicación de la conclusión)
5 ¬fa MT, 2, 4
6 fa  ca EC, 1
7 ca SD, 5, 6
8 lo MP, 3, 7 (fbf que cierra el supuesto y que es el consecuente del implicador de la conclusión)
9 ¬ma → lo TD, 4-8

GII- GI2A
2020-21 16
 M1
Tema 4: Deducción Natural
LÓGICA

¿Cómo se hace una deducción? Lo vemos con ejemplos

EJEMPLO 11 Se demuestra por deducción natural que la fbf: gp es una conclusión de las siguientes premisas:

P1: rb → mb, P2: mb → bv  gp, P3: rb

Se realiza la deducción usando la estrategia de reducción al absurdo.

-1 rb → mb
-2 mb → bv  gp
-3 rb
4 ¬gp (supuesto cuya premisa es la negación de la conclusión)
5 mb MP,1, 3
6 bv  gp MP, 2, 5
7 gp EC, 6
8 ¬gp  gp IC,4, 7 (de la suposición 4 se deduce una contradicción)
9 gp IN, 4-8 (no es cierta la fbf 4 sino su complementaria)

GII- GI2A
2020-21 16
 M1
Tema 4: Deducción Natural
LÓGICA

¿Cómo se hace una deducción? Lo vemos con ejemplos

EJEMPLO 12 Se demuestra por deducción natural que la fbf: ¬ap  ¬fe es una conclusión de las siguientes premisas:

P1: ¬(es → ap  fe), P2: ap  fe → es, P3: ¬es

Se realiza la deducción aplicando reglas de inferencia a las premisas.

-1 ¬(es → ap  fe)
-2 ap  fe → es
-3 ¬es
4 ¬( ¬es  (ap  fe))) DI, 1
5 ¬¬es  ¬(ap  fe)) Morgan, 4
6 es  ¬(ap  fe)) DN, 5
7 es EC, 6
8 es  ¬es IC, 3, 7
9 ¬ap  ¬fe ECQ, 8

GII- GI2A
2020-21 16
 M1
Material para completar apuntes de lógica
LÓGICA

Libros recomendados :

“Lógica de Primer Orden”. Castel Mª J. y Llorens F. DCCIA, U.A. 1999.

“Introducción a la Lógica Formal”. Deaño, A. Alianza U.Textos, 1992.

“Lógica Simbólica” Garrido, M. Ed. Tecnos, S.A., 2ºed. 1991

“Matemática Discreta y Lógica”. Una perspectiva C. C”. Grassmann, W.K. y Tremblay. Ed. Prentice Hall, 1996.

Enlaces web

Apuntes de la asignatura Lógica Computacional de la UNED

Lógica y Teoría de Conjuntos de Carlos Ivorra Castillo

http://sisbib.unmsm.edu.pe/bibvirtualdata/libros/Filosofia/intro_logica/1_parte.pdf

http://divulgamat.ehu.es/weborriak/TestuakOnLine/03-04/PG03-04-bcarrascal.pdf

GII- GI2A
2020-21 23