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

2. Записать рассуждение в логической символике и проверить правильность рассуждения методом Куайна, методом редукции и методом резолюций.

9. Если у меня хватит времени прочитать книгу, то я пойду погулять или встречусь с друзьями. С друзьями я встречаюсь во время прогулки. Значит, я встречусь с друзьями.

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

4. Построить машину Тьюринга для перевода из начальной конфигурации в заключительную. На ленте МТ записаны нули и единицы, пустые ячейки содержат нули, .  Проверить работу машины Тьюринга для конкретных значений x,y. Нарисовать граф, соответствующий построенной МТ.

5. Показать примитивную рекурсивность функции :