# Subject description - B0B01LGR

Summary of Study | Summary of Branches | All Subject Groups | All Subjects | List of Roles | Explanatory Notes               Instructions
 B0B01LGR Logic anad Graphs Extent of teaching: 3+2 Guarantors: Demlová M. Roles: PV,P Language ofteaching: CS Teachers: Dostál M. Completion: Z,ZK Responsible Department: 13101 Credits: 5 Semester: Z,L

Anotation:

This course covers basics of mathematical logic and graph theory. Syntax and sematics of propositional and predicate logic is introduced. Stress is put on understanding of the notion of semantic consequent of sets of formulas. The relationship between a formula and its model and rezolution methods (both in propositional and predicate logic) are dealt with. Further, basic notions from graph theory are introduced.

Study targets:

The aim of the course is to introduce students with basis of mathematical logic and graph theory.

Content:

 1 Syntax and semantics of propositional logic, formulas, truth valuation, a tautology, a contradiction, a satisfiable formula. 2 Tautological equivalence of two formulas. CNF a ndDNF, Boolean calculus. 3 Semantic consequence. The rezolution method in propositionl logic. 4 Syntax of predicate logic, a sentence, an open formula. 5 Interpretation of predicate logic, tautological equivalence of sentences and semantic consequence. 6 The rezolution method in predicate logic. 7 Applications of rezolution method. Natural deduction as an example of a sound and complete deduction system.Theorem of completness. 8 Undirected and directed graphs, basic notions. Connectivity, trees, spanning trees. 9 Rooted trees, strong connectivity ,acyclic graphs, topological sort of vertices and edges. 10 Euler graphs and their applications. 11 Hamiltonian graphs and their applications. 12 Independent sets, cliques, vertex and edge cover, Graph coloring. 13 Plannar graphs.

Course outlines:

 1 Syntax and semantics of propositional logic, formulas, truth valuation, a tautology, a contradiction, a satisfiable formula. 2 Tautological equivalence of two formulas. CNF a ndDNF, Boolean calculus. 3 Semantic consequence. The rezolution method in propositionl logic. 4 Syntax of predicate logic, a sentence, an open formula. 5 Interpretation of predicate logic, tautological equivalence of sentences and semantic consequence. 6 The rezolution method in predicate logic. 7 Applications of rezolution method. Natural deduction as an example of a sound and complete deduction system.Theorem of completness. 8 Undirected and directed graphs, basic notions. Connectivity, trees, spanning trees. 9 Rooted trees, strong connectivity ,acyclic graphs, topological sort of vertices and edges. 10 Euler graphs and their applications. 11 Hamiltonian graphs and their applications. 12 Independent sets, cliques, vertex and edge cover, Graph coloring. 13 Plannar graphs.

Exercises outline:

 1 Syntax and semantics of propositional logic, formulas, truth valuation, a tautology, a contradiction, a satisfiable formula. 2 Tautological equivalence of two formulas. CNF a ndDNF, Boolean calculus. 3 Semantic consequence. The rezolution method in propositionl logic. 4 Syntax of predicate logic, a sentence, an open formula. 5 Interpretation of predicate logic, tautological equivalence of sentences and semantic consequence. 6 The rezolution method in predicate logic. 7 Applications of rezolution method. Natural deduction as an example of a sound and complete deduction system.Theorem of completness. 8 Undirected and directed graphs, basic notions. Connectivity, trees, spanning trees. 9 Rooted trees, strong connectivity ,acyclic graphs, topological sort of vertices and edges. 10 Euler graphs and their applications. 11 Hamiltonian graphs and their applications. 12 Independent sets, cliques, vertex and edge cover, Graph coloring. 13 Plannar graphs.

Literature:

 [4] Hodel, R. E.: An Introduction to Mathematical Logic, 2013, ISBN-13 978-0-486-49785-3 [5] Diestel, R.: Graph Theory, Springer-Verlag, 4th edition, 2010, ISBN 978-3-642-14278-9

Requirements:

None.

Webpage:

http://math.feld.cvut.cz/dostamat/teaching/lgr1819.htm http://math.feld.cvut.cz/gollova/lgr.html

Keywords:

Propositional logic, predicat logic, semantic consequence, rezolution method, undirected and directed graphs, connectivity, trees and spanning trees, Euler trails, Hamiltonian paths, coloring.

Subject is included into these academic programs:

 Program Branch Role Recommended semester BPOI_BO_2018 Common courses P 2 BPOI4_2018 Computer Games and Graphics P 2 BPOI3_2018 Software P 2 BPOI2_2018 Internet things P 2 BPOI1_2018 Artificial Intelligence and Computer Science P 2 BPOI1_2016 Computer and Information Science P 2 BPOI_BO_2016 Common courses P 2 BPOI4_2016 Computer Games and Graphics P 2 BPOI3_2016 Software P 2 BPOI2_2016 Internet things P 2 BPBIO_2018 Common courses PV 5 BPKYR_2016 Common courses P 1

 Page updated 24.5.2019 17:53:31, semester: Z,L/2020-1, L/2019-20, Z,L/2018-9, Z/2019-20, Send comments about the content to the Administrators of the Academic Programs Proposal and Realization: I. Halaška (K336), J. Novák (K336)