2.5.3. Частично рекурсивные функции

Оператор минимизации ставит в соответствиеn+1-местной частичной функции n-местную частичную функцию так, что

и

или определены и не равны 0,

а

В этом случае введем обозначение:

Частичная функция называетсячастично рекурсивной (ЧРФ), если существует последовательность частичных функций , в которойи всякаяявляется либо базисной функцией, либо получается из предыдущих функций с помощью оператора суперпозиции, примитивной рекурсииили минимизации.

Пример 4. Нигде не определенная функция является ЧРФ:

.

Пример 5. Функция

является ЧРФ:

2. Задания для домашних и контрольных работ

3.1. Совершенные дизъюнктивные нормальные формы, совершенные конъюнктивные нормальные формы

Построить таблицы истинности для следующих формул алгебры высказываний и привести эти формулы к СДНФ и СКНФ.

1. (x∧¬y)→(y∧z);

2.(x→¬y)→(¬y∧z);

3.((x∧¬y)→x)→z;

4.(x∧¬(y→z)→x∨(y∧z);

5.z→(x∧¬y)∨(y∧z);

6.((x∨z)∧¬y)→¬(y→z);

7. ((x∧(z→¬y)→¬y)∨¬z);

8. ¬(x∧¬y)→z∨(y∧z);

9. (((x→y)→¬z)∨¬y)∧z;

x∧(z→y)→¬z∨¬y; ((x∨z)∧¬y)→¬(y→z);

(x→y)→¬z∨¬(y∧¬z);

x→¬(y→z)∧(z∨x);

¬((¬x∧z)→y)∨¬z;

(¬(x→y)∧z→¬z)∨¬y;

x∨¬(z→y)→¬(¬y∧z);

((x∧z→y)→¬z)∨¬z;

(x∧z →y)→¬z∨¬y;

(x→y∧¬z)∨¬y→z;

¬x→¬(y→z)∨(y∧z);

((x∨y)→¬z)→(¬y∧z);

(¬x→y)→¬(z∨y)∧z;

((¬(x→y)∧¬z)∨¬y)→z;

(¬z→y)→x∧(¬z∨¬y)∧z;

((x∧¬z)∨¬y)→z∧¬(x→y).

3.2. Логическое следствие в алгебре высказываний

Проверить истинность соотношений тремя способами (используя определение логического следствия и пп. 3,4 теоремы 2.

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. ;

21. ;

22. ;

23. ;

24. ;

25. .

3.3. Исчисление высказываний

Пусть -формулы исчисления высказываний.Построить вывод формулы исчисления высказываний из данного множества гипотез.

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. 

8. 

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. 

19. ;

20. ;

21. 

22. ;

23. ;

24. ;

25. ;

26. ;

27. ;

28. ;

29. .

4. Алгебраические системы.

Построить подсистему алгебраической системы , порожденную множеством (через обозначен булеан множестваB,т.е. множество всех подмножеств множестваB):

1. 

2. 

3. 

4. 

5. 

6. 

7. 

8. 

9. 

10. 

11. 

12. 

13. 

14. 

15. 

16. 

17. 

18. 

19. 

20. 

21. 

22. 

23. 

24. Ø,

25. 

26. Ø,

27. 

28. 

29. Ø,

4. Формулы логики предикатов

Выписать все подформулы данной формулы сигнатуры

и определить свободные и связанные переменные формулы:

1. 

2. 

3. 

4. 

5. 

6. 

7. 

8. 

9. 

10. 

11. 

12. 

13. 

14. 

15. 

16. 

17. 

18. 

19. 

20. 

Пусть - атомарные формулы логики предикатов. Выписать все подформулы данной формулы и определить свободные и связанные переменные формулы:

1. 

2. 

3. 

4. 

5. 

6. 

7. 

8. 

9. 

10. 

11. 

12. 

13. 

14. 

15. 

16. 

17. 

18. 

19. 

20. 

4. Истинность формулы логики предикатов

в алгебраической системе

Написать формулу Ф(х), истинную в алгебраической системетогда и только тогда, когда

1. х=1;

2. х=2ⁿ для некоторого натурального n;

3. х>4;

4. х– нечетное число;

5. х– простое число.

Написать формулу Ф(х,y),истинную в алгебраической системетогда и только тогда, когда

1. ;

2. ;

3. хделит;

4. ;

5. , гдеp- простое число.

Написать формулу Ф(х,y,z),истинную в алгебраической системетогда и только тогда, когда

1. xделится наyс остатком2;

2. x+3y>2z;

3. z– общий делительyиz;

4. z= НОК (x,y);

5. z= НОД (x,y).

Написать формулу Ф(х,y,z),истинную в алгебраической системетогда и только тогда, когда

1. x=0;

2. x=-1;

3. 2x-3y– четное число;

4. 3z=4x-5y;

5. z-2y делится на 3x.

Пусть – булеан множестваB,т.е. множество всех подмножеств множестваB.Написать формулуФ(х,y,z),истинную в алгебраической системетогда и только тогда, когда

1. есть пересечениеи;

2. есть объединениеи;

3. Ø;

4. ;

5. есть дополнение.

Пусть – булеан множестваB,т.е. множество всех подмножеств множестваB.Написать формулуФ(х,y,z),истинную в алгебраической системетогда и только тогда, когда

1. ;

2. Ø;

3. есть одноэлементное множество;

4. 

5. 

Написать формулу , такую что

1. 

2. 

3. 

4. 

5. 

6. 

7.