Zkouška 4.6.2008

[Osiris]

Tenhle termín byl dost drsný (tedy alespoň podle mě, nedal jsem to myslím).

Měli jsme nadefinováni jinou výrokovou logiku, než tu standardní, a k ní celkem těžké příklady.

V predikátové logice byl převést formuli na prenexní tvar + zjistit, zda je dokazatelná popř. důkaz, větu o rozšíření pomocí funkčního symbolu a dále dokázat něco v Peannově aritmetice.

[Martin Černý]

Podrobnější popis:
Zkouška písemná, 6 příkladů, celkem max. 50b na 3 je potřeba 22b. Čas na písemku 2hod. Výsledky během několika dnů v SISu.
Celkově téměř nebylo potřeba znát teorii, protože tam (až na otázku č. 5, která byla přímo na definici a důkaz) všechna byla uvedena.

Měl jsem zadání B

V úvodu písemky byly dvě stránky se základy výrokové logiky, ale trochu pozměněné:
- vše definováno pomocí NOT a AND
- ohodnocení výrokových proměnných ne jako funkce, ale jako podmnožina všech výrokových proměnných (proměnné obsažené v podmnožině jsou pravdivé)
- úplně vynechána formální metoda, symboly |- a |= definovány ekvivalentně
Nevím, jak moc to bylo třeba, ale pro jistotu jsem všechny příklady z výrokové logiky řešil přesně podle definic, jak byly uvedeny v písemce. (takže implikaci jsem převáděl na AND a tak...)

Výroková logika:

1)
a) Ukažete, že všechny výrokové spojky lze vyjádřit pomocí AND a NOT (2 body)
b) ukažte, že formule A a B jsou sémanticky ekvivalentní (mají stejnou množinu modelů) právě když A<=>B je validní formule. (3b)

2)
a) ukažte, že neplatí: je-li T splnitelná množina formulí, potom ja každá formule z T validní (1b)
b) Dokažte, že obrácená implikace a) platí (4b)

3) Pozitivní formule je formule vytvořená jen z výrokových proměnných, OR a AND (tj. neobsahuje negaci, implikaci ani ekvivalenci)
Dokažte, že negace pozitivní formule není validní. (10b)

Predikátová logika:
4)
(Ex)P(x) -> (Vx)(Q(x) <-> (Ex)P(x)) // nejsem si jistej, takhle nějak to bylo plus mínus nějakej kvantifikátor
a) Převod formule do prenexního tvaru. (3b)
b) Rozhodněte, zda je formule větou predikátové logiky. Pokud ano, uveďte důkaz (7b)

5)
a) Definujte konzervativní rozšíření teorie (1b)
b) Formulujte větu o zavedení predikátového symbolu a dokažte, že takto vznikne konzervativní rozšíření teorie. (9b)

6)
Byly zde uvedeny axiomy Robinsonovy aritmetiky a Peanovy aritmetiky (viz slidy)
V Peanově aritmetice dokažte že (Vx)(S(x) != x) (10b)

Mě osobně to příjemně překvapilo a nic mi nepřišlo obzvláště těžké, ale to je asi věc názoru... (a taky se uvidí, jak jsem nakonec dopad )

[czestmyr]

A do pytle...
Jina, nez klasicka vyrokova z prednasky, rikas?
Tak to se obavam, ze to mam cely blbe A to jsem si rikal, jak bylo to zadani lehky...
Co jsi byl za skupinu? Ja byl (A)

Jinak pro ostatni: byly tam pomerne jednoduchy vety z vyrokovy logiky - nektery nebyly na prednasce, ale byly trivialni. Dalo se to dokazat pres semantiku, takze celkem v pohode.
To byly dva priklady, celkem za 10 bodu

Potom tam bylo prevadeni formule v predikatovy logice do prenexniho tvaru a dale zjistit, zda je dokazatelna. Pokud nebyla, tak jsme meli uvest, za jakych predpokladu by byla. Ta formule byla takovato: Ex(x) (A(x) -> B(x)) -> (Vs(x)A(x) -> B(x)). Tenhle priklad byl za 10 bodu

Dalsi priklad - uvest vetu o zavedeni funkcniho symbolu a dokazat ji. Taky 10 bodu

Pak jeste dokazat v Peanove aritmetice Vs(x)(x >= 0) Taktez za 10 bodu

Pak tam bylo jeste neco n a dokazani z predikatovy logiky, ale to uz si nepamatuju, jak presne znelo.

[Osiris]

Tak už jsou výsledky, dal jsem to za 2... A jsem rád