Post on 12-Feb-2020
transcript
Lógica de Primer Orden: Lógica dePredicados
Departamento de Matematicas
Logica de Primer Orden: Logica de Predicados– p.1/21
Predicados
Definici on
Un predicado es una oración que contiene unnúmero definido de variables y que se vuelve enuna proposición cuando las variables sonsustituidas por valores.
Logica de Primer Orden: Logica de Predicados– p.2/21
Predicados
Definici on
Un predicado es una oración que contiene unnúmero definido de variables y que se vuelve enuna proposición cuando las variables sonsustituidas por valores. El dominio de un predicadoes el conjunto de todos los valores que pueden sersustituidos en las variables.
Logica de Primer Orden: Logica de Predicados– p.2/21
Cuantificador Universal
Definici on
Sea Q(x) un predicado y D el dominio de Q.
Logica de Primer Orden: Logica de Predicados– p.3/21
Cuantificador Universal
Definici on
Sea Q(x) un predicado y D el dominio de Q. Unasentencia universal es una declaración de la forma:
∀x ∈ D,Q(x) (1)
Logica de Primer Orden: Logica de Predicados– p.3/21
Cuantificador Universal
Definici on
Sea Q(x) un predicado y D el dominio de Q. Unasentencia universal es una declaración de la forma:
∀x ∈ D,Q(x) (1)
Y es definida a ser verdadera si y sólo si Q(x) esverdadera para todo elemento x que está en eldominio D.
Logica de Primer Orden: Logica de Predicados– p.3/21
Cuantificador Universal
Definici on
Sea Q(x) un predicado y D el dominio de Q. Unasentencia universal es una declaración de la forma:
∀x ∈ D,Q(x) (1)
Y es definida a ser verdadera si y sólo si Q(x) esverdadera para todo elemento x que está en eldominio D. La afirmación es falsa si y sólo si Q(x)es falsa al menos para un elemento x del dominio.
Logica de Primer Orden: Logica de Predicados– p.3/21
Cuantificador Universal
Definici on
Sea Q(x) un predicado y D el dominio de Q. Unasentencia universal es una declaración de la forma:
∀x ∈ D,Q(x) (1)
Y es definida a ser verdadera si y sólo si Q(x) esverdadera para todo elemento x que está en eldominio D. La afirmación es falsa si y sólo si Q(x)es falsa al menos para un elemento x del dominio.El elemento x para el cual Q(x) es falsa se llamacontraejemplo a la afirmación universal.
Logica de Primer Orden: Logica de Predicados– p.3/21
Cuantificador existencial
Definici on
Sea Q(x) un predicado con cominio D.
Logica de Primer Orden: Logica de Predicados– p.4/21
Cuantificador existencial
Definici on
Sea Q(x) un predicado con cominio D. Unadeclaración existencial es una declaración de laforma:
∃x ∈ D, Q(x) (2)
Logica de Primer Orden: Logica de Predicados– p.4/21
Cuantificador existencial
Definici on
Sea Q(x) un predicado con cominio D. Unadeclaración existencial es una declaración de laforma:
∃x ∈ D, Q(x) (2)
Y es definida a ser verdadera si y sólo si existe enel dominio D al menos un valor de x para el cualQ(x) es verdadera.
Logica de Primer Orden: Logica de Predicados– p.4/21
Cuantificador existencial
Definici on
Sea Q(x) un predicado con cominio D. Unadeclaración existencial es una declaración de laforma:
∃x ∈ D, Q(x) (2)
Y es definida a ser verdadera si y sólo si existe enel dominio D al menos un valor de x para el cualQ(x) es verdadera. A este valor lo referiremos aunejemplo para la afirmación.
Logica de Primer Orden: Logica de Predicados– p.4/21
Cuantificador existencial
Definici on
Sea Q(x) un predicado con cominio D. Unadeclaración existencial es una declaración de laforma:
∃x ∈ D, Q(x) (2)
Y es definida a ser verdadera si y sólo si existe enel dominio D al menos un valor de x para el cualQ(x) es verdadera. A este valor lo referiremos aunejemplo para la afirmación. La afirmación seráfalsa si para todo x en el dominio Q(x) es falsa.
Logica de Primer Orden: Logica de Predicados– p.4/21
El símbolo ∀ se llama cuantificador universal.
Logica de Primer Orden: Logica de Predicados– p.5/21
El símbolo ∀ se llama cuantificador universal.
El símbolo exists se llama cuantificador existencial.
Logica de Primer Orden: Logica de Predicados– p.5/21
Ejemplo
Suponga que se hace referencia a las figuras queaparecen en la gráfica:
a
b c
d
g
e
f
Logica de Primer Orden: Logica de Predicados– p.6/21
Ejemplo
Suponga que se hace referencia a las figuras queaparecen en la gráfica:
a
b c
d
g
e
f
Podríamos definir
nuestro discurso a lasfiguras a,b,c,d,e,f,g.
Logica de Primer Orden: Logica de Predicados– p.6/21
Ejemplo
Suponga que se hace referencia a las figuras queaparecen en la gráfica:
a
b c
d
g
e
f
Podríamos definir
nuestro discurso a lasfiguras a,b,c,d,e,f,g. Ydefinir los predicados:
Azul(t) = t es de color azul.Rojo(t) = t es de color rojo.
Triangulo(t) = t es un triángulo .Cuadrado(t) = t es un cuadrado.
Circulo(t) = t es un círculo.
Logica de Primer Orden: Logica de Predicados– p.6/21
Indique cuáles afirmaciones son verdaderas:
1. ∀ t, Circulo(t) ∨ Rojo(t)
2. ∃ t, Cuadrado(t) ∧ Rojo(t)
3. ∀ t, Cuadrado(t) ∧ Rojo(t)
4. ∀ t, Triangulo(t) ∨ Rojo(t)
5. ∃ t, Cuadrado(t) ∧ Azul(t)
Logica de Primer Orden: Logica de Predicados– p.7/21
Con los predicados y la figura generamos la tabla:Azul Rojo Triangulo Cuadrado Circulo
a T F T F F
b T F T F F
c F T F F T
d F T F T F
e F T F T F
f F T F T F
g F T F F T
Logica de Primer Orden: Logica de Predicados– p.8/21
Para la afirmación:
∀ t, Circulo(t) ∨ Rojo(t)
Azul Rojo Triangulo Cuadrado Circulo Circulo ∨ Rojo
a T F T F F F
b T F T F F F
c F T F F T T
d F T F T F T
e F T F T F T
f F T F T F T
g F T F F T T
Logica de Primer Orden: Logica de Predicados– p.9/21
Para la afirmación:
∀ t, Circulo(t) ∨ Rojo(t)
Azul Rojo Triangulo Cuadrado Circulo Circulo ∨ Rojo
a T F T F F F
b T F T F F F
c F T F F T T
d F T F T F T
e F T F T F T
f F T F T F T
g F T F F T T
La afirmación es falsa
Logica de Primer Orden: Logica de Predicados– p.9/21
Para la afirmación:
∀ t, Circulo(t) ∨ Rojo(t)
Azul Rojo Triangulo Cuadrado Circulo Circulo ∨ Rojo
a T F T F F F
b T F T F F F
c F T F F T T
d F T F T F T
e F T F T F T
f F T F T F T
g F T F F T T
La afirmación es falsa : a y b son contraejemplos.
Logica de Primer Orden: Logica de Predicados– p.9/21
Para la afirmación:
∃ t, Cuadrado(t) ∧ Rojo(t)
Azul Rojo Triangulo Cuadrado Circulo Cuadrado ∧ Rojo
a T F T F F F
b T F T F F F
c F T F F T F
d F T F T F T
e F T F T F T
f F T F T F T
g F T F F T F
Logica de Primer Orden: Logica de Predicados– p.10/21
Para la afirmación:
∃ t, Cuadrado(t) ∧ Rojo(t)
Azul Rojo Triangulo Cuadrado Circulo Cuadrado ∧ Rojo
a T F T F F F
b T F T F F F
c F T F F T F
d F T F T F T
e F T F T F T
f F T F T F T
g F T F F T F
La afirmación es cierta
Logica de Primer Orden: Logica de Predicados– p.10/21
Para la afirmación:
∃ t, Cuadrado(t) ∧ Rojo(t)
Azul Rojo Triangulo Cuadrado Circulo Cuadrado ∧ Rojo
a T F T F F F
b T F T F F F
c F T F F T F
d F T F T F T
e F T F T F T
f F T F T F T
g F T F F T F
La afirmación es cierta : d, e y f son ejemplos.
Logica de Primer Orden: Logica de Predicados– p.10/21
Para la afirmación:
∀ t, Cuadrado(t) ∧ Rojo(t)
Azul Rojo Triangulo Cuadrado Circulo Cuadrado ∧ Rojo
a T F T F F F
b T F T F F F
c F T F F T F
d F T F T F T
e F T F T F T
f F T F T F T
g F T F F T F
Logica de Primer Orden: Logica de Predicados– p.11/21
Para la afirmación:
∀ t, Cuadrado(t) ∧ Rojo(t)
Azul Rojo Triangulo Cuadrado Circulo Cuadrado ∧ Rojo
a T F T F F F
b T F T F F F
c F T F F T F
d F T F T F T
e F T F T F T
f F T F T F T
g F T F F T F
La afirmación es falsa
Logica de Primer Orden: Logica de Predicados– p.11/21
Para la afirmación:
∀ t, Cuadrado(t) ∧ Rojo(t)
Azul Rojo Triangulo Cuadrado Circulo Cuadrado ∧ Rojo
a T F T F F F
b T F T F F F
c F T F F T F
d F T F T F T
e F T F T F T
f F T F T F T
g F T F F T F
La afirmación es falsa : a, b, c y g son contraejemplos.
Logica de Primer Orden: Logica de Predicados– p.11/21
Para la afirmación:
∀ t, Triangulo(t) ∨ Rojo(t)
Azul Rojo Triangulo Cuadrado Circulo Triangulo ∨ Rojo
a T F T F F T
b T F T F F T
c F T F F T T
d F T F T F T
e F T F T F T
f F T F T F T
g F T F F T T
Logica de Primer Orden: Logica de Predicados– p.12/21
Para la afirmación:
∀ t, Triangulo(t) ∨ Rojo(t)
Azul Rojo Triangulo Cuadrado Circulo Triangulo ∨ Rojo
a T F T F F T
b T F T F F T
c F T F F T T
d F T F T F T
e F T F T F T
f F T F T F T
g F T F F T T
La afirmación es cierta.
Logica de Primer Orden: Logica de Predicados– p.12/21
Para la afirmación:
∃ t, Cuadrado(t) ∧ Azul(t)
Azul Rojo Triangulo Cuadrado Circulo Cuadrado ∧ Azul
a T F T F F F
b T F T F F F
c F T F F T F
d F T F T F F
e F T F T F F
f F T F T F F
g F T F F T F
Logica de Primer Orden: Logica de Predicados– p.13/21
Para la afirmación:
∃ t, Cuadrado(t) ∧ Azul(t)
Azul Rojo Triangulo Cuadrado Circulo Cuadrado ∧ Azul
a T F T F F F
b T F T F F F
c F T F F T F
d F T F T F F
e F T F T F F
f F T F T F F
g F T F F T F
La afirmación es falsa.
Logica de Primer Orden: Logica de Predicados– p.13/21
Ejemplo
Considere los siguientes datos:
Nombre Carrera Edad Hobby
Juan ITEC 21 Leer
María IMA 20 Música
Tomás IIS 23 Futbol
Lalo LATI 22 Anime
Luis IFI 21 Leer
Soledad LCC 24 Futbol
Logica de Primer Orden: Logica de Predicados– p.14/21
Ejemplo
Considere los siguientes datos:
Nombre Carrera Edad Hobby
Juan ITEC 21 Leer
María IMA 20 Música
Tomás IIS 23 Futbol
Lalo LATI 22 Anime
Luis IFI 21 Leer
Soledad LCC 24 Futbol
Nuestro dominio consiste de las personas
Juan, María, Tomás, Lalo, Luis, y Soledad.
Logica de Primer Orden: Logica de Predicados– p.14/21
Ejemplo
Considere los siguientes datos:
Nombre Carrera Edad Hobby
Juan ITEC 21 Leer
María IMA 20 Música
Tomás IIS 23 Futbol
Lalo LATI 22 Anime
Luis IFI 21 Leer
Soledad LCC 24 Futbol
Nuestro dominio consiste de las personas
Juan, María, Tomás, Lalo, Luis, y Soledad.Indique cuáles afirmaciones son verdaderas:
1. ∃x, x es menor de 19 años.
2. ∃x, x tiene como hobby el correr.
3. ∀x, x tiene como hobby leer o x eshombre.
4. ∀x, si x tiene como hobby la músicaentonces x es mujer.
5. ∃x, x tiene como carrera Letras.
Logica de Primer Orden: Logica de Predicados– p.14/21
De acuerdo a las preguntas, en este ejemplo conviene defi-
nir los predicados:M19(t) = t tiene menos de 19 años.
Co(t) = t tiene como hobby correr.Leer(t) = t tiene como hobby leer.Mus(t) = t tiene como hobby la música.
H(t) = t es un hombre.M(t) = t es un mujer.
Letras(t) = t tiene como carrera Letras.
Logica de Primer Orden: Logica de Predicados– p.15/21
De acuerdo a los predicados, tendríamos la siguiente tabla:M19 C Leer Mus H M Letras
Juan F F T F T F F
María F F F T F T F
Tomás F F F F T F F
Lalo F F F F T F F
Luis F F T F T F F
Soledad F F F F F T F
Logica de Primer Orden: Logica de Predicados– p.16/21
De acuerdo a los predicados, tendríamos la siguiente tabla:M19 C Leer Mus H M Letras
Juan F F T F T F F
María F F F T F T F
Tomás F F F F T F F
Lalo F F F F T F F
Luis F F T F T F F
Soledad F F F F F T F
La afirmación ∃x, x es menor de 19 años es falsa.
Logica de Primer Orden: Logica de Predicados– p.16/21
De acuerdo a los predicados, tendríamos la siguiente tabla:M19 C Leer Mus H M Letras
Juan F F T F T F F
María F F F T F T F
Tomás F F F F T F F
Lalo F F F F T F F
Luis F F T F T F F
Soledad F F F F F T F
La afirmación ∃x, x tiene como carrera Letras es falsa.
Logica de Primer Orden: Logica de Predicados– p.16/21
De acuerdo a los predicados, tendríamos la siguiente tabla:M19 C Leer Mus H M Letras
Juan F F T F T F F
María F F F T F T F
Tomás F F F F T F F
Lalo F F F F T F F
Luis F F T F T F F
Soledad F F F F F T F
La afirmación ∃x, x tiene como hobyy correr es falsa.
Logica de Primer Orden: Logica de Predicados– p.16/21
Para la afirmación:
∀x, x tiene como hobby leer o x es hombre
M19 C Leer Mus H M Letras Leer ∨ H
Juan F F T F T F F T
María F F F T F T F F
Tomás F F F F T F F T
Lalo F F F F T F F T
Luis F F T F T F F T
Soledad F F F F F T F F
Logica de Primer Orden: Logica de Predicados– p.17/21
Para la afirmación:
∀x, x tiene como hobby leer o x es hombre
M19 C Leer Mus H M Letras Leer ∨ H
Juan F F T F T F F T
María F F F T F T F F
Tomás F F F F T F F T
Lalo F F F F T F F T
Luis F F T F T F F T
Soledad F F F F F T F F
Deducimos que es falsa
Logica de Primer Orden: Logica de Predicados– p.17/21
Para la afirmación:
∀x, x tiene como hobby leer o x es hombre
M19 C Leer Mus H M Letras Leer ∨ H
Juan F F T F T F F T
María F F F T F T F F
Tomás F F F F T F F T
Lalo F F F F T F F T
Luis F F T F T F F T
Soledad F F F F F T F F
Deducimos que es falsa : María y Soledad son los contrae-
jemplos.
Logica de Primer Orden: Logica de Predicados– p.17/21
Para la afirmación:
∀x, si x tiene como hobby la música, entonces x es mujer.
M19 C Leer Mus H M Letras Mus → M
Juan F F T F T F F T
María F F F T F T F T
Tomás F F F F T F F T
Lalo F F F F T F F T
Luis F F T F T F F T
Soledad F F F F F T F T
Logica de Primer Orden: Logica de Predicados– p.18/21
Para la afirmación:
∀x, si x tiene como hobby la música, entonces x es mujer.
M19 C Leer Mus H M Letras Mus → M
Juan F F T F T F F T
María F F F T F T F T
Tomás F F F F T F F T
Lalo F F F F T F F T
Luis F F T F T F F T
Soledad F F F F F T F T
Deducimos que es verdadera.
Logica de Primer Orden: Logica de Predicados– p.18/21
Para la afirmación:
∀x, si x tiene como hobby la música, entonces x es mujer.
M19 C Leer Mus H M Letras Mus → M
Juan F F T F T F F T
María F F F T F T F T
Tomás F F F F T F F T
Lalo F F F F T F F T
Luis F F T F T F F T
Soledad F F F F F T F T
Deducimos que es verdadera.
No te que la clave es que F → X es T.
Logica de Primer Orden: Logica de Predicados– p.18/21
Ejemplo
Sea P (x) el predicado con dominio los númeroreales:
x2 ≤ 10
Identifique cuáles opciones contienen afirmacionesverdaderas:1. P (−2)
2. P (−6)
3. P (1
2)
4. P (2)
5. P (−4)
Logica de Primer Orden: Logica de Predicados– p.19/21
Ejemplo
Sea P (x) el predicado con dominio los númeroreales:
x2 ≤ 10
Identifique cuáles opciones contienen afirmacionesverdaderas:1. P (−2) Verdadera: (−2)2 = 4 ≤ 10.
2. P (−6)
3. P (1
2)
4. P (2)
5. P (−4)
Logica de Primer Orden: Logica de Predicados– p.19/21
Ejemplo
Sea P (x) el predicado con dominio los númeroreales:
x2 ≤ 10
Identifique cuáles opciones contienen afirmacionesverdaderas:1. P (−2) Verdadera: (−2)2 = 4 ≤ 10.
2. P (−6) Falsa: (−6)2 = 36 6≤ 10.
3. P (1
2)
4. P (2)
5. P (−4)
Logica de Primer Orden: Logica de Predicados– p.19/21
Ejemplo
Sea P (x) el predicado con dominio los númeroreales:
x2 ≤ 10
Identifique cuáles opciones contienen afirmacionesverdaderas:1. P (−2) Verdadera: (−2)2 = 4 ≤ 10.
2. P (−6) Falsa: (−6)2 = 36 6≤ 10.
3. P (1
2) Verdadera: (1/2)2 = 1/4 ≤ 10.
4. P (2)
5. P (−4)
Logica de Primer Orden: Logica de Predicados– p.19/21
Ejemplo
Sea P (x) el predicado con dominio los númeroreales:
x2 ≤ 10
Identifique cuáles opciones contienen afirmacionesverdaderas:1. P (−2) Verdadera: (−2)2 = 4 ≤ 10.
2. P (−6) Falsa: (−6)2 = 36 6≤ 10.
3. P (1
2) Verdadera: (1/2)2 = 1/4 ≤ 10.
4. P (2) Verdadera: (2)2 = 4 ≤ 10.
5. P (−4)
Logica de Primer Orden: Logica de Predicados– p.19/21
Ejemplo
Sea P (x) el predicado con dominio los númeroreales:
x2 ≤ 10
Identifique cuáles opciones contienen afirmacionesverdaderas:1. P (−2) Verdadera: (−2)2 = 4 ≤ 10.
2. P (−6) Falsa: (−6)2 = 36 6≤ 10.
3. P (1
2) Verdadera: (1/2)2 = 1/4 ≤ 10.
4. P (2) Verdadera: (2)2 = 4 ≤ 10.
5. P (−4) Falsa: (−4)2 = 16 6≤ 10.
Logica de Primer Orden: Logica de Predicados– p.19/21
Ejemplo
Sea P (x, y) el predicado: Si x < y, entoncesx2 < y2. Con dominio para x y para y todo elconjunto de los números reales. Identifique cuálesopciones contienen afirmaciones verdaderas:1. P (3, 2)
2. P (−2, 1)
3. P (−3, 1)
4. P (1
2, 1)
5. P (1,−3)
Logica de Primer Orden: Logica de Predicados– p.20/21
Ejemplo
Sea P (x, y) el predicado: Si x < y, entoncesx2 < y2. Con dominio para x y para y todo elconjunto de los números reales. Identifique cuálesopciones contienen afirmaciones verdaderas:1. P (3, 2) : (3 < 2) → (9 < 4): verdadera.2. P (−2, 1)
3. P (−3, 1)
4. P (1
2, 1)
5. P (1,−3)
Logica de Primer Orden: Logica de Predicados– p.20/21
Ejemplo
Sea P (x, y) el predicado: Si x < y, entoncesx2 < y2. Con dominio para x y para y todo elconjunto de los números reales. Identifique cuálesopciones contienen afirmaciones verdaderas:1. P (3, 2) : (3 < 2) → (9 < 4): verdadera.2. P (−2, 1) : (−2 < 1) → (4 < 1): falsa.3. P (−3, 1)
4. P (1
2, 1)
5. P (1,−3)
Logica de Primer Orden: Logica de Predicados– p.20/21
Ejemplo
Sea P (x, y) el predicado: Si x < y, entoncesx2 < y2. Con dominio para x y para y todo elconjunto de los números reales. Identifique cuálesopciones contienen afirmaciones verdaderas:1. P (3, 2) : (3 < 2) → (9 < 4): verdadera.2. P (−2, 1) : (−2 < 1) → (4 < 1): falsa.3. P (−3, 1) : (−3 < 1) → (9 < 1): falsa.
4. P (1
2, 1)
5. P (1,−3)
Logica de Primer Orden: Logica de Predicados– p.20/21
Ejemplo
Sea P (x, y) el predicado: Si x < y, entoncesx2 < y2. Con dominio para x y para y todo elconjunto de los números reales. Identifique cuálesopciones contienen afirmaciones verdaderas:1. P (3, 2) : (3 < 2) → (9 < 4): verdadera.2. P (−2, 1) : (−2 < 1) → (4 < 1): falsa.3. P (−3, 1) : (−3 < 1) → (9 < 1): falsa.
4. P (1
2, 1) : (1/2 < 1) → (1/4 < 1): cierta.
5. P (1,−3)
Logica de Primer Orden: Logica de Predicados– p.20/21
Ejemplo
Sea P (x, y) el predicado: Si x < y, entoncesx2 < y2. Con dominio para x y para y todo elconjunto de los números reales. Identifique cuálesopciones contienen afirmaciones verdaderas:1. P (3, 2) : (3 < 2) → (9 < 4): verdadera.2. P (−2, 1) : (−2 < 1) → (4 < 1): falsa.3. P (−3, 1) : (−3 < 1) → (9 < 1): falsa.
4. P (1
2, 1) : (1/2 < 1) → (1/4 < 1): cierta.
5. P (1,−3) : (1 < −3) → (1 < 9): cierta.
Logica de Primer Orden: Logica de Predicados– p.20/21
Ejemplo
Para la afirmación:
∀ político x, x es un buen conversador
Indique cuáles expresiones la describen:1. Entre todos los políticos, algunos son buenos
conversadores.
Logica de Primer Orden: Logica de Predicados– p.21/21
Ejemplo
Para la afirmación:
∀ político x, x es un buen conversador
Indique cuáles expresiones la describen:1. Entre todos los políticos, algunos son buenos
conversadores.2. Todo político es un buen conversador.
Logica de Primer Orden: Logica de Predicados– p.21/21
Ejemplo
Para la afirmación:
∀ político x, x es un buen conversador
Indique cuáles expresiones la describen:1. Entre todos los políticos, algunos son buenos
conversadores.2. Todo político es un buen conversador.3. Cada político es un buen conversador.
Logica de Primer Orden: Logica de Predicados– p.21/21
Ejemplo
Para la afirmación:
∀ político x, x es un buen conversador
Indique cuáles expresiones la describen:1. Entre todos los políticos, algunos son buenos
conversadores.2. Todo político es un buen conversador.3. Cada político es un buen conversador.4. Algunos buenos conversadores son políticos.
Logica de Primer Orden: Logica de Predicados– p.21/21
Ejemplo
Para la afirmación:
∀ político x, x es un buen conversador
Indique cuáles expresiones la describen:1. Entre todos los políticos, algunos son buenos
conversadores.2. Todo político es un buen conversador.3. Cada político es un buen conversador.4. Algunos buenos conversadores son políticos.5. Cualquier político es un buen conversador.
Logica de Primer Orden: Logica de Predicados– p.21/21