Изучение функций в курсе математики
Контрольная работа - Математика и статистика
Другие контрольные работы по предмету Математика и статистика
Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
Комсомольский-на-Амуре государственный
технический университет
Факультет компьютерных технологий
Кафедра Информационных систем
РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ
по дисциплине Дискретная математика
Студент группы 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:
№abcF1F20000011000010010110010201001100103011011001041000110000510101111116110100011171111111111
Столбцы, соответствующие F1 и F2, совпадают. Это значит, что аналитические преобразования исходной формулы верны.
Задание 4. Ниже приведена клауза
Необходимо выяснить при помощи алгоритма Вонга и метода резолюции является ли клауза теоремой.
Решение
Метод Вонга.
Построим дерево доказательства.
Все ветви дерева заканчиваются клаузами, в которых по обеим сторонам символа присутствует одна и та же буква. Следовательно, логическая теорема верна.
Метод резолюция.
Необходимо преобразовать клаузу таким образом, чтобы после знака получился ноль, при этом избавимся от импликации.
?
Выпишем по порядку все посылки и далее начнем их склеивать.
17(2;3)А28(1;5)39(7;4)410(9;6)B511(10;8)?6
Иначе, порядок склеивания можно представить в виде цепочки равносильных преобразований:
Задание 5. Заданы номера наборов аргументов, на которых булева функция принимает значение, равное единице. Необходимо:
- Записать булеву функцию в СДНФ и СКНФ;
- Минимизировать функцию с помощью минимизационной карты;
- Построить алгоритм Куайна.
- Выяснить к каким функционально-замкнутым классам принадлежит булева функция;
f (x1,x2,x3,x4)=1010010010110011
Решение
- Запишем СДНФ и СКНФ булевой функции.
СДНФ(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) (123 4) (123 4) (1
234) (1234)
- Строим минимизационную карту и пошагово выполняем алгоритм.
Шаг1.
№x1x2x3x4x1x2x1x3x1x4x2x3x2x4x3x4x1x2x3x1x2x4x1x3x4x2x3x4x1x2x3x4f00000000000000001100010010110111102001001010210222130011011113113330401001002202204405010110123123155160110110322322660701111113333337708100022200044408191001223011455190101010232102546210111101123311355731111211003222206644120131101323231675513014111033232276661411511113333337777151
Шаг 2. Вычеркиваем строки, в которых функция обращается в нуль.
Шаг 3. В каждом столбце из сохранившихся чисел вычеркиваем те, равные которым уже вычеркнуты в этом столбце на предыдущем шаге.
Шаг 4. В сохранившихся строках выбираем значения наименьших по числу множителей конъюнкций (включая и конъюнкции с одним множителем переменные) и обводим их.
Шаг 5. Если в одном столбце обведено несколько одинаковых чисел, то вычеркиваем все, кроме одного.
Результирующая таблица имеет вид:
№x1x2x3x4x1x2x1x3x1x4x2x3x2x4x3x4x1x2x3x1x2x4x1x3x4x2x3x4x1x2x3x4f00000000000000001100010010110111102001001010210222130011011113113330401001002202204405010110123123155160110110322322660701111113333337708100022200044408191001223011455190101010232102546210111101123311355731111211003222206644120131101323231675513014111033232276661411511113333337777151Шаг 6. Сокращенная ДНФ имеет вид
f = 24131234
Строим матрицу покрытий:
№Просты?/p>