## Discrete Mathematics and Graphs, academic year 2018/19

### Content:

#### Lectures:

1. Foundation of Propositional logic, Boolean calculus.
2. Foundation of Predicate logic, quantifiers, interpretation.
3. Sets, cardinality of sets, countable and uncountable sets.
4. Binary relations on a set, equivalence relation, partial order.
5. Integers, Euclid (extended) algorithms.
6. Relation modulo n, congruence classes Zn and operations on Zn.
7. Algebraic operations, semigroups, groups.
8. Sets together with two binary operations, Boolean algebras.
9. Rings of congruence classes Zn, fields Zp.
10. Undirected graphs, trees and spanning trees.
11. Directed graphs, strong connectivity and acyclic graphs.
12. Euler graphs and Hamiltonian graphs, coloring.
13. Combinatorics.

#### Tutorials:

1. Foundation of Propositional logic, Boolean calculus.
2. Foundation of Predicate logic, quantifiers, interpretation.
3. Sets, cardinality of sets, countable and uncountable sets.
4. Binary relations on a set, equivalence relation, partial order.
5. Integers, Euclid (extended) algorithms.
6. Relation modulo n, congruence classes Zn and operations on Zn.
7. Algebraic operations, semigroups, groups.
8. Sets together with two binary operations, Boolean algebras.
9. Rings of congruence classes Zn, fields Zp.
10. Undirected graphs, trees and spanning trees.
11. Directed graphs, strong connectivity and acyclic graphs.
12. Euler graphs and Hamiltonian graphs, coloring.
13. Combinatorics.

### References:

• D. Lindsay N. Childs: A Concrete Introduction to Higher Algebra, Springer.
• R. Johnsonbaugh: Discrete Mathematics, Prentice Hall.

### Assesment (zapocet):

Requirements: Active participation in labs and scoring at least 8 points from midterm.

Midterm: Midterm will be written during the labs in 9th week of semester, i.e. November 27th. Midterm test consists of three parts: 1. logic - propositional and predicate logic (gain max. 6 points); 2. binary relations (gain max. 6 points); and 3. solving an equation in rezidue classes (gain max. 8 points). You can obtain max. 20 points, obligatory for assesment is 8 points.

### Final exam:

A necessary condition is to obtain assesment (zapocet).

Final exam contains two parts - a written part (obligatory) and an oral part (not obligatory). Written test will consist of 6 problems, max. gain 80 points, with 105 minutes allowed for solving them.

#### Written test:

Problem 1: Negation of a sentence of predicate logic.

Problem 2: Binary relations on a set; properties of a binary relation (reflexivity, symmetry, antisymmetry, transitivity, equivalence relation, partial order), or a composition of relations.

Problem 3: Binary operations: For a given binary operation o on a set A decide whether (A,o) is a semigroup, a monoid, or a group. Furhter questions can be put: An equality which does not have a solution, a subsemigroup (a submonoid, a subgroup).

Problem 4: Structures Zn and their subgroup of invertible elements. Order of some/all of its elements. Solving a parametric linear equation in Zn.

Problem 5: Graphs: It is necessary to understand basic notions, be able to give small examples with prescribed properties, and use some of the facts/procedures that were shown at the lecture.

Problem 6: Combinatorics: A word problem concerning enumerative combinatorics.

#### Oral part:

The oral part will look at theory and can bring max. 20 points; can be taken by those who gained at least 40 points in the written part.