Содержание домашнего задания

Задача 2. Дана булева функция . Исследовать ее принадлежность каждому из классов

Алгоритм решения задачи о принадлежности функции классам :

- построить таблицу истинности функции ;

- если значение функции в первой строке таблицы равно 0 , то иначе

- если значение функции в последней строке таблицы равно 1 , то иначе

- если в таблице истинности можно указать пару противоположных наборов на которых функция принимает одинаковые значения то иначе ;

- если в таблице истинности можно указать наборы и такие, что и то иначе

- для проверки принадлежности функции классу нужно построить ее полином Жегалкина; если степень ПЖ не превосходит 1

то иначе

Задача 3. Дана система булевых функций . Исследовать полноту этой системы функций и, если она полна, выделить из нее базис.

Алгоритм исследования полноты системы булевых функций:

- построить таблицу, число строк в которой равно числу функций в , а число столбцов равно 5 по числу основных замкнутых классов (см. стр.);

- проверить принадлежность функции классу и поставить на пересечении соответствующих и строки и столбца знак " ", если , и знак "-", если ;

- если на предыдущем шаге в результате исследования получен знак " ", то продолжить исследование по "вертикали"- проверить принадлежность функции классу и т.д. если же на предыдущем шаге получен знак "-", то продолжить исследование по горизонтали - проверить принадлежность функции классу и т.д.;

-- исследование заканчивается, если выполнено одно из двух условий: 1) в каждом столбце таблицы стоит по крайней мере один знак "-", либо 2) в одном из столбцов таблицы стоят только знаки " ".

В первом случае система функций целиком не содержится ни в одном из классов и, согласно критерию Поста, является полной, во втором случае она целиком содержится в одном из классов и потому не является полной.

Для выделения базиса из полной системы функций нужно упорядочить по числу функций множество подсистем системы :