## Discrete Mathematics and Graphs, academic year 2017/18

### Content:

#### Lectures:

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

#### Tutorials:

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

### References:

- DLindsay N. Childs: A Concrete Introduction to Higher Algebra, Springer; 3rd edition (November 26, 2008), ISBN-10: 0387745270
- Richard Johnsonbaugh: Discrete Mathematics, Prentice Hall, 4th edition (1997), ISBN 0-13-518242-5

### 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 28th. 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.

#### Grading:

The resulting grade is based on three inputs. S is the number of points brought from midterm calculated as follows: if the gain M from midterm taken for the first time is at least 10, then S = M - 10 (from re-taken midterm the points are not calculated); P is the number of points from the written part; and U is the number of points from the oral part.

1) If a student gained less than 40 points from the written test, the student failed the exam.

2) If a student gained 40 or more points from the written test, then the student can take an oral exam. The grade is then determined by the total P + S + U and the following key:

Sum | Grade |

50-59 | E (sufficient) |

60-69 | D (satisfactory) |

70-79 | C (good) |

80-89 | B (very good) |

>89 | A (excellent) |