Контрольная работа: Многочлен Жегалкина. Диаграмма Эйлера-Венна. Свойства логической функции двух переменных
Контрольная работа
Дисциплина: Дискретная математика.
Дата добавления на сайт: 23 февраля 2025
Контрольная работа
Дисциплина: Дискретная математика
1.Многочлен Жегалкина. Нахождение многочлена Жегалкина по СДНФ (с обоснованием)
Полином Жегалкина - сумма по модулю 2, в которой каждое слагаемое представляет собой
·Константу
·отдельную переменную
·произведение нескольких переменных.
Алгоритм построения полинома Жегалкина по СДНФ (основан на доказательстве теоремы о существовании полинома Жегалкина).
Начало. Задана совершенная ДНФ функции f(x1, …, xn).
Шаг 1. Заменяем каждый символ дизъюнкции на символ суммы по модулю 2.
Шаг 2. Заменяем каждую переменную с инверсией x равносильной формулой x 1.
Шаг 3. Раскрываем скобки.
Шаг 4. Вычеркиваем из формулы пары одинаковых слагаемых.
Конец. Получен полином Жегалкина функции f(x1, …, xn).
Сумма по модулю два может быть выражена через дизъюнкцию, конъюнкцию и отрицание: AЪB=A
Е
B, откуда AЕ1= многочлен жегалкин логический множество
2. Заданы универсальное множество U и три его подмножества A, B, C.
Проверить (доказать или опровергнуть) справедливость соотношения:
Решение:
Построим диаграмму Эйлера-Венна, изобразив универсальное множество прямоугольником, а подмножества кругами. Отметим на диаграмме штриховкой дополнение к пересечению A,B,C.
Теперь изобразим на диаграмме штриховкой дополнения к каждому из подмножеств:
Построим их объединение и получим:
Последняя диаграмм совпадает с диаграммой множества
, поэтому, что и требовалось доказать.. Задано бинарное отношение
,
где .
Определить, выполняются ли для данного отношения свойства симметричности и рефлексивности. Ответ обосновать.
| 10 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 9 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 8 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 7 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 6 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 5 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 4 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 3 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 2 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Рефлексивность. Это отношение рефлексивно, т.к. для
А выполняется x+x четно.Симметричность. Это отношение симметричное на множестве А, т.к (x +y)-четно => (y+x)-четно.
. Упростив логическую функцию двух переменных , проверить ее самодвойственность, монотонность и линейность. Ответ обосновать.
Решение:
Функция линейная, т.к. представима в виде линейного полинома Жегалкина:
Функция не монотонна, т.к. имеются наборы (10)f(11)
Функция самодвойственна, т.к. на всех наборах выполняется условие
. На вершину горы ведут девять дорог. Сколькими различными способами можно подняться на гору и спуститься?
Решение:
По условию задачи, нас интересует выборка из 9 элементов 2 элементов, при которой выбираемые элементы возвращаются в исходное множество (можно возвращаться теми же дорогами), а порядок выбора элементов не важен:
