Многочлен Жегалкина. Диаграмма Эйлера-Венна. Свойства логической функции двух переменных

Многочлен Жегалкина. Диаграмма Эйлера-Венна. Свойства логической функции двух переменных

Контрольная работа

Дисциплина: Дискретная математика

1. Многочлен Жегалкина. Нахождение многочлена Жегалкина по СДНФ (с обоснованием)

Полином Жегалкина - сумма по модулю 2, в которой каждое слагаемое представляет собой

·  Константу

·        отдельную переменную

·        произведение нескольких переменных.

Алгоритм построения полинома Жегалкина по СДНФ (основан на доказательстве теоремы о существовании полинома Жегалкина).

Начало. Задана совершенная ДНФ функции f(x₁, …, x_n).

Шаг 1. Заменяем каждый символ дизъюнкции на символ суммы по модулю 2.

Шаг 2. Заменяем каждую переменную с инверсией x равносильной формулой x  1.

Шаг 3. Раскрываем скобки.

Шаг 4. Вычеркиваем из формулы пары одинаковых слагаемых.

Конец. Получен полином Жегалкина функции f(x₁, …, x_n).

Сумма по модулю два может быть выражена через дизъюнкцию, конъюнкцию и отрицание: AÚB=AÅB, откуда AÅ1=

многочлен жегалкин логический множество

2. Заданы универсальное множество U и три его подмножества A, B, C.

Проверить (доказать или опровергнуть) справедливость соотношения:

Решение:

Построим диаграмму Эйлера-Венна, изобразив универсальное множество прямоугольником, а подмножества кругами. Отметим на диаграмме штриховкой дополнение к пересечению A,B,C.

Теперь изобразим на диаграмме штриховкой дополнения к каждому из подмножеств:

Построим их объединение и получим:

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

. Задано бинарное отношение

,

где .

Определить, выполняются ли для данного отношения свойства симметричности и рефлексивности. Ответ обосновать.

Рефлексивность. Это отношение рефлексивно, т.к. для  А выполняется x+x четно.

Симметричность. Это отношение симметричное на множестве А, т.к (x +y)-четно => (y+x)-четно.

. Упростив логическую функцию двух переменных , проверить ее самодвойственность, монотонность и линейность. Ответ обосновать.

Решение:

Функция линейная, т.к. представима в виде линейного полинома Жегалкина:

Функция не монотонна, т.к. имеются наборы (10)<(11), при которых f(10)>f(11)

Функция самодвойственна, т.к. на всех наборах выполняется условие

. На вершину горы ведут девять дорог. Сколькими различными способами можно подняться на гору и спуститься?

Решение:

По условию задачи, нас интересует выборка из 9 элементов 2 элементов, при которой выбираемые элементы возвращаются в исходное множество (можно возвращаться теми же дорогами), а порядок выбора элементов не важен: