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

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

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

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

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

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

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

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

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

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

по дисциплине «Дискретная математика»

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

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

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

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

Решение

Метод Вонга.

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

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

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

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

Ǿ

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

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

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

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

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

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

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

f (x₁,x₂,x₃,x₄)=1010010010110011

Решение

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

СДНФ(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}

₃

₄

_{1 2 3 4 1 2 3 4}

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

f = ( _{1 2 3 4) ( 1 2 3 4}) ( _{1 2 3 4}) ( ₁

_{2 3 4}) ( _{1 2 3 4}) ( _{1 2 3 4}) ( ₁

_{2 3 4}) ( _{1 2 3 4})

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

Шаг1.

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