Является ли полной система булевых функций ? Если система функций полная ,то выписать все возможные базисы.
Решение:
Рассмотрим функцию .
1. Принадлежность функции к классу :
.
Следовательно, .
2. Принадлежность функции к классу :
.
Следовательно, .
3. Принадлежность функции к классу .
Предположим, что функция линейная и, следовательно, представима в виде полинома Жегалкина первой степени:
.
Найдем коэффициенты .
Фиксируем набор 000:
,
,
Следовательно, .
Фиксируем набор 100:
,
,
Следовательно, .
Фиксируем набор 010:
,
,
.
Следовательно, .
Фиксируем набор 001:
,
,
, .
Следовательно, функция (по нашему предположению) может быть представлена полиномом вида:
.
Если функция линейная, то на всех остальных наборах ее значение должно равняться 1. Но на наборе 111 . Значит, функция не является линейной, т.е. .
4. Принадлежность функции к классу .
Функция самодвойственная, если на любой паре противоположных наборов (наборов, сумма десятичных эквивалентов которых равна , где п - количество переменных функции) функция принимает противоположные значения.
Вычисляем . Вычисляем значения функции на оставшихся наборах:
Строим таблицу:
(000) 0 |
(001) 1 |
(010) 2 |
(011) 3 |
(100) 4 |
(101) 5 |
(110) 6 |
(111) 7 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
На наборах 1 и 6, 2 и 5, 3 и 4 функция принимает одинаковые значения. Следовательно, .
5. Принадлежность функции к классу .
Из таблицы видно: 000 < 111 , но . Следовательно, .
Рассмотрим функцию .
1. Принадлежность функции к классу :
.
Следовательно, .
2. Принадлежность функции к классу :
.
Следовательно, .
3. Принадлежность функции к классу .
Предполагаем, что
.
Фиксируем набор 000:
,
.
Фиксируем набор 100:
,
.
Фиксируем набор 010:
,
.
Фиксируем набор 001:
,
.
Окончательно получаем
.
Это равенство не соблюдается на наборе 011:
,
.
Следовательно, .
4. Принадлежность функции к классу .
Вычислим значения функции на оставшихся наборах:
Строим таблицу :
(000) 0 |
(001) 1 |
(010) 2 |
(011) 3 |
(100) 4 |
(101) 5 |
(110) 6 |
(111) 7 |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
Из таблицы видно, что на наборах 3 и 4 функция принимает одинаковые значения. Следовательно, .
5. Принадлежность функции к классу .
Из таблицы видно, что 111 > 000 , но . Следовательно, .
Строим критериальную таблицу:
К0 |
К1 |
КЛ |
КС |
КМ |
||
f1 |
- |
- |
- |
- |
- |
|
f2 |
- |
- |
- |
- |
- |
В таблице в каждом столбце стоят минусы. Следовательно, система булевых функций
является полной .
Найдем все возможные базисы. По критериальной таблице составим КНФ :
.
Приведем КНФ к ДНФ :
.
По полученной ДНФ выписываем искомые базисы:
.
- Введение
- Задание 1
- Представить с помощью кругов Эйлера множественное выражение
- Используя законы и свойства алгебры множеств, упростить заданное выражение.
- Задание 2
- Заданы множества кортежей:
- Показать, что эти множества представляют собой соответствия между множествами N1 и N2 , если N1 = N2 = . Дать полную характеристику этих соответствий
- Задание 3
- Частично упорядоченное множество М задано множеством упорядоченных пар
- Построить диаграмму и определить, является ли данное множество решеткой. Если заданное множество является решеткой, то определить, является ли решетка дедекиндовой , дистрибутивной.
- Задание 4
- Является ли полной система булевых функций ? Если система функций полная ,то выписать все возможные базисы.
- Задание 5
- Минимизировать булеву функцию по методу Квайна - Мак-Класки.
- Задание 6
- Для неориентированного графа , у которого ,
- а) вычислить числа ;
- б) определить хроматическое число .
- Задание 7
- Для заданной сети :
- а) найти величину минимального пути и сам путь от вершины до вершины по алгоритму Дейкстры ;
- Литература