Jdi na navigaci předmětu

Algebra a logika (2022)

kontakt

Jan Starý, jan.stary@fit.cvut.cz

anotace

Cílem výběrové přednášky je prohloubit a rozšířit témata ze základního kurzu logiky a popsat souvislosti logiky s informatikou a algebrou. Podrobněji viz předběžný plán níže.

literatura

Výchozím textem je Úvod do matematické logiky. Pro zvídavé jsou zde i některé původní články na jednotlivá témata.

bylo

  • př 18.02. Jazyk predikátové logiky; splňování, volné a vázané proměnné.
  • př 25.02. Dokazatenost. Uzávěr, věta o dedukci.
  • cv 25.02. Splňování ve strukturách. Axiomy rovnosti. Prenexní tvar.
  • př 04.03. Věta o korektnosti. Idea Henkinova důkazu úplnosti.
  • př 11.03. bezesporné zúplnění, důkaza Gödelovy věty.
  • cv 11.03. kompaktnost: důsledky v algebře: tělesa, grupy, …​
  • př 18.03. rozšiřování teorií, konzervativní Henkinovské rozšíření
  • př 25.03. Rezoluční metoda: Skolemizace, unifikace.
  • cv 25.03. substituce, unifikační algoritmus
  • př 01.04. Rezoluční metoda: Robinson.
  • př 08.04. Rezoluční metoda: aplikace v algebře.
  • cv 08.04. Axiomy teorie množin
  • př 15.04. (Velikonoce)
  • př 22.04. Relace, funkce, ekvivalence, uspořádání
  • cv 22.04. základní množinové konstrukce
  • př 29.04. Dobrá uspořádání, ordinální čísla.
  • př 06.05. Axiom výběru, principy maximality.
  • cv 06.05. Přirozená, celá, racionální, reálná čísla.
  • př 13.05. Mohutnost: kardinální čísla.

hodnocení

Úspěšně absolvovat BI-ALO obnáší získat zápočet a složit zkoušku.

Na přednáškách i cvičeních budu průběžně zadávat drobné podúlohy, přeskakovat krátké důkazy technikálií apod, které později podrobně uděláme (tj. uděláte) na cvičeních. Zkoušce pak předchází zápočtový test obsahující dva „početní“ příklady. Zkoušku lze skládat teprve po získání zápočtu.

Po dvou „praktických“ úlohách tvořících zápočet (typicky nějaká konkrétní „početní“ otázka v konkrétní struktuře, konstrukce nějaké struktury, prenexní tvar, Skolemizace, resoluce, apod.) následují dvě obsáhlejší „teoretické“ otázky (typicky definice-věta-důkaz). V teoretických otázkách jde o pochopení základních pojmů, hlavní věty, a hlavní myšlenky důkazů, nikoli o sáhodlouhou indukci nebo technikálie.

Pokud někoho obzvláště zaujme některé z témat, která jsme prošli, může jednu z těchto teoretických otázek navrhnout sám předem. Taková zkoušková otázka podléhá mému schválení co do rozsahu; dobrým příkladem je: definice dobrých uspořádání, ordinálů, a důkaz věty o tom, že každé dobré uspořádání je isomorfní s právě jedním ordinálem; nebo: axiom výběru a s ním ekvivalentní principy maximality.

cvičení

Zde budou zveřejněny úlohy, jejichž řešením na cvičení lze získávat body přispívající k zápočtu. Číslování vět a důkazů se odvolává vždy na současnou verzi textu (který průběžně roste). Kdyby některý z příkladů někoho zaujal, ozvěte se prosím.

  • Dokažte lemma o variantách.
  • Dokažte lemma o konstantách.
  • Ukažte na příkladech, že podmínky na (ne)výskyt volných proměnných jsou v prenexních operacích nutné; to jest, ukažte konkrétní formule, které mají volné proměné, a ekvivalence používané v prenexních operací následně neplatí; tuto neekvivalenci předveďte na konkrétních strukturách.
  • Vypracujte cvičení na konci oddílu 3.1

zkouškové termíny

Zkouškovým termínem je kterýkoli den zkouškového období, který se vám hodí, pokud o něm vím řekněme dva dny předem. Při našem počtu nemá cenu vypisovat termíny hromadně, resp. můžeme formálně vypsat každý takový termín.

logika v blízkém okolí