School Work">
Matematicas Discretas: Logica
Matematicas Discretas: Logica
Matematicas Discretas: Logica
Lgica
Un idad I .Lgica
Conte nido:
Matematicas DiscretasI
Lgica
Matematicas DiscretasI
Lgica
Es usual distinguir entre las oraciones y las proposiciones que expresan. Dos oraciones, que son
claramente distintas porque constan de diferentes palabras ordenadas en distintas formas, pueden
en el mismo contexto tener el mismo significado y emplearse para afirmar la misma proposicin.
Pedro conduce el auto.
El auto es conducido por Pedro.
son dos oraciones diferentes, porque la primera contiene cuatro palabras y mientras que la segunda
contiene seis. Pero las dos tienen el mismo significado. Se utiliza el trmino proposicin para
referirse al contenido que ambos enunciados afirman [7].
La diferencia entre enunciados y proposiciones puede entenderse mejor si se hace notar que una
oracin es siempre oracin de un lenguaje particular en el cual se emite, mientras que las
proposiciones no son propias de un lenguaje. Las cuatro oraciones:
It is raining.
Est lloviendo.
Il pleut.
Es regnet.
ciertamente son diferentes, porque estn escritas en lenguajes diferentes: ingls, espaol, francs y
alemn, pero tienen el mismo significado, y en un contexto apropiado se pueden usar para afirmar la
proposicin de la cual cada una es una formulacin distinta.
Los trminos proposicin y enunciado no son exactamente sinnimos, pero en el contexto de la
investigacin lgica se usan en un sentido muy parecido. Algunos autores prefieren el trmino
enunciado al de proposicin [7].
Una proposicin es un teorema de menor generalidad o importancia. Se pueden utilizar letras
maysculas o minsculas, en este texto, se utilizan minsculas como p, q, o r, para denotar las
proposiciones. Por ejemplo:
p: 9 + 5 = 14 .
q: Ciudad Jurez es la capital de Chihuahua.
r: El nmero de tomos en el universo es 1075.
s: Si x es un nmero positivo real y x 2=9, entonces x=3.
De lo anterior, p es una proposicin verdadera, q es falsa; r puede ser verdadera o falsa, pero no
ambas; y s es proposicin verdadera.
Para entender mejor qu es una proposicin, a continuacin se listan algunos enunciados que no son
proposiciones:
u: Entrega tu tarea!
v: Si x 2=9, entonces x=3.
w: Es divertido este curso?
El enunciado v no es una proposicin porque la variable x no se especifica. Si x fuera un nmero
real positivo, entonces la proposicin v sera verdadera, pero si x fuera -3, entonces sera falsa. Por
ltimo, u y w no son enunciados declarativos.
Ejercicio 1. Escriba tres proposiciones simples.
Matematicas DiscretasI
Lgica
Ejercicio 2. Indique la razn por la cual las siguientes expresiones no son proposiciones:
a) Vamos al cine?
b) Prstame tu calculadora.
c) Presione ENTER para finalizar.
d) Enciende la computadora.
Las compuertas lgicas son la base para el desarrollo de circuitos digitales ms complejos.
Las compuertas lgicas son la base para el diseo de sistemas digitales.
c) Si las compuertas lgicas son la base para el diseo de circuitos digitales de mediana escala de
integracin, entonces se deben estudiar primero antes de hacer diseos con ellas.
Las proposiciones simples son:
? Las compuertas lgicas son la base para el diseo de circuitos digitales de mediana escala de
integracin
? Las compuertas lgicas se deben estudiar primero antes de hacer diseos con ellas.
d) Un programa es legible solamente si est bien estructurado.
Las proposiciones simples son:
?
?
Un programa es legible
Un programa est bien estructurado
Matematicas DiscretasI
Lgica
Ejercicio 3: Cules son las proposiciones simples de las siguientes proposiciones compuestas?
a) El nmero 7 es impar y el nmero 8 es par.
b) La lgica es una disciplina que estudia la estructura, el fundamento y el uso de las expresiones del
conocimiento humano.
c) Los programas son formulaciones concretas de algoritmos abstractos basados en ci ertas
representaciones y estructuras de datos.
p : El lpiz no se quebr
La negacin de cualquier enunciado verdadero es falsa y la negacin de cualquier enunciado falso es
verdadera. La negacin de un enunciado se puede expresar prefijando la frase no, es falso que, o
no es el caso que.
1.2.2. Conjuncin
Sean p y q dos proposiciones. Se define la conjuncin de p y q, denotada con p ? q, como la
proposicin que es verdadera cuando ambas, p y q, sean verdaderas, y es falsa, cuando p o q, o ambas
sean falsas. [5]. Por ejemplo:
p: El carro est descompuesto
q: La escuela est lejos
La conjuncin de p y q es:
p ? q: El carro est descompuesto y la escuela est lejos
La conjuncin de dos enunciados se puede formar colocando la palabra y entre ellos: los dos
enunciados as combinados se llaman conyuntos. Otro smbolo que se puede utilizar para
representar una conjuncin es el punto ?.
Matematicas DiscretasI
Lgica
Matematicas DiscretasI
Lgica
p? q
p? q
a) Conjuncin
b) Disyuncin
c) Negacin
p ? q
( p ? q ) ? r
______
______
______
______
Matematicas DiscretasI
Lgica
1.4. Condicionales
1.4.1. Condicional
La implicacin condicional p ? q (si p entonces q) significa que la veracidad de p implica la
veracidad de q. Es decir, si p es verdadera, entonces q debe ser verdadera. La nica manera de que
esto falle es que p sea verdadera cuando q es falsa. La proposicin si p entonces q tambin se lee p
implica q.
La proposicin p se denomina hiptesis o antecedente y la proposicin q, conclusin o consecuente. La
hiptesis es la clusula que sigue al condicional si. La formulacin si p entonces q destaca la
hiptesis, mientras que la formulacin p solo si q subraya la conclusin.
Por ejemplo, considere la proposicin Si todos los alumnos estudian (p) entonces aprueban el
examen (q). Si no estudian no aprueban, la proposicin es cierta. Si no estudian no hay forma de
argumentar que la afirmacin es falsa. Si estudian y no aprueban el examen, entonces la proposicin
es falsa. Por ltimo, si estudian y aprueban el examen la proposicin es verdadera. La figura 1.2
muestra la tabla de verdad de la implicacin condicional.
p
p? q
La implicacin entre dos proposiciones p, q es verdadera en todos los casos menos en aquel en el que
el antecedente es verdadero y el consecuente falso. [1]
La hiptesis es la clusula posterior al condicional si. La clusula slo si es la conclusin. Cuando
significa lo mismo que si. La conclusin expresa una condicin necesaria. La hiptesis expresa
una condicin suficiente.
La formulacin s i p entonc e s q enfatiza la hiptesis, mientras que la formulacin p slo si q
enfatiza la conclusin; la diferencia es slo de estilo.
Ejercicio 6. Escribir en forma simblica cada una de las proposiciones que a continuacin se listan.
1. Si son las 11:00 entonces es hora de empezar la clase.
Las proposiciones simples son:
p: son las 11:00
Matematicas DiscretasI
Lgica
p? q
Matematicas DiscretasI
Lgica
En algunos casos, es posible que dos proposiciones compuestas tengan los mismos valores de verdad,
sin importar los valores de verdad de sus proposiciones constituyentes. Tales proposiciones son
lgicamente equivalentes.
La bicondicional (o equivalencia) es verdadera cuando ambas proposiciones tienen el mismo valor de
verdad y falso cuando ambas tienen diferente valor. La bicondicional se define con la tabla de verdad
(p? q)? (q? p).
Existen dos equivalencias lgicas de cierto inters e importancia, que expresan las relaciones entre
conjuncin, disyuncin y negacin. Puesto que la disyuncin p ? q afirma solamente que por lo menos
uno de los dos disyuntos es verdadero, no se contradice al afirmar que por lo menos uno es falso, sino
solamente afirmando que ambos son falsos. As, afirmar la negacin de la disyuncin p ? q es
lgicamente equivalente a afirmar la conjuncin de las negaciones de p y de q. En smbolos, tenemos
el bicondicional (p? q)? (p? q) cuya verdad lgica queda establecida con la tabla de verdad de la figura
1.4.
p? q
(p ? q)
(p? q)
Figura 1.4 Tabla de verdad de comprobacin de equivalencias lgicas del primer teorema de DeMorgan
De igual manera, al afirmar la conjuncin de p y de q se afirma que ambas son verdaderas, para
contradecirlas necesitamos solamente afirmar que al menos una de ellas es falsa. As, afirmar la
negacin de la conjuncin p? q es lgicamente equivalente a afirmar la disyuncin de las negaciones
de p y de q. En smbolos, se tiene la bicondicional (p ? q) ? p? q, que fcilmente se puede probar
como tautologa. Estos dos bicondicionales tautolgicos se con ocen como los teoremas de DeMorgan y
fueron enunciados por el matemtico y lgico Augusto DeMorgan (1806 -1871). Los teoremas de
DeMorgan pueden tener las siguientes formulaciones en espaol.
La negacin de la disyuncin de dos enunciados es lgicamente equivalente a la conjuncin de las
negaciones de los dos enunciados.
La negacin de la conjuncin de dos enunciados es lgicamente equivalente a la disyuncin de las
negaciones de los dos enunciados [7].
10
Matematicas DiscretasI
Lgica
1.4.3. Recproca
La proposicin q ? p se llama la recproca de p ?
simplemente cambia los papeles de p y q.
Considerando la frase: S i est lloviendo entonces hay nubes en el cielo . Esta es la proposicin
compuesta p ? q donde p= est lloviendo y q= hay nubes en el cielo. Esta es una proposicin
verdadera. Su recproca q ? p se lee: Si hay nubes en el cielo entonces est lloviendo. sta es una
proposicin falsa.
q es la proposicin q ?
p. La proposicin p ?
q es
p? q
q ? p
1.4.5. Tautologas
La proposicin P es una tautologa si P es verdadera para todos los valores de verdad que se
asignen a p1, ..., pn. Una tautologa es una proposicin que es verdadera en cualquier circunstancia.
Aun cuando estas proposiciones son siempre verdaderas, son importantes porque cuando se traten
proposiciones que se ven algo complicadas y se quiera mostrar que son verdaderas, la manera de
hacerlo ser utilizando otras proposiciones que se sabe son siempre verdaderas.
1.4.6. Contradiccin
La proposicin P es una contradiccin si P es falsa para todos los valores de verdad que se asignen
a p1, ...,pn. Una contradiccin es una proposicin que es falsa en cualquier circunstancia.
11
Matematicas DiscretasI
Lgica
p? p
p ? p
1.4.7. Contingencia
Si los valores de verdad de una proposicin son en algunos casos verdaderos y en otros falsos, a la
proposicin se le llama contingencia. [1]
12
Matematicas DiscretasI
Lgica
p: i<2
q:j<5
r: i+j=5
I = 1, S=1
Imprime S
S=S+2I+1
I=I+1
Figura 1.5
13
Matematicas DiscretasI
Lgica
Sn=2 S n-1
y la condicin inicial
S0 = 1
?1
n! ? ?
?n ?n ? 1 ??n ? 2 ?? 2 ? 1
si n ? 0
si n ? 1
Es decir, si n? 1, n! Es igual a producto de todos los enteros entre 1 y n, inclusive 0! se define como
uno. Por ejemplo:
3! = 3 ? 2 ? 1 = 6,
6! = 6 ? 5 ? 4 ? 3 ? 2 ? 1 =720
1.5.3. Ejercicios.
1. Sean p, q y r las proposiciones siguientes:
p: est lloviendo
q: el Sol est brillando
r: hay nubes en el cielo.
Traducir la siguiente notacin lgica, utilizando p, q, r y conectivos lgicos.
a) Est lloviendo y el sol est brillando.
b) Si est lloviendo, entonces hay nubes en el cielo.
c) Si no est lloviendo, entonces el Sol no est brillando y hay nubes en el cielo.
d) El Sol est brillando si y slo si no est lloviendo.
e) Si no hay nubes en el cielo entonces el Sol no est brillando.
2. Sean p, q y r como en el ejercicio 1. Traducir lo siguiente a oraciones en espaol.
a) (p ?
b) (p ?
c) p ?
d) ( p ?
e) (p ?
q) ? r
r) ? q
(q ? r)
(q ? r))
q)? r
14
Matematicas DiscretasI
Lgica
15
Matematicas DiscretasI
Lgica
p1
p2
?
pn
? q
p 1 , p2 , ? , p n
? q
Las proposiciones p1, p2, ..., pn son las hiptesis (o premisas) y la proposicin q es la conclusin. El
argumento es vlido si siempre que p1 y p2 y ... y p n sean todas verdaderas, entonces q deber
tambin ser verdadera; en caso contrario, el argumento no es vlido (es una falacia) [2].
En un argumento vlido, se dice que la conclusin se sigue de las hiptesis. No se dice que la
conclusin sea verdadera; slo se dice que si se garantizan las hiptesis, entonces se tiene
garantizada la conclusin. Un argumento es vlido debido a su forma, no a su contenido.
Ejemplo. Determinar si el siguiente argumento es vlido: p? q, p ?? q
Como primera solucin se construye una tabla de verdad para todas las proposiciones que aparecen
en el argumento.
p
p?
De la tabla se puede observar que siempre que las hiptesis p ? q y p son verdaderas, la conclusin
q tambin lo es, por lo tanto, el argumento es vlido.
En la segunda solucin se puede dejar de lado la tabla de verdad, verificando directamente que
siempre que las hiptesis sean verdaderas, la conclusin tambin es verdadera. Suponiendo que p? q
y p sean verdaderas. Entonces q debe ser verdadera, ya que en caso contrario p ? q sera falsa. Por
tanto, el argumento es vlido.
Ejemplo. Representar el siguiente argumento en forma simblica y determinar si es vlido:
Si Juan obtiene el ascenso se compra un carro.
Juan se compra un carro.
___________________________________________
? Juan obtiene el ascenso
Si se hace:
16
Matematicas DiscretasI
Lgica
p? q
q
______
? p
Si el argumento es vlido, entonces siempre que p ?
q y p sean ambas verdaderas, p debera ser
verdadera. Esto es posible si p es falsa y q es verdadera. En este caso, p no es verdadera; as el
argumento no es vlido.
1.6.1. Inferencias
Inferencia es el proceso por el cual se llega a una proposicin y se afirma sobre la base de una o ms
proposiciones aceptadas como punto inicial del proceso. Para determinar si una inferencia es
correcta, el lgico examina las proposiciones que constituyen los puntos inicial y final de este proceso,
as como las relaciones que existen entre ellos [7].
Tabla 1.5 Equivalencias lgicas
1
2a
b
c
3a
b
4a
b
5a
b
6a
b
c
d
7a
b
8a
b
c
d
9
10a
p? q
?p ? q? ?
Doble negacin
?q ? p ?
?p ? q? ? ?q ? p ?
?p ? q ?? ?q ? p?
??p ? q ?? r ?? ?p ? ?q ? r ??
??p ? q ?? r ?? ?p ? ?q ? r ??
?p ? ?q ? r ??? ??p ? q?? ?p ? r ??
?p ? ?q ? r ??? ??p ? q?? ?p ? r ??
?p ? p? ? p
?p ? p? ? p
? p ? c? ? p
?p ? t ?? t
?p ? c ? ? c
?p ? t ?? p
?p ? p ??
?p ? p??
?p ? q ? ?
?p ? q ? ?
?p ? q ? ?
?p ? q ? ?
?p ? q ? ?
?p ? q ? ?
Leyes conmutativas
Leyes asociativas
Leyes distributivas
Leyes de idempotencia
Leyes de identidad
Tautologa (Verdadera)
Contradiccin (Falsa)
?p ? q ?
?p ? q ?
?p ? q ?
?p ? q ?
?q ? p ?
?p ? q ?
Leyes de De Morgan
Contrapositiva
Implicacin
17
Matematicas DiscretasI
b
11a
b
12a
b
13
14
15
Lgica
?p ? q ? ? ?p ? q ?
?p ? q ? ? ?p ? q ?
?p ? q ? ? ?p ? q ?
??p ? r ? ? ?q ? r ?? ? ??p ? q? ? r ?
??p ? q ?? ?p ? r ?? ? ?p ? ?p ? r ??
?p ? q ?? ??p ? q? ? ?q ? p??
??p ? q ?? r ?? ?p ? ?q ? r ??
?p ? q ? ? ??p ? ? q ? ? c?
En una demostracin una conclusin se admite como correcta considerando que las premisas
(suposiciones, axiomas, hiptesis), y que el razonamiento utilizado para la deduccin de la
conclusin, a partir de las premisas, sigue un conjunto de reglas aceptables de la inferencia lgica.
Estas reglas de inferencia lgica son las estructuras de razonamiento que se consideran correctas, es
decir, son aquellas cuya frmula proposicional asociada es una tautologa.
Las reglas de inferencia son una tcnica o listas de tcnicas que de alguna forma evitan la necesidad
de construir tablas de verdad, especialmente las grandes. Estas reglas ayudan de la siguiente forma:
1. Permiten considerar slo los casos donde todas las hiptesis son verdaderas. Dado que slo se
consideran los renglones de una tabla de verdad donde cada hiptesis tiene un valor
verdadero de uno y no se construye la tabla de verdad.
2. Son fundamentales en el desarrollo de una prueba paso a paso mostrando cmo la conclusin
q lgicamente sigue de la hiptesis p1, p2, p3, ...,pn en una implicacin
?p1 ?
p2 ? p3 ? ... ? pn ?? q
16
17
18
19
20
21
22
?p ? q ?
?p ? q? ? p
?p ? c ? ? p
?p ? ?p ? q ??? q
??p ? q ?? q ?? p
??p ? q ?? p ?? q
p ? ?q ? ?p ? q ??
p?
18
Matematicas DiscretasI
23
24
25a
b
c
26a
b
27a
b
??p ?
??p ?
?p ?
?p ?
?p ?
??p ?
??p ?
??p ?
??p ?
Lgica
q ?? ?q ? r ???
q ?? ?q ? r ???
q ?? ??p ? r ? ?
q ?? ??p ? r ? ?
q ?? ?p ? r ??
q? ? ?r ?
q? ? ?r ?
q ?? ?r ?
q ?? ?r ?
?p ?
r?
?p ? r ?
?q ? r ??
?q ? r ??
?q ? r ?
s ??? ??p ? r ?? ?q ? s ??
s ??? ??p ? r ?? ?q ? s ??
s ?? ? ??q ? s ?? ?p ? r ??
s ?? ? ??q ? s ?? ?p ? r ??
Transitividad de ?
Transitividad de ? o silogismo hipottico
Dilemas constructivos
Dilemas destructivos
P
28
? P? Q
Adicin
P? Q
29
30
31
32
33
34
?P
P
P? Q
?Q
P? Q
Q
? P
P? Q
P
?Q
P? Q
Q? R
?P? R
P
Q
?P? Q
Simplificacin
Modus ponens
Modus tollens
Silogismo disyuntivo
Silogismo hipottico
Conjuncin
19
Matematicas DiscretasI
Lgica
?p ? ?p ? q???
20
Matematicas DiscretasI
Lgica
Otro ejemplo:
Premisa 1.
Premisa 2.
Conclusin.
p? q
Premisa 2:
Conclusin.
?q
La regla de inferencia llamada modus ponendo ponens (PP) permite demostrar q a partir de p? q y p.
El segundo ejemplo se simboliza de la manera siguiente, donde p es la proposicin Victoria estudia
suficiente y q es la proposicin aprobar el examen.
? p? ? q
?p
??q
En cada uno de los ejemplos, la regla modus ponendo ponens permite pasar de dos premisas a la
conclusin. Esta regla de inferencia dice que si se tienen dos proposiciones de la forma p? q y p, se
puede deducir la conclusin q.
El nombre modus ponendo ponens se puede explicar de la siguiente manera: Esta regla de inferencia
es el mtodo (modus), que afirma (ponens) el consecuente, afirmando (ponendo) el antecedente [8].
21
Matematicas DiscretasI
Lgica
?? p
?? p
p
El auto enciende
El auto funciona adecuadamente
p? q
q
? p
La regla modus tollendo tollens permite pasar de dos premisas: (a) a una proposicin condicional, y
(b) una proposicin que niega el consecuente, a una conclusin que niega el antecedente.
Otro ejemplo, se tiene la proposicin condicional:
Si me dan un ascenso, entonces me puedo comprar un carro.
Se niega el consecuente:
No me puedo comprar un carro.
Entonces se puede negar el antecedente:
Por tanto, no me dan el ascenso.
22
Matematicas DiscretasI
Lgica
se puede concluir
o
p
q
_______
?p? q
? q? p
Ejemplo:
Premisa 1.
Premisa 2.
Mara es adolescente
Juan es adulto
p ? q
_______
? p
q
Premisa:
Conclusin:
23
Matematicas DiscretasI
Lgica
que negando (tollendo) un miembro de una disyuncin se afirma (ponens) el otro miembro.
Simblicamente se puede expresar:
De la premisa:
y la premisa:
se puede concluir
o
de la premisa:
y la premisa:
se puede concluir
p? q
p
______
?q
p? q
q
______
?p
24
Matematicas DiscretasI
Lgica
Esta conclusin no dice que me dan el ascenso ni que me voy de vacaciones. Slo dice lo que ocurrira
si me dan el ascenso.
Ejercicio. Qu conclusin se puede sacar por la ley de silogismo hipottico de los conjuntos de
proposiciones siguientes?
1. Si el agua se hiela, entonces sus molculas forman cristales. Si las molculas forman cristales,
entonces el agua aumenta de volumen.
Si el agua se hiela, entonces el agua aumenta de volumen.
2. Si Toms conduce a una velocidad de 50 km/h, entonces en 9 horas habr recorrido 450 km.
Si en 9 horas ha recorrido 450 km, entonces habr recorrido 90 km ms que ayer en el mismo
perodo.
Si Toms conduce a una velocidad de 50 km/h, entonces habr recorrido 90 km ms que ayer en el
mismo periodo.
25
Matematicas DiscretasI
Lgica
10
15
20
25
30
Extraterrestres
16
32
26
Matematicas DiscretasI
Lgica
como se quera comprobar. De esta forma, (I) se cumple. Por el principio de induccin matemtica
todas las proposiciones p(n) son verdaderas. En particular se tiene que A(60)=259.
Ejemplo 2.
naturales.
Se dice que Gauss resolvi, siendo un nio, la suma de los primeros 100 nmeros
27
Matematicas DiscretasI
Lgica
Adems, hay 50 sumas, que es la mitad de 100, cuya suma es 101. Entonces, (101)(50) = 5050, y este
es el resultado que me pide el maestro.
El enunciado clsico de un problema como el anterior es:
Demostrar por induccin lo siguiente:
n
i?
i ?1
n?n ? 1 ?
2
Siguiendo el mtodo de induccin, se tienen que hacer los dos pasos. Esto es,
Paso 1 (B). Primero se verifica que la proposicin se cumple con n=1. Se tiene:
1
i ? 1? ? ? A
i ?1
1?1 ? 1? 2
? ? 1? ? ? B
2
2
Como A y B son iguales, se cumple para n=1.
Paso 2 (I). Segn el mtodo de induccin matemtica, se tiene que suponer que la proposicin es
vlida para un nmero n= k.
Si de ah se deduce, siguiendo una secuencia vlida de argumentos, que la proposicin es vlida para
el valor n= k+1, se puede afirmar que dicha proposicin es vlida para cualquier nmero n. Siguiendo
este mtodo, se supone cierta la proposicin para n=k, esto es, lo que se debe suponer es que:
k
i?
i ?1
k ?k ? 1?
, es vlida . . . . . . . . . C
2
Es necesario tratar de comprobar que la proposicin es vlida para n= k+1, a partir de (C) n=k. Pero,
qu significa deducir que es vlida para n=k+1?
Significa que, utilizando argumentos vlidos, que en este caso son algebraicos, se llegue de:
k
i?
i ?1
k ?k ? 1 ?
2
k ?1
i ?1
i?
?k ? 1??k ? 2?
2
Se tiene lo siguient e:
k ?1
i ?1
i?
i ?1
i?
k ?1
i? k? 1
Siguiendo con el mtodo de induccin matemtica, gracias al paso inductivo, se puede escribir:
28
Matematicas DiscretasI
Lgica
k ?1
k ?k ? 1?
?
2
i ?1
k?1
i? k ? 1
k ?k ? 1?
? ?k ? 1?
2
i?
i? k ? 1
La igualdad anterior se puede establecer ya que se est suponiendo que la proposicin se cumple
para n=k.
Al obtener el comn denominador, se tiene que:
k?1
k ?k ? 1?? 2?k ? 1?
2
i?
i ?1
i?
i ?1
?k ? 1??k ? 2?
2
? ?2i ? 1?? n
i ?1
Paso 1. (B)
1
Para n=1,
? ?2i ? 1?? 1
?1
i ?1
Paso 2. (I)
Para n=k
k
? ?2i ? 1?? k
i ?1
Para n=k+1
29
Matematicas DiscretasI
Lgica
k ?1
i ?1
? k ? ?2k ? 1? ? k 2 ? 2k ? 1
2
? ?k ? 1?
1.8. Referencias
[1] J. L Ramrez, M. Jurez y L. Villalobos. Curso propedutico de Matemticas. CENIDET.
Cuernavaca, Mor., Junio de 1994.
[2] R. Johnsonbaugh. Matematicas Discretas. Ed. Prentice Hall. Cuarta edicin. Mxico, 1999.
ISBN:970-17-0253-0.
[3] E. Scheinerman. Matematicas Discretas . Ed. Thomson Learning. Mxico, 2001. ISBN 970-686071 -1.
[4] P. Fletcher, H. Hoyle y C. W. Patty. Foundations of Discrete Mathematics. Ed. PWS-KENT.
Boston, 1991. ISBN 0-534-98381-2 (International Studen Edition)
[5] C. Liu. Elementos de Matemticas Discretas. Ed. McGraw -Hill. Segunda Edicin. Mxico, 1995.
ISBN 970-10-0743-3.
[6] K. Ross y C. R. B. Wright. Matemticas Discretas. Ed. Prentice Hall. Segunda Edicin. Mxico,
1990. ISBN 968-880-180-1.
[7] I. M. Copy y C. Cohen. Introduccin a la Lgica. Ed. Limusa. Octava edicin, Mxico, 1997. ISBN
968 -18-4882-9.
[8] P. Suppes y S. Hill. Introduccin a la lgica matemtica. Ed. Revert, S. A., Espaa, 1968.
30