Logický proseminář - ZS 2008/9
čtvrtek 9:10-10:40 v 137/Cel, ALG100004 a ALG200004 (0/2 Z, 0/2 Z)
Cíle kurzu
Cílem kurzu je přiblížit studentům základy práce v logice, ukázat souvislosti mezi jednotlivými vyučovanými předměty, vyjasnit jakékoli obsahové či metodologické nejasnosti, které mohou během prvního roku studia vyvstávat, a seznámit studenty s konkrétní náplní práce logika. Vše by si měli osvojit při procvičování látky probrané v kurzu Logika I a případně i v jiných kurzech určených pro první rok studia.
Sylabus
Atestace
Zápočet je udělován za aktivní účast a zápočtovou písemku.
Konzultace
Standardní konzultace nemám vypsané, ale pokud si s něčím nevíte rady, klidně mi napište a domluvíme se. Na katedře standardně bývám v úterý od cca 9.00 do cca 12.00, radši mi ale dejte předem vědět, že přijdete, můžete si tak ušetřit případnou zbytečnou cestu. Po předchozí domluvě (osobně či emailem) je možný i jiný termín.
Literatura
Příklady jsou brány z nejrůznějších zdrojů, základní probíraná látka však stejně jako přednáška dr. Bílkové vychází z následujících knih:
1. hodina (9.10.2008)
Organizační záležitosti. Látka neprobírána z důvodu imatrikulace.
2. hodina (16.10.2008)
Různé základní typy důkazů (přímý, nepřímý a sporem), jejich vztahy a příklady. Důkazy matematickou indukcí - obecná idea, pro přirozená čísla, pro formule. Jazyk a metajazyk.
3. hodina (23.10.2008)
Sémiotika (pragmatika, sémantika, syntaktika). Paradoxy logické (Russellův), sémantické (lháře, Berryho, Grellingův) a pseudoparadoxy (varianta lháře, holič). Rekurzívní definice - délka formule, počet závorek, počet atomů,... Ohodnocení, tautologie, vyplývání. Platí když Γ |= p ∧ q, pak Γ |= p a Γ |= q, ale neplatí když Γ |= p ∨ q, pak Γ |= p nebo Γ |= p. (V závěrečném spěchu, myslím, zaznělo, že to naopak platí. Správně mělo zaznít, že tvrzení obecně platí pouze pokud je Γ tvořena výhradně atomy, což však bohužel nezaznělo. Tvrzení Γ |= φ ∨ ψ, pak Γ |= φ nebo Γ |= ψ nicméně neplatí ani za těchto omezujících podmínek.)
4. hodina (30.10.2008)
Polská prefixová notace. Extrémy funkce závorky fle ku délka fle. Ohodnocení - definice, důkaz (indukcí podle složitosti i alternativně sporem) rozšíření z atomů na fle a jeho jednoznačnosti včetně diskuse důsledků tohoto tvrzení. Splnitelnost a tautologie - jejich testování, informačně SAT a problém zda P=NP. Nesplnitelné množiny a vyplývání z nich.
- úkol na příště - vyřešte nové příklady a kdo nestihl i staré příklady! V případě nejasností konzultujte knihu doc. Švejdara, poraďte se s kolegy či mne kontaktujte.
6.11.2008 hodina odpadla
5. hodina (13.11.2008)
Většinu hodiny jsme věnovali řešení domácích úkolů. Vzájemná definovatelnost spojek. Funkční úplnost množiny spojek konjunkce, disjunkce (stačí jedna z nich) a negace - důkaz indukcí (van Dalen, věta 1.3.6) či přímo z tabulky výrokové fce, ten nám navíc dává konstrukci DNF či CNF. Distribuce konjunce a disjunkce. Jednoduchý algoritmus k sestrojení DNF či CNF.
- úkol na příště - vyřešte příklady (úplná DNF je taková DNF, že v každé konjunkci se nalézají všechny výrokové atomy formule, obdobně pro CNF) V případě nejasností mě kontaktujte!
6. hodina (20.11.2008)
Dokazovaní funkční (ne)úplnosti množiny spojek. Jednoduchý důkaz, že jsou nejvýše (a tedy i právě) dvě binární logické spojky, které jsou funkčně úplné. Spojka IF p THEN q ELSE r. Problém tautologičnosti a splnitelnosti pro CNF a DNF. Vlastnosti vyplývání a vztah se splnitelností. Dokazovaní v Hilbertovském kalkulu. Monotónost dokazování z předpokladů. Pokud je fle dokazatelná z množiny předpokladů, pak už je dokazatelná z její konečné podmnožiny. Důsledky věty o dedukci - vlastnosti implikace. Důkazy několika formulí v HK.
- úkol na příště - vyřešte příklady. V případě nejasností mě kontaktujte!
7. hodina (27.11.2008)
Dokazování v hilbertovském kalkulu - použití věty o dedukci, tranzitivita implikace, různé triky, lemma o neutrální formuli.
- úkol na příště - vyřešte příklady. V případě nejasností mě kontaktujte!
8. hodina (4.12.2008)
Dokazovaní v hilbertovském kalkulu - distribuce negace pres konjunkci, ekvivalentní systémy, (ne)závislost axiomů. Věta o kompaktnosti - některé její formulace pro výrokovou logiku, použití, Švejdar cv. 1 str. 27 a př. 1.2.3 str. 24.
- úkol na příště - vyřešte příklady. V případě nejasností mě kontaktujte!
9. hodina (11.12.2008)
Syntaktické vs. sémantické pojmy. Predikátová logika prvního řádu - logické a mimologické symboly, matematická struktura - nosič a realizace symbolů, ohodnocení, platnost formule ve struktuře při daném ohodnocení. Především motivace jednotlivých pojmů a co za nimi hledat.
- úkol na příště - vyřešte příklady. V případě nejasností mě kontaktujte!
10. hodina (18.12.2008)
Řešení příkladů z minule - základní sémantické pojmy v predikátové logice a jejich vlastnosti. The Hardest Logical Puzzle Ever - Wikipedia či přímo Boolosův článek.
1. ZÁPOČTOVÁ PÍSEMKA (8.1.2009)
S ohledem na výsledek písemky se ve čtvrtek 15.1.2009 od 9:10 v Cel/137 konala konzultační hodina, kde bychom společně vyřešili písemku a případně i některé další příklady dle vaší volby.
2. ZÁPOČTOVÁ PÍSEMKA (22.1.2009)
3. ZÁPOČTOVÁ PÍSEMKA (5.2.2009)
4. ZÁPOČTOVÁ PÍSEMKA (11.3.2009)
DALŠÍ ZÁPOČTOVÁ PÍSEMKA (???)
V případě zájmu jsem ochoten vypsat další termín v průběhu letního zkouškového období. Zájemci ať mě případně kontaktují.
Předpokládá se schopnost řešit úlohy z výrokové logiky podobné těm, které jsme řešili na semináři a v rámci domácích cvíčení.
Zprávníček - sdělte mi (anonymně) svoje názory na seminář - negativní, pozitivní, návrhy na zlepšení či změnu... Díky za reakce!
email: karel zavináč chvalovsky tečka cz