Запись функции в виде СДНФ часто является достаточно длинной. Наша задача состоит в упрощении этой записи. Для эффективного упрощения применим метод Блейка-Порецкого. Метод заключается в попарном склеивании всех элементарных конъюнкций СДНФ между собой, а также полученных в процессе склеивания элементарных конъюнкций меньшего числа переменных. После этого производим поглощение конъюнкциями меньшего числа переменных конъюнкций большего числа переменных.
Для упрощения формул рассматриваются следующие эквивалентные соотношения, выводимые из основных с помощью элементарных преобразований.
1.
Рассмотрим этот метод на примере
П р и м е р . Упростить СНДФ функции
Пронумеруем элементарные конъюнкции СДНФ.
Выполним все попарные склеивания элементарных конъюнкций в СДНФ (под результатом поставим номера склеиваемых конъюнкций):
В качестве упрощения указанных операций рассмотрим алгоритм Куайна.
Допустим известна строка значений функции f(x, y, z).
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 0 1 1 1
0 1 0 0 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 1
1 0 0 0 1
1 0 0 1 0
1 0 1 0 1
1 0 1 1 1
1 1 0 0 0
1 1 0 1 0
1 1 1 0 0
1 1 1 1 0
В виде СДНФ функция имеет вид
.
Это сокращенная ДНФ функции. Тупиковая ДНФ функции строится с помощью импликативной матрицы Куайна. Столбцы матрицы идентифицируются элементарными конъюнкциями булевой функции f(x, y, z, u), входящими в СДНФ, а строки – элементарными конъюнкциями, входящими в сокращенную ДНФ. Если заголовок строки является импликантой заголовка столбца, то на пересечении соответствующих строки и столбца ставится крестик. Далее нужно выбрать такое подмножество строк, которые содержат хотя бы один крестик.
(Импликантой булевой функции f называется элементарное произведение, которое равно нулю, во всех тех наборах, где f равна нулю). Строим таблицу Куайна
Если в столбце только один крестик, то такую строку надо выбрать обязательно; это строка
Далее вычеркиваем столбцы, на пересечении которых с уже выбранной строкой стоят крестики (это столбцы 3, 4, 5, 6). В каждом из оставшихся столбцов стоят два крестика. Множество оставшихся строк имеет четыре подмножества, удовлетворяющих условию чтобы каждый из невычеркнутых столбцов имел крестик хотя бы в одной из строк данного подмножества. Это строки {1, 3, 5}, {1, 3, 6}, {2, 3, 5}, {2, 4, 5, 6}.
Таким образом для рассматриваемой функции имеется четыре тупиковых ДНФ:
Первые три из них являются МДНФ.
Двойственность в алгебре высказываний.
Определение. Пустьf(x1, x2, ... xn) – формула алгебры высказываний. Двойственной к ней будем называть формулу f *(x1, x2, ... xn), определенную следующим соотношением
f *(x1, x2, ... xn) .
Из закона двойного отрицания следует, что (f * )* ≡ f.
П р и м е р 1 .
Теорема 1 (закон двойственности). Формулыf1(x1, x2, ...xn) и f2(x1, x2, ...xn) равносильны тогда итолько тогда, когда равносильныf1*(x1, x2, ...xn) и f2* (x1, x2, ...xn).
Утвержден6ие. Столбец значений функцииf * может быть получен из столбца значений функции f с помощью инвертирования (т.е. переписывания в обратном порядке) и поэлементного отрицания.
П р и м е р 2 .Рассмотрим функцию f(x1, x2, x3) ≡ из предыдущего параграфа. Получим таблицу истинности формулы f*≡.
0 0 0 1 1 0 0 0
0 0 1 1 1 0 0 1
0 1 0 1 0 0 0 0
0 1 1 1 1 0 0 0
1 0 0 0 0 0 1 1
1 0 1 0 0 1 1 1
1 1 0 0 1 0 0 1
1 1 1 0 1 1 1 1
Теорема 2 (принцип двойственности для булевых формул) Двойственная к булевой формуле может быть получена заменой констант 0 на 1, 1 на 0, и сохранением структуры формул (т. е. соответствующего порядка действий).
П р и м е р 3 . Скобка в правой части поставлена для соблюдения порядка действий.
Функции алгебры логики.
В высказываниях нас не интересует содержательная часть, а интересует только значения истинности.( т. е. xiпринимают значений только 0 или 1). Множество всех наборов значений истинности высказывательных переменных xi конечно и (составляет 2n наборов) и может быть задано таблично. Например, для f(x1, x2) имеем
x1 x2
0 0
0 1
1 0
1 1
Определение. ПустьB2 = {0, 1}. Булевой функцией (функцией алгебры логики) от n переменных называется отображение f: B2n в B2. Напомним, что
Другими словами.
Определение. Функция f(x1, x2, ..., xn) называется булевой(или функцией алгебры логики), если все ее аргументы являются булевыми, а сама функция может принимать только два значения 0 и 1.
Множество булевых функций от n переменных обозначается P2(n).
Способы задания булевых функций.
Способы задания не отличаются от обычных способов задания функций в анализе.
.
.
из предыдущего параграфа. Получим таблицу истинности формулы f*≡. 
и сохранением структуры формул (т. е. соответствующего порядка действий).
Скобка в правой части поставлена для соблюдения порядка действий.
