Ответы и указания

Глава 1. Высказывания, формулы, тавтологии. 2. 2), 5), 8), 10) – истинные высказывания. 1), 4), 7) – ложные высказывания. 3), 6) высказываниями не являются. 3. Обратите внимание, что 7) – составное высказывание. 5. Не являются тавтологиями: 2), 3), 5). Вернуться в Задачи.

Глава 3. Исчисление высказываний. 1. 1), 2), 5), 7), 8), 9) – формулы исчисления высказываний. 3), 4), 6), 10) формулами исчисления высказываний не являются. 2. 2). 3. 5) Применить лемму. 6), 7), 9) – применить результат 5). 8), 10), 11), 12) – применить результат 9). Вернуться в Задачи.

Глава 5. Предикаты. 1. 1). 3) . 5) . 7) . 8) . 9) . 10) . 2. 1), 3), 4), 6), 7), 9), 10). 1. 2), 5), 8). 0. 3. 7) Воспользоваться формулой .

4. 1).

2) . 3) .

4) . 5) .

6) . 7) .

8) .

9) .

10) . 8. Можно привести такой пример: , . Предикаты рассматриваются на множестве . Вернуться в Задачи.

Глава 8. Рекурсивные функции. 1. 1) . 2) .

3) 4) . 5) . 6) . 7) .

8) 9)

10) Вернуться в Задачи.

Глава 9. Машины Тьюринга. 1. 1) . 2) . 3) . 4) . 5) . 6) . 7) . 8) . 9) .

11) . 2. 1) а) ; б) . 2) а) Неприменима;

Б) . 3) а); б) Неприменима. 4) а) ; б) Неприменима. 5) а) Неприменима; б) . 6. 1) а) ; б) . 2) а) ;

Б) . 3) а) ; б) . 7. 1) а) ; б) . 2) а); б) . Вернуться в Задачи.

< Предыдущая