Существуют много видов алгебр логики, в которых произвольная логическая функция представляется как суперпозиция некоторых базисных функций. Например, широко известной является булева система функций: конъюнкция (Ù), дизъюнкция (Ú) и отрицание (`). Эта система функций в качестве базиса была введена английским математиком Булем, с именем которого связано начало всей математической логики. Поэтому алгебра логики на основе этих операций называется алгеброй Буля или булевой алгеброй. Рассмотрим свойства булевыхопераций.
Свойства булевых операций
1. Аксиоматические свойства
х • х = х, x Ú x = x,
x •`x = 0, x Ú`x = 1, х • 0 = 0, x Ú 0 = x,
x • 1 = x, x Ú 1 = 1.
2. Свойства коммутативности
х1 Ú х2 = х2 Ú х1,
х1 • х2 = х2 • х1.
3. Свойства ассоциативности
(х1 Ú х2) Ú х3 = х1 Ú (х2 Ú х3),
(х1 • х2) • х3 = х1 • (х2 • х3).
4. Свойства дистрибутивности
(х1 Ú х2) • х3 = (х1 • х3) Ú (х2 • х3),
(х1 • х2) Ú х3 = (х1 Ú х3) • (х2 Ú х3).
5. Принцип двойственности (Закон де Моргана)
х1 • х2 = `х1 Ú`х2,
х1 Ú х2 = `х1 •`х2.
6. Закон двойного отрицания: х =`х.
В булевой алгебре любая логическая функция может быть представлена булевой формулой в виде совершенной дизъюнктивной формы (СДНФ). Причем, как будет показано ниже, представление произвольной логической функции в виде СДНФ является единственным.
2.2.2. Совершенные дизъюнктивная и конъюнктивная нормальные формы
Рассмотрим возможность представления произвольной функции в виде булевой формулы, содержащей только операции дизъюнкции, конъюнкции и отрицания.
Теоремы 1 и 2 доказывают возможность такого представления. Введем некоторые понятия.
Элементарной конъюнкцией(ЭК) называется выражение где все – различны, а r – ранг конъюнкции. Функция-константа единица (Ui = 1) считается конъюнкцией нулевого ранга.
Элементарной дизъюнкцией (ЭД) называется выражение где все – различны, а r – ранг дизъюнкции. Функция-константа единица (Ui = 0) считается дизъюнкцией нулевого ранга.
Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция N = U1 Ú U2 Ú ...Ú Uk элементарных конъюнкций U1, U2, ..., Uk. Совершенная ДНФ – частный случай ДНФ, элементарные конъюнкции которой содержат все переменные и ранг их равен n.
Конъюнктивной нормальной формой (КНФ) называется конъюнкция N = U1 Ù U2 Ù ...Ù Uk элементарных дизъюнкций U1, U2, ..., Uk. Совершенная КНФ – частный случай КНФ, элементарные дизъюнкции которой содержат все переменные и ранг их равен n.
Теорема 1.Произвольную логическую функцию f(х1, х2, ..., хn) можно представить в виде
(2)
где σi Î {0, 1}, xi0 =`хi, xi1 = xi, σ = (σ1, …, σn) и дизъюнкция берётся по всем n-мерным наборам из нулей и единиц.
Доказательство. Покажем, что левая и правая части соотношения (2) совпадают. Подставим в (2) произвольный набор α = (α1, …, αn), где каждое αi Î {0,1}. В левой части получим f(α1, α2, …, αn), а в правой части:
Равенства в правой части вытекают из свойств конъюнкции, дизъюнкции и из того, что: хσ = 1 Û х = σ.
Если f(х1, х2,..., хn) ≢ 0, то соотношение (2) можно переписать в форме:
(3)
Эта формула (3) называется совершенной дизъюнктивной нормальной формой (СДНФ) функции f(x1, х2,..., xn).
Следствие.Для произвольной логической функции существует взаимнооднозначное соответствие между ее СДНФ и таблицей истинности:
а) СДНФ содержит ровно столько элементарных конъюнкций, сколько единичных наборов у функции;
б) каждому единичному набору σ = (σ1, …, σn) соответствует элементарная конъюнкция всех переменных функции, в которой для σi = 0переменная хiберется с отрицанием и дляσi = 1–без отрицания.
Рассмотрим построение СДНФ по таблице истинности функции f(x1, х2, ..., xn). Для каждого набора σ = (σ1, …, σn) из единичного множества [1](такого, что f(σ1, …, σn) = 1), составляется выражение ЭК: . Затем эти конъюнкции соединяются знаком дизъюнкции.
Пример 1. Построим СДНФ для функции неэквивалентности f7(x1, х2)=(х1 Å х2). Исходя из единичного множества этой функции [1] = {(0, 1), (1, 0)} формула СДНФ будет иметь вид: FСДНФ = `х1 • х2 Ú х1•`х2.
Теорема 2. Произвольную логическую функцию f (х1, х2,..., хn) можно представить в виде:
(4)
где σi Î {0, 1}, хi0 = хi, xi1 = xi, σ = (σ1, …, σn)
и конъюнкция берётся по всем n-мерным наборам из нулей и единиц.
Доказательство. Из свойства булевой функции имеем f (х1, х2,..., хn) = (х1, х2, ..., хn). Для функции `f(х1, х2,..., хn) по теореме 1 существует представление в виде
тогда имеем:
что следует из закона де Моргана.
Заметим также, что . Следовательно,
Если f(х1, х2, ..., хn) ≢ 1, то соотношение (4) можно переписать в форме
(5)
Эта форма называется совершенной конъюнктивной нормальной формой (СКНФ).
Следствие.Для произвольной логической функции также существует взаимнооднозначное соответствие между ее СКНФ и таблицей истинности:
а) СКНФ содержит ровно столько элементарных дизъюнкций, сколько нулевых наборов у функции;
б) каждому нулевому набору σ = (σ1, …, σn) соответствует элементарная дизъюнкция всех переменных функции, в которой для σi = 1 переменная хi берется с отрицанием и для σi = 0 – без отрицания.
Рассмотрим построение СКНФ по таблице истинности функции f(x1, х2,..., xn). Для каждого набора σ = (σ1, …, σn) из нулевого множества [0] (такого, что f(σ1, …, σn) = 0), составляется выражение ЭД: . Затем эти дизъюнкции соединяются знаком конъюнкции.
Пример 2. Построим СКНФ для функции неэквивалентности f7(x1, х2) = (х1 Å х2). Исходя из нулевого множества этой функции [0] = {(0, 0), (1, 1)} формула СКНФ будет иметь вид: FСКНФ = (х1 Ú х2) • (`х1 Ú `х2).
х1 • х2 = `х1 Ú`х2,
х1 Ú х2 = `х1 •`х2.
где все 
– различны, а r – ранг конъюнкции. Функция-константа единица (Ui = 1) считается конъюнкцией нулевого ранга.
где все 
– различны, а r – ранг дизъюнкции. Функция-константа единица (Ui = 0) считается дизъюнкцией нулевого ранга.
(2)
Равенства в правой части вытекают из свойств конъюнкции, дизъюнкции и из того, что: хσ = 1 Û х = σ.
(3)
. Затем эти конъюнкции соединяются знаком дизъюнкции.
(4)
где σi Î {0, 1}, хi0 = хi, xi1 = xi, σ = (σ1, …, σn)
(х1, х2, ..., хn). Для функции `f(х1, х2,..., хn) по теореме 1 существует представление в виде
. Следовательно,
(5)
. Затем эти дизъюнкции соединяются знаком конъюнкции.