Рассматриваем только те строки таблицы, где формула принимает значение 0. Каждой такой строке соответствует дизъюнкция всех переменных (без повторений). Причем аргумент, принимающий значение 0, берется без отрицания, значение 1 – с отрицанием. Наконец, образуют конъюнкцию полученных дизъюнкций.
Пример 30.
Построить СКНФ для данных формул логики высказываний.
1. .
2.
Решение.
Строим таблицу значений, используя предыдущий пример (табл. 15).
Таблица 15
№
x
y
z
Рассматриваем только наборы, на которых формула принимает значение ноль.
СКНФ (0): № 0, 1, 2, 3, 6:
Строим таблицу значений, используя предыдущий пример (табл. 16).
Таблица 16
№
x
y
F=(x® y)ÙxÙy
СКНФ (0): № 0, 1, 2:
2.2. Булевы функции
2.2.1. Представление булевой функции формулой логики высказываний
Определение. Булевой функцией f(x1, x2, …, xn) называется n-местная функция, аргументы которой принимают значения во множестве {0, 1} и сама функция принимает значения в этом же множестве.
Всякую булеву функцию от n переменных можно задать таблицей из 2n строк, в которой в каждой строке записывают одну из оценок списка переменных, принимающих значение 0 или 1.
Пример 31.
Для n=3 булеву функцию можно задать таблицей 17.
Таблица 17
№
x1
x2
x3
f(x1, x2, x3)
f(0, 0, 0)
f(0, 0, 1)
f(0, 1, 0)
f(0, 1, 1)
f(1, 0, 0)
f(1, 0, 1)
f(1, 1, 0)
f(1, 1, 1)
Используется также задание булевой функции в виде двоичного слова, длина которого зависит от числа переменных.
Пример 32.
Пусть задана булева функция от трех переменных (табл. 18). Тогда число наборов .
Таблица 18
№ набора
х1
х2
х3
f
0
0
0
0
0
1
0
0
1
0
2
0
1
0
1
3
0
1
1
0
4
1
0
0
1
5
1
0
1
1
6
1
1
0
0
7
1
1
1
1
Номера наборов всегда нумеруются, начиная с нуля, в таблице приведено стандартное расположение всех наборов функции трех переменных (обратите внимание, что каждый набор представляет собой двоичный код числа, равный номеру соответствующего набора). Первые четыре столбца одинаковы для всех булевых функций от трех переменных. Столбец значений функции задается или вычисляется.
Эту же функцию можно записать f(х1, х2, х3)=00101101.
Существует ровно различных булевых функций от n переменных. Константы 0 и 1 считают нуль-местными булевыми функциями.
Утверждение. Каждой формуле логики высказываний соответствует некоторая булева функция.
Пример 33.
Построить все булевы функции, зависящие от двух переменных.
Решение.
Поскольку n=2, различных булевых функций от двух переменных существует ровно 16 (табл. 19).
Таблица 19
№функции
Значение функции
Формула, соответствующая функции
1. 1
f=0000
f=0
2. 2
f=0001
f=x1Ùx2
3. 3
f=0010
f=
4. 4
f=0011
f=x1
5. 5
f=0100
f=
6. 6
f=0101
f=x2
7. 7
f=0110
f=x1Åx2
8. 8
f=0111
f=x1Úx2
9. 9
f=1000
f=
10. 10
f=1001
f=
11. 11
f=1010
f=
12. 12
f=1011
f=
13. 13
f=1100
f=
14. 14
f=1101
f=x1®x2
15. 15
f=1110
f=
16. 16
f=1111
f=1
Теорема. Пусть f(x1, x2, …, xk) k-местная булева функция. Если f не равна тождественно нулю, то существует такая формула F, зависящая от списка переменных x1, x2, …, xn и находящаяся в СДНФ относительно этого списка, что F выражает собой функцию f. Формула F определена однозначно с точностью до перестановки дизъюнктивных членов.
Теорема 2. Пусть f(x1, x2, …, xk) k-местная булева функция. Если f не равна тождественно единице, то существует такая формула F, зависящая от списка переменных x1, x2, …, xk и находящаяся в СКНФ относительно этого списка, что F выражает собой функцию f. Формула F определена однозначно с точностью до перестановки конъюнктивных членов.
Поскольку каждая булева функция представима в виде формулы логики высказываний, то принцип построения СДНФ и СКНФ сохраняется такой же как и для формул логики высказываний.
Пример 34.
Построить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 00101110.
Решение.
Строим таблицу значений функции (табл. 20):
Таблица 20
№
x1
x2
x3
f(x1, x2, x3)
СКНФ (0): № 0, 1, 3, 7
СДНФ (1): № 2, 4, 5, 6
2.2.2. Минимизация нормальных форм
Выше было сказано, что произвольная булева функция может быть представлена формулой в дизъюнктивной и конъюнктивной нормальной форме. Равносильными преобразованиями можно получить формулу, содержащую меньшее, чем исходная, число переменных.
Определение. Минимальной ДНФ (МДНФ) функции f(x1, x2, …, xn) называется ДНФ, реализующая функцию f и содержащая минимальное число символов переменных по сравнению со всеми другими ДНФ, реализующими функцию f.
Минимальную ДНФ данной формулы можно найти, перебрав конечное число равносильных ей ДНФ и выбрав среди них ту, которая содержит минимальное число переменных. Однако при большом числе переменных такой перебор практически невыполним. Существуют эффективные способы нахождения минимальной ДНФ. Рассмотрим два из них.
Каждый из рассмотренных ниже методов состоит из двух этапов:
· построение сокращенной ДНФ;
· построение матрицы покрытий. Построение МДНФ.
Определение. Если для всякого набора а = (а1, а2, …, an) значений переменных условие g(a) = 1 влечет f(a) = 1, то функция g называется частью функции f (или функция f накрывает функцию g). Если при этом для некоторого набора с = (с1, с2, …, сn)функция g(c)=1, то говорят, что функция g накрывает единицу функции f на наборе с (или что g накрывает конституенту единицы функции f).
Конституента единицы функции f есть часть функции f, накрывающая единственную единицу функции f.
Определение. Элементарная конъюнкция К называется импликантомфункции f, если для всякого набора а = (а1, а2, …, an) из 0 и 1 условие К(а)=1 влечет f(a)=1.
Определение. Импликант К функции f называется простым, если выражение, получающееся из него выбрасыванием любых множителей, уже не импликант функции f.
Всякий импликант функции f есть часть функции f.
Теорема. Всякая функция реализуется дизъюнкцией всех своих простых импликант.
Определение. Сокращенная ДНФ функции f есть дизъюнкция всех простых импликант функции f.
Утверждение. Всякая функция f реализуется своей сокращенной ДНФ. Для всякой функции, не равной тождественно нулю, существует единственная сокращенная ДНФ.
Теорема (Куайна). Если в СДНФ функции f провести все операции неполного склеивания, а затем все операции поглощения и удаления дублирующих членов, то в результате получится сокращенная ДНФ функции f.
1. Строим таблицу значения для данной функции (табл. 20). Строим СДНФ функции. При этом слагаемые нумеруем и записываем в столбец (табл. 21).
Таблица 20
№
x1
x2
x3
x4
f(x1, x2, x3, х4)
СДНФ (1): № 0, 1, 2, 3, 5, 8, 10, 12, 13, 14, 15.
Таблица 21
№ слагаемого
слагаемое
2. Проводим все операции неполного склеивания.
Первый этап склеивания (табл. 22):
Таблица 22
Слагаемые
Склеивание по
Результат
Новые слагаемые
1, 2
x4
1
1, 3
x3
2
1, 6
x1
3
2, 4
x3
4
2, 5
x2
3, 4
x4
6
3, 7
x1
7
5, 9
x1
8
6, 7
x3
9
6, 8
x2
10
7, 10
x2
11
8, 9
x4
12
8, 10
x3
13
9, 11
x3
14
10, 11
x4
15
В первом этапе склеивания участвовали все слагаемые СДНФ, значит, ни одно из исходных слагаемых не войдут в сокращенную ДНФ. После первого этапа склеивания (и возможных поглощений) получаем, что
Пронумеруем дизъюнктивные члены в полученной ДНФ в порядке их следования от 1 до 15 (табл. 23).
Второй этап склеивания:
Таблица 23
Слагаемые
Склеивание по
Результат
1, 6
x3
2, 4
x4
2, 9
x1
3, 7
x3
9, 13
x2
10, 11
x3
12, 15
x3
13, 14
x4
В процедуре склеивания на втором этапе не принимали участие слагаемые № 5, 8 с предыдущего шага, поэтому после второго этапа склеивания и последующих поглощений получаем, что
Поскольку дальнейшее склеивания невозможны, то это и будет сокращенная ДНФ исходной функции.
2.2.2.2. Построение сокращенной ДНФ в классе дизъюнктивных нормальных форм
Этот метод не отличается большой эффективностью, но он прост для изложения и не требует введения дополнительных понятий.
Пусть булева функция задана таблицей истинности или СДНФ.
Минимизирующая карта булевой функции представляет собой квадратную матрицу 2n´2n, где n – число переменных. Первые столбцы отводят для аргументов, дальнейшие – для их всевозможных конъюнкций по 2, по 3 и т. д. сомножителей, предпоследний - для конъюнкции всех аргументов, последний – для значений функции.
Шаг 1. Столбцы для аргументов, как обычно в таблицах истинности, заполняются всевозможными наборами 0 и 1. В столбцах для конъюнкций проставляются десятичные значения двоичных чисел, соответствующих наборам значений аргументов. Последний столбец заполняется соответственно значению функции.
Далее работа чередуется по строкам, по столбцам.
Шаг 2. Вычеркиваются строки, в которых функция обращается в нуль.
Шаг 3. В каждом столбце из сохранившихся чисел вычеркивают те, равные которым уже вычеркнуты в этом столбце на предыдущем шаге.
Шаг 4. В сохранившихся строках выбирают «значения» наименьших по числу множителей конъюнкций (включая и конъюнкции с одним множителем – переменные) и обводят их кружочками.
Шаг 5. Если в одном столбце обведено несколько одинаковых чисел, то вычеркивают все, кроме одного.
Шаг 6. С помощью оставшихся обведенных чисел образуют конъюнкции. Для этого переводят каждое число в двоичную систему. Переменную, которой соответствует 1, берут сомножителем без отрицания, которой соответствует 0 – с отрицанием.
Шаг 8. Составляют дизъюнкцию полученных конъюнкций. В результате получаем сокращенную ДНФ функции.
Пример 36.
Построить сокращенную ДНФ для функции f=11100101.
Решение.
1.Строим минимизационную карту (табл. 24):
Таблица 24
№
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
f(x1, x2, x3)
1
1
1
0
0
1
0
1
2. Вычеркиваем строки, в которых функция обращается в нуль (табл. 25):
Таблица 25
№
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
f(x1, x2, x3)
1
1
1
0
0
1
0
1
3. В каждом столбце из сохранившихся чисел вычеркиваем те, равные которым уже вычеркнуты в этом столбце на предыдущем шаге (табл. 26):
Таблица 26
№
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
f(x1, x2, x3)
1
1
1
0
0
1
0
1
4. В сохранившихся строках выбираем «значения» наименьших по числу множителей конъюнкций (включая и конъюнкции с одним множителем – переменные) и обводим их (табл. 27):
Таблица 27
№
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
f(x1, x2, x3)
1
1
1
0
0
1
0
1
5. Если в одном столбце обведено несколько одинаковых чисел, то вычеркиваем все, кроме одного (табл. 28):
Таблица 28
№
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
f(x1, x2, x3)
1
1
1
0
0
1
0
1
6. С помощью оставшихся обведенных чисел образуем конъюнкции. Для этого переводим каждое число в двоичную систему. Переменную, которой соответствует 1, берем сомножителем без отрицания, 0 – с отрицанием. Составляем дизъюнкцию полученных конъюнкций.
Сокращенная ДНФ имеет вид:
Пример 37.
Построить сокращенную ДНФ функции f=1111010010101111 с использованием минимизационной карты.
Решение.
Строим минимизационную карту (табл. 29) и пошагово выполняем алгоритм.
Шаг 1.
Таблица 29
№
x1
x2
x3
x4
x1x2
x1x3
x1x4
x2x3
x2x4
x3x4
x1x2x3
x1x2x4
x1x3x4
x2x3x4
x1x2x3x4
f
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Шаг 2. Вычеркиваем строки, в которых функция обращается в нуль (табл. 30):
Таблица 30
№
x1
x2
x3
x4
x1x2
x1x3
x1x4
x2x3
x2x4
x3x4
x1x2x3
x1x2x4
x1x3x4
x2x3x4
x1x2x3x4
f
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Шаг 3. В каждом столбце из сохранившихся чисел вычеркиваем те, равные которым уже вычеркнуты в этом столбце на предыдущем шаге (табл. 31):
Таблица 31
№
x1
x2
x3
x4
x1x2
x1x3
x1x4
x2x3
x2x4
x3x4
x1x2x3
x1x2x4
x1x3x4
x2x3x4
x1x2x3x4
f
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Шаг 4. В сохранившихся строках выбираем «значения» наименьших по числу множителей конъюнкций (включая и конъюнкции с одним множителем – переменные) и обводим их (табл. 32):
Таблица 32
№
x1
x2
x3
x4
x1x2
x1x3
x1x4
x2x3
x2x4
x3x4
x1x2x3
x1x2x4
x1x3x4
x2x3x4
x1x2x3x4
f
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Шаг 5. Если в одном столбце обведено несколько одинаковых чисел, то вычеркиваем все, кроме одного (табл. 33):
Таблица 33
№
x1
x2
x3
x4
x1x2
x1x3
x1x4
x2x3
x2x4
x3x4
x1x2x3
x1x2x4
x1x3x4
x2x3x4
x1x2x3x4
f
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Шаг 6. Сокращенная ДНФ имеет вид
2.2.2.3. Построение всех тупиковых ДНФ
Определение. Тупиковой ДНФ (ТДНФ) функции f называется такая ДНФ ее простых импликант, из которых нельзя выбросить ни одного импликанта, не изменив функции f.
Теорема. Всякая минимальная ДНФ некоторой функции является ее тупиковой ДНФ.
Для получения МДНФ функции f необходимо построить все ТДНФ функции f и выбрать те из них, которые содержат минимальное число букв.
Алгоритм построения всех тупиковых ДНФ.
Пусть f(x1, x2, …, xn) есть булева функция.
Шаг 1. Построим СДНФ функции f и пусть P1, P2, …,Pn есть ее конституенты (единицы).
Шаг 2. Построим сокращенную ДНФ функции f и пусть К1, К2, …, Кm – ее простые импликанты.
Шаг 3. Построим матрицу покрытий простых импликант функции f ее коституентами единицы (табл. 34), полагая, что
Таблица 34
N
P1
P2
…
Pj
…
Pn
K1
a11
a12
…
a1j
…
a1n
K2
a21
a22
…
a2j
…
a2n
Ki
ai1
ai2
…
aij
…
ain
Km
am1
am2
…
amj
…
amn
Шаг 4. Для каждого столбца j (1 £ j £ n)найдем множество Ej всех тех номеров i строк, для которых aij=1. Пусть Составим выражение Назовем его решеточным выражением. Это выражение можно рассматривать как формулу, построенную в свободной дистрибутивной решетке с образующими 1, 2, …, m и с операциями конъюнкции и дизъюнкции.
Шаг 5. В выражении А раскроем скобки приведя выражение А к равносильному выражению , где перечислены все конъюнкции элементы ei1, ei2, …, ein которой взяты из скобок 1, 2, …, n соответственно в выражении А.
Шаг 6. В выражении В проведем все операции удаления дублирующих членов и все операции поглощения. В результате получим равносильное выражение С, представляющее собой дизъюнкцию элементарных конъюнкций.
Пример 38.
Построить все минимальные ДНФ для функции f=1111010010101111.
Решение.
Сокращенная ДНФ для данной функции имеет вид
Строим матрицу покрытий (табл. 35).
Таблица 35
№
Простые импликанты
Конституенты единицы функции f
x1
x2
x3
x4
0000
0001
0010
0011
0101
1000
1010
1100
1101
1110
1111
1
1
1
-
-
+
+
+
+
2
0
0
-
-
+
+
+
+
3
-
0
-
0
+
+
+
+
4
1
-
-
0
+
+
+
+
5
0
-
0
1
+
+
6
-
1
0
1
+
+
Пошагово будем выбирать слагаемые, которые войдут в минимальную ДНФ. Если слагаемое нами выбрано, то мы помечаем конституенты единицы функции f, которые будут покрыты (по строке). При этом автоматически исключаем из рассмотрения конституенты единицы, которые уже покрыты, но относятся к другим слагаемым сокращенной ДНФ.
Шаг 1. Выбираем слагаемое 1 (табл. 36):
Таблица 36
№
Простые импликанты
Конституенты единицы функции f
x1
x2
x3
x4
0000
0001
0010
0011
0101
1000
1010
1100
1101
1110
1111
1
1
1
-
-
+
+
+
+
2
0
0
-
-
+
+
+
+
3
-
0
-
0
+
+
+
+
4
1
-
-
0
+
+
+
+
5
0
-
0
1
+
+
6
-
1
0
1
+
+
Шаг 2. Выбираем слагаемое 2 (табл. 37):
Таблица 37
№
Простые импликанты
Конституенты единицы функции f
x1
x2
x3
x4
0000
0001
0010
0011
0101
1000
1010
1100
1101
1110
1111
1
1
1
-
-
+
+
+
+
2
0
0
-
-
+
+
+
+
3
-
0
-
0
+
+
+
+
4
1
-
-
0
+
+
+
+
5
0
-
0
1
+
+
6
-
1
0
1
+
+
Шаг 3. Выбираем слагаемое 4 (табл. 38):
Таблица 38
№
Простые импликанты
Конституенты единицы функции f
x1
x2
x3
x4
0000
0001
0010
0011
0101
1000
1010
1100
1101
1110
1111
1
1
1
-
-
+
+
+
+
2
0
0
-
-
+
+
+
+
3
-
0
-
0
+
+
+
+
4
1
-
-
0
+
+
+
+
5
0
-
0
1
+
+
6
-
1
0
1
+
+
Шаг 4. Выбираем слагаемое 5 (табл. 39):
Таблица 39
№
Простые импликанты
Конституенты единицы функции f
x1
x2
x3
x4
0000
0001
0010
0011
0101
1000
1010
1100
1101
1110
1111
1
1
1
-
-
+
+
+
+
2
0
0
-
-
+
+
+
+
3
-
0
-
0
+
+
+
+
4
1
-
-
0
+
+
+
+
5
0
-
0
1
+
+
6
-
1
0
1
+
+
Поскольку все конституенты единицы покрыты, то одна из ТДНФ имеет вид
Поскольку выбор включаемых слагаемых произволен, то функция может иметь несколько ТДНФ. Для рассматриваемой функции существует еще несколько ТДНФ:
Все найденные ТДНФ являются минимальными ДНФ.
Пример 39.
Построить одну из МДНФ функции f=11100101.
Решение.
Сокращенная ДНФ для данной функции имеет вид
Строим матрицу покрытий (табл. 40):
Таблица 40
№
Простые импликанты
Конституенты единицы функции f
x1
x2
x3
000
001
010
101
111
1
0
0
-
+
+
2
0
-
0
+
+
3
1
-
1
+
+
4
-
0
1
+
+
Шаг 1. Выбираем слагаемое 3 (табл. 41):
Таблица 41
№
Простые импликанты
Конституенты единицы функции f
x1
x2
x3
000
001
010
101
111
1
0
0
-
+
+
2
0
-
0
+
+
3
1
-
1
+
+
4
-
0
1
+
+
Шаг 2. Выбираем слагаемое 2 (табл. 42):
Таблица 42
№
Простые импликанты
Конституенты единицы функции f
x1
x2
x3
000
001
010
101
111
1
0
0
-
+
+
2
0
-
0
+
+
3
1
-
1
+
+
4
-
0
1
+
+
Шаг 3. Выбираем слагаемое 1(табл. 43):
Таблица 43
№
Простые импликанты
Конституенты единицы функции f
x1
x2
x3
000
001
010
101
111
1
0
0
-
+
+
2
0
-
0
+
+
3
1
-
1
+
+
4
-
0
1
+
+
В результате получаем МДНФ:
2.2.2.4. Алгоритм минимизации функций в классе ДНФ
1. Строим СДНФ функции f.
2. Строим сокращенную ДНФ функции f.
3. С помощью матрицы покрытий и решеточного выражения строим все ТДНФ функции f.
4. Среди построенных ТДНФ выбираем все минимальные дизъюнктивные нормальные формы функции f.
Пример 40.
В классе нормальных форм минимизировать функцию f=01011110.
Решение.
Для построения сокращенной ДНФ используем алгоритм Куайна.
Строим СДНФ для функции f. Таблица значений имеет вид (табл. 43):
Таблица 43
№
x1
x2
x3
f
СДНФ (1): № 1, 3, 4, 5, 6 (табл.44):
Таблица 44
№ слагаемого
Слагаемое СДНФ
2. Проводим все операции неполного склеивания (табл. 45):
Таблица 45
Слагаемые
Склеивание по
Результат
1, 2
х2
1, 4
х1
3, 4
х3
3, 5
х2
Дальнейшее склеивание невозможно. Все слагаемые предыдущего шага участвовали в операции склеивания, поэтому сокращенная ДНФ имеет вид:
ÚÚÚ.
3. Строим матрицу покрытий (табл. 46).
Таблица 46
№
Простые импликанты
Конституенты единицы функции f
x1
x2
x3
001
011
100
101
110
1
0
-
1
+
+
2
-
0
1
+
+
3
1
0
-
+
+
4
1
-
0
+
+
Последовательно выбираем слагаемые: № 4, 1, 2 (табл. 47).
Таблица 47
№
Простые импликанты
Конституенты единицы функции f
x1
x2
x3
001
011
100
101
110
1
0
-
1
+
+
2
-
0
1
+
+
3
1
0
-
+
+
4
1
-
0
+
+
В результате МДНФ имеет вид: ÚÚ.
Пример 41.
Построить МДНФ функции f=11011011.
Решение.
Для построения сокращенной ДНФ используем минимизационную карту (табл. 48).
Шаг 1.
Таблица 48
№
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
f(x1, x2, x3)
1
1
0
1
1
0
1
1
Шаг 2. Вычеркиваем строки, в которых функция обращается в нуль (табл. 49):
Таблица 49
№
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
f(x1, x2, x3)
0
0
0
0
0
0
0
1
0
0
1
0
1
1
1
1
0
1
0
1
0
2
2
0
0
1
1
1
1
3
3
1
1
0
0
2
2
0
4
1
1
0
1
2
3
1
5
0
1
1
0
3
2
2
6
1
1
1
1
3
3
3
7
1
Шаг 3. В каждом столбце из сохранившихся чисел вычеркиваем те, равные которым уже вычеркнуты в этом столбце на предыдущем шаге (табл. 50):
Таблица 50
№
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
f(x1, x2, x3)
Шаг 4. В сохранившихся строках выбираем «значения» наименьших по числу множителей конъюнкций (включая и конъюнкции с одним множителем – переменные) и обводим их (табл. 51):
Таблица 51
№
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
f(x1, x2, x3)
Шаг 5. Если в одном столбце обведено несколько одинаковых чисел, то вычеркиваем все, кроме одного (табл. 52):
Таблица 52
№
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
f(x1, x2, x3)
Шаг 6. Сокращенная ДНФ имеет вид:
Строим матрицу покрытий (табл. 53).
Таблица 53
№
Простые импликанты
Конституенты единицы функции f
x1
x2
x3
000
001
011
100
110
111
1
0
0
-
+
+
2
1
1
-
+
+
3
0
-
1
+
+
4
1
-
0
+
+
5
-
0
0
+
+
6
-
1
1
+
+
Последовательно выбираем слагаемые: № 1, 2, 5, 6 (табл. 54).
Таблица 54
№
Простые импликанты
Конституенты единицы функции f
x1
x2
x3
000
001
011
100
110
111
1
0
0
-
+
+
2
1
1
-
+
+
3
0
-
1
+
+
4
1
-
0
+
+
5
-
0
0
+
+
6
-
1
1
+
+
В результате МДНФ имеет вид:
2.2.3. Полные системы булевых функций
Определение. Система булевых функций f1,f2, …, fn называется полной, если любая булева функция может быть выражена через функции f1,f2, …, fn с помощью суперпозиций.
Пример 42.
Исходя из определения полной системы булевых функций, следует, что система {Ù, Ú, Ø} является полной, так как любая булева функция может быть представима в виде СДНФ и/либо СКНФ.
Дадим определение суперпозиции функций.
Определение. - конечная система булевых функций. Функция f называется суперпозицией ранга 1(или элементарной суперпозицией) функций f1, f2, …, fm, если f может быть получена одним из следующих способов:
переименованием некоторой переменной xj какой-нибудь функции fi, т. е. f=fi(x1, …, xj-1, y, xj+1, …, xk1), где y может совпасть с любой переменной;
подстановкой некоторой функции fl (1£ l m) вместо какой-либо переменной xj любой из функций fiÎK0, т. е. f=fi(x1, …, xj-1, fl(x1, x2, …, xk1), xj+1, ..., xki).
Определение. Суперпозиции ранга 1 образуют класс функций К1. Класс функций, получающихся из функций класса Кr-1 суперпозиций ранга r-1 с помощью элементарных суперпозиций, называется классом функцийKr суперпозиций ранга r. Суперпозициями функций из К0 называются функции, входящие в какой-либо из классов Kr.
Определение. Класс (множество) К булевых функций называется функционально замкнутым, если вместе с функциями из этого класса он содержит и все их суперпозиции.
Пример 43.
1. Четыре булевы функции одной переменной (f1 = 00, f2 = 11, f3 = 01, f4 = 10) образуют замкнутый класс.
2. Булевы функции f1 = x и образуют замкнутый класс.
Теорема. Класс T0={f | f(0, 0, …, 0)=0} функций, сохраняющих константу ноль на нулевом наборе, замкнут относительно суперпозиций.
Теорема. Класс T1={ f | f(1, 1, …, 1)=1} функций, сохраняющих константу один на единичном наборе замкнут относительно суперпозиций.