КР БИС 31з

Контрольная работа

Задача 1. Составив таблицы истинности, выяснить равносильны ли следующие булевы функции:

y¹) # (y _ z):

9) f(x; y; z) = ((x $ y¹) ! z) ! (x $ z¹); g(x; y; z) = (¹x $ y¹) ^(x _y) ^z: 10) f(x; y; z) = (x ! (y $ z)) $ ((x ! y) $ z); g(x; y; z) = (x !

y) ^ (z ^ x) ^ y:

Задача 2. Докажите, что следующие формулы являются тавтологиями:

1)(((p ^ q) ! r) ^ (¹r _ s¹)) ! (¹p _ q¹);

2)((p ! r) ^ (q ! s) ^ (¹r _ s¹)) ! (¹p _ q¹);

3)((p ! q) ^ (r ! s)) ^ (p _ r) ^ (q ^ s)) ! ((q ! p) ^ (s ! r))

4)((p ! q) ^ (r ! s) ^ (p _ r)) ! (q _ s);

5)(p ! q) ! ((r ! q¹) ! [((s ! p¹) ! ((t¹_ p) ! (t ! s)))])

6)(p ! q) ! ((q ! r) ! (p ! r));

7)(p ! q) ! ((p ! (q ! r)) ! (p ! r));

8)(p ! r) ! ((q ! r) ! ((p _ q) ! r));

9)(q ! r) ! ((p _ q) ! (p _ r));

10)(p ! q) ! ((p ! q¹) ! p¹):

Задача 3. Формулу f(x; y; z) из задачи 1 равносильными преобразованиями приведите сначала СДНФ, затем к СКНФ.

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

1)f(0; 0; 1; 1) = f(1; 0; 0; 1) = f(0; 1; 0; 0) = f(0; 0; 1; 0) = 1;

2)f(1; 0; 0; 0) = f(0; 1; 0; 0) = f(0; 0; 1; 0) = f(0; 0; 0; 1) = f(0; 1; 1; 0) = 1;

3)f(1; 1; 1; 0) = f(1; 1; 0; 1) = f(1; 0; 1; 1) = f(0; 1; 1; 1) = f(1; 0; 0; 1) = 1;

4)f(1; 1; 0; 0) = f(1; 0; 0; 1) = f(0; 0; 1; 1) = f(1; 0; 1; 0) = f(0; 1; 0; 1) = f(1; 1; 1; 1);

5)f(0; 0; 0; 0) = f(1; 0; 1; 1) = f(0; 0; 0; 1) = f(1; 0; 0; 0) = f(1; 1; 1; 1) = f(0; 1; 1; 0) = 1;

6)f(1; 0; 1; 1) = f(1; 0; 0; 0) = f(0; 1; 0; 0) = f(0; 0; 1; 0) = 1;

7)f(1; 0; 1; 1) = f(0; 1; 0; 1) = f(0; 0; 1; 1) = f(0; 1; 0; 1) = f(0; 1; 1; 0) = 1;

8)f(1; 1; 1; 1) = f(1; 0; 0; 1) = f(1; 0; 1; 1) = f(0; 1; 0; 1) = f(1; 0; 0; 1) = 1;

1

9)f(1; 1; 0; 1) = f(1; 0; 0; 1) = f(0; 0; 0; 1) = f(1; 0; 1; 0) = f(1; 1; 0; 1) = f(1; 1; 1; 1);

10)f(0; 0; 0; 0) = f(1; 0; 0; 1) = f(0; 0; 0; 1) = f(1; 0; 1; 0) = f(1; 1; 1; 1) = f(0; 1; 1; 0) = 1:

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

1)f(0; 0; 1; 1) = f(1; 0; 0; 1) = f(0; 1; 0; 0) = f(0; 0; 1; 0) = 0;

2)f(1; 0; 0; 0) = f(0; 1; 0; 0) = f(0; 0; 1; 0) = f(0; 0; 0; 1) = f(0; 1; 1; 0) = 0;

3)f(1; 1; 1; 0) = f(1; 1; 0; 1) = f(1; 0; 1; 1) = f(0; 1; 1; 1) = f(1; 0; 0; 1) = 0;

4)f(1; 1; 0; 0) = f(1; 0; 0; 1) = f(0; 0; 1; 1) = f(1; 0; 1; 0) = f(0; 1; 0; 1) = f(1; 1; 1; 1) = 0;

5)f(0; 0; 0; 0) = f(1; 0; 1; 1) = f(0; 0; 0; 1) = f(1; 0; 0; 0) = f(1; 1; 1; 1) = f(0; 1; 1; 0) = 0;

6)f(0; 1; 1; 1) = f(1; 0; 0; 0) = f(0; 1; 0; 1) = f(1; 0; 1; 0) = 0;

7)f(1; 0; 0; 0) = f(0; 1; 0; 0) = f(0; 0; 1; 0) = f(0; 0; 0; 1) = f(0; 1; 1; 0) = 0;

8)f(1; 1; 1; 1) = f(1; 0; 0; 1) = f(1; 0; 1; 0) = f(0; 1; 1; 1) = f(1; 0; 1; 1) = 0;

9)f(1; 1; 0; 0) = f(1; 1; 0; 1) = f(0; 0; 1; 1) = f(1; 1; 1; 0) = f(0; 1; 0; 1) = f(1; 1; 1; 1) = 0;

10)f(0; 0; 0; 0) = f(1; 0; 1; 1) = f(0; 0; 0; 1) = f(1; 0; 1; 0) = f(1; 1; 1; 1) = f(0; 1; 0; 0) = 0;

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

1)(F ! G) ! ((G ! H) ! (F ! H));

2)(F ! (G ! H)) ! (G ! (F ! H));

3)F ! (G ! (F ^ G));

4)(F ! (G ! H)) ! ((F ^ G) ! H);

5)((F ^ G) ! H) ! (F ! (G ! H));

6)F ! F ;

7)F ! (F ! G);

8)(G ! F ) ! (F ! G);

9)(F ! G) ! (G ! F );

10)F ! (G ! (F ! G)):

Теорема дедукции. F1; : : : Fm¡1; Fm ` G , F1; : : : Fm¡1 ` Fm ! G:

Пример решения задачи.

Доказать правило силлогизма F ! G; G ! H ` F ! H: Применив теорему дедукции, перейдем к эквивалентной формулировке F; F ! G; G ! H ` H и решим задачу в этой формулировке.

1.F; F ! G ` G по modus ponens (MP);

2.G; G ! H ` H по MP.

Другие примеры и производные правила вывода в И.А. Лавров, Л.Л. Максимова Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физматлит. 1973, 1995, 2002.

Задача 7. Доказать, что формулы являются теоремами исчисления предикатов:

1) (8x)(8y)B(x; y) $ (8y)(8x)B(x; y);

2

2)(9x)(9y)B(x; y) $ (9y)(9x)B(x; y);

3)(8x)(8y)B(x; y) ! (8x)B(x; x);

4)(9x)B(x; x) ! (9x)(9y)B(x; y);

5)(9x)B(x) $ (8x)B(x);

6)(8x)B(x) $ (9x)B(x);

7)(8x)B(x) ^ (8x)C(x) $ (8x)(B(x) ^ C(x));

8)(9x)B(x) ^ (9x)C(x) $ (9x)(B(x) ^ C(x));

9)A ^ (8x)B(x) $ (8x)(A ^ B(x));

10)A ^ (9x)B(x) $ (9x)(A ^ B(x)):

Задача 8. Выяснить, являются ли следующие формулы общезначимыми формулами алгебры предикатов:

1)(9x)(9y)(P (x; y)) ! (9x)(P (x; x));

2)(8x)(F (x) ! G(x)) ! ((8x)(F (x)) ! (8x)(G(x)));

3)((8x)(9y)(P (x; y)) ! (9y)(8x)(P (x; y)));

4)(8x)(F (x) ! G(x)) ! ((9x)(F (x)) ! (9x)(G(x)));

5)((9x)(P (x)) ^ (9x)(F (x)) ! (9x)(G(x)));

6)(9x)(8y)(Q(x; x) ^ Q(x; y));

7)(9x)(9y)(P (x) ^ P (y));

8)(9x)(9y)(Q(x; y) ! (8z)R(x; y; z));

9)P (x) ! (8y)(P (y));

10)(9x)P (x) ! (8x)P (x):

Задача 9. Машина Тьюринга с внешним алфавитом A = f¸; 1g и алфавитом внутренних состояний Q = fq0; q1; : : : ; q12; q13g определяется следующей функциональной схемой:

Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина каждое из следующих слов (в начальный момент времени машина находится в состоянии q1

3

и обозревает крайнюю правую ячейку, в которой записан пустой символ ¸;

вследующей слева ячейке уже записан символ 1):

1)¸1¸11¸; ¸111¸1¸; ¸11¸111¸11¸;

2)¸11¸111¸; ¸1111¸1¸; ¸1¸1¸1111¸;

3)¸1¸111¸; ¸1111¸11¸; ¸1¸11¸111¸;

4)¸111¸1111¸; ¸1¸1111¸; ¸111¸1¸11¸;

5)¸11¸1111¸; ¸111¸11¸; ¸11¸111¸1¸;

6)11¸11¸¸; 1¸111¸¸1; ¸111¸111;

7)1¸1¸1¸1¸; 11¸¸11¸¸; 111¸¸¸111;

8)1¸¸1¸11; 11¸11¸¸11; ¸1¸1¸11¸11;

9)¸111¸11¸11; ¸1¸1¸111; ¸¸1111¸11¸;

10)¸11¸111¸1; ¸¸11111¸; ¸11¸¸1111¸:

Задача 10. Применяя равносильные преобразования, преобразовать данные формулы к предваренной (пренексной) нормальной форме, т. е. к

форме вида (Q1x1) : : : (Qmxm)(F (x1; : : : xn)); где m · n; каждый Qi есть один из кванторов 8 или 9 и формула F (x1; x2; : : : ; xn) не содержит кван-

торов:

1)(8x)(P (x) ! Q(x)) ! [(9x)(P (x)) ! (9y)(Q(y))];

2)(8x)(P (x)) ! (8x)(Q(x));

3)(8x)(Q(x; y)) _ [(9x)(Q(x; x)) ! (8z)(R(t; z) ! (9x)(Q(x; x)))];

4)(8y)(Q(y; z)) ! (9x)(R(x; t; z));

5)(8y)(Q(x; y)) ! R(x; x);

6)P (y) ! [(8x)(Q(x; y)) ! P (y)];

7)(9x)(R(x; y; z)) ! (8x)(Q(x; y));

8)[(9x)(P (x)) _ (8x)(Q(x))] ^ [S(y) ! (8x)(R(x))];

9)(8x)(P (x; y)) _ [(9x)(P (x; x)) ! (8z)((Q(y; z) ! (9x)(P (x; z))))];

10)(P (y) ^ Q(x)) ! (8y)(R(y; z)):

Пример. Привести к пренексной нормальной форме. (9y)[P (x) ! Q(y)] ! (8y)[P (y)_

(8z)(Q(z))]:

Решение.

(9y)[P (x) ! Q(y)] ! (8y)[P (y) _ (8z)(Q(z))] =

=(9y)[P (x) ! Q(y)] ! (8t)[P (t) _ (8z)(Q(z))] =

=(8y)f[P (x) ! Q(y)] ! (8t)(8z)[P (t) _ Q(z)]g = = (8y)(8t)(8z)f[P (x) ! Q(y)] ! [P (t) _ Q(z)]g:

Задача 11.

Вариант 1. Орграф задан перечислением дуг: (1; 2); (1; 4); (2; 5); (2; 1); (3; 1); (3; 5); (4; 1); (4; 5); (5; 3): Для данного орграфа найти матрицу достижимости, решив систему уравнений в полукольце B .

Вариант 2. Орграф задан перечислением дуг: (1; 2); (1; 3); (2; 5); (2; 4); (3; 4); (2; 1); (3; 5); (5; 5): Для данного орграфа найти матрицу достижимости, решив систему уравнений в полукольце B .

Вариант 3. Орграф задан перечислением дуг: (1; 5); (2; 1); (2; 2); (2; 3); (2; 4); (3; 3); (3; 5); (4; 2); (4; 5); (5; 1): Для данного орграфа найти матрицу достижимости, решив систему уравнений в полукольце B .

4

рицу достижимости, решив систему уравнений в полукольце B .

Задача 12.

Вариант 1. На дугах орграфа из задачи 11 задана функция весов:

'(1; 2) = 6; '(1; 4) = 2; '(2; 5) = 6; '(2; 1) = 3; '(3; 1) = 5; '(3; 5) = 4; '(4; 1) = 1; '(4; 5) = 1; '(5; 3) = 1: Найти матрицу стоимостей для данного графа, решив систему уравнений в полукольце R .

Вариант 2. На дугах орграфа из задачи 11 задана функция весов:

'(1; 2) = 4; '(1; 3) = 2; '(2; 5) = 1; '(2; 4) = 2; '(3; 4) = 6; '(2; 1) = 4; '(3; 5) = 3; '(5; 5) = 1: Найти матрицу стоимостей для данного графа, решив систему уравнений в полукольце R .

Вариант 3. На дугах орграфа из задачи 11 задана функция весов:

'(1; 5) = 1; '(2; 1) = 1; '(2; 2) = 2; '(2; 3) = 1; '(2; 4) = 2; '(3; 3) = 3; '(3; 5) = 6; '(4; 2) = 4; '(4; 5) = 3; '(5; 1) = 3: Найти матрицу стоимостей для данного графа, решив систему уравнений в полукольце R .

Вариант 4. На дугах орграфа из задачи 11 задана функция весов:

'(1; 3) = 2; '(1; 4) = 4; '(2; 3) = 5; '(2; 4) = 1; '(2; 5) = 7; '(3; 5) = 1; '(4; 4) = 2; '(5; 1) = 5; '(5; 2) = 4: Найти матрицу стоимостей для данного графа, решив систему уравнений в полукольце R .

Вариант 5. На дугах орграфа из задачи 11 задана функция весов:

'(1; 2) = 1; '(1; 4) = 2; '(2; 5) = 6; '(2; 1) = 3; '(3; 1) = 5; '(3; 5) = 4; '(4; 1) = 1; '(4; 5) = 1; '(5; 3) = 1: Найти матрицу стоимостей для данного графа, решив систему уравнений в полукольце R .

Вариант 6. На дугах орграфа из задачи 11 задана функция весов:

'(1; 2) = 4; '(1; 4) = 2; '(2; 5) = 1; '(2; 4) = 2; '(3; 4) = 6; '(2; 3) = 4; '(3; 5) = 3; '(5; 5) = 1: Найти матрицу стоимостей для данного графа, решив систему уравнений в полукольце R .

5

Вариант 7. На дугах орграфа из задачи 11 задана функция весов:

'(1; 5) = 1; '(2; 1) = 1; '(2; 2) = 1; '(2; 3) = 1; '(2; 4) = 2; '(3; 3) = 3; '(3; 5) = 6; '(4; 3) = 4; '(4; 5) = 3; '(5; 1) = 3: Найти матрицу стоимостей для данного графа, решив систему уравнений в полукольце R .

Вариант 8. На дугах орграфа из задачи 11 задана функция весов:

ного графа, решив систему уравнений в полукольце R .

Вариант 9. На дугах орграфа из задачи 11 задана функция весов:

'(1; 5) = 1; '(2; 1) = 5; '(2; 2) = 2; '(2; 3) = 1; '(2; 4) = 2; '(3; 3) = 3; '(3; 5) = 6; '(4; 2) = 4; '(4; 5) = 3; '(5; 1) = 3: Найти матрицу стоимостей для данного графа, решив систему уравнений в полукольце R .

Вариант 10. На дугах орграфа из задачи 11 задана функция весов:

ного графа, решив систему уравнений в полукольце R .

Задача 13.

Вариант 1. Машина Тьюринга с внешним алфавитом A = f¸; 1g и алфавитом внутренних состояний Q = fq0; q1; : : : ; q12; q13g определяется следующей функциональной схемой:

Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина слово ¸111¸1111¸; (в начальный момент времени машина находится в состоянии q1 и обозревает крайнюю правую ячейку, в которой записан пустой символ ¸; в следующей слева ячейке уже записан символ 1).

Вариант 2. Машина Тьюринга с внешним алфавитом A = f¸; 1g и алфавитом внутренних состояний Q = fq0; q1; : : : ; q12; q13g определяется следующей функциональной схемой:

6

Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина слово ¸1¸111¸; (в начальный момент времени машина находится в состоянии q1 и обозревает крайнюю правую ячейку, в которой записан пустой символ ¸; в следующей слева ячейке уже записан символ 1).

Вариант 3. Машина Тьюринга с внешним алфавитом A = f¸; 1g и алфавитом внутренних состояний Q = fq0; q1; : : : ; q12; q13g определяется следующей функциональной схемой:

Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина слово ¸11¸111¸; (в начальный момент времени машина находится в состоянии q1 и обозревает крайнюю правую ячейку, в которой записан пустой символ ¸; в следующей слева ячейке уже записан символ 1).

7

Вариант 4. Машина Тьюринга с внешним алфавитом A = f¸; 1g и алфавитом внутренних состояний Q = fq0; q1; : : : ; q12; q13g определяется следующей функциональной схемой:

Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина ¸11¸11¸; слово (в начальный момент времени машина находится в состоянии q1 и обозревает крайнюю правую ячейку, в которой записан пустой символ ¸; в следующей слева ячейке уже записан символ 1).

Вариант 5. Машина Тьюринга с внешним алфавитом A = f¸; 1g и алфавитом внутренних состояний Q = fq0; q1; : : : ; q12; q13g определяется следующей функциональной схемой:

Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина слово

8

1¸111¸1111¸; (в начальный момент времени машина находится в состоянии q1 и обозревает крайнюю правую ячейку, в которой записан пустой символ ¸; в следующей слева ячейке уже записан символ 1).

Вариант 6. Машина Тьюринга с внешним алфавитом A = f¸; 1g и алфавитом внутренних состояний Q = fq0; q1; : : : ; q12; q13g определяется следующей функциональной схемой:

фавитом внутренних состояний Q = fq0; q1; : : : ; q12; q13g определяется следующей функциональной схемой:

9

Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина слово 1¸11¸1111¸; (в начальный момент времени машина находится в состоянии q1 и обозревает крайнюю правую ячейку, в которой записан пустой символ ¸; в следующей слева ячейке уже записан символ 1).

Вариант 8. Машина Тьюринга с внешним алфавитом A = f¸; 1g и алфавитом внутренних состояний Q = fq0; q1; : : : ; q12; q13g определяется следующей функциональной схемой:

Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина 11¸1¸11¸; слово (в начальный момент времени машина находится в состоянии q1 и обозревает крайнюю правую ячейку, в которой записан пустой символ ¸; в следующей слева ячейке уже записан символ 1).

Вариант 9. Машина Тьюринга с внешним алфавитом A = f¸; 1g и алфавитом внутренних состояний Q = fq0; q1; : : : ; q12; q13g определяется следующей функциональной схемой:

10