Доказать полноту (неполноту) систем булевых функций

Класс функций F называется полным, если его замыкание совпадает с P_n:

.

Другими словами, множество функций F образует полную систему, если любая функция реализуема в виде формулы над F.

4.2 {|}

Система {|} – полная, т. к.

5. Получить СДНФ для формул, а затем перейти к СКНФ:

5.4.

- ДНФ (дизъюнктивная нормальная форма) – дизъюнкция элементов, каждый из которых представляет собой конъюнкцию отдельных различных логических переменных либо со знаком отрицания, либо без него.

СДНФ (совершенная ДНФ) – это такая ДНФ, в которой каждая элементарная конъюнкция содержит все элементарные высказывания, либо их отрицания по одному разу, элементарные конъюнкции не повторяются.

Построим СДНФ для формулы по таблице истинности:

x	y	z	xy

Выделим все наборы переменных, для которых функция принимает значение 1 и каждому набору поставить в соответствие конъюнкцию переменных и их отрицаний. Рассматриваемая функция будет представлена дизъюнкцией этих конъюнкций.

Переход к СКНФ:

СКНФ (совершенная КНФ) – это такая КНФ (конъюнкция элементов, каждый из которых представляет собой дизъюнкцию логических переменных со знаком отрицания или без него), в которой каждая элементарная дизъюнкция содержит все элементарные высказывания, либо их отрицания по одному разу, элементарные дизъюнкции не повторяются.