Logica de predicados
Los lenguajes formales, como el de la lógica proposicional, tienen un componente sintáctico y otro semántico. En esta lección veremos la sintaxis del lenguaje de la lógica proposicional. La sintaxis de la lógica proposicional está formada por una gramática y un alfabeto. El primero consta de símbolos, los cuales se dividen en tres categorías: signos lógicos, no lógicos y signos de puntuación. Estos últimos pueden ser prescindibles, los símbolos lógicos y los no lógicos son necesarios.
La gramática, por su parte consiste en un conjunto de reglas que nos permite generar fórmulas del lenguaje a partir de otras fórmulas. Para entender la noción de fórmula hemos de introducir previamente los símbolos del alfabeto del lenguaje de la lógica proposicional. Este consta de:
1. Letras proposicionales (símbolos no lógicos). No hay un número determinado. Para los fines de este curso de lógica, estipularemos las letras “p”, “q”, “r” y “s” como nuestras letras proposicionales.
2. Conectivas (símbolos lógicos). ̚ , →, ↔, ˄, ˅
3. Signos de puntuación. Paréntesis ( ).
De las conectivas, la primera se llama negación y es una conectiva monaria. El resto son conectivas binarias. A continuación veremos el nombre de cada una y cómo se leen.
“ ̚ “ se llama negación y se lee “no”
“→” se llama condicional y se lee “si…entonces”.
“↔” se llama bicondicional y se lee “si y solo si”.
“˄” se llama conjunción y se lee “y”.
“˅” se llama disyunción y se lee “o”.
Una estructura es una secuencia ordenada
M =<A, R1,…Rn, F1,…Fm, {ci| i ∈ I}>
tal que:
• A es un conjunto no vacío, ( Notacion: A = |M|)
• R1,…Rn son relaciones sobre A (n≥0)
• F1,…Fm son funciones en A (m≥0)
• ci(i∈I) son elementos distinguidos de A
Ejemplos:
– < N,Par,≤,+,*, 0,1> naturales
– <N,< > CPO de los naturales
– < Z, +, -, 0 > grupo de los enteros
Alfabeto
Definición 1: El alfabeto de la lógica de predicados estará formado por los
siguientes conjuntos simbólicos:
•Conjunto de Símbolos de Variables (VAR): Es un conjunto de las últimas letras
del alfabeto en minúsculas. Se utilizan subíndices, por ejemplo:
•Conjunto de símbolos de Constantes (CONS): Este conjunto lo forman las
primeras letras del alfabeto en minúsculas, también utilizaremos subíndices:
•Conjunto de letras de función (FUNC): Representaremos a este conjunto por las
letras f,g,h,L. Incluimos subíndices para poder diferenciar las funciones:
•Conjunto de letras de Predicado (PRED): Se representan mediante letras
mayúsculas,
Símbolos de conectivas: ¬ = Negación
∨= Conectiva "o"
∧ = Conectiva "y"
→ = implicación
↔ = Doble implicación o equivalencia
Cuantificadores:
∃=existencial
∀=Universal
Signos de puntuación: Paréntesis ( ) y coma.
Definición 2: Término es una cadena de símbolos que representan a objetos y
dependen de las siguientes reglas:
•"Toda variable o constante individual es un término."
•"Si t1,t2,L,tn son términos y f
n
es una función de aridad n entonces f
n
(t1,t2,L,tn) es
un término"
•Todos los términos posibles se generan aplicando únicamente las dos reglas
anteriores Cualquier término lo generamos a partir de las dos reglas dichas
anteriormente.
Definición 3: Un átomo es una cadena de símbolos de la forma:
donde P
n
es un predicado de aridad n y sin
términos
Definición 4: Definimos el conjunto de fórmulas bien formadas (fbf):
1. "Todo átomo (P,Q,R,S,...) es una fórmula bien formada. (Se denominará fórmula
atómica)."
2. "Si es una fórmula bien formada, ¬ A también lo es.
3. Si y son fórmulas bien formadas, también lo son (A ∧ B), (A ∨ B) y (A ⇒ B).
4. No hay más fórmulas."
Creación fbf
Una FBF es una tautología si toma el valor de verdad bajo cada una de las posibles asignaciones de valores de verdad a las variables de enunciado que aparecen en ella.
a una FBF en la que intervengan n variables de enunciado diferente (siendo n cualquier número natural) le corresponderá una función de verdad de n argumentos, y la tabla de verdad tendrá 2n filas, una para cada una de las posibles combinaciones de valores de verdad para las variables de enunciado. Nótese además que existen funciones de verdad distintas de n argumentos, que corresponden a las maneras posibles de disponer los 1’s y los 0’s en la última columna de una tabla de verdad de 2n filas. Esta claro que el número de formas enunciativas que se pueden construir utilizando n variables de enunciados es infinito, así que formas enunciativas distintas pueden corresponder a una misma función de verdad.
Las tautologías son lógicamente necesarias. Las contradicciones son lógicamente imposibles. Las contingencias son lógicamente posibles, pero se clasifican en:
a) posibles o imposibles empíricamente y
b) posibles o imposibles técnicamente. Lo empíricamente imposible en el pasado puede llegar a ser posible en el futuro, dependiendo del desarrollo de la ciencia.
Ejemplos de formalización
1. Todos los actores son famosos.
a) D = las personas
A(-): - es actor
F(-): - es famoso
∀x[A(x) −→ F(x)]
b) D = los actores
F(-): - es famoso
∀xF(x)
2. Algunos padres son responsables.
a) D = las personas
P(-): - es padre
R(-): - es responsable
∃x[P(x) ∧ R(x)]
b) D = los padres
R(-): - es responsable
∃xR(x)
3. Todos los miembros son padres o son maestros.
a) D = las personas
M(-): - es miembro
P(-): - es padre
MA(-): - es maestro
∀x[M(x) −→ P(x) ∨ MA(x)]
b) D = los miembros
P(-): - es padre
MA(-): - es maestro
∀x[P(x) ∨ MA(x)]
4. Algunos pol´ıticos son incompetentes o son corruptos.
a) D = las personas
P(-): - es pol´ıtico
I(-): - es incompetente
C(-): - es corrupto
∃x[P(x) ∧ (I(x) ∨ C(x))]
∃x[(P(x) ∧ I(x)) ∨ (P(x) ∧ C(x))]
∃x¬[P(x) −→ ¬(I(x) ∨ C(x))]
b) D = los pol´ıticos
I(-): - es incompetente
C(-): - es corrupto
∃x[I(x) ∨ C(x)]
5. Las manzanas y los pl´atanos son nutritivos.
a) D = las frutas
M(-): - es manzanza
P(-): - es pl´atano
N(-): - es nutritivo
∀x[M(x) ∨ P(x) −→ N(x)]
∀x[(M(x) −→ N(x)) ∧ (P(x) −→ N(x))]
b) D1 = las manzanas (x)
D2 = los pl´atanos (y)
N(-): - es nutritivo
∀xN(x) ∧ ∀yN(y)
6. Algunas frutas y verduras son nutritivas.
a) D = los alimentos
F(-): - es fruta
V(-): - es verdura
N(-): - es nutritivo
∃x∃y[F(x) ∧ V (y) ∧ N(x) ∧ N(y)]
∃x[F(x) ∧ N(x)] ∧ ∃x[V (x) ∧ N(x)]
∃x[(F(x) ∨ V (x)) ∧ N(x)]
b) D1 = las frutas (x)
D2 = las verduras (y)
N(-): - es nutritivo
∃xN(x) ∧ ∃yN(y)
7. Si algo anda mal, entonces todos se quejan.
D1 = las cosas (x)
D2 = las personas (y)
M(-): - anda mal
2
Q(-): - se queja
∃xM(x) −→ ∀yQ(y)
8. Luis es Guapo.
D = las personas
G(-): - es guapo
G(l)
9. a) Pedro es amigo de todos.
b) Algunos son amigos de Pedro.
c) Todos son amigos de todos.
D = las personas
A(-,-): - es amigo de -
a) ∀xA(p, x)
b) ∃xA(x, p)
c) ∀x∀yA(x, y)
10. S´olo los ejecutivos llevan cartera.
D = las personas
E(-): - es ejecutivo
C(-): - lleva cartera
∀x[C(x) −→ E(x)]
∀x[¬E(x) −→ ¬C(x)]
La gramática, por su parte consiste en un conjunto de reglas que nos permite generar fórmulas del lenguaje a partir de otras fórmulas. Para entender la noción de fórmula hemos de introducir previamente los símbolos del alfabeto del lenguaje de la lógica proposicional. Este consta de:
1. Letras proposicionales (símbolos no lógicos). No hay un número determinado. Para los fines de este curso de lógica, estipularemos las letras “p”, “q”, “r” y “s” como nuestras letras proposicionales.
2. Conectivas (símbolos lógicos). ̚ , →, ↔, ˄, ˅
3. Signos de puntuación. Paréntesis ( ).
De las conectivas, la primera se llama negación y es una conectiva monaria. El resto son conectivas binarias. A continuación veremos el nombre de cada una y cómo se leen.
“ ̚ “ se llama negación y se lee “no”
“→” se llama condicional y se lee “si…entonces”.
“↔” se llama bicondicional y se lee “si y solo si”.
“˄” se llama conjunción y se lee “y”.
“˅” se llama disyunción y se lee “o”.
Una estructura es una secuencia ordenada
M =<A, R1,…Rn, F1,…Fm, {ci| i ∈ I}>
tal que:
• A es un conjunto no vacío, ( Notacion: A = |M|)
• R1,…Rn son relaciones sobre A (n≥0)
• F1,…Fm son funciones en A (m≥0)
• ci(i∈I) son elementos distinguidos de A
Ejemplos:
– < N,Par,≤,+,*, 0,1> naturales
– <N,< > CPO de los naturales
– < Z, +, -, 0 > grupo de los enteros
Alfabeto
Definición 1: El alfabeto de la lógica de predicados estará formado por los
siguientes conjuntos simbólicos:
•Conjunto de Símbolos de Variables (VAR): Es un conjunto de las últimas letras
del alfabeto en minúsculas. Se utilizan subíndices, por ejemplo:
•Conjunto de símbolos de Constantes (CONS): Este conjunto lo forman las
primeras letras del alfabeto en minúsculas, también utilizaremos subíndices:
•Conjunto de letras de función (FUNC): Representaremos a este conjunto por las
letras f,g,h,L. Incluimos subíndices para poder diferenciar las funciones:
•Conjunto de letras de Predicado (PRED): Se representan mediante letras
mayúsculas,
Símbolos de conectivas: ¬ = Negación
∨= Conectiva "o"
∧ = Conectiva "y"
→ = implicación
↔ = Doble implicación o equivalencia
Cuantificadores:
∃=existencial
∀=Universal
Signos de puntuación: Paréntesis ( ) y coma.
Definición 2: Término es una cadena de símbolos que representan a objetos y
dependen de las siguientes reglas:
•"Toda variable o constante individual es un término."
•"Si t1,t2,L,tn son términos y f
n
es una función de aridad n entonces f
n
(t1,t2,L,tn) es
un término"
•Todos los términos posibles se generan aplicando únicamente las dos reglas
anteriores Cualquier término lo generamos a partir de las dos reglas dichas
anteriormente.
Definición 3: Un átomo es una cadena de símbolos de la forma:
donde P
n
es un predicado de aridad n y sin
términos
Definición 4: Definimos el conjunto de fórmulas bien formadas (fbf):
1. "Todo átomo (P,Q,R,S,...) es una fórmula bien formada. (Se denominará fórmula
atómica)."
2. "Si es una fórmula bien formada, ¬ A también lo es.
3. Si y son fórmulas bien formadas, también lo son (A ∧ B), (A ∨ B) y (A ⇒ B).
4. No hay más fórmulas."
Creación fbf
Una FBF es una tautología si toma el valor de verdad bajo cada una de las posibles asignaciones de valores de verdad a las variables de enunciado que aparecen en ella.
a una FBF en la que intervengan n variables de enunciado diferente (siendo n cualquier número natural) le corresponderá una función de verdad de n argumentos, y la tabla de verdad tendrá 2n filas, una para cada una de las posibles combinaciones de valores de verdad para las variables de enunciado. Nótese además que existen funciones de verdad distintas de n argumentos, que corresponden a las maneras posibles de disponer los 1’s y los 0’s en la última columna de una tabla de verdad de 2n filas. Esta claro que el número de formas enunciativas que se pueden construir utilizando n variables de enunciados es infinito, así que formas enunciativas distintas pueden corresponder a una misma función de verdad.
Las tautologías son lógicamente necesarias. Las contradicciones son lógicamente imposibles. Las contingencias son lógicamente posibles, pero se clasifican en:
a) posibles o imposibles empíricamente y
b) posibles o imposibles técnicamente. Lo empíricamente imposible en el pasado puede llegar a ser posible en el futuro, dependiendo del desarrollo de la ciencia.
Ejemplos de formalización
1. Todos los actores son famosos.
a) D = las personas
A(-): - es actor
F(-): - es famoso
∀x[A(x) −→ F(x)]
b) D = los actores
F(-): - es famoso
∀xF(x)
2. Algunos padres son responsables.
a) D = las personas
P(-): - es padre
R(-): - es responsable
∃x[P(x) ∧ R(x)]
b) D = los padres
R(-): - es responsable
∃xR(x)
3. Todos los miembros son padres o son maestros.
a) D = las personas
M(-): - es miembro
P(-): - es padre
MA(-): - es maestro
∀x[M(x) −→ P(x) ∨ MA(x)]
b) D = los miembros
P(-): - es padre
MA(-): - es maestro
∀x[P(x) ∨ MA(x)]
4. Algunos pol´ıticos son incompetentes o son corruptos.
a) D = las personas
P(-): - es pol´ıtico
I(-): - es incompetente
C(-): - es corrupto
∃x[P(x) ∧ (I(x) ∨ C(x))]
∃x[(P(x) ∧ I(x)) ∨ (P(x) ∧ C(x))]
∃x¬[P(x) −→ ¬(I(x) ∨ C(x))]
b) D = los pol´ıticos
I(-): - es incompetente
C(-): - es corrupto
∃x[I(x) ∨ C(x)]
5. Las manzanas y los pl´atanos son nutritivos.
a) D = las frutas
M(-): - es manzanza
P(-): - es pl´atano
N(-): - es nutritivo
∀x[M(x) ∨ P(x) −→ N(x)]
∀x[(M(x) −→ N(x)) ∧ (P(x) −→ N(x))]
b) D1 = las manzanas (x)
D2 = los pl´atanos (y)
N(-): - es nutritivo
∀xN(x) ∧ ∀yN(y)
6. Algunas frutas y verduras son nutritivas.
a) D = los alimentos
F(-): - es fruta
V(-): - es verdura
N(-): - es nutritivo
∃x∃y[F(x) ∧ V (y) ∧ N(x) ∧ N(y)]
∃x[F(x) ∧ N(x)] ∧ ∃x[V (x) ∧ N(x)]
∃x[(F(x) ∨ V (x)) ∧ N(x)]
b) D1 = las frutas (x)
D2 = las verduras (y)
N(-): - es nutritivo
∃xN(x) ∧ ∃yN(y)
7. Si algo anda mal, entonces todos se quejan.
D1 = las cosas (x)
D2 = las personas (y)
M(-): - anda mal
2
Q(-): - se queja
∃xM(x) −→ ∀yQ(y)
8. Luis es Guapo.
D = las personas
G(-): - es guapo
G(l)
9. a) Pedro es amigo de todos.
b) Algunos son amigos de Pedro.
c) Todos son amigos de todos.
D = las personas
A(-,-): - es amigo de -
a) ∀xA(p, x)
b) ∃xA(x, p)
c) ∀x∀yA(x, y)
10. S´olo los ejecutivos llevan cartera.
D = las personas
E(-): - es ejecutivo
C(-): - lleva cartera
∀x[C(x) −→ E(x)]
∀x[¬E(x) −→ ¬C(x)]
Comentarios
Publicar un comentario