V zimn�m semestru akademick�ho roku 2012/2013 vedu jedno cvi�en� k p�edn�ce V�rokov� a predik�tov� logika. Cvi�en� se kon� v �ter� od 17:20 v S6 na Mal� Stran�.

Po�adavky na z�po�et jsou ��ste�n� ur�en� centr�ln� - z�sk�n� jist�ho po�tu bod� (bude up�esn�no pozd�ji) z kr�tk�ch test� (15 minut), d�le je vy�adov�na prezence a aktivita (�e�en� �lohy u tabule, dobr� n�pad vy��en� z lavice, ...).

Od 23.10.2012 se za��naj� na cvi�en� ps�t kr�tk� testy. �lohy na test budou �erpat z l�tky probran� na cvi�en� a p�edn�ce.

6.11.2012 cvi�en� odpad� kv�li zahrani�n� cest� na konferenci.

20.11.2012 je cvi�en� zru�eno kv�li nemoci vyu�uj�c�ho.

Aktu�ln� platn� t�mata na kr�tk� test

V�dy je t�eba uva�ovat tak� pojmy v rozumn�m okol� n�e uveden�ch hesel.

• formule, struktury, pravdivost formule ve struktu�e
• izomorfismus struktur, element�rn� ekvivalence, element�rn� podstruktury
• podstruktura, extenze, expanze, redukt
• vztah pravdivosti formule a logick�ch spojek
• definovateln� mno�iny, vztah k rela�n�m datab�z�m
• kvantifik�tory, voln� a v�zan� prom�nn�, substituovatelnost, varianty formule
• axiomy, odvozovac� pravidla, dokazatelnost formul�, teorie T, Thm(T)
• v�rokov� logika, CNF, DNF tvar formule, korektnost, �plnost
• teorie uspo��d�n�: LO, DeLO, DiLO, + konce
• teorie n�sledn�ka: SC, SC₀, SCI
• aritmetick� teorie: Pr, Q, P
• ekvivalence v�rok� a teori�, po�ty neekvivalentn�ch v�rok� a teori�
• kompletn� teorie, r�zn� typy v�rok�: pravdiv�, l�iv�, konzistentn�
• axiomatizovatelnost, kone�n� axiomatizovatelnost, odd�litelnost, otev�enost, uzav�enost

�lohy na dom�c� �kol

N�sleduj� jednoduch� �lohy na dom�c� �kol. Ka�d� �loha odpov�d� jedn� ��rce za aktivitu.

1. Kolik kus� oble�en� je pot�eba, aby mohla ka�d� �ena m�t sv�j nezam�niteln� vkus?

2. Kolik existuje neekvivalentn�ch v�rokov�ch formul� nad mno�inou prvov�rok� P?

3. Kolik by mohlo existovat r�zn�ch (tj. neekvivaletn�ch) bin�rn�ch logick�ch spojek?

4. Je CNF/DNF tvar pro danou formuli jednozan�n�? Navrhn�te metodu na zkr�cen� CNF/DNF reprezentace formule.

5. Jsou d�ny formule ψ a χ. Kolik je neekvivalentn�ch v�rok� φ, �e ψ|-φ a φ|-χ. Pracujeme se mno�inou prvov�rok� P.

6. Uka�te, �e mno�ina K je kone�n� axiomatizovateln�, pr�v� kdy� K a -K jsou axiomatizovateln�.

7. Pracujme s mno�inou prvov�rok� P (m��e b�t nekone�n�). M�jme K₁,K₂,...,K_n, kde n∈N axiomatizovateln� mno�iny ohodnocen� nad P. Napi�te axiomatiku ∪_i=1ⁿK_i.

8. Formulujte Pigeon Hole Principle pro 4 holuby a 3 d�ry jako splnitelnost CNF v�rokov� formule. Pomoc� rezolu�n� metody uka�te, �e dan� �loha nem� �e�en�.

9. Uka�te, �e mno�ina p�irozen�ch ��sel m� men�� mohutnost ne� mno�ina v�ech jej�ch podmno�in.

10. Pracujme s mno�inou prvov�rok� P (m��e b�t nekone�n�). Existuje mno�ina ohodnocen� na P, kter� nen� axiomatizovateln�? Pokud ano, popi�te takovou mno�inu.