4. Некрасова М.Г. Дискретная математика часть 1

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

1)Пусть неверно, что если Джон – коммунист, то Джон – атеист; тогда Джон – коммунист или атеист, либо не является ни тем, ни другим.

2)Или Сэм пойдёт на вечеринку, и Макс не пойдёт на неё; или Сэм не пойдёт на вечеринку, и Макс отлично проведёт время.

3)Неверно, что ни Петров, ни Сидоров не выдержали экзамен.

4)Неверно, что если Иванов или Петров сдали экзамен, то и Сидоров его сдал.

5)Неверно, что ветер дует тогда и только тогда, когда нет дождя и светит солнце.

6)Джо получит приз в том и только в том случае, если он умён или если Джим глуп.

7)Неверно, что если Сидоров не кассир, то Сидоров убил кассира; следовательно, фамилия кассира – Сидоров.

8)Неверно, что и Петров, и Иванов не выдержали экзамена; значит, хотя бы один из них сдал экзамен.

9)Если завтра я получу стипендию или займу деньги у товарища и если магазин будет открыт, то я завтра куплю фотоаппарат нужной модели, если он будет в продаже.

10)Когда погода плохая, то или падает настроение, или портится самочувствие, и в обоих случаях не хочется работать.

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

1)(( A B) A) (C ( A C)) .

2)((A B) (A C)) (A B) .

3)( A B) (( A C) B) .

4)((A B) (B C)) (A C) .

5)(( A B) C) ( A C) .

6)((A B) B) ((A C) B).

7)(( A B) C) ( A ( A C)) .

8)(B C) ((A B) C) .

9)( A B) (( A B) C) .

10)( A B) (( A C) (B C)) .

121

Задание 4. Ниже приведена клауза. Необходимо выяснить при помощи алгоритма Вонга и метода резолюций, является ли клауза теоремой.

1)А В,C D, B E, D F, E F, A C A.

2)X Y, X A,Y B A B.

3)X Y,Y Z, X A,Z B A B.

4)A B, A B, B C D , A D A C.

5)D B, D B,C D, D C,C B A A.

6)P Q, R S, S Q T ,T P R.

7)B D, B A, A B, A B C D C.

8)C, D C, A B D , B C A.

9)C B A , B D,C A D.

10)A C B , D A,C D B.

Задание 5. В табл. 3.1 заданы номера наборов аргументов, на которых булева функция принимает значение, равное единице. Необходимо:

а) записать булеву функцию в СДНФ, СКНФ; б) минимизировать функцию с помощью минимизационной карты;

в) выяснить, к каким функционально-замкнутым классам принадлежит булева функция.

Задание 6. Разбить высказывание на элементарные и записать в виде кванторной формулы логики предикатов, используя наименьшее возможное число предикатов наименьшей местности. Привести формулу к предваренной нормальной форме.

1)Сумма любых двух чисел, имеющих различную четность, есть число нечетное.

2)Через три любые точки, не лежащие на одной прямой, проходит единственная плоскость.

122

3)Функция не имеет точек разрыва тогда и только тогда, когда функция непрерывна в любой точке области определения.

4)Через две различные точки проходит единственная прямая.

5)Два произвольных числа равны, если каждое из них делится на

другое.

6)Функция возрастает на интервале, если в каждой точке этого интервала её первая производная положительна.

7)Через всякую точку, не лежащую на прямой, можно провести не более одной прямой, параллельной данной.

8)Для любых двух различных действительных чисел найдется число, расположенное между ними.

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

10)Функция дифференцируема на множестве, если она дифференцируема во всех точках этого множества.

Задание 7. Построить интерпретацию формулы логики предикатов.

1)x yP x, y y xP x, y .

2)x yP x, y xQ x y zR y, z .

3)x zP x, z y zR y, z y zS y, z .

4)x zP x, z x yR x, y zQ z .

5)x y zP x, y, z yQ y x zS x, z .

6)x yP x, y Q x R y .

7)x yP x, y x y zR x, y, z zS z .

8)x yP x, y y zR y, z zQ z .

9)yP y x yR x, y zS z .

10)xP x, y y zR y, z zS y, z .

123

3.3.Пример выполнения расчетно-графического задания (Часть 1)

Задание 1. Представьте заштрихованные области диаграммы Эйлера-Венна (рис. 3.2) максимально компактным аналитическим выражением, в котором используется минимальное количество операций и букв.

Решение.

Рис. 3.2 На рис. 3.3 изображена диаграмма ЭйлераВенна, заштрихованные области которой соответствуют выражению A C D. На рис. 3.4 изображена диаграмма Эйлера-

Венна, заштрихованные области которой соответствуют выражению

(D C) B.

Чтобы получить необходимое множество (см. рис. 3.2), необходимо вычесть из первого аналитического выражения второе. В результате полу-

чаем (A C D) \ ((D C) B).

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

«Прядильный станок остановится, если оборвется нить хотя бы на одном из трех веретен».

Решение.

Введем обозначения:

а – «прядильный станок остановился»;

b – «нить оборвалась на первом веретене»; с – «нить оборвалась на втором веретене»; d – «нить оборвалась на третьем веретене».

Исходное высказывание содержит связку «если …, то …», которая соответствует импликации. Формула имеет вид

(b c d) a. 124

Задание 3. Используя равносильности логики высказываний, упростить исходную формулу

a c a b c a .

Для исходной формулы и упрощенной построить таблицу истинности.

Решение.

ac a b c a a c a b c a

a c a b c a a b c a

a c b a c a a b a c

a c b a c a b c a a b c c a b c

a b c c a c b.

Столбцы, соответствующие F1 и F2, совпадают. Это значит, что аналитические преобразования исходной формулы верны.

Задание 4. Ниже приведена клауза

A B C , A B, B A, B D C D.

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

Решение.

Метод Вонга.

Построим дерево доказательства (рис. 3.5).

Все ветви дерева заканчиваются клаузами, в которых по обеим сторонам символа присутствует одна и та же буква. Следовательно, логическая теорема верна.

125

Метод резолюций.

Необходимо преобразовать клаузу

A B C , A B, B A, B D C D .

таким образом, чтобы после знака получился ноль, при этом избавимся от импликации:

A B C, A B, B A, B D,С, D .

Выпишем по порядку все посылки и далее начнем их «склеивать»:

6)D

Иначе, порядок «склеивания» можно представить в виде цепочки равносильных преобразований:

(A B C) (A B) (B A) (B D) С D

(A B C) ((A B) (B A)) ((B D) D) С

(A B C) A B D С ((A B C) A) B D С

((B A) (A C)) B D С (((B A) (A C)) С) B D

((A B C) (A C C)) B D A B C B D .

Задание 5. Заданы номера наборов аргументов, на которых булева функция принимает значение, равное единице. Необходимо:

а) записать булеву функцию в СДНФ, СКНФ; б) минимизировать функцию с помощью минимизационной карты;

в) выяснить, к каким функционально-замкнутым классам принадлежит булева функция.

Дана функция f(x1, x2, x3, x4) = 0011010111001010.

Решение.

а) Запишем СДНФ и СКНФ булевой функции.

СДНФ (1): № 2, 3, 5, 7, 8, 9, 12, 14:

f x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4.

127

СКНФ (0): № 0, 1, 4, 6, 10, 11, 13, 15:

fx1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4

x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4 .

б) Построим минимизационную карту (табл. 3.3) и пошагово выполним алгоритм.

Шаг 1.

Таблица 3.3

Шаг 2. Вычеркиваем строки, в которых функция обращается в ноль. Шаг 3. В каждом столбце из сохранившихся чисел вычеркиваем те,

равные которым уже вычеркнуты в этом столбце на предыдущем шаге. Шаг 4. В сохранившихся строках выбираем «значения» наименьших

по числу множителей конъюнкций (включая и конъюнкции с одним множителем – переменные) и обводим их.

Шаг 5. Если в одном столбце обведено несколько одинаковых чисел, то вычеркиваем все, кроме одного.

Результирующая таблица имеет следующий вид (табл. 3.4). Шаг 6. Сокращенная ДНФ имеет вид

f x1 x2 x3 x1 x2 x3 x1 x2 x4 x1 x2 x4 x1 x3 x4 x1 x3 x4 .

128

Таблица 3.4

Строим матрицу покрытий (табл. 3.5).

Таблица 3.5

Последовательно выбираем слагаемые 1, 2, 3, 4. В результате получаем МДНФ

f x1 x2 x3 x1 x2 x3 x1 x2 x4 x1 x2 x4 .

129