Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
«Комсомольский-на-Амуре государственный
технический университет»
Факультет компьютерных технологий
Кафедра «Информационных систем»
РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ
по дисциплине «Дискретная математика»
Студент группы 9-ПИ Шикер С.А.
2010
Задача 1. Представьте заштрихованные области диаграммы Эйлера-Венна (рис.1) максимально компактным аналитическим выражением, в котором используется минимальное количество операций и букв.
/>
рис.1
Решение
На рис.2 изображена диаграмма Эйлера-Венна, заштрихованные области которой соответствуют выражению: C∩D. На рис.3 изображена диаграмма Эйлера-Венна, заштрихованные области которой соответствуют выражению: C/B. На рис.4 изображена диаграмма Эйлера-Венна, заштрихованные области которой соответствуют выражению: C∩А.
/>/>/>Рис. 2 Рис. 3 Рис.4
Чтобы получить необходимое множество (рис. 1) необходимо между этими тремя выражениями поставить операцию объединение. В результате получаем:
(C∩D)È(C/B)È(C∩A)
Задание 2. Записать высказывание в виде формулы логики высказываний, используя пропозициональные (логические) переменные для обозначения элементарных высказываний, т.е. таких, которые уже не могут быть построены из каких – либо других высказываний:
Неверно, что если Сидоров — не кассир, то Сидоров убил кассира; следовательно, фамилия кассира – Сидоров.
Решение
Введем обозначения:
a – «Сидоров – кассир»
b – «Сидоров убил кассира»
Исходное высказывание содержит связку «если …, то …», которая соответствует импликации, а так же связку «Неверно, что…» и предлог «не», что соответствует отрицанию. Формула имеет вид:
/>→ a
Задание 3. Используя равносильности логики высказываний, упростить исходную формулу
/>
Для исходной формулы и упрощенной построить таблицу истинности.
Решение.
/>/>
Введем обозначения: F1 = />
F2 = />
Построим таблицу истинности для F1 и F2:
№
a
b
c
/>
/>
/>
/>
F1
/>
F2
1
1
1
1
1
1
1
2
1
1
1
1
3
1
1
1
1
1
4
1
1--PAGE_BREAK----PAGE_BREAK--
(1;5)/>
3
/>
9
(7;4)/>
4
/>
10
(9;6)B
5
/>
11
(10;8)Ǿ
6
/>
Иначе, порядок «склеивания» можно представить в виде цепочки равносильных преобразований:
/>
Задание 5. Заданы номера наборов аргументов, на которых булева функция принимает значение, равное единице. Необходимо:
Записать булеву функцию в СДНФ и СКНФ;
Минимизировать функцию с помощью минимизационной карты;
Построить алгоритм Куайна.
Выяснить к каким функционально-замкнутым классам принадлежит булева функция;
f (x1,x2,x3,x4)=1010010010110011
Решение
Запишем СДНФ и СКНФ булевой функции.
СДНФ(1):№ 0,2,5,8,10,11,14,15
f= />1/>2/>3/>4/>1/>2 />3/>4/>1/>2/>3/>4/>1/>2/>3/>4/>
/>1/>2/>3/>4/>1/>2/>3/>4/>1/>2/>3/>4/>1/>2/>3/>4 продолжение
--PAGE_BREAK--
СКНФ(0):№ 1,3,4,6,7,9,12,13
f = (/>1/>2/>3/>4) (/>1/>2/>3/>4) (/>1/>2/>3/>4) (/>1/>
/>2/>3/>4) (/>1/>2/>3/>4) (/>1/>2/>3/>4) (/>1/>
/>2/>3/>4) (/>1/>2/>3/>4)
Строим минимизационную карту и пошагово выполняем алгоритм.
Шаг1.
№
x1 продолжение
--PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK--
х2
/>
7, 8
х4
/>
С результатами таблицы повторим операцию склеивания.
1)/>
2)/>
3) />
4)/>
5)/>
6)/>
7)/>
8)/>
9)/>
Слагаемые
Склеивание по переменной
Результат склеивания
1, 4
x1
/>
2, 3
x3
/>
6, 9
х2
/>
7, 8
х4
/>
В итоге получим:
f = />1/>3/>2/>4/>1/>2/>3/>4
4. Построим таблицу значений функции
х1
х2
х3
х4
f
1
1
1
2
1
1
3
1
1
4
1
5
1
1
1
6
1
1
7
1
1
1
8
1
1
9
1
1
10
1
1
1
11
1
1
1
1
12
1
1
13
1
1
1
14
1
1
1
1
15
1
1
1
1
1
f(0,0,0,0)≠0 />
f(1,1,1,1)=1/>1
f(0,0,0,0)=f(1,1,1,1)≠0 />
Поскольку набор (1,1,1,1) больше любого другого набора и f(0,0,1,0)=1, f(0,0,1,1)=0, то />
Для того чтобы выяснить, является ли функция линейной построим многочлен Жегалкина (с помощью треугольника Паскаля) продолжение
--PAGE_BREAK--
слагаемое
х1
х2
х3
х4
f
D Паскаля
1
f=1010010010110011
х4
1
111011011101010
х3
1
1
00110110011111
х3 х4
1
1
1
0101101010000
х2
1
111011111000
х2 х4
1
1
1
00110000100
х2 х3
1
1
0101000110
х2 х3 х4
1
1
1
1
111100101
х1
1
1
00010111
х1 х4
1
1
1
0010100
х1 х3
1
1
011110
х1 х3 х4
1
1
1
11111
х1 х2
1
1
1
0000
х1 х2 х4
1
1
1
000
х1 х2 х3
1
1
1
1
00
х1 х2 х3 х4
1
1
1
1
Полином Жегалкина имеет вид:
1+x4+x2+x2x3x4+x1x3x4, f/>
T0
T1
S
L
M
f
-
+
-
-
-
Задание 6. Разбить высказывание на элементарные и записать в виде кванторной формулы логики предикатов, используя наименьшее возможное число предикатов наименьшей местности
Через всякую точку, не лежащую на прямой, можно провести не более одной прямой, параллельной данной.
Решение
1. Введем обозначения:
P(x, y): «точка y принадлежит прямой x»
Q(x, y): «x // y»
Исходное выражение можно записать в виде следующей формулы:
/>/>
2. Сначала приведем формулу к приведенной нормальной форме, т. е. избавимся от знака импликации, используя равносильности логики высказываний и логики предикатов:
/>
Для приведения к предваренной нормальной форме необходимо вынести все кванторы в начало формулы (используя равносильности логики предикатов):
/>
Задание 7. Построить интерпретацию формулы логики предикатов:
/>
Решение
Данная формула является открытой (первое вхождение переменной у не связано квантором) и формула содержит нульместный предикат (S). Значит, интерпретация будет состоять из четырех шагов.
Зададим множество, на котором будем рассматривать все предикаты: М=R, где R – множество действительных чисел.
Каждой предикатной букве ставим в соответствие предикат:
P(x, y): “x> y”; R(x,y,z): “xy=z”, S(z): “z=1”;
При данной интерпретации высказывание /> является ложным (читается: для любых действительных чисел x и y, x>y), /> — истинное высказывание (читается: существуют такие действительные числа x,y,z, что xy=z), /> — истинное высказывание (читается: существует такое действительное число z, что z=1). В результате получили высказывание, которое можно записать:
/>
Значит, данная интерпретация обращает формулу логики предикатов в истинное высказывание.