Upload
powerbit
View
252
Download
1
Embed Size (px)
DESCRIPTION
matematica
Citation preview
Elementos de Matemtica Discreta
Antonio De Jess Bonilla Bonilla1
Universidad Autnoma de Santo DomingoFacultad de CienciasEscuela de Matemtica
1Profesor titular escuelas Matemtica e Informtica
Agosto del 2015
Parte I
EMD/ABB 1/698
Contenido I
INTRODUCCIN
NOCIONES DE LGICA FORMALIntroduccinClculo proposicionalFormas normalesClculo de predicado
TEORA DE CONJUNTOSConceptos y definicionesOperaciones con conjuntosPropiedades de las operaciones con conjuntosConjuntos numricosDivisibilidad y algoritmos de enterosAlgoritmo de EuclidesFuncin caractersticaEMD/ABB 2/698
Contenido IISucesionesRepresentacin de conjuntos en una computadoralgebras booleanasProducto cartesiano o conjunto productoInduccin y recursin
TEORA DE NMEROS Y COMBINATORIAElementos de conteoPermutaciones: Se toma en cuenta el ordenCombinaciones: No toma en cuenta el ordenCombinaciones con repeticin
CONGRUENCIA, RELACIONES Y FUNCIONESCongruenciaEcuaciones diofnticas linealesCongruencias lineales
EMD/ABB 3/698
Contenido IIIRelacionesRelaciones de equivalenciaRelaciones de ordenFuncionesPrincipio del palomar
INTRODUCCIN A LA PROBABILIDADElementos de probabilidadProbabilidad condicional e independenciaVariables aleatorias
EMD/ABB 4/698
Introduccin I
La matemtica discreta es la rama de la matemtica quetiene por objeto el estudio de conjuntos discretos (finitos oinfinitos numerables). Es lo contrario a la matemticacontinua, que se fundamenta en el conjunto de los reales yque estudia conceptos como lmites, continuidad, etc.
La matemtica discreta estudia objetos como grficas, lgica,etc., cuyos elementos pueden ser contados o tratados uno auno, separadamente. Es decir, la matemtica discreta tienecomo base fundamental al conjunto de los enteros.
El lenguaje que usamos a diario suele ser poco claro y deprecisin dudosa y nuestra forma de pensar a veces se haceconfusa. De aqu que la lgica desde sus inicios se ha
EMD/ABB 5/698
Introduccin II
convertido en una herramienta que tiende a disciplinarnos en eluso del lenguaje y el pensamiento. No es posible concebir elestudio de alguna actividad humana sin entender laimportancia de la lgica en dicho proceso.La lgica junto la teora de conjuntos tocan transversalmentetodas las ramas del saber. La teora de conjuntos juega unpapel importante en la formacin bsica de los futurosprofesionales de las reas de ciencias y tecnologas.
Por qu estudiar Lgica?
EL lenguaje que usamos a diario nos conduce muchas veces aambigedades que permiten hacer interpretaciones distintas ydesde el punto de vista de la lgica, esto es inaceptable. Poresta razn, la ciencia utiliza un lenguaje diferente que evite las
EMD/ABB 6/698
Introduccin III
ambigedades y que sea universal. De aqu que la lgica vienea llenar este vaco, porque aunque utiliza un lenguajesimblico, es ms preciso y exacto que el lenguaje comn.
EMD/ABB 7/698
ContenidoINTRODUCCINNOCIONES DE LGICA FORMAL
IntroduccinClculo proposicionalFormas normalesClculo de predicado
TEORA DE CONJUNTOSConceptos y definicionesOperaciones con conjuntosPropiedades de las operaciones con conjuntosConjuntos numricosDivisibilidad y algoritmos de enterosAlgoritmo de EuclidesFuncin caractersticaSucesionesRepresentacin de conjuntos en una computadoralgebras booleanasProducto cartesiano o conjunto productoInduccin y recursin
TEORA DE NMEROS Y COMBINATORIAElementos de conteoPermutaciones: Se toma en cuenta el ordenCombinaciones: No toma en cuenta el ordenCombinaciones con repeticin
CONGRUENCIA, RELACIONES Y FUNCIONESCongruenciaEcuaciones diofnticas linealesCongruencias linealesRelacionesRelaciones de equivalenciaRelaciones de ordenFuncionesPrincipio del palomar
INTRODUCCIN A LA PROBABILIDADElementos de probabilidadProbabilidad condicional e independenciaVariables aleatorias
EMD/ABB 8/698
Introduccin I
La palabra lgica proviene de la palabra griega LOGOS, quesignifica pensamientos correctos. El adjetivo formal se refierea que la lgica trabaja en base a la razn pura,independientemente de la experiencia que se tenga, es decir,prescindiendo del contenido del pensamiento.
El estudio de la informtica y/o matemtica para cualquierestudiante es mucho ms interesante y provechoso, sipreviamente se le introduce en el mundo de la lgica formal.El manejo del lenguaje lgico y el uso de procedimientoseficientes de razonamiento son elementos que contribuyensignificativamente al desarrollo de algoritmos computacionalesde calidad.
EMD/ABB 9/698
Introduccin II
La lgica tiene por objeto estudiar la validez de losrazonamientos.
EMD/ABB 10/698
ContenidoINTRODUCCINNOCIONES DE LGICA FORMAL
IntroduccinClculo proposicionalFormas normalesClculo de predicado
TEORA DE CONJUNTOSConceptos y definicionesOperaciones con conjuntosPropiedades de las operaciones con conjuntosConjuntos numricosDivisibilidad y algoritmos de enterosAlgoritmo de EuclidesFuncin caractersticaSucesionesRepresentacin de conjuntos en una computadoralgebras booleanasProducto cartesiano o conjunto productoInduccin y recursin
TEORA DE NMEROS Y COMBINATORIAElementos de conteoPermutaciones: Se toma en cuenta el ordenCombinaciones: No toma en cuenta el ordenCombinaciones con repeticin
CONGRUENCIA, RELACIONES Y FUNCIONESCongruenciaEcuaciones diofnticas linealesCongruencias linealesRelacionesRelaciones de equivalenciaRelaciones de ordenFuncionesPrincipio del palomar
INTRODUCCIN A LA PROBABILIDADElementos de probabilidadProbabilidad condicional e independenciaVariables aleatorias
EMD/ABB 11/698
Clculo proposicional I
Empecemos ofreciendo algunas definiciones que sern tiles anuestros propsitos.
Un razonamiento es el proceso mental que nos permiteobtener conclusiones partiendo de declaraciones dadaspreviamente. La lgica trabaja con dos tipos de razonamientos:el razonamiento material que se basa en el estudio de lavalidez de los contenidos de las expresiones tratadas; y elrazonamiento formal que estudia la validez de lasexpresiones construidas basada en la razn pura y mediantereglas formales establecidas.
EMD/ABB 12/698
Clculo proposicional II
En el lenguaje ordinario utilizamos normalmente cuatro tiposde oraciones: declarativas, interrogativas, exclamativas eimperativas. De estas, nos interesa trabajar bsicamnete conlas declarativas.Una proposicin es una oracin declarativa, de la cual sepueda afirmar que su contenido es verdadero o falso, pero noambas cosas a la vez. Es decir, las proposiciones tienen unnico valor de verdad. Se llama valor de verdad de unaproposicin a la verdad o falsedad de la misma.
Por ejemplo, las oraciones siguientes son proposiciones:
1. Pedro es inteligente y estudioso
2. Bogot es la capital de Colombia
3. Hoy est lloviendo
EMD/ABB 13/698
Clculo proposicional III
Las proposicones pueden ser: simples (atmicas) ocompuestas (moleculares). Se llaman proposicionessimples aquellas que constan de slo un sujeto y slo unpredicado y debe ser afirmativa. Se llaman proposicionescompuestas aquellas que estn formadas por dos o msproposiciones simples enlazadas entre si por medio de ciertoselementos llamados operadores o conectivas lgicas (no,y, o, si . . . , entonces . . . , si y slo si ).Ejemplos de proposiciones simples.
1. Lima es la capital de Per.
2. 9 es un nmero primo.
3. Hoy est lloviendo.
4. Un tringulo tiene tres lados.
EMD/ABB 14/698
Clculo proposicional IV
La proposicin Juan no es artista no es una proposicinsimple por ser un juicio de otro juicio.
Ejemplos de proposiciones compuestas.
1. 2 es un nmero primo y par.
2. Felipe es inteligente y afortunado.
3. Juan es profesor o artista.
4. Andrs y Antonio son deportistas.
5. Si un tringulo es equiltero, entonces esissceles.
6. O Luis es militar o es mdico.
EMD/ABB 15/698
Clculo proposicional V
variable proposicional: es un smbolo que contiene unaproposicin y generalmente se representa por letrasminsculas como p, q, r, s, t, etc.
Por ejemplo, consideremos las proposiciones:
p: 2 es un nmero primo
q: 2 es un nmero par
La proposicin: 2 es un nmero primo y par puede ser escritacomo: p y q.De la misma manera, la proposicin: 2 no es un nmero primoni par puede escribirse como: no p y no q.
EMD/ABB 16/698
Clculo proposicional VI
Operador mondico: es aquel que afecta solamente a unaproposicin atmica. La negacin es el nico operadormondico y lo simbolizaremos por .Operador didico: es aquel que afecta a dos proposicionesatmicas o moleculares.
Tablas de verdad: Son arreglos de filas y columnas donde serepresentan todas las combinaciones posibles de los valoresde verdad de las proposiciones simples que forman lasproposiciones compuestas y el valor de verdad de cadacombinacin.Negacin
EMD/ABB 17/698
Clculo proposicional VII
La negacin de una proposicin se obtiene anteponiendo a laproposicin las expresiones: Es falso que, No es verdad queo insertando la partcula no en la proposicin cuando seaposible.
Si una proposicin es verdadera, su negacin es falsa yviceversa.
La tabla de verdad de la negacin es
p pV FF V
EMD/ABB 18/698
Clculo proposicional VIII
Conjuncin
La conjuncin es una proposicin compuesta formada por dosproposiciones simples, enlazadas por el operador y () y quees verdadera slo cuando las dos proposiciones sonverdaderas; en cualquier otro caso es falsa.La tabla de verdad de la conjuncin es:
p q p qV V VV F FF V FF F F
EMD/ABB 19/698
Clculo proposicional IX
Disyuncin inclusiva
La disyuncin inclusiva es una proposicin compuesta formadapor dos proposiciones simples, enlazadas por el operador o() y que es falsa slo cuando ambas proposiciones son falsas;en cualquier otro caso es verdadera. A esta disyuncin tambinse le llama disyuncin dbil.La tabla de verdad de la disyuncin inclusiva es:
p q p qV V VV F VF V VF F F
EMD/ABB 20/698
Clculo proposicional X
Disyuncin exclusiva
La disyuncin exclusiva es una proposicin compuestaformada por dos proposiciones simples, enlazadas por eloperador o...o (Y) y que es falsa slo cuando ambasproposiciones tienen el mismo valor de verdad; en cualquierotro caso es verdadera. A esta disyuncin se le llamadisyuncin fuerte.La tabla de verdad de la disyuncin exclusiva es:
p q p Y qV V FV F VF V VF F F
EMD/ABB 21/698
Clculo proposicional XI
Condicional
La implicacin o condicional es una proposicin compuestaformada por dos proposiciones simples, enlazadas por eloperador Si ... entonces ... (). En esta conectiva hay quedistinguir dos partes:
Si ...: recibe el nombre de antecedente o hiptesis
entonces ...: recibe el nombre de consecuente o conclusin
En muchas ocasiones el Si y el entonces estnsobreentendidos o sustituidos por otros trminos equivalentes.La condicional es falsa slo cuando el antecedente es
EMD/ABB 22/698
Clculo proposicional XII
verdadero y el consecuente es falso; en cualquier otro caso esverdadera.La tabla de verdad de la condicional es:
p q p qV V VV F FF V VF F V
En p q decimos que p es condicin suficiente para q y que qes condicin necesaria para p.
Bicondicional o doble condicional
EMD/ABB 23/698
Clculo proposicional XIII
La bicondicional o doble condicional es una proposicincompuesta formada por dos proposicones simples, enlazadaspor el operador ... si y slo si ... () y que es verdadera slocuando ambas proposiciones tienen el mismo valor de verdad;en caso contrario es falsa.
La tabla de verdad de la bicondicional es:
p q p qV V VV F FF V FF F V
EMD/ABB 24/698
Clculo proposicional XIV
EL nmero de filas en una tabla de verdad viene dado por 2n,donde n es la cantidad de proposiciones simples en laproposicin compuesta. Para construir todas lascombinaciones posibles de valores de verdad de lasproposiciones simples, en la primera columna se alternan losvalores de verdad V y F en cantidad de 2n1 cada uno. En lasegunda columna, se alternan en cantidad de 2n2, y assucesivamente, hasta llegar a la ltima columna en que sealternan en cantidad de 20.
Ejemplo 1
La tabla de verdad de p p es
EMD/ABB 25/698
Clculo proposicional XV
p p p pV F VF V V
Ejemplo 2
La tabla de verdad de (p q) q es
p q p q (p q) qV V V VV F F VF V F VF F F V
EMD/ABB 26/698
Clculo proposicional XVIEjemplo 3
La tabla de verdad de (p q) (p q) es
p q q p q (p q) (p q) (p q) (p q)V V F V F F VV F V F V V VF V F V F F VF F V V F F V
Ejemplo 4
La tabla de verdad de (p q) (p q) es
p q p (p q) (p q) (p q) (p q) (p q)
V V F V V F FV F F F F V FF V V V V F FF F V V V F F
EMD/ABB 27/698
Clculo proposicional XVII
Ejemplo 5
La tabla de verdad de (p q) (r Y q) esp q r r (p q) (r Y q) (p q) (r Y q)V V V F V V VV V F V V F FV F V F F F FV F F V F V FF V V F V V VF V F V V F FF F V F V F FF F F V V V V
Tautologa: es una proposicin compuesta que siempre esverdadera, independientemente de los valores de verdad de lasproposiciones simples que la forman. Los ejemplos 1, 2 y 3 sontautologas.
EMD/ABB 28/698
Clculo proposicional XVIII
Contradiccin: es una proposicin compuesta que siempre esfalsa, independientemente de los valores de verdad de lasproposiciones simples que la forman. El ejemplo 4 es unacontradiccin.Utilizaremos el smbolo T para representar una tautologacualquiera y F para denotar una contradiccin cualquiera.Contingencia: es una proposicin compuesta que no estautologa ni contradiccin. El ejemplo 5 es una contingencia.
Consistente: es una proposicin compuesta que es verdaderapara por lo menos una combinacin de los valores de verdadde las proposiciones simples que la componen. Es evidenteque las contingencias son consistentes, pero las proposicionesconsistentes no necesariamente con contingencias. Lastautologas son consistentes y no son contingencias.
EMD/ABB 29/698
Clculo proposicional XIX
Proposiciones lgicamente equivalentes: dos proposicionescompuestas son lgicamente equivalentes , cuando tienen elmismo valor de verdad para todas las posibles combinacionesde los valores de verdad de las proposiciones simples que lacomponen. Es decir, cuando tienen la misma tabla de verdad.
Ejemplos
Consideremos las siguentes proposiciones. Construyamosalgunas proposiciones compuestas.
p: El frio lleg.q: El viento no sopla.
EMD/ABB 30/698
Clculo proposicional XX
r: Luis est de vacaciones.
Entonces las proposicines:
1. El frio lleg y El viento no sopla, se escribesimblicamente p q.
2. Luis no est de vacaciones o El viento no sopla, seescribe r q.
3. Es falso que (El frio lleg o El viento sopla), se escribe(p q).
4. El frio lleg, El viento sopla y Luis est de vacaciones, seescribe p q r.
EMD/ABB 31/698
Clculo proposicional XXI
5. (El frio lleg y El viento no sopla) o (El frio no lleg y Luisno est de vacaciones), se escribe (p q) (p r).
6. Si El frio lleg, entonces El viento no sopla, se escribep q.
7. El frio lleg si y slo si El viento no sopla, se escribep q.
8. No es cierto que EL frio lleg si y slo si El viento nosopla, se escribe (p q).
9. Luis no est de vacaciones si y slo si El frio no lleg, seescribe r p.
10. Si El frio no lleg o El viento no sopla, entonces El friolleg y El viento no sopla, se escribe (p q) (p q).
EMD/ABB 32/698
Clculo proposicional XXII
Ejemplos
Proposiciones simblicas escritas en lenguaje natural,utilizando p, q y r anteriores :
p (q r) : EL frio lleg o el viento nosopla o Luis est de va-ciones.
p r : El frio no lleg y Luis est devacaciones.
EMD/ABB 33/698
Clculo proposicional XXIII
(p r) q : (El frio no lleg o Luis no es-t de vacaciones) y El vientosopla.
(p r) : No es cierto que (El frio llegy Luis est de vacaciones).
(p q) r : (El frio lleg y El viento so-pla) o Luis no est de vaca-ciones.
EMD/ABB 34/698
Clculo proposicional XXIV
p r : Si El frio lleg, entonces Luisest de vacaciones.
r p : Luis no est de vacacionessi y slo si El frio no lleg.
(p q) (q p) : Si El frio lleg, entonces Elviento no sopla o si El vien-to no sopla, entonces EL friolleg.
Ejercicios 1
1. Suponga que p es una proposicin falsa, q una proposicinverdadera y r, una proposicin falsa. De termine el valorde verdad de las siguientes proposiciones:
EMD/ABB 35/698
Clculo proposicional XXVa. p q b. (p)c. (p q) d. p (q)e. {(p q) (p q)} f. (p q) rg. {(p q) r} h. p (q r)i. (p q r) (p q r) j. (p q) p
2. Considere las proposiciones:p : El pavo es un cuadrpedo.q : Per es un pas africano.r : La yuca es un tubrculo.
Determine el valor de verdad de las proposicionessiguientes:a. p qb. q rc (p q) (p r)d. {p (q r)} {(p q) (p r)}
EMD/ABB 36/698
Clculo proposicional XXVI
3. Construya la tabla de verdad de las siguientesproposiciones y determine cules son tautologas,contradicciones y contingencias:
a. (p q) q b. (p q) pc. {p (p q)} p d. p (p q) pe. (p q) (q p) f. (q p) (q p)g. {(p q) r} p h. p {(p q) r}i. (p q) (p q) j. (p q) (q q)k. {(p (p q)} p l. {p (p q)} qm. (p q) (p q) n. (p q) q
4. Pruebe las siguientes tautologas de uso comn ( reglasde inferencia).
EMD/ABB 37/698
Clculo proposicional XXVII
1. (p q) (p q) De DMorgan (DDM)2. (p q) (p q) De DMorgan (DDM)3. (p q) (q p) Conmutatividad (CONM)4. (p q) (q p) Conmutatividad (CONM)5. p p Doble negacin (DN)6. (p q) (p q) Def. condicional (DEF)7. (p q) [(p q) (q p)] Def. bicondicional (DEF)8. (p q) [(pq) (pq)] Def. bicondicional (DEF)9. [(p q) p] q Modus Ponens (MP)10. [(p q) q] p Modus Tollens (MT)
EMD/ABB 38/698
Clculo proposicional XXVIII
11. [(p q) (q r)] (p r) Transitividad (T)12. (p q) p q Silogismo disy. (SD)13. [(p q)(r s)(pr)] (qs) Dilema const. (DC)14. [(p q) (r s) (q s)]
(p r)Dilema dest. (DD)
15. (p q) p Simplificacin (SIMP)16. p (p q) Adicin (AD)17. p (p p) Tautologa (TAU)18. [p (q r)] [(p q) r] Asociatividad (ASOC)
EMD/ABB 39/698
Clculo proposicional XXIX
19. [p (q r)] [(p q) r] Asociatividad (ASOC)20. (p q) (q p) Transposicin (TRANSP)21. [(p q) r] [p (q r)] Exportacin (EXP)22. [p (qr)] [(pq) (pr)] Distribucin (DIST)23. [p (qr)] [(pq) (pr)] Distribucin (DIST)24. (p q) (p q) Conjuncin (CONJ)25. (p p) p Idempotencia (IDEM)26. (p p) p Idempotencia (IDEM)27. (p F ) p Identidad (IDEN)28. (p T ) p Identidad (IDEN)
EMD/ABB 40/698
Clculo proposicional XXX
29. (p T ) T Dominacin (DOM)30. (p F ) F Dominacin (DOM)31. [p (p q)] p Absorcin (ABS)32. [p (p q)] p Absorcin (ABS)33. (p p) T Inversa (INV)34. (p p) F Inversa (INV)
5. Aplique la distribucin a los enunciados siguientesa. p (q s)b. r (p q)c. s (t p)
EMD/ABB 41/698
Clculo proposicional XXXI
d. (r s) (q r)e. (r s) (q r)f. (r s) (p q)
g. [(p q) (r s)] p qh. (p q) (r s) t (q r)
6. Convierta las siguientes proposiciones en condicionales ydespus aplquele la transposicin (literal ysimblicamente).
a. O hace fro o voy de paseo.
b. Es falso que Lima sea la capital del Per y Madrid no sea lacapital de Espaa.
c. Pizarro conquist el Per y Corts conquist Mxico
EMD/ABB 42/698
Clculo proposicional XXXII
d. Es falso que Alberto sea mdico o ingeniero
e. Es falso que Luis no tenga 25 aos y Carlos no tenga 27aos.
Formas argumentales
En muchos casos se puede determinar, si un razomamiento escorrecto o no en base a experiencias vividas. Sin embargo, enotros casos, decidir si un razonamiento es correcto o no, puederesultar muy complejo. Por tanto, se requiere de una mayorprecisin para determinar cuando el razonamiento es correcto.
Una forma argumental es una proposicin de la forma
(p1 p2 p3 . . . pn) = q
EMD/ABB 43/698
Clculo proposicional XXXIII
op1, p2, p3, . . . , pn ` q,
donde p1, p2, p3,. . . ,pn y q son proposiciones.Es decir, una forma argumental es la representacin simblicade una razonamiento.
A las proposiciones
p1, p2, p3, . . . , pn
se les llama premisas o hiptesis de la forma argumental y ala proposicin q, se le llama conclusin.
Una forma argumental es vlida si y slo si, se obtiene laconclusin, a partir de las premisas dadas previamente.Es decir, si es una tautologa. En caso contrario, es una falacia.
EMD/ABB 44/698
Clculo proposicional XXXIV
Las tablas de verdad son instrumentos de fcil manejo y muypoderosos para probar la validez de razonamientos, sinembargo, no son prcticas cuando el nmero de proposicionessimples aumenta, ya que el nmero de filas de la tablaaumenta exponencialmente.
EMD/ABB 45/698
Deduccin proposicional I
Esto hace que se utilicen procedimientos ms prcticos en laprueba de validez de razonamientos, aunque se requiera demayor capacidad de abstraccin. Uno de estos procedimientoses el de la deduccin proposicional.
Deduccin proposicional
Las tautologas que fueron probadas en el ejercicio 4 seutilizan como reglas de inferencias para permitirnos inferirlgicamente de un conjunto de afirmaciones, otra afirmacin.Es importante sealar que la conclusin debe deducirse delconjunto de premisas aunque no sea directamente. Laspremisas son proposiciones que se consideran siempreverdaderas.
EMD/ABB 46/698
Deduccin proposicional II
Los pasos que se dan en la prueba de validez de unrazonamiento deben estar siempre justificado por alguna de lasreglas de inferencias. Cabe decir que este procedimiento slonos permite probar la validez de razonamientos y el hecho deque no lo hayamos probado, no quiere decir que no se pueda;simplemente que no hemos encontrado la solucin.
Frmulas proposicionales
Una Frmula proposicional se define recursivamente de lasiguiente manera:
a. Una variable proposicional es una frmula proposicional.
EMD/ABB 47/698
Deduccin proposicional III
b. Las proposiciones construidas de frmulas proposicionalesmediante las conectivas: , , , , y los smbolosauxiliares (, ); [,] y {, } son frmulas proposicionales.
Nota. Cuando no haya lugar a confusin, utilizar la palabrafrmula en lugar de frmula proposicional.
Para demostrar (probar) la validez de una formaargumental por deduccin proposicional, los pasosaceptados como vlidos son:
1. En cualquier paso puede ser usado una premisa.
2. Todo paso puede ser sustituido por otro equivalente.
3. En todo paso se puede escribir la conclusin de una regla deinferencia, si sus premisas son pasos previos.
EMD/ABB 48/698
Deduccin proposicional IV
4. Cualquier teorema o propiedad conocida ( reglas deinferencias ) puede ser usada en un paso.
Ejemplos
Probar los siguientes razonamientos mediante deduccinproposicional.
1. p, p q, r q ` rPrueba:
1) p P2) p q P3) r q P4) q de 1) y 2) x SD5) r de 3) y 4) x MT6) r de 5) x DN
EMD/ABB 49/698
Deduccin proposicional V
2. t s, q s, t ` qPrueba:
1) t s P2) q s P3) t P4) s de 1) y 3) x MP5) q de 2) y 4) x MT6) q de 5) x DN
3. p q, q r, r ` pPrueba:
EMD/ABB 50/698
Deduccin proposicional VI
1) p q P2) q r P3) r P4) p r de 1) y 2) x T5) p de 3) y 4) x MT
4. (p q) (r s), s t, t ` pPrueba:
1) (p q) (r s) P2) s t P3) t P4) s de 2) y 3) x MT5) s r de 4) x AD6) r s de 5) x CONM
EMD/ABB 51/698
Deduccin proposicional VII
Prueba (cont.)
7) (r s) de 6) x DDM8) (p q) de 1) y 7) x MT9) p q de 8) x DDM10) p de 9) x SIMP
Pruebe la validez de los siguientes razonamientos mediante ladeduccin proposicional.
EMD/ABB 52/698
Deduccin proposicional VIII
1. Juan no dice la verdad, o Pedro estuvo en casa cerca delas ocho. Si Pedro estuvo en casa cerca de las ocho, el vioa su hermano. Si Pedro vio a su hermano, sabe quienestuvo antes. Luego, si Juan dice la verdad, entoncesPedro sabe quien estuvo antes.
Solucin
Consideremos las formas proposicionales:
p : Juan dice la verdad
q : Pedro estuvo en casa a las ocho
r : Pedro vio a su hermano
EMD/ABB 53/698
Deduccin proposicional IX
s : Pedro sabe quien estuvo antes
El razonamiento o forma argumental viene dado por:
p q, q r, r s ` p sPrueba:
1) p q P2) q r P3) r s P4) q s de 2) y 3) x T5) p q de 1) x DEF6) p s de 4) y 5) x T
EMD/ABB 54/698
Deduccin proposicional X
2. No es cierto que Josefa est con Rosa y Mayra. Si Hoy esLunes, entonces Josefa est con Rosa. Hoy es Lunes.Luego, Josefa no est con Mayra.
Solucin
Consideremos las formas proposicionales:p : Josefa est con Rosaq : Josefa est con Mayrar : Hoy es Lunes
El razonamiento o forma argumental viene dado por:
(p q), r p, r ` qPrueba:
EMD/ABB 55/698
Deduccin proposicional XI
1) (p q) P2) r p P3) r P4) p de 2) y 3) x MP5) p q de 1) x DDM6) q de 4) y 5) x SD
3. Si Felipe es constructor de apartamentos y ngel comprun apartamento, entonces Antonio ganar la causa.Antonio no ganar la causa o ngel es responsable. Perongel no es responsable. Por tanto, Felipe no esconstructor de apartamentos o ngel no compr unapartamento
EMD/ABB 56/698
Deduccin proposicional XII
Solucin
Consideremos las formas proposicionales:
p : Felipe es constructor de apartamentos
q : ngel compr un apartamento
r : Antonio ganar la causa
s : ngel es responsable
El razonamiento o forma argumental viene dado por:
(p q) r, r s, s ` p qPrueba:
EMD/ABB 57/698
Deduccin proposicional XIII
1) (p q) r P2) r s P3) s P4) r de 2) y 3) x SD5) (p q) de 1) y 4) x MT6) p q de 5) x DDM
EMD/ABB 58/698
Ejercicios I
Pruebe los siguientes razonamientos mediante deduccinproposicional.
1. p q, q r, p ` r2. (t s) r, r, t ` s3. r s, p, q r, p q ` s4. (p q), q t, p t, s t ` s5. q t, t r, r ` q6. (p q) (r s), (q s) t, t ` (p r)7. (p q) r, r p ` q8. (p q) (r s), p r, (p s) (r q) ` (q s)9. p q, r q, r s, p t, t r, p p ` s
EMD/ABB 59/698
Ejercicios II
10. p q, q r, s r ` p s11. (p q) r, (q r) s, p ` s12. p, q r, q p, t r ` t13. s p, p t, t r ` s r14. p, p q, p (q r) ` r15. p (q r), p, r ` q16. p q, q ` p17. (p q) r, r, p ` q18. p (q r), p, r ` q19. p q, p q ` p q
EMD/ABB 60/698
Ejercicios III
Pruebe la validez de los siguientes razonamientos mediante ladeduccin proposicional.
20. Si aumentan los precios, entonces aumenta la canastafamiliar bsica. Si aumenta la canasta familiar bsica,entonces disminuye el poder adquisitivo del pesodominicano. Aumentan los precios. Luego, disminuye elpoder adquisitivo del peso dominicano.
21. Si contratan a Juan para desarrollar un sistema y lodesarrolla bien, entonces le pagan buen sueldo. ContratanA juan para desarrollar un sistema y lo desarrolla bien. Portanto,le pagan buen sueldo.
EMD/ABB 61/698
Ejercicios IV
22. Carlos es elegido si y slo si la votacin es numerosa. Lavotacin es numerosa. Carlos no es elegido o Daniel sernombrado. Por tanto, Daniel ser nombrado.
23. Si no hay subsidio del gobierno para la agricultura,entonces hay controles gubernativos sobre la agricultura.Si hay controles gubernativos sobre la agricultura,entonces no hay depresin agrcola. Hay depresin osuperproduccin agrcolas. Es un hecho que no haysobreproduccin. Entonces hay subsidios del gobiernopara la agricultura.
24. El director no estudi bien la mocin o la aprueba. Estuditodo muy bien, de modo que debe aprobar la mocin.
EMD/ABB 62/698
Ejercicios V
25. Habiendo tenido la vctima dinero en el bolsillo, el robo nofue el motivo del crimen. Pero el motivo del crimen fue elrobo o la venganza. Luego, el motivo del crimen fue lavenganza.
26. Si Luis viaja a New york, encontrar a Pedro. Si encuentraa Pedro, Luis recibir la noticia. Luego, Luis recibe lanoticia o no viaja a New york.
27. Carlos es Economista o mdico. Pero si Carlos eseconomista, Carlos dominara las matemticas. Como nodomina las matemticas hay que inferir que Carlos esmdico.
EMD/ABB 63/698
Ejercicios VI
28. Es falso que Mara y Rosa sean buenas programadoras. SiRosa no es buena programadora, es rechazada para eltrabajo. De la misma forma, si Mara no es buenaprogramadora, es rechazada para el trabajo. Si Lily esbuena programadora, no es rechazada para el trabajo. Portanto, Lily no es buena programadora.
29. Si Juan es ingeniero de sistemas, es programador. Perono es programador o es soporte tcnico. No es soportetcnico. Por tanto, no es ingeniero de sistemas.
30. Si Arturo se casa, entonces Mara se enferma. Mara seenferma siempre y cuando Arturo no se haga sacerdote.Por tanto, si Arturo se casa, entonces no se hacesacerdote.
EMD/ABB 64/698
Ejercicios VII
31. Tanto Juan como Pedro son matemticos. Como Juan esmatemtico se tiene que si Pedro es matemtico, entoncesLuis es fsico. Por tanto, Luis es fsico.
32. Si un 1GB de memoria es mejor que nada, comprar msmemoria. Como un 1GB de memoria es mejor que nada,comprar un nuevo computador. Por tanto, si un 1GB dememoria es mejor que nada, entonces comprar un nuevocomputador y ms memoria.
33. Considere las siguientes formas proposicionales:p : El dia est soleado.q : Hace calor.r : Luis est contento.
EMD/ABB 65/698
Ejercicios VIII
Exprese verbalmente los razonamientos siguientes y pruebe lavalidez de los mismos:a. p q, p r ` r qb. p q, p r ` r qc. p (q r), q r ` pd. p (q r), p q, p ` re. (p q) r, r p ` q
EMD/ABB 66/698
ContenidoINTRODUCCINNOCIONES DE LGICA FORMAL
IntroduccinClculo proposicionalFormas normalesClculo de predicado
TEORA DE CONJUNTOSConceptos y definicionesOperaciones con conjuntosPropiedades de las operaciones con conjuntosConjuntos numricosDivisibilidad y algoritmos de enterosAlgoritmo de EuclidesFuncin caractersticaSucesionesRepresentacin de conjuntos en una computadoralgebras booleanasProducto cartesiano o conjunto productoInduccin y recursin
TEORA DE NMEROS Y COMBINATORIAElementos de conteoPermutaciones: Se toma en cuenta el ordenCombinaciones: No toma en cuenta el ordenCombinaciones con repeticin
CONGRUENCIA, RELACIONES Y FUNCIONESCongruenciaEcuaciones diofnticas linealesCongruencias linealesRelacionesRelaciones de equivalenciaRelaciones de ordenFuncionesPrincipio del palomar
INTRODUCCIN A LA PROBABILIDADElementos de probabilidadProbabilidad condicional e independenciaVariables aleatorias
EMD/ABB 67/698
Formas normales I
El procedimiento de la deduccin proposicional tiene lalimitacin de que slo nos permite probar la validez de unrazonamiento, pero no la invalidez. Esto sin embargo, nosignifica que un procedimiento que no hayamos podido probarsu validez sea invlido, sencillamente no lo hemos podidolograr.Para vencer la limitacin de la deduccin proposicional surgenlas llamadas formas normales.Literal: Es una variable proposicional, negada o no negada.Forma normal: es una frmula proposicional formada slo porconjunciones, disyunciones, y negaciones que afecten a unasola variable proposicional.Las formas normales pueden ser:
EMD/ABB 68/698
Formas normales II
- Forma normal disyuntiva (FND)
- Forma normal conjuntiva (FNC)
Forma normal disyuntiva (FND): es una frmulaproposicional F constituida por una disyuncin finita deconjunciones finitas puras. Conjunciones finitas puras sonaquellas cuyos componentes estn formados por una solavariable proposicional negada o no negada (literal). Es decir,
ni=1
mij=1
Lij
,donde cada Lij es un literal.
EMD/ABB 69/698
Formas normales IIIPor ejemplo,
(p q) (r p q) (r p q)
es una forma normal disyuntiva.
A las conjunciones finitas puras de la forma normal disyuntivase les llama sumandos.
Forma normal conjuntiva (FNC): es una frmula Fconstituida por una conjuncin finita de disyunciones finitaspuras. Disyunciones finitas puras son aquellas cuyascomponentes estn formados por una sola variableproposicional negada o no negada (literal). Es decir,
ni=1
mij=1
Lij
,EMD/ABB 70/698
Formas normales IV
donde cada Lij es un literal.Por ejemplo,
(p q r) (p q r) (r t r),
es una forma normal conjuntiva.
A las disyunciones finitas puras de la forma normal conjuntivase les llama factores.
Para hallar cualquiera de las formas normales de una frmula,el procedimiento que se sigue es el siguiente:
EMD/ABB 71/698
Formas normales V
1. Eliminar todo lo que no sea conjuncin o disyuncinmediante las equivalencias
(p q) (p q) y (p q) (p q) (p q).
2. Eliminar las negaciones que afecten a los operadores oconectivas lgicas mediante las leyes de DMorgan.
3. Aplicar las leyes de distribucin, si se necesita.
EMD/ABB 72/698
Formas normales VI
Definicin
El Dual de una proposicin p que contiene solamente , y ,representado por pd, se obtiene al sustituir cada ocurrencia de() de p por () y cada ocurrencia de T (F ) por F (T ).Por ejemplo, las leyes de DMorgan , as como tambin lasleyes inversas son duales.
Principio de dualidad
Sean p y q proposiciones que slo contienen , y . Si p y qson lgicamente equivalentes, entonces pd y qd sonlgicamente equivalentes.
Es decir, si p q entonces pd qd.
EMD/ABB 73/698
Formas normales VII
A una frmula constituida por p p ( afirmacin o negacin deuna variable) se le llama tercio excluido. Observe que es unatautologa. Una frmula constituida por p p (afirmacin ynegacin de una variable al mismo tiempo ) se le llamacontradiccin.La forma normal disyuntiva (FND) nos permite determinar si unrazonamiento dado es consistente o contradictorio. Esconsistente si al menos en un sumando no hay contradiccin;en caso contrario, el razonamiento es contradictorio.
Ejemplo
Determine si el siguiente razonamiento es consistentemediante la FND:
[p (q r)] [(q p) r].
EMD/ABB 74/698
Formas normales VIII
Solucin:
[p (q r)] [(q p) r] [p (q r)] [(q p) r] [p (q r)] [(q p) r] [p (q r)] [(q p) r] [p (q r)] [q p r] (p q r) q p r
Como no hay contradiccin en al menos uno de los sumandos,se tiene que el razonamiento es consistente.
EMD/ABB 75/698
Formas normales
Ejemplo
Determine si el siguiente razonamiento es consistentemediante la FND:
[(p (q r)) (s t)] [(p r) (q p)].
Solucin:[(p (q r)) (s t)] [(p r) (q p)] [(p (q r)) (s t)] [(p r) (q p)] [(p (q r)) (s t)] [(p r) (q p)] [(p (q r)) (s t)] [(p r) (q p)] [(p (q r)) (s t)] [(p r) (q p)] [(p (q r)) (s t)] [(p r) (q p)]
EMD/ABB 76/698
Formas normales
[(p q) (p r) (s t)] [((p r) q) ((p r) p)] [(p q) (p r) (s t)][((p q) (r q)) ((p p) (r p))] (p q) (p r) (s t)(p q) (r q) (p p) (r p) (p q) (p r) (s t) (r q) (p p) (r p) FND
Como no hay contradiccin en al menos uno de los sumandos,se tiene que el razonamiento es consistente.
EMD/ABB 77/698
Ejercicios I
Determine si los siguientes razonamientos son consistentes,mediante la FND.
1. (p q) (p q)2. [(p r) (r q)] (p q)3. (p q) (p q)4. [(p q) (q s)] (p q)5. (q r) [(q p) (r p)]6. [(p (q r)) (q (r p))] p7. [(p r) s] [s (p r)]8. [(p q) r] [(s t) (p q)]9. (p q) [(p r) (q r)]
EMD/ABB 78/698
Formas normales I
Con la forma normal conjuntiva (FNC) podemos determinar siun razonamiento es vlido (tautologa) o invlido. Una formanormal conjuntiva es tautolgica, si en todos sus factores haytercio excluido; en caso contrario es invlida.
Ejemplo
Determinar mediante la FNC si el siguiente razonamiento esvlido o invlido.
(p q) [(q r) p]
EMD/ABB 79/698
Formas normales II
Solucin:
(p q) [(q r) p] (p q) [(q r) p] (p q) [(q r) p] (p q) [(q r) p] (p q) [(q r) p] (p q) p (q r) [(p q p)] (q r) (p q p q) (p q p r) (p q) (p q r)
Como no hay tercio excluido en todos los factores, elrazonamiento (forma argumental) es invlido (falacia).
EMD/ABB 80/698
Formas normales III
Ejemplo
Determinar mediante la FNC si el siguiente razonamiento esvlido o invlido.
(p q) [(q r) p]
Solucin:
(p q) [(q r) p] (p q) [(q r) p] (p q) [(q r) p] (p q) p (q r) (p q p) (q r) (p q p q) (p q p r)
EMD/ABB 81/698
Formas normales IV
Como hay tercio excluido en todos los factores, elrazonamiento es vlido.
EMD/ABB 82/698
Ejercicios I
Determine mediante la FNC si los siguientes razonamientosson vlidos o invlidos
1. (p q) (p q)2. [(p r) (r q)] (p q)3. [(p q) (p s)] (q p)4. [(p q) p] q5. (p q) [(p q) q]6. [p (q r)] [(p q) r]7. (p q) (p q)8. (p q) (q p)9. (p q) (r s)
EMD/ABB 83/698
Ejercicios II
10. (q r) [(p q) (p r)]
EMD/ABB 84/698
ContenidoINTRODUCCINNOCIONES DE LGICA FORMAL
IntroduccinClculo proposicionalFormas normalesClculo de predicado
TEORA DE CONJUNTOSConceptos y definicionesOperaciones con conjuntosPropiedades de las operaciones con conjuntosConjuntos numricosDivisibilidad y algoritmos de enterosAlgoritmo de EuclidesFuncin caractersticaSucesionesRepresentacin de conjuntos en una computadoralgebras booleanasProducto cartesiano o conjunto productoInduccin y recursin
TEORA DE NMEROS Y COMBINATORIAElementos de conteoPermutaciones: Se toma en cuenta el ordenCombinaciones: No toma en cuenta el ordenCombinaciones con repeticin
CONGRUENCIA, RELACIONES Y FUNCIONESCongruenciaEcuaciones diofnticas linealesCongruencias linealesRelacionesRelaciones de equivalenciaRelaciones de ordenFuncionesPrincipio del palomar
INTRODUCCIN A LA PROBABILIDADElementos de probabilidadProbabilidad condicional e independenciaVariables aleatorias
EMD/ABB 85/698
Clculo de predicado I
Cuantificadores
Las herramientas lgicas que hemos visto hasta ahora no sonsuficientes como para expresar en lenguaje lgico todas lassituaciones que se presentan en el lenguaje comn. Loscuantificadores vienen a llenar este vaco porque permitenconstruir proposiciones particularizadas o generalizadas apartir de funciones proposicionales.
EMD/ABB 86/698
Clculo de predicado II
Un smbolo que puede ser sustituido por cualquier objeto deuna coleccin dada de tales objetos se le llama variable.
Sea P (x) una oracin que contiene la variable x, cuyos valorespertenecen a un conjunto D. P recibe el nombre de funcinproposicional o predicado sobre D, si para cada x D, P (x)es una proposicin. Es decir, si al sustituir x por un objetocualquiera de D, P se convierte en una proposicin. Alconjunto D se le llama dominio de discurso o dominio dereferencia o dominio de definicin.Por ejemplo, sea
P (x) : x es un entero primo,donde D = Z+.
EMD/ABB 87/698
Clculo de predicado III
Puesto que P (x) se convierte en una proposicin para cadavalor de x, ya que dependiendo de que x sea primo o no, P (x)es verdadera o falsa. Entonces podemos decir que P (x) esuna funcin proposicional.
Ejemplos
Los siguientes enunciados son funciones proposicionalesa. x2 + 7x+ 12 = 0, donde D = Rb. x es un entero divisible por 3, donde D = Z+
c. x es un beisbolista que di 40 jonrones o ms en lacampaa del 2009 en GL. D = conjunto de beisbolistas
EMD/ABB 88/698
Clculo de predicado IV
Sea P (x) una funcin proposicional con dominio de referenciaD . Las expresiones del lenguaje comn como:Existe un x P (x), Para algn x P (x), corresponden aafirmaciones cuantificadas existencialmente y se escribencomo
x P (x).EL smbolo significa existe y representa el cuantificadorexistencial.La expresin
x P (x)es verdadera si P (x) es verdadera para al menos un x D yfalsa si P (x) es falsa para toda x D.Ejemplo
EMD/ABB 89/698
Clculo de predicado V
La afirmacinx (2x+ 3 = 10), D = R
es verdadera porque existe un nmero real x =7
2para el cual
la proposicin es verdadera.La afirmacin
x (x2 + 1 = 0), D = Res falsa porque no existe un nmero real para el cual laproposicin sea verdadera.
Expresiones como Para cualquier x P (x), Para todo x P (x) ,Para cada x P (x) representan afirmaciones cuantificadasuniversalmente y se escribe como x P (x). El smbolo significa para todo y representa el cuantificador universal.
EMD/ABB 90/698
Clculo de predicado VI
La afirmacinx P (x)
es verdadera si P (x) es verdadera para cada x D y falsa siP (x) es falsa para al menos un x D.Ejemplo
La afirmacinx (x2 + 1 > 0), D = R
es verdadera, porque x2 + 1 > 0 es verdadera para cada x D.La afirmacin
x(
x
x2 + 1=
3
10
), D = R
EMD/ABB 91/698
Clculo de predicado VII
es falsa, porquex
x2 + 1=
3
10
es falsa para por lo menos un x D, digamos para x = 2.
Equivalencia de cuantificadores
a. x P (x) x P (x)b. x P (x) x P (x)
Leyes de De Morgan para lgica
a. (x P (x)) x P (x)b. (x P (x)) x P (x)
EMD/ABB 92/698
Clculo de predicado VIII
Muchas veces las expresiones del lenguaje comn tieneninterpretaciones diferentes, por ejemplo la afirmacin
No todo entero primo es imparpuede interpretarse como:
Todo entero primo no es impar.Esta no es la interpretacin correcta.La interpretacin correcta es:
Algn entero primo no es impar.Consideremos las siguientes funciones proposicionales:P (x) : x es entero primoQ(x) : x es impar.La primera interpretacin se escribe como:
x (P (x) Q(x))
EMD/ABB 93/698
Clculo de predicado IX
y la segunda se escribe
x (P (x) Q(x)).
Observe que
x (P (x) Q(x)) x (P (x) Q(x)).
De la misma manera se observa que
x (P (x) Q(x)) (x (P (x) Q(x))).
Ejercicios
EMD/ABB 94/698
Clculo de predicado X
1. Determine si el enunciado dado es una funcinproposicional. Si lo es, encuentre el dominio de referencia.
a. 7n 1 es mltiplo de 6b. Elija un entero entre 3 y 19c. Los medias rojas de Boston ganaron la serie mundial del
2007d. 3x 5 = 2
2. Considere la funcin proposicional:P (n): 3 divide a (2n 1), D = Z+.Escriba cada proposicin en palabras y diga el valor deverdad de las siguientes proposiciones:
a. P (4) b. P (5) c. P (8) d. P (11)e. n P (n)
EMD/ABB 95/698
Clculo de predicado XI
3. Considere la funcin proposicional P (x): x es un golfista.El dominio de referencia es el conjunto de deportistas.Escriba en palabras cada proposicin.
a. x P (x)b. x P (x)c. x P (x)d. (x P (x))
4. Escriba la negacin de los ejercicios del punto 3 ensmbolos y palabras.
5. Considere las funciones proposicionales: P (x): x es unprofesor universitario y Q(x): x ensea matemtica. ELdominio de referencia es el conjunto de todos losprofesores. Escriba en palabras y determine el valor deverdad de cada afirmacin.
a. x (P (x) Q(x))
EMD/ABB 96/698
Clculo de predicado XII
b. x (P (x) Q(x))c. x (Q(x) P (x))d. x (P (x) Q(x))
6. Escriba la negacin de los ejercicios del punto 5 ensmbolos y palabras.
7. Considere las funciones proposicionales
P (x): x es un abogado
Q(x): x tiene un yate.
Escriba en smbolos y en palabras las siguientesafirmaciones.
a. Todos los abogados tienen un yateb. Algunos abogados tienen un yate
EMD/ABB 97/698
Clculo de predicado XIII
c. Todos los dueos de yate son abogadosd. Alguien que tiene un yate es abogado
8. Escriba la negacin en smbolos y palabras de losejercicios del punto 7.
9. Determine el valor de verdad de cada afirmacin. ELdominio de referencia es R.
a. x (x2 > x)b. x (x2 > x)c. x (x > 1 x2 > x)d. x (x > 1 x2 > x)e. x (x > 1 x/(x2 + 1) < 1/3)
10. Escriba la negacin en smbolos y en palabras de losejercicios del punto 9.
EMD/ABB 98/698
Clculo de predicado XIV
En el clculo proposicional, las variables representanproposiciones atmicas. Es decir, aquella en la que unapropiedad determinada se le atribuye a un sujeto. Es claro quea un mismo sujeto se le puede atribuir distintas propiedades yuna misma propiedad la pueden tener varios sujetos.Por ejemplo, de Pedro se puede decir que es gordo, alto,inteligente. Del mismo modo, mamfero se le puede atribuir auna Vaca, un caballo, un Perro, etc.El clculo de predicados considera los diferentes elementosque intervienen en las proposiciones, mientras que en elclculo proposicional, las proposiciones se consideran comoun todo.En el clculo de predicados, llamamos trmino al sujeto delque se predica algo y predicado, lo que se dice del sujeto.
EMD/ABB 99/698
Clculo de predicado XV
Los sujetos constantes, individuales o particulares se nombrangeneralmente con letras minsculas como: a, b, c, etc.,mientras que el smbolo x, se utiliza para variables de sujetos oindividuos.
Consideremos el argumento:
Todos los caballos son cuadrpedos. Santy es un caballo. Portanto, Santy es un cuadrpedo.Seanp : Todos los caballos son cuadrpedos.q : Santy es un caballo.r : Santy es un cuadrpedo.
EMD/ABB 100/698
Clculo de predicado XVI
La forma argumental de este argumento, viene dada por:
(p q) r.
Esta forma argumental no es vlida, ya que la formaproposicional es una contingencia.Sin embargo, desde el punto de vista lgico intuitivo, esteargumento parece ser vlido. Esto nos lleva a pensar que lalgica proposicional que hemos desarrollado hasta ahora notiene las herramientas suficientes que nos permita establecerla relacin entre las premisas y la conclusin.
El clculo de predicados suple esta deficiencia.
Por ejemplo, tomemos la proposicin:
EMD/ABB 101/698
Clculo de predicado XVII
Todos lo matemticos son cientficosPodemos decir que si Jos es matemtico, entonces Jos escientfico. De la misma forma, si Pedro es matemtico,entonces Pedro es cientfico. De modo ms general, podemosescribir: si x es matemtico, entonces x es cientfico.Consideremos la funcin proposicional:
P (x) : x es matemtico x es cientfico.La expresin x P (x) se interpreta como: para todo x, si x esmatemtico, entonces x es cientfico. En lo adelante Cuandohaya posibilidad de confusin en la notacin, usaremos elsmbolo : para separar el cuantificador de la funcinproposicional. As escribiremos
x : P (x).
EMD/ABB 102/698
Clculo de predicado XVIII
En el caso del enunciado anterior, podemos escribir
x : x es matemtico x es cientfico.
Teorema
Si P (x) es una funcin proposicional y a un objeto del dominiode definicin de x, entonces
xP (x) P (a)es una tautologa.
Demostracin
Si suponemos que la condicional es falsa es porque xP (x)es verdadera y P (a) es falsa. Ahora bien, si P (a) es falsa,entonces xP (x) es falsa y esto es contradictorio con el hechode que xP (x) es verdadera.
EMD/ABB 103/698
Clculo de predicado XIX
Para probar la validez de argumentos que incluyenproposiciones universales se pueden aplicar las mismas reglasde inferencias ( o de derivacin) del clculo proposicional.Tomemos como ejemplo el argumento:
Todos los santiagueros son cibaeos. Todos los cibaeos sonemprendedores. Luego, todos los santiagueros sonemprendedores.
Este argumento se escribe en forma simblica como:SeanP (x) : x es santiaguero.Q(x) : x es cibaeo.R(x) : x es emprendedor.
Entonces el argumento lo escribimos como:
EMD/ABB 104/698
Clculo de predicado XX
x : P (x) Q(x), x : Q(x) R(x) ` x : P (x) R(x)Prueba
Como las premisas son verdaderas, tomemos un objetoparticular cualquiera del dominio de definicin de x, digamosx0 y hagamos
p : x0 es santiaguero.q : x0 es cibaeo.r : x0 es emprendedor.
Entonces el argumento se escribe:
p q, q r ` p r
EMD/ABB 105/698
Clculo de predicado XXI
Es evidente que este argumento es vlido, segn la derivacindel clculo proposicional porque corresponde a la regla deinferencia de transitividad.
Consideremos el argumento:
Todos los caballos son cuadrpedos. Santy es un caballo. Portanto, Santy es un cuadrpedo.SeanP (x) : x es un caballo.Q(x) : x es un cuadrpedo.P (x0) : Santy es un caballo.
Entonces el argumento se escribe como:
x : P (x) Q(x), P (x0) ` Q(x0)
EMD/ABB 106/698
Clculo de predicado XXII
Prueba
Como las premisas son ambas verdaderas, se puede aplicar laregla de inferencia del Modus Ponens del clculo proposicionaly se obtiene la conclusin.
Ejercicios
Determine si los argumentos siguientes son vlidos o no.
1. Todos los Fsicos son analistas. Todos los analistas soninteligentes. Luego, todos los Fsicos son inteligentes.
2. Toda persona cariosa es amada. Todos los que sonamados son dichosos. Juan es carioso. luego, Juan esdichoso.
EMD/ABB 107/698
Clculo de predicado XXIII
3. Toda figura es un cuadriltero. Un tringulo es una figura.Por tanto, un tringulo tiene cuatro lados.
4. Todos los beisbolistas son atletas. Todos los futbolistasson atletas. Por tanto, todos los beisbolistas sonfutbolistas.
5. Los guineos son frutas agradables y saludables. Toda frutaagradable y saludable no se desarrolla en pantanos.Luego, los guineos no se desarrollan en pantanos.
6. Todo el que ama es un enfermo. Pedro vive en la ciudad.Todo el que vive en la ciudad no ama. Por tanto, Pedro noes un enfermo.
EMD/ABB 108/698
Clculo de predicado XXIV
7. Toda persona inteligente es estudiosa. Toda personaestudiosa es exitosa. Todo hombre es exitoso. Luego, Todohombre es inteligente.
Para indicar expresiones como: Existe un nico, Hay unsolo, Hay un nico, se utiliza otro cuantificador del cual nohemos hablado que es:
!.Cuando de escribe
!xP (x),se quiere decir que hay un nico elemento x tal que P (x).
La proposicin!xP (x)
EMD/ABB 109/698
Clculo de predicado XXV
es verdadera, si y slo si, existe un nico objeto en el dominiode definicin de x para el cual P (x) es verdadera. Es falsacuando P (x) es falsa para todos los valores de x dentro de sudominio de definicin o cuando hay ms de un valor de x paralos cuales P (x) es verdadera.
Consideremos el argumento:
Algunos hombres son inteligentes. Todas las personasinteligentes son sabias. Luego, Algunos hombres son sabios.
SeanP (x) : x es un hombre.Q(x) : x es inteligente.R(x) : x es sabio.
EMD/ABB 110/698
Clculo de predicado XXVI
El argumento en forma simblica se escribe como:
x : P (x) Q(x), x : Q(x) R(x) ` x : P (x) R(x)Prueba
Como suponemos que las premisas son verdaderas, existe porlo menos un objeto x0 en el dominio de definicin de x para elcual la proposicin es P (x0) Q(x0) y por tanto, ambas sonverdaderas. Como la segunda premisa es verdadera, se tieneque Q(x0) R(x0) es verdadera. Ahora bien, como Q(x0) esverdadera, se tiene que R(x0). Luego, tenemos queP (x0) R(x0) es verdadera y x : P (x) R(x) es unaproposicin verdadera. Luego, el argumento es vlido.
EMD/ABB 111/698
Clculo de predicado XXVII
Este argumento es un caso particular del argumento delclculo prosicional
p q, q r ` p r,
que es un argumento vlido.
Ejercicios
Determine si los argumentos siguientes son vlidos o no.
1. Todos los filsofos son cientficos. Algunos hombres sonfilsofos. Luego, hay hombres que son cientficos.
2. Si un hombre toca guitarra, entonces es msico. Hayhombres que son msicos. Por tanto, hay hombres quetocan guitarra.
EMD/ABB 112/698
Clculo de predicado XXVIII
3. Algunos conductores son imprudentes. Los conductoresimprudentes son agresivos. Luego, Algunos conductoresimprudentes son agresivos.
4. Algunos seres vivos son parsitos. Los hombres son seresvivos. Por tanto, Algunos hombres son parsitos.
5. Los universitarios que estudian son exitosos. Hayuniversitarios que no estudian. Por tanto, Hayuniversitarios que no son exitosos.
6. Todos los msicos clsicos son artistas. Existen msicosque no son artistas. Luego, Existen msicos que no sonclsicos.
EMD/ABB 113/698
Clculo de predicado XXIX
Cuantificadores anidados
Los cuantificadores anidados se utilizan cuando necesitamosdos o ms variables en una funcin proposicional. Por ejemplo,cuando escribimos
xy(x2 + y2 0), D = R,
queremos significar que para cada x y para cada y, se tieneque (x2 + y2 0). Evidentemente que esta afirmacin esverdadera.
Si se escribexy (x+ y = 0), D = R,
EMD/ABB 114/698
Clculo de predicado XXX
significamos que para cada x existe al menos una y tal quex+ y = 0. Esta afirmacin es verdadera.
Cuando se escribe
xy (x > y), D = Z+,
queremos decir que para toda x, existe una y tal que x > y.
Esta afirmacin es falsa porque existe al menos una x,digamos x = 1 para la cual x > y es falsa para todo enteropositivo y.
Consideremos la afirmacin
xy((x < 0) (y < 0) (xy = 15)), D = Z.
EMD/ABB 115/698
Clculo de predicado XXXI
Esto significa que existe una x y existe una y, digamos x = 3y y = 5 tal que xy = 15, lo cual es verdadera.
Considere la afirmacin
xy (x y), D = Z+.Esta afirmacin es falsa.
Negacin de cuantificadores en dos variables
La negacin de cuantificadores en dos variables se obtieneaplicando las leyes de DMorgan repetidamente. De modo que
a. (x y P (x, y)) x( y P (x, y)) x y P (x, y)b. (x y P (x, y)) x( y P (x, y)) x y P (x, y)
EMD/ABB 116/698
Clculo de predicado XXXII
c. (x y P (x, y)) x( y P (x, y)) x y P (x, y)d. (x y P (x, y)) x( y P (x, y)) x y P (x, y)
Ejercicios
1. Considere la funcin proposicin P (x, y) : x y. ELdominio de referencia es Z+. Determine el valor de verdadde cada una de las siguientes proposiciones.
a. xy P (x, y)b. xy P (x, y)c. xy P (x, y)
2. Escriba la negacin de cada uno de los ejercicios delpunto 1.
EMD/ABB 117/698
Clculo de predicado XXXIII
3. Determine el valor de verdad de las siguientesproposiciones. El dominio de referencia es D = R.
a. xy (x2 < y + 1)b. xy (x2 < y + 1)c. xy (x2 + y2 = 9)d. xy (x2 + y2 0)e. xy (x2 + y2 = 9)
f. xy ((x < y) (x2 < y2))g. xy ((x < y) (x2 < y2))h. xy ((x < y) (x2 < y2))i. xy (x2 + y2 = 9)j. yx (x2 < y + 1)k. xy (x2 + y2 0)
EMD/ABB 118/698
Clculo de predicado XXXIV
l. xy (x2 + y2 0)4. Escriba la negacin de cada uno de los ejercicios del
punto 3.
EMD/ABB 119/698
Contenido IINTRODUCCIN
NOCIONES DE LGICA FORMALIntroduccinClculo proposicionalFormas normalesClculo de predicado
TEORA DE CONJUNTOSConceptos y definicionesOperaciones con conjuntosPropiedades de las operaciones con conjuntosConjuntos numricosDivisibilidad y algoritmos de enterosAlgoritmo de EuclidesFuncin caractersticaSucesionesRepresentacin de conjuntos en una computadoralgebras booleanas
EMD/ABB 120/698
Contenido IIProducto cartesiano o conjunto productoInduccin y recursin
TEORA DE NMEROS Y COMBINATORIAElementos de conteoPermutaciones: Se toma en cuenta el ordenCombinaciones: No toma en cuenta el ordenCombinaciones con repeticin
CONGRUENCIA, RELACIONES Y FUNCIONESCongruenciaEcuaciones diofnticas linealesCongruencias linealesRelacionesRelaciones de equivalenciaRelaciones de ordenFuncionesPrincipio del palomar
INTRODUCCIN A LA PROBABILIDADEMD/ABB 121/698
Contenido IIIElementos de probabilidadProbabilidad condicional e independenciaVariables aleatorias
EMD/ABB 122/698
ContenidoINTRODUCCINNOCIONES DE LGICA FORMAL
IntroduccinClculo proposicionalFormas normalesClculo de predicado
TEORA DE CONJUNTOSConceptos y definicionesOperaciones con conjuntosPropiedades de las operaciones con conjuntosConjuntos numricosDivisibilidad y algoritmos de enterosAlgoritmo de EuclidesFuncin caractersticaSucesionesRepresentacin de conjuntos en una computadoralgebras booleanasProducto cartesiano o conjunto productoInduccin y recursin
TEORA DE NMEROS Y COMBINATORIAElementos de conteoPermutaciones: Se toma en cuenta el ordenCombinaciones: No toma en cuenta el ordenCombinaciones con repeticin
CONGRUENCIA, RELACIONES Y FUNCIONESCongruenciaEcuaciones diofnticas linealesCongruencias linealesRelacionesRelaciones de equivalenciaRelaciones de ordenFuncionesPrincipio del palomar
INTRODUCCIN A LA PROBABILIDADElementos de probabilidadProbabilidad condicional e independenciaVariables aleatorias
EMD/ABB 123/698
Conceptos y definiciones I
Conjuntos
Un conjunto es cualquier coleccin de objetos bien definidosen el sentido de que se pueda determinar con precisin y sinambiguedad cuando un objeto pertenece o no al conjunto. Alos objetos que componenen un conjunto se les llamaelementos o miembros del conjunto. Por ejemplo, el conjuntode las letras del alfabeto castellano; el conjunto de los numerosreales entre cero y uno, etc.. Los conjuntos representan labase sobre la cual se construye toda la matemtica. De aqu suimportancia en todo estudio cientfico.Los conjuntos se representan generalmente por letrasmaysculas como A,B,C, S, T, . . . y sus elementos, por letrasminsculas como x, y, z, s, t, a, . . . .
EMD/ABB 124/698
Conceptos y definiciones II
Para indicar que el objeto x es elemento o miembro delconjunto A, se escribe
x Ay para decir que x no pertenece al conjunto A se escribe
x 6 A
Los conjuntos se pueden describir por extensin ocomprensin. Un conjunto se define por extensin cuandosus elementos se enlistan entre llaves, separados por comas.Por ejemplo, el conjunto
{a, b, c, d},
EMD/ABB 125/698
Conceptos y definiciones III
est descrito por extensin. El orden de los elementos en unconjunto no tiene importancia.De aqu que los conjuntos
{d, c, b, a}, {b, a, c, d}, {c, a, d, b},representan todos, al conjunto dado.En un conjunto los elementos no se repiten, es decir, loselementos repetidos, sencillamente se ignoran.Un conjunto se describe por comprensin cuando seespecifica una propiedad comn que satisfacen los elementosdel conjunto. Sea P (x) una funcin proposicional referente alobjeto x.La forma de escribir el conjunto por comprensin es
{x |P (x)},
EMD/ABB 126/698
Conceptos y definiciones IV
que significa la coleccin de todos los objetos x para los que Phace sentido y es verdadera.Por ejemplo,
{x |x es un entero positivo par menor que 10}es el conjunto
{2, 4, 6, 8}.En el primer caso, tenemos un conjunto definido porcomprensin y luego, el mismo conjunto, pero definido porextensin.
Ejemplo
El conjunto de todas las letras de la palabra bits se puededescribir como
EMD/ABB 127/698
Conceptos y definiciones V
{b, i, t, s}o por
{x |x es una letra en la palabra bits}.El conjunto que no tiene elemento se le llama conjunto vacoy se representa por o { }.Por ejemplo,
= {x |x es un nmero real y x2 + 1 = 0},puesto que el cuadrado de un nmero real es siempre mayor oigual a cero.
Subconjunto
EMD/ABB 128/698
Conceptos y definiciones VI
Decimos que un conjunto A es subconjunto del conjunto B sitodos los elementos de A son tambin elementos de B, esdecir, si cuando x A, entonces x B o
x : [x A x B].
Se escribeA B.
Si un conjunto A no es subconjunto de B, se escribe
A 6 B.
EMD/ABB 129/698
Conceptos y definiciones VII
U
A B
A B
U
A B
A* B y B* A
U
A B
A* B y B* A
Por ejemplo, sean
A = {2, 4, 5}, B = {1, 2, 3, 4, 5, 6}, D = {3, 4, 5, 6, 7}.
EMD/ABB 130/698
Conceptos y definiciones VIII
Se observa que A B, A 6 D, B 6 D.Las relaciones entre conjuntos pueden ser representadasmediante los llamados diagramas de Venn en honor al lgicoJohn Venn. As, Si A es un conjunto cualquiera, entoncesA A. Es decir, cualquier conjunto es subconjunto de simismo.
Es fcil probar que A para cualquier conjunto A.Ejemplo
Consideremos un conjunto X y sea
T = {X, {X}}.
EMD/ABB 131/698
Conceptos y definiciones IX
Es claro que X T y {X} T . Luego, podemos decir que
{X} T y {{X}} T.
Por otro lado, es evidente que X 6 T .Notacin
Para algunos conjuntos de uso comn en este curso, usaremosla siguiente notacin
a. N = {0, 1, 2, 3, . . . }b. Z = {. . . ,4,3,2,1, 0, 1, 2, 3, . . . }c. Z+ = {1, 2, 3, . . . }d. Z = {. . . ,3,2,1}
EMD/ABB 132/698
Conceptos y definiciones X
Notacin (cont.)
e. Q ={ab| a Z, b Z, b 6= 0
}f. I =
{x |x no se puede expresar como a
b, a Z, b Z
}g. R = Q Ih. R = R {,+} = conjunto de los reales extendidos.
Igualdad
Decimos que los conjuntos A y B son iguales, si y slo si,tienen exactamente los mismos elementos. Se escribe
A = B.
Por ejemplo, los conjuntos
EMD/ABB 133/698
Conceptos y definiciones XI
A = {x |x es un nmero entero y x2 1 = 0} y B = {1, 1},son iguales. Es decir,
A = B.
Es fcil probar que
A = B, si y slo si, A B y B A.Por ejemplo:
Consideremos los conjuntos
A = {r Z|r = 3m para algn entero m}y
B = {s Z|s = 3n+ 3 para algn entero n}.
EMD/ABB 134/698
Conceptos y definiciones XII
Probemos que A = B.Prueba:
Debemos probar que A B y B A.Primero. Probemos que A B.Sea x A, entonces existe un m Z tal que x = 3m. Ahorabien, podemos escribir x = 3n+ 3 donde n = m 1 es tambinun entero. Por tanto, x B y A B.Segundo. Probemos que B A.Sea x B, entonces existe un n Z tal que x = 3n+ 3. Ahorabien, podemos escribir x = 3m donde m = n+ 1 es tambin unentero. Por tanto, x A y B A. Luego, A = B.
EMD/ABB 135/698
Conceptos y definiciones XIII
El conjunto que contiene todos los elementos con los cuales setrabaja en el estudio se le llama conjunto universo oconjunto universal y se representa por U . Esto es, todos losconjuntos con los cuales trabajamos suponemos que sonsubconjuntos del conjunto universo. Cuando no haya lugar aconfusin en el contexto de trabajo, obviaremos el conjuntouniverso. Un conjunto A es finito si posee n elementosdistintos, donde n N. Al nmero n se le llama cardinal de Ay lo representamos por |A|. Por ejemplo, los conjuntos
A = {1, 2, 3, 4, 5} y B = {x R|x2 1 = 0}
son finitos y tienen como cardinales |A| = 5 y |B| = 2.
Los conjuntos N y Z no son finitos.
EMD/ABB 136/698
Conceptos y definiciones XIV
Complemento de un conjunto
El complemento de un conjunto A se define como el conjuntode todos los elementos del conjunto universal que nopertenecen a A. Se representa por Ac. Por ejemplo, siU = {1, 2, 3, 4, 5, 6, 7, 8, 9} y A = {1, 3, 6, 7, 9}, el complementode A es
Ac = {2, 4, 5, 8}.Conjunto potencia
Sea A un conjunto. Al conjunto de todos los subconjuntos de Ase le llama conjunto potencia de A y se representa por P (A)o 2A.
Por ejemplo, sea A = {a, b, c}.
EMD/ABB 137/698
Conceptos y definiciones XV
El conjunto potencia de A viene dado por
P (A) = {{a}, {b}, {c}, {a, b}, {a, c}, {b, c}, , A}
El cardinal del conjunto potencia de un conjunto A se definecomo
|P (A)| = 2|A|.As que el cardinal de P (A), donde A es el conjunto delejemplo anterior es
|P (A)| = 2|A| = 23 = 8
EMD/ABB 138/698
Conceptos y definiciones XVI
Una Familia de conjuntos es un conjunto cuyos elementosson a su vez conjuntos. Por ejemplo, el conjunto
F = {{a}, {1, 2}, {c, b}, , {4, 5, 6}}
es una familia de conjuntos. El conjunto
G = {{b}, {3, 4, 5}, 3, {c, d}, 7}
no es una familia de conjuntos. El conjunto potencia de unconjunto A es una familia de conjuntos.
Sea I un conjunto de ndices. Una familia de conjuntos tambinse puede definir como
F = {Ai}iI , donde los Ai son conjuntos.
EMD/ABB 139/698
ContenidoINTRODUCCINNOCIONES DE LGICA FORMAL
IntroduccinClculo proposicionalFormas normalesClculo de predicado
TEORA DE CONJUNTOSConceptos y definicionesOperaciones con conjuntosPropiedades de las operaciones con conjuntosConjuntos numricosDivisibilidad y algoritmos de enterosAlgoritmo de EuclidesFuncin caractersticaSucesionesRepresentacin de conjuntos en una computadoralgebras booleanasProducto cartesiano o conjunto productoInduccin y recursin
TEORA DE NMEROS Y COMBINATORIAElementos de conteoPermutaciones: Se toma en cuenta el ordenCombinaciones: No toma en cuenta el ordenCombinaciones con repeticin
CONGRUENCIA, RELACIONES Y FUNCIONESCongruenciaEcuaciones diofnticas linealesCongruencias linealesRelacionesRelaciones de equivalenciaRelaciones de ordenFuncionesPrincipio del palomar
INTRODUCCIN A LA PROBABILIDADElementos de probabilidadProbabilidad condicional e independenciaVariables aleatorias
EMD/ABB 140/698
Operaciones con conjuntos I
Sean A y B dos conjuntos cualesquiera de U .
La unin de A y B se define como el conjunto de todos loselementos que pertenecen a A o a B o a ambos. Serepresenta por A B. Simblicamnete, se escribe
A B = {x U |x A o x B}.El diagrama de Venn para la unin es
EMD/ABB 141/698
Operaciones con conjuntos II
U
A B
ABEjemplo
Sean los conjuntos A = {a, 5, q} y B = {3, a, 7}. Entonces
A B = {a, 5, q, 3, 7}.
EMD/ABB 142/698
Operaciones con conjuntos III
La interseccin de A y B se define como el conjunto de todoslos elementos comunes a A y a B. Se representa por A B.Simblicamnete, se escribe
A B = {x U |x A y x B}.
El diagrama de Venn para la interseccin es
EMD/ABB 143/698
Operaciones con conjuntos IV
U
A B
ABEjemplo
Sean los conjuntos A = {a, b, 7, d} y B = {3, b, c, 7}. Entonces
A B = {b, 7}.
Conjuntos disjuntos
EMD/ABB 144/698
Operaciones con conjuntos V
Dos conjuntos A y B son Disjuntos si no poseen elementoscomunes. Es decir, si
A B = .Ejemplo
Sean A = {2, 3, 4, 7} y B = {x R|x2 1 = 0}. Es claro queA B = .Generalizacin de la unin e interseccin
Sea I un conjunto de ndices. Suponga que para cada i Ihay un Ai U . Entonces generalizando, se tiene
iIAi = {x|x Ai para algn i I}
EMD/ABB 145/698
Operaciones con conjuntos VI
yiIAi = {x|x Ai, i I}.
Si I = Z+, entonces
iIAi = A1 A2 A3 =
i=1Ai
yiIAi = A1 A2 A3 =
i=1Ai
Ejemplo
Sean U = R, I = R+. Suponga que para todo n I se tieneque An = [n, n]. Entonces
iIAi = R y
iIAi = {0}
EMD/ABB 146/698
Operaciones con conjuntos VII
La diferencia de A menos B se define como el conjunto detodos los elementos que estn en A y que no estn en B. Serepresenta por AB. Simblicamnete, se escribe
AB = {x U |x A y x 6 B}.As que el complemento de A se puede escribir comoAc = U A.El diagrama de Venn para la diferencia es
EMD/ABB 147/698
Operaciones con conjuntos VIII
U
A B
ABEjemplo
Sean los conjuntos A = {4, 5, a, b, 7, d} y B = {3, 5, d, e, 7}.Entonces
AB = {4, a, b}.
EMD/ABB 148/698
Operaciones con conjuntos IX
La diferencia simtrica de A y B se define como el conjuntode todos los elementos que estn en A B y que no estn enA B. Se representa por A4B. Simblicamnete, se escribe
A4B = {x U |x (AB) y x 6 (AB)} = (AB)(AB).
El diagrama de Venn para la diferencia simtrica es
EMD/ABB 149/698
Operaciones con conjuntos X
U
A B
ABEjemplo
Sean los conjuntos A = {3, 4, a, b, 7, d} y B = {2, 4, b, e, 5}.Entonces
A4B = {2, 3, a, 7, d, e, 5}.
EMD/ABB 150/698
ContenidoINTRODUCCINNOCIONES DE LGICA FORMAL
IntroduccinClculo proposicionalFormas normalesClculo de predicado
TEORA DE CONJUNTOSConceptos y definicionesOperaciones con conjuntosPropiedades de las operaciones con conjuntosConjuntos numricosDivisibilidad y algoritmos de enterosAlgoritmo de EuclidesFuncin caractersticaSucesionesRepresentacin de conjuntos en una computadoralgebras booleanasProducto cartesiano o conjunto productoInduccin y recursin
TEORA DE NMEROS Y COMBINATORIAElementos de conteoPermutaciones: Se toma en cuenta el ordenCombinaciones: No toma en cuenta el ordenCombinaciones con repeticin
CONGRUENCIA, RELACIONES Y FUNCIONESCongruenciaEcuaciones diofnticas linealesCongruencias linealesRelacionesRelaciones de equivalenciaRelaciones de ordenFuncionesPrincipio del palomar
INTRODUCCIN A LA PROBABILIDADElementos de probabilidadProbabilidad condicional e independenciaVariables aleatorias
EMD/ABB 151/698
Propiedades de las Operaciones con conjuntos I
Conmutativas AsociativasA B = B A A (B C) = (A B) CA B = B A A (B C) = (A B) CDistributivas IdempotenciaA (B C) = (A B) (A C) A A = AA (B C) = (A B) (A C) A A = A
Complemento Complemento(Ac)c = A A Ac = UA Ac = c = UU c = c = U
EMD/ABB 152/698
Propiedades de las Operaciones con conjuntos II
Ley de De Morgan Ley de De Morgan
(A B)c = Ac Bc (A B)c = Ac BcConjunto universal Conjunto universal
(A U) = U (A U) = AConjunto vaco Conjunto vaco
(A ) = A (A ) =
Para probar que los conjuntos A y B son iguales ( A = B),debemos probar que A B y B A.
EMD/ABB 153/698
Propiedades de las Operaciones con conjuntos III
A modo de ejemplo, probemos una de las leyes de DMorgan
(A B)c = Ac Bc.
Prueba
1. Probemos que (A B)c Ac Bc.Sea x (A B)c. Entonces x 6 (A B). De aqu que x 6 A yx 6 B. Entonces x Ac y x Bc. Por tanto, x Ac Bc.Luego, (A B)c Ac Bc.2. Probemos que Ac Bc (A B)c.
EMD/ABB 154/698
Propiedades de las Operaciones con conjuntos IV
Sea x Ac Bc. Entonces x Ac y x Bc. De aqu que x 6 Ay x 6 B. Entonces x 6 (A B) y por tanto, x (A B)c.Luego, Ac Bc (A B)c.Hemos probado que (A B)c Ac Bc y Ac Bc (A B)c.Por tanto,
(A B)c = Ac Bc
Generalizacin de las Leyes de DMorgan
Sea I un conjunto de ndices. suponga que para cada i I hayun Ai U . Entonces generalizando, se tiene
( iIAi)
c = iIAci
EMD/ABB 155/698
Propiedades de las Operaciones con conjuntos V
y( iIAi)
c = iIAci
TeoremaSean A y B dos conjuntos finitos. Entonces
|A B| = |A|+ |B| |A B|.La demostracin se bosqueja mediante los diagramas de Venn.
TeoremaSean A, B, y C conjuntos finitos. Entonces
|ABC| = |A|+|B|+|C||AB||BC||AC|+|ABC|.
Ejemplo
EMD/ABB 156/698
Propiedades de las Operaciones con conjuntos VI
Suponga que una Universidad requiere 12 profesores deMatemtica y 8 de Fsica. De estos, 3 deben ensear ambasmaterias. Cuntos profesores necesita la Universidad?SolucinSea A el conjunto de los profesores de Matemtica. Entonces|A| = 12 y sea B el conjunto de los profesores de Fsica.Entonces |B| = 8. Y |AB| = 3. Luego, la Universidad necesita|A B| = |A|+ |B| |A B| = 12 + 8 3 = 17 profesores.
EMD/ABB 157/698
Ejercicios I
1. Sean los conjuntos:A = {x|x N, x par, 0 < x < 8}B = {x|x Q, x(x2 6) = 0}C = {x|x N,x2 + x+ 20 > 0}
a. Determine por extensin a A, B y C.b. Encuentre P (A).c. Determine si es verdero o falso y justifique su respuesta
4 A, 4 A, 3 6 B, 4 C, C, C,{0} C
2. Sean los conjuntos:A = {x|x N,x2 + 5x 0}B = {x|x N, 2x+ 7 < 25}C = {x|x N, x2 ; 0}
EMD/ABB 158/698
Ejercicios II
a. Determine los conjuntos por extensin.b. Encuentre
AC, A C, (AC) (C A), B A, B A C
3. Cules de los conjuntos siguientes son iguales?E = {r, t, s}, F = {s, t, r, s}, D = {t, s, t, r}, {s, r, s, t}
4. Cules de los siguientes conjuntos son finitos?a. {x|x es un dia de las semana}b. {x|x es un nmero natural impar}c. {x|x es un ser humano de la tierra}d. {1, 2, 3, . . . , 1000}e. {2, 4, 6, . . . }
5. Cules de los conjuntos siguientes son iguales?{0}, {},
EMD/ABB 159/698
Ejercicios III
6. Determine los conjuntos que son vacosa. {x|x2 = 9, 2x = 4}b. {x|x 6= x}c. {x|x+ 3 = 3}d. {x|x2 < 0}e.{x
x+ 310 = 1/5 , x N}
7. Demuestre que A = {4, 5, 6, 7} no es subconjunto deB = {x|x es par}
8. Demuestre que si A B y B C, entonces A C9. Encuentre P (A), si A = {3, 4, 5}
10. Demuestre que si A , entonces A = .
EMD/ABB 160/698
Ejercicios IV
11. Sean U = {1, 2, 3, 4, 5, 6, 7, 8, 9}, A = {1, 2, 3, 4}, B ={2, 4, 6, 8}, C = {3, 4, 5, 6}. Encuentre
a. Ac, A C, B Cb. (A C)c, A B
12. En un Hospital de Santo Domingo se tienen los datossiguientes sobre 50 pacientes: 21 sufren de diabetes; 22sufren del corazn; 10 sufren de diabetes y de la vista; 9sufren de la vista y el corazn; 6 sufren de diabetes y elcorazn; 5 de la vista, diabetes y el corazn. Determine elnmero de pacientes que:
a. Sufren de la vistab. Sufren slo de la vistac. Sufren de diabetes pero no del coraznd. Sufren de la vista pero no de diabetes
EMD/ABB 161/698
Ejercicios V
13. Demuestre que (AB) B = 14. Sean A y B dos conjuntos cualesquiera. Demuestre que
(A B) A (A B)15. El director de la escuela Anacleto Prez de Anapulla
dispone de recursos limitados y redacta a la secretara deeducacin el siguiente informe sobre un conjunto A deestudiantes: 36 estudian Ingls; 23 estudian Francs; 13estudian Portugus; 6 estudian Ingls y Francs; 4estudian Francs y Portugus; 11 estudian Ingls yPortugus; y 1 estudia los tres idiomas. El informe fuerechazado por la secretara. por qu?
16. Sean A, B y C tres conjuntos, de los cuales se conoce:a. C (A B)
EMD/ABB 162/698
Ejercicios VI
b. |A B C| = 3c. |A B| = 3d. |B C| = 5e. |A C| = 4f. |A| = 20
g. |A C| = 35h. |A B| = 40
Hallar el cardinal de los conjuntos B y C.
17. Dibujar un diagrama de Venn de tres conjuntos no vacosA, B y C tales que satisfagan las propiedades:
a. A B, C B, A C = b. A B, C 6 B, A C 6= c. A C, A 6= C, B C = d. A (B C), B C, C 6= B, A 6= C
EMD/ABB 163/698
Ejercicios VII
18. Demuestre que si A B = , entonces A Bc19. Demuestre que si A B, entonces A (B A) = B
20. Sean U = {a, b, c, d, e, f, g}, A = {a, b, c, d, e}B = {a, c, e, g}, C = {b, e, f, g}. Encuentre
a. A C b. B A c. C B d. Bc Ce. Cc A f. (A C)c g. (ABc)ch. (A Ac)c
EMD/ABB 164/698
ContenidoINTRODUCCINNOCIONES DE LGICA FORMAL
IntroduccinClculo proposicionalFormas normalesClculo de predicado
TEORA DE CONJUNTOSConceptos y definicionesOperaciones con conjuntosPropiedades de las operaciones con conjuntosConjuntos numricosDivisibilidad y algoritmos de enterosAlgoritmo de EuclidesFuncin caractersticaSucesionesRepresentacin de conjuntos en una computadoralgebras booleanasProducto cartesiano o conjunto productoInduccin y recursin
TEORA DE NMEROS Y COMBINATORIAElementos de conteoPermutaciones: Se toma en cuenta el ordenCombinaciones: No toma en cuenta el ordenCombinaciones con repeticin
CONGRUENCIA, RELACIONES Y FUNCIONESCongruenciaEcuaciones diofnticas linealesCongruencias linealesRelacionesRelaciones de equivalenciaRelaciones de ordenFuncionesPrincipio del palomar
INTRODUCCIN A LA PROBABILIDADElementos de probabilidadProbabilidad condicional e independenciaVariables aleatorias
EMD/ABB 165/698
Conjunto de los nmeros naturales (N) I
Definicin
El conjunto de los nmeros naturales se define como
N = {0, 1, 2, 3, 4, . . . }.
El conjunto de los nmeros naturales se puede empezar encero (0) o en uno (1). Nosotros lo vamos a empezar en cero(0). El conjunto N es infinito.
Definicin
Sea A un conjunto no vaco cualquiera. Decimos que unaoperacin ? es Interna en A, si para cualesquiera a y b en A sesigue que a ? b A. Suele decirse que el conjunto A esCerrado con respecto a la operacin ?.
EMD/ABB 166/698
Conjunto de los nmeros naturales (N) II
Operaciones internas en N: suma (+) y multiplicacin (*)
Principio del buen orden
Todo subconjunto no vaco de nmeros naturales tiene unprimer elemento o elemento mnimo. Es decir, siA N, A 6= , entonces existe m A 3 m n, n A.Teorema
No hay nmero natural entre 0 y 1.
Demostracin
Supongamos que existe un nmero natural a, tal que0 < a < 1. Entonces hay un conjunto A 6= de nmerosnaturales menores que 1.
EMD/ABB 167/698
Conjunto de los nmeros naturales (N) III
Por el principio del buen orden, A tiene un primer elemento,digamos m A. Entonces 0 < m < 1. Multiplicando todos losmiembros de la ltima desigualdad por m tenemos que0 < m2 < m. Pero esto contradice el hecho de que m era elelemento mnimo de A.
Por tanto, entre 0 y 1 no hay nmero natural.
EMD/ABB 168/698
Conjunto de los nmeros enteros (Z) I
Definicin
El conjunto de los nmeros enteros se define como
Z = {. . . ,3,2,1, 0, 1, 2, 3, 4, . . . }.
El conjunto Z es infinito.
Operaciones internas en Z: suma (+), resta (-) ymultiplicacin (*).
N Z
EMD/ABB 169/698
ContenidoINTRODUCCINNOCIONES DE LGICA FORMAL
IntroduccinClculo proposicionalFormas normalesClculo de predicado
TEORA DE CONJUNTOSConceptos y definicionesOperaciones con conjuntosPropiedades de las operaciones con conjuntosConjuntos numricosDivisibilidad y algoritmos de enterosAlgoritmo de EuclidesFuncin caractersticaSucesionesRepresentacin de conjuntos en una computadoralgebras booleanasProducto cartesiano o conjunto productoInduccin y recursin
TEORA DE NMEROS Y COMBINATORIAElementos de conteoPermutaciones: Se toma en cuenta el ordenCombinaciones: No toma en cuenta el ordenCombinaciones con repeticin
CONGRUENCIA, RELACIONES Y FUNCIONESCongruenciaEcuaciones diofnticas linealesCongruencias linealesRelacionesRelaciones de equivalenciaRelaciones de ordenFuncionesPrincipio del palomar
INTRODUCCIN A LA PROBABILIDADElementos de probabilidadProbabilidad condicional e independenciaVariables aleatorias
EMD/ABB 170/698
Divisibilidad I
Definicin
Sean a, b Z. Se dice que a divide a b, escrito a | b, si existek Z tal que b = ka. Si a | b se dice que a es un divisor de b oque b es un mltiplo de a
Ejemplo
2 | 6, 5 | 40, 11 | 55Si a no divide a b, se escribe a6 | b.Propiedades de la divisibilidad
Sean a, b, c, d Z.a. 1 | a, a | a, a | 0.b. Si a | b y b | a, entonces a = b.
EMD/ABB 171/698
Divisibilidad II
c. Si a | b, entonces a | bc y ac | bc.d. Si a | b y a | c, entonces a | b+ c.e. Si a | b y a | c, entonces a | bx+ cy, x, y Z.f. Si a | b y b | c, entonces a | c.
g. Si a | b y c | d, entonces ac | bd.Divisin segn Euclides
Sean a, b Z con b 6= 0. Entonces existen enteros nicos q y r,tales que a = bq + r, 0 r < |b|.
a es llamado dividendo.b es llamado divisor.q es llamado cociente.r es llamado resto.
EMD/ABB 172/698
Divisibilidad III
Definicin
Un factor o divisor es cada uno de los operandos de unproducto.
Ejemplos
La expresin abc tiene como factores a a, b y c.Los factores de 5x(a+ b) son : 5, x y (a+ b).Los factores de (13)(37) son : 13 y 37.
EMD/ABB 173/698
Nmeros primos I
Definicin
Un nmero p N, p > 1 es primo si sus nicos divisores en Nson 1 y p. Si un nmero n N, n > 1 no es primo, decimosque es compuesto
Ejemplos
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, . . .
El 2 es el nico primo par.
Ejemplos
6, 15, 42, 70 son compuestos.
Propiedad
EMD/ABB 174/698
Nmeros primos II
Si n es un entero compuesto, entonces n tiene al menos undivisor primo menor o igual a
n.
El 0 , 1 y los enteros negativos no son primos ni compuestospor definicin.
Teorema fundamental de la aritmtica
Sea n N, n > 1 no primo. Existen nmeros primos nicosp1, p2, , pr y enteros no negativos nicos m1,m2, ,mr,tales que n se puede expresar de manera nica, excepto en elorden de los factores, como
n = pm11 pm22 . . . p
mrr .
EMD/ABB 175/698
Nmeros primos III
A esta expresin se le llama Descomposicin factorial de nen nmeros primos.
Ejemplos
Descomponer los nmeros 18, 70 y 56 en factores primos:
18 = 2 3 3 = 2 32, 70 = 2 5 7, 56 = 2 2 2 7 = 23 7Los factores en los que se descompone el nmero n se lesllama Divisores de n.
EMD/ABB 176/698
Mximo comn divisor I
Definicin
Sean a, b Z. Decimos que c Z, c 6= 0, es un Divisor comnde a y b, si c | a y c | b.Definicin
Sean a, b Z, con al menos uno de ellos distinto de cero. Sedice que c Z es el Mximo comn divisor de a y b,denotado por c = MCD(a, b), si y slo si, se satisfacen lassiguientes condiciones:
a. c | a y c | b.b. c es el mayor divisor comn de a y b. Es decir, si d es otro
divisor comn de a y b, entonces d | c.c. c > 0
EMD/ABB 177/698
Mximo comn divisor II
Ejemplo
Calcular el MCD(24, 18).
El conjunto de los divisores de 24 es: {1, 2, 3, 4, 6, 8, 12, 24}.El conjunto de los divisores de 18 es: {1, 2, 3, 6, 9, 18}.El conjunto de los divisores comunes es: {1, 2, 3, 6}.El mayor de los comunes es el 6. As que el
MCD(24, 18) = 6.
Propiedades
Sean a, b Z, con al menos uno de ellos distinto de cero.Entonces
EMD/ABB 178/698
Mximo comn divisor III
a. MCD(a, b) 0b. MCD(a, b) = MCD(b, a)
c. MCD(0, a) = |a|d. MCD(ka, a) = |a|, k Ne. MCD(a, b) = MCD(a,b) = MCD(a,b) =
MCD(a, b) = MCD(|a|, |b|)f. Si a = b = 0, entonces para todo c Z, c es un divisor
comn de a y b. Por tanto, no existe un MCD(a, b).
g. El MCD(a, b) es nico.
h. MCD(ka, kb) = |k|MCD(a, b), k 6= 0
EMD/ABB 179/698
Mximo comn divisor IV
Procedimiento para calcular el MCD(a, b)
Sean a, b N, a, b > 1.Se descompone a y b en sus factores primos. Luego, elproducto de los factores comunes elevados al menorexponente es el MCD(a, b). Es decir, suponga que
a = pk11 pk22 pk33 . . . pkrry
b = pl11 pl22 pl33 . . . plrr ,donde ki, li 0.
EMD/ABB 180/698
Mximo comn divisor V
Entonces
MCD(a, b) = pmn{k1,l1}1 p
mn{k2,l2}2 p
mn{k3,l3}3 . . . p
mn{kr,lr}r
Ejemplo
Calcular MCD(2520, 4950).
2520 = 23 . 32 . 5 . 7
4950 = 2 . 32 . 52 . 11
Luego, elMCD(2520, 4950) = 21 . 32 . 51 = 90.
Teorema
EMD/ABB 181/698
Mximo comn divisor VI
Sean a, b, q, r N, con a = bq + r, 0 r < b. Entonces
MCD(a, b) = MCD(b, r).
Ejemplo
24 = 18 1 + 6(a = 24, b = 18, q = 1, r = 6)18 = 6 3 + 0Luego,
MCD(24, 18) = MCD(18, 6) = 6.
Definicin
Sean a, b Z. Decimos que a y b son Primos relativos ocoprimos o primos entre si, si los nicos divisores comunesde a y b son 1 y -1. Es decir, MCD(a, b) = 1.
EMD/ABB 182/698
Mximo comn divisor VII
Ejemplo
El 8 y el 35 son primos relativos.
Teorema
Sean a, b Z con al menos uno de ellos distinto de cero.Entonces a y b son primos entre si, si y slo si, existenx0, y0 Z, tales que
ax0 + by0 = 1.
EMD/ABB 183/698
ContenidoINTRODUCCINNOCIONES DE LGICA FORMAL
IntroduccinClculo proposicionalFormas normalesClculo de predicado
TEORA DE CONJUNTOSConceptos y definicionesOperaciones con conjuntosPropiedades de las operaciones con conjuntosConjuntos numricosDivisibilidad y algoritmos de enterosAlgoritmo de EuclidesFuncin caractersticaSucesionesRepresentacin de conjuntos en una computadoralgebras booleanasProducto cartesiano o conjunto productoInduccin y recursin
TEORA DE NMEROS Y COMBINATORIAElementos de conteoPermutaciones: Se toma en cuenta el ordenCombinaciones: No toma en cuenta el ordenCombinaciones con repeticin
CONGRUENCIA, RELACIONES Y FUNCIONESCongruenciaEcuaciones diofnticas linealesCongruencias linealesRelacionesRelaciones de equivalenciaRelaciones de ordenFuncionesPrincipio del palomar
INTRODUCCIN A LA PROBABILIDADElementos de probabilidadProbabilidad condicional e independenciaVariables aleatorias
EMD/ABB 184/698
Algoritmo de Euclides I
Algoritmo de Euclides
Sean a, b N, a b > 0. Sea r0 = a, r1 = b. Aplicando enforma sucesiva la divisin segn Euclides, se tiene
r0 = r1q1 + r2, 0 < r2 < r1r1 = r2q2 + r3, 0 < r3 < r2
rk = rk+1qk+1 + rk+2, 0 < rk+2 < rk+1
rn2 = rn1qn1 + rn, 0 < rn < rn1rn1 = rnqn + rn+1, rn+1 = 0
Luego, el MCD(a, b) = rn, donde rn es el ltimo resto no nulo.
Nota: La sucesin {rn}n1 es finita, puesto que
r1 > r2 > r3 > 0. (estrctamente decreciente)
EMD/ABB 185/698
Algoritmo de Euclides II
Ejemplo
Calcular MCD(24, 18).
Solucin
En este caso r0 = a = 24, r1 = b = 18. Si se divide 24 entre 18,se obtiene r0 = r1 q1 + r2, 0 < r2 < r1. Es decir,24 = 18 1 + 6, 0 < 6 < 18. Como r2 6= 0, se divide r1 = 18entre r2 = 6 y se obtiene r1 = r2q2 + r3, donde r3 = 0. Como r2es el ltimo residuo distinto de cero, tenemos que
MCD(24, 18) = r2 = 6.
Ejemplo
Calcular MCD(25134, 19185).
EMD/ABB 186/698
Algoritmo de Euclides III
Solucin
En este caso r0 = 25134, r1 = 19185
r0 = r1 q1 + r2 = 19185 1 + 5949r1 = r2 q2 + r3 = 5949 3 + 1338r2 = r3 q3 + r4 = 1338 4 + 597r3 = r4 q4 + r5 = 597 2 + 144r4 = r5 q5 + r6 = 144 4 + 21r5 = r6 q6 + r7 = 21 6 + 18r6 = r7 q7 + r8 = 18 1 + 3r7 = r8 q8 + r9 = 3 6 + 0.
EMD/ABB 187/698
Algoritmo de Euclides IV
Luego,
MCD(25134, 19185) = r8 = 3 ltimo resto distinto de cero.
EMD/ABB 188/698
Ejercicios I
1. Sean a, c Z y b N. Suponga que 2b est a la derechade a; que a su vez, est a la derecha de b. Suponga que cest a la izquierda de 0. Cual de la siguientesafirmaciones es falsa?:
a. 2b > b b. c < 0 c. a > b d. b > 0 e. a < c
2. Si a y b son enteros consecutivos y a < b, entonces cul delas siguientes afirmaciones es verdadera para b a?a. 0 b. 1 c. 3a+ 2 d. 1 e. a b
EMD/ABB 189/698
Ejercicios II
3. Si a, b Z y b es el predecesor de a, y el sucesor de a es9 , entonces cul de las siguientes afirmaciones esverdadera para a+ b?
a. 15 b. 17 c. 21 d. 20 e. 19
4. Si a es un entero par y b es un entero impar, entoncescul de las siguientes afirmaciones es (son) siempreverdadera(s)?
a. Slo a2 es un nmero positivob. Slo b2 es un nmero positivoc. Slo (a b)2 es un nmero impar positivod. Slo a. y c.e. Slo b. y c.f. Ninguna de las anteriores
EMD/ABB 190/698
Ejercicios III
5. Aplique el algoritmo de Euclides para encontrarMCD(1001, 275), MCD(687,234).
6. Sea m Z+. Pruebe que(k + 1)(k + 2)(k + 3) (k +m), k 0 es divisible por m!.
7. Sea n Z+. Pruebe que (n!)2 divide a (2n)!.8. Sean a, b, c, d Z+, pruebe que si a | b y c | d, entonces
ac | bd
9 Pruebe que el producto de tres (3) enteros consecutivoses divisible por 6. Adems, 24 divide al producto si elprimero es par.
10. Pruebe que 100 | (1110 1)11. Sea n Z+. Pruebe que 30 | (n5 n)
EMD/ABB 191/698
Ejercicios IV
12. Pruebe que si n = st, s > 0, t > 0, entonces (s!)t |n!13. Sean n,m Z+ y a > 1. Pruebe que (an 1) | (am 1), si
y slo si n |m14. Encuentre aplicando el algoritmo de Euclides:
a. MCD(72, 16)b. MCD(80, 32)c. MCD(848, 656)d. MCD(93164, 5826)e. MCD(279492, 17478)f. MCD(3907853, 3802499)
15. Pruebe que MCD(a, b) es nico.
EMD/ABB 192/698
Mnimo comn mltiplo I
Definicin
Sean a, b Z {0}. El Mnimo comn mltiplo de a y b,representado por MCM(a, b), es el nico entero positivo c quesatisface las condiciones siguientes:
1. a | c y b | c ( esto dice que c es mltiplo comn).2. Si a | d y b | d con d > 0, entonces c d ( significa esto que
c es el menor de los mltiplos positivos comunes de a y b).
EMD/ABB 193/698
Mnimo comn mltiplo II
Definicin