Matemaatilise loogika elemendid
Eksam 11.VI 1999
 

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.