Pavel Surynek's Academic Page | V�rokov� a predik�tov� logika (NAIL062)

V�rokov� a predik�tov� logika (NAIL062)

Obecn�  |  Povinnosti     


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, SC0, 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 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.