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

4. Представление логических функций 
в виде СДНФ (СКНФ)
Будем использовать логическую функцию “эквивалентность”, записанную в виде х^у. Напомним, что 0⁰= 1; 0¹=0; 1⁰= 0; 1¹= 1.Таким образом, х^у = 1 тогда и только тогда, когда х = у.
Лемма. Любая логическая функция f(x₁, x₂, …, x_n) может быть представлена в виде дизъюнкции 2^п дизъюнктных слагаемых, причем дизъюнкция берется по всевозможным наборам из Eⁿ.Этот факт будем записывать следующим образом:
(*)
где дизъюнкция проводится по всевозможным наборам (s₁, s₂, …, s_п) из Е^п.
Доказательство леммы.
а) Пусть f(x₁, x₂, …, x_n)= 1. Тогда слева в формуле (* ) стоит 1. Докажем, что и справа в этом случае стоит 1, для чего достаточно указать одно дизъюнктное слагаемое, равное 1. Но среди всех наборов (s₁, s₂, …, s_п) имеется набор s₁ = х₁, s₂ = х₂, …, s_п = х_п. Очевидно, что для этого набора слагаемое равно 1 (так как и .
б) Пусть f(x₁, x₂, …, x_n) = 0. Предположим, что справа стоит не ноль, а единица, тогда какое-то слагаемое тоже должно равняться 1, т. е. для некоторого набора

Это означает (по свойствам конъюнкции), что , откуда следует, что х₁=₁, х₂=_,…, х_п=_n, но в этом случае  f ( ₁, __n) f(x_1,x₂, …,x_n) = 0 и, значит, справа нет слагаемого, равного 1, т. е. в этом случае и справа и слева в формуле (* ) стоит 0. Лемма доказана.