V�rokov� a predik�tov� logika (NAIL062)
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� testV�dy je t�eba uva�ovat tak� pojmy v rozumn�m okol� n�e uveden�ch hesel.
�lohy na dom�c� �kolN�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 K1,K2,...,Kn, kde n∈N axiomatizovateln� mno�iny ohodnocen� nad P. Napi�te axiomatiku ∪i=1nKi. 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.
|