Download Notas sobre Lógica Dr. JA Hernândezservîn

Notas sobre Lógica
Dr. J. A. Hernândezservîn
E-mail address: [email protected]
Índice general
Capítulo 1. Conjuntos
1.1. Teoría de conjuntos
1.2. Cardinalidad
1.3. Inducción Matematica
5
5
8
8
Capítulo 2. Algebra de Boole
2.1. Definiciones y propiedades
2.2. Formas canónicas y simplificación
11
11
13
Capítulo 3. Lógica Proposicional
3.1. Definición de Operadores Lógicos
3.2. Conectivas, Tablas y Funciones de Verdad
3.3. Equivalencia Lógica
3.4. Conjuntos adecuados de conectivas
3.5. Calculo de deducción natural,
3.6. Reglas De Inferencia
15
15
17
18
25
27
30
Capítulo 4. Lógica de predicados
4.1. Semántica
4.2. Teoría de modelos
4.3. Verdad Logica
4.4. Calculo axiomático
4.5. Propiedades formales
4.6. Deducción Natural
35
35
36
39
39
39
39
Capítulo 5. Otras lógicas
5.1. Multivalente
5.2. Difusa
5.3. Modal
5.4. Temporal
5.5. Intuicionista y no monótona
41
41
41
41
41
41
Bibliografía
43
Bibliografía
43
3
CHAPTER 0. ÍNDICE GENERAL
Apéndice. Apendice (Lógica y conjuntos)
.1. Lógica de proposiciones y conjuntos
4
45
45
Capítulo 1
Conjuntos
1.1.
1.1.1.
Teoría de conjuntos
Definición de conjuntos.
Definition 1. Un conjunto es una colección de objetos.
Un conjunto sse denotará por letras mayusculas, A, B, C, etc. Para
indicar la pertenencia se escribe e ∈ A, se lee “e pertenece al conjunto
A”. Para denotar el hecho contrario se escribe e ∈
/ A, y se lee “e no
pertenece al conjunto A”. El conjunto que no contiene elementos se
llama conjunto vacio y se denota ∅. Los conjuntos se describen mediante
un listado de sus elementos entre corchetes.
Definition 2. Un conjunto se puede describir mediante una lista
o asociando los elementos mediante una propiedad.
Example. El conjunto de las letras minisculas del alfabeto es {a, b, c, ..., z}.
O mediante una propiedad y se escribe de la siguiente forma
{x|x es una letra miniscula del alfabeto}.
El conjunto de los numeros naturales N = {0, 1, 2, ...}.
+
El segmento de numeros naturales N+
k = {1, 2, ..., k}, entonces N0 =
∅.
El conjunto de los numeros enteros Z = {..., −2, −1, 0, 1, 2, ...}.
Por último podemos enunciar el conjunto de los números racionales,
reales y complejos, esto es Q, R, y C respectivamente. En particular
el conjunto de numeros racionales se puede expresar con la siguiente
propiedad
o
n
m
Q = r|r = , m, n ∈ Z .
n
Deigual forma se puede describir el conjunto de numeros complejos
mediante una propiedad,
C = z|z = a + ib, a, b ∈ R y i2 = −1 .
De que manera se puede describir R?
5
Fac. Ingeniería, UAEM
Lógica
Definition 3. Se dice que S es un subconjunto de un conjunto C,
y se denota por S ⊆ C, si todo elemento de S esta en C. Para describir
lo contrario escribimos S * C, lo cual significa que ningun elemento de
S pertenece a C.
Example. Por ejemplo, N ⊆ Z ⊆ Q ⊆ R ⊆ C.
Puesto que Z contiene alos numeros positivos enteros incluyendo el
cero. Ademas cualquier n ∈ Z , se puede expresar como n = n1 ∈ Q,
pues n1 cumple la propiedad en la definición del conjunto de racionales. De manera analoga se verifica R ⊆ C. Cualquier r ∈ R se puede
expresar como r = a + i · 0 ∈ C
Definition 4. (Complemento) Llamaremos complemento de un
conjunto A, denotado Ac , a los elementos del conjunto universal que
no estan en A.
(Union) Se llama union de A, B, denotado por A ∪ B,
al conjunto de elementos que pertenecen a A o B, o a
ambos.
(Intersección) Se llama interssección de A y B, denotado por A ∩ B, al conjunto de elementos que pertenecen a A y B,
A ∩ B = {a|a ∈ A, y a ∈ B} .
(Diferencia) Se llama diferencia del conjunto A con respecto al conjunto B, denotado por A−B, a los elementos
de A que no pertenecen a B
A − B = {a ∈ A|a ∈
/ B} .
(Producto Cruz) Si A, B son conjuntos, el producto
cruz, denotado por A × B, es el conjunto de las parejas
ordenadas (a, b) tales que a ∈ A y b ∈ B
A × B = {(a, b)|a ∈ A, b ∈ B}
Si A1 , A2 , ..., An son conjuntos entonces
A1 × · · · × An = {(a1 , ..., an )|ai ∈ Ai }
Example. Ejemplos de complementos. Considerar el conjunto universal U = {x|x es una letra miniscula del alfabeto ingles}, sea A =
{a, b, s, t} ⊆ U , entonces Ac = {c, f, g, h, i, j.k, l, m, n, o, p, q, r, u, v, z, w} ⊆
U . La letra ñ∈ U ?
Ahora si U = {x|x es una palabra del idioma ingles }, entonces pronto ∈
U?
Dr. J. A. Hernández
6
Fac. Ingeniería, UAEM
Lógica
Sea A = {a, b, c}, B = {c, f, g, h, i}, entonces A∪B = {a, b, c, f, g, h, i}.
Para la interseccion tenemos que A ∩ B = {c}.
Ahora, supongamos que A = R y B = R entonces tenemos que
A × B es el conjunto
C = R × R = {(x, y)|x, y ∈ R} .
El cual corresponde al plano cartesiano. Ahora definamos los siguientes subconjuntos de C,
P = (x, y) ∈ R × R|y = x2
Q = {(x, y) ∈ R × R|y = x}
S = {(x, y) ∈ R × R|y = 1}
por lo tanto tenemos que
P ∩Q
P ∩S
Q∩S
Sc
=
=
=
=
{(0, 0)}
{(−1, 1), (1, 1)}
{(1, 1)}
{(x, y) ∈ R × R|y 6= 1}
Exercise 5. Cual es el producto cruz de Z con el mismo?. Hacer un
diagrama. Es N×N subconjunto de Z×Z? Si la respuesta es afirmativa
identificar en el diagrama tal subconjunto.
1.1.2.
Diagramas de Venn.
1.1.3.
Relaciones y Funciones.
Definition 6. Una relación sobre los conjuntos A1 , ..., An es un
subconjunto R de A1 × · · · × An . Dada una relacion n−aria se usa la
notación (a1 , ..., an ) ∈ R o para el caso n = 2, se escribe aRb.
Example. Sea A1 = {0, 1, 2}, A2 = {a, b} y sea R = {(0, a), (0, b), (1, b), (2, a)}
la realación entre estos dos conjuntos. Por ejemplo, (1, b) ∈ R pero
(1, a) ∈
/ R.
Definition 7. Una función f : A → B es una relación f ⊆ A × B
que verifica las siguientes condiciones
1. Para todo a ∈ A existe un b ∈ B tal que (a, b) ∈ f y
2. Si (a, b), (a, b0 ) ∈ f entonces b = b0 .
Si C ⊆ A , Imf = {f (a)|a ∈ C} ⊆ B se denomina conjunto imagen de
f . C = Domf , se denomina domino de f y B se llama codominio. El
rango de f es el conjunto imagen f (A).
Dr. J. A. Hernández
7
Fac. Ingeniería, UAEM
Lógica
Figura 1.1.1. Figura
Example. La relación del ejemplo anterior no es función porque
0Rb y 0Rb pero a 6= b.
Sea la función f : Z → Z, tal que f (n) = n2 , f es una función
porque a cada elemento del dominio le corresponde un elemento del
codominio. El rango de f es el conjunto de naturales que son cuadrados
perfectos.
Definition 8. Dados g : A → B y f : B → C , se define la
composición f ◦ g : A → C, de tal forma que (f ◦ g)(x) = f (g(x)). La
composición es asociativa esto es g : A → B, f : B → C y h : C → D
, entonces h ◦ (f ◦ g) = (h ◦ f ) ◦ g.
Example. Dadas las funciones f : Z → Z y g : Z → Z, definidas
por f = 2x + 2 y g = 3x − 2, entonces
f ◦ g = f (g(x)) = 2(3x − 2) + 2 = 6x − 2
(g ◦ f )(x) = g(f ) = 3(2x + 2) − 2 = 6x − 4
Definition 9. Una función f : A → B es inyectiva si para todo
a, a ∈ A f (a) = f (a0 ) tenemos que a = a0 .
Se dice f sobreyectiva si para todo b ∈ B existe un a ∈ A tal que
f (a) = b.
Y finalmente f se dice biyectiva si ambas, inyectiva y sobreyectiva.
0
1.2.
Cardinalidad
1.2.1.
Cardinalidad de los numeros Naturales.
1.2.2.
Cardinalidad de un conjunto.
1.2.3.
Cardinalidad de los Racionales.
1.3.
Inducción Matematica
1.3.1. Inducción Matematica. Supongamos que p(x) es una
propiedad matemática de tal forma que p(x), significa que p se cumple
para x. Entonces el principio de inducción matemática afirma que:
(
i) p(0)
es verdaero
Si
ii) Para toda k > 0, p(k − 1) implica p(k)
entonces p(n) es verdadero para toda n.
Ai que la prueba por inducción conmsiste de lo siguiente:
Dr. J. A. Hernández
8
Fac. Ingeniería, UAEM
Lógica
1. Probar el caso base, esto es se cumple i).
2. Probar caso inductivo, esto es se cumple ii). Para
ello considerar k > 0 arbitrario y suponer que se cumple p(k − 1) (hipotesis de inducción), una vez hecho este
supuesto deducir p(k).
Example 10. Sea la p la siguiente propiedad matemática
p(n) :
n
X
l=1
l=
n(n + 1)
.
2
Demostrar usando inducción matemática que p(n) es cierto para
cualquier n positivo.
Demostración. Caso base (n = 1).
p(1) es verdadero, puesto que
1
X
l=1
l=
1(1 + 1)
=1
2
Caso inductivo. Sea k > 1 y supongamos que p(k − 1) es verdadero, esto es
k−1
X
l=1
l=
(k − 1)k
Hipotesis de Inducción (H.I.)
2
Ahora para demostrar que p(k) es verdadero procedemos de la siguiente manera
!
k
k−1
X
X
l =
l +k
l=1
l=1
k(k − 1)
+ k, Por H.I.
2
k−1
= k
+1
2
k+1
= k
2
k(k + 1)
=
2
Por tanto se ha demostrado el caso inductivo, p(k − 1) implica p(k).
Por el principio de inducción se concluye que p(n) es verdadero para
todo n ∈ N.
=
Dr. J. A. Hernández
9
Lógica
Fac. Ingeniería, UAEM
1.3.2. Resolución de propociones lógicas mediante la inducción Matemática.
Dr. J. A. Hernández
10
Capítulo 2
Algebra de Boole
2.1.
Definiciones y propiedades
Un álgebra de Boole es un conjunto con dos operaciones binarias +
y ·, dos elementos distintos 0 y 1 y una operación unitaria 0 , llamada
complemento. El conjunto B es algebra Booleana si se cumplen los
siguientes axiomas
(
a+0=a
[B1]: Leyes de Identidad
a·1=a
(
a+b=b+a
[B2]: Conmutatividad
a·b=b·a
(
(a + b) + c = a + (b + c)
[B3]: Asociatividad
(ab)c = a(bc)
(
a + (bc) = (a + b)(a + c)
[B4]: Distributividad
a(b + c) = (ab) + (ac)
(
a + a0 = 1
[B5]: Complementos
aa0 = 0
Ahora: si B = {0,1} las operaciones se pueden definir sobre este
conjunto. La Algebra se puede escribir de la siguiente forma
A = {B, +, ·,0 , 0, 1}.
2.1.1. Propiedades del Algebra de Boole. Las siguientes propiedades aplican para cualquier algebra de Boole que cumpla con los
axiomas definidos en sección Section 2.1. Por lo que la demostración se
seguirá a partir de tales axiomas.
2.1.1.1. Idempotencia. Si a es un elemento de B entonces se cumple las siguientes relaciones
(
a+a=a
(2.1.1)
Idempotencia
aa = a
Las relaciones (2.1.1) se pueden demostrar usando los axiomas B1−
B5 ya definidos en seccion Section 2.1
11
Fac. Ingeniería, UAEM
Lógica
2.1.1.2.
Dominancia.
(
a+1=a
Dominancia
a0 = 0
2.1.1.3. Absorción. Para cualesquiera a, b elementos de B se cumple la siguiente propiedad
2.1.1.4.
(
a(a + b) = a
Absorción
a + ab = a
.
2.1.1.5. Leyes de De Morgan. Para cualquier elemento a, b se
cumplen las leyes de De Morgan
(
(a + b)0 = a0 b0
(ab)0 = a0 + b0
Demostración. Observación: Si y es el complemento de x, por
definición se debe demostrarse que x + y = 1 y xy = 0.
2.1.1.6. Involución. La involución es la aplicación de operador
unitario 0 asi mismo.
n
(a0 )0 = a Para todo a ∈ B
Demostración. La demostración se sigue de manera analoga a
las propiedades anteriores.
a + a0 = 1, por B5
aa0 = 0, por B5
es decir a0 es el complemento de a
2.1.1.7. Relación del 0 y el 1. La siguietnes relaciones se cumplen
para los elementos 0 y 1.
00 = 1
10 = 0
2.1.2. Principio de Dualidad. El principio de dualidad consiste en tener una fórmula arbitraria en una Algebra de Boole y mediante
la inversion de operadores la fórmula seguierá siendo válida. Esto es,
de manera precisa:
Definition 11. El dual de cualquier enunciado en un álgebra de
Booleana se obtiene intercambiando los operadores + y • y los elementos 0 y 1 en el enunciado original.
Dr. J. A. Hernández
12
Fac. Ingeniería, UAEM
Lógica
Example 12. Si se tiene el siguiente eneunciado a + a(b + 1) = a
entonces el dual sería a • (a + b • 0) = a.
2.1.3. Funciones Booleanas. Las expresiones Booleanas de las
cuales consta las funciones se construyen de la siguiente forma
1. 0, 1, x1 , x2 , ....xn
2. Si E1 y E2 son expresiones boolenas entonces E1 + E2 y E1 E2
son expresiones booleanas.
3. Si E es una expresión booleana, E 0 también es una expresión
booleana.
Una función Boolena se define del conjunto B n = {x1 , ...., xn } al conjunto B = {0, 1}. Una función definida sobre B n es de grado n. Las
funciones booleanas tienen una representación tabular de la siguiente
forma, por ejemplo, considerar la siguiente función f (a, b, c) = ab + c0
la cual tiene la siguiente representación en forma tabular
a
1
1
1
1
0
0
0
0
2.2.
b
1
1
0
0
1
1
0
0
c ab c0 ab + c0
1 1 0
0 1
1 0 0
0 0
1 0 0
0 0
1 0 0
0 0
Formas canónicas y simplificación
Definition 13. Fromas normal disyuntiva y conjuntiva.
Maxitérmino:: Suma de literals booleanas apareciendo solamente una vez, e.g. a + b, a0 + b, a + b0 , etc.
Minitérmino:: Un minitérmino de n variables es un producto
booleano de las n literales (varaibles complemento) en las cuales
cada literal aparece exactamente una vez, e.g. a0 b, ab0 y a0 b0 .
FND:: Una función en forma disyuntiva es una expansión suma
de minitérminos.
FNC:: Una función en forma conjuntiva es una expansión producto de maxitérminos.
2.2.1.
Expresión de una función en forma canónica.
Dr. J. A. Hernández
13
Fac. Ingeniería, UAEM
Lógica
x
1
1
1
1
0
0
0
0
y
1
1
0
0
1
1
0
0
z
1
0
1
0
1
0
1
0
f
0
1
1
1
0
0
0
0
Cuadro 3. Función f = xyz 0 + xy 0 z + xy 0 z 0
2.2.1.1. Tablas de verdad. Si la función f (x, y, z) se representa
mediante una tabla de verdad, entonces f se expresa en FND como sigue: El método se descibe mediante un ejemplo. Considerar la siguiente
función booleana
Los mitérminos se construyen de la siguiente forma, se toman los
valores de la función distintos del cero y se escriben las literales (sin
complemento) donde aparece 1, esto es, en el segundo renglón el minitérmino que corresponde es xyz 0 y de manera analoga para el tercero y
el cuarto xy 0 z y xy 0 z 0 . Por lo que la función f tiene la representación
xyz 0 + xy 0 z + xy 0 z 0 .
Ahora, la FNC se obtiene de la siguiente forma: Se toman los valores
de f distintos a 1, se escribe el complemento de las literales con valor
de 1 y se dejan sin cambio las literales con valor de 0. De manera
especifíca, f tendría la siguiente representación
(x0 + y + z 0 )(x + y 0 + z 0 )(x + y + z 0 )(x + y + z).
2.2.1.2.
Método Algebraico.
Dr. J. A. Hernández
14
Capítulo 3
Lógica Proposicional
3.1.
Definición de Operadores Lógicos
Para definir la sintáxis de la lógica se usa un vocabulario de símbolos primitivos y algunas reglas de formación de palabras. El conjunto
de símbolos de proposición Σ serán las letras minisculas del alfabeto.
Por ejemplo,
1. p, q, ... son símbolos de proposición.
2. Los símbolos lógicos son:
a) Los símbolos 0, 1 que denotan falso o verdadero respectivamente.
b) El conectivo ¬, que denota la negación
c) Las siguientes conectivas binarias, → (implicación), ∨ (disyunción), ∧ (conjunción) y ←→ (bicondicional).
3. Los símbolos auxiliares, ”(” y ”)”.
4. De está forma de construye el alfabeto AΣ basado en Σ. La
siguiente tabla muestra una explicación más detallada de las
primeras combinaciones que se pueden construir con el alfabeto
AΣ .
¬p
p∧q
p∨q
p→q
p↔q
p3q
Negación de p
pyq
poq
Si p, entonces q
p si y sólo si q
p tal que q
El condicional q → p se llama converso de p → q y ¬q → ¬p se llama
contraposición de p → q.
Ejemplos de uso de la notación y simbología definida en la tabla
anterior.
3.1.1. Fórmulas bien formadas. De todas las combinaciones
de símbolos que se pueden formar usando el alfabeto AΣ , se definen
mediante las siguientes reglas inductivas.
15
Fac. Ingeniería, UAEM
Lógica
[
[¬
[∧
[∨
[→
[↔
]
]
]
]
]
]
0, 1 y p, para toda p ∈ Σ son fórmulas bien formadas
Si φ es una fórmula entonces ¬φ es una fórmula.
Si φ, ψ es una fórmula entonces φ ∧ ψ es una fórmula.
Si φ, ψ es una fórmula entonces φ ∨ ψ es una fórmula.
Si φ, ψ es una fórmula entonces φ → ψ es una fórmula.
Si φ, ψ es una fórmula entonces φ ↔ ψ es una fórmula.
Se usaran las letras α, β,... del alfabeto griego, comjuntamente con
A, B,.... para denotar fórmulas bien formadas (fbf). El conjunto de
fórmulas se denotará por LΣ .
Example. 1. Para toda x existe un y tal que x < y. Expresado en
simbolos lógicos tendriamos
(∀x)(∃y)(x < y)
o alternativamente
(∀x)(∃y) 3 x < y
los parentesis se pueden reemplazar por el simbolo 3 .
Para toda e existe un d tal que para todo y, si |x − y| < d entonces
|f (x) − f (y)| < e. Expresado lógicamente quedaria
(∀e) (∃b) (|x − y| < d → |f (x) − f (y)| < e)
3. Para toda y existe exactamente un y tal que x + y = 0. Traduciendo la expresion con operadores lógicos quedaría,
(∀x)(∃!y)(x + y = 0)
4. x + y 6= 0 si y sólo si x 6= 0 o y 6= 0. En simbolos lógicos tenemos
que,
(x + y 6= 0) ↔ (x 6= 0) ∧ (y 6= 0)
5. Finalmente se puede dar un ejemplo de traducción del lenguaje
ordinario al lógico. Considerar la siguiente frases:
a) Si llueve se terminarán los problemas de sequia y no hará falta
más dinero
b) Un partido de futbol no se gana a menos que se corra mucho y
se tenga calidad.
Identificando en la frase a)
p −− Llueve
q −− se terminarán los problemas
r −− falta más dinero
Dr. J. A. Hernández
16
Fac. Ingeniería, UAEM
Lógica
y en la frase b)
p −− Un partido de futbol se gana
q −− se corra mucho
r −− se tenga calidad
entonces la frase a) del lenguaje natural al formal quedaría
p → q ∧ ¬r
y la frase b)
p→q∧r
3.2.
Conectivas, Tablas y Funciones de Verdad
Cada conectivo lógico tiene asociado una tabla y función de verdad.
Los valores de verdad que toma p son verdadero y falso que se denotan
por “V” y “F”, respectivamente. Sin embargo, en estas notas 1 denotará
verdadero y 0 falso, para estar acorde con la notación binaria de las
computador
p
1
1
0
0
p ¬p
1 0
0 1
Negación ¬
p
1
1
0
0
q p→q
1
1
0
0
1
1
0
1
Condicional →
q p∧q
1
1
0
0
1
0
0
0
Conjunción ∧
p
1
1
0
0
q p↔q
1
1
0
0
1
0
0
1
Bicondicional ↔
p
1
1
0
0
q p∨q
1
1
0
1
1
1
0
0
Disyunción ∨
p
1
1
0
0
q p⊕q
1
0
0
1
1
1
0
0
Disyunción exclusiva ⊕
Cuadro 1. Tablas de verdad para los conectivos ¬, ∧,
∨,→, ↔, ⊕
Cada tabla de verdad tienen asociada una función de verdad para
los distintos conectivos . Por ejemplo, la negación tiene asociada la
Dr. J. A. Hernández
17
Fac. Ingeniería, UAEM
Lógica
función f¬ : {0, 1} → {0, 1}, que se deduce de la tabla de verdad (1),
esto es
f¬ (1) = 0
f¬ (0) = 1.
Similarmente, podemos obtener la función asociada al conectivo ∧
de la figura (3.3.1), esto es, la función f∧ : {0, 1} × {0, 1} → {0, 1} tal
que
f∧ (1, 1)
f∧ (1, 0)
f∧ (0, 1)
f∧ (0, 0)
=
=
=
=
1
0
0
0.
De igual manera so obtienen las funciones asociadas a los conectivos
restantes.
3.3.
Equivalencia Lógica
En esta sección se define lo que significa que dos formas enunciativas sean lógicamente equivalentes. Para esto se define lo que es una
atribución veritativa y una valoración. Variables enunciativas son denotadad por p, q, r,... o p1 , p2 , ..., pn . Una forma enunciativa es una
combinación de variables enunciativas relacionadas por los conectivos
¬, ∧,∨, →, etc. Ejemplos de formas enunciativa son
A ≡ (p ∧ q → r) ↔ (p → (¬q ∨ r))
B≡p → s
Aqui las variables enunciativas son p, q, r, s.
Definition 14. (Valoración)
Dada una forma enunciativa A, llamamos valoración a una asignación v, del algfabeto Σ a los valores de verdad. Es decir una valoración
es una función
v : Σ −→ {0, 1}.
Por ejemplo, sea A ≡ p ∨ q → r forma enunciativa. Podemos obtener
la tabla de verdad asociada a A, esto es
Dr. J. A. Hernández
18
Fac. Ingeniería, UAEM
Lógica
p
1
1
1
1
0
0
0
0
q p∨q
1
1
1
1
0
1
0
1
1
1
1
1
0
0
0
0
r
1
0
1
0
1
0
1
0
A
1
0
1
0
1
0
1
1
Cuadro 2. Tabla de verdad de A ≡ p ∨ q → r. La
columna en tonos grises indica los valores de verdad que
toma A, para cualquier valor de verdad de p, q, r.
En la tabla (2), segundo renglón, se han marcado con negritas los
valores que toman las variables enunciativas p, q, r que definen la forma
enunciativa A, esto es
p q r
1 1 0
Cuadro 3. Atribución veritativa de A.
la cual corresponde a una de las ocho posibles atribuciones veritativas de A, y que se puede comprobar comparando tablas (1) y (2). Las
valoraciones para fbf se obtiene mediante la siguiente definición.
Definition 15. (Valoración) Dada A, B una valoración es una
función v, cuyo dominio son las formas enunciativas y cuyo rango es el
conjunto {0, 1} , tales que
1. JpKv = v(p) si A es una variable enunciativa
2. J¬AKv = v¬ (JAKv )
3. JA ∧ BKv = v∧ (JAKv , JBKv )
4. JA ∨ BKv = v∨ (JAKv , JBKv )
5. JA → BKv = v→ (JAKv , JBKv )
6. JA ↔ BKv = v↔ (JAKv , JBKv ).
Donde v es la valoración que depende del operador al que se aplique.
Basado en la definición de valoración se define un concepto importante
en lógica.
Definition 16. Una forma enunciativa se dice que es
Dr. J. A. Hernández
19
Fac. Ingeniería, UAEM
Lógica
1. Tautologia, si toma el valor de verdad 1 para toda
valoración.
2. Contradicción, si toma el valor de verdad 0 para
toda valoración.
3. Contingencia, si toma el valor 1 par algunos y 0
para otros.
Definición (16) es equivalente a que la tabla de verdad de una forma
enunciativa tome valores de verdad 1 si es tautologia y 0 si es contradicción, o 0 y 1’s si es contingencia. Por ejemplo, la columna en la
tabla de verdad (2), de la forma enunciativa A toma los valores 0 y 1’s
concluyendo asi que A es contingencia.
Continuando con la forma enunciativa A de la tabla (2). Se ha
dicho que una atribución veritativa de esta forma enunciativa es la que
se muestra en tabla (3) maracada con negritas en la tabla (2), que
representaremos por v. Esto es, v(p) = 1, v(q) = 1 y v(r) = 0
Ahora, podemos calcular la valoración v asociada para algunos de
los conectivos. Asi, por la definición (15) inciso (4) tenemos que
(3.3.1)
Jp ∨ qKv =
=
=
=
v∨ (JpKv , JqKv )
v∨ (v(p), v(q))
v∨ (1, 1)
1
que es por supuesto el valor correspondiente a la columna p ∨ q, sobre
el renglón marcado con negritas que corresponde a v. De la misma
forma podemos calcular la valoración para α de la forma enunciativa A.
Aplicando la definición (16) incisos (4) (5) para v a la forma enunciativa
A ≡ p ∨ q → r tenemos
(3.3.2)
JAKv =
=
=
=
=
=
Jp ∨ q → rKv
v→ (Jp ∨ qKv , JrKv )
v→ (v∨ (v(p), v(q)), v(r))
v→ (v∨ (1, 1), 0)
v→ (1, 0)
0
Nuevamente, es el valor que corresponde a la columna A en el renglón marcado con negritas que corresponde a la atribución α escogida
mostrada en la tabla (3).
Para finalizar, escojamos ahora la atribución veritativa de la forma
enunciativa A ≡ p ∨ q → r que corresponde al último renglón en la
Dr. J. A. Hernández
20
Fac. Ingeniería, UAEM
Lógica
tabla (2). Ahora en este caso tendremos, v(p) = 0, v(q) = 0 y v(r) = 0.
Aplicando definición (15) incisos (4) y (5), tenemos
(3.3.3)
JAKv =
=
=
=
=
=
Jp ∨ q → rKv
v→ (Jp ∨ qKv , JrKv )
v→ (v∨ (v(p), v(q)), v(r))
v→ (v∨ (0, 0), 0)
v→ (0, 0)
1
Que como se puede observar coincide con el valor de A en el ultimo
renglón de la tabla (2). En los calculos (3.3.1), (3.3.2) y (3.3.3) se han
utilizado las funciones de verdad asociadas a los conectivos, mostradas
en la tabla (1).
Finalmente podemos enunciar la definición pŕincipal de esta sección.
Definition 17. Sean A y B formas enunciativa. Se dice que son
lógicamente equivalentes, denotado por A ⇔ B, si y sólo si para toda
v valoración se cumple que JAKv = JBKv . Por lo que se ha visto, esto
es equivalente a comparar las tablas de verdad de A y B.
Se puede establecer una relación entre la equivalencia lógia y el
concepto de tautologia, la cual se establecerá en forma de un teorema.
Theorem 18. Sean A y B formas enunciativas. A es lógicamente
equivalente a B si y sólo si A ↔ B es una tautologia.
Demostración. Supongamos primero que A y B son lógicamente
equivalentes, esto es A ⇔ B. Esto quiere decir, por la definición (17),
que para toda valoración v se cumple JAKv = JBKv . Ahora, aplicando
la valoracion v a A ↔ B, tenemos que por definición (15)(6),
JA ↔ BKv = v↔ (JAKv , JBKv )
Por un lado, sabemos que JAKv , JBKv pueden tomar solo dos valores
de verdad, 0 y 1. Pero de la tabla de verdad (1) para el bicondicional,
se infiere que no importa si JAKv = 1 o JBKv = 0 en en ambos casos
f↔ (1, 1) = f↔ (0, 0) = 1. De lo cual se concluye que, por definición (16)
que A ↔ B es tautologia, pues v(A ↔ B) = 1 para toda valoración v.
Ahora para demostrar que A ⇔ B, se hará por reducción al absurdo. Esto es, supongamos que A ↔ B es tautologia y que A ⇔ B
no se cumple. Por tanto, de las definición (17), existe una atribución
veritativa α tal que para la valoración vα , vα (A) 6= vα (B). Ahora, si
Dr. J. A. Hernández
21
Fac. Ingeniería, UAEM
Lógica
aplicamos esta valoración a la forma enunciativa A ↔ B, por definición
(15)(6) tenemos
(3.3.4)
vα (A ↔ B) = f↔ (vα (A), vα (B))
De las tablas de verdad (1) para el bicondicional,tenemos f↔ (0, 1) =
f↔ (1, 0) = 0. Esto es, seimpre que vα (A) 6= vα (B) se tiene vα (A ↔
B) = 0, lo cual contradice la hipotesis de que (A ↔ B) es tautologia. Por tanto, A ⇔ B se tiene que cumplir, luego A es lógicamente
equivalente a B
Para ejemplificar el resultado del teorema (18), consideremos las
siguientes formas enunciativas A = ¬(p ∨ q) y B = (¬p ∧ ¬q). Para
demostrar que A y B son lógicamente equivalentes debemos demostrar
que A ↔ B es tautologia. Para ello debemos construir la tabla de
verdad de
C ≡ ¬(p ∨ q) ↔ (¬p ∧ ¬q).
La tabla de verdad de la forma enunciativa C queda,
p ¬∨ q ↔ ¬p ∧ ¬q
1 0 1 1 0 0 0
1 0 0 1 0 0 1
0 0 1 1 1 0 0
0 1 0 1 1 1 1
Cuadro 4. Tabla de verdad de C
La columna en tono gris obscuro, tabla 4, corresponde a la valores
adquiridos por C para toda atribución veritativa, esto para todas las
combinacioes de 0 y 1’s de las variables p, q. Evidentemente ha dado
como resultado el valor de verdad 1 en todos los casos, por consiguiente
C es tautologia y por teorema 18 podemos concluir que A ≡ ¬(p ∨ q)
y B ≡ (¬p ∧ ¬q) son lógicamente equivalentes.
Debemos tambien observar que las columnas, que se han marcado
en tonos tenues de grises en la tabla 4, corresponden a los valores de
verdad de las formas enunciativas ¬(p ∨ q) y (¬p ∧ ¬q). En la tabla 4
se observa que los valores de las columnas coinciden. Esto quiere decir
que para todos los valores de verdad de las variables p y q sus tablas
de verdad coinciden. En otras palabras para toda función veritativa v,
v(A) = v(B), de lo cual se deduce por la definición 17, que A ⇔ B.
Dr. J. A. Hernández
22
Fac. Ingeniería, UAEM
Lógica
Otro resultado que se usará en las proximas secciones y para la
demostración de algunas de las propiedades de conjuntos es la siguiente
proposición.
Proposition 19. Si A y A → B son tautologias entonces B es
tautologia.
Demostración. La demostración se hará por reducción al absurdo. Esto es, supongamos que A y A → B son tautologias y B no lo es.
De lo cual se infiere, por definición (16), que existe v valoración tal que
v(B) = 0. Pero v(A) = 1 por suposición y
v(A → B) = f→ (v(A), v(B))
= f→ (1, 0)
= 0
Que contradice la suposición de que A → B es tautologia por definición (16). Asi que la suposición inicial de que B no es tautologia es
incorrecto, por tanto B es tautologia.
3.3.1.
Argumentación y validez.
Definition 20. (Forma argumentativa)
Una forma argumentativa es una sucesion finita de formas eneunciativas de las cuales la ultima se considera la conclusion y el resto las
premisas.
La formas argumentativas pueden o no ser validas. Para establecer la validez de las formas argumentativas se definira en funcion de
valoraciones.
Definition 21.
a (Forma argumentativa valida) La forma argumetnativa A1 , ...., An A es invlaida si existe valoracion v tal que v(Ai ) = 1
para toda i y v(A) = 0.
va.
Como complemento se definira la longitud de una forma enunciati-
Definition 22. Dada una forma enunciativa, el grado es una aplicacion del conjunto de los formas enunciativas al conjunto de los numeros naturales. Se define el grado de una forma de manera inductiva
como sigue:
1. ∂(A) = 0 si A es una letra eneunciativa
2. A, B formas enunciativas
∂(¬A) = 1 + ∂(A)
∂(A ∧ B) = 1 + ∂(A) + ∂(B)
Dr. J. A. Hernández
23
Fac. Ingeniería, UAEM
Lógica
∂(A ∨ B) = 1 + ∂(A) + ∂(B)
∂(A → B) = 1 + ∂(A) + ∂(B)
∂(A ↔ B) = 1 + ∂(A) + ∂(B)
Example 23. El grado de la forma enunciativa, A ≡ (p → q) ∨
(¬(q → r)) se calcula de la siguiente forma:
∂A = 1 + ∂(p → q) + ∂(¬(q → r))
= 1 + 1 + ∂(p) + ∂(q) + 1 + 1 + ∂(q) + ∂(r)
= 4
Definition 24. (Consecuencia logica) Dado Γ = {A1 , ..., An } y A
formas enunciativas, A una consecuencia logia de Γ si y solo s para
toda valoracion v, tal que v(Ai ) = 1 para cada Ai entonces v(A) = 1.
La conexion entre las dos definiciones dadas conanterioridad se pueden
resumir en una proposicion.
Proposition 25. La forma argumentativa A1 , ..., An ∆A es valida
si y solo si A es consecuencia logica del conjunto Γ = {A1 , ..., An }
Demostración. Si A1 , ..., An ∆A es valida, por definicion (21) no
existe valoraciion v tal que v(Ai ) = 1, para toda i y v(A) = 0. Por
consiguiente, para toda valoracion v si v(Ai ) = 1 para toda i entonces
v(A) = 1, esto es A es consecuencia logica de Γ, por definicion (24).
Ahora si A es consecuencia logica de Γ. Si existiera v valoracion
tal que v(Ai ) = 1 para toda i con v(A) = 0, esto es A1 , ..., An ∆A
es invalida tenemos que A no puede ser conscuencia logica de Γ. Por
consiguiente no puede existir valoracion v con las caracteristicas antes
mencionadas.
Proposition 26. La forma argumentativa A1 , ..., An ∆A es valida
(o equivalentemente A es consecuencia logica del conjunto {A1 , ..., An })si
y solo si la forma enunciativa
A1 ∧ · · · ∧ An → A
es tautologia.
Demostración. La demostracion se hara por reduccion al abseurdo. Supongamos que A1 , ..., An ∆A es valida y que A1 ∧ · · · ∧ An → A
no es tautologia. Existe valoracion v tal que v(A1 ∧ · · · ∧ An ) = 1: y
v(A) = 0. Bajo esta valoracion, v(Ai ) = 1 para toda i y v(A) = 0. Por
tanto, A1 , ..., An ∆A no es valida, que es una contradiccion.
Ahora supongamos que (A1 ∧ · · · ∧ An ) → A es tautologia entonces
A1 , ..., An ∆A es valida. Si A1 , ..., An ∆A no es valida entonces existe v
valoracion tal que v(Ai ) = 1, y v(A) = 0.
Dr. J. A. Hernández
24
Fac. Ingeniería, UAEM
Lógica
Aplicando la valoracion v,
v(A1 ∧ · · · ∧ An → A) = f→ (v(A1 ∧ · · · ∧ An ), v(A))
= f→ (1, 0)
= 0
lo cual contradice.
Example 27. Probar que
¬B → A) es valida.
(( A ∨ B ) ∧ ¬B)
0 0 0
0
1
0 1 1
0
0
1 1 0
1
1
1 1 1
0
0
la forma enunciativa C ≡ ((A ∨ B) ∧
→
1
1
1
1
A
0
0
1
1
v(A ∨ B) = 1, v(¬B) = 1 entonces v(A) = 1
v(A ∨ B) =
=
1 = v(¬B) =
=
=
f∨ (v(A), v(B))
f∨ (1, 0)
f¬ (v(B))
f¬ (0)
1
Esto prueba que la forma argumentativa A ∨ B, ¬B∆A es válida.
Dicho de otra forma A es vconsecuencia lógica del conjunto {A∨B, ¬B}
La demostracion se hace calculando su tabla de verdad, concluyendo
que C es tautologia y por lo tanto C es valida.
Esta forma argumentativa recibe el nombre de silogismo disyuntivo como regla de inferencia.
3.4.
Conjuntos adecuados de conectivas
V
Leyes de equivalencia usando {¬, }
W
V
A B ⇐⇒ ¬(¬A ¬B)
A → B ⇐⇒
∧ ¬B) V
V ¬(A V
A ↔ B ⇐⇒ ¬ (A ¬B) ¬ (B ¬A)
W
Leyes de equivalencia usando {¬, }
Dr. J. A. Hernández
25
Fac. Ingeniería, UAEM
Lógica
W
B ⇐⇒ ¬(¬A W¬B)
A → B ⇐⇒W¬A W B
W
A ↔ B ⇐⇒ ¬ [¬ (¬A B) ¬ (¬B A)]
A
V
Leyes de equivalencia usando {¬, →}
A ∧W
B ⇐⇒ ¬(A → ¬B)
A W B ⇐⇒ ¬A → B
A B ⇐⇒ ¬B → A
W
A W B ⇐⇒ (A → B) → B
A B ⇐⇒ (B → A) → A
A ↔ B ⇐⇒ ¬ [(A → B) → ¬ (B → A)]
Example.
Solución
A
0
0
1
1
3.4.1.
∧ B ←→ ¬( A −→ ¬B)
0 0
1
0 0
1
1
0 1
1
0 0
1
0
0 0
1
0 1
1
1
1 1
1
1 1
0
0
Barra de Sheffer.
A | B ⇐⇒ ¬(A ∧ B)
Como ejemplo se puede comprobar que
Example. ¬A ⇐⇒ A|A
Demostracion:
A|A ⇐⇒ ¬(A ∧ A)
⇐⇒ ¬A ∨ ¬A
⇐⇒ ¬A
Example. A ∧ B ⇐⇒ ¬(A|B) ⇐⇒ (A|B)|(A|B)
Demostracion:
Dr. J. A. Hernández
26
Fac. Ingeniería, UAEM
Lógica
(A|B)|(A|B) ⇐⇒
⇐⇒
⇐⇒
⇐⇒
⇐⇒
¬ [A|B ∧ A|B]
¬ [¬(A ∧ B) ∧ ¬(A ∧ B)]
¬ [¬A ∨ ¬B]
¬¬A ∧ ¬¬B
A∧B
3.4.2.
Barra de Pierce.
W
A ↓ B ⇐⇒ ¬ (A B)
Por ejemplo se pueden probar las siguientes equivalencias
Example. A → B ⇐⇒ ¬(¬A ↓ B) ⇐⇒ [(A ↓ A) ↓ B] ↓ [(A ↓ A) ↓ B]
Demostración:
[(A ↓ A) ↓ B] ↓ [(A ↓ A) ↓ B] ⇐⇒
⇐⇒
⇐⇒
⇐⇒
⇐⇒
⇐⇒
3.5.
¬ [[(A ↓ A) ↓ B] ∨ [(A ↓ A) ↓ B]]
¬ [¬ [(A ↓ A) ∨ B] ∨ ¬ [(A ↓ A) ∨ B]]
¬ [¬ [¬(A ∨ A) ∨ B] ∨ ¬ [¬(A ∨ A) ∨ B]]
¬ [¬ [¬A ∨ B] ∨ ¬ [¬A ∨ B]]
¬ [(A ∧ ¬B) ∨ (A ∧ ¬B)]
¬A ∨ B
Calculo de deducción natural,
3.5.1. Sistema Formal Axiomático L. En esta sección se definirá un sistema formal axiomatico. Le definición se basa en el material
ya visto en capitulo I y II. Como ejemplo de estos sistemas tendremos
en l aximatización de la teroría de conjuntos.
Definition 28. El sistema formal L se caracteriza por
1. Vocabulario. El vocabulario se compone del conjunto infinito
numerable de simbolos
{¬, →, (, ), p1 , p2 , ..., }
Dr. J. A. Hernández
27
Lógica
Fac. Ingeniería, UAEM
2. Conjunto de fbf ’s. Es se pueden defininir de manera inductiva. a) p1 , p2 , ... las variables son fbf’s. b) Si A y B son fbf’s
entonces ¬A, y A → B,....,etc. son fbf’s. c) El conunto de todas
las fbf’s es el generado empleando reglas a) y b).
3. Un conjunto minimo de conectivas es {¬, →}, entonces {∧, ∨, ↔}
se definen como
(A ∧ B)
⇔
¬(A → ¬B)
(A ∨ B)
⇔
¬A → B
(A ↔ B)
⇔
¬ [(A → B) → (¬(B → A))]
4. Axiomas. Para cualquier A, B y C los siguientes son fbf’s son
axiomas del sistema L
L1
A → (B → A)
L2
(A → (B → C)) → ((A → B) → (A → C))
L3
((¬A) → (¬B)) → (B → A)
5. Reglas de Inferencia. En el sistema L hay solamente una regla
de inferencia, Modus Ponens, que afirma
A
A→B
(MP)
B
Los simbolos ” ∧ ”, ” ∨ ” y ” → ” no pertenecen al vocabulario de L,
pero han sido definidos en términos de ¬ y →. Esto se sigue de la tabla
de equivalencias, que muestra que {¬, →} es un conjunto minimo de
conectivas. Se mantiene reducido el número de conectivas con el fin de
mantener simple el sistema axiomatico, esto es el número de axiomas
y reglas es reducido o el más simple.
Definition 29. (Deducción) Sea Γ un conjunto de fbf’s. Una sucesión finita A1 , ..., An de fbf’s de L, es una deducción a partir de Γ si
para todo i ∈ {1, ..., n} se cumple alguna de las condiciones
1. Ai es un axioma de L
2. Ai ∈ Γ
3. Ai se infiere inmediatamente de dos miembros anteriores de
la sucesión, digamos Aj , Ak (j < i, k < i) mediante el Modus
Ponens.
El ultimo miembro An se dice deducible a partir de Γ, denotado por
Γ `L An .
Definition 30. Una demostración en L es una deducción en L
sin premisas. Si la fbf A es el último miembro de una demostración,
decimos que A es un teorema de L y escribimos `L A.
Dr. J. A. Hernández
28
Fac. Ingeniería, UAEM
Lógica
Remark. 1. `L A es abreviatura de ∅ `L A.
2. Los axiomas son teoremas de L, ya que sus demostraciones son
sucesiones de fbf’s de un solo meimbro, el propio axioma.
Example. Supongamos que queremos demostrar que
G0 ≡ (p1 → p2 ) → (p1 → p1 )
es un teorema de L
1. G0 no es un axioma del sistema L
2. Las únicas formulas de que se disponen son axiomas. Aplicando
el axioma 2, y {A 7→ p1 , B 7→ p2 , C 7→ p1 } se obtiene
G1 ≡ (p1 → (p2 → p1 )) → ((p1 → p2 ) → (p1 → p1 ))
3. Ahora, debemos eliminar (p1 → (p2 → p1 )) de G1 aplicando la
regla MP. Pero antes que nada se debera reducir la fbf (p1 →
(p2 → p1 )). Aplicando axioma L1 con {A 7→ p1 , B 7→ p2 } se
obtiene
G2 ≡ (p1 → (p2 → p1 ))
que es la segunda formula en la demostración y coincide con el
antecedente de G1 . Se puede ahora aplicar MP a las fbf G1 y
G2 , obteniendo
(p1 → p2 ) → (p1 → p1 )
3.5.2.
Deducción natural. Teorema de la deducción.
Theorem 31. Sean A y B fbf ’s de L y Γ un conjunto de fórmulas
de L (que puede ser vacío). Si Γ ∪ {A} `L B entonces Γ `L A → B.
Demostración. La prueba se hará en el número de pasos de la
deducción de B a partir de Γ ∪ {A}.
I. Caso Base.
(a) Si B un axioma de L se puede construir la demostración de la
siguiente forma
(1) B Axioma de L
(2) B → (A → B), L1
(3) A → B MP
De esta forma A → B es un teorema de L y por tanto se deduce
trivialmente a partir de Γ.
(b) Si ahora B ∈ Γ , se puede construir la demostración de la
siguiente forma
(1) B premisa por ser miembro de Γ
(2) B→ (A→B), L1
(3) A→B MP, 1,2
Dr. J. A. Hernández
29
Fac. Ingeniería, UAEM
Lógica
De esta forma Γ `L A → B
y por último si B es A ya se ha demostrado que A → A es un
teorema de L
II. Caso inductivo. (n > 1) Hipótesis de inducción la proposición se
verifica para todas derivacines Γ ∪ {A} `L C con menos de n pasos.
Para esto se tiene dos posibilidades:
a) B es un a xioma de L o B ∈ Γ ∪ {A} por lo que se procede como
en el caso base.
b) B sse obtiene de dos reglas anteriores mediante la aplicación de
la regla de inferencia modus ponens. Estas dos fbf serán de la forma C y
C → B y tanto una coma la otra de deducen a partir de Γ ∪ {A} `L en
menos de n pasos. De esta forma aplicando la hipótesis de inducción,
Γ `L A → C y Γ `L A → (C → B) .
Ahora la deducción Γ `L A → B se deduce de la siguiente forma:
....
(k − 2) A → C
(k − 1) A → (C → B)
(k) [A → (C → B)] → [(A → C) → (A → B)], L2
(k + 1) (A → C) → (A → B), MP, k − 1
(k + 2) (A → B), MP, k − 2, k + 1
Reciproco del teorema de la deducción
Proposition 32. Sean A, B fbf de L y Γ un conjunto de fbf de L
( que puede ser vacío). Si Γ `L (A → B) entonces Γ ∪ {A} `L B
3.6.
Reglas De Inferencia
REGLAS BASICAS DE INFERENCIA
Reglas de Implicacion
eliminacion de implicador[EI,MP]
A→B
A
B
introduccion del Implicador[II]
A
⇓
B
A→B
Reglas de Conjuncion
eliminacion del Conjuntor[EC]
A
V
A
Dr. J. A. Hernández
B
V
EC1 ............... A B B EC2
30
Fac. Ingeniería, UAEM
Lógica
introduccion del Conjuntor[IC]
A
A
B
V
B
Reglas de Disyuncion
eliminacion del Disyuntor[ED]
A
_
B
A
⇓
C
B
⇓
C
C
introduccion del Disyuntor[ID]
A
B
W
ID1............. A W
ID2
A B
B
Reglas de la Negacion
eliminacion del Negador[EN]
¬¬A
A
introduccion del Negador
A
⇓
V
B ¬B
¬A
REGLAS DE LA INFERENCIA DERIVADAS
Reglas derivadas de la implicacion [sil]
A→B
B→C
A→C
ley de Identidad [id]
A
A
Mutacion de premisas[mut]
Dr. J. A. Hernández
31
Fac. Ingeniería, UAEM
Lógica
A→(B→C)
B→(A→C)
Carga de Premisas[cpr]
A
B→A
Reglas de derivadas de la negacion
Mudus Tollens[MT]
A→B
¬B
¬A
introduccion del doble negador[IDN]
A
¬¬A
principio de no contraccion [PNC]
V
¬(A ¬A)
ley de contraposicion[Cp]
A→B
¬B→¬A
Ex contradictione quodlibet[ECQ]
V
A ¬A
B
principio del tercio excluso[PTE]
A
W
¬A
Reglas derivadas de la conjuncion y disyuncion
ley de importacion[IMP]
A→(B→C)
V
A B→C
silogismo Disyuntivo[SD1]
W
A B
¬B
A
Ley de exportacion[Exp]
Dr. J. A. Hernández
32
Fac. Ingeniería, UAEM
Lógica
V
A B→C
A→(B→C)
Silogismo WDisyuntivo
A B
¬A
B
Exercise. Capitulo IV
{A → B, ¬B} ` ¬A
(0) A → B
(1) ¬B
(2) revisar teoria, aprnder formula, n veces.
(3) A por un monento supongo que A es verdadero
(4) B
(5) B ∧ ¬B
(6) ¬A
{A, B ∧ ¬B} ` ¬A
Dr. J. A. Hernández
33
Capítulo 4
Lógica de predicados
4.1.
Semántica
4.1.1.
Nombres, Functores y Relatores.
Vocabulario.
Simbolos comunes a todos los formalismos
Simbolos de variable x, y, z, x0 , yV
0, z
W0 , ...........xn , yn , zn
Conectivas y cuantificadores ¬, , , →, ↔, ∀,y∃.
Signos de puntuacion: ”(” ; ”)” ; ” , ”.
Simbolos Peculiares de un formalismo
Constantes a, b, c, ...a0 , b0 , c0 , ...., an , bn , cn el conjuntor de constantes se denota por C.
Simbolos de funciones f n , g n , f0n , g0n , ...., f n , .........el conjunto de
simbolos de funciones se denota por F .
Simbolos de relación n − ádicos P n , Qn , P0n , Qn0 m, ......, Pmn , Qnm .
El conjunto de simbolos de relacion se donotar a por P.
Terminos.
Un termino de L es una expression que consiste de variables
constantes y simbolos de funcion, y se define mediante las siguientes
reglas:
S
Si t ∈ V U entonces t es un termino.
Si t1 , ......, | tn son terminos de L y f n es un simbolo de funcion
n − ádico entonces f n (t1 , ...., tn ) es un termino de L.
El conjunto de terminos se denota por T .
4.1.2. Formula Atomica.
Una formula atómica es una expression , en la que intervienen
simbolos y terminos de relacion y se define como:
ejemplo:
Si t1 , ....tn son terminos de L y Rn es un simbolo de relocion n − ádico
entonces Rn (t1 , ...., tn ) es una formula atomica de L.
35
Fac. Ingeniería, UAEM
Lógica
4.1.3. Formula Bien Formada.
Una formula bien formada <‌<fbf>‌>de L es una expresion, en la que
intervienen formulas atomicas, conectivas y/o cuantificadores, que se
pueden formar de acuerdo a las siguientes reglas.
Toda formula atomica de L, es una fbf.
V
W
Si A, Bson fbf´s de L, tambien lo son ¬A, ¬B, A B, A B, A →
B y A ↔ B.
Si A es una fbf y x ∈ V entonces (∀x)(A) y (∃x) (A) son fbf´s.
4.1.4.
Cuantifcadores,
Radio de accion de un cuantificador:
a. En la fbf (∀x)A el radio de accion de (∀x) es A
b. En la fbf (∃x) A el radio de accion de (∃x)es A
Ocurencia ligada de una variable: Una ocurrencia de una variable xse
dice ligada si aparece dentro del radio de accion de un cuantificador
(∃x) y (∀x).
Ocurrencia libre de una variable: Una ocurrencia de la variable x en
una fbf se dice que es libre, si su aparicion no es ligada.
4.2.
Teoría de modelos
La teoria de modelos es la formalizacion mediante una entidad (como
el conjunto de los numeros-naturales), junto con las propiedades y
relaciones que se dan entre sus elementos.
la Veracidad de una formula se da en el contexto de una
interpretacion.
4.2.1. Una Interpretación.
Elegir el donimio o universo; es decir un conjunto no vacio de
individuos que se referian a las variables.
Asignar significado a los simbolos peculiares del formalismo:
Asignar a cada constante un individuo, a cada simbolo de funcion en el dominio y a cada simbolo de relacion una relacion en
el dominio.
Una interpretacion I de , es un par (DI , J)que consiste en:
Un conjunto no vacio DI , el dominio de I
Una aplicacion J que asigna:
-a cada Simbolo constante, ai de L un elemento distinguido de DI ,
esto es J(ai ) = ai
Dr. J. A. Hernández
36
Fac. Ingeniería, UAEM
Lógica
n
n
-A cada simbolo de funcion J (fin ) = f i tal que f i = DIn → DI
-A cada simbolo de relacion Rin − n − ario de L una relacion
n
n
n
J (Rin ) = Ri tal que Ri ⊂ DIn esto es Ri = {(d1 , ...., dn ) : di ∈ DI } es
un conjunto de n − tuplas de DIn .
4.2.2.
Valoracion.
(Valoracion en I)
Una valoracion v en I es una aplicacion que asigna a cada variable de
L un elemento x de; dominio de la interpretacion
v:
V → DI
DI
x → v(x) = x
(Valoracion x-equivalente)
Sea x ∈ DI , donde DI es el dominio de una interpretacion I y sea v
una valoracion en I. la valoracion vxx tal que.
vxx = { Vx...........si..Z≡X;
(Z)..en..otro..caso
se dice que es una valoracion x- equivalente de v.
Una valoracion V en I es una aplicacion que asigma a cada termino
de I un elemento del dominio DI .
V : T → DI
definidad mediante la siguiente regla.

V
(1)v(x)
si...t ∈ V V t ≡ x

(2)J(a)
si..t ∈ C t ≡ a
V (t) =
 (3)J(f n )(V (t )....V (t )) si..f n ∈ F V(t ∈ T.. V t ∈ T ) V t ≡ f n (t .....t )
1
n
1
n
1
n
i
i
i
donde v es una valoracion de v en DI
4.2.3. Evaluacion.
Dada una fbf A de L en el texto contexto de una interpretacion
I = (DI , J)y una valoracion V en I. EvalI,V es una aplicacion de
fbf´s a valores de verdad que se definen inductivamente como:
Si A ≡ Rn (t1 ....tn )(esto es Aes una formula atomica) entonces
EvalI,V (A) = J(Rn )(V (t1 )....V (tn ))
n
= R (V (t1 )....V (tn )) = V
n
n
si y solo si V (t1 )....V (tn ) ∈ R , donde R = J(Rn ) es una relacion de
DIn ;
Si A es de la forma:
¬B entonces EvalI,V (A) = f¬ (EvalI,V (B))
Dr. J. A. Hernández
37
Fac. Ingeniería, UAEM
Lógica
W
(B V C) entonces EvalI,V (A) = fW (EvalI,V (B), EvalI,V (C))
(B C) entonces EvalI,V (A) = fV (EvalI,V (B), EvalI,V (C))
(B → C) entonces EvalI,V (A) = f→ (EvalI,V (B), EvalI,V (C))
(B ↔ C) entonces EvalI,V (A) = f↔ (EvalI,V (B), EvalI,V (C))
Si A ≡ (∀x)B entonces EvalI,V (A) = V si y solo si para toda
valoracion Vxx x- equivalente de V, EvalI,VxX (B) = V ;
Si A ≡ (∃x)B entonces EvalI,V (A) = V si y solo si para alguna
valoracion Vxx x- equivalente de V .
4.2.4. Satisfactibilidad. Sea una interpretacion I = (DI , J).
sea A una fbf de L. la valoracion V en I satisface la fbf A (denotado,
V sat A) si y solo si se cumple que EvalI,V (A) = V .
4.2.5. Equivalencia logica y verdad. Dos fbf´s A y B de L
son logicamente equivalentes, denotado por A ⇐⇒ B, si y solo si para
toda interpretacion I y para toda valoracion V en I,V satisface a A si
y solo si V satisface a B
Una fbf A es verdadera en I si y solo si toda valoracion V en I
satisface a A.
Una fbf A es falsa en I si y solo si no existe valoracion V en I
que satisfaga a A.
4.2.6.
Formulas cerradas y verdad en una interpretacion.
Proposicion
Sea A una fbf de L e I una interpretacion de L.
Entonces I |= A si y solo si I |= (∀x)A.
Colorario
Sean y1 , .....yn variables de L, sea A una fbf de L en I
una interpretacion de L. Entonces ,I |= A si y solo si
I |= (∀y1 )......(∀yn )A.
–
Lema
Sea Auna fbf de L e I una interpretacion de L. si V y
ϕson valoraciones tales que V (x) = ϕ(x) para toda
variable libre x que ocurren en Aentonces V satisface
Asi y solo si ϕsatisface A.
Proposicion
Sea Auna fbf cerreda de L e I una interpretacion de L.
Entonces, I |= A o I |= ¬A.
Dr. J. A. Hernández
38
Fac. Ingeniería, UAEM
Lógica
4.3.
Verdad Logica
Formula logicamente valida
Sea una fbf Ade I.
Aes logicamente valida si y solo si para toda interpretacion Im
A es verdadera en l.
A es insatisfacible si y solo si para toda interpretacion I,A es
falsa en I.
A es satisfacible si y solo si existe una interpretacion I y una
valoracion en I tal que V satisface A en I.
Proposicion
Saen A y B fbf´s de L. si A y (A → B)son logicamente
validas entonces B es logicamente valida.
Proposicion
Saen A y B fbf´s de L. A es logicamente equivalente a
B si y solo si la fbf (A ↔ B)es logicamente valida.
4.3.1.
Consecuencia Logica y Modelos.
Modelos
Dada una fbf cerrada A de L, decimos que una
interpretacion I es modelo de Asi y solo si la fbf Aes
verdadera en la interpretacion I.
–
Sea Γ un conjunto de fbf´s cerradas de L, sea Iuna
interpretacion de L. I es modelo de Γ si y solo si I es
modelo para cada una de las formulas de Γ.
–
Sea Γ un conjunto de fbf´s cerradas de L.
Γes valido si y solo si para toda interpretacion I es modelo de
Γ.
Γes insatisfacible si y solo si no existe una interpretacion I de
L que sea modelo de Γ.
Γ es satisfacible si y solo si existe una interpretacion I de L que
es modelo de Γ.
4.4.
4.5.
4.6.
Dr. J. A. Hernández
Calculo axiomático
Propiedades formales
Deducción Natural
39
Capítulo 5
Otras lógicas
5.1.
5.2.
Difusa
5.3.
Modal
5.4.
5.5.
Multivalente
Temporal
Intuicionista y no monótona
41
Bibliografía
43
Apendice (Lógica y conjuntos)
.1.
Lógica de proposiciones y conjuntos
En esta sección se estudiaran los conjuntos basados en la lógica
de proposiciones. Se definarán los conjuntos tomando como punto de
partida dos axiomas. Los axiomas no se discutirán en detalle, aunque
se darań explicaciones pertinentes para el buen entendimiento de la
sección. La teoría axiomatica se estudiará más adelante con el calculo
axiomático.
.1.1. Conjuntos. Empezaremos por definir lo que es un conjunto
y el conjunto vacio usando el lenguaje formal.
Definition 33. ∅ = x ↔ (∀y)(y ∈
/ x)
La definición establece que x es el vacio si x no tiene elementos. O
el vacio es aquello que no tiene elementos.
La siguiente definición nos dice de manera precisa lo que es un
conjunto.
Definition 34. y es un conjunto ↔ (∃x) ((x ∈ y) ∨ (y = ∅))
La definición 34 establece que y es un conjunto si y tiene elementos
o y no tiene elementos. Notar que la definición hace uso de la definición
33. Y puesto que la definición es un si y sólo si, tenemos que si y = ∅
entonces y es un conjunto. Que quiere decir que ∅ por definición es un
conjunto.
Para poder construir la teoria de conjuntos se necesitan axiomas.
En términos generales un axioma es un enunciado que se acepta como
cierto sin tener que recurrir a una demostración formal del enunciado.
La otra caracteristica es que son las leyes, si es que podemos decirlo de
esta manera, en las cuales se basa una teoria. En este caso la teoria de
conjuntos se construira basada en dos axiomas, que se enuncia a continuación. Los conjuntos se denotarán por letras mayusculas mientras
que letras minisculas denotarán elementos pertenecientes a conjuntos,
si no se establece lo contrario.
45
Fac. Ingeniería, UAEM
Lógica
Axiom 35. (Axioma de Extensionalidad)
(∀x)(x ∈ A ↔ x ∈ B) → A = B
El axioma establece las condiciones en las culaes dos conjuntos son
iguales. Basta que todos los elementos del conjunto A pertenezcan a
B y los elementos del conjunto B pertenezcan a A para considerar los
conjuntos iguales.
Axiom 36. (Separación)
(∃B)(∀x)(x ∈ B ↔ x ∈ A ∧ p(x))
donde p(x) puede ser cualquier propiedad.
El axioma 36 no es completamente intuitivo a diferencia del axioma
35, porque envuelve una propiedad p(x). A medida que la teoría se
desarrolle se clarificará su uso y porque es tan necesario.
La siguiente definición establece la no pertenencia de un elemento
a un conjunto.
Definition 37. x ∈
/ A ↔ ¬(x ∈ A)
La definición expresa la no pertenencia mediante la negación de
pertenenecia. x ∈
/ A se lee, “x no pertenece al conjunto A”.
Usando el axiome se separación y definición 37 podemos demostrar que el conjunto vacio no tiene elementos. Expresado en forma de
teorema tenemos,
Theorem 38. x ∈
/∅
Demostración. Tomando como propiedad p(x) : x 6= x, se tiene
por el axioma de separación: para toda x existe un conjunto A tal que
x ∈ A si y sólo si x ∈ ∅ y x 6= x. En lenguaje formal el axioma de
separación dice,
(.1.1)
(∃A)(∀x)(x ∈ A ↔ (x ∈ ∅) ∧ (x 6= x))
Ahora, si suponemos que x ∈ A tenemos que por (.1.1) x 6= x, lo cual
es absurdo. Por tanto, debe necesariamente pasar
(∀x)(x ∈
/ A)
lo que implica por la definción 33, que A = ∅. Asi que se concluye que
x∈
/∅
Dr. J. A. Hernández
46
Fac. Ingeniería, UAEM
Lógica
.1.2. Definiciónes sobre conjuntos. Basado en los axiomas y
definiciones de la sección (34) se definirán algunas de las propiedades
basicas de los conjuntos, tales como subconjuntos.
Definition 39. A ⊆ B ↔ (∀x)(x ∈ A → x ∈ B)
De la anterior definición se obtiene el significado de A ⊆ A. Esto es,
A es un subconjuto de si mismo. Escrito en forma de teorema tenemos,
Theorem 40. A ⊆ A
Demostración. La siguiente forma enunciativa
(∀x)(x ∈ A → x ∈ A)
es verdad, o en otras palabras identificando p ≡ x ∈ A, es obvio que
p → p es una tautologia. Por definición (39), se sigue que
A ⊆ A ↔ (∀x)(x ∈ A → x ∈ A)
luego A ⊆ A.
El teorema siguiente da las condiciones de cuando dos conjuntos
son iguales basado en el concepto de subconjunto. El axioma de extensionalidad da el resultado deseado.
Theorem 41. (A ⊆ B) ∧ (B ⊆ A) → A = B.
que
Demostración. Por la definición de subconjunto (39), se tiene
(.1.2)
(.1.3)
(.1.4)
(A ⊆ B) ∧ (B ⊆ A) → (∀x) [(x ∈ A → x ∈ B)
∧(x ∈ B → x ∈ A)]
→ (∀x)(x ∈ A ↔ x ∈ B)
→ A=B
Con esto tres paso pasos hemos terminado la demostración del teorema, puesto que se ha concluido que A = B. Sin embargo, se explicaran cada uno de ellos. La justificación es como sigue. La expresion
(.1.2) se sigue de la definición (39), pues simplemente se ha traducido
la expresion (A ⊆ B) ∧ (B ⊆ A) al lenguaje formal. La expresion (.1.3)
se obtiene de (.1.2) aplicando algunas equivalencias lógicas. Esto es, si
se identifica p ≡ x ∈ A y q ≡ x ∈ B se tiene que expresion (.1.2) se
puede expresar como (p → q) ∧ (q → p) y (.1.3) quedaria (p ↔ q), por
tanto tenemos la forma enunciativa
(.1.5)
(p → q) ∧ (q → p) → (p ↔ q).
Para justificar el paso de (.1.2) a (.1.3) debemos demostrar que la
forma enunciativa (.1.5) es tautologia. Para ello se construye la tabla
de verdad de (.1.5). La tabla de verdad es como sigue
Dr. J. A. Hernández
47
Fac. Ingeniería, UAEM
Lógica
(p → q) ∧ (q → p) → (p ↔ q)
1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 1 1 1 1 0 0
0 1 1 0 1 0 0 1 0 0 1
0 1 0 1 0 1 0 1 0 1 0
Cuadro 1. La colunna en tono gris obscuro muestra
que la forma enunciativa (p → q) ∧ (q → p) → (p ↔ q)
es tautologia, pues todos los valores de verdad son 1.
Por tanto el pasar de (.1.2) a (.1.3) está justificado. Finalmente,
pasar de (.1.3) a (.1.4) es simplemente la aplicación del axioma de
extensionalidad (35).
Dr. J. A. Hernández
48