V zimním semestru akademického roku 2010/2011 vedu jedno cvičení k přednášce Výroková a predikátová logika. Cvičení se koná v úterý od 12:20 v S11 na Malé Straně.

Požadavky na zápočet jsou prezence, aktivita (řešení úlohy u tabule, dobrý nápad vyřčený z lavice, ...) a napsání zápočtových písemek, které se budou psát alespoň dvě.

16.11.2010 se bude psát první zápočtová písemka. Náplní písemky může být cokoli, co se do daného termínu probere na cvičení (včetně suplovaných) nebo přednášce (přednáška 15.11.2010 se nepočítá).

7.12.2010 se bude psát opravná písemka k první zápočtové písemce. Rozsah látky pro písemku zůstává stejný.

4.1.2011 se bude psát centrálně organizovaná zápočtová písemka. Náplň písemky stanovil přednášející, zřejmě také na přednášce o náplni písemky pojednal.

11.1.2011 se bude psát opravná písemka ke druhé zápočtové písemce. Úlohy pro písemku budou čerpat z témat probaných do Vánoc. Typově bude písemka odpovídat první zápočtové písemce.

V případě neúspěchu v obou pokusech o napsání některé ze zápočtových písemek je třeba, aby se uchazeč o zápočet dostavil na konzultaci a prokázal porozumění látce, ve které chyboval.

---

Poznámky ke cvičením

Cvičení 30.11.2010
1) ⊢ (∀x)φ→(∃x)φ ověřte pomocí syntaktických prostředků.
Použijeme axiom substituce ⊢ (∀x)φ→φ(x/t), dále dokážeme, že platí ⊢ φ(x/t)→(∃x)φ a z pravidla tranzitivity tj. T ⊢ φ→ψ a T ⊢ ψ→χ, pak T ⊢ φ→χ, dostáváme požadované tvrzení.
Důkazy lemmat:
⊢ (∀x)¬φ→¬φ(x/t) (1) je instance axiomu substituce, z ⊢ ((∀x)¬φ→¬φ(x/t))→(¬¬φ(x/t)→¬(∀x)¬φ) (2), což je instance obvyklého lemmatu (otočený PL3), potom dostaneme pomocí MP s (1) a (2) ⊢ ¬¬φ(x/t)→¬(∀x)¬φ tedy ⊢ φ(x/t)→(∃x)φ (odstranění dvojité negace a přepis ∀ pomocí ∃).
K důkazu pravidla tranzitivity použijeme instanci PL1 T ⊢ (ψ→χ)→(φ→(ψ→χ)), z čehož MP s předpokladem T ⊢ ψ→χ dostáváme T ⊢ (φ→(ψ→χ)) (3), nyní použijeme PL2, tedy T ⊢ (φ→(ψ→χ))→((φ→ψ)→(φ→χ)), z čehož MP s (3) dostaneme T ⊢ (φ→ψ)→(φ→χ), z čehož MP s předpokladem T ⊢ φ→ψ dostáváme požadované tvzení T ⊢ φ→χ.

2) ⊢ (∃x)(∀x)φ↔(∀x)φ ověřte pomocí syntaktických prostředků.
Nejprve položením t=x dostáváme z tvrzení ⊢ ψ(x/t)→(∃x)ψ dokázaného v předchozím příkladě ⊢ ψ→(∃x)ψ. Volbou ψ:=(∀x)φ dostáváme ⊢ (∀x)φ→(∃x)(∀x)φ.
Předpokládejme, že platí ⊢ φ→ψ (4), kde x nemá volný výskyt v ψ, potom z ⊢ (φ→ψ)→(¬ψ→¬φ), což je instance obvyklého lemmatu (otočený PL3), pomocí MP s (4) dostáváme ⊢ (¬ψ→¬φ). Pomocí pravidla generalizace obdržíme ⊢ (∀x)(¬ψ→¬φ) (5). Jelikož x není volná v ψ, je ⊢ (∀x)(¬ψ→¬φ)→(¬ψ→(∀x)¬φ) instancí axiomu zavedení ∀, pomocí MP s (5) dostáváme ⊢ (¬ψ→(∀x)¬φ) (6). Nyní již obvyklými obraty, které byly ukázány výše (otočení →, odstranění dvojité negace a přepis ∀ pomocí ∃) dostáváme ⊢ ((∃x)φ→ψ) (7).
Položením ψ:=(∀x)φ (lze, protože x není volná ve (∀x)φ) a φ:=(∀x)φ a pomocí předpokladu, že ⊢ (∀x)φ→(∀x)φ, což je obvyklé lemma, dostáváme ⊢ (∃x)(∀x)φ→(∀x)φ.

3) Nechť φ(x,y) je výroková formule obsahující právě proměnné x a y. Oveřte, zda platí, že φ(x,y) je splnitelná, právě když formule (φ(x,y)∨φ(¬x,y)∨φ(x,¬y)∨φ(¬x,¬y)) je pravdivá.

Úlohy na doplnění aktivity
Odkazuji se na materiál STAV z webových stránek docenta Mlčka.
Přednáška 1: 5, 13, 14, 15.
Přednáška 2: 3, 4, 5, 7, 10.
Přednáška 3: 5, 7.
Přednáška 5: 3, 4, 5, 6, 7, 8, 9.
Přednáška 6: 4, 5, 6, 7.
Přednáška 7: 8, 9, 10.
Přednáška 8: 6, 7, 8, 9.
Přednáška 9: 1, 2.
Přednáška 10: 1, 2, 3, 4.