Булевые функции

Лекция №10 См. Пособие «Алгебра логики», с. 27−39, §§ 2.1−2.2. Глава II. Булевы функции 2.1. Понятие булевой функции В главе I отмечалось, что семантически формулы алгебры логики полностью описываются таблицами истинности. Следовательно, можно отвлечься от синтаксической структуры формул и рассматривать только их таблицы истинности, которые представляют собой не что иное как табличное задание различных функциональных зависимостей. В связи с этим естественно ввести в алгебре логики понятие функции, принимающей значения 0 или 1, аргументы которой также принимают значения 0 или 1. Дадим строгое определение этого понятия. При этом элементы множества {0, 1} рассматриваются как формальные символы, допускающие логическую интерпретацию, но не имеющие арифметического смысла. Определение 2.1.1. Произвольное отображение n-й степени множества {0, 1} во множество {0, 1} называется булевой функцией n переменных. Таким образом, f (x1, x2, …, xn) – булева функция n переменных, если f: {0, 1}n → {0, 1}. Булевы функции также называют логическими, переключательными функциями или функциями алгебры логики. Рассмотрим различные способы задания булевых функций. Всякую булеву функцию f (x1, x2, …, xn) можно задать таблицей истинности (табл. 2.1.1), в левой части которой перечислены в лексикографическом порядке все возможные наборы значений переменных, а в правой части – соответствующие значения функции. x1 x2 … xn−1 xn … 0 … 0 1 … … … … … … Таблица 2.1.1 f (x1, x2, …, xn) f (0,0, …, 0, 0) f (0,0, …, 0, 1) 1 1 1 1 … … 1 1 1 f (1,1, …, 1, 0) f (1,1, …, 1, 1) Если булева функция f и формула F алгебры логики имеют одну и ту же таблицу истинности, то будем говорить, что формула F представляет или реализует функцию f. Таким образом, формула F алгебры логики, представляющая булеву функцию f, может служить способом задания этой функции. Следует отметить, что задание булевой функции представляющей ее формулой алгебры логики неоднозначно. Действительно, любые две равносильные формулы алгебры логики имеют одинаковые таблицы истинности, а значит, представляют одну и ту же булеву функцию. Еще одним способом задания булевой функции является перечисление всех наборов значений переменных, на которых она принимает значение 0, либо перечислением всех наборов значений переменных, на которых она принимает значение 1. Пример 2.1.1. Для булевой функции f (x1, x2, x3) даны наборы значений переменных x1, x2, x3, на которых функция принимает значение нуль, остальные значения функции f равны единице: f (1, 0, 0) = f (1, 0, 1) = f (1, 1, 1) = 0.  Определение 2.1.2. Кортеж всех возможных значений булевой функции f (x1, x2, …, xn), упорядоченный в соответствии с лексикографическим порядком на множестве наборов значений переменных x1, x2, …, xn, называется вектором значений функции f. Указание значений булевой функции также является одним из способов ее задания. Пример 2.1.2. Вектором значений булевой функции f (x1, x2, x3) из примера 2.1.1 является кортеж (1111 0010).  Определим, сколько существует различных булевых функций n переменных. Теорема 2.1.1 (о числе булевых функций n переменных). Число различных булевых 𝑛 функций n переменных равно 22 . Доказательство. Чтобы задать булеву функцию f (x1, x2, …, xn) n переменных, нужно перечислить все возможные наборы значений переменных x1, x2, …, xn, составленных из нулей и единиц, и для каждого такого набора указать значение функции, которое она принимает на этом наборе. Таким образом, сначала требуется определить число всех возможных наборов значений переменных x1, x2, …, xn. Эти наборы представляют собой кортежи длины n с элементами из множества {0, 1}, причем элементы в кортежах могут повторяться. Другими словами, набор значений переменных x1, x2, …, xn – это размещение с повторением из двух элементов по n. Следовательно, число всех возможных наборов значений переменных x1, x2, …, xn равно числу 𝐴𝑛̅2 всех размещений с повторением из двух элементов по n. Известно, что число 𝐴𝑘̅𝑚 всех размещений с повторениями из m элементов по k равно mk. Отсюда 𝐴𝑛̅2 = 2n. Получили, что для задания булевой функции f (x1, x2, …, xn) n переменных нужно указать ее значение (0 или 1) для каждого из 2n различных наборов значений переменных n x1, x2, …, xn. Значит, число различных булевых функций n переменных равно числу 𝐴2̅2 n 𝑛 всех размещений с повторениями из двух элементов по 2n. Имеем 𝐴2̅2 = 22 . Теорема доказана.  Определение 2.1.3. Булева функция f (x1, x2, …, xn) называется тождественно равной нулю (или константой 0), если она при любых значениях переменных принимает значение 0. Определение 2.1.4. Булева функция f (x1, x2, …, xn) называется тождественно равной единице (или константой 1), если она при любых значениях переменных принимает значение 1. Определение 2.1.5. Две булевы функции f (x1, x2, …, xn) и g (x1, x2, …, xn) называются равными, если для всех возможных наборов значений переменных они принимают одинаковые значения. Если булевы функции f (x1, x2, …, xn) и g (x1, x2, …, xn) равны, то пишут: f (x1, x2, …, xn) = g (x1, x2, …, xn). Из определения 2.1.3 следует, что равные функции имеют одну и ту же таблицу истинности. Определение 2.1.6. Переменная xi в булевой функции f (x1, x2, …, xi−1, xi , xi+1, …, xn) называется существенной, если f (x1, x2, …, xi−1, 0 , xi+1, …, xn)  f (x1, x2, …, xi−1, 1 , xi+1, …, xn) хотя бы для одного набора значений остальных переменных. В этом случае говорят, что булева функция f (x1, x2, …, xi−1, xi , xi+1, …, xn) существенно зависит от переменной xi. Определение 2.1.7. Переменная xi в булевой функции f (x1, x2, …, xi−1, xi , xi+1, …, xn) называется несущественной (или фиктивной), если f (x1, x2, …, xi−1, 0 , xi+1, …, xn) = f (x1, x2, …, xi−1, 1 , xi+1, ..., xn) при любых значениях остальных переменных. Другими словами, переменная xi в булевой функции f (x1, x2, …, xi−1, xi , xi+1, …, xn) является фиктивной, если изменение значения переменной xi в любом наборе значений переменных x1, x2, …, xn не меняет значения функции f. Пример 2.1.3. Рассмотрим булеву функцию f (x, y, z), заданную таблицей истинности (табл. 2.1.2). Из табл. 2.1.2 находим: f (0, 0, 0) = f (0, 0, 1) = 0; f (0, 1, 0) = f (0, 1, 1) = 1; f (1, 0, 0) = f (1, 0, 1) = 0; f (1, 1, 0) = f (1, 1, 1) = 0. Таким образом, для функции f (x, y, z) выполняется следующее условие: f (x, y, 0) = f (x, y, 1) при любых значениях переменных x и y. Значит, согласно определению 2.1.7 переменная z в функции f (x, y, z) является фиктивной. Переменная x в рассматриваемой функции является существенной, так как, например, f (0, 1, 1) = 1, а f (1, 1, 1) = 0. Функция f также существенно зависит и от переменной y, так как, например, f (0, 0, 0) = 0, а f (0, 1, 0) = 1.  Пусть переменная xi в булевой функции f (x1, x2, …, xi−1, xi , xi+1, …, xn) является фиктивной. Рассмотрим таблицу истинности функции f и вычеркнем в ней все строки вида (1, 2, …, i−1, 1, i+1, …, n) и столбец значений переменной xi. В результате получим таблицу истинности функции  (x1, x2, …, xi−1, xi+1, …, xn), которая уже зависит от n − 1 переменных. В этом случае говорят, что функция  получена из функции f с помощью удаления фиктивной переменной xi, а функция f получена из функции  с помощью введения фиктивной переменной xi. Определение 2.1.8. Пусть f (x1, x2, …, xn) и  (x1, x2, …, xm) – две булевы функции, где n  m. Функции f и , зависящие от разного числа переменных, называются равными, если одна из них получается из другой с помощью введения или удаления некоторых фиктивных переменных. Согласно определению 2.1.6 любое конечное множество M булевых функций можно считать зависящим от одного и того же множества переменных, которое является объединением множеств переменных всех функций из множества M. Таблица 2.1.2 x y z f 0 0 0 0 1 0 1 0 1 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 Рассмотрим все булевы функции одной и двух переменных. Определение 2.1.9. Булевой функцией одной переменной называется функция f: {0, 1} → {0, 1}. Таким образом, областью определения и областью значений булевой функции одной переменной является множество {0, 1}. Из теоремы 2.1.1 следует, что существуют четыре различных булевых функций одной переменной. Все они приведены в таблице истинности (табл. 2.1.3), где номер функции, записанный в двоичной системе счисления, есть столбец значений соответствующей функции. Таблица 2.1.3 x f0 (x) f1 (x) f2 (x) f3 (x) 0 0 1 1 1 0 1 1 Из этой таблицы легко видеть, что булевы функции одной переменной могут быть представлены формулами алгебры логики следующим образом: f0 (x) = 0, f1 (x) = x, f2 (x) =  x, f3 (x) = 1. Замечание 2.1.1. Если функция алгебры логики реализуется формулой, содержащей единственную логическую связку, то она имеет такое же название, какое имеет используемая в формуле логическая связка.  Согласно замечанию 2.1.1 булевы функции одной переменной имеют следующие названия: f0 (x) – тождественно равная нулю (или константа 0); f1 (x) – тождественная; f2 (x) – отрицание; f3 (x) − тождественно равная единице (или константа 1). В функциях f0 (x) и f3 (x) переменная x является фиктивной, а в функциях f1 (x) и f2 (x) – существенной. Определение 2.1.10. Булевой функцией двух переменных называется функция g: {0, 1}2 → {0, 1}. Областью определения булевой функции двух переменных является множество {0, 2 1} – множество всех упорядоченных пар, составленных из нулей и единиц, а областью значений − множество {0, 1}. По теореме 2.1.1 имеется 16 различных булевых функций двух переменных. Перечислим их в таблице истинности (табл. 2.1.4), нумеруя функции так же, как и функции одной переменной. При этом будем обозначать gi (x1, x2) более кратко через gi. x1 1 1 x2 1 1 g0 g1 1 g2 1 g3 1 1 g4 1 g5 1 1 g6 1 1 g7 1 1 1 g8 1 g9 g10 g11 1 1 1 0 0 0 0 1 1 1 0 1 Таблица 2.1.4 g12 g13 g14 g15 1 1 1 1 1 1 1 1 0 0 1 1 0 1 0 1 Учитывая таблицу 2.1.4 и замечание 2.1.1, для наиболее важных булевых функций двух переменных приведем реализующие их формулы алгебры логики и соответствующие названия функций: g0 (x1, x2) = 0 – тождественно равная нулю (или константа 0); g1 (x1, x2) = x1  x2 – конъюнкция; g6 (x1, x2) = x1  x2 – сложение по модулю 2 (mod 2); g7 (x1, x2) = x1  x2 – дизъюнкция; g8 (x1, x2) = x1  x2 – стрелка Пирса; g9 (x1, x2) = x1  x2 – эквиваленция; g13 (x1, x2) = x1 → x2 – импликация; g14 (x1, x2) = x1  x2 – штрих Шеффера; g15 (x1, x2) = 1 – тождественно равная единице (или константа 1). Замечание 2.1.2. Функции g0 (x1, x2) и g15 (x1, x2) имеют две фиктивные переменные. Формально эти функции отличаются от f0 (x) и f3 (x) в табл. 2.1.3, так как все булевы функции одной переменной представляют собой унарные алгебраические операции на множестве {0, 1}, а все булевы функции двух переменных – бинарные алгебраические операции на множестве {0, 1}. Однако, согласно определению 2.1.6, f0 (x) = g0 (x1, x2) и f3 (x) = g15 (x1, x2).  Определим операцию над булевыми функциями, с помощью которой можно образовывать новые функции из нескольких исходных. Определение 2.1.11. Суперпозицией функций f1, f2, …, fk называется функция f, полученная некоторой подстановкой функций f1, f2, …, fk друг в друга и переименования переменных. Замечание 2.1.3. Приведенное определение суперпозиции не является строгим, а отражает интуитивный смысл этой операции. Строгое определение суперпозиции булевых функций можно найти, например, в курсе лекций И.А. Палий [9].  Пример 2.1.4. Рассмотрим функции f1 (x, y) = x → y, f2 (x, y) = x  y, f3 (x) = 𝑥̅ . Функция f (x, y) = (x  y) → 𝑥̅ является суперпозицией функций f1, f2 и f3.  2.2. Представление произвольной булевой функции в виде формулы алгебры логики Всякая формула алгебры логики является булевой функцией. Тавтология и противоречие есть постоянные функции. Возникает вопрос о представлении произвольной булевой функции некоторой формулой алгебры логики. Соглашение 2.2.1. В этом параграфе и далее в главе II условимся операцию конъюнкцию обозначать символом «» и при этом точку опускать.  Пусть x – переменная и  − параметр, принимающие значения из множества {0, 1}. Обозначим через x выражение x  𝑥̅ 𝜎̅. Тогда 𝑥̅ , если 𝜎 = 0; 𝑥𝜎 = { 𝑥, если 𝜎 = 1.  Выражение x , то есть переменная x с отрицанием или без него, называется литерой. Лемма 2.2.1. x = 1  x = . Доказательство. Пусть x = 1, то есть x  𝑥̅ 𝜎̅ = 1. Следовательно, согласно определению операции дизъюнкции, x = 1 или 𝑥̅ 𝜎̅ = 1. Если x = 1, то по определению операции конъюнкции x =  = 1. Если же 𝑥̅ 𝜎̅ = 1, то 𝑥̅ = 𝜎̅ = 1, откуда x =  = 0. Итак, мы показали, что если x = 1, то x = . Пусть x = . Тогда x = x  𝑥̅ 𝜎̅ = x x  𝑥̅ 𝑥̅ = x  𝑥̅ = 1. Лемма доказана.  Теорема 2.2.1 (разложение булевой функции n переменных по m переменным). Всякая булева функция f (x1, x2, …, xn) может быть представлена в следующем виде: 𝑓 (𝑥1 , 𝑥2 , … , 𝑥𝑚 , 𝑥𝑚+1 , … , 𝑥𝑛 ) = = ⋁ 𝑥1 𝜎1 𝑥2 𝜎2 … 𝑥𝑚 𝜎𝑚 𝑓(𝜎1 , 𝜎2 , … , 𝜎𝑚 , 𝑥𝑚+1 , … , 𝑥𝑛 ) , (2.2.1) (𝜎1 , 𝜎2 ,…, 𝜎𝑚 ) где m  n, а дизъюнкция берется по всем возможным наборам значений переменных x1, x2, …, xm. Доказательство. В левой и правой частях равенства (2.2.1) – булевы функции переменных x1, x2, …, xn. Чтобы доказать равенство двух булевых функций, число переменных которых одинаково, нужно показать равенство их значений для всех возможных наборов значений переменных. Пусть (1, 2, …, n) – произвольный набор значений переменных (x1, x2, …, xn). Тогда функция в левой части равенства (2.2.1) на этом наборе принимает значение f (1, 2, …, n). Найдем значение функции в правой части равенства (2.2.1) на наборе (1, 2, …, n). Пусть (1, 2, …, m) – произвольный набор переменных x1, x2, …, xm. Заметим сначала, что по лемме 2.2.1 для любого номера i (i = 1, 2, …, m) равенство 𝑥𝑖 𝜎𝑖 = 1 выполняется тогда и только тогда, когда xi = i. Значит, конъюнкция 𝑥1 𝜎1 𝑥2 𝜎2 … 𝑥𝑚 𝜎𝑚 на наборе (1, 2, …, m) равна 1 тогда и только тогда, когда i = i (i = 1, 2, …, m). Во всех остальных случаях, то есть когда для некоторого номера i {1, 2, …, m} справедливо неравенство i  i и, следовательно, 𝛼𝑖 𝜎𝑖 = 0, значение конъюнкции 𝑥1 𝜎1 𝑥2 𝜎2 … 𝑥𝑚 𝜎𝑚 на наборе (1, 2, …, m) равно 0. Поэтому функция в правой части равенства (2.2.1) на наборе (1, 2, …, n) принимает значение ⋁ 𝛼1 𝜎1 𝛼2 𝜎2 … 𝛼𝑚 𝜎𝑚 𝑓(𝜎1 , 𝜎2 , … , 𝜎𝑚 , 𝛼𝑚+1 , … , 𝛼𝑛 ) = (𝜎1 , 𝜎2 ,…, 𝜎𝑚 ) = 𝛼1 𝛼1 𝛼2 𝛼2 … 𝛼𝑚 𝛼𝑚 𝑓(𝛼1 , 𝛼2 , … , 𝛼𝑚 , 𝛼𝑚+1 , … , 𝛼𝑛 ) = 𝑓(𝛼1 , 𝛼2 , … , 𝛼𝑛 ). Получили, что булевы функции в обеих частях равенства (2.2.1) равны, так как на произвольном наборе (1, 2, …, n) принимают одно и то же значение.  Представление (2.2.1) булевой функции f (x1, x2, …, xm, xm+1, …, xn) называется разложением этой функции по m переменным x1, x2, …, xm. Рассмотрим важные частные случаи, когда m = 1 и m = n. Следствие 2.2.1 (разложение булевой функции одной переменной). Всякая булева функция f (x1, x2, …, xn) может быть представлена в следующем виде: 𝑓 (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = 𝑥̅1 𝑓 (0, 𝑥2 , … , 𝑥𝑛 )  𝑥1 𝑓 (1, 𝑥2 , … , 𝑥𝑛 ). (2.2.2) Доказательство. Разложим функцию f (x1, x2, …, xn), например, по переменной x1. Тогда по теореме 2.2.1 функцию можно представить в виде: 𝑓 (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = ⋁ 𝑥1 𝜎1 𝑓(𝜎1 , 𝑥2 , … , 𝑥𝑛 ). 𝜎1 Так как 1 может принимать два значения − 0 или 1, то в этом равенстве всего два логических слагаемых. Подставляя вместо 1 его возможные значения, получаем, что 𝑓 (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = 𝑥1 0 𝑓(0, 𝑥2 , … , 𝑥𝑛 )  𝑥11 𝑓(1, 𝑥2 , … , 𝑥𝑛 ) = = 𝑥̅1 𝑓(0, 𝑥2 , … , 𝑥𝑛 )  𝑥1 𝑓(1, 𝑥2 , … , 𝑥𝑛 ). В этом случае функции f (0, x2, …, xn) и f (1, x2, …, xn) называются компонентами разложения. Аналогичное разложение справедливо для любой из n переменных.  Следствие 2.2.2 (разложение булевой функции по всем n переменным). Всякая булева функция f (x1, x2, …, xn), не равная тождественно нулю, может быть представлена в следующем виде: 𝑓 (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = ⋁ 𝑥1 𝜎1 𝑥2 𝜎2 … 𝑥𝑛 𝜎𝑛 , (2.2.3) 𝑓(𝜎1 , 𝜎2 ,…, 𝜎𝑛 )=1 где дизъюнкция берется по всем наборам (1, 2, …, n) значений переменных x1, x2, …, xn, на которых функция f принимает значение 1. Доказательство. По теореме 2.2.1 функцию f (x1, x2, …, xn) можно представить в виде: 𝑓 (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = 𝑥1 𝜎1 𝑥2 𝜎2 … 𝑥𝑛 𝜎𝑛 𝑓(𝜎1 , 𝜎2 , … , 𝜎𝑛 ) , ⋁ (2.2.4) (𝜎1 , 𝜎2 ,…, 𝜎𝑛 ) где дизъюнкция берется по всем 2n наборам значений переменных x1, x2, …, xn. Логические сомножители f (1, 2, …, n) в конъюнкциях правой части равенства (2.2.4) равны 0 или 1. Если f (1, 2, …, n) = 0, то соответствующая конъюнкция также равна 0. Так как по условию функция f не является тождественно равной нулю, то, удаляя в правой части этого равенства равные нулю конъюнкции, получим ⋁ 𝑥1 𝜎1 … 𝑥𝑛 𝜎𝑛 𝑓(𝜎1 , … , 𝜎𝑛 ) = (𝜎1 ,…, 𝜎𝑛 ) ⋁ 𝑥1 𝜎1 … 𝑥𝑛 𝜎𝑛 .  𝑓(𝜎1 ,…, 𝜎𝑛 )=1 Таким образом, произвольная булева функция f (x1, x2, …, xn) n переменных, не равная тождественно нулю, может быть представлена в виде формулы алгебры логики (2.2.3).  Заметим, что любая подформула 𝑥1 𝜎1 𝑥2 𝜎2 … 𝑥𝑛 𝜎𝑛 формулы 𝑥1 𝜎1 𝑥2 𝜎2 … 𝑥𝑛 𝜎𝑛 ⋁ (2.2.5) 𝑓(𝜎1 , 𝜎2 ,…, 𝜎𝑛 )=1 является элементарной конъюнкцией. Следовательно, формула (2.2.5) находится в ДНФ. При этом, как легко видеть, она удовлетворяет все четырем условиям совершенства. Таким образом, формула (2.2.5) находится в СДНФ. Поэтому разложение (2.2.5) не равной тождественно нулю булевой функции f (x1, x2, …, xn) называется совершенной дизъюнктивной нормальной формой (СДНФ) этой функции. Число логических слагаемых в СДНФ функции f (x1, x2, …, xn) равно числу наборов значений переменных x1, x2, …, xn, на которых функция принимает значение 1. Значит, между таблицей истинности функции f и ее СДНФ существует взаимно однозначное соответствие. Следовательно, СДНФ для любой тождественно не равной нулю булевой функции является единственной (с точностью до перестановки элементарных конъюнкций и литер в них). Единственной булевой функцией, не имеющей СДНФ, является тождественно равная нулю. Ее также можно представить формулой алгебры логики, например формулой x 𝑥̅ . Таким образом, справедлива следующая теорема. Теорема 2.2.2. Всякая булева функция f (x1, x2, …, xn) может быть представлена булевой формулой. Если f не является тождественно равной нулю, то существует представляющая ее формула, находящаяся в СДНФ: 𝑓 (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = ⋁ 𝑓(𝜎1 , 𝜎2 ,…, 𝜎𝑛 )=1 𝑥1 𝜎1 𝑥2 𝜎2 … 𝑥𝑛 𝜎𝑛 , причем такое представление единственно с точностью до перестановки элементарных конъюнкций и литер в них.  Каждое логическое слагаемое в СДНФ функции f называется конституентой единицы. Дадим строгое определение этого понятия. Определение 2.2.1. Пусть x1, x2, …, xn – переменные, принимающие значения из множества {0, 1}, и (1, 2, …, n) – набор, состоящий из нулей и единиц. Конституентой единицы набора (1, 2, …, n) называется элементарная конъюнкция K1(1, 2, …, n) = 𝑥1 𝜎1 𝑥2 𝜎2 … 𝑥𝑛 𝜎𝑛 . Из леммы 2.2.1 следует, что K1(1, 2, …, n) = 1 тогда и только тогда, когда xi = i (i = 1, 2, …, n). Таким образом, СДНФ булевой функции является дизъюнкция некоторых конституент единицы, среди которых нет одинаковых. Из формулы (2.2.5) следует алгоритм построения СДНФ произвольной тождественно не равной нулю булевой функции f (x1, x2, …, xn) по таблице истинности: 1. В таблице истинности функции f (x1, x2, …, xn) отмечаются все наборы (1, 2, …, n) значений переменных x1, x2, …, xn, для которых f (1, 2, …, n) = 1. 2. Для каждого отмеченного набора (1, 2, …, n) записывается конституента единицы 𝑥1 𝜎1 𝑥2 𝜎2 … 𝑥𝑛 𝜎𝑛 , в которой переменная xi (i = 1, 2, …, n) берется с отрицанием, если i = 0, и без отрицания, если i = 1. 3. Дизъюнкция всех полученных в результате выполнения п. 2 конституент единицы дает СДНФ функции f. Пример 2.2.1. Найти СДНФ булевой функции f (x1, x2, x3), заданной таблицей истинности (табл. 2.2.1). Решение. Выделим в табл. 2.2.1 жирным шрифтом наборы значений Таблица 2.2.1 x1 x2 x3 f переменных, на которых данная функция принимает значение 1. Для каждого выделенного набора (1, 2, n) записывается 0 0 1 0 1 0 конституента единицы 𝑥1 𝜎1 𝑥2 𝜎2 𝑥3 𝜎3 , 1 0 1 1 1 0 в которой переменная xi (i = 1, 2, 3) берется с отрицанием, если i = 0, 1 0 0 0 и без отрицания, если i = 1. Получаем, что набору (0, 0, 0) 1 0 1 1 соответствует конституента единицы 𝑥̅1 𝑥̅2 𝑥̅3 , (0, 1, 0) − 𝑥̅1 𝑥2 𝑥̅3 , (1, 0, 1 1 0 1 1) − 𝑥1 𝑥̅2 𝑥3 , (1, 1, 0) − 𝑥1 𝑥2 𝑥̅3 . 1 1 1 0 Дизъюнкция всех полученных конституент единицы является СДНФ функции f. Таким образом, получаем, что СДНФ f = 𝑥̅1 𝑥̅2 𝑥̅3  𝑥̅1 𝑥2 𝑥̅3  𝑥1 𝑥̅2 𝑥3  𝑥1 𝑥2 𝑥̅3 .  Если булева функция f задана реализующей ее формулой алгебры логики F, не находящейся в СДНФ, то найти СДНФ булевой функции f можно двумя способами: 1) построить таблицу истинности формулы F и воспользоваться приведенным выше алгоритмом построения СДНФ булевой функции по таблице истинности; 2) привести формулу F к СДНФ, используя алгоритм приведения формулы алгебры логики к СДНФ, основанный на ее равносильных преобразованиях (см. п. 1.1.5). Булеву функцию можно представить не только ее СДНФ. Справедлива следующая теорема, которую сформулируем без доказательства. Теорема 2.2.3. Всякая булева функция f (x1, x2, …, xn), не равная тождественно единице, может быть представлена в следующем виде: 𝑓 (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = ⋀ 𝑥1 1−𝜎1  𝑥21−𝜎2  …  𝑥𝑛 1−𝜎𝑛 , (2.2.6) 𝑓(𝜎1 , 𝜎2 ,…, 𝜎𝑛 )=0 где конъюнкция берется по всем наборам (1, 2, …, n) значений переменных x1, x2, …, xn, на которых функция f принимает значение 0.  Очевидно, что любая подформула 𝑥11−𝜎1  𝑥21−𝜎2  …  𝑥𝑛1−𝜎𝑛 формулы (2.2.6) является элементарной дизъюнкцией. Это означает, что формула (2.2.6) находится в КНФ. Более того, она удовлетворяет все четырем условиям совершенства и, следовательно, находится в СКНФ. Поэтому представление (2.2.6) не равной тождественно единице булевой функции f (x1, x2, …, xn) называется ее совершенной конъюнктивной нормальной формой (СКНФ). Так же как и СДНФ булевой функции, СКНФ определяется однозначно с точностью до перестановки элементарных дизъюнкций и литер в них. Единственной булевой функцией, не имеющей СКНФ, является тождественно равная единице. Она реализуется, например, формулой x  𝑥̅ . Таким образом, имеет место теорема, аналогичная теореме 2.2.2. Теорема 2.2.4. Если f не является тождественно равной единице, то существует представляющая ее формула, находящаяся в СКНФ: 𝑓 (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = ⋀ 𝑥11−𝜎1  𝑥21−𝜎2  …  𝑥𝑛 1−𝜎𝑛 , 𝑓(𝜎1 , 𝜎2 ,…, 𝜎𝑛 )=0 причем такое представление единственно с точностью до перестановки элементарных дизъюнкций и литер в них.  Каждый логический сомножитель в СКНФ функции f называется конституентой единицы. Строго это понятие определяется следующим образом. Определение 2.2.2. Пусть x1, x2, …, xn – переменные, принимающие значения из множества {0, 1}, и (1, 2, …, n) – набор, состоящий из нулей и единиц. Конституентой нуля набора (1, 2, …, n) называется элементарная дизъюнкция K0 (1, 2, …, n) = 𝑥11−𝜎1  𝑥21−𝜎2  …  𝑥𝑛 1−𝜎𝑛 . Из леммы 2.2.1 следует, что K0 (1, 2, …, n) = 0 тогда и только тогда, когда xi = i (i = 1, 2, …, n). Значит, СКНФ булевой функции является конъюнкцией некоторых конституент нуля, среди которых нет одинаковых. Из формулы (2.2.6) следует алгоритм построения СКНФ произвольной тождественно не равной единице булевой функции f (x1, x2, …, xn) по таблице истинности. 1. В таблице истинности функции f (x1, x2, …, xn) отмечаются все наборы (1, 2, …, n) значений переменных x1, x2, …, xn, для которых f (1, 2, …, n) = 0. 2. Для каждого набора (1, 2, …, n) записывается конституента нуля 𝑥11−𝜎1  𝑥21−𝜎2  …  𝑥𝑛 1−𝜎𝑛 , в которой переменная xi (i = 1, 2, …, n) берется с отрицанием, если i = 1, и без отрицания, если i = 0. 3. Конъюнкция всех полученных в результате выполнения п. 2 конституент нуля дает СКНФ функции f. Пример 2.2.2. Найти СКНФ булевой функции f(x1, x2, x3) из примера 2.2.1. Решение. В табл. 2.2.1 находим все наборы значений переменных, на которых данная функция принимает значение: (0, 0, 1), (0, 1, 1), (1, 0, 0), (1, 1, 1). Для каждого из вышеперечисленных наборов (1, 2, n) записывается конституента нуля 𝑥11−𝜎1  𝑥21−𝜎2  𝑥31−𝜎3 , в которой переменная xi (i = 1, 2, 3) берется с отрицанием, если i = 1, и без отрицания, если i = 0. Получаем, что набору (0, 0, 1) соответствует конституента нуля 𝑥1  𝑥2  𝑥̅3 , (0, 1, 1) − 𝑥1  𝑥̅2  𝑥̅3 , (1, 0, 0) − 𝑥1  𝑥̅2  𝑥̅3 , (1, 1, 1) − 𝑥̅1  𝑥̅2  𝑥̅3 . Конъюнкция всех полученных конституент нуля является СКНФ функции f. Таким образом, получаем, что СКНФ f = (𝑥1  𝑥2  𝑥̅3 ) (𝑥1  𝑥̅2  𝑥̅3 ) (𝑥1  𝑥̅2  𝑥̅3 ) (𝑥̅1  𝑥̅2  𝑥̅3 ).  Если булева функция f представлена формулой алгебры логики F, не находящейся в СКНФ, то найти СКНФ булевой функции f можно следующими способами: 1) построить таблицу истинности формулы F и воспользоваться приведенным выше алгоритмом построения СКНФ булевой функции по таблице истинности; 2) привести формулу F к СКНФ, используя алгоритм приведения формулы алгебры логики к СКНФ, основанный на ее равносильных преобразованиях (см. п. 1.1.5). Между СДНФ и СКНФ булевой функции существует связь, отраженная в следующей теореме. Теорема 2.2.5. Пусть f (x1, x2, …, xn) – булева функция n переменных, тождественно не равная единице. Тогда справедлива равносильность СКНФ f  СДНФ 𝑓.̅ Доказательство. Используя теорему 2.2.2 и учитывая, что 𝑓 (̅ 𝜎1 , 𝜎2 , … , 𝜎𝑛 ) = 1  𝑓(𝜎1 , 𝜎2 , … , 𝜎𝑛 ) = 0, имеем СДНФ 𝑓 ̅ = 𝑥1 𝜎1 𝑥2 𝜎2 … 𝑥𝑛 𝜎𝑛 = ⋁ 𝑓̅(𝜎1 , 𝜎2 ,…, 𝜎𝑛 )=1 = 𝑥1 𝜎1 𝑥2 𝜎2 … 𝑥𝑛 𝜎𝑛  ⋁ 𝑓(𝜎1 , 𝜎2 ,…, 𝜎𝑛 )=0  𝑥1 𝜎1  𝑥2 𝜎2  …  𝑥𝑛 𝜎𝑛 . ⋀ 𝑓(𝜎1 , 𝜎2 ,…, 𝜎𝑛 )=0 Так как 𝑥 𝜎 = { 𝑥̅ , если 𝜎 = 0, 𝑥̅ , если 𝜎 = 1, то 𝑥 𝜎 = { 𝑥, если 𝜎 = 1, 𝑥, если 𝜎 = 0. Заметим, что 𝑥 1−𝜎 = { 𝑥̅ , если 𝜎 = 1, Тогда 𝑥𝑖 𝜎𝑖 = 𝑥 1−𝜎𝑖 (i = 1, 2, …, n). 𝑥, если 𝜎 = 0. Получили, что СДНФ 𝑓 ̅  ⋀ 𝑥 1−𝜎1  𝑥 1−𝜎2  …  𝑥 1−𝜎𝑛 = СКНФ 𝑓.  𝑓(𝜎1 , 𝜎2 ,…, 𝜎𝑛 )=0 Теорема доказана.  СДНФ и СКНФ булевых функций имеют большое значение для теоретических исследований и решения практических задач. В частности, их используют при минимизации булевых функций.