Download Unidad I: Lógica Matemática

Unidad I: Lógica Matemática
Juan Miguel Olalla
UNIDAD I: LÓGICA MATEMÁTICA
1.1. Introducción
La Lógica Matemática es la rama de las Matemáticas que nos permite comprender sobre la
validez o no de razonamientos y demostraciones que se realizan.
La lógica estudia la forma del razonamiento, y es ampliamente aplicada en la filosofía,
matemáticas, computación y física. En la filosofía para determinar si un razonamiento es
válido o no, ya que una frase puede tener diferentes interpretaciones, sin embargo la lógica
permite saber el significado correcto. En las matemáticas para demostrar teoremas e inferir
resultados matemáticos que puedan ser aplicados en investigaciones. En la computación
para revisar programas.
En esta unidad en primer lugar revisamos el concepto de proposición, estableciendo el
significado y utilidad de los conectivos o conectores lógicos, los cuáles de utilizan para
formar proposiciones compuestas. También definimos los conceptos de tautología y
contradicción,
así como explicaremos las proposiciones lógicamente equivalente por
medio de tablas de verdad. Luego daremos a conocer las aplicaciones del cálculo
proposicional en la teoría de los circuitos. Finalmente; abordamos el estudio de los
cuantificadores.
1.2. Proposiciones
Diremos que una proposición es un enunciado (o frase) en el cual podemos asignar un
valor de verdad o falsedad; pero no ambos al mismo tiempo. Por ejemplo:
Son proposiciones:

Albert Einstein descubrió América.

56 − 20 + 4 = 40

La luna es un satélite natural de la tierra.

El dos es un número primo.

4+3 = 7
ESPOCH – Escuela de Ingeniería en Sistemas
1
Unidad I: Lógica Matemática

Juan Miguel Olalla
32 + 42 = 52
Existen enunciados que no son proposiciones, porque no es posible establecer su valor de
verdad por ejemplo:

¡Adiós!

¿Qué hora es?

Mañana lloverá

5 − 4x = 1
No es una proposición. Pero, si sustituimos x por
cualquier número, ella se convierte en proposición. A este tipo de frases se
les llama funciones proposicionales.
NOTAS:
1. Las proposiciones las notaremos con las letras , , etc.
2. Aquellas proposiciones que no se pueden descomponer en dos o más
proposiciones; se llaman proposiciones simples.
3. Las proposiciones que están formadas por dos o más proposiciones simples por
medio de conectores llamados lógicos se llaman proposiciones compuestas.
4. Si una proposición es verdadera se denotará por la letra “V” o el “1” y si es falsa
se denotará por “F” o por el “0”.
1.3. Conectores Lógicos
1. Negación
Dada una proposición , se puede obtener otra proposición anteponiendo la palabra
"no" o "no es cierto que". El símbolo utilizado es ~ que significa "no". Por
ejemplo: Sea la proposición
≡ ”Estoy estudiando"; La negación de esta
proposición simple será ~ ≡ "No estoy estudiando" o también "No es cierto que
estoy estudiando".
La negación aplicada a una proposición simple nos da una nueva proposición
simple. Se observa que: Si
negación ~
es V, la negación ~ es F; mientras que, si
es F; la
es V. Por medio de esta regla podemos construir la tabla de
verdad de la negación; esto es:
ESPOCH – Escuela de Ingeniería en Sistemas
2
Unidad I: Lógica Matemática
Juan Miguel Olalla
~
V
F
F
V
2. Conjunción
La conjunción es el conector que relaciona dos proposiciones simples para formar
una compuesta, con la letra "y" cuyo símbolo es ∧. Por tanto
≡ "Juan es bueno" y
Por ejemplo: Sean las proposiciones simples
feliz", la conjunción de
y
será
∧
∧
se lee " y ".
≡ "María es
≡ "Juan es bueno y María es feliz”
Por la naturaleza del nexo "y" para que una proposición compuesta sea verdadera,
necesariamente las dos proposiciones simples deben serlo. Para los demás casos
será falsa. Por tanto la tabla de verdad en este caso es:
∧
V
V
V
V
F
F
F
V
F
F
F
F
3. Conjunción negativa
La conjunción negativa “ni… y ni…” asociada a las proposiciones
resultado una nueva proposición compuesta
es verdadera cuando
y
↓
que se lee: “ni
y
da como
y ni ”, la cual
es falsa, en los casos restantes es falsa. Su tabla de
verdad es:
↓
V
V
F
V
F
F
F
V
F
F
F
V
ESPOCH – Escuela de Ingeniería en Sistemas
3
Unidad I: Lógica Matemática
Juan Miguel Olalla
4. Disyunción
La disyunción es un conector lógico que relaciona dos proposiciones simples para
formar una proposición compuesta; por medio del símbolo ∨ , entonces, se obtiene
∨
la proposición compuesta
que se lee " o ". Por ejemplo: Sea p ≡ " 3 + 2 =
5" y q ≡ "4 es un número par"; entonces
La disyunción permite una elección, así o
∨
≡ “3 + 2 = 5 o 4 es un número par”.
es V, o
es V o son ambas V a la vez.
Luego si decimos "Londres es capital de Venezuela o 4 es un número par" no
estamos mintiendo puesto que para que la proposición disyuntiva sea verdadera
debemos aceptar que la primera parte es verdadera o que la segunda parte es
verdadera o que ambas son verdaderas.
Según esto se tiene la siguiente tabla de verdad:
∨
V
V
V
V
F
V
F
V
V
F
F
F
5. Disyunción exclusiva
La disyunción exclusiva “…o, pero no ambos” asociada a las proposiciones
da como resultado una nueva proposición
cual es falsa cuando
y
∨
y
y se lee “ o , pero no ambas”, la
son iguales, mientras que en los demás casos es
verdadera. Su tabla es:
∨
V
V
F
V
F
V
F
V
V
F
F
F
ESPOCH – Escuela de Ingeniería en Sistemas
4
Unidad I: Lógica Matemática
Juan Miguel Olalla
6. Condicional o implicación
Sean
y q proposiciones, el conector lógico condicional o implicación da una
→
nueva proposición
que se lee "
entonces ". La proposición
tanto, como (~ ) ∨
→
entonces
" o " condición
es la proposición (~ ) ∨
es igual a la proposición
" o "si
por definición. Por
→ , sus tablas de verdad son las
mismas, entonces, se tiene que:
~
(~ ) ∨
p
q
p→q
V
V
F
V
V
V
V
V
F
F
F
V
F
F
F
V
V
V
F
V
V
F
F
V
V
F
F
V
7. Bicondicional o bi-implicación
Sean
y
dos proposiciones, si relacionamos estas proposiciones con el conector
lógico bicondicional obtenemos la proposición
↔
que se lee " si y sólo si ".
Esta proposición
↔
condicional
condicional ”. Se deja como tarea comprobar que la tabla de
y
verificación de
↔
es la proposición ( → ) ∧ ( → ) o en otras palabras “
es la siguiente:
↔
V
V
V
V
F
F
F
V
F
F
F
V
Por las reglas anteriores se puede determinar tablas de verificación y los valores de
verdad de proposiciones compuestas en las cuales aparecen varios conectores
lógicos.
ESPOCH – Escuela de Ingeniería en Sistemas
5
Unidad I: Lógica Matemática
Juan Miguel Olalla
Las tablas vistas anteriormente las podemos resumir en una sola, la misma que es:


∨
∨
↓
∧
→
q→p
↔
V
V
F
F
V
F
F
V
V
V
V
V
F
F
V
V
V
V
F
F
V
F
F
V
V
F
V
V
V
F
V
F
F
F
F
V
V
F
F
F
F
V
V
V
1.4. Construcción de tablas de verdad
En la construcción de tablas de verdad debemos considerar lo siguiente:
1. Determinar el número posibles de combinaciones. Si hay proposiciones, el número
de combinaciones será 2
2. Se debe procurar respetar el orden de los valores de verdad dentro de la tabla así
por ejemplo: Si hay tres proposiciones, el número de combinaciones serán 2 = 8;
por lo tanto para primera proposición serán 4 verdaderas y 4 falsas; para la segunda
proposición 2 verdaderas y 2 falsas; para la tercera: una verdadera y la otra falsa.
1.5. Tautologías y contradicciones
1.5.1. Tautologías.- Se dice que una proposición es una tautología, cuando todos los
valores de verdad de la tabla son verdaderos, Por ejemplo:
→ ~ (~
∧
a)
↓
)
V
V V V V
V F
V F
V F
F
F
V V F
F
F
V V
V V
F
F
V
F
F
F
V V
F
F
F
V
V
F
ESPOCH – Escuela de Ingeniería en Sistemas
∨ ~
b)
V V F
F
V
V V F
6
Unidad I: Lógica Matemática
Juan Miguel Olalla
1.5.2. Contradicciones.- Se dice que una proposición es una contradicción, cuando todos
los valores de verdad de una tabla son falsos. Por ejemplo:
a)
(
∧
) ∧ ~
V
V V
F F
V
V F F
V
F
F
F F
V
F
F
F
V
F V F
F
F
F
F V F
∧ ~
b)
V
F V F
1.6. Implicación Lógica (⇒)
Se dice que
implica lógicamente a
, si el resultado de la tabla de verdad es una
tautología. Por ejemplo:
∧
⇒
V V V V V
V F
F
V V
F
F V V
F
F
F
F
F
V
1.7. Equivalencia Lógica (⇔, ≡)
Se dice que P es lógicamente equivalente a Q, si es que ambas proposiciones tienen la
misma tabla de verdad, o que el resultado de la tabla es una tautología. Por ejemplo:
a)
∨( ∧∼ ) ⇔
b)
→
⇔∼
→∼
c)
→
⇔∼
∨
d)
↓
⇔∼
∧∼
ESPOCH – Escuela de Ingeniería en Sistemas
7
Unidad I: Lógica Matemática
Juan Miguel Olalla
1.8. Leyes del Álgebra de proposiciones
Teorema.- Sean ,
i)
y
proposiciones; las siguientes proposiciones son tautologías:
Propiedad de idempotencia de los conectores ∼, ∧, ∨
a) ∼ (∼ ) ⇔
ii)
b) ( ∧ ) ⇔
c) ( ∨ ) ⇔
Propiedad conmutativa de los conectivos ∧, ∨
a) ( ∨ ) ⇔ ( ∨ )
b) ( ∧ ) ⇔ ( ∧ )
iii)
Propiedad asociativa de los conectores ∧, ∨
a) [( ∨ ) ∨ ] ⇔ [ ∨ ( ∨ )]
b) [( ∧ ) ∧ ] ⇔ [ ∧ ( ∧ )]
iv)
Propiedad distributiva de los conectores ∧, ∨
a)
[ ∧ ( ∨ )] ⇔ [( ∧ ) ∨ ( ∧ )]
b) [ ∨ ( ∧ )] ⇔ [( ∨ ) ∧ ( ∨ )]
v)
Leyes de Morgan para las proposiciones
a) ∼ ( ∨ ) ⇔ ∼ ( ) ∧∼ ( )
b) ( ∧ ) ⇔ ∼ [∼ ( ) ∨∼ ( )]
vi)
Ley de absorción
a)
∨( ∧ ) ⇔
b) ( ∧ ) →
c) ( ∧ ) →
vii)
viii)
Ley de identidad
a)
∨
⇔
∧
⇔
b)
∨
⇔
∧
⇔
Ley de complemento
a)
ix)
∨∼
⇔
∧∼
⇔
Otras leyes
a)
→
⇔∼
∨
b)
↓
⇔∼
c)
↔
⇔ (∼
∨ ) ∧ (∼
∨ )
d)
∨
⇔ (∼
∨ ) ∧ (∼
∨ )
∧∼
ESPOCH – Escuela de Ingeniería en Sistemas
8
Unidad I: Lógica Matemática
Juan Miguel Olalla
1.9. Ejercicios Resueltos
1. Hallar la tabla de verificación de las siguientes proposiciones compuestas, siendo ,
y
proposiciones simples:
a) ((~p) ∧ q) → (p ∨ (~q))
~
((~ ) ∧ )
~
( ∨ (~ ))
((~ ) ∧ ) → ( ∨ (~ ))
V
V
F
F
F
V
V
V
F
F
F
V
V
V
F
V
V
V
F
F
F
F
F
V
F
V
V
V
b) Supongamos que p es verdadera, q falsa y r verdadera; determinar el valor de
verdad de la siguiente proposición compuesta: [(p ∨ (~q)] ↔ [q ∧ r]
∨ (~ )
~
V
F
V
V
V
∧
[( ∨ (~ )] ↔ [ ∧ ]
F
F
c) Hallar el valor de verdad de (p ∧ q) ∨ r
∧
( ∧ )∨
V
V
V
V
V
V
V
F
V
V
V
F
V
F
V
V
F
F
F
F
F
V
V
F
V
F
V
F
F
F
F
F
V
F
V
F
F
F
F
F
ESPOCH – Escuela de Ingeniería en Sistemas
9
Unidad I: Lógica Matemática
Juan Miguel Olalla
d) Hallar el valor de verdad de [p ∨ (q ∧ r)] ↔ [(p ∨ q) ∧ (p ∨ r)]
∧
∨( ∧ )
∨
∨
1
( ∨ )∧( ∨ )
1↔2
2
V
V
V
V
V
V
V
V
V
V
V
F
F
V
V
V
V
V
V
F
V
F
V
V
V
V
V
V
F
F
F
V
V
V
V
V
F
V
V
V
V
V
V
V
V
F
V
F
F
F
V
F
F
V
F
F
V
F
F
F
V
F
V
F
F
F
F
F
F
F
F
V
ESPOCH – Escuela de Ingeniería en Sistemas
10
Unidad I: Lógica Matemática
Juan Miguel Olalla
1.10. Ejercicios Propuestos
1. Escribir cinco frases de proposiciones y cinco frases que no sean proposiciones.
2. Determinar cuáles de las siguientes frases son proposiciones
a) 3 + 2 = 5
b) + 1 = 4
c) ¡Hola!
d) Yo estudio
3. Negar las siguientes proposiciones.
a) Diana es modista
b) 12 es un número par
c) estas dos rectas son paralelas
d) todos los hombres son mortales
e) algunos deportistas son ciclistas
f) ningún loro vive en el polo norte
4. Sean
, ,
y
proposiciones. Calcular el valor de verdad de las siguientes
proposiciones suponiendo que
y
son verdaderas y que
y son falsas:
a)
(p ∧ q) → r
b) (r ∨ s) → q
c)
q ↔ (p ∧ s)
d) p → ~(r ∧ s)
e)
(q → s) → r
f)
g) (q ∨ r) ∧ (p ∨ s)
i)
~[(r → p) ∨ (s → q)]
~(p ↔ q)
h) (r → s) ∧ (p ∧ q)
j)
[(r → q) ↔ (~p ↔ r)]
5. Utilizando tablas de verificación determinar cuáles de las siguientes proposiciones
son tautologías:
a)
~(p ∧ ~p)
b) (p → q) ↔ (~q → ~p)
c)
(p → q) → (~p ∨ q)
d) [(p → q) ∧ p] → q
e)
[(p → q) ∧ ~q] → ~p
f)
g) [(p → q) ∧ (q → r)] ↔ (p → r)
~(p → q) ↔ (p ∧ ~q)
h) [p → (q → r)] ↔ [(p → q) → r]
6. Utilizando las leyes del álgebra proposicional, simplifique las siguientes
proposiciones:
a) [ ∧ (~p → q)] →
b) (p → q) ∧ p →
c) ~( ∧ ) ↔ ( → ~ )
ESPOCH – Escuela de Ingeniería en Sistemas
11