Логические (булевы) функции основные логические функции

Пример 5.1. Пусть задана функция:

Видно, ее СДНФ содержит (по числу 1) 6 дизъюнктных слагаемых, но ее сокращенная ДНФ содержит (после объединения единиц) всего 2 буквы
f = x₁x₂
Пример 5.2. Следующий пример показывает, “как соединять единицы по кругу”.

Здесь сокращенная ДНФ содержит 2 слагаемых (СДНФ содержала бы 5):

Пример 5.3. Пример показывает использование карт Карно при п = 4.

Здесь сокращенная ДНФ содержит 4 слагаемых (СДНФ содержит 8):
При п = 5 использование карт Карно является несколько более сложным и здесь не приводится.

6. Полиномы Жегалкина

Полиномом (многочленом) Жегалкина от п переменных называется функция
P =__x__x₂ + ..._nx_n +_n +1x_x₂ +...+_{n +C}²_nx_n-1x_n + ...+_2n-1x_x₂..xn
Всего здесь 2^п слагаемых. Напомним, что + сейчас означает сложение по модулю 2, коэффициенты _, __ⁿ_-1 являются константами (равными нулю или единице).
Теорема. Любая функция п переменных может быть представлена полиномом Жегалкина и это представление единственно.
Доказательство. Любая функция f(x₁, x₂, …, x_n) имеет свою таблицу истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределенными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент. Так как число наборов равно числу коэффициентов (и равно 2^п), отсюда следует утверждение теоремы.
Доказательство этой теоремы показывает, как по таблице истинности построить полином Жегалкина.
Имеется 2-й способ нахождения полинома Жегалкина для функций, заданных в виде ДНФ. Этот способ основан на том, что х+1 =  . Если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя при этом правило де Моргана, а все отрицания заменяем прибавлением единицы. После этого раскрываем скобки по обычным правилам, при этом учитываем, что четное число одинаковых слагаемых равно нулю (так как х+ х = 0), а нечетное число одинаковых слагаемых равно одному такому слагаемому.
Пример.
( xy + 1)((x + 1)(y + 1) + 1)((y + 1)z + 1) + 1 = (xy + 1)(xy + x + y)(yz + z + 1) + 1 = (x + y)(yz + z + 1) + 1= xyz + yz + xz +yz + x + y + 1 = xyz + xz + x +y + 1.
Последнее выражение и есть полином Жегалкина данной функции.
Функция f (x₁,x₂,…,x_n) называется линейной, если ее полином Жегалкина содержит только первые степени слагаемых. Более точно функция называется линейной, если ее можно представить в виде
f(x₁, x₂, …, x_n) = a₀ + a₁ x₁ + a₂ x₂ +…+ a_n x_n.
Класс линейных функций часто обозначают через L. (Заметим, что число линейных функций п переменных равно 2^п+1).