Методичка по Дискретке

21

г) e(eX Z) (X Z)eY .

7.Найдите все самодвойственные булевы функции от двух аргументов. Сколько из них существенно зависят от всех своих аргументов?

8.Какие из следующих функций самодвойственны?

а) (eA BeA) DeA BeC;

б) f(x1, x2, ..., x2m+1) = x1 x2 ... x2m+1 δ, δ {0; 1}; в) (A B) (A C) (B C);

г) xz + (x + z)(y + 1).

9.Посчитайте число таких булевых функций от n аргументов, двойственные функции которых совпадают с их отрицанием.

10.Докажите, что всякая самодвойственная булева функция от n аргументов принимает одинаковое число раз (т.е. на одинаковом числе наборов значений аргументов) значения 0 и 1.

11.В произвольной несамодвойственной булевой функции так отождествите ее аргументы, чтобы получилась несамодвойственная функция от возможно меньшего числа аргументов. Каким может быть это число? Покажите, что всегда можно получить несамодвойственную функцию от двух аргументов. Дальнейшее уменьшение числа переменных, вообще говоря невозможно.

12.Какие из следующих функций монотонны?

а) A B + A C + B C + A; б) (01100111);

в) xyz + x + yz;

г) xyz (xyz + xy).

13.Найдите все монотонные булевы функции от трех аргументов.

14.Проверьте монотонность конъюнкции от n аргументов и монотонность дизъюнкции от n аргументов.

15.Выясните, при каких n следующие функции монотонны.

а) (ex1ex2 ...exn) (x1 x2 ... xn);

б) (x1 x2 ... xn−2exn−1exn) (x1 + x2 + ... + xn); в) (x1 x2 ... xn−1exn) (x1 + x2 + ... + xn).

16.Докажите, что среди всех булевых функций от n аргументов число функций, сохраняющих 0, но не сохраняющих 1, равно числу функций, сохраняющих 1, но не сохраняющих 0. Найдите это число.

17.Сколько существует линейных булевых функций от n аргументов, существенно зависящих от всех своих аргументов?

18.Какие из следующих функций линейны?

а) (A B) C;

б) (A (B C)) ((A B) (A C)); в) (10010101);

г) (x y z) xyez) (x + y)z.

19. Доказать полноту следующих систем функций сведением к заведомо полным системам:

а) {xy (x ez)}; б) {(0100); 1}.

20. С помощью теоремы Поста проверить на полноту следующие системы функций:

а) {A B; A eB C, 1};

б) {0; 1; A (B C)eA (B + C)};

22

в) {A B; eA};

г) {A B; eA eB; 1}; д) {y xz; 0; 1}.

7. Формальные теории. Логика предикатов. Задания для работы на занятии.

1. Доказать, построив вывод:

а) `e(A B) ((A C) (A eB)); б) ` (A (A eB)) (B eA);

в) `e(A eA) (ee(A eA) A); г) ` (A eA) (eeA e(A eA)); д) ` B ((A eB) e(B A)).

2. Зная множества P + и P + истинности предикатов P (x1, x2, ..., xn) и eP (x1, x2, ..., xn) соответственно, заданных над одними и теми же множествами, найдите множество истинности следующего предиката:

а) (P (x) eP (x)) P (x);

б) (P (x) (eP (x) P (x))) eP (x); в) (P (x) eP (x)) P (x);

г) (eP (x) P (x)) (eP (x) P (x)).

3.Выразите множества истинности следующих предикатов через множества истинности входящих в них элементарных предикатов:

а) (eP (x) Q(x)) (eP (x) Q(x));

б) e(P (x)eR(x))e(P (x) Q(x)) (P (x) Q(x));

в) ((P (x)eR(x))e(eQ(x) P (x))) (Q(x) P (x)); г) ((eP (x) Q(x)) (P (x)eQ(x)))e(P (x) Q(x)).

4.Каким условиям удовлетворяют множества истинности одноместных предикатов P (x) и Q(x), заданных на множестве M, если

а) конъюнкция их тождественно истинна; б) конъюнкция превращается в истинное высказывание при подстановке лю-

бого из элементов множества P + истинности предиката P (x) и только таких элементов;

в) дизъюнкция их тождественно ложна; г) импликация их тождественно истинна; д) эквиваленция их тождественно ложна;

е) эквиваленция превращается в истинное высказывание при подстановке любого из элементов множества P + истинности предиката P (x) и только таких элементов.

5.Пусть P (x) и Q(x) такие одноместные предикаты, заданные над одним

итем же множеством M, что высказывание

а) ( x)[Q(x) (P (x) (Q(x) P (x)))] истинно; докажите, что тогда истинно и высказывание ( x)(P (x) Q(x));

б) ( x)[P (x) (P (x) (Q(x)eP (x)))] истинно; докажите, что тогда истинно и высказывание ( x)(P (x) Q(x));

в) ( x)[P (x) ((P (x) (Q(x)) eP (x))] ложно; докажите, что тогда истинно высказывание ( x)(P (x) Q(x));

г) ( x)[eP (x) (P (x)e(eQ(x) P (x)))] ложно; докажите, что тогда истинно высказывание ( x)(Q(x)) и ложно высказывание ( x)(P (x)).

24

в) ( x)(P (x)) ( x)(P (x) Q(x)); г) ( x)(P (x) Q(x)) ( x)(P (x)); д) ( x)(P (y) P (x));

е) ( x)(P (x, x)) ( x)( y)(P (x, y));

ж) ( x)( y)(Q(x, y)) ( y)( x)(Q(x, y)); з) ( x)( y)( z)((P (x)eP (y)) Q(z)).

15.Являются ли тавтологиями следующие формулы логики предикатов? а) ( x)( y)(Q(x, y)) ( y)( x)(Q(x, y));

б) ( x)( y)(Q(x, y)) ( y)( x)(Q(x, y));

в) ( x)(P (x) Q(x)) [( x)(P (x)) ( x)(Q(x))]; г) ( x)( y)((P (x) P (y)) (eP (x)eP (y))).

16.Проанализируйте следующие рассуждения на предмет их правильности. Для этого выявите логические схемы, на которых они основаны, и выясните, справедливы ли они.

а) Все ромбы параллелограммы. Все прямоугольники параллелограммы. Следовательно все ромбы прямоугольники.

б) Некоторые четные функции периодические. Ни одна монотонная функция не является четной. Следовательно, ни одна монотонная функция не является периодической.

в) Некоторые математики суть логики. Все логики знакомы с произведениями Аристотеля. Следовательно, некоторые математики знакомы с произведениями Аристотеля.

г) Все хирурги врачи. Некоторые врачи Герои России. Следовательно, некоторые хирурги Герои России.

Задания для домашней работы.

1.Доказать, построив вывод:

а) ` ((B eA) eB) (B A); б) ` (B (B eA)) (eB eA); в) `e((A eB) eA) e(A B); г) `eA ((B A) e(eA B)).

2. Зная множества P + и P + истинности предикатов P (x1, x2, ..., xn) и eP (x1, x2, ..., xn) соответственно, заданных над одними и теми же множествами, найдите множество истинности следующего предиката:

а) (P (x)eP (x)) (P (x) eP (x)); б) eP (x) (P (x)eP (x));

в) (P (x) eP (x)) (eP (x) P (x)); г) (eP (x) P (x)) P (x).

3.Выразите множества истинности следующих предикатов через множества истинности входящих в них элементарных предикатов:

а) (P (x) Q(x)) (Q(x) R(x)) (Q(x) eR(x)); б) (eP (x) Q(x))e(P (x) eR(x)) (eP (x) eQ(x)); в) (Q(x) eR(x))e(eR(x) Q(x)) (eQ(x) R(x));

г) ((eR(x) eP (x)) (Q(x)eP (x))) (eQ(x)eP (x)) R(x).

4.Каким условиям удовлетворяют множества истинности одноместных предикатов P (x) и Q(x), заданных на множестве M, если

а) конъюнкция их тождественно ложна;

25

б) дизъюнкция превращается в истинное высказывание при подстановке любого из элементов множества P + истинности предиката P (x) и только таких элементов;

в) дизъюнкция их тождественно истинна; г) импликация их тождественно ложна; д) эквиваленция их тождественно истинна.

5.Пусть P (x) и Q(x) такие одноместные предикаты, заданные над одним

итем же множеством M, что высказывание

а) ( x)[P (x) (Q(x) P (x))] ложно; докажите, что тогда высказывание ( x)(P (x)) ложно, а ( x)(Q(x)) истинно;

б) ( x)[((P (x) Q(x)) eP (x)) P (x)] истинно; докажите, что тогда ложно высказывание ( x)(P (x) Q(x));

в) ( x)[P (x) (P (x)e(Q(x) eP (x)))] ложно; докажите, что тогда ложно и высказывание ( x)(P (x) Q(x));

г) ( x)[eP (x) (P (x) (Q(x) P (x)))] истинно; докажите, что тогда ложно высказывание ( x)(P (x) Q(x)).

6. Какими могут быть множества P + и Q+ истинности предикатов P (x) и Q(x) соответственно, заданных над непустым множеством M, если известно, что следующее высказывание истинно:

а) ( x)(P (x)eQ(x)) ( x)(P (x) Q(x)); б) e( x)(P (x) Q(x)) ( x)(P (x) Q(x)); в) ( x)(eP (x) Q(x)) e( x)(P (x) Q(x)); г) ( x)(eP (x) Q(x)) e( x)(P (x) Q(x)).

7. Какими могут быть множества P + и Q+ истинности предикатов P (x) и Q(x) соответственно, заданных над непустым множеством M, если известно, что следующее высказывание ложно:

а) ( x)(P (x) Q(x)) ( x)(P (x) Q(x)); б) ( x)(eP (x) Q(x)) ( x)(P (x) eQ(x)); в) ( x)(eP (x) Q(x))e( x)(P (x) eQ(x)); г) ( x)(P (x) Q(x)) ( x)(P (x) Q(x)).

8.Придайте следующим формулам указанные интерпретации и определите истинностные значения получающихся высказываний:

а) ( x)(P (x)) ( x)(Q(x)), M = N, P (x) : x < 5, Q(x) : x > 6; б) ( x)(eP (x)), M = N, P (x) : x < 2;

в) ( x)(P (x)) ( x)(Q(x)), M = N, P (x) : 3 делится на x, Q(x) : 2 делится на x;

г) ( x)(P (x)) P (y), M = {2, 3}, P (x) : 2 делится на x, y = 3.

9.Покажите, что каждая интерпретация каждой из следующих формул на одноэлементном множестве дает истинное высказывание:

а) ( x)(P (x)) P (y); б) P (x)eP (y);

в) P (x) (P (x) P (y)); г) P (y) ( x)(P (x)).

10.Покажите, что при интерпретации формул из предыдущей задачи на двухэлементном множестве не всегда получается истинное высказывание.

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

( x)(P (x) P (y))eP (y).

26

12. Определите, какие из следующих формул выполнимы, а какие нет (т.е. тождественно ложны):

а) ( x)(P (x)eP (x));

б) ( x)(P (x) Q(x)) (( x)(P (x)) ( x)(Q(x)));

в) ( x)( y)(P (x)eP (y)); г) ( x)( y)(P (x)eP (y)).

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

а) ( x)( y)( z)(F (x, y, z)) и ( z)( y)( x)(F (x, y, z)); б) ( x)(P (x) Q(y)) и ( x)(P (x)) Q(y);

в) ( x)(P (y) Q(x)) и P (y) ( x)(Q(x));

г) ( x)(P (x) Q(x)) и ( x)(P (x)) ( x)(Q(x)).

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

а) e( x)(P (x)) ( x)(eP (x));

б) ( x)(P (x)) ( x)(P (x) Q(x)); в) ( x)(P (x) Q(x)) ( x)(P (x)); г) ( x)(P (x) Q(x)) ( x)(P (x)); д) ( x)( y)(P (x, y)) ( x)(P (x, x));

е) ( x)( y)(Q(x, y)) ( y)( x)(Q(x, y)); ж) ( x)( z)(F (x, y)eF (z, y));

з) ( y)( x)(P (x, y)) ( x)( y)(P (x, y)).

15.Являются ли тавтологиями следующие формулы логики предикатов? а) ( x)(P (x) Q(x)) [( x)(P (x)) ( x)(Q(x))];

б) ( x)(P (x) Q(x)) [( x)(P (x)) ( x)(Q(x))]; в) ( x)(P (x) Q(x)) [( x)(P (x)) ( x)(Q(x))]; г) ( x)( y)(P (y) Q(x, y)).

16.Проанализируйте следующие рассуждения на предмет их правильности. Для этого выявите логические схемы, на которых они основаны, и выясните, справедливы ли они.

а) Некоторые четные функции периодические. Ни одна монотонная функция не является четной. Следовательно, ни одна периодическая функция не является монотонной.

б) Все квадраты правильные многоугольники. Ни одна трапеция не есть правильный многоугольник. Следовательно, ни одна трапеция не есть квадрат.

в) Все студенты БашГУ жители Уфы. Некоторые жители Уфы пенсионеры. Следовательно, некоторые студенты БашГУ пенсионеры.

г) Все пловцы спортсмены. Ни один спортсмен не курит. Следовательно, ни один курящий не является пловцом.