Тьюринг машинасының автоматы жұмыс барысында келесі әрекеттерді орындай алады

1. Сыртқы алфавиттің таңбасын ұяшыққа жазыңыз (соның ішінде бос), ішіндегісін (соның ішінде бос) ауыстырыңыз.

   
   

2. Бір ұяшықты солға немесе оңға жылжытыңыз.

   
   

3. Ішкі күйіңізді өзгертіңіз.

   
   

Тьюринг машинасының бір пәрмені осы үш құрамдастың нақты комбинациясы болып табылады: ұяшыққа қандай таңбаны жазу керек (автомат оның үстінде орналасқан), қайда жылжыту керек және қай күйге бару керек нұсқаулар. Команда барлық құрамдастарды қамтымаса да (мысалы, таңбаны өзгертпеңіз, жылжытпаңыз немесе ішкі күйін өзгертпеңіз).

1. f(x,y)=x&y функциясы берiлген (1,1), (1,0) аралықта мәнiн тапыңыз. Жауабы: & бұл амал конъюнкция амалын (көбейту) білдіреді. Яғни f₁(1,1)=1&1=1; f₂(1,0)=1&0=1

   
   

2. және бейнелеулер берiлсiн. композицияны табыңыз:

   
   

3. және бейнелеулер берiлсiн. композицияны табыңыз:

   
   

4. А қаласынан В қаласына 2 жолмен, ал В қаласынан С қаласына 3 жолмен баруға болады. В қаласы арқылы А қаласынан С қаласына қанша әдiспен жетуге болады? Жауабы: Біз бұл есепте қосымша айнымалылар енгіземіз. A қаласынан B қаласына 2 жолмен баратындықтан біз оларды (x1,x2) деп аламыз. Ал B қаласынан С қаласына 3 жолмен баратын болғандықтан біз оларды (y1, y2, y3) деп аламыз. Шешуі: (x1,y1); (x1,y2), (x1,y3); (x2,y1); (x2,y2); (x2,y3) Жауабы: 6 әдіспен баруға болады.

   
   

5. А қаласынан В қаласына 3 жолмен, ал В қаласынан С қаласына 5 жолмен баруға болады. В қаласы арқылы А аласынан С қаласына қанша әдiспен жетуге болады? Шешімі: Біз бұл есепте қосымша айнымалылар енгіземіз. A қаласынан B қаласына 3 жолмен баратындықтан біз оларды (x1,x2,x3) деп аламыз. Ал B қаласынан С қаласына 5 жолмен баратын болғандықтан біз оларды (y1, y2, y3, y4, y5) деп аламыз. Шешуі: (x1,y1); (x1,y2); (x1,y3); (x1,y4); (x1, y5); (x2,y1); (x2,y2); (x2,y3); (x2,y4); (x2, y5); (x3,y1); (x3,y2); (x3,y3); (x3,y4); (x3, y5) Жауабы: 15 әдіспен баруға болады.

   
   

6. А қаласынан В қаласына 2 жолмен, ал В қаласынан С қаласына 3 жолмен баруға болады. А қаласынан С қаласына В дан өтпейтiн 2 жол бар. А қаласынан С қаласына қанша ´дiспен жетуге болады? Шешімі: Біз бұл есепте қосымша мән енгіземіз. A қаласынан B қаласына 2 жолмен баратындықтан біз оларды (x1,x2) деп аламыз. Ал B қаласынан С қаласына 3 жолмен баратын болғандықтан біз оларды (y1, y2, y3) деп аламыз. A қаласынан C қаласына B дан өтпейтін 2 жол болғандықтан оларды z1, z2 деп белгілейміз. Шешуі: (x1,y1); (x1,y2); (x1,y3); (x2,y1); (x2,y2); (x2,y3); z1; z3. Жауабы: 8 әдіспен баруға болады.

   
   

7. А қаласынан В қаласына 3 жолмен, ал В қаласынан С қаласына 5 жолмен баруµа болады. А қаласынан С қаласына В дан өтпейтiн 4 жол бар. А қаласынан С қаласына қанша әдiспен жетуге болады? Шешімі: Біз бұл есепте қосымша мән енгіземіз. A қаласынан B қаласына 3 жолмен баратындықтан біз оларды (x1,x2,x3) деп аламыз. Ал B қаласынан С қаласына 5 жолмен баратын болғандықтан біз оларды (y1, y2, y3, y4, y5) деп аламыз. A қаласынан C қаласына B дан өтпейтін 4 жол болғандықтан оларды z1, z2, z3, z4 деп белгілейміз. Шешуі: (x1,y1); (x1,y2); (x1,y3); (x1,y4); (x1,y5); (x2,y1); (x2,y2); (x2,y3); (x2,y4); (x2,y5); (x3,y1); (x3,y2); (x3,y3); (x3,y4); (x3,y5); z1; z2; z3; z4. Жауабы: 19 әдіспен баруға болады.

   
   

8. А – 30 дан үлкен емес, 3 ге бөлiнетiн натурал сандар жиыны. мәнін есептеңіз Жауабы: 3, 6, 9, 12, 15, 18, 21, 24, 27, 30

   
   

9. А – 15 тен үлкен емес, 3 ге бөлiнетiн натурал сандар жиыны. мәнін есептеңіз Жауабы: 3, 6, 9, 12, 15

   
   

10. А – 12 ден үлкен емес жұп натурал сандар жиыны. мәнін есептеңіз Жауабы: 2, 4, 6, 8, 10, 12

    
    

11. , . _{дәлелдеңіз,} табыңыз.

    
    

12. есептеңіз. Жауабы: 7*7*7=343

    
    

13. Айталық болсын. табыңыз. Жауабы: A мен В ның бірігуі: 1,2,3,4,5,6,7,8 B∩C={2,4} A\C={7} B дельта С: {1,3,5,6,8}

    
    
14. 
    
    _{формулаға пара-пар тек және амалдары көмегімен құрылған формуланы табыңыз.}
    

15. 1, 1, 2, 3, 3 цифрлардың көмегiмен қанша бес таңбалы сан жазуға болады? Бұл есепті n! формуласымен шығарамыз. Бұл жерде n деп отырғанымыз

    
    

Шешуі: 5!/2!*1!*2!=120/4=30 болады

теңдік дұрыс екеніне көз жеткізіңіз.

17. 3, 3, 3, 8, 8 цифрлардың көмегiмен қанша бес таңбалы сан жазуға болады?

    
    

18. «Математика» сөздiң әрiптерiн ауыстыра отырып қанша сөз алуға болады? Жауабы: Біз бұл есепте комбинаториканың орын ауыстыру формуласын пайдаланамыз. P(n1,n2,n3..nk)=n!/n1!n2!n3!...nk! Бұл жерде n деп отырғанымыз әріптердің жалпы саны. Ал n1 дегеніміз сөзде кездескен м әріпінің жалпы саны, n2 дегеніміз а әріпінің жалпы саны, т.с.с. Шешуі: P(2,3,1,1,1)=10!/(2!*3!*2!*1!*1!*1!)=604800/2*2!=302400/2=151200

    
    

19. Топта 25 студент оқиды, олардың ішінде 13 – ағылшын тілін, 12 – неміс, 13 – француз, 4 студент ағылшын және француз, 6 – ағылшын және неміс, 5 – неміс және француз тілдерін біледі. Қанша студент үш тілді біледі? (8 бал)

    
    
20. 
    
    _{тепе-теңдікті дәлелдеңіз.}
    

21. , . , , табыңыз. Жауабы: = {1,2,4,5,6,8,9,10} ={2,6}

    
    
22. 
    
    _{тепе-теңдікті дәлелдеңіз Жауабы:}
    

23. Айталық болсын.

    
    

табыңыз.

24. 
    
    _{формулаға пара-пар тек және амалдары көмегімен құрылған формуланы табыңыз.}
    

25. жиыны А = {1, 2, 3, 4, 5, 6} жиынындағы қатынасты анықтайды. Оған жататын барлық реттелген жұптарды табыңыз.

    
    

26. ДНФті табыңыз: (x~y)  ( zT ).

    
    

27. A(G) матрица берілген. Графты салыңыз.

    
    

;

28. Ақиқат кестесін құрыңыз:
    

Жауабы:

29. B(G) матрица берілген. Графты салыңыз. ;
    

30 . Ақиқат кестесін құрыңыз: