Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2018/2019

Logika a grafy

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
B0B01LGR Z,ZK 5 3+2 česky
Přednášející:
Matěj Dostál, Alena Gollová
Cvičící:
Matěj Dostál, Alena Gollová, Anna Kalousová
Předmět zajišťuje:
katedra matematiky
Anotace:

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ů.

Požadavky:

Nejsou.

Osnova přednášek:

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.

Osnova cvičení:

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.

Cíle studia:

Cílem předmětu je seznámit studenty se základy matematické logiky a základy teorie grafů.

Studijní materiály:

[1] D. van Dalen: Logic and Structure. Springer, Berlin, Heidelberg, 2004.

[2] J. A. Bondy, U. S. R. Murty: Graph theory with applications. Elsevier Science Ltd/North-Holland, 1976.

V češtině:

[3] M. Demlová, B. Pondělíček: Matematická logika. ČVUT Praha, 1997.

[4] Matoušek, J., Nešetřil, J.: Kapitoly z diskrétní matematiky, Nakladatelství Karolinum, 2000.

[5] Demel, J.: Grafy a jejich aplikace, Academia 2002, druhé vydání 2015.

Poznámka:
Další informace:
http://math.feld.cvut.cz/dostamat/teaching/lgr1819.htm http://math.feld.cvut.cz/gollova/lgr.html
Rozvrh na zimní semestr 2018/2019:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
místnost T2:A4-202b
Kalousová A.
09:15–10:45
(přednášková par. 1
paralelka 101)

Dejvice
Učebna
místnost T2:A4-202b
Kalousová A.
11:00–12:30
(přednášková par. 1
paralelka 102)

Dejvice
Učebna
místnost T2:C4-363
Kalousová A.
12:45–14:15
(přednášková par. 1
paralelka 107)

Dejvice
Cvicebna
St
místnost T2:A4-202b
Gollová A.
09:15–10:45
(přednášková par. 1
paralelka 106)

Dejvice
Učebna
místnost T2:A4-202b
Kalousová A.
11:00–12:30
(přednášková par. 1
paralelka 104)

Dejvice
Učebna
Čt
místnost T2:C4-78
Gollová A.
09:15–10:45
(přednášková par. 1
paralelka 103)

Dejvice
Posluchárna
místnost T2:C4-78
Gollová A.
11:00–12:30
(přednášková par. 1
paralelka 105)

Dejvice
Posluchárna
místnost KN:E-128

16:15–17:45
(přednášková par. 1
paralelka 108)

Karlovo nám.
Cvičebna K3
místnost KN:E-107
Gollová A.
14:30–16:00
(přednášková par. 1)
Karlovo nám.
Zengerova posluchárna K1

místnost T2:D3-309
Gollová A.
11:00–12:30
LICHÝ TÝDEN

(přednášková par. 1)
Dejvice
Posluchárna
Rozvrh na letní semestr 2018/2019:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
místnost T2:D3-209
Dostál M.
11:00–12:30
(přednášková par. 1)
Dejvice
Posluchárna
místnost T2:C3-51
Dostál M.
14:30–16:00
(přednášková par. 1
paralelka 101)

Dejvice
Posluchárna
místnost T2:C3-51
Dostál M.
12:45–14:15
(přednášková par. 1
paralelka 102)

Dejvice
Posluchárna
Út
místnost T2:D3-209
Dostál M.
12:45–14:15
SUDÝ TÝDEN

(přednášková par. 1)
Dejvice
Posluchárna
St
místnost T2:A4-202b
Kalousová A.
14:30–16:00
(přednášková par. 1
paralelka 103)

Dejvice
Učebna
místnost T2:A4-202b
Kalousová A.
16:15–17:45
(přednášková par. 1
paralelka 104)

Dejvice
Učebna
místnost T2:A4-202b

18:00–19:30
(přednášková par. 1
paralelka 105)

Dejvice
Učebna
Čt
místnost T2:A4-202a
Dostál M.
12:45–14:15
(přednášková par. 1
paralelka 106)

Dejvice
Ucebna
místnost T2:A4-202a
Dostál M.
14:30–16:00
(přednášková par. 1
paralelka 107)

Dejvice
Ucebna
místnost T2:A4-202a
Dostál M.
16:15–17:45
(přednášková par. 1
paralelka 108)

Dejvice
Ucebna

místnost T2:A4-202a

11:00–12:30
(přednášková par. 1
paralelka 110)

Dejvice
Ucebna
místnost T2:A4-202a

12:45–14:15
(přednášková par. 1
paralelka 109)

Dejvice
Ucebna
Předmět je součástí následujících studijních plánů:
Platnost dat k 17. 7. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet4680706.html