M1

LÓGICA LÓGICA DE PRIMER ORDEN

La Lógica de Primer Orden es la ciencia que trata del análisis y codificación del razonamiento. Hoy día es el sistema que fundamenta la informática
ya que la formalización del conocimiento y la automatización de razonamientos son primordiales en muchas áreas de la ciencia de la computación.

T1-Log: Razonar con Lógica de Primer Orden

- Razonamiento deductivo válido.
- Esquema general de un razonamiento.
- Sistema de Lógica de Primer Orden

T2-Log: Formalización de razonamientos con el

lenguaje lógico Propósito :
- Lenguaje proposicional y predicativo.  Desarrollar destrezas de razonamiento mediante el aprendizaje de
- Obtención de fórmulas y estructuras lógicas. procesos deductivos del sistema formal de la Lógica de Primer Orden .

T3-Log: Semántica lógica

- Interpretación de fórmulas lógicas.
- Tautologías.
- Tablas de verdad y contraejemplo.
- Interpretación de estructuras lógicas.

T4-Log: Deducción Natural

- Reglas de inferencia.
- Estrategias para hacer deducciones.
- Subdeducciones o supuestos provisionales.

UA 1
2018-10
 M1
LÓGICA T1-Log: Razonar con Lógica de Primer Orden

Razonamiento lógico: proceso cognitivo por medio del cual a partir de premisas y por aplicación de reglas se infiere o deduce una conclusión. Las
premisas son los hechos que describen el conocimiento conocido y la conclusión es el conocimiento que se obtiene a partir de ellas.

Razonamiento lógico deductivo: 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. En un razonamiento deductivo válido 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.

ESQUEMA GENERAL DE UN RAZONAMIENTO

Si P = { P1, P2,…Pn }
Si es cierto P entonces es cierto Q.
Es cierto P, por lo tanto, es cierto Q Esquema: P1, P2,… Pn  Q
PQ
P: conjunto de proposiciones premisas El símbolo  se llama deductor

Q: proposición objetivo o conclusión

Proposición lógica: afirmación que tiene sentido pleno y que puede ser verdadera o falsa pero no ambas cosas. independientemente de su
contenido. Por ejemplo, “Madrid es la capital de España”, es un hecho cierto, pero considerándolo como una proposición para su tratamiento
lógico, será un enunciado que puede ser cierto o falso. En el cálculo lógico que desarrollaremos no se tendrá en cuenta el conocimiento
empírico de los hechos que describen el problema sino su estructura o “forma lógica”.
Según su complejidad una proposición puede ser:
Atómica: enunciado simple., como por ejemplo, “Ana estudia lógica”.
Molecular: enunciado formado por la conexión de varias proposiciones atómicas, como por ejemplo, “Ana estudia lógica y física” donde la
proposición atómica “Ana estudia lógica” se conecta con “Ana estudia física” mediante la conectiva “y”.
Ojo: No son proposiciones: a) x > 5 por ser una afirmación que será cierta o falsa según el valor de x. b) ¿Cómo estás? No es una afirmación.

UA
2018-10 2
 M1
LÓGICA T1-Log: Razonar con Lógica de Primer Orden

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

- Interesa demostrar la validez de la estructura lógica del razonamiento sin tener en cuenta la información que aporte el problema.

- Aplicando reglas del sistema lógico se demostrará que la verdad de la conclusión se deduce de la verdad de las premisas.

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

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

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

UA
2018-10 4
 M1
LÓGICA T1-Log: Razonar con Lógica de Primer Orden

Niveles de abstracción en lógica de primer orden para demostrar la validez de razonamientos

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

Elementos del cálculo:

Lenguaje : alfabeto y reglas sintácticas para la formalización de razonamientos

Semántica: reglas y métodos semánticos para estudiar la verdad de la estructura lógica.

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

CÁLCULO LÓGICO

EJECUTA LOS SIGUIENTES PASOS:

Paso 1: Se formaliza el problema de razonamiento con el lenguaje lógico obteniendo su estructura lógica del

razonamiento.

Paso 2: Se interpreta la estructura lógica usando las Tablas de Verdad y el Método del Contraejemplo

Paso 3: Se aplican reglas de inferencia del cálculo deductivo de Gentzen para obtener conclusiones.

UA
2018-10 5
 M1
LÓGICA T1-Log: Razonar con Lógica de Primer Orden

Ej1: RAZONAMIENTO
P1: Si estoy contento entonces canto.
P2: No canto.
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 de las premisas: P1: A  B; P2: ¬B; Q: ¬A

Estructura lógica del razonamiento: A  B, ¬B  ¬A (1)

Paso 2: Se estudia si (1) es una estructura lógica válida interpretando cada fórmula.

Paso 3: Si (1) es válida se obtiene ¬A aplicando reglas de inferencia a las premisas (deducción).

DEDUCCIÓN
INTERPRETACIÓN A  B, (premisa)
Es cierta? A  B, (premisa) y ¬B (premisa)
Es cierta? ¬B (premisa) … se aplican reglas de inferencia
Regla de inferencia: razonamiento propuesto por el
ENTONCES …
sistema cuya validez ha sido comprobada.
Es cierta? ¬A (conclusión) Se obtiene ¬A (conclusión) Ej: La regla MT (modus tollens): A  B, ¬B  ¬A,
permite obtener la conclusión ¬A a partir de las
premisas: A  B, ¬B
UA
2018-10 6
 Paso 1 del cálculo lógico
M1
Tema 2: Formalización de razonamientos Formalizar razonamiento
LÓGICA

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

Alfabeto: Permite expresar las conexiones del lenguaje natural como leyes lógicas.

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, implicador (): formaliza: Si A entonces B, A es suficiente para B, B es necesario para A, A sólo si B, No A a menos que B. Se
escribe: A  B

Bicondicional, coimplicador (): formaliza :A si, y sólo si B, A es equivalente a B, A es suficiente y necesario para 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 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 ENUNCIADOS CON EL LENGUAJE PROPOSICIONAL:

1º Detectar las proposiciones atómicas diferentes que aparecen en cada proposición. Elegir una variable proposicional para cada una de ellas 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º Obtener la fórmula lógica de la proposición. 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:
UA • Análisis de circuitos y confiabilidad de sistemas mediante árboles lógicos.
2018-10 7
• Aplicaciones a problemas de planificación,...
 Paso 1 del cálculo lógico
M1
Tema 2: Formalización de razonamientos Formalizar razonamiento
LÓGICA

EJEMPLOS DE FORMALIZACIÓN DE PROPOSICIONES CON EL LENGUAJE PROPOSICIONAL

Las siguientes proposiciones Pi se formalizan usando usa el siguiente marco conceptual MC = { ca: canto; ba: bailo; ta: taconeo }

P1. Canto y bailo; Fbf-P1: ca  ba

P2. Canto pero no bailo ni taconeo. Fbf-P2: ca  ¬ba  ¬ta

P3: Ni canto ni bailo Fbf-P3: ¬ca  ¬ba

P4: Es cierto que cante aunque no lo es que, baile o taconee. Fbf-P4: ca  ¬(ba v ta)

P5: O canto y bailo, o es falso que cante y taconee . Fbf-P5: (ca  ba) v ¬(ca  ta)

P6: Es suficiente que cante para que baile y no taconee Fbf-P6: ca  ba  ¬ta

P7: Es necesario que cante para que baile y no taconee Fbf-P7: ba  ¬ta  ca

P8: Sólo si canto y bailo, no taconeo Fbf-P8: ¬ta  ca  ba

P9: Para que baile es necesario y suficiente que cante Fbf-P9: ba  ca

P10: A menos que taconee o baile, no canto Fbf-P10: ca  ta v ba

P11: Taconeo y bailo a menos que no cante Fbf-P11: ¬(ta  ba)  ¬ca

P12: Ni canto ni bailo a menos que no taconee Fbf-P12: ¬(¬ca  ¬ba)  ¬ta

P13: No es necesario que cante ni baile para que taconee Fbf-P13: ¬(ta  ca  ¬ba)

P14: Es necesario, pero no suficiente, que cante para que baile Fbf-P14: (ba  ca)  ¬(ca  ba)

La estructura lógica de un razonamiento que tuviera como premisas las proposiciones P1 y P6 y como conclusión la fbf: ¬ta sería:
ca  ba, ca  ba  ¬ta  ¬ta

UA
2018-10 8
 Paso 1 del cálculo lógico
M1
Tema 2: Formalización de razonamientos Formalizar razonamiento
LÓGICA

Lenguaje Predicativo: Introduce un conjunto de símbolos que permiten simbolizar sujetos, propiedades (acciones, cualidades) y relaciones con otros
sujetos. El conjunto de estos sujetos se conoce como universo o dominio de discurso (D) del discurso.

Alfabeto: proposicional + símbolos de:

Predicado: componente de la proposición que define las propiedades y relaciones entre sujetos.
- Predicados: P(Arg1,…Argn)
Se formaliza con un identificador formado por letra(s)) y con términos encerrados entre paréntesis,
- Arg constantes: a,b,c…
a los que llamaremos argumentos del predicado. Éstos identifican a los sujetos de la proposición
- Arg variables: x,y,z…
afectados por el 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: es guapo; sujeto : Luis; Predicado de propiedad con sujeto variable:

MC={Guapo(x): x es guapo} Fbf-P1: Guapo(luis) (fbf atómica) Cualidad que se le atribuye a un conjunto de sujetos

Ej: P2: “Luis y Juan son guapos” Ej: P3:”Todos son guapos”.

sujetos : Luis, Juan; MC={Guapo(x): x es guapo}

Fbf-P2: Guapo(luis)  Guapo(juan) (fbf molecular) Fbf-P3: x Guapo(x) (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); x € D, D= {sujetos que aparecen en el problema}
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); x € D.
sujetos: Luis, María, Ana; Ej: P8: “Todos los que son novios de María lo son de Ana”

UA Fbf-P5: Novio(luis, maria)  Novio(luis,ana) (fbf molecular) Fbf-P8: x [ Novio(x, maria)  Novio(x, ana) ] (fbf molecular); x € D.
2018-10 9
 Paso 1 del cálculo lógico
M1
Tema 2: Formalización de razonamientos Formalizar razonamiento
LÓGICA

Equivalencias lógicas: Cualquier fbf se puede escribir de manera equivalente pero sintácticamente diferente 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¬).

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 de razonamiento formalizado.

UA
2018-10 10
 Paso 2 del cálculo lógico
M1 Valoración semántica de la estructura lógica.
LÓGICA Tema 3: Semántica lógica 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, 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 estudiar cuándo una proposición es verdadera (V) o falsa (F). Consideramos:

- Los valores de verdad de la lógica bivalente son: V para verdadero o cierto y F para falso.

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

- El valor de verdad que toma una fbf molecular depende de su estructura lógica (conectivas).

- Las siguientes reglas semánticas permiten obtener el valor semántico de una fbf lógica:

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

- La tabla anterior se conoce como tabla de verdad.

UA
2018-10 11
 Paso 2 del cálculo lógico
M1 Valoración semántica de la estructura lógica.
LÓGICA Tema 3: Semántica lógica Pruebas: Tabla de Verdad y Método del Contraejemplo

- 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.

Ej: Tabla de verdad de la fbf1: p  q  ¬p

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

p q ¬p q  ¬p p  q  ¬p

1 V V F F F
2 V F F F F
3 F V V V V
4 F F V F V

UA
2018-10 12
 Paso 2 del cálculo lógico
M1 Valoración semántica de la estructura lógica.
LÓGICA Tema 3: Semántica lógica Pruebas: Tabla de Verdad y Método del Contraejemplo

-  es una Interpretación modelo de una fbf-P si ésta 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 ésta 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 algunas interpretaciones son modelo y otras contramodelo de la fbf-P.

Ej: Interpretar o clasificar semánticamente la fbf-1: p  q  ¬p EJ: Clasificar semánticamente la fbf-2: 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-1 es una contingencia ya que tiene interpretaciones La fbf-2 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.

UA
2018-10 13
 Paso 2 del cálculo lógico
M1 Valoración semántica de la estructura lógica.
LÓGICA Tema 3: Semántica lógica Pruebas: Tabla de Verdad y Método del Contraejemplo

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:

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

- 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 las componentes atómicas de la fbf-R. Si

aparece contradicción la fbf-R no admite ninguna interpretación contraejemplo, por lo que se clasificaría como tautología, esto

implicaría que el razonamiento R asociado a ella es correcto.

UA 13
2018-10
 Paso 2 del cálculo lógico
M1 Valoración semántica de la estructura lógica.
LÓGICA Tema 3: Semántica lógica Pruebas: Tabla de Verdad y Método del Contraejemplo

Ej Se estudia la validez del razonamiento R1: P1: p  q; P2: q  r; Q: p  r, a partir del estudio semántico de su fbf asociada
Fbf-R1 : (p  q)  (q  r)  (p  r) usando a) una tabla de verda; b) método del contraejemplo.

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

4 V F F F V F F V Como todas las interpretaciones  son modelo,

5 F V V V V V V V
la Fbf-R1 es una tautología, luego el razonamiento R1 es correcto
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

b) Interpretación de la Fbf-R1 aplicando el método del contraejemplo.

Suponemos que la fbf-R1 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).

Luego la fbf –R1 no puede ser falsa, no tiene ninguna interpretación contraejemplo, luego es una tautologia y R1 correcto.
UA 14
2018-10
 Paso 2 del cálculo lógico
M1 Valoración semántica de la estructura lógica.
LÓGICA Tema 3: Semántica lógica Pruebas: Tabla de Verdad y Método del Contraejemplo

La validez de un razonamiento se puede determinar interpretando cada una de las fbfs que conforman su estructura lógica.
Una estructura lógica es válida si siempre que las premisas se interpreten todas como verdaderas la conclusión también
sea interpretada como verdadera.

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

- 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.

- 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. Para comprobar este resultado se supone que la estructura lógica tiene una interpretación contraejemplo. Para ello se

interpretan las premisas como verdaderas y la conclusión como falsa y se buscan los valores de verdad de las componentes atómicas de las

fbfs de la estructura. Si esta 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.

UA 15
2018-10
 Paso 2 del cálculo lógico
M1 Valoración semántica de la estructura lógica.
LÓGICA Tema 3: Semántica lógica Pruebas: Tabla de Verdad y Método del Contraejemplo

En los siguientes ejemplos se estudia la validez de los razonamientos R2 y R3 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.

EJ R2: ¬A  B, ¬B  A EJ R3: ¬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

R2 es válido ya que en la fila 2 las premisas P1 y R3 NO es válido ya que en la fila 1 las premisas P1 y P2 son V y Q es F.
P2 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 R3 es la de la fila 1.

! OjO !: Si se demuestra que Q es consecuencia lógica de las premisas Pi, se puede asegurar que no lo es ¬Q
Comprobarlo con los ejemplos anteriores.
UA 16
2018-10
 Paso 2 del cálculo lógico
M1 Valoración semántica de la estructura lógica.
LÓGICA Tema 3: Semántica lógica Pruebas: Tabla de Verdad y Método del Contraejemplo

EJ Sea el razonamiento: R4: P1: A, P2: ¬B  A, Q: ¬B. Se demuestra la validez de R4 aplicando el método del contraejemplo.

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

1) Suponemos que R4 admite una interpretación contraejemplo, es decir, se pueden interpretar las premisas P1, P2 como verdaderas (V)
y la conclusión Q como falsa (F). Escribimos:

P1: A P2: ¬B  A Q: ¬ B

V V F

2) Se demuestra su existencia, es decir, 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 supuesta 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 condicional con antecedente F es siempre V).

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

Como existe interpretación contraejemplo de R4 dada por el conjunto I = { A=V, B=V}, el razonamiento R4 no es válido.

¡OjO!: Es suficiente que exista una (pueden existir más) interpretación contraejemplo en un razonamiento para asegurar que no es correcto.

UA 17
2018-10
 M1 Paso 3 del cálculo lógico
LÓGICA Tema 4: Deducción Natural Obtener conclusiones mediante
Deducción Natural

R: P1, P2, …Pn  Q

Se debe demostrar la obtención de la fbf-Q a partir de las fbfs premisas Pi usando 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 con Prolog).

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 que permiten manipular
sintácticamente dichas fbfs se pueden obtener conclusiones. Éstas se dicen que son fbfs 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).

Una deducción es correcta cuando se consiga una secuencia finita de fórmulas donde cada una de ellas se haya 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
UA 18
2018-10
 M1 Paso 3 del cálculo lógico
LÓGICA Tema 4: Deducción Natural Obtener conclusiones mediante
R: P1, P2, …Pn  Q Deducción Natural

Sub-deducción o Supuesto provisional: en cualquier paso de una deducción se puede introducir un supuesto provisional que es una
sub-deducción en 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 de un supuesto
cerrado. 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 de la siguiente forma :
- 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 tiene como conectiva principal un implicador, es decir, es de la forma: A  B en la
deducción 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 las fbfs 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.

UA 19
2018-10
 M1 Paso 3 del cálculo lógico
LÓGICA Tema 4: Deducción Natural Obtener conclusiones mediante
Deducción Natural
¿Cómo se hace una deducción? Lo vemos con ejemplos

1º En líneas diferentes se escriben las fbfs premisas poniendo un guion delante del número de línea en la que se encuentran.
2º En las siguientes líneas se escriben las fbfs deducidas y/o las premisas de supuestos justificando cada una con el nombre
de la regla por la que se ha obtenido o bien identando la línea en el caso de que la fbf abra un supuesto.
3º Se finaliza cuando se obtiene la fbf conclusión.

Ej Se demuestra por deducción natural que la fbf:-Q ¬ma  lo es una conclusión que se deduce de las siguientes premisas:

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

Como la conclusión tiene la forma del implicador 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

UA 20
2018-10
 M1 Paso 3 del cálculo lógico
LÓGICA Tema 4: Deducción Natural Obtener conclusiones mediante
Deducción Natural

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

Ej Se demuestra por deducción natural que la fbf-Q: gp es una conclusión que se deduce 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)

UA 21
2018-10
 M1 Paso 3 del cálculo lógico
LÓGICA Tema 4: Deducción Natural Obtener conclusiones mediante
Deducción Natural

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

Ej Se demuestra por deducción natural que la fbf-Q: ¬ap  ¬fe es una conclusión que se deduce 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

UA 22
2018-10
 M1
Material para completar los temas de lógica
LÓGICA

Algunos libros básicos:

“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 [Link], 1992.

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

“Matemática Discreta y Lógica”. Una perspectiva desde la C. C”. Grassmann, W.K. y Tremblay.

Ed. Prentice Hall, 1996.

Más en Bibliografía de Guía Docente /UACloud)

Enlaces web:

Lógica computacional UNED: [Link]

Libro de Lógica y teoría de conjuntos de Carlos Iborra: [Link]

[Link]

UA 23
2018-10
 M1 Conceptos ([Link])
LÓGICA

Razonar: Exponer razones para probar algo.

Inferencia: Deducción de una cosa a partir de otra, conclusión.

Conclusión: Resolución que se ha tomado sobre una materia tras su estudio o análisis.

Deducción: Método de razonamiento que parte de conceptos generales o principios universales para llegar a conclusiones particulares.

Deducir: Inferir, obtener conclusiones de un conocimiento previo.

UA 24
2018-10