Please contribute to the protection of the environment: print this document only if you consider it absolutely necessary.
Warning: This page contains likely dynamic content (i.e., resources in a wider sense).
Read all of this web page carefully because it contains important information for you.
Keep the link to it in safe custody, you may need to read this web page again.
Do not forget the associate learning project, an optional continuous evaluation out-of-class practical activity such that if you are thinking of grading with distinction (matrícula de honor, in Spanish), your participation in it is strongly recommended.
Do not forget either the corresponding talk pages.
This university learning plan consists of a primer on discrete mathematics and its applications including a brief introduction to a few numerical analysis.
'I was speaking one day to a chemical expert about Avogrado's hypothesis concerning the number of molecules of the gases in equal volume, and its relation with the so-called Mariotte's law and its consequences in modern chemistry, and he came to answer: "Theories, theories! All of that does not matter to me ... That is for those who do science, I just apply it." I kept silent, torturing my mind to finding out how science can be applied without doing it, and finally, when after some time I knew why our expert had been close to dying, I understood it finally.'
Miguel de Unamuno (1864-1936): De la enseñanza superior en España [On higher education in Spain], Madrid, Revista Nueva, 1899, http://www.liburuklik.euskadi.eus/handle/10771/24524, p. 45. Also, in: Obras Completas de Miguel de Unamuno, Vol. VIII (Ensayos), pp. 1-58 (the quotation, on page 32).
'Listening to my father during those early years, I began to realise how important it was to be an enthusiast in life. He taught me that if you are interested in something, no matter what it is, go at it full speed ahead. Embrace it with both arms, hug it, love it and above all become passionate about it. Lukewarm is no good. Hot is no good, either. White hot and passionate is the only thing to be.'
Office: 1904/1/9 (according to the planimetry of Cáceres campus facilities and services: building [Civil Engineering premises]/floor/office) (you may consult the course programme (ficha12a) to find out where it is).
The recommendations included in the Computer Engineering Curricula 2016* and in the Computer Science Curricula 2013†, among others, have been considered.
Regarding Discrete Mathematics, the latter report identifies the following topics as the knowledge base for discrete structures (pp.76-81):
(DS1) Functions, relations and sets,
(DS2) Basic logic,
(DS3) Proof techniques,
(DS4) Basics of counting,
(DS5) Graphs and trees, and
(DS6) Discrete probability,
to which we would add:
(DM1) Algebraic structures,
(DM2) Matrices,
(DM3) Algorithms and complexity, and
(DM4) Basic number theory.
On the other hand, we have to keep in mind that some of these topics are studied in other courses taught at the School of Technology: DS6, in Statistics (UEX 501270); DM2, in Linear Algebra (UEX 502382); DM3, in Introduction to Programming (UEX 502304) and in Analysis and Design of Algorithms (UEX 501273); DS5, in Analysis and Design of Algorithms (UEX 501273) and in Data Structures and Information (UEX 501271), although from an algorithmic point of view.
With respect to Numerical Calculus and in order to provide students with a sufficient introduction to the algorithms and methods for computing discrete approximations used to solving continuous problems, in terms of linear and non linear approaches to a problem, we identify as essential contents:
(NC1) Roots of Equations,
(NC2) Linear Algebraic Equations, and
(NC3) Curve Fitting (regression and interpolation).
On the other hand, again, we have to keep in mind that some of these topics are studied in other courses taught at the School of Technology: NC2, in Linear Algebra (UEX 502382); NC3, in Statistics (UEX 501270) (with regard to regression).
After taking this course students should have reached the following objectives:
Targets: Representation, formulation, abstraction, modelling, verification and generalization.
General: Acquire scientific culture and mathematical culture in particular. Enhance reflective and creative attitudes. Enhance skills and abilities of analysis, search, discovery, verification and generalization. Promote the development and enhancement of problem-solving skills and of positive attitudes towards mathematical, analytical and concrete critical thinking. Be prepared for independent, critical study and assessment of elementary academic and informative publications about the topics covered in the course. Develop the capacity for lifelong learning.
Common: Enhance the ability to develop strategies for problem solving and decision making. Increase the ability to interpret the results obtained. Increase the rigor in the arguments and develop the reading and writing skills, the ability to use information and the capacity to make written or oral presentation of ideas and reasoning.
Specific for themes 1 (Fundamentals) and 2 (Number Theory): Enhance the ability to understand and use the logical-mathematical language. Develop the capacity for abstraction through the construction of logical-mathematical arguments. Enhance the capacity of logical-mathematical reasoning in its deductive, inductive, abductive and algorithmic types.
Specific for themes 3 (Combinatorics) and 4 (Difference Equations): Enhance the capacity of logical-mathematical reasoning in its inductive, algorithmic and recursive types. Enhance the ability to count.
Although in respect of scientific knowledge, it has no particular prerequisites, some prior background in maths (mainly in algebra, calculus and probability) and computing (mainly in programming) is welcomed but in no way presupposed. Regarding English language, it may be desirable that you are at a intermediate conversational level, e.g. at least as skilled as an independent (self-reliant) user (level B) according to the Common European Framework of Reference for Languages*. You might find out your English level taking this free online English test and then you might improve your knowledge of the English language, for instance, practising your English skills at your level, and many more things available on these pages by the British Council (Prince of Asturias Award for Communication and Humanities 2005).
As this book cover the vast majority of the material of the course — which, incidentally, corresponds to what is currently taught in hundreds of universities in the field of discrete mathematics —, students are encouraged to adopt and study it. Rosen's book is both a textbook and a workbook with lots of exercises and practical cases (computer projects, computations and explorations). It is even a guidebook including suggested readings, Despite its encyclopaedic spirit, it is also a handbook including lists of key terms and results and review questions.
As you know, the content of newer editions are usually updated and improved versions of the content of older editions, occasionally including new content, so it is highly recommendable that, as far as possible, you read and study the new versions of the sections and exercises. However, within that aim of making continuous improvements, some contents may have been removed so it is also important to take a look to the older and newer editions, therefore keep mainly in mind these editions (even though only the seventh is highlighted):
All these companion websites include, among other material and resources, interactive demos, self assessments and extra examples.
Companion books describing solutions for each of the proposed exercisesedit
On the other side, this book is accompanied by books describing solutions for each of the proposed exercises, for instance, for the 5th and 7th US editions:
Companion books exploring and discussing contents and solutions to the proposed 'computer projects' and 'computations and explorations'edit
And also by the supplementary books exploring and discussing contents and solutions to the 'computer projects' and 'computations and explorations' sections, from the 7th US edition:
Companion book about applications of discrete mathematicsedit
Finally, you can download another supplement, one book about applications of discrete mathematics, last edition, paired with Rosen's book 6th edition, in any case for you to study it once you finish the course, except for the chapters that are of interest to it:
Participating in MATDIN is an optional continuous evaluation out-of-class practical activity which is worth a try for contributing to your personal developmentand because it might help you boost your course grade; furthermore, if you are thinking of grading with distinction ['matrícula de honor', in Spanish], your participation in this project is strongly recommended. Find out more on
its descriptive web page and in the welcome message to the course.
It is important that you become aware that joining the university project 'Discrete numerical mathematics' is optional. Therefore, it is entirely up to you to do it. But if you do it, remember, you are required to:
(a) use your true identity on free, open and public access web pages (Wikipedia) — although you can use an alias as your username, you must report your real identity (first, middle and last name) on your user page on the English Wikipedia —;
(b) be polite and respect diversity (please remember, diversity is a wealth, neither a problem nor a threat);
'Do I contradict myself? Very well then I contradict myself, (I am large, I contain multitudes.)' Walt Whitmann (1819-1892): Song of Myself (in Leaves of Grass, 1855)
Contents: ► Logic: propositions, propositional equivalences, predicates and quantifiers, nested quantifiers, translating English statements into the language of logic and vice versa, valid arguments and rules of inference; direct and indirect proofs, verification and refutation strategies (truth tables, proof by contraposition, proof by contradiction, normal forms, natural deduction, semantic tableaux). ► Sets: concepts and definitions, cardinality and power set; relations (membership, inclusion and equality), operations (union, intersection, complement, difference, symmetric difference) and properties, partition, cardinality of the union, cartesian product. ► Maps and functions: types (injective, surjective and bijective), monotony, representation (cartesian, arrow-set, matrix-based and graph-based), composition, inverse; multiset. ► Relations: properties, representing relations using matrices and graphs; equivalence relations, equivalence classes and partitions; tolerance relations; orderings, Hasse diagrams; preference relations. ► Cardinality: infinite sets, countability, Cantor's diagonal argument, Cantor's theorem and the continuum hypothesis. ► Induction: weak, strong and structural; well ordering. ► Algebraic structures: magma, semigroup, monoid, group, ring, integral domain, field; homomorphism.
Seminars/Labs: ► [1]: Proofs and refutations, I; ► [2]: Proofs and refutations, II; ► [3]: Proofs and refutations, III; ► [4]: Induction and recursion; ► [5]: Cardinality and algebraic structures.
Contents: ► Divisibility and modular arithmetic: divisibility, division algorithm, modular arithmetic. ► Primes and greatest common divisor: integer representations, prime numbers and their properties, the fundamental theorem of arithmetic, conjectures and open problems about primes, greatest common divisor and least common multiple, the Euclidean algorithm, Bézout's theorem and the extended Euclidean algorithm. ► Solving congruences: linear congruences, Euler's φ function, the Chinese remainder theorem, Euler-Fermat's theorem, Fermat's little theorem, Wilson's theorem and Wolstenholme's theorem. ► Applications of congruences: cryptography. ► Divisibility rules: power residues, divisibility rules. ► Diophantine equations: linear equations, systems.
Seminars/Labs: ► [6]: Divisibility, modular arithmetic, primes, gcd and congruences; ► [7]: Diophantine and congruence equations, I; ► [8]: Diophantine and congruence equations, II.
Contents: ► The basics of counting: the sum rule, the product rule, the subtraction rule (inclusion-exclusion principle) and the division rule; the pigeonhole principle and its generalization; binomial coefficients and identities; variations, permutations and combinations. ► Combinatorial proofs: bijective proofs and double counting proofs. ► Combinatorial modeling: 1st, sample selection and unit labelling with and without repetition; 2nd, grouping units (distribution, storage or placement of objects into recipients); 3rd, partitions of sets, and 4th, partitions of numbers.
Contents: ► Linear difference equations: homogeneous and non-homogeneous; with constant coefficients; direct; simple or multiple; indirect: systems of linear difference equations. ► Linear discrete dynamical systems: population dynamics, linear discrete dynamical models, BIDE models, Markov chains. ► Solving equations numerically: method of successive approximations (fixed point iteration); secant method.
Optional seminars/labs, two editathons (whenever we have time, the first in the middle of the semester and the second at the end; anyway, the exact content of this personal-enhancement tasks will not be mandatory covered on any exam): ► [14]: Start of the optional reading and writing of a mathematical and computational, reflective, critical and analytical short essay of the text A. K. Dewdney (1993) The Tinkertoy Computer and other machinations. Chapter 17: Automated Math. New York: W. H. Freeman. ('Juegos de ordenador. De cómo un par de programas obtusos pasan por genios en los tests de inteligencia.' Investigación y Ciencia, No. 116, May 1986, pp. 94-98, Prensa Científica, S. A. [In Spanish]). ► [15]: Start of the optional reading and writing of a mathematical and computational, reflective, critical and analytical short essay about the Collatz conjecture and its 'visualization' (for example: Collatz Graph: All Numbers Lead to One, de Jason Davies). (See also the sandbox/workshop of this course).
Appendices (optional) (some complimentary or curious facts apart from the present programme, although related to it)
English-language Wikipedia is a collective and voluntary work that, like all works, contains inaccuracies(1), while «perfection is a polished collection of mistakes» (phrase often attributed on the web to Mario Benedetti and to Mario Satz).
I encourage you to correct them, to contribute with everything you learn about the topics we deal with, to contrast with Wikipedia in other languages if you know them, to gather information from other texts, in short, to drink in good sources. And write new articles in the English-language Wikipedia. Ultimately, contribute to improve this free encyclopedia as you study and learn.
By way of example, some good sources on the web are:
Bibliography: theory and proposed and solved exercisesedit
In English:
In Spanish:
—¤— Kenneth H. Rosen. Discrete mathematics and its applications. New York, New York State (US-NY), United States: McGraw-Hill, 7th edition, 2012. ISBN978-0-07-338309-5. (Chapter 1 and related exercises).
—¤— Amador Antón y Pascual Casañ, Lógica Matemática. Ejercicios. I. Lógica de enunciados. Valencia, Valencian Community (ES-VC), Spain: NAU llibres, 3rd edition, 1987. ISBN84-85630-42-4
—¤— María Manzano y Antonia Huertas, Lógica para principiantes. Humanes de Madrid, Madrid, Community of Madrid (ES-MD), Spain: Alianza, 2006. ISBN84-206-4570-2.
—¤— Kenneth A. Rosen. Matemática discreta y sus aplicaciones. Aravaca, Madrid, Community of Madrid (ES-MD), Spain: McGraw-Hill/Interamericana de España, S.A.U., 5th edition, 2004. ISBN84-481-4073-7. (Sections 1.1, 1.2, 1.3, 1.4, 1.5, 3.1 and related exercises).
Baugher, Greg A. "Section 1.6 Rules of Inference"(Video). Department of Math/Science/Informatics, Penfield College, Mercer University. Georgia (US-GA), USA.
Baugher, Greg A. "Section 1.7 Introduction to Proofs"(Video). Department of Math/Science/Informatics, Penfield College, Mercer University. Georgia (US-GA), USA.
Baugher, Greg A. "Section 1.8 Proof Methods and Strategy"(Video). Department of Math/Science/Informatics, Penfield College, Mercer University. Georgia (US-GA), USA.
Summa Logicae (María Manzano, Gustavo Santos, Belén Pérez Lancho, José Meseguer, Enrique Alonso, Huberto Marraud, Antonia Huertas, Dick de Jongh, Giovanna D'Agostino, Alberto Policriti)
Zermelo's well-ordering theorem (Note: The fact that every set may be well ordered, is what most people apparently also call 'Well-ordering principle' (WOP); ref., e.g.: Bagaria, Joan, 'Set Theory', The Stanford Encyclopedia of Philosophy (Fall 2019 Edition), Edward N. Zalta (ed.), URL = <https://plato.stanford.edu/archives/fall2019/entries/set-theory/>, and so many others; what Wikipedia and Wolfram MathWorld and others call WOP is the particular case of being a well-ordered set by <; in short, the current situation in the literature is that WOP has two meanings, either Zermelo's Theorem or is well-orderd by <).
Worth-read chapter: Mosterín, Jesús (1993). Los conceptos científicos. In: Ulises Moulines, Carlos (ed.). La ciencia: estructura y desarrollo. Madrid:Trota, Consejo Superior de Investigaciones Científicas and Sociedad Estatal Quinto Centenario. Pages 15-30. ISBN 84-87699-72-3
Bibliography: theory and proposed and solved exercisesedit
In English:
In Spanish:
—¤— Kenneth A. Rosen. Discrete mathematics and its applications. 7th edition. (Sections 2.1, 2.2, 2.3, Chapter 9 and related exercises). McGraw-Hill, New York, New York, United States, 2012, ISBN978-0-07-338309-5
—¤— Kenneth A. Rosen. Matemática discreta y sus aplicaciones. 5th edition. (Sections 1.6, 1.7, 1.8, Chapter 7 and related exercises). McGraw-Hill/Interamericana de España, S.A.U., Aravaca (Madrid), Madrid, Spain, 2004, ISBN84-481-4073-7
Baugher, Greg A. "Section 2.1 The Basics of Sets"(Video). Department of Math/Science/Informatics, Penfield College, Mercer University. Georgia (US-GA), USA.
Baugher, Greg A. "Section 2.2 Set Operations"(Video). Department of Math/Science/Informatics, Penfield College, Mercer University. Georgia (US-GA), USA.
Krithivasan, Kamala. "Lecture 10 - Sets"(Video). Indian Institute of Technology Madras.
Soto Espinosa, Jesús. "Conjuntos finitos"(Vídeo). Guadalupe, Murcia, Región de Murcia (ES-MC), España: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Ejercicios"(Vídeo). Guadalupe, Murcia, Región de Murcia (ES-MC), España: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM). (Ejercicio 1).
Soto Espinosa, Jesús. "Aplicaciones entre conjuntos finitos"(Vídeo). Guadalupe, Murcia, Región de Murcia (ES-MC), España: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Ejercicios"(Vídeo). Guadalupe, Murcia, Región de Murcia (ES-MC), España: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM). (Ejercicio 2).
Soto Espinosa, Jesús. "Aplicaciones. Ejercicio 1"(Vídeo). Guadalupe, Murcia, Región de Murcia (ES-MC), España: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Aplicaciones. Ejercicio 2"(Vídeo). Guadalupe, Murcia, Región de Murcia (ES-MC), España: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Aplicaciones. Ejercicio 3"(Vídeo). Guadalupe, Murcia, Región de Murcia (ES-MC), España: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Y indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively.
All definitions tacitly require the homogeneous relation be transitive: for all if and then
A term's definition may require additional properties that are not listed in this table.
Bibliography: theory and proposed and solved exercisesedit
In English:
In Spanish:
—¤— Kenneth A. Rosen. Discrete mathematics and its applications. 7th edition. (Sections 2.5, 5.1, 5.2, 5.3, Chapter 9 and related exercises). McGraw-Hill, New York, New York, United States, 2012, ISBN978-0-07-338309-5
—¤— Kenneth A. Rosen. Matemática discreta y sus aplicaciones. 5th edition. (Sections 3.2.5, 3.3, 3.4, Chapter 7 and related exercises). McGraw-Hill/Interamericana de España, S.A.U., Aravaca (Madrid), Madrid, Spain, 2004, ISBN84-481-4073-7
The Continuum Hypothesis (la página web «oficial» de la hipótesis del continuo, en Infinity Ink [Nancy McGough, 1992]). Disponible en: http://www.ii.com/math/ch/
Y indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively.
All definitions tacitly require the homogeneous relation be transitive: for all if and then
A term's definition may require additional properties that are not listed in this table.
—¤— José García García and Manuel López Pellicer. Álgebra lineal y geometría. Curso teórico-práctico. 7th edition. Marfil, Alcoy, Spain. ISBN: 84-268-0269-9.
Bibliography: theory and proposed and solved exercisesedit
In English:
In Spanish:
—¤— Thomas Koshy. Elementary number theory with applications. Academic Press (an imprint of Elsevier Inc.), New York, United States, 2nd edition, 2007, ISBN: 978-0-12-372487-8
—¤— Kenneth A. Rosen. Discrete mathematics and its applications. 7th edition. (Chapter 4 and related exercises). McGraw-Hill, New York, New York, United States, 2012, ISBN978-0-07-338309-5
Kenneth A. Rosen. Elementary number theory and its applications. Addison-Wesley, Reading, Massachusetts, United States, 1986, ISBN 0-201-06561
—¤— Máximo Anzola y José Caruncho. Problemas de Álgebra. Tomo 2. Anillos - Polinomios - Ecuaciones. 3ª edición. Primer Ciclo, Madrid, Spain. (Capítulo 7 «Divisibilidad en y », 94 ejercicios resueltos; Capítulo 8 «Ecuaciones diofánticas», 27 ejercicios resueltos; Capítulo 9 «Sistemas de numeración», 25 ejercicios resueltos), 1982. ISBN84-300-6417-6.
—¤— Kenneth A. Rosen. Matemática discreta y sus aplicaciones. 5th edition. (Sections 2.4, 2.5, 2.6 and related exercises). McGraw-Hill/Interamericana de Spain, S.A.U., Aravaca (Madrid), Madrid, Community of Madrid (ES-MD), Spain, 2004, ISBN 84-481-4073-7
Soto Espinosa, Jesús. "Algoritmo de la división"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Números primos, ejemplo 1"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Números primos, ejemplo 2"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Números primos, ejemplo 3"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Números primos, ejemplo 5"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Infinitud de los números primos"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Teorema fundamental de la aritmética"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Máximo común divisor"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Máximo común divisor, ejemplo 1"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Máximo común divisor, ejemplo 2"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Máximo común divisor, ejemplo 3"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Máximo Común Divisor, ejemplo 4"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Algoritmo de Euclides"(Video). Universidad Católica de Murcia (UCAM).
— Bézout's lemma
Soto Espinosa, Jesús. "Identidad de Bézout"(Video). Universidad Católica de Murcia (UCAM).
Soto Espinosa, Jesús. "Identidad de Bézout, ejemplo 1"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Identidad de Bézout, ejemplo 2"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
— Modular arithmetic. Euler's φ function (totient function)
Soto Espinosa, Jesús. "Función φ de Euler"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Función φ de Euler, propiedad 1"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Función φ de Euler, propiedad 2"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
— Diophantine equations
Hervás Jorge, Antonio. "Ecuaciones diofánticas"(Video). Universidad Politécnica de Valencia (UPV).
Soto Espinosa, Jesús. "Ecuación diofántica"(Video). Universidad Católica de Murcia (UCAM).
— Combinatorial proofs: 1st, bijective proofs; 2nd, double counting proofs; 3rd, using distinguished element, and 4th, using the inclusion-exclusion principle
—¤— Kenneth A. Rosen. Discrete mathematics and its applications. 7th edition. (Chapters 6 and 8 and related exercises). McGraw-Hill, New York, New York, United States, 2012, ISBN978-0-07-338309-5
I. Espejo Miranda, F. Fernández Palacín, M. A. López Sánchez, M. Muñoz Márquez, A. M. Rodríguez Chía, A. Sánchez Navas and C. Valero Franco. Estadística Descriptiva y Probabilidad. Servicio de Publicaciones de la Universidad de Cádiz. (Appendix 1: Combinatoria). 2006. (GNU FDL). http://knuth.uca.es/repos/l_edyp/pdf/febrero06/lib_edyp.apendices.pdf
—¤— Kenneth A. Rosen. Matemática discreta y sus aplicaciones. 5th edition. (Chapters 4 and 6 and related exercises). McGraw-Hill/Interamericana de España, S.A.U., Aravaca (Madrid), Madrid, Spain, 2004, ISBN84-481-4073-7
Baugher, Greg A. "Section 6.1 The Basics of Counting"(Video). Department of Math/Science/Informatics, Penfield College, Mercer University. Georgia (US-GA), USA.
Krithivasan, Kamala. "Lecture 27 - Pigeonhole Principle"(Video). Adyar, Chennay (formerly Madras), Tamil Nadu (IN-TN), India: Indian Institute of Technology Madras.
Krithivasan, Kamala. "Lecture 30 - Generating Functions"(Video). Adyar, Chennay (formerly Madras), Tamil Nadu (IN-TN), India: Indian Institute of Technology Madras.
Krithivasan, Kamala. "Lecture 31 - Generating Functions (cont.)"(Video). Adyar, Chennay (formerly Madras), Tamil Nadu (IN-TN), India: Indian Institute of Technology Madras.
Soto Espinosa, Jesús. "Principios básicos de conteo"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Ejercicios"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM). (Ejercicio 3).
— Variations, permutations and combinations
Soto Espinosa, Jesús. "Variaciones"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Variaciones con repetición"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Permutaciones"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Permutaciones, ejemplo 1"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Permutaciones circulares"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Permutaciones con repetición"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Combinaciones"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Combinaciones con repetición"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Ejercicios"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
— Binomial numbers
Soto Espinosa, Jesús. "Número binomial"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Número binomial, ejercicio 2"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Número binomial, ejercicio 3"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Número binomial, ejercicio 5"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Número binomial, fórmula de Stifel"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Coeficiente Multinomial, ejercicio 1"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Combinatoria, ejemplo 6"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Combinatoria, ejemplo 7"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Combinatoria, ejemplo 8"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Combinatoria, ejemplo 9"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Combinatoria, ejemplo 10"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Combinatoria, ejemplo 11"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Teorema del binomio"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Fórmula de Leibniz"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Ejercicios"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
— Inclusion-exclusion principle
Soto Espinosa, Jesús. "Principio de inclusión-exclusión"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Generalización del principio de inclusión-exclusión"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Principio de inclusión-exclusión - Ejemplo 1"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Desarreglos"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Contando desarreglos"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Ejercicios"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
— Partitions
Soto Espinosa, Jesús. "Particiones. Número de Bell"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Número de Stirling de segunda clase"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Soto Espinosa, Jesús. "Ejercicios"(Video). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Bibliography: theory and proposed and solved exercisesedit
En español:
En inglés:
Richard Johnsonbaugh. Discrete mathematics. 6th edition. (Chapter 7 and corresponding exercises). Prentice Hall Inc., New York, New York, United States, 2005, ISBN0-13-117686-2
—¤— Kenneth A. Rosen. Discrete mathematics and its applications. 7th edition. (Chapters 5 and 8 and corresponding exercises). McGraw-Hill, Nueva York, Nueva York, Estados Unidos, 2012, ISBN978-0-07-338309-5
Javier Cobos Gavala. Apuntes de introducción a la matemática discreta. (E.T.S. de ingeniería informática, University of Seville). http://ma1.eii.us.es/material/IMD_ii_Ap.pdf
—¤— Richard Johnsonbaugh. Matemáticas discretas. 6th edition. (Chapter 7 and corresponding exercises). Pearson Educación de México, S.A. de C.V., Naucalpan de Juárez, Edo. de México, México, 2005, ISBN970-26-0637-3
—¤— Kenneth A. Rosen. Matemática discreta y sus aplicaciones. 5th edition. (Chapters 4 and 6 and corresponding exercises). McGraw-Hill/Interamericana de España, S.A.U., Aravaca (Madrid), Madrid, Spain, 2004, ISBN84-481-4073-7
Enrique Vílchez Quesada. Resolución de relaciones de recurrencia lineales no homogéneas con coeficientes constantes a través de valores y vectores propios. Uniciencia, 24, 2010, pp. 121-132. https://dialnet.unirioja.es/servlet/articulo?codigo=5381351
Krithivasan, Kamala. "Lecture 32 - Recurrence relations"(Video). Adyar, Chennay (formerly Madras), Tamil Nadu (IN-TN), India: Indian Institute of Technology Madras.
Krithivasan, Kamala. "Lecture 33 - Recurrence relations (cont.)"(Video). Adyar, Chennay (formerly Madras), Tamil Nadu (IN-TN), India: Indian Institute of Technology Madras.
Krithivasan, Kamala. "Lecture 34 - Recurrence relations (cont.)"(Video). Adyar, Chennay (formerly Madras), Tamil Nadu (IN-TN), India: Indian Institute of Technology Madras.
Rodríguez Álvarez, María José. "Resolución de recurrencias con Mathematica"(Video). Departamento de Matemática Aplicada, Escuela Técnica Superior de Ingeniería Informática. Valencia, Valencian Community (ES-VC), Spain: Universidad Politécnica de Valencia (UPV). (Otra URL)
Bibliography: theory and proposed and solved exercisesedit
In English:
In Spanish:
—¤— Kenneth A. Rosen. Discrete mathematics and its applications. 7th edition. (Chapters 10 and 11 and corresponding exercises). McGraw-Hill, New York, New York, United States, 2012, ISBN978-0-07-338309-5
—¤— Kenneth A. Rosen. Matemática discreta y sus aplicaciones. 5th edition. (Chapters 8 and 9 and corresponding exercises). McGraw-Hill/Interamericana de España, S.A.U., Aravaca (Madrid), Madrid, Spain, 2004, ISBN84-481-4073-7
Krithivasan, Kamala. "Lecture 14 - Graphs"(Video). Adyar, Chennay (formerly Madras), Tamil Nadu (IN-TN), India: Indian Institute of Technology Madras.
Krithivasan, Kamala. "Lecture 15 - Graphs (Contd.)"(Video). Adyar, Chennay (formerly Madras), Tamil Nadu (IN-TN), India: Indian Institute of Technology Madras.
Soto Espinosa, Jesús. "Matemática discreta"(Collection of videos). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
Martín Barreiro, Carlos. "El problema de la interpolación lineal"(Video). Santiago de Guayaquil, Provincia del Guayas (EC-G), Ecuador: Facultad de Ciencias Naturales y Matemáticas, Escuela Superior Politécnica del Litoral (ESPOL).
Martín Barreiro, Carlos. "Polinomio de Lagrange"(Video). Santiago de Guayaquil, Provincia del Guayas (EC-G), Ecuador: Facultad de Ciencias Naturales y Matemáticas, Escuela Superior Politécnica del Litoral (ESPOL).
Martín Barreiro, Carlos. "Polinomio de Lagrange. Ejemplo"(Video). Santiago de Guayaquil, Provincia del Guayas (EC-G), Ecuador: Facultad de Ciencias Naturales y Matemáticas, Escuela Superior Politécnica del Litoral (ESPOL).
— Lagrange polynomial
Martín Barreiro, Carlos. "Polinomio de Newton"(Video). Santiago de Guayaquil, Provincia del Guayas (EC-G), Ecuador: Facultad de Ciencias Naturales y Matemáticas, Escuela Superior Politécnica del Litoral (ESPOL).
Martín Barreiro, Carlos. "Polinomio de Newton. Ejemplo"(Video). Santiago de Guayaquil, Provincia del Guayas (EC-G), Ecuador: Facultad de Ciencias Naturales y Matemáticas, Escuela Superior Politécnica del Litoral (ESPOL).
Martín Barreiro, Carlos. "Análisis numérico"(Vídeo). Santiago de Guayaquil, Provincia del Guayas (EC-G), Ecuador: Facultad de Ciencias Naturales y Matemáticas, Escuela Superior Politécnica del Litoral (ESPOL).
Soto Espinosa, Jesús. "Momentos de ciencia"(Collection of videos). Guadalupe, Murcia, Region of Murcia (ES-MC), Spain: Escuela Politécnica Superior, Universidad Católica San Antonio de Murcia (UCAM).
More multimedia by the mentioned authors and by othersedit
In English:
In Spanish:
Baugher, Greg A. "Greg A. Baugher YouTube channel"(Collection of videos). Department of Math/Science/Informatics, Penfield College, Mercer University. Georgia (US-GA), USA.
Herke, Sarada. "Spoonful of Maths"(Collection of videos). School of Mathematics and Physics, The University of Queensland. Brisbane, Queensland (AU-QLD), Commonwealth of Australia.
Hervás Jorge, Antonio. "Colección de vídeos". Departamento de Matemática Aplicada, Escuela Técnica Superior de Ingeniería Informática. Valencia, Comunidad Valenciana (ES-VC), España: Universidad Politécnica de Valencia (UPV).
Jordán Lluch, Cristina. "Colección de vídeos". Departamento de Matemática Aplicada, Escuela Técnica Superior de Ingeniería Informática. Valencia, Comunidad Valenciana (ES-VC), España: Universidad Politécnica de Valencia (UPV).
Martín Barreiro, Carlos. "Análisis numérico"(Course). Santiago de Guayaquil, Provincia del Guayas (EC-G), Ecuador: Facultad de Ciencias Naturales y Matemáticas, Escuela Superior Politécnica del Litoral (ESPOL).
Rodríguez Álvarez, María José. "Colección de vídeos". Departamento de Matemática Aplicada, Escuela Técnica Superior de Ingeniería Informática. Valencia, Comunidad Valenciana (ES-VC), España: Universidad Politécnica de Valencia (UPV).
Soto Espinosa, Jesús. "Colección de vídeos". Unidad Central de Informática / Escuela Politécnica Superior. Guadalupe, Murcia, Región de Murcia (ES-MC), España: Universidad Católica San Antonio de Murcia (UCAM).
Sample exam questions, instrumental and relational[note 1], and some answers
'It is axiomatic that the greater the student's individual effort, the more thorough will be his (sic) learning.' Timothy J. Fitikides: Common mistakes in English, Longmans, 6ª edición / 6th edition, 2000, p. vii.
The following exercises with solution are sample exam questions and answers for the contents of the course.
You should be able to respond any of them in a maximum of 30 minutes.
It is highly important that you keep in mind that when you sit an exam, both theoretical (including proofs of theorems) and practical questions about all topics worked out in class may be asked.
The concreteness of the questions within the context of these examples implies in no case a course content cut.
Rigor when it comes to carrying out the solutions must be the central focus.
Show what you do and how you do it.
Do not simplify your answers, write legibly and explain your work, showing all intermediate steps, seeking to ensure that your arguments are clear and logically sound.
Label, or define, any variables and notation you choose to work with; also explain how you are solving each question as you go along, for example, stating clearly any theorem or result you use; neatness, cleanliness and organization count.
Once you consider an exercise solved, you can check your work against our resolution (however, keep in mind the possibility of correct alternative paths to the solution).
Important if you have joined MATDIN (the learning project on Wikipedia): You might like to see these exercises as seeds to help you in finding examples to illustrate your contributions to the project.
Question L1. (2.5 points).
On the island of truthfuls and deceitfuls — another nomenclature in the literature for the
couple have been (knights, knaves) and (truth-tellers/'truthers', liars) — there are two types of inhabitants, 'truthfuls' who always tell the truth and 'deceitfuls' who always lie. It is assumed that every inhabitant is either a truthful or a deceitful person. There were two inhabitants, and , standing together in the front yard of a house. You passed by and asked them, 'Are you truthful or deceitful persons?'
a) answered, 'If is a truthful person then I am a deceitful person.' Can it be determined whether and were truthfuls or deceitfuls? (1.25 p.)
b) Afterward, said, 'Don't believe ; he's lying.' With this new information, can it be determined whether and were truthfuls or deceitfuls? (1.25 p.)
Solution:
Let us use for ' is a truthful person' --- therefore, is an abbreviation for ' is a deceitful person' ---.
a) 's statement, 'If is a truthful person then I am a deceitful person', can be expressed as and the fact that says it, as . In view of the truth table:
the only model for is the 2nd interpretation, so it can be determined that is a truthful person and a deceitful person.
b) 's statement, 'Don't believe ; he's lying', is equivalent to ' is a deceitful person', which can be expressed as and the fact that says it, as , which simply says that neither both and can be truthfuls nor deceitfuls at the same time, and this adds nothing new, as expected because it was already determined. Indeed, in view of the truth table:
we notice that everything remains the way it was, the 2nd interpretation is again a model, but now for .
Question L2. (2.5 points)
With the help of propositional logic, prove that the following argument is valid or not. 'This program will compile whenever we have declared the variables. However, in truth, we will declare the variables precisely if we do not forget to do so. It turns out that the program has not compiled. Then it follows that we have forgotten to declare the variables.' Important: Do not solve it using truth tables.
Solution:
You can check the complete solution through semantic tableaux of several examples in this document (in Spanish, for the time being); (in particular, see exercise 7).
Question L3. (2.5 points).
a) Define adequate set of connectives (asc), also called completely expressive or functionally complete set of connectives.
b) Provide two examples of two-element asc, explaining why they are so and assuming that we know the asc which elements are the most usual connectives .
Solution:
a) In Propositional Logic, an adequate set of connectives (asc) is any set of connectives such that every logical connective can be represented as an expression involving only those belonging to the asc.
b) As it is said in the wording, we assume that we know that the set of the most usual connectives, is an asc. Two two-element asc are the sets and . In effect, we only have to check, for each two-element set, that the missing most usual connectives may be represented only with the ones in the set:
Question L4. (2.5 points).
There are animals on a hill, they are two-legged or four-legged. A villager says: 'At least one of the animals has two legs and given any pair of animals, at least one of them has four legs.'
(a) Formalise in predicate logic what the local said.
(b) How many of them are two-legged and how many are four-legged?
Solution:
Considering the set of animals on the hill as the universe of discourse, let be:
(a) ;
(b)
Translating (1) and (15) into English: (1) there is a two-legged animal and (15) there is no pair of animals in which both are two-legged, so there is only one two-legged animal and therefore, 76 four-legged animals.
Question L5. (2.5 points).
Source: Lewis Carroll, Symbolic Logic: Part I. Elementary (Macmillan, 1896), pg. 118. Public Domain.
40.
(1) No kitten, that loves fish, is unteachable;
(2) No kitten without a tail will play with a gorilla;
(3) Kittens with whiskers always love fish;
(4) No teachable kitten has green eyes;
(5) No kittens have tails unless they have whiskers.
Universe = 'kittens'; A = loving fish; B = green-eyed; C = tailed; D = teachable; E = whiskered; H = will play with a gorilla.
You are required to:
(a) Formalise all these statements into Predicate Logic.
(b) In the universe of kittens and using Predicate Logic, deduce the one conclusion that follows from these statements and makes the argument valid.
(c) Translate your symbolic answer into English.
Solution:
Considering the set of kittens as the universe of discourse, let be:
(a) (1) ;
(2) ;
(3) ;
(4) ;
(5) .
(b)
(c) No green-eyed kitten will play with a gorilla.
Question L6. (2.5 points).
Formalise into Predicate Logic:
(a) 'All that is , it is also .'
(b) 'If all is , then it is also .'
(c) 'There is none which is or and is not .'
Solution:
(a) .
(b) It can be rewritten as 'if all is , then all is too,' therefore, . Warning!, but .
(c) . Or put it in other words, 'if something is or then it is ,' which in the language of Predicate Logic is written as follows: .
(a) Propose three sets, and , such that , and . (0,5 points).
(b) According to a survey of a certain group of students, they said that, if they had to decide between two courses, equally interesting because of their contents, they prefer that one for which the time they dedicate to study it is the lowest and for which they foresee the best results in exams. In case of equality of study times and of exam results forecasts, they are indifferent to them. Study the properties of this binary relation. (2 points).
be a binary relation defined on the set , for every two elements and in , where is the figure of the units of the usual product between two natural numbers (for example, ).
a) Find out theCayley table for the operation on .
b) Is an abelian group? (You can reason using the Cayley table).
Solution:
a) Here is the Cayley table of the binary operation defined on the set :
b) Let us check if satisfies the five requirements (axioms) to be qualified as an abelian group:
a) is closed under (it is also said that is a closed operation or an internal composition law on ) since for all and in , . It is easy to reason using the table: every number in the table is an element of .
b) is associative on — we could check every triad, , and so on, however it is easier to reason using the fact that the product () of natural numbers is associative: simply, , is true since when we multiply the unit digits among natural numbers we have to carry no number —;
c) is conmutative (the table is symmetric with respect to the main diagonal);
d) the identity for in is as can be seen from the Cayley table since the first row and the first column are the same than the heading row and column, respectively;
e) not every element is invertible — we can use the table for checking this: given a certain number, heading a row, we only have to find out which other number gives the identity when operated with the former one, and this can be done by searching for the identity on that row (for example, is the inverse of because [we search for on the second row (headed by ), finding it on the fourth column (headed by ])—: the inverse of is , of is , of is and of is , but has no inverse — when operating any other number with the result is always (such a number, as in this case, is called an absorbing element for in [as zero for the product of integers]), so it is impossible to obtain the identity as a result —.
In short, has not abelian group structure (it has an abelian monoid structure).
Question C1. (2.5 points).
Proof by definition that is an infinite set.
Solution:
A set is infinite precisely if there exists a bijection between it and one of its proper subsets (definition by Dedekind). As an example, consider , defined by . Let us prove that it is a bijective mapping. In effect:
is a mapping , which is trivial, as if is given and because of the definition of , there exists , this being unique for each , that is, that if , then, because of the definition of , ;
is injective , which is trivial because of the definition of , as if , that is, if , then, ;
is surjective , which is also trivial due to the definition of , as if is given, then satisfies .
Question C2. (2.5 points).
Knowing that (integers) is a denumerable set and that the denumerable union of denumerable sets is a denumerable set, prove that (rationals) is a denumerable set.
Solution:
is a denumerable set as it can be expressed by the denumerable union , where every is a denumerable set, since , defined by and is a bijection. Note that the set is the set of all the rational numbers that have the same denominator .
Cuestión C3. (2.5 points).
Let be a denumerable set and let . Prove that is a denumerable set.
Solution:
As is a denumerable set then --- by definition of denumerable set --- there is a bijection . Let , defined by , if and by , if , that is, the correspondence is defined on two subdomains, on as the constant correspondence , a bijection, and on as , also a bijection, and as such subdomains are disjoint and their images, and are disjoint too, then is a bijection.
a) Prove that, for any , is divisible by . (1.25 p.)
b) Calculate the remainder of (for any ), when it is divided by . (1.25 p.)
Solution:
We use congruence relation theory.
a) On the one hand:
On the other:
Substituting in :
which, by definition of congruence relations, means that is divisible by .
b) On the one hand:
On the other:
If we add side by side and :
In other words, the requested remainder is .
(i) Because congruence relations are symmetric and transitive. (ii) Rising each side of the congruence relation to the power . (iii) Multiplying each side of the congruence relation by . (iv) Multiplying each side of the congruence relation by . (v) Rising each side of the congruence relation to the power .
Question NT3. (2.5 points).
One company spent euros in buying electronic devices, some of them ground breaking and providing maximum performance. Smartphones were euros each, tablets were euros each and laptops were euros each. How many of each device did they buy? Solve this question using the theory of:
a) diophantine equations;
b) congruence equations.
Solution:
Once translated the information from the wording into a system of linear equations and simplifying the latter:
a) A diophantine equation has solution precisely if . In such a case,
is a particular solution of the equation, where and and are a pair of Bézout coefficients (the coefficients of and in one linear combination that is equal to ) (Bézout's identity). The general solution of that equation is:
where is a particular solution and .
The following table shows the use of the extended Euclidean algorithm for this case. The computation stops when the remainder is zero (in red color). The previous remainder, (also in red color), is the greatest common divisor. Bézout coefficients are and (in magenta color). Numbers in cyan color, and , are, up to the sign, the quotients of the original numbers by the greatest common divisor.
index i
quotient qi−1
remainder ri
si
ti
0
99
1
0
1
19
0
1
2
99 ÷ 19 = 5
99 − 5 × 19 = 4
1 − 5 × 0 = 1
0 − 5 × 1 = −5
3
19 ÷ 4 = 4
19 − 4 × 4 = 3
0 − 4 × 1 = −4
1 − 4 × (−5) = 21
4
4 ÷ 3 = 1
4 − 1 × 3 = 1
1 − 1 × (−4) = 5
−5 − 1 × 21 = −26
5
3 ÷ 1 = 3
3 − 3 × 1 = 0
−4 − 3 × 5 = −19
21 − 3 × (−26) = 99
Thus,
is a particular solution and:
is the general solution, where .
So, how many of each device did they buy, knowing that they bought at least one device of each type? Let us see. We know that and that . Thus, and , and consequently, and . As , . Substituting in the equations, we obtain: , and .
Sol.: smartphones, tablets and laptops.
b) As a congruence equation, it could be:
Or, equivalently:
As , this way prompts us to consider all positive multiples of , lesser than , as possible solutions: .
Let us try the other way. The diophantine equation could also be seen as the following congruence equation:
Or, equivalently:
As , the equation has a unique solution , which is:
that is to say,
Exploring the potential residues, we find out that:
and thus, multiplying this congruence six times by itself, side by side:
and, as a congruence relation is transitive:
In other words, (since ).
As , we obtain that .
Finally, from , we can assess the value of , .
Sol.: smartphones, tablets and laptops.
Question NT4. (2.5 points).
How could we distribute litres of water in a total of different containers of , and litres? Solve this question using the theory of Diophantine equations.
Solution:
Let , , and denote the number of containers of , and liters, respectively, used in the solution. The conditions set forth in the statement of the question are taken up by the equations: and . By subtracting the first equation from the second equation: , that is a Diophantine equation. As , such Diophantine equation has integer solutions. As , the Bézout coefficients are and . A particular solution is: , . The general solution is: , , where . Assuming that at least one container of each type is involved in the solution, then . By replacing and with the general solution found, then, on the one side: , hence , thus and therefore, , and on the other: , hence , thus , that is, and therefore, . Thus, . If is replaced in the general solution with its value, and , then it is obtained that .
Sol.: Assuming that at least one container of each type must be filled, then the liters of water can be distributed using containers of liter, of liters and of liters. (If such a thing is not assumed, then another solution would be possible: containers of liter, of liters and of liters. [Verify this]).
Question NT5. (2.5 points).
Abigail wants to send Balbina the most simple call message: eh. They can only send numbers. Abigail and Balbina use the letters' position in the alphabet to code them (thus, Abigail codes e as 06 and h as 08). They use RSA to encrypt their messages. If Abigail choose and as the ground primes for RSA:
a) imagine you are Abigail and obtain the encrypted message that you have to send to Balbina;
b) imagine you are Balbina and decrypt the encrypted message that Abigail has sent to you.
Solution:
Following the steps of RSA algorithm:
1) , .
2) .
3) (Euler phi of ).
4) We have to choose as the secret key () a relatively prime with and less than , at the same time; we choose .
5) The secret key and the public key () are linked by the equation , in this case: , so .
6) If we code the original message, (eh), we have 0608. It can be proven that that if the coded message satisfies , then the ciphered message , also satisfies . As we are interested in code, then cipher, then decipher and finally decode, we have to group into blocks so that each one of their individual coding is less than . Let and be the coded blocks and let and be the ciphered blocks. As RSA method establishes, the encryption is performed by solving the congruence equation and the decryption by solving the congruence equation .
Let us answer now the two sections of the question.
a) Putting ourselves in the shoes of Abigail, let us assess the ciphered message that we have to send to Balbina. Let us cipher : the solution of is . Let us cipher : the solution of is . Thus, the message that we have to send is: 0608.
b) Putting ourselves in the shoes of Balbina, let us decipher the ciphered message that Abigail has sent us. Let us decipher : the solution of is . Let us decipher : the solution of is . Thus, the message we have just deciphered is: 0608.
Question CT1. (2.5 points)
Let be the set of decimal digits, that is, . Using combinatorial reasoning, calculate:
a) The number of subsets of which elements are all primes.
b) The number of subsets of having a prime number of elements.
Solution:
a) Let be the set consisting of the the prime numbers in . What is actually requested is the number of nonempty (nonvoid) subsets of , in other words, subtracting one (the empty set) from the total number of subsets of :
Sol.: subsets.
b) The total number of subsets of elements of a set of elements is given by . Thus, running over the prime numbers in :
Sol.: subsets.
Question CT2. (2.5 points)
A group of twelve people visit a museum. Everybody is wearing a woolen overcoat. Upon entering, they leave their coats in the attended cloakroom. On leaving, the cloakroom attendant puts the twelve coats on the counter. Each person in the group picks out one at random, completely absent-minded because of a very interesting discussion. Using combinatorial reasoning, calculate in how many ways can the coats be chosen by them so that none of them get their own coat back.
Solution:
This involves finding the number of derangements of objects. Instead of calculating for , we are going to do for the general case of having objects. Let denote the objects themselves. Let be the set of all permutations of the objects and let be the set of all derangements that have fixed elements. Then, the set of all derangements is:
Let us see it:
How many permutations fix one specific number? The answer is the number of permutations of the other (non fixed) numbers, that is to say, , and as there are numbers, then, the number of permutations that fix any of these numbers is .
How many permutations fix two specific numbers? The answer is the number of permutations of the other (non fixed) numbers, that is to say, , and as there are ways of choosing two different numbers out of numbers, then, the number of permutations that fix any two of these numbers is .
Let us note that in the case of , that is, , when we subtract those which fix the , then we are subtracting once those which fix both the and the and when we subtract those that fix the we are subtracting again those which fix both the and the . Thus, we have to add them one time. If we follow this reasoning, the number of permutations (derangements) for which no number is in its original place is:
Thus, if , there are:
derangements. Sol.: In ways.
Question CT3. (2.5 points)
An urn contains seven balls numbered one through seven. They are randomly chosen, one by one and without reposition until the urn is empty. As they are removed from the urn, we write their figures down from left to right on a first out, first writen basis. Using combinatorial reasoning calculate how many numbers thus formed start and end with an even digit.
Solution:
There are positions for the figures. At both ends, hypotheses imply even figure. There are three even figures between and : , and . Being guided by the distribution of objects into recipients models, consider these even figures (distinguishable boxes) and the two ends (distinguishable objects) of the seven-digit number, on an underlying injective mapping (at most, one end by each figure, as there are not two balls with the same figure). For each one of these cases at the ends (each one of the variations) we have to take into account all the possibilities for the intermediate positions. The number of these possibilities is given by the permutations of elements (one new abstraction as distinguishable objects [the intermediate positions] being distributed into distinguishable recipients [the figures , and and the even figure that is at none of the ends of the seven-digit number thus formed], this time on an underlying bijective mapping). Applying the rule of product:
Sol.: numbers.
Question CT4. (2.5 points)
A secret ballot is made in a meeting of seventeen people. Two people have cast invalid ballots, three have cast blank ballots, five have cast dissenting votes and seven have cast assenting votes. Using combinatorial reasoning calculate in how many ways this could have occured.
Solution:
Let us use the occupancy model for the non ordered distribution of balls into boxes; balls and boxes representing ballots and people, respectively. Consider the persons (distinguishable boxes) and the assenting ballots (indistinguishable balls), on an underlying injective mapping (at most, one ballot by each person) — alternatively, we could consider the number of subsets of elements from a set of elements —. In any case, there are ways of distributing the assenting ballots into the boxes. For each one of these cases (each one of the combinations), there are empty boxes left. Now, using a similar reasoning, there are ways of distributing the dissenting ballots into the boxes, with empty boxes remaining for each one of these cases. Similarly, there are ways of distributing the blank ballots into the boxes, with empty boxes remaining for each one of the cases. So, lastly, there are ways in which invalid ballots can be placed into the boxes. Applying the rule of product:
Sol.: In ways.
Question CT5. (2.5 points).
Use a combinatorial reasoning to respond.
a) A number is palindrome if it reads the same from left to right and from right to left. In base ten, how many seven-digit numbers are palindromes? (1.25 p.)
b) Let us assume a sided polygon network (-gon network). Calculate , the number of nodes (vertices) of the network, knowing that the number of line segments (sides + diagonals) is . (1.25 p.)
Solution:
a) A seven digit palindrome fits into the model , where . There are possibilities for , for , for and other possibilities for . Because of the rule of product, there is a total of seven digit palindromes.
b) If is the number of nodes, then the number of line segments is the number of subsets of two elements (each line segment can be viewed as a subset of two elements, as it can be abstracted from the fact that it joins two nodes) from a set of elements (the nodes), and this number is, by definition of combination, . Then, . Thus, .
Question RR1. (2.5 points)
Let the following be the definition of the sum of two natural numbers and :
Prove that the solution of this recurrence is .
Solution:
Let us note that is alien to recursion. Thus, in an easier but equivalent way, denoting by , we get a linear non homogeneous recurrence relation with constant coefficients and with a constant function as the function on the RHS of the equation:
a) General solution of the homogeneous:
The characteristic polynomial is:
thus, is a simple characteristic root.
The general solution of the homogeneous is:
b) Particular solution of the non homogeneous:
As the function on the RHS is constant, let us try out a general constant (real number) as a possible particular solution:
but this is a contradiction, so we have to increase the degree of the polynomial. Let us try out with a first degree polynomial, . Substituting:
Thus:
is a particular solution of the non homogeneous.
c) General solution of the non homogeneus:
d) Considering the initial conditions:
From the initial condition, , we have:
Substituting in (1), we get the desired solution:
or, in other words:
Question RR2. (2.5 points)
Let and be the numbers of malicious software belonging to two malware types, in the day , that coexist in a certain insecure wide area network (WAN) under malware evolution daily control. Let us assume that the original memberships were of and and that the coexistence evolution is as follows:
every day, the growth in malware type is the sum of the triple of the growth in type on the previous day and the growth in type also on the previous day plus seven new malware (that were classified as type ),
and also every day, the growth in malware type is the result of subtracting the growth in type on the previous day from the growth in type on the previous day, plus three new malware (that were classified as type ).
Find out and solve the system of recurrence equations of the evolution of the malware.
Solution:
Let us analyze the evolutions of the two types of malware on their own growths (that these evolutions had to be calculated in terms of the populations or not is not specified by the wording and, on the other side, calculating them on their growths is easier because the order of the recurrence relation has decreased in one time unit). Let and denote the growths from time to time , i.e. and . The system of linear recurrence equations that correponds to this situation is:
a) Calculating :
From the first equation we get:
Substituting (2) in (4):
Substituting (3) in the latter, and simplifying, grouping and sorting, we get a linear non homogeneous recurrence relation with constant coefficients and with a constant function as the function on the RHS (right-hand side) of the equation:
a.1) General solution of the homogeneous:
The characteristic polynomial is:
that is:
thus, double characteristic root.
The general solution of the homogeneous is:
a.2) Particular solution of the non homogeneous:
As the function on the RHS is constant, let us try out a general constant (real number) as a possible particular solution:
then . Thus:
is a particular solution of the non homogeneous.
a.3) General solution of the non homogeneous:
b) Calculating :
Substituting (5) in (1), and simplifying, grouping and sorting, we get:
c) Considering the initial conditions:
From the initial conditions, and we have:
On the other side:
and now, substituting (6) in (7):
d) The solution to the situation under the wording of the question (evolution of these two types of malware on their own growths) is:
where and are the populations of both types of malware by the end of the first hour (data not provided in the wording).
Question G1. (2.5 points)
The accompanying graph shows the connections among four tram stations. You may:
a) Write the adjacency matrix of that graph.
b) Interpret the matrices and (reason what situations they represent).
c) Reason, using those matrix representations, if it is a strongly connected graph or not.
d) Reason, using those matrix representations, what is the length of the shortest path from to and how many paths may be considered as the "shortest" ones.
We draw up the adjacency matrix of the graph, by matching the positional subscripts , , and of its elements with the labels , , and , so that, for example, corresponds to a possible path from to , . Thus, the element of is the number of direct connections --- with no intermediate station (paths of length one in the graph) --- between the tram stations corresponding to and , in the direction . In this way, we interpret as the existence of one direct connection from to , , this is, , whilst corresponds to the non existence of a direct connection from to , , this is, .
b) The powers and of are:
The element of is the number of connections with exactly one station in the middle (length two paths in the graph) from the corresponding station to to the corresponding station to , under the previous formalization. Similarly, the element of represents the number of connections with two intermediate stations (three length paths in the graph) from the corresponding station to to the corresponding station to , again according to the previous formalization.
c) A graph is strongly-connected precisely if there exists a path from any vertex to any vertex. On the other side, given a graph , with vertices, it is possible to know if there exists a path from the vertex to the vertex , regardless of the length but depending on the element of the matrix as it is the total number of paths from to (if there were such that then no path would be possible from to and the graph would not be strongly connected). The graph under our study, , with vertices, is strongly connected because has not zero elements:
which mean that any two stations are connected each other, either directly or indirectly via one or two intermediate stops. Indeed, for this particular graph, neither has zero elements:
that is to say, any two stations are connected each other via one or two intermediate stops.
d) Denoting by the element at position of the matrix , we note that and that , this being the first non-zero digit, so the shortest path has two intermediate stops and there is only one shortest path (since the value of is one).
Because of custom and maybe tradition we begin considering , and so we start dealing this question with and then adjust to match what was required. Let be . Then, the table of divided differences is:
where:
The interpolating polynomial is:
as well as in recurrence form:
Thus:
, that is satisfied by , but no longer by since .
, that is satisfied by and , but no longer by since .
, which is satisfied by all of the points, even by since .
The next difference is zero, which confirms that the interpolating polynomial, suggested by this method, is a second degree polynomial:
In summary, starting with , the general term is , and adjusting to match the beginning as required, the general term is:
My intention is to having two practice tests for training the final exam, the mid-course and end-course preparatory exams (another two assessment tools). Based on what we have worked with so far, both preparatory exams will replicate the final exam in level, content and format. These exams will be performed as homework and should be expected to be closed-book exams and to last two hours (the same as the final exam). This 'controlled self-assessment' mechanism intend to stimulate the personal work of the student, detect mistakes and weakness and make aware of possible comprehension gaps, and correct them. Two large-group classes are dedicated to share ideas and solutions in a whole-class discussion, one for each exam. These exams are for training and self-study use. They are not graded by the teacher and they are not included in the calculation of the final grade. As the final exam is individual-based, I recommend that you do them individually rather than in groups, anyway the choice is yours.
Past qualifying activities and real exams with some solutionsedit
Most of them are bilingual documents with side by side texts in a double column format, the left column being the Spanish text and the right column being the corresponding English text. (Why? Please read for instance what Maria Martinello says).
Tentative course outline (chronogram for the 2019-2020 academic year)edit
Important: Let us remember that exercises from Rosen's books and many others are available under the all rights reserved regime. However, their study and work on are an endless source of ideas for making contributions to Wikipedia.
This tentative course outline, which corresponds to the approved course program (ficha12a) is orientative and dynamic
(the planned development of the course may vary according to the particularities of the students involved).
Class (large group) meetings (48 h) and seminar/laboratory meetings (12 h)
Dates
Topics
Basic texts readings and study
Following is a selection of training exercises,essentially instrumental. Do not forget those that are worked in class and seminar/lab meetings. The concreteness of the examples implies in no case a course content cut. It is strongly recommended to solve exercises and other questions, the more the better. There is a more than enough bibliography to which to consult.
Rosen 5th ed. Spain/USA
Rosen 7th ed. USA
Others
Rosen 5th ed. Spain/USA
Rosen 7th ed. USA
Others
Theme 1
Fundamentals
(16 h LG and 5 h S/L)
Wed 29/1 Start date of classes
Symbolic logic, I: Propositional logic
Propositional logic;
The method of truth tables as a verification strategy.
University project Discrete and numerical mathematics (optional out-of-class activity): Beginning date of the academic component of the project in the 2nd semester of the academic year 2018-2019. You should read its descriptive web page, Wikipedia:School and university projects/Discrete and numerical mathematics. Once you have read that web page, and if you are interested in the project and only if you have queries or need help to do what you have been told (on that web page) to do or want to help your colleagues to do it or want to share questions, concerns or suggestions about the project, you could attend at 4:00 p.m., to Room O5 (meeting will finish at no later than 5:30 p.m.). (Bring a computer if you need help). (This meeting will be in Spanish).
Group B
Fri
31/1
Groups A and E
Mon
3/2
Seminar/Laboratory No. 1: Proofs and refutations, I
Exam review: large-group class dedicated to share ideas and solutions in a whole-class discussion about the mid-course preparatory exam (done as homework).
Theme 3
Combinatorics
(8 h LG and 3 h S/L)
Group B
Fri
27/3
Groups A and E
Mon
30/3
Seminar/Laboratory No. 9: Combinatorics, I
(Occasionally computer-assisted) hands-on word-problem-solving on issues related to:
University project Discrete and numerical mathematics (optional out-of-class activity): (Second checkpoint). You should have continually been working in your contributions, publishing each update, along with the corresponding themes to which they belong are worked in class, and linking each new major contribution on the contributions page of the project. Furthermore, you must publish, also on an ongoing basis, in your logbook (sandbox), the part of your self-report that deals with what you have developed so far.
University project Discrete and numerical mathematics (optional out-of-class activity): (Third and last checkpoint). You should have continually been working in your contributions, publishing each update, along with the corresponding themes to which they belong are worked in class, and linking each new major contribution on the contributions page of the project. Furthermore, you must publish, also on an ongoing basis, in your logbook (sandbox), the part of your self-report that deals with what you have developed so far (in this case all you have done). Starting from now until the ending date, you can review all what you have done and you can correct minor errors and complete other small details.
Exam review: large-group class dedicated to share ideas and solutions in a whole-class discussion about the end-course preparatory exam (done as homework).
Feel free to correct any typographical error you have detected in any of the project or plan pages (this is Wikipedia!).
Also all the feedback for doing better the next time, that is, all the comments, impressions, opinions, sensations and advices, wishes, suggestions or proposals concerning how we might improve this initiative will be most welcomed and greatly appreciated. The talk page of the learning plan is an ideal place to write them on. Please do not hesitate to do so. It means a lot to us.
Juan Miguel León Rojas declares under his own responsibility that the learning plan specified here meets all the essential requirements of the academic program (ficha12a) corresponding to the course Further Mathematics taught at the School of Technology, University of Extremadura.
Please contribute to the protection of the environment: print this document only if you consider it absolutely necessary.
Transverse information 1.- Some points about Free/Libre & Open Knowledge (FLOK)
'True poems of cante jondo are attributable to no one at all but float on the wind like golden thistledown and each generation clothes them in its own distinctive color, in releasing them to the future.'
.svg)
![{\displaystyle {\begin{array}{ll}\mathbf {Step} &\mathbf {Reason} \\1.\;\forall x(\neg Dx\rightarrow \neg Ax)&{\text{Premise}}\\2.\;\forall x(\neg Cx\rightarrow \neg Hx)&{\text{Premise}}\\3.\;\forall x(Ex\rightarrow Ax)&{\text{Premise}}\\4.\;\forall x(Dx\rightarrow \neg Bx)&{\text{Premise}}\\5.\;\forall x(\neg Ex\rightarrow \neg Cx)&{\text{Premise}}\\6.\;\neg Da\rightarrow \neg Aa&{\text{UI 1 }}{\text{(universal instantiation)}}\\7.\;\neg Ca\rightarrow \neg Ha&{\text{UI 2 }}{\text{(universal instantiation)}}\\8.\;Ea\rightarrow Aa&{\text{UI 3 }}{\text{(universal instantiation)}}\\9.\;Da\rightarrow \neg Ba&{\text{UI 4 }}{\text{(universal instantiation)}}\\10.\;\neg Ea\rightarrow \neg Ca&{\text{UI 5 }}{\text{(universal instantiation)}}\\11.\;\neg Aa\rightarrow \neg Ea&\mathrm {Cp_{1}{\text{ 8 }}} {\text{(contraposition [also called transposition] law)}}\\12.\;Ba\rightarrow \neg Da&\mathrm {Cp_{2}{\text{ 9 }}} {\text{(contraposition [also called transposition] law)}}\\13.\;(Ba\rightarrow \neg Da)\wedge (\neg Da\rightarrow \neg Aa)&{\text{CI 12, 6 }}{\text{(conjunction introduction)}}\\14.\;(Ba\rightarrow \neg Aa)&{\text{Syl 13 }}{\text{(hypothetical syllogism)}}\\15.\;(Ba\rightarrow \neg Aa)\wedge (\neg Aa\rightarrow \neg Ea)&{\text{CI 14, 11 }}{\text{(conjunction introduction)}}\\16.\;(Ba\rightarrow \neg Ea)&{\text{Syl 15 }}{\text{(hypothetical syllogism)}}\\17.\;(Ba\rightarrow \neg Ea)\wedge (\neg Ea\rightarrow \neg Ca)&{\text{CI 16, 10 }}{\text{(conjunction introduction)}}\\18.\;(Ba\rightarrow \neg Ca)&{\text{Syl 17 }}{\text{(hypothetical syllogism)}}\\19.\;(Ba\rightarrow \neg Ca)\wedge (\neg Ca\rightarrow \neg Ha)&{\text{CI 18, 7 }}{\text{(conjunction introduction)}}\\20.\;(Ba\rightarrow \neg Ha)&{\text{Syl 19 }}{\text{(hypothetical syllogism)}}\\21\;\forall x(Bx\rightarrow \neg Hx)&{\text{UG 20 }}{\text{(universal generalisation)}}\end{array}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/08af13a6564e69425520837e8c7a152f97ee6686)
![{\displaystyle \left[0,18\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/335c3d0a8963f52b74e77a8c9b614451b0b29a91)
![{\displaystyle \left[-9,9\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b616c8a1915d0d9849ebc177ee020437bcf51b6)
