Jdi na navigaci předmětu

Algebra a logika (2024)

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

  • 23.02. Syntax a sémantika predikátové logiky.
  • 01.03. Splňování ve strukturách: příklady.
  • 01.03. Volné a vázané proměnné. Dokazatenost.

bude

  • 08.03. Věta o dedukci. Věta o korektnosti.
  • 15.03. Prenexní tvar, axiomy rovnosti.
  • 15.03. Úplnost: Henkinova věta.
  • 22.03. Bezesporné Henkinovské zúplnění, Gödelova věta. Kompaktnost.
  • 29.03. (Velikonoce)
  • 29.03. (Velikonoce)
  • 05.04. Důsledky kompaktnosti v algebře. (lichý pátek)
  • 05.04. Skolemizace, rezoluce bez proměnných (lichý pátek)
  • 12.04. Unifikace, predikátová rezoluce
  • 12.04. Rezoluce: pologrupy
  • 19.04. Základy teorie množin
  • 26.04. Relace, funkce, ekvivalence, uspořádání
  • 26.04. Dobrá uspořádání, ordinální čísla.
  • 03.05. Přirozená čísla
  • 10.05. Konstrukce celých, racionálních, reálných čísel.
  • 10.05. Axiom výběru, principy maximality.
  • 17.05. Mohutnosti, 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.

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í