4
правки
Изменения
→Примеры
* <tex>\left\{\land,\lor,\neg\right\}</tex> (конъюнкция, дизъюнкция, отрицание);
* <tex>\left\{\land,\oplus,1\right\}</tex> (конъюнкция, сложение по модулю два, константа один).
Первая система используется, например, для представления функций в виде [[СДНФ|дизъюнктивных]] и [[СКНФ|конъюнктивных нормальных форм]], вторая — для представления в виде [[Полином Жегалкина|полиномов Жегалкина]]. Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты системы.
Максимально возможное число булевых функций в базисе — четыре.
Иногда говорят о системе функций, полной в некотором замкнутом классе, и , соответственно , о базисе этого класса. Например, систему <tex>\left\{\oplus,1\right\}</tex> можно назвать базисом класса линейных функций.
== Источники ==
