Title:

# Discrete Mathematics

Code:IDA
Ac.Year:2004/2005
Sem:Winter
Curriculums:
ProgrammeFieldYearDuty
IT-BC-3BIT1stCompulsory
Language of Instruction:Czech, English
Credits:7
Completion:examination (written)
Type of
instruction:
Hour/semLecturesSeminar
Exercises
Laboratory
Exercises
Computer
Exercises
Other
Hours:39100412
ExamsTestsExercisesLaboratoriesOther
Points:60010030
Guarantor:Krupková Vlasta, RNDr., CSc. (DMAT)
Lecturer:Havel Václav, prof. RNDr., DrSc. (DMAT)
Krupková Vlasta, RNDr., CSc. (DMAT)
Švarc Svatopluk, RNDr., CSc. (DMAT)
Faculty:Faculty of Electrical Engineering and Communication BUT
Department:Department of Mathematics FEEC BUT
Follow-ups:
 Algorithms (IAL), DIFS Computer Graphics Principles (IZG), DCGM Formal Languages and Compilers (IFJ), DIFS Mathematical Analysis (IMA), DMAT Modelling and Simulation (IMS), DITS Numerical Methods and Probability (INM), DMAT

Learning objectives:
The modern conception of the subject yields a fundamental mathematical knowledge which is necessary for a number of related courses. The student will be acquainted with basic facts and knowledge from the set theory, topology and especially the discrete mathematics with focus on the mathematical structures applicable in computer science.
Description:
The sets, relations and mappings. The topology and the continuous mapping. The structures with one and two operations. Equivalences and partitions. Posets. Lattices and Boolean algebras.The proposional calculus. The normal forms of formulas. Deduction. The proving techniques. The elementary notions of the graph theory. Connectedness. Subgraphs and morphisms of graphs. Planarity. Trees and their properties. Simple graph algorithms.
Learning outcomes and competencies:
The student will obtain the basic orientation in mathematics as well as the foundations of the discrete mathematics, logic and related mathematical structures (elementary topology, binary relations, posets, lattices, groups, graphs etc.).
Syllabus of lectures:

• A set intuitively. Basic set operations. The power set. The set of numbers. Binary relations. A mapping as a binary relation. Domain and co-domain. Functions and sequences. The composition of relations.
• Injective, surjective and bijective mappings. The inverse mapping. The image and the inverse image. Important collections of sets with applications. Topological definition of continuity.
• Operations on a set. Classification of the structures with one and two operations. The group of permutations of a finite set. Cominatorial properties of finite sets. The Principle of inclusion and exclusion.
• Reflective, symetric, antisymetric and transitive binary relations. Reflective, symetric and transitive closure. Equivalences and partitions with examples.
• The partially ordered sets. Lattices and their basic properties. Khalimsky's digital line and its order of specialization. The natural order of the real numbers. The Hasse diagrams. The lattice as a set with two binary operations. The Boolean algebra.
• The basic properties of Boolean algebras. The duality and the set representation of a finite Boolean algebra.
• Predicates, formulas, quantifiers and basic logical connectives. The proposional calculus and its syntaxis. The classification of formulas. Some subclasses of the proposional calculus.
• The nterpretation of formulas. Tautologies,non-performable formulas and the logic equivalence of formulas. The structure of the algebra of non-equivalent formulas.
• Prenex normal forms of formulas. The truthfulness and determinism.
• Deduction systems. The system of the natural deduction and its rules. The proof in the system of natural deduction. The techniques of proofs.
• The elementary notions of the graph theory. The Shortest path algorithm. The connectivity of graphs. The subgraphs.
• The isomorphism and the homeomorphism of graphs. The Planarity problém.
• The trees and the spanning trees and their properties. The searching of the binary tree. Selected searching algorithms.
Syllabus of numerical exercises:
Practice on selected parts of lectures matter.
Syllabus of computer exercises:
Two two-hour practice supporting lectures 8, 9, and 10.
Syllabus - others, projects and individual work of students:
Practice leading instructor will specify problems.
Fundamental literature:

• Faure, R., Heurgon, E., Stuctures ordonnées et algebres de Boole, Gauthier-Villars, Paris, 1971.
• Gantmacher, F.R., The Theory of Matrices, Chelsea Publ. Comp., New York, 1960.
• Havel, V., Holenda, J., Lineární algebra, STNL, Praha, 1984.
• Hellerstein, N.S., Diamond, A., Paradox Logic, World Scientific, Singapore, 1996.
• Johnsonbaugh, R., Discrete mathematics, Macmillan Publ. Comp., New York, 1984.
• Jablonskij, S.V., Úvod do diskrétnej matematiky, Alfa, Bratislava, 1984.
• Kolář, J., Štěpánková, O., Chytil, M., Logika, algebry a grafy, STNL, Praha, 1989.
• Kolibiar, M., kol., Algebra a príbuzné disciplíny, Alfa, Bratislava, 1992.
• Kolman, B., Elementary Linear Algebra, Macmillan Publ. Comp., New York 1986.
• Kolman, B., Introductory Linear Algebra, Macmillan Publ. Comp., New York 1991.
• Kučera,  L., Kombinatorické algoritmy, SNTL, Praha 1983.
• Lipschutz, S., 3000 Solved Problems in Linear Algebra, McGraw-Hill, New York, 1989.
• Lipschutz, S., Lipson, M.L., 2000 Solved Problems in Discrete Mathematics, McGraw-Hill, New York, 1992.
• Manna, Z., Matematická teorie programů, SNTL, Praha 1981.
• Novák, V., Fuzzy množiny a jejich aplikace, SNTL, Praha 1986.
• Preparata, F.P., Yeh, R.T., Úvod do teórie diskrétnych štruktúr, Alfa, Bratislava, 1982.
• Rosen K. H., Discrete Mathematics and its Applications, AT & T Information systems, New York 1988.
• Sochor, A., Klasická matematická logika, Karolinum, Praha 2001.
• Štěpán, J., Diskrétní matematika, UP, Olomouc, 1990 (skriptum).
• Vickers, S., Topology Via Logic, Cambridge University Press, Cambridge, 1989.
Study literature:

• Demlová, M., Nagy, J., Algebra, STNL, Praha 1982.
• Havel, V., Holenda, J., Lineární algebra, STNL, Praha, 1984.
• Hrůza, B., Mrhačová, H., Cvičení z lineární algebry, PC-Dir, Brno, 1984.
• Johnsonbaugh, R., Discrete mathematics, Macmillan Publ. Comp., New York, 1984.
• Kolář, J., Štěpánková, O., Chytil, M., Logika, algebry a grafy, STNL, Praha, 1989.
• Kolibiar, M., kol., Algebra a príbuzné disciplíny, Alfa, Bratislava, 1992.
• Kolman, B., Elementary Linear Algebra, Macmillan Publ. Comp., New York, 1986.
• Kolman, B., Introductory Linear Algebra, Macmillan Publ. Comp., New York, 1991.
• Lipschutz, S., 3000 Solved Problems in Linear Algebra, McGraw-Hill, New York, 1989.
• Lipschutz, S., Lipson, M.L., 2000 Solved Problems in Discrete Mathematics, McGraw-Hill, New York, 1992.
• Preparata, F.P., Yeh, R.T., Úvod do teórie diskrétnych štruktúr, Alfa, Bratislava, 1982.
• Rosen, K.H., Discrete Mathematics and its Applications, AT & T Information systems, New York 1988.
• Štěpán, J., Diskrétní matematika, UP, Olomouc, 1990 (skriptum).
• Fields, J.E., Introduction to Graph Theory, Southern Connecticut State University, 2001.
• Connel, E.H., Elements of Abstract and Linear Algebra, University of Miami, 2004.
• MacGillivray, G., UVic Discrete Mathematics Study Guide, University of Victoria, Ca.
• Peressini, D., DMP: Definitions, University of Colorado and Boulder, 1997.
• Diestel, R., Graph Theory, Springer-Verlag, New York, 2000.
Controlled instruction:
Pass out the computer practices and the the elaboration of homeworks/projects in the determined range.
Progress assessment:
An active work on computer practice and the active work on homeworks/projects.