П_7

Федеральное государственное бюджетное образовательное учреждение

высшего образования

«Саратовский государственный технический университет имени Гагарина Ю.А.»

Кафедра «Информационно-коммуникационные системы и программная инженерия»

Контрольная работа по дисциплине

«Математическая логика и теория алгоритмов»

Тема: «Основы математической логики»

Вариант № 2

Саратов 2023

Вариант 2

Задача 1. Составить таблицы истинности для следующих формул и указать, какие из формул являются выполнимыми, какие опровержимыми, какие тождественно истинными (тавтологиями), а какие тождественно ложными (противоречиями):

1. Y=

P	Q							Y
0	0	1	1	1	0	0	0	0
0	1	0	1	1	0	1	1	0
1	0	1	0	0	0	1	0	0
1	1	0	0	1	1	1	1	1

Формула в некоторых случаях принимает 1, а в некоторых 0, значит, формула является выполнимой

Задача 2. Используя СДНФ, найдите формулу, принимающую значение 0 только на следующих наборах значений переменных:

1. F(1,0,0)=F(1,1,1)=1;

x	y	z	F
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	1	x1¬x2¬x3
1	0	1	0
1	1	0	0
1	1	1	1	x1x2x3

Ответ : СДНФ

Задача 3. На множестве вещественных чисел R найти множества истинности предикатов и , где

и Тогда    множество точек, расположенных не ниже прямой

   и не ниже прямой   то есть пересечение множеств истинности предикатов P и Q. 

Сначала построим график из двух уравнений и определим область определения неравенств. P выше прямой    , Q выше прямой . Определим четыре области, образовавшиеся пересечением прямых.

Тогда,

Задача 4. Пусть дана программа машины Тьюринга:

Допустим, на ленте есть слово: 11100. Что будет напечатано на ленте после выполнения программы, если вначале работы каретка находится над крайним левым символом (1)?

	1	0	2	a0
q0
q1	1q1	2q1		0q2
q2	1q0	2 q2		q0

1.(1, q1) сдвиг вправо (1, q1)

2.(1, q1〉сдвиг вправо (1, q1)

3.(1, q) сдвиг вправо (1, q1) 4.(0, q1)сдвиг вправо (2, q)

5.(0, q1) сдвиг вправо (2, q1)

6.(λ, q1) →〈0, q2〉

7.(0, q2) сдвиг вправо (2, q2)

8.(λ, q2)→(a0, !)(достигнуто терминальное состояние) Получившиеся слово: 111222

Задача 5. Для следующих формул логики предикатов найти равносильные им формулы, в которых из логических связок имеются только операции , а знаки отрицания стоят только перед предикатными символами:

=

=

Ответ:

Задача 6. Проверить, верны ли следующие следствия:

Предположим, что высказывание не верно, то три первые три высказывания истинны, а последнее ложно

1. 

2. 

3. 

4. 

• Каждый столбец соответствуют решение из столбца высказывания находим из 4 высказывания находим значения

• Теперь найденные значения подставляем в третье выражение.

1	2	3	4

Из-за недостающих данных строим таблицу

Переходим к таблице;

случай	F	L
1	0	1	1
2	1	0	1
3	1	1	1

_{Рассмотрим случай 1;} F=0, L=1

_Тогда,

о
			F=0, L=1

_{Проверка}

_{Противоречий нет.}

_{Рассмотрим случай 2;} F=1, L=0

о		L=0 тогда
			F=1,L=0

_{Проверка}

_{Противоречий нет.}

_{Рассмотрим случай 3;} F=1, L=1

о		L=1 тогда

_{Проверка}

_{Противоречий нет.}

_{Вывод: получилось, что при всех F, L все посылки истинны, а заключение ложно.}