SUBJECT
Discrete mathematics 1
lecture + practical
bachelor
4+3
Semester 1
Autumn semester
-
Logical operations, quantifiers, formulas. Sets, set operations, subsets. Binary relations,equivalence relation, equivalence classes, partial ordering. Functions, Cartesian product of sets, general relations, connection to relational data bases. Binary operations, operations in general, logical operations.
-
Peano-axioms, natural numbers, induction, recursion. Operations with natural numbers, ordering of natural numbers. Semigroup, unit element, group, Abelian group.
-
Numbers: integers, rational numbers, real and complex numbers, quaternions. Ring, integral domain, skew field, field.
-
Finite sets. Combinations, permutation. Polynomial theorem, sieve formulae.
-
Divisor, prime and irreducible numbers. Divisibility in rings. Euclidean algorithm. Basic theorem of number theory. Congruencies, Diophantine equations and their solution in linear case. Chinese remainder theorem. Diffie-Hellmann key exchange, RSA system. Number theoretical functions.
-
Infinite sets: Cantor-Bernstein theorem, Cantor’s theorem. Countable sets and their characterizations. Sets with cardinality of continuum.
-
R. Graham, D. E. Knuth, O. Patashnik: Concrete Mathematics
-
D. E. Knuth: The Art of Computer Programming
-
N. L. Biggs: Discrete Mathematics
-
Járai Antal: Bevezetés a matematikába (Eötvös Kiadó, Budapest, 2007)
Recommended literature:
-
Láng Csabáné: Bevezetés a matematikába
-
Dringó- Kátai: Bevezetés a matematikába
-
Szendrei Ágnes: Diszkrét matematika