Булевы функции
Использование эквивалентных преобразований. Понятие основных замкнутых классов. Метод минимизирующих карт и метод Петрика. Операция неполного попарного склеивания. Полином Жегалкина и коэффициенты второй степени. Таблицы значений булевых функций.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 06.06.2011 |
| Размер файла | 90,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Контрольная работа по дисциплине «Дискретная математика»
Тема: «Булевы функции»
Задание
Даны булевы функции
Требуется:
1. Составить таблицы значений функций и .
2. Используя эквивалентные преобразования, привести к СДНФ и СКНФ
3. По таблице значений составить таблицу значений ; используя эти таблицы, указать для их СДНФ и СКНФ
4. Представить формулой в базисах
5. Представить полиномом Жегалкина
6. Найти для сокращенную ДНФ методом Квайна
7. Найти для все минимальные ДНФ
a. Методом минимизирующих карт
b. Методом Петрика
Изобразить соответствующие контактные схемы
8. Каким из пяти основных замкнутых классов принадлежит и почему?
Решение
1. Составить таблицы значений функций и .
|
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
|
|
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
|
|
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
|
|
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
|
0 |
0 |
0 |
1 |
0 |
0 |
1 |
|
|
0 |
0 |
1 |
0 |
1 |
0 |
0 |
|
|
0 |
1 |
0 |
0 |
1 |
0 |
0 |
|
|
0 |
1 |
1 |
1 |
0 |
0 |
1 |
|
|
1 |
0 |
0 |
1 |
1 |
1 |
0 |
|
|
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
1 |
1 |
0 |
0 |
0 |
1 |
0 |
|
|
1 |
1 |
1 |
1 |
1 |
0 |
0 |
2. Используя эквивалентные преобразования, привести к СДНФ и СКНФ
СДНФ:
СКНФ:
3. По таблице значений составить таблицу значений ; используя эти таблицы, указать для их СДНФ и СКНФ
функция класс коэффициент эквивалентный
|
0 |
0 |
0 |
1 |
0 |
0 |
1 |
|
|
0 |
0 |
1 |
0 |
1 |
0 |
0 |
|
|
0 |
1 |
0 |
0 |
1 |
0 |
0 |
|
|
0 |
1 |
1 |
1 |
0 |
0 |
1 |
|
|
1 |
0 |
0 |
1 |
1 |
1 |
0 |
|
|
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
1 |
1 |
0 |
0 |
0 |
1 |
0 |
|
|
1 |
1 |
1 |
1 |
1 |
0 |
0 |
СДНФ:
СКНФ:
|
0 |
0 |
0 |
1 |
|
|
0 |
0 |
1 |
1 |
|
|
0 |
1 |
0 |
0 |
|
|
0 |
1 |
1 |
1 |
|
|
1 |
0 |
0 |
0 |
|
|
1 |
0 |
1 |
1 |
|
|
1 |
1 |
0 |
1 |
|
|
1 |
1 |
1 |
0 |
СДНФ:
СКНФ:
4. Представить формулой в базисах
Базис :
Базис :
Базис :
Базис :
5. Представить полиномом Жегалкина
При
При
При
При
При
При
При
При
6. Найти для сокращенную ДНФ методом Квайна
К данным элементарным конъюнкциям невозможно применить операцию неполного попарного склеивания, т. Е. метод Квайна неприменим. Данная СДНФ является минимальной ДНФ.
7. Найти для все минимальные ДНФ
a. Методом минимизирующих карт
Данную СДНФ невозможно упростить с помощью минимизирующих карт, следовательно, она совпадает с минимальной ДНФ.
b. Методом Петрика
|
Х |
||||
|
Х |
||||
|
Х |
Данную СДНФ невозможно упростить с помощью метода Петрика, следовательно, она совпадает с минимальной ДНФ.
Изобразить соответствующие контактные схемы
8. Каким из пяти основных замкнутых классов принадлежит и почему?
, т. к. не сохраняет константу 0:
.
, т. к. не сохраняет константу 1:
.
, т. к. не сохраняет константу таблица истинности не совпадает с .
, т. к. в полиноме Жегалкина присутствуют коэффициенты второй степени.
, т. к. , что противоречит свойству монотонности.
Размещено на Allbest.ru
Подобные документы
Изучение булевых функций. Алгоритм представления булевых функций в виде полинома Жегалкина. Система функций множества. Алгебраические преобразования, метод неопределенных коэффициентов. Таблица истинности для определенного количества переменных.
курсовая работа [701,9 K], добавлен 27.04.2011Понятие, основные свойства элементарных булевых функций и соотношения между ними. Формулировка принципа двойственности. Совершенные дизъюнктивная и конъюнктивная нормальные формы. Многочлен (полином) Жегалкина. Суперпозиция и замыкание класса функций.
презентация [24,4 K], добавлен 05.02.2016Полнота и замкнутость системы булевых функций. Алгоритм построения таблицы истинности двойственной функции. Класс L линейных функций, сущность полинома Жегалкина. Распознавание монотонной функции по вектору ее значений. Доказательство теоремы Поста.
учебное пособие [1,3 M], добавлен 20.08.2014Логика - наука о законах и формах мышления, а основное понятие алгебры логики - высказывание. Основные понятия и тождества булевой алгебры. Изучение методов минимизации булевых функций. Метод Квайна, основанный на применении двух основных соотношений.
контрольная работа [178,2 K], добавлен 20.01.2011Свойства алгебры Жегалкина. Действия с логическими константами (нулём и единицей). Свойства элементарных булевых функций, задаваемых логическими операциями. Способы построения полиномов с помощью таблиц истинности (метод неопределенных коэффициентов).
курсовая работа [467,2 K], добавлен 28.11.2014Составление таблицы значений функции алгебры логики и нахождение всех существенных переменных. Связный ориентированный и взвешенный граф. Построение функции полиномом Жегалкина. Текст программы для алгоритма Дейкстры. Определение единиц и нулей функции.
контрольная работа [43,2 K], добавлен 27.04.2011Сокращенные, тупиковые дизъюнктивные нормальные формы. Полные системы булевых функций. Алгоритм Квайна, Мак-Класки минимизации булевой функции. Геометрическое представление логических функций. Геометрический метод минимизации булевых функций. Карты Карно.
курсовая работа [278,1 K], добавлен 21.02.2009Общая теоретическая часть. Графический метод. Функциональный метод. Метод функциональной подстановки. для построения графика некоторых функций составляют таблицу значений функции для некоторых значений аргумента, затем наносят соответствующие точки на пло
контрольная работа [54,3 K], добавлен 26.11.2004Решение дифференциальных уравнений. Численный метод для заданной последовательности аргументов. Метод Эйлера относиться к численным методам, дающим решение в виде таблицы приближенных значений искомой функции. Применение шаговых методов решения Коши.
дипломная работа [1,2 M], добавлен 16.12.2008Переключательные функции одного аргумента. Переключательные функции двух аргументов. Представление переключательной функции в виде многочленов. Совершенная дизъюнктивная нормальная форма переключательной функции. Функция в виде полинома Жегалкина.
реферат [45,6 K], добавлен 27.11.2008
