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 of
teaching:
CS
Teachers:Dostál M. Completion:Z,ZK
Responsible Department:13101 Credits:5 Semester:Z,L

Anotation:

Tento předmět se zabývá základy matematické logiky a teorie grafů. Je zavedena syntaxe a sémantika výrokové logiky a predikátové logiky prvního řádu. Důraz je kladen na pochopení pojmu sémantického důsledku, na vztah mezi formulí a jejím modelem, a na resoluční metodu. Dále jsou zavedeny některé základní pojmy teorie grafů a popsány algoritmy na řešení některých základních úloh z teorie grafů.

Course outlines:

1. Formule výrokové logiky, pravdivostní ohodnocení, tautologie, kontradikce, splnitelné formule.
2. Tautologická ekvivalence formulí. CNF a DNF, Karnaughovy mapy, Booleovský kalkul.
3. Sémantický důsledek, Rezoluční metoda ve výrokové logice.
4. Predikátová logika, syntakticky správné formule, sentence.
5. Interpretace predikátové logiky, tautologická ekvivalence sentencí a sémantický důsledek.
6. Rezoluční metoda v predikátové logice.
7. Aplikace rezoluční metody. Přirozená dedukce jako příklad úplného a bezesporného odvozovacího systému. Věta o úplnosti.
8. Grafy neorientované a orientované, základní pojmy. Souvislost, stromy, kostry.
9. Kořenové stromy, silná souvislost, acyklické grafy, topologické očíslování vrcholů a hran.
10. Eulerovy grafy a jejich aplikace.
11. Hamiltonovy grafy a jejich aplikace.
12. Nezávislé množiny, kliky v grafu. Vrcholové a hranové barvení grafů.
13. Rovinné grafy.

Exercises outline:

1. Formule výrokové logiky, pravdivostní ohodnocení, tautologie, kontradikce, splnitelné formule.
2. Tautologická ekvivalence formulí. CNF a DNF, Karnaughovy mapy, Booleovský kalkul.
3. Sémantický důsledek, Rezoluční metoda ve výrokové logice.
4. Predikátová logika, syntakticky správné formule, sentence.
5. Interpretace predikátové logiky, tautologická ekvivalence sentencí a sémantický důsledek.
6. Rezoluční metoda v predikátové logice.
7. Aplikace rezoluční metody. Přirozená dedukce jako příklad úplného a bezesporného odvozovacího systému. Věta o úplnosti.
8. Grafy neorientované a orientované, základní pojmy. Souvislost, stromy, kostry.
9. Kořenové stromy, silná souvislost, acyklické grafy, topologické očíslování vrcholů a hran.
10. Eulerovy grafy a jejich aplikace.
11. Hamiltonovy grafy a jejich aplikace.
12. Nezávislé množiny, kliky v grafu. Vrcholové a hranové barvení grafů.
13. Rovinné grafy.

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:

Webpage:

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

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 22.3.2019 17:49:48, 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)