Popis předmětu - B0B01LGR

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
B0B01LGR Logika a grafy Rozsah výuky:3+2
Garanti:Demlová M. Role:PV,P Jazyk výuky:CS
Vyučující:Dostál M. Zakončení:Z,ZK
Zodpovědná katedra:13101 Kreditů:5 Semestr:Z,L

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

Cíle studia:

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

Obsah:

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.

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

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

Literatura:

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

Požadavky:

Nejsou.

Webová stránka:

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

Klíčová slova:

Výroková logika, predikátová logika, sémantický důsledek, rezoluční metoda, neorientované a orientovane grafy, souvislost, stromy, kostry, Eulerovy tahy, Hamiltonovy cesty, barvení grafu.

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr
BPOI_BO_2018 Před zařazením do oboru P 2
BPOI4_2018 Počítačové hry a grafika P 2
BPOI3_2018 Software P 2
BPOI2_2018 Internet věcí P 2
BPOI1_2018 Základy umělé inteligence a počítačových věd P 2
BPOI1_2016 Informatika a počítačové vědy P 2
BPOI_BO_2016 Před zařazením do oboru P 2
BPOI4_2016 Počítačové hry a grafika P 2
BPOI3_2016 Software P 2
BPOI2_2016 Internet věcí P 2
BPBIO_2018 Před zařazením do oboru PV 5
BPKYR_2016 Před zařazením do oboru P 1


Stránka vytvořena 18.7.2019 17:51:20, semestry: Z,L/2020-1, L/2018-9, Z,L/2019-20, připomínky k informační náplni zasílejte správci studijních plánů Návrh a realizace: I. Halaška (K336), J. Novák (K336)
Za obsah odpovídá: doc. Ing. Ivan Jelínek, CSc.