Принцип двойственности. разложение булевых функций по переменным. совершенные дизъюнктивная и конъюнктивная нормальные формы. Лабораторная работа Функции алгебры логики (булевы функции) Совершенные нормальные формы

Обозначим через . Тогда

x s =

В частности, тогда и только тогда, когда .

С помощью “степенной функции” всякую булеву функцию можно представить в виде:

называемом разложением булевой функции по переменной .

В самом деле, если , то , и

Если , то , и

Пример 4.

Разложим функцию по переменной . Для этого сначала построим таблицу функции :

Из таблицы видно, что и .

Используя формулу разложения по переменной , находим

Пример 5.

Разложим функцию из примера 4 по всем переменным. Так как функция принимает значение 1 на трех наборах: , то согласно следствию из теоремы о разложении, имеем

Определение 3.

Разложение булевой функции по всем переменным в виде

называется совершенной дизъюнктивной нормальной формой (СДНФ).

Пример 6.

- СДНФ для функции (см. пример 5).

Теорема 2.

Всякая булева функция (кроме 0) имеет единственную СДНФ.

Доказательство. Согласно следствию из теоремы о разложении

Замечание. Если под дизъюнкцией одного слагаемого понимать само это слагаемое, то дизъюнкции нуля слагаемых не существует, поэтому не существует СДНФ для функции 0.

При построении СДНФ имеет место следующее

Правило единицы. принимает значение 1; для каждого такого набора в СДНФ делается заготовка слагаемого . Если в данном наборе аргументов , то над переменной в заготовленном слагаемом навешивается отрицание: .

Теорема 3.

Всякая булева функция может быть выражена через дизъюнкцию, конъюнкцию и отрицание:

Доказательство.

Если , то . Если , то

Теорема 4.

Всякая булева функция (кроме 1) может быть единственным образом выражена в виде совершенной конъюнктивной нормальной форме (СКНФ):

Доказательство.

Если , то и

Применив к последнему тождеству принцип двойственности, находим

При построении СКНФ имеет место следующее

Правило нуля. Рассматриваются только те наборы аргументов, на которых функция принимает значение 0; для каждого такого набора в СКНФ делается заготовка сомножителя . Если в данном наборе аргументов , то над переменной в заготовленном сомножителе навешивается отрицание: .

Пример 7.

Построим функцию для импликации: . Импликация принимает значение 0 на одном наборе:

Так как в этом наборе и , то по правилу нуля получаем

.

Итак, - искомая функция для импликации.

Полнота системы

Определение 4. Система функций {f 1 , f 2 , ..., f s , ...}ÌP 2 называется полной в Р 2 , если любая функция f (x 1 , ..., x n ) Î P 2 может быть записана в виде формулы через функции этой системы.

Полные системы

1. P 2 – полная система.

2. Система M ={x 1 &x 2 , x 1 Úx 2 , } – полная система, т.к. любая функция алгебры логики может быть записана в виде формулы через эти функции.

Пример 8. Неполные системы: { }, {0,1}.

Лемма (достаточное условие полноты)

Пусть система U = {f 1 , f 2 , ..., f s , ...} полна в Р 2 . Пусть B = {g 1 , g 2 , ..., g k , ...} – некоторая система из Р 2 , причем любая функция f i Î U может быть выражена формулой над B , тогда система B полна в Р 2 .

7. Система {x 1 &x 2 , x 1 Åx 2 , 0, 1} полна в Р 2 , U = {x 1 &x 2 , }, = x 1 Å1.

Полином Жегалкина

f (x 1 , ..., x n ) Î P 2 , представим ее в виде формулы через конъюнкцию и сумму по модулю два, используя числа 0 и 1. Это можно сделать, так как {x 1 &x 2 , x 1 Åx 2 , 0, 1} полна в Р 2 . В силу свойства x & (y Åz ) = xy Å xz можно раскрыть все скобки, привести подобные члены, и получится полином от n переменных, состоящий из членов вида х х ...х , соединенных знаком Å. Такой полином называется полиномом Жегалкина.

Общий вид полинома Жегалкина:

где , s = 0, 1, ..., n , причем при s = 0 получаем свободный член а 0 .

Представление функции в виде полинома Жегалкина

1. Представим любую функцию формулой над {x 1 &x 2 , } и сделаем замену =x Å1. Этот способ удобен, если функция задана формулой.

Пример 9 . (x 1 (x 2 x 3))(x 1 Ú x 2) x 3 = (x 1 Ú x 2 Ú x 3)(x 1 Ú x 2) x 3 = (`x 1 x 2 Ú x 1 x 3 Ú x 1 x 2 Ú x 2 Ú x 2 x 3)x 3 = (`x 1 x 3 Ú x 2)x 3 = x 1 x 3 x 2 x 3 = ((x 1 x 3 Å1)x 2 Å1)x 3 = x 1 x 2 x 3 Åx 2 x 3 Åx 3 .

Надо помнить, что четное число одинаковых слагаемых в сумме по mod 2 дает 0.

2. Метод неопределенных коэффициентов. Он удобен, если функция задана таблицей.

Пример 10 .

Запишем с неопределенными коэффициентами полином Жегалкина для функции трех переменных f (x 1 , x 2 , x 3) = (01101001) = а 0 Å а 1 х 1 Å а 2 х 2 Å а 3 х 3 Å b 1 x 1 x 2 Å b 2 x 2 x 3 Åb 3 x 1 x 3 Åcx 1 x 2 x 3 . Затем находим коэффициенты, используя значения функции на всех наборах. На наборе (0, 0, 0) f (0, 0, 0) = 0, с другой стороны, подставив этот набор в полином, получим f (0, 0, 0) = а 0 , отсюда а 0 = 0. f (0, 0, 1) = 1, подставив набор (0, 0, 1) в полином, получим: f (0, 0, 1) = а 0 Å а 3 , т.к. а 0 = 0, отсюда а 3 = 1. Аналогично, f (0, 1, 0) = 1 = а 2 , f(0, 1, 1) = 0 = а 2 Å а 3 Å b 2 b 2 = 0; а 1 = 1; 0 = а 1 Å а 3 Å b 3 , b 3 = 0; 0 = а 1 Å а 2 Å b 1 , b 1 = 0; 1 = 1 Å 1 Å 1 Å c ; c = 0; тогда полином Жегалкина для данной функции примет вид: f (x 1 , x 2 , x 3) = x 1 Å x 2 Å x 3 .

Многочлен Жегалкина можно получить также с помощью треугольника Паскаля по единицам его левой стороны по таблице следующим образом. Построим многочлен Жегалкина для функции f = (10011110). Верхняя сторона треугольника есть функция f . Любой другой элемент треугольника есть сумма по модулю для двух соседних элементов предыдущей строки. Левая сторона треугольника для функции f содержит шесть единиц. Многочлен Жегалкина будет содержать шесть слагаемых. Первая единица треугольника соответствует набору (000). Первое слагаемое многочлена есть 1. Третья снизу единица в левой стороне треугольника соответствует набору (101). В качестве слагаемого многочлена берем x 1 x 3 . Аналогично для других единиц треугольника. Слева от наборов показаны слагаемые многочлена Жегалкина.

Теорема Жегалкина

Каждая функция из может быть представлена в виде полинома Жегалкина единственным образом.

Здесь единственность понимается с точностью до порядка слагаемых в сумме и порядка сомножителей в конъюнкциях:

, s = 0, 1, ..., n .

Доказательство.

Любая функция из Р 2 может быть представлена формулой над {x 1 & x 2 , x 1 Å x 2 , 0, 1}, а эта формула после раскрытия всех скобок и приведения подобных членов дает полином Жегалкина. Докажем единственность представления. Рассмотрим функции f (x 1 , ..., x n ) от n переменных. Мы знаем, что всего таких функций, т.е. их таблиц истинности, 2 n . Подсчитаем число различных полиномов Жегалкина от n переменных, т.е. число вариаций вида: . Число наборов равно числу всех подмножеств множества { x 1 , ..., x n }, сюда входит и пустое множество (если s = 0). Число подмножеств множества из n элементов равно 2 n , а так как каждый набор входит с коэффициентом , принимающим два значения: 0 или 1, то число всевозможных полиномов будет . Так как каждому полиному соответствует единственная функция, число функций от n переменных равно числу полиномов, то каждой функции будет соответствовать единственный полином.

Определение.

Функция f (x 1 , ..., x n ), полином Жегалкина для которой имеет следующий линейный относительно переменных вид: f = а 0 Å а 1 х 1 Å а 2 х 2 Å ... Å а n х n , называется линейной.

Лемма о нелинейной функции .

Суперпозицией нелинейной функции, отрицания и константы 1 можно получить конъюнкцию.

Доказательство.

Пусть f (x 1 , ..., x n ) – нелинейная функция. Тогда полином Жегалкина содержит для нее слагаемое, в котором присутствует произведение x i x j . Будем считать для простоты, что x 1 x 2 в многочлене Жегалкина является этим произведением. Произведя группировку слагаемых, функцию f представим в виде

Функция h 0 не есть тождественный нуль, иначе в полиноме Жегалкина отсутствует слагаемое с произведением x 1 x 2 . Тогда существует набор (a 3 , …, a n ) из 0 и 1, для которого h 0 (a 3 , …, a n ) = 1. Пусть h 1 (a 3 , …, a n ) = a , h 2 (a 3 , …, a n ) = b , h 3 (a 3 , …, a n ) = c . Тогда

Построим функцию:

Где d = ab Å c . Если d = 0, то h (x 1 , x 2) = x 1 x 2 . Если d = 1, то h (x 1 , x 2) = x 1 x 2 Å 1 и тогда Лемма доказана.

Функция f (x 1 , ..., x n) сохраняет константу a Î {0, 1}, если f (a , …, a ) = a .

Пример 11.

Функция xy сохраняет 0, сохраняет 1. Функция x ®y сохраняет 1 и не сохраняет 0.

Минимизация булевых функций

Минимизация нормальных форм

Минимальной ДНФ (МДНФ) функции f (x 1 , ... ,x n ) называется ДНФ, реализующая функцию f и содержащая минимальное число символов переменных по сравнению со всеми другими видами ДНФ, реализующими функцию f .

Если для всякого набора = (a 1 , ..., a n ) значений переменных условие g ()=1 влечёт , то функция g называется частью функции f (или функция f накрывает функцию g ). Если при этом для некоторого набора = (c 1 , ..., c n ) функция g ()=1, то говорят, что функция g накрывает единицу функции f на наборе (или что g накрывает конституенту единицы функции f ). Заметим, что конституанта единицы функции f есть часть функции f , накрывающая единственную единицу функции f .

Элементарная конъюнкция K называется импликантом функции f , если для всякого набора =(a 1 , ..., a n ) из 0 и 1 условие K ()=1 влечет f ()=1.

Импликант K функции f называется простым, если выражение, получающееся из него выбрасыванием любых множителей, уже не импликант функции f .

Ясно, что всякий импликант функции f есть часть функции f .

Теорема 5.

Всякая функция реализуется дизъюнкцией всех своих простых имликант (ПИ).

Следовательно, f = A . Теорема доказана.

Сокращенная ДНФ функции f есть дизъюнкция всех простых импликант функции f . Всякая функция f реализуется своей сокращенной ДНФ. Для всякой функции, не равной тождественно нулю, существует единственная сокращенная ДНФ.

Пусть A и B – произвольные формулы. Из свойств булевых операций вытекают следующие обратимые правила преобразования ДНФ:

1) – полное склеивание (развертывание);

2) – неполное склеивание;

3) – обобщенное склеивание;

4) – поглощение;

5) – идемпотентность (удаление дублирующих членов).

Теорема Квайна. Если в СДНФ функции f провести все операции неполного склеивания, а затем все операции поглощения и удаления дублирующих членов, то в результате получится сокращения ДНФ функции f .

Доказательство.

Пусть имеем сокращенную ДНФ функции f . Проведем все операции развертывания к каждому простому импликанту для получения недостающих переменных в каждом дизъюнктивном слагаемом сокращенной ДНФ. В полученном выражении из нескольких одинаковых дизъюнктивных слагаемых оставим только по одному экземпляру. В результате получим СДНФ функции f . Теперь, исходя из полученной СДНФ, в обратном порядке проведем операции добавления одинаковых дизъюнктивных слагаемых (с помощью правил идемпотентности), неполного склеивания и поглощения. В итоге получим исходную сокращенную ДНФ.

3.1 Разложение булевых функций по переменным

3.2 Алгебра Жегалкина

Выше мы показали, что любая булева функция может быть задана с помощью таблицы истинности. В настоящем разделе излагается переход от табличного перехода задания функции к аналитическому.

3.1 Разложение булевых функций по переменным.

Пусть G– параметр, равный 0 или 1. Введем обозначение:

Проверкой легко установить, что x G = 1, тогда и только тогда, когдаx =G. Отсюда следует, конъюнкция
равна 1 (здесьGравен 0 или 1) тогда и только тогда, когда
. Например, конъюнкция
(в которойG 2 =G 1 = 0,G 3 =G 4 = 1) равна 1 только в случае, когдаx 1 =x 2 = 0,x 3 =x 4 = 1.

Теорема 1 Всякая булева функция f (x 1 , x 2 ,…, x n ) может быть представлена в следующей форме:

где 1 ≤ k ≤ n , в дизъюнкции берется по всем наборам значений переменных.

Это представление носит название разложения функции по переменным
. Например, приn= 4,k= 2 разложение (3.1) имеет вид:

.

Докажем справедливость разложения (3.1). Для этого возьмем произвольный набор значений переменных
. Покажем, что левая и правая части соотношения (3.1) принимают при нем одно и то же значение. Действительно, так какx G = 1 тогда и только тогда, когдаx =G, то среди 2 К конъюнкции
правой части (3.1) в единицу обращается только одна, в которой
. Все остальные конъюнкции
равны нулю.

Поэтому . В качестве следствия из разложения (3.1) получаем следующие два специальных разложения.

Разложение по переменной x n :

Если булева функция не есть константа 0, то справедливо разложение

Разложение по всем переменным:

,
(3.3)

где дизъюнкция берется по всем наборам
, при которых значение функции
равно 1.

Разложение (3.3) называется совершенной дизъюнктивной нормальной формой (сокращенная запись СДНФ) функции.

Разложение (3.3) дает способ построения СДНФ. Для этого в таблице истинности отмечаем все строки
, в которых
. Для каждой такой строки образуем конъюнкцию
и затем все полученные конъюнкции соединяем знаком дизъюнкции.

Таким образом, существует взаимно однозначное соответствие между таблицей истинности функции
и ее СДНФ. А это значит, что СДНФ для булевой функции единственна.

Единая булева функция, не имеющая СДНФ, есть константа 0.

Пример 1 Найти совершенную дизъюнктивную форму для функции
.

Составим таблицу истинности для данной функции:

Отсюда получаем:
==.

Важную роль в алгебре логики играет следующее разложение булевых функций.

Теорема 2 Всякая булева функция
может быть представлена в следующей форме:

где 1≤k≤n, а конъюнкция беретсяпо всем 2 k наборам значений переменных.

Действительно, пусть
– произвольный набор значений переменных. Покажем, что левая и правая части соотношения (3.4) принимают при нем одно и то же значение. Так как
только тогда, когда
, то среди 2 k дизъюнкций
правой части (3.4) в 0 обращается только одна, в которой
. Все остальные дизъюнкции равны 1.

Поэтому
==
.

Непосредственно из разложения (3.4) следуют разложения булевых функций:

Последнее разложение носит название совершенной конъюнктивной нормальной формы (СКНФ). Разложение (3.6) дает способ построения СКНФ. Для этого в таблице истинности отмечаем все строки
, в которых. Для каждой такой строки образуем дизъюнкцию
и затем все полученные конъюнкции соединяем знаком конъюнкции. Таким образом, существует взаимно однозначное соответствие между таблицей истинности функции
и ее СКНФ. А это значит, что СКНФ для булевой функции единственна.

Единственная булева функция, не имеющая СКНФ, есть константа 1.

Пример 2 Найти совершенную конъюнктивную нормальную форму для функции
.

Составим таблицу истинности для данной функции.

Отсюда получаем СКНФ

Формула вида (краткая запись
), где
– конъюнкции
называетсядизъюнктивной нормальной формой (ДНФ).

В силу приведенного определения ДНФ будут, например, выражения:
,
.

Как отмечено в пункте 2.2, все логические операции можно свести к трем: конъюнкции, дизъюнкции и отрицания. Причем, ввиду закона де Моргана, знак отрицания можно предполагать отнесенным только к переменным.

Теперь, используя дистрибутивный закон, раскрываем скобки и получаем дизъюнктивную нормальную форму. Итак, справедлива следующая теорема.

Теорема 3 Для любой формулы алгебры логики существует равносильная ей дизъюнктивная нормальная форма.

Доказательство данной теоремы дает способ построения дизъюнктивной нормальной формы для любой формулы алгебры логики.

Пример 3 Найти дизъюнктивную нормальную форму для следующей формулы:
.

Исключая знак
по закону
и применяя законы де Моргана и двойного отрицания, получаем:

Затем, применяя закон дистрибутивности, раскроем скобки

Последнее выражение есть дизъюнктивная нормальная форма.

Форма вида
(краткая запись), где
- дизъюнкции
называетсяконъюнктивной нормальной формой (КНФ).

Такими являются, например, выражения:

,
.

Как показано выше, для любой формулы алгебры логики существует равносильная ей дизъюнктивная форма. Используя дистрибутивный закон , из данной ДНФ легко получить КНФ.

Итак, справедлива следующая теорема.

Теорема 4 Для любой формулы алгебры логики существует равносильная ей конъюнктивная нормальная форма.

Доказательство данной теоремы дает способ построения конъюнктивной нормальной формы для любой формулы алгебры логики.

Пример 4 Найти дизъюнктивную и конъюнктивную нормальные формы для следующей формулы:
.

Используя закон
, исключаем знак
. Получаем формулу
.

Используя закон де Моргана, получаем формулу
. Раскрывая скобки, получаем дизъюнктивную нормальную форму

.

Чтобы получить конъюнктивную нормальную форму, применим к формуле
дистрибутивный закон, получаем:

Последнее выражение является конъюнктивной нормальной формой. Так как
и
, то полученная КНФ равносильна следующей КНФ:

Среди всех нормальных формул данной формулы выделим совершенную нормальную форму как дизъюнктивную, так и конъюнктивную. Учитывая разложение (3), нетрудно заметить, что совершенная дизъюнктивная нормальная форма формулы алгебры логики, содержащей ровно nразличных переменных, есть ее дизъюнктивная нормальная форма, в которой:

1) все конъюнкции попарно различны;

2) каждая конъюнкция содержит ровно nпеременных;

3) в каждой конъюнкции встречаются все nпеременных.

На примере 1 мы рассмотрели один из способов построения СДНФ, основанный на составлении таблицы истинности. Следующий способ построения СДНФ основан на применении законов алгебры логики.

Пример 5 Найти совершенную дизъюнктивную форму формулы
.

Используя, что
, получаем
. Ввиду законов де Моргана и двойного отрицания имеем получили дизъюнктивную нормальную форму
. Данная ДНФ равносильна формуле.

Раскрывая скобки, получаем: .

Используя закон идемпотентности, получаем требуемую СДНФ:

Учитывая разложение (3.6), нетрудно заметить, что совершенная конъюнктивная нормальная форма формулы алгебры логики, содержащей ровно n различных переменных, есть ее конъюнктивная нормальная форма, в которой:

1) все дизъюнкции попарно различны;

2) каждая дизъюнкция содержит ровно nчленов;

3) в каждой дизъюнкции встречаются все nпеременных.

На примере 2 мы рассмотрели один из способов построения СКНФ, основанный на составлении таблицы истинности. Следующий способ построения СКНФ основан на применении законов алгебры логики.

Пример 6 Найти совершенную конъюнктивную нормальную форму формулы
.

Используя,
, получаем
.

Данная формула является конъюнктивной нормальной формой. Она равносильна формуле .

Используя закон дистрибутивности, получаем:

Применяя закон идемпотентности, получаем требуемую совершенную конъюнктивную нормальную форму

тождественно истинной , если она при всех значениях входящих в нее переменных принимает значениеистинно .

Примерами тождественно истинных формул являются формулы:

Формула алгебры логики называется тождественно ложной , если она при всех значениях, входящих в нее переменных, принимает значениеложь.

Примерами тождественно ложных формул являются формулы:

,

Формула алгебры логики называется выполнимой , если она при некоторых значениях, входящих в нее переменных, принимает значениеистинно.

Примерами выполнимых формул являются следующие формулы:

,
.

В алгебре логики можно поставить следующую задачу: указать способ (алгоритм), позволяющий для каждой формулы алгебры логики выяснить, является она тождественно истинной или нет. Поставленная задача носит название проблемы разрешения.

Рассмотрим следующие два способа решения этой задачи.

Способ 1 (табличный) Для того, чтобы определить, является ли данная формула тождественно истинной или нет, достаточно составить ее таблицу истинности.

Однако данный способ, хотя и дает принципиальное решение проблемы разрешимости, он довольно громоздкий.

Способ 2 основан на приведении формул к нормальной форме.

Теорема 4 Формула алгебры логики тогда и только тогда является тождественно истинной, когда каждая дизъюнкция в ее конъюнктивной нормальной форме содержит некоторую переменную вместе с ее отрицанием.

Действительно, если каждая дизъюнкция в конъюнктивной нормальной форме содержит переменную вместе с ее отрицанием, то все дизъюнкции равны 1, ибо
,
. Отсюда следует, что КНФ является тождественно истинной.

Пусть теперь данная формула является тождественно истинной, и пусть
есть некоторая дизъюнкция в КНФ данной формулы. Допустим, что данная дизъюнкция не содержит переменной вместе с ее отрицанием. В таком случае мы можем каждой переменной, не стоящей под знаком отрицания, дать значение 0, а каждой переменной, стоящей под знаком отрицания – значение 1. После указанной подстановки все дизъюнкции станут равны 0, следовательно, формула не является тождественно истинной. Получили противоречие.

Пример 7 Выяснить, будет ли тождественно истинной формула

.

Используя, что
, получаем
.

Применяя закон дистрибутивности, получаем КНФ:

Так как каждая дизъюнкция содержит некоторую переменную вместе с ее отрицанием, то формула тождественно истинна.

Аналогично предыдущей теореме доказывается теорема:

Теорема 5 Формула алгебры логики тогда и только тогда является тождественно ложной, когда каждая конъюнкция в ее дизъюнктивной форме содержит некоторую переменную вместе с ее отрицанием .

Выделим переменную x 1 и рассмотрим функцию f относительно нее.

Все множество наборов таблицы истинности разбивается на два подмножества, в каждом из которых по четыре набора <0, a 2 , a 3 > и <1, a 2 , a 3 >.

Тогда функцию f(x 1 ,x 2 ,x 3) можно представить в виде дизъюнкции двух функций от двух переменных и эта формула будет иметь вид:

Рассмотрим следующие формулы:

Левая часть первой формулы эквивалентна правой, поскольку для x 1 =0 и в соответствии с операцией конъюнкции. Аналогично можно показать справедливость второй формулы. Таким образом, поставив эти формулы в предыдущую дизъюнкцию, получим:

Это выражение называется разложением функции f(x 1 ,x 2 ,x 3) по переменной x 1 .

Теперь аналогично можно разложить функции f(0,x 2 ,x 3) и f(1,x 2 ,x 3) по переменной x 2 . Получим

Подставляя эти формулы в предыдущие получим

Внесем в соответствии с дистрибутивностью операции & переменную x 1 и ее инверсию в скобки, получим

В общем виде для функции f(x 1 ,x 2 ,..,x n) от n переменных разложение по m переменным (m£n) имеет вид

где дизъюнкция берется по всем 2 m наборам переменных x 1 ,x 2 ,..,x m .

Рассмотрим разложение (*4) при крайнем случае, когда m=n. (см. пример (*3)).

Тогда во всех конъюнкциях значения функции f на каждом фиксированном наборе имеет значения равные нулю или единице. Удалив все нулевые конъюнкции, получим новое разложение и в этом новом разложении удалим в конъюнкциях сомножители функций, т.к. они равны 1. Оставшееся выражение называется СДНФ (совершенная дизъюнктивная нормальная форма).

Проделаем все это для примера (*3).

После удаления из (*3) конъюнкций с нулевыми значениями функции f на заданных наборах, получим:

Так как в соответствии с таблицей истинности

f(0,0,0) = f(0,1,0) = f(1,1,0) = f(1,1,1)=1

то из конъюнкций уберем сомножители функций, после чего получим:

Это и есть совершенная дизъюнктивная нормальная форма булевой функции f.

Лемма. Любая булева функция (кроме константы "0") имеет СДНФ, при том только одну.

Аналогично можно ввести конъюнктивную форму,

Построение СДНФ для функции, заданной таблицей

Данное следствие носит конструктивный характер, т.к. оно по таблице функции позволяет построить формулу, являющуюся СДНФ (если ).
СДНФ функции f содержит ровно столько конъюнкций, сколько единиц в таблице f ; каждому “единичному” набору (d 1 ,…,d n), т.е. набору, на котором значение функции равно 1, соответствует конъюнкция всех переменных, в которой x i взято с отрицанием, если d i=0 , и без отрицания, если d i =1 .

Разложение булевых функций по переменным.

Пусть G – параметр, равный 0 или 1. Введем обозначение:

Проверкой легко установить, что x G = 1, тогда и только тогда, когда x = G. Отсюда следует, конъюнкция равна 1 (здесь G равен 0 или 1) тогда и только тогда, когда . К примеру, конъюнкция (в которой G 2 = G 1 = 0, G 3 = G 4 = 1) равна 1 только в случае, когда x 1 = x 2 = 0, x 3 = x 4 = 1.

Теорема 1 Всякая булева функция f(x 1 ,x 2 ,…,x n) должна быть представлена в следующей форме:

где 1 ≤ k ≤ n, в дизъюнкции берется по всœем наборам значений переменных.

Это представление носит название разложения функции по переменным . К примеру, при n = 4, k = 2 разложение (3.1) имеет вид:

.

Докажем справедливость разложения (3.1). Для этого возьмем произвольный набор значений переменных . Покажем, что левая и правая части соотношения (3.1) принимают при нем одно и то же значение. Действительно, так как x G = 1 тогда и только тогда, когда x = G, то среди 2 К конъюнкции правой части (3.1) в единицу обращается только одна, в которой . Все остальные конъюнкции равны нулю.

По этой причине . В качестве следствия из разложения (3.1) получаем следующие два специальных разложения.

Разложение по переменной x n:

В случае если булева функция не есть константа 0, то справедливо разложение

Разложение по всœем переменным:

, (3.3)

где дизъюнкция берется по всœем наборам , при которых значение функции равно 1.

Разложение (3.3) принято называть совершенной дизъюнктивной нормальной формой (сокращенная запись СДНФ) функции.

Разложение (3.3) дает способ построения СДНФ. Для этого в таблице истинности отмечаем всœе строки , в которых . Для каждой такой строки образуем конъюнкцию и затем всœе полученные конъюнкции соединяем знаком дизъюнкции.

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, существует взаимно однозначное соответствие между таблицей истинности функции и ее СДНФ. А это значит, что СДНФ для булевой функции единственна.

Единая булева функция, не имеющая СДНФ, есть константа 0.

Пример 1 Найти совершенную дизъюнктивную форму для функции .

Составим таблицу истинности для данной функции:

Отсюда получаем: = = .

Важную роль в алгебре логики играет следующее разложение булевых функций.

Теорема 2 Всякая булева функция должна быть представлена в следующей форме:

где 1≤k≤n, а конъюнкция берется по всœем 2 k наборам значений переменных.

Действительно, пусть – произвольный набор значений переменных. Покажем, что левая и правая части соотношения (3.4) принимают при нем одно и то же значение. Так как только тогда, когда , то среди 2 k дизъюнкций правой части (3.4) в 0 обращается только одна, в которой . Все остальные дизъюнкции равны 1.

По этой причине = = .

Непосредственно из разложения (3.4) следуют разложения булевых функций:

Последнее разложение носит название совершенной конъюнктивной нормальной формы (СКНФ). Разложение (3.6) дает способ построения СКНФ. Для этого в таблице истинности отмечаем всœе строки , в которых . Для каждой такой строки образуем дизъюнкцию и затем всœе полученные конъюнкции соединяем знаком конъюнкции. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, существует взаимно однозначное соответствие между таблицей истинности функции и ее СКНФ. А это значит, что СКНФ для булевой функции единственна.

Единственная булева функция, не имеющая СКНФ, есть константа 1.

Пример 2 Найти совершенную конъюнктивную нормальную форму для функции .

Составим таблицу истинности для данной функции.

Отсюда получаем СКНФ

Формула вида (краткая запись ), где – конъюнкции принято называть дизъюнктивной нормальной формой (ДНФ).

В силу приведенного определœения ДНФ будут, к примеру, выражения: , .

Как отмечено в пункте 2.2, всœе логические операции можно свести к трем: конъюнкции, дизъюнкции и отрицания. Причем, ввиду закона де Моргана, знак отрицания можно предполагать отнесенным только к переменным.

Теперь, используя дистрибутивный закон, раскрываем скобки и получаем дизъюнктивную нормальную форму. Итак, справедлива следующая теорема.

Теорема 3 Для любой формулы алгебры логики существует равносильная ей дизъюнктивная нормальная форма.

Доказательство данной теоремы дает способ построения дизъюнктивной нормальной формы для любой формулы алгебры логики.

Пример 3 Найти дизъюнктивную нормальную форму для следующей формулы: .

Исключая знак по закону и применяя законы де Моргана и двойного отрицания, получаем:

Затем, применяя закон дистрибутивности, раскроем скобки

Последнее выражение есть дизъюнктивная нормальная форма.

Форма вида (краткая запись ), где - дизъюнкции принято называть конъюнктивной нормальной формой (КНФ).

Такими являются, к примеру, выражения:

, .

Как показано выше, для любой формулы алгебры логики существует равносильная ей дизъюнктивная форма. Используя дистрибутивный закон , из данной ДНФ легко получить КНФ.

Итак, справедлива следующая теорема.

Теорема 4 Для любой формулы алгебры логики существует равносильная ей конъюнктивная нормальная форма.

Доказательство данной теоремы дает способ построения конъюнктивной нормальной формы для любой формулы алгебры логики.

Пример 4 Найти дизъюнктивную и конъюнктивную нормальные формы для следующей формулы: .

Используя закон , исключаем знак . Получаем формулу .

Используя закон де Моргана, получаем формулу . Раскрывая скобки, получаем дизъюнктивную нормальную форму

.

Чтобы получить конъюнктивную нормальную форму, применим к формуле дистрибутивный закон, получаем:

Последнее выражение является конъюнктивной нормальной формой. Так как и , то полученная КНФ равносильна следующей КНФ:

Среди всœех нормальных формул данной формулы выделим совершенную нормальную форму как дизъюнктивную, так и конъюнктивную. Учитывая разложение (3), нетрудно заметить, что совершенная дизъюнктивная нормальная форма формулы алгебры логики, содержащей ровно n различных переменных, есть ее дизъюнктивная нормальная форма, в которой:

1) всœе конъюнкции попарно различны;

2) каждая конъюнкция содержит ровно n переменных;

3) в каждой конъюнкции встречаются всœе n переменных.

На примере 1 мы рассмотрели один из способов построения СДНФ, основанный на составлении таблицы истинности. Следующий способ построения СДНФ основан на применении законов алгебры логики.

Пример 5 Найти совершенную дизъюнктивную форму формулы .

Используя, что , получаем . Ввиду законов де Моргана и двойного отрицания имеем получили дизъюнктивную нормальную форму . Данная ДНФ равносильна формуле .

Раскрывая скобки, получаем: .

Используя закон идемпотентности, получаем требуемую СДНФ:

Учитывая разложение (3.6), нетрудно заметить, что совершенная конъюнктивная нормальная форма формулы алгебры логики, содержащей ровно n различных переменных, есть ее конъюнктивная нормальная форма, в которой:

1) всœе дизъюнкции попарно различны;

2) каждая дизъюнкция содержит ровно n членов;тождественно истинной , в случае если она при всœех значениях входящих в нее переменных принимает значение истинно .

Примерами тождественно истинных формул являются формулы:

тождественно ложной , в случае если она при всœех значениях, входящих в нее переменных, принимает значение ложь.

Примерами тождественно ложных формул являются формулы:

Формула алгебры логики принято называть выполнимой , в случае если она при некоторых значениях, входящих в нее переменных, принимает значение истинно.

Примерами выполнимых формул являются следующие формулы:

В алгебре логики можно поставить следующую задачу: указать способ (алгоритм), позволяющий для каждой формулы алгебры логики узнать, является она тождественно истинной или нет. Поставленная задача носит название проблемы разрешения.

Рассмотрим следующие два способа решения этой задачи.

Способ 1 (табличный) Для того, чтобы определить, является ли данная формула тождественно истинной или нет, достаточно составить ее таблицу истинности.

При этом данный способ, хотя и дает принципиальное решение проблемы разрешимости, он довольно громоздкий.

Способ 2 основан на приведении формул к нормальной форме.

Теорема 4 Формула алгебры логики тогда и только тогда является тождественно истинной, когда каждая дизъюнкция в ее конъюнктивной нормальной форме содержит некоторую переменную вместе с ее отрицанием.

Действительно, в случае если каждая дизъюнкция в конъюнктивной нормальной форме содержит переменную вместе с ее отрицанием, то всœе дизъюнкции равны 1, ибо , . Отсюда следует, что КНФ является тождественно истинной.

Пусть теперь данная формула является тождественно истинной, и пусть есть некоторая дизъюнкция в КНФ данной формулы. Допустим, что данная дизъюнкция не содержит переменной вместе с ее отрицанием. В таком случае мы можем каждой переменной, не стоящей под знаком отрицания, дать значение 0, а каждой переменной, стоящей под знаком отрицания – значение 1. После указанной подстановки всœе дизъюнкции станут равны 0, следовательно, формула не является тождественно истинной. Получили противоречие.

Пример 7 Выяснить, будет ли тождественно истинной формула

.

Используя, что , получаем .

Применяя закон дистрибутивности, получаем КНФ:

Так как каждая дизъюнкция содержит некоторую переменную вместе с ее отрицанием, то формула тождественно истинна.

Аналогично предыдущей теореме доказывается теорема:

Теорема 5 Формула алгебры логики тогда и только тогда является тождественно ложной, когда каждая конъюнкция в ее дизъюнктивной форме содержит некоторую переменную вместе с ее отрицанием .

Разложение булевых функций по переменным. - понятие и виды. Классификация и особенности категории "Разложение булевых функций по переменным." 2017, 2018.

Множество В, на котором определены две бинарные операции (конъюнкция и дизъюнкция) и одна унарная операция (отрицание) и выделены два элемента 0 и 1 называется булевой алгеброй.

Причем для этих операций необходимо выполнение следующих свойств:

Ассоциативность

Коммутативность

Дистрибутивность конъюнкции относительно дизъюнкции

Дистрибутивность дизъюнкции относительно конъюнкции

Идемпотентность

Двойное отрицание

Свойства констант

Правила де Моргана

Закон противоречия

Закон исключенного третьего

В алгебре логики эти законы называются равносильностями.

Совершенные нормальные формы

Совершенная дизъюнктивная нормальная форма

Введем обозначения:

; А А =1; Х А =1, если Х=А, Х А =0, если ХА.

Формула Х А 1…… Х А n , где А=- какой-либо двоичный набор, а среди переменных Хi могут быть совпадающие называется элементарной конъюнкцией.

Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ).

Элементарная конъюнкция называется правильной, если в нее каждая переменная входит не более одного раза (включая ее вхождение под знаком отрицания).

Например: 1) (значок конъюнкции в данном случае опущен).

1),4) - правильные элементарные конъюнкции;

2)- переменная х входит один раз сама и второй раз под знаком отрицания;

Переменная y входит трижды: один раз сама и два раза под знаком отрицания.

Правильная элементарная конъюнкция называется полной относительно переменных х 1 …..х n , если в нее входит каждая их этих переменных причем только один раз (может быть и пол знаком отрицания).

Например: из перечисленных в предыдущем примере конъюнкций полной является только 4) относительно переменных x,y,z,t; а относительно переменных x,y,z полной является только 1).

Совершенной дизъюнктивной нормальной формой (СДНФ) относительно переменных х 1 …..х n называется дизъюнктивная нормальная форма, в которой нет одинаковых элементарных конъюнкций и все элементарные конъюнкции правильны и полны относительно переменных х 1 …..х n

Разложение по переменным

Теорема 1. Всякая логическая функция может быть представлена в СДНФ:

где m, а дизъюнкция берется по всем 2 m наборам значений переменных х 1 ,…х m . Функция f разложена по первым n-переменным. Данное равенство называется разложением по переменным. х 1 ,…х m . Например при n=4, m=2 разложение имеет вид:

теорема доказывается подстановкой в обе части равенства (1) произвольного набора (b 1 ,…,b m , b m+1 ,…,b n) всех n-переменных.

При m = 1 из (1) получаем разложение функции по одной переменной:

Очевидно, что аналогичное разложение справедливо для любой из n- переменных.

Другой важный случай когда n=m. При этом все переменные в правой части (1) получают фиксированные значения и функции в конъюнкции правой части становятся равными 0 или 1, что дает:

где дизъюнкция берется по всем наборам (b 1 …b n), на которых f=1. При f=0 множество конъюнкций в правой части пусто. Такое разложение называется совершенной дизъюнктивной нормальной формой. СДНФ функции f содержит ровно столько конъюнкций, сколько единиц получается в таблице истинности f. Каждому единичному набору (b 1 ,…, b n) соответствует конъюнкция всех переменных, в которой x i взято с отрицанием, если b i =0 b ,и без отрицания, если, b i =1. Таким образом существует взаимно однозначное соответствие между таблицей истинности функции f и ее СДНФ, и,следовательно, СДНФ для всякой логической функции единственна. Единственная функция не имеющая СДНФ - это константа 0.

Теорема 2 . Всякая логическая функция может быть представлена в виде булевой формулы.

Действительно, для всякой функции, кроме константы 0, таким представлением может служит ее СДНФ. Константу 0 можно представить булевой формулой.