This course is no longer offered
20283 Discrete Mathematics: Set Theory, Combinatorics and Logic 1
Credits: 4 intermediate credits in Mathematics
Prerequisites: none
Recommended: Introduction to Mathematics
Authors: Abraham Ginzburg, Shmuel Berger, Itai Hareven
This course presents mathematical concepts and methods that provide a background for the study of Computer Science and contributes to the development of students’ mathematical sophistication.
Topics: Set theory – Sets and their elements, subsets, operations on sets. The power set. Cartesian products. Relations. Multiplication and inversion of relations. Equivalence relations, partitions, quotient sets. Partial and linear orderings. Functions. Mathematical induction. Countable sets and the cardinality of the set of real numbers. Cantor-Schröder-Bernstein’s theorem, Cantor’s theorem. Cardinals: addition, multiplication and exponentiation. Combinatorics – The principles of addition and multiplication. Permutations, combinations and variations with and without repetitions. Newton's binomial formula and identities involving binomial coefficients. The inclusion-exclusion principle. Total disorders. Euler's function. The pigeonhole principle. Recursive relations and generating functions. Mathematical logic – Propositional calculus: syntax and semantics – propositions, connectives, truth tables, tautologies and contradictions, complete sets of connectives, normal forms, models, proof theory2 – deductive systems and formal proofs. Predicate calculus: syntax – quantifiers, terms, predicates, well formed formulas. Semantics – interpretations, truth in an interpretation and logical truth.
1There is some overlap in the content of this and other courses. For details, see Overlapping Courses. Beginning in Spring 2011, this course will be replaced with an updated version.
2Taught only briefly.