Булевы Функции Функциональная полнота

  • Просмотров 930
  • Скачиваний 32
  • Размер файла 24
    Кб

Булевы Функции: Функциональная полнота. В алгебре булевых функций P2=<P2;S> S – Операцией является подстановка функции в функцию, суперпозиция. Порождающее множество алгебры P2, принято называть полной системой булевых функций. Система булевых функций является независимой, если не одной функцией этой системой нельзя выразить через остальные. Система функций полна, если через неё можно выразить любую булеву функцию. Примеры

полных систем: Любую булеву функцию можно представить в нормальной форме используя только операции +,*,not. {&, v, not}. Конъюнкцию с помощью законов Деморгана можно выразить через остальные элементы системы: X&Y=not (not(X) v not(Y)) – поэтому система {v, not}. Аналогично по другому закону Деморгана можно получить v через &, not поэтому (&, not). Импликация выражается через Дизъюнкцию и Отрицание: X v Y = not(X)  Y, следовательно {, not} также полная.

Через сложение (по модулю 2), умножение и 1 можно выразить основные логические операции: X&Y=X*Y X v Y=X+Y+XY Not(X)=X+1 X  Y=X+Y+1 Поэтому {+,*,1} система полна, и каждую булеву функцию в виде многочлена от Н переменных, который в честь автора Полином И.И. Жегалкина. Представление функции в форме Полинома Жегалкина. Следовательно, можно говорить о линейных булевых функциях, то есть функции вида f(X1,…,Xn)=A1X1+…+AnXn+B, обозначим буквой L множество всех

линейных функций данного вида. Система булевых функций полна, если через нее можно выразить какую-нибудь полную систему. Не пустое, собственное подмножество множество P2, замкнутое относительно суперпозиции образует под-алгебру. F,g1,…,gn€H=>f(g1,g2,…,gn)€H, H<P2 Под-алгебра задается нетривиальным функцией, сохраняющимся при суперпозиции. Любая подсистема, целиком лежащая в некоторой под алгеброй, неполна. Примеры под алгебр:

Множество линейных функций L образует под алгебру. L – замкнутая относительно суперпозиции. Любое множество линейных функций не образует полную систему: линейные функции порождают снова линейные функции. Поэтому, например система {0,1,+, not, } не полна. Функция f сохраняет ноль если f(0,…,0). Множество C0 всех таких функций образует под алгебру. Любое множество функций целиком лежащее в С0 не образует полную систему. Например {&, v, +,