Přehled studia |
Přehled oborů |
Všechny skupiny předmětů |
Všechny předměty |
Seznam rolí |
Vysvětlivky
Návod
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. Dále jsou zavedeny některé základní pojmy teorie grafů a popsány algoritmy k ř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ů.
Studenti by měli rozlišovat syntax a sémantiku, umět pracovat se syntaktickým i sémantickým důsledkem, a dále by měli být schopni formalisovat ve vhodném jazyce jednoduché praktické úlohy.
Dále by studenti měli být schopni řešit teoretické i praktické grafové úlohy, a měli by být schopni popsat a použít základní grafové algoritmy.
Obsah:
Obsahem předmětu je matematická logika a teorie grafů.
Z matematické logiky probereme základy výrokové logiky a logiky prvního řádu (predikátové logiky). Studujeme formální syntax, jazyky logiky jsou přirovnány k programovacím jazykům. Je diskutován praktický problém odvození závěru z daných předpokladů. Zavedeme syntaktická odvozovací pravidla a budeme diskutovat jejich smysluplnost. Standardním způsobem zavedeme význam (sémantiku) výrokové logiky. Prostudujeme sémantický důsledek a jeho vztah k důsledku syntaktickému. V predikátové logice přednostně zavádíme sémantiku a studujeme pravdivost tvrzení predikátové logiky v dané interpretaci. Probereme resoluční metodu ve výrokové i predikátové logice.
V části týkající se teorie grafů předvedeme praktické problémy, které jsou popsatelné a řešitelné metodami teorie grafů. Zavedeme základní pojmy teorie grafů jako vyjadřovací prostředek k popisu teoretických i praktických úloh. Odvodíme teoretické vlastnosti daných pojmů jako prostředek k tvorbě grafových algoritmů.
Osnovy přednášek:
Témata ve výrokové logice (cca 4 týdny):
| 1. | | Formální jazyk. Jazyk výrokové logiky. |
| 2. | | Odvozování důsledků (přirozená dedukce). |
| 3. | | Význam a sémantický důsledek. |
Témata v predikátové logice (cca 4 týdny):
| 1. | | Jazyk predikátové logiky. |
| 2. | | Přirozená dedukce v predikátové logice. |
| 3. | | Význam a sémantický důsledek v predikátové logice. |
| 4. | | Reserva: pokročilá témata. |
Témata z teorie grafů: (cca 5 týdnů):
| 1. | | Základní pojmy teorie grafů. |
| 2. | | Kostry. |
| 3. | | Silná souvislost. |
| 4. | | Kreslení jedním tahem. |
| 5. | | Barvení. |
Osnovy cvičení:
Řešení teoretických i algoritmických úloh z logiky a teorie grafů.
Upevňování a rozšiřování znalostí a dovedností z přednášek.
Literatura:
| [1] | | M. Huth, M. Ryan: Logic in Computer Science: Modelling and Reasoning about Systems. Cambridge University Press, 2004. |
| [2] | | J. A. Bondy, U. S. R. Murty: Graph theory with applications. Elsevier Science Ltd/North-Holland, 1976. |
V češtině:
| [3] | | J. Velebil: Velmi jemný úvod do matematické logiky. Online 2007. |
| [4] | | M. Demlová, B. Pondělíček: Matematická logika. ČVUT Praha, 1997. |
| [5] | | J. Demel: Grafy a jejich aplikace. Academia 2002, druhé vydání 2015. |
| [6] | | P. Kovář: Teorie grafů. Online, 2019. |
Požadavky:
Nejsou.
Webová stránka:
https://cw.fel.cvut.cz/b212/courses/b0b01lgr/
Klíčová slova:
Výroková logika, predikátová logika, syntaktický a sémantický důsledek, základní pojmy teorie grafů, grafové algoritmy.
Předmět je zahrnut do těchto studijních plánů:
| Stránka vytvořena 19.8.2022 17:49:54, semestry: L/2021-2, Z/2024-5, Z,L/2022-3, 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) |