Diskrétní matematika a logika pro KM

Přednášející:

Marie Demlová (gar.)

Cvičící:

Marie Demlová (gar.), Jiřina Scholtzová

Předmět zajišťuje:

katedra matematiky

Anotace:

Základy matematické logiky a teorie grafů se zaměřením na obor

„Kybernetika a měření“. Jedná se zejména o tyto partie výrokové

logiky: pravdivostní ohodnocení, sémantický důsledek a tautologická

ekvivalence formulí, CNF a DNF, rezoluční metoda ve výrokové

logice. Dále je zavedena predikátová logika. V teorii grafů se jedná o

zavedení orientovaného i neorientovaného grafu, pojem stromu,

eulerovských a hamiltonovských grafů. Na závěr jsou uvedeny binární

operace s důrazem na grupy a jejich vlastnosti.

Požadavky:

Podmínkou získání zápočtu je aktivní účast na cvičeních.

Další informace viz http://math.feld.cvut.cz/demlova/teaching/dmc_vyuka.html

Osnova přednášek:

1. Formule výrokové logiky, pravdivostní ohodnocení.

2. Sémantický důsledek, tautologická ekvivalence.

3. CNF a DNF, Booleovský kalkul.

4. Rezoluční metoda ve výrokové logice.

5. Zavedení predikátové logiky, kvantifikátory.

6. Interpretace predikátové logiky.

7. Grafy orientované a neorientované.

8. Stromy a kořenové stromy.

9. Eulerovy grafy a jejich aplikace.

10. Hamiltonovy grafy a jejich aplikace.

11. Barevnost grafů, kliky v grafech.

12. Základní binární operace a jejich vlastnosti.

13. Pologrupy a monoidy.

14. Grupy a jejich vlastnosti.

Osnova cvičení:

1. Formule výrokové logiky, pravdivostní ohodnocení.

2. Sémantický důsledek, tautologická ekvivalence.

3. CNF a DNF, Booleovský kalkul.

4. Rezoluční metoda ve výrokové logice.

5. Zavedení predikátové logiky, kvantifikátory.

6. Interpretace predikátové logiky.

7. Grafy orientované a neorientované.

8. Stromy a kořenové stromy.

9. Eulerovy grafy a jejich aplikace.

10. Hamiltonovy grafy a jejich aplikace.

11. Barevnost grafů, kliky v grafech.

12. Základní binární operace a jejich vlastnosti.

13. Pologrupy a monoidy.

14. Grupy a jejich vlastnosti.

Cíle studia:

Studijní materiály:

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

2. J. Demel: Grafy. SNTL Praha, 1988.

Poznámka:

Rozsah výuky v kombinované formě studia: 14+6

Typ cvičení: s

Další informace:

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Kybernetika a měření- strukturované studium (povinně volitelný předmět)