Loading AI tools
Линейная булева функция — булева функция, полином Жегалкина которой имеет первую степень.[1] Более развёрнуто булева функция называется линейной, если она выражается в виде:
Примеры линейных булевых функций: тождественный , тождественная , тождественная функция, отрицание, исключающее или, эквиваленция. Конъюнкция и дизъюнкция линейными не являются.
Количество линейных функций переменных равно . Переменная линейной функции существенна тогда и только тогда, когда .
Линейные функции допускают также двойственное определение. Булева функция является линейной тогда и только тогда, когда её кополином Жегалкина имеет первую степень. Линейные функции легко переводятся между представлениями в виде полинома и кополинома при помощи следующих свойств:
Множество всех линейных булевых функций образует замкнутый класс, предполный в . Таким образом, класс линейных функций является одним из пяти предполных классов булевой логики.
Функция является линейной тогда и только тогда, когда значения функции на любых двух соседних по существенной переменной наборах отличаются. У любой линейной функции равное количество нулей и единиц.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
