Многочлен Жегалкина. Диаграмма Эйлера-Венна. Свойства логической функции двух переменных
Алгоритм построения многочлена Жегалкина по совершенной дизъюнктивной нормальной форме. Диаграмма Эйлера-Венна, изображение универсального множества и подмножества. Проверка самодвойственности, монотонности и линейности логической функции двух переменных.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 20.04.2015 |
| Размер файла | 227,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Контрольная работа
Дисциплина: Дискретная математика
1. Многочлен Жегалкина. Нахождение многочлена Жегалкина по СДНФ (с обоснованием)
Полином Жегалкина - сумма по модулю 2, в которой каждое слагаемое представляет собой
· Константу
· отдельную переменную
· произведение нескольких переменных.
Алгоритм построения полинома Жегалкина по СДНФ (основан на доказательстве теоремы о существовании полинома Жегалкина).
Начало. Задана совершенная ДНФ функции f(x1, …, xn).
Шаг 1. Заменяем каждый символ дизъюнкции на символ суммы по модулю 2.
Шаг 2. Заменяем каждую переменную с инверсией x равносильной формулой x 1.
Шаг 3. Раскрываем скобки.
Шаг 4. Вычеркиваем из формулы пары одинаковых слагаемых.
Конец. Получен полином Жегалкина функции f(x1, …, xn).
Сумма по модулю два может быть выражена через дизъюнкцию, конъюнкцию и отрицание: ABAB, откуда A1=
многочлен жегалкин логический множество
2. Заданы универсальное множество U и три его подмножества A, B, C.
Проверить (доказать или опровергнуть) справедливость соотношения:
Решение:
Построим диаграмму Эйлера-Венна, изобразив универсальное множество прямоугольником, а подмножества кругами. Отметим на диаграмме штриховкой дополнение к пересечению A,B,C.
Теперь изобразим на диаграмме штриховкой дополнения к каждому из подмножеств:
Построим их объединение и получим:
Последняя диаграмм совпадает с диаграммой множества, поэтому, что и требовалось доказать.
3. Задано бинарное отношение
,
где .
Определить, выполняются ли для данного отношения свойства симметричности и рефлексивности. Ответ обосновать.
|
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)-четно.
4. Упростив логическую функцию двух переменных , проверить ее самодвойственность, монотонность и линейность. Ответ обосновать.
Решение:
Функция линейная, т.к. представима в виде линейного полинома Жегалкина:
Функция не монотонна, т.к. имеются наборы (10)<(11), при которых f(10)>f(11)
Функция самодвойственна, т.к. на всех наборах выполняется условие
5. На вершину горы ведут девять дорог. Сколькими различными способами можно подняться на гору и спуститься?
Решение:
По условию задачи, нас интересует выборка из 9 элементов 2 элементов, при которой выбираемые элементы возвращаются в исходное множество (можно возвращаться теми же дорогами), а порядок выбора элементов не важен:
Размещено на Allbest.ru
Подобные документы
Изучение булевых функций. Алгоритм представления булевых функций в виде полинома Жегалкина. Система функций множества. Алгебраические преобразования, метод неопределенных коэффициентов. Таблица истинности для определенного количества переменных.
курсовая работа [701,9 K], добавлен 27.04.2011Переключательные функции одного аргумента. Переключательные функции двух аргументов. Представление переключательной функции в виде многочленов. Совершенная дизъюнктивная нормальная форма переключательной функции. Функция в виде полинома Жегалкина.
реферат [45,6 K], добавлен 27.11.2008Множеством именуется некоторая совокупность элементов, объединенных по какому-либо признаку. Над множествами определяют операции, во многом сходные с арифметическими. Операции над множествами интерпретируют геометрически с помощью диаграмм Эйлера-Венна.
реферат [15,8 K], добавлен 03.02.2009Определение понятия множеств Г. Кантора, их примеры и обозначения. Способы задания, включение и равенство множеств, операции над ними: объединение, пересечения, разность, дополнение, их определение и наглядное представление на диаграмме Эйлера-Венна.
реферат [70,9 K], добавлен 11.03.2009Тождества, используемые для системы Жигалкина. Многочлен Жигалкина функции одной, двух и трех переменных. Содержание теоремы. Практический пример преобразования многочлена с помощью метода цепочки и неопределенных коэффициентов. Закон полного поглощения.
контрольная работа [95,5 K], добавлен 06.08.2013Доказательство тождества с помощью диаграмм Эйлера-Венна. Определение вида логической формулы с помощью таблицы истинности. Рисунок графа G (V, E) с множеством вершин V. Поиск матриц смежности и инцидентности. Определение множества вершин и ребер графа.
контрольная работа [463,0 K], добавлен 17.05.2015Изобретение Леонардом Эйлером геометрической схемы, с помощью которой можно изобразить отношения между подмножествами. Изучение частного случая кругов Эйлера — диаграммы Эйлера—Венна, изображающей все 2^n комбинаций n свойств (конечную булеву алгебру).
презентация [595,0 K], добавлен 16.02.2015Понятие функции нескольких переменных. Аргументы, частное значение и область применения функции. Рассмотрение функции двух и трех переменных. Предел функции нескольких переменных, теорема. Главная сущность непрерывности функции нескольких переменных.
реферат [86,3 K], добавлен 30.10.2010Определение точки экстремума для функции двух переменных. Аналог теоремы Ферма. Критические, стационарные точки. Теорема "Достаточное условие экстремума", доказательство. Схема исследования функции нескольких переменных на экстремум, практический пример.
презентация [126,2 K], добавлен 17.09.2013Понятия зависимой, независимой переменных, области определения функции. Примеры нахождения области функции. Примеры функций нескольких переменных: линейная, квадратическая, функция Кобба-Дугласа. Построение графика и линии уровня функции двух переменных.
презентация [104,8 K], добавлен 17.09.2013
