This course is no longer offered
20276 Discrete Mathematics 1
Credits: 6 intermediate credits in Mathematics
Prerequisites: none
Recommended: Linear Algebra or Introduction to Mathematics
The aim of the course is to acquaint students with concepts, outcomes and methods relating to mathematical topics which constitute important tools for dealing with the theoretical foundations of computer science and to contribute to the development of students’ mathematical sophistication.
Topics: Volume I - Set Theory: Sets, member, equality of sets, set operations (union, intersection, difference, complement); Power set, Cartesian products, relations, multiplication of relations, inverse relation; Reflexive, symmetric, anti-symmetric, transitive relations; Equivalence relations and partitions; the quotient set; Functions: one-to-one, onto; Partial order; induction; Infinite sets and cardinality; countable sets; The cardinality of the set of real numbers; The Cantor-Bernstein theorem; Cantor's theorem. Volume II - Combinatorics: The principles of addition and multiplication; Permutations, combinations, variations, with and without repetitions; Newton's binomial formula; identities involving binomial coefficients; Recursion relations; solution of linear recursion relations; The principle of inclusion and exclusion; Applications of inclusion-exclusion: Euler's function; number of derangements of a set; The pigeonhole principle; Generating functions. Volume III – Logic: A. Propositional calculus: Logical connectives: Syntax; Truth tables, tautologies and contradictions; Complete sets of connectives; normal forms; B. Introduction to predicate calculus: Quantifiers, predicates, formulae; syntax; Interpretations and assignments; Truth in an interpretation; Logically true formulae. Volume IV - Algebraic structures: Binary operations, groupoids; Homomorphism, isomorphism; Congruence and the quotient groupoid; Semigroups; identity elements; monoids; Inverse elements; Groups, Zn, normal subgroups.
1This course is being replaced. There is some overlap in the content of this and other courses. For details, see Overlapping Courses.