Matematica Discreta

MATEMATICA DISCRETA
Prof: Santiago Domingo
Moquillaza Henríquez

Calculo Proposicional
Ejercicios:
1)Demuestre que T ⋀ S puede deducirse de las premisas
p -> q , q -> ~r , r , p ⋁ (T ⋀ S)
1) p -> q
2) q -> ~r
3) p -> ~r
4) r -> ~p
5) r
6) ~p
7) p ⋁ (T ⋀ S)
8) ~p -> (T ⋀ S)
9) (T ⋀ S)

(premisa)
p -> q <-> ~q -> ~p
(premisa)
(silogismo hipotético)
(3, contraposición (15))
(premisa)
(4,5,MP(3))(premisa)
(7,condicional (12))
(6,8,MP)
p->q ⋀ p->q

2) Demuestre que dado p ⋀ q , p -> r ⋀ q , r -> s ⋁ T ,
~s puede deducirse T:
1) p
2) p -> r ⋀ q
3) r ⋀ q
4) r
5) r -> s ⋁ T
6) s ⋁ T
7) ~s -> T
8) ~s
9) T

Simplificación Conjuntiva (p ⋀ q -> p)
(premisa)
(1,2,MP)
(Simplificación Conjuntiva)
(premisa)
(4,5,MP)
(6,Condicional)
(premisa)
(7,8,MP)

3) Proporcione la demostración para laimplicación p
-> (q -> s) , (~r ⋁ p) , q -> (r -> s ) es decir usted debe
llegar a la implicancia r -> s
1) ~r ⋁ p
(premisa)
2) r -> p
(1,Condicional)
3) p -> (q -> s )
(premisa)
4) r -> (q -> s )
(2,3,Silogismo Hipotético)
5) ~r ⋁ (q -> s )
(4,Disyuncion
Condicional)
6) ~r ⋁ (~q ⋁ s )
(5,Disyuncion Condicional)
7) q
8) q ⋀ (~r ⋁ ~q ⋁ s ) (6,7,Intersectando)
9) q ⋀ ~r ⋁ q ⋀ ~q ⋁ q ⋀ s (Distribuyendo)
10) q ⋀~r ⋁ F ⋁ q ⋀ s (Falacia)
11) q ⋀ ~r ⋁ q ⋀ s
(Identidad)
12) q ⋀ (~r ⋁ s)
(Distributiva)
13) ~r ⋁ s
(12,Simplificacion)
14) r -> s
(13,Condicional)

Métodos de Demostración:
Método directo o de Hipótesis auxiliar:
Se basa en el principio p -> q si se asume como verdad p se
debe demostrar que q es verdad.
Ejemplo:
Si m y n son números enteros impares entonces su producto
es impar.
p = m y n sonnúmeros enteros impares
q = su producto es impar
m = 2k1 + 1
n = 2k2 + 2

(impar,k1 Є Z+)
(impar,k2 Є Z+)

m*n = (2k1 + 1)(2k2 + 1)
= 4k1k2 + 2k1 + 2k2 + 1
= 2(2k1k2 + k1 + k2 ) + 1

-> impar

Método por Reducción al Absurdo:
Se debe llegar a una falacia, es decir partiendo de un p llegar a un ~p.
Ejemplo
_
Demostrar que √2 es irracional
_
Asumir que √2 es racional.
Si es racional p,q ∈ Z+ / ademásp y q son primos entre si.
_
√2 = p/q
->
elevando al cuadrado
2 = p2/q2
->
2q2 = p2
->
p es par, es decir un divisor de 2
p
p2 es par

->
->

q
p es par

p -> q <-> ~q -> ~p
p es impar
p=2k+1

p=2k1
2k12

->

->

->
->

(Método Indirecto)
p2 es impar
(2k+1) 2 = 4k2 + 4k + 1
par
impar

2q2 = (2k1)2

->

q2 = (4k1)2
2

q es par (es decir divisor de 2)

Entonces se llega a una contradicción dado quep y q
tienen como divisor a 2 por lo tanto p y q no son primos
entre si por lo tanto √2 no es un numero racional.

Método Indirecto:
Se utiliza la contra positiva, a veces conviene demostrar ~q
-> ~p que equivale a demostrar p -> q.
Ejm:
Demuestre que si n es entero y n3 es impar entonces n
es par.
p = n3 es impar
q = n es par
~q
n es impar

->
->

~p
n3+5 es par

Si n es impar se puederepresentar: n=2k1 +1
n3 = (2k1+1) 3+ (8k13+12k12+6k1+1)
n3 + 5 = (8k13+12k12+6k1+1+5)
= (8k13+12k12+6k1+6)
= 2(4k13+6k12+3k1+3)
es par

lqqd.

Método de Demostración por Inducción
Matemática
Consiste en demostrar que si la proposición es verdad para
un valor inicial (paso base). Se asume como verdad la
preposición para un P(k) (hipótesis inductiva) entonces se
debe cumplir P(k+1), esta consecuenciaultima es la que se
debe demostrar, dándole la forma de P(k).

Propiedad del Buen Orden:
Todo conjunto de enteros no negativos tiene un elemento
mínimo.

Inducción Matemática
1) Supongamos que conocemos que P(1) es
verdadera.
2) También P(k) -> P(k+1) para todos los enteros
positivos k.
3) Hay que demostrar P(N).
4) Asume como verdad 1 y 2.
Demostración:
Sea P(n) una proposición abierta con lascondiciones (1) y (2) y sea F=[T Є Z+/P(T) es falsa]
se demostrara por el absurdo.

Por el principio de buen orden todo conjunto que pertenece
a los enteros tiene un elemento mínimo por ejemplo un T Є
conjunto F ahora T ‡ 1 (porque si no estaría en contradicción
con la hipótesis 1) entonces T>1 ; si T>1 -> P(T-1)(por la
propiedad 2 es verdad ) Pero T-1 F -> P(T-1+1) es P(T) es
también verdad por...