MLG - Definice

up:: MLG

old

-

1. Logika

Dále napište definici pojmu „konjunktivní tvar formule“. 6 Dále napište definici pojmu „disjunktivní tvar formule“. Dále napište definici pojmu „kontradikce“. Dále napište definici pojmu „tautalogie“. Dále napište definici pojmu „splnitelná formule“.

b) Napište definici pojmu „průnik množin A a B“. 2

2. Množiny

Dále napište definici pojmu „tranzitivní relace”. 2 Dále napište definici pojmu „antisymetrická relace”. Dále napište definici pojmu „symetrická relace”. 3 Dále napište definici pojmu „antisymetrická relace”. 3 Dále napište definici pojmu „reflexivní relace”.

3. Grafy

Dále napište definici pojmu „faktor grafu“. 2 Dále napište definici pojmu „kostra grafu“ 2 Dále napište definici pojmu „strom“ v teorii grafů. Dále napište definici pojmu „neorientovaný graf“. Dále napište definici pojmu „orientovaný graf“.

Dále napište definici pojmu „uzavřený“ tah. Dále napište definici pojmu „otevřený“ tah. 3 Dále napište definici pojmu „Eulerovský“ tah.

4. Automaty

Dále napište definici pojmu „dosažitelný stav automatu“. Dále napište definici pojmu „výpočet automatu nad slovem u“. Dále napište definici pojmu „regulární jazyk“. 3

---

Rozdíl množin A a B, který značíme A-B, je množina, která obsahuje všechny prvky množiny A s výjimkou těch, jež jsou zároveň prvky množiny B

Graf se nazývá Eulerovský, pokud v něm existuje (uzavřený či otevřený) tah, který obsahuje každou hranu právě jednou. Nazývá se (uzavřený či otevřený) Eulerovský Tah

Stav q se nazývá dosažitelný, pokud existuje slovo takové, že výpočet nad tímto slovem končí ve stavu q. Konečný automat se nazývá dosažitelný, pokud jsou dosažitelné všechny jeho stavy

Definice

1.Logika

Formule se nazývá X, pokud je Y v každém ohodnocení Formule se nazývá Tautologie, pokud je pravdivá v každém ohodnocení Formule se nazývá Kontradikce, pokud je nepravdiváv každém ohodnocení Formule se nazývá Splnitelná, pokud je splnitelná nějakém ohodnocení

Konjunktivní: Formule, která je logicky spojena pomocí spojky OR mezi jednotlivými složkami. Disjunktivní: Formule, která je logicky spojena pomocí spojky AND mezi jednotlivými složkami.

2.Množiny

( Relace, kde pro ) Reflexivní: všechna a ∈ A platí: (a, a) ∈ R. Symetrická: každé a, b ∈ A platí: pokud (a, b) ∈ R, pak (b, a) ∈ R. Antisymetrická: každé a, b platí: pokud (a, b) ∈ R a (b, a) ∈ R, pak a = b. Tranzitivní: všechna a, b, c platí: pokud (a, b) ∈ R a (b, c) ∈ R, pak (a, c) ∈ R. Ekvivalence: Relace, která je reflexivní, symetrická a tranzitivní. Uspořádání: Relace, která je reflexivní, antisymetrická a tranzitivní.

3.Grafy

Graf se nazývá strom, pokud neobsahuje žádnou kružnici a je souvislý. Podgraf obsahující všechny vrcholy původního grafu G se nazývá faktor grafu G. Faktor souvislého grafu G, který je zároveň stromem, se nazývá kostra grafu G. Kritická cesta je jakákoli orientovaná cesta z s do t, jejíž délka je maximální mezi všemi takovými cestami. TAH: Uzavřený= stejném | Otevřený= různých ⇒  Cesta, která začíná a končí ve X vrcholu. Eulerovský tah: Cesta, která navštěvuje každý hranu v grafu právě jednou.

4.Automaty

Jazyk L se nazývá regulární, pokud existuje konečný automat A, který ho přijímá, tedy L=L(A) Stav q se nazývá dosažitelný, pokud existuje slovo takové, že výpočet nad tímto slovem končí ve stavu q.