Примеры подсчета числа булевых функций
v Найти число булевых функций, входящих в объединение классов 
и 
: 
.
При решении данной задачи необходимо учесть, что функции по своим значениям при нулевых и единичных наборах аргументов бывают 4 типов:
| f(0, ..., 0) | 0 | 0 | 1 | 1 |
| f(1, ..., 1) | 0 | 1 | 0 | 1 |
Тогда по формуле включений-исключений получим:
v Найти число булевых функций, входящих в множество 
.
При решении задачи необходимо рассматривать самый малочисленный класс, участвующий в выражении, в данном случае – это класс L. Из 4-х типов линейных только 2 сохраняют константу 0, поэтому ответом будет половина от всех линейных.
.
v Найти число булевых функций, входящих в множество 
.
При решении задачи необходимо учесть, что самодвойственные функции по своим значениям при нулевых и единичных наборах аргументов бывают 2 типов:
| f(0, ..., 0) | 0 | 1 |
| f(1, ..., 1) | 1 | 0 |
.
v Найти число булевых функций, входящих в множество 
.
.
.
v Найти число булевых функций, входящих в множество 
.
.
Практические задания
Булевы функции: преобразования, двойственные,
Нормальные формы
Задание 1. Упростить следующие формулы.
а. 
;
б. 
;
в. 
;
г. 
;
д. 
;
е. 
.
Задание 2. Выяснить, является ли функция g двойственной к функции f (д, е – используя принцип двойственности).
а. 
; 
.
б. 
; 
.
в. 
; 
.
г. 
; 
.
д. 
; 
.
е. 
; 
.
Задание 3. Указать все фиктивные переменные у функции f:
|
|
|
а. 
.
б. 
.
в. 
.
г. 
.
д. 
.
е. 
.
Задание 4. Представить в СДНФ следующие функции:
а. 
.
б. 
.
в. .
г. 
.
Задание 5. Представить в СКНФ следующие функции:
а. 
.
б. 
.
в. 
.
г. 
.
Задание 6. Построить ДНФ функций:
а. 
.
б. 
.
в. 
.
г. 
.
Задание 7. Построить КНФ функций:
а. 
.
б. 
.
в. 
.
г. 
.
Полином Жегалкина, линейность, самодвойственность функций
Задание 1. Для следующих булевых функций найдите их полином Жегалкина:
а. 
.
б. 
.
в. 
.
г. 
.
д. 
.
е. 
.
Задание 2. Для следующих булевых функций найдите их полином Жегалкина: а, б методом неопределенных коэффициентов; в, г, д – методом треугольника Паскаля.
а. 
.
б. 
.
в. 
.
г. 
.
д. 
.
Задание 3. Докажите, что следующие булевы функции линейны:
а. 
.
б. 
.
в. 
.
г. 
.
д. 
.
Задание 4. Докажите, что в каждой паре одна из булевых функций двойственна другой:
а. 
, 
.
б. 
, 
.
в. 
, 
.
г. 
, 
.
д. 
, 
.
е. 
, 
.
Задание 5. Докажите, что следующие булевы функции самодвойственны:
а. 
.
б. 
.
в. 
.
г. 
.
д. 
.
е. 
.
Задание 6. Построить множество всех функций, зависящих от переменных x1, x2 и принадлежащих замыканию множества А:
а. 
.
б. 
.
в. 
.
г. 
.
д. 
.
е. 
.
Задание 7. Покажите, что 
, выразив 
формулой над множеством А:
а. 
.
б. 
.
в. 
.
г. 
.
д. 
.
|
|
|
е. 
.
Монотонность функций. Полнота систем булевых функций
Задание 1. Докажите монотонность следующих булевых функций:
а. 
.
б. 
.
в. 
.
г. 
.
д. 
.
е. 
.
Задание 2. Выясните, какие из следующих булевых функций монотонны:
а. 
.
б. 
.
в. 
.
г. 
.
д. 
.
е. 
.
Задание 3. Исследуйте на полноту следующие системы булевых функций:
а. 
.
б. 
.
в. 
.
г. 
.
д. 
.
е. 
.
Задание 4. Докажите, что следующие системы булевых функций являются базисами:
а. 
.
б. 
.
в. 
.
г. 
.
д. 
.
е. 
.
Задание 5. Из полной системы булевых функций выделите всевозможные базисы:
а. 
.
б. 
.
в. 
.
г. 
д. 
.
е. 
.
Дата добавления: 2021-02-10; просмотров: 2251; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!