1. A. Defineerida järgmised lausearvutuse mõisted:
1) valem,
2) väärtustus,
3) samaselt tõene valem, kehtestatav valem,
4) valemite samaväärsus,
5) valem A järeldub valemist B,
6) täielik elementaarkonjunktsioon (kirjutada ka üldkuju välja),
7) täielik disjunktiivne normaalkuju (kirjutada ka üldkuju välja),
B. Formuleerida:
8) lemma täieliku elementaarkonjunktsiooni tõesuspiirkonna kohta,
9) lemma TDNK tõesuspiirkonna kohta,
10) Boole’i funktsiooni TDNK olemasolu tarvilik ja piisav tingimus,
C. Vastata küsimustele:
11) millistele erikujudele saab lausearvutuse valemeid samaväärsusteisendustega
viia?
12) milline on samaselt tõese valemi TDNK?
13) millises vahekorras on valemite A(X,Y) ja B(X,Y) TDNK-d,
kui A-st järeldub B?
14) tuua näide kahest sellisest valemist, kus on samad muutujad
ja millest kumbki ei järeldu teisest.
2. Konstrueerida iga tingimuse rahuldamiseks võimalikult väikese
kandjaga
interpretatsioon:
1) "x[P(x)=>Q(x)]=t, "x[Q(x)=>R(x)]=t,
$x[P(x)~R(x)]=v,
2) "x[P(x)=>Q(x)]=v, "x[Q(x)=>P(x)]=v,
$x[P(x)~Q(x)]=t,
3) "x(A(x)vB(x)) = t, $x(A(x)&B(x))
=v, "x(A(x)=>B(x)) =t, "x(B(x)=>A(x))
=v,
4) "x(A(x)~B(x)) =v, "x(B(x)~C(x))
=v, "x(A(x)~C(x)) =v, "x(A(x)=>B(x))
=v, "x(B(x)=>C(x)) =v,
5) "x$yA(x,y)
=t, $x"(x,x)=v,
"x(A(x,y)=>¬A(y,x))=t.
3. Turingi masinate hargnemine.
1) Anda definitsioon ja selgitada vastavust programmeerimiskeelte
vastava konstruktsiooniga,
2) Selgitada, miks on definitsioonis kompositsioon,
3) Formuleerida ja tõestada teoreem hargnemismasina olemasolust.