Решение практических заданий по дискретной математике
Является ли полной система булевых функций ? Если система функций полная ,то выписать все возможные базисы.
Решение:
Рассмотрим функцию .
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 |
- |
- |
- |
- |
- |
В таблице в каждом столбце стоят минусы. Следовательно, система булевых функций
является полной .
Найдем все возможные базисы. По критериальной таблице составим КНФ :
.
Приведем КНФ к ДНФ :
.
По полученной ДНФ выписываем искомые базисы:
.