Изучение функций в курсе математики

Министерство образования и науки Российской Федерации

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

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

Высшего профессионального образования

“Комсомольский-на-Амуре государственный

Технический университет”

Факультет компьютерных технологий

Кафедра “Информационных систем”

РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ

По дисциплине “Дискретная математика”

Студент группы 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:

ABCF1F2
00000110000
10010110010
20100110010
30110110010
41000110000
51010111111
61101000111
71111111111

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

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

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

Решение

Метод Вонга.

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

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

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

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

Ǿ

Выпишем по порядку все посылки и далее начнем их “склеивать”.

17(2;3)А
28(1;5)
39(7;4)
410(9;6)B
511(10;8)Ǿ
6

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

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

– Записать булеву функцию в СДНФ и СКНФ;

– Минимизировать функцию с помощью минимизационной карты;

– Построить алгоритм Куайна.

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

F (x1 ,x2 ,x3 ,x4 )=1010010010110011

Решение

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

СДНФ(1):№ 0,2,5,8,10,11,14,15

F = 123412 3412341234

1234123412341234

СКНФ(0):№ 1,3,4,6,7,9,12,13

F = (1234) (1234 ) (1234 ) (1

234 ) (1234 ) (1234 ) (1

234 ) (1234 )

2. Строим минимизационную карту и пошагово выполняем алгоритм.

Шаг1.

X1X2X3X4X1 x2X1 x3X1 x4X2 x3X2 x4X3 x4X1 x2 x3X1 x2 x4X1 x3 x4X2 x3 x4X1 x2 x3 x4F
00000000000000001
10001001011011110
20010010102102221
30011011113113330
40100100220220440
50101101231231551
60110110322322660
70111111333333770
81000222000444081
91001223011455190
1010102321025462101
1110112331135573111
1211003222206644120
1311013232316755130
1411103323227666141
1511113333337777151

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

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

Шаг 4. В сохранившихся строках выбираем “значения” наименьших по числу множителей конъюнкций (включая и конъюнкции с одним множителем – переменные) и обводим их.

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

Результирующая таблица имеет вид:

X1X2X3X4X1 x2X1 x3X1 x4X2 x3X2 x4X3 x4X1 x2 x3X1 x2 x4X1 x3 x4X2 x3 x4X1 x2 x3 x4F
00000000000000001
10001001011011110
20010010102102221
30011011113113330
40100100220220440
50101101231231551
60110110322322660
70111111333333770
81000222000444081
91001223011455190
1010102321025462101
1110112331135573111
1211003222206644120
1311013232316755130
1411103323227666141
1511113333337777151

Шаг 6. Сокращенная ДНФ имеет вид

F = 24131234

Строим матрицу покрытий:

Простые импликантыКонституенты единицы функции f
X1X2X3X400000010010110001010101111101111
1001111
2111111
301011

Последовательно выбираем слагаемые 1,2,5

В результате получаем МДНФ:

F = 13241234

3. Построим алгоритм Куайна.

Построим таблицу значений функции

Х1Х2Х3Х4F
000001
100010
200101
300110
401000
501011
601100
701110
810001
910010
1010101
1110111
1211000
1311010
1411101
1511111

СДНФ (1): № 0, 2, 5, 8, 10, 11, 14, 15

1)

2)

3)

4)

5)

6)

7)

8)

СлагаемыеСклеивание по переменнойРезультат склеивания
1, 2X3
1, 4X1
2, 5X1
4, 5X3
4, 6Х4
5, 6Х4
5, 7Х2
6, 8Х2
7, 8Х4

С результатами таблицы повторим операцию склеивания.

1)

2)

3)

4)

5)

6)

7)

8)

9)

СлагаемыеСклеивание по переменнойРезультат склеивания
1, 4X1
2, 3X3
6, 9Х2
7, 8Х4

В итоге получим:

F = 13241234

4. Построим таблицу значений функции

Х1Х2Х3Х4F
000001
100010
200101
300110
401000
501011
601100
701110
810001
910010
1010101
1110111
1211000
1311010
1411101
1511111

1. f(0,0,0,0)≠0 0

2. f(1,1,1,1)=11

3. f(0,0,0,0)=f(1,1,1,1)≠0

4. Поскольку набор (1,1,1,1) больше любого другого набора и f(0,0,1,0)=1, f(0,0,1,1)=0, то

Для того чтобы выяснить, является ли функция линейной построим многочлен Жегалкина (с помощью треугольника Паскаля)

СлагаемоеХ1Х2Х3Х4FD Паскаля
100000F=1010010010110011
Х400010111011011101010
Х30010100110110011111
Х3 х4001110101101010000
Х201000111011111000
Х2 х40101100110000100
Х2 х3011000101000110
Х2 х3 х401111111100101
Х11000100010111
Х1 х4100110010100
Х1 х310100011110
Х1 х3 х41011011111
Х1 х2110010000
Х1 х2 х411010000
Х1 х2 х31110100
Х1 х2 х3 х4111100

Полином Жегалкина имеет вид:

1+x4 +x2 +x2 x3 x4 +x1 x3 x4, f

T0T1SLM
F+

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

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

Решение

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

P(x, y): “точка y принадлежит прямой x”

Q(x, y): “x // y”

Исходное выражение можно записать в виде следующей формулы:

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

Для приведения к предваренной нормальной форме необходимо вынести все кванторы в начало формулы (используя равносильности логики предикатов):

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

Решение

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

1. Зададим множество, на котором будем рассматривать все предикаты:М=R, где R – множество действительных чисел.

2. Каждой предикатной букве ставим в соответствие предикат:

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). В результате получили высказывание, которое можно записать:

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


1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading...
Изучение функций в курсе математики