1. В чём состоит разница между методом Квайна и методом Мак – Класки?
2. Минимизировать ФАЛ f(x1, x2, x3, x4), принимающую значение 1 на наборах:
1) 3,4,5,7,9,11,12,13.
2) 1,2,6,7,9,12,13.
3) 2,3,5,6,10,11,14.
4) 0,8,10,11,13,15.
5) 6,8,9,12,13,14.
6) 6,7,8,10,11,13.
7) 1,2,3,12,13,14,15.
8) 0,4,5,6,7,14,15.
9) 2,4,7,9,10,14,15.
10) 0,2,4,8,12,14,15.
11) 0,2,3,5,11,12,15.
12) 5,7,8,9,10,11,15.
Сделать проверку с помощью таблиц истинности.
Как мы уже знаем из теоремы о функциональной полноте, любая булева функция представима в виде формулы, содержащей лишь операции , т.е. представима в виде терма сигнатуры { }.
Сигнатурой назовём совокупность функциональных символов с указанием их местности.
Система булевых функций F= {f1,f2,f3,…,fn} называется полной, если любая булева функция представима в виде терма сигнатуры, т.е. в виде суперпозиций функций из F.
Функция f(x1,x2,…,xn) называется суперпозицией функций g(y1,…,ym) и h1(x1,…,xn),…, hm(x1,…,xn), если f(x1,x2,…,xn)= g( h1(x1,…,xn),…, hm(x1,…,xn)).
Из сказанного выше ясно, что система { } является полной.
Ответ на вопрос о полноте произвольной системы даёт теорема Поста, формулируемая ниже.
Введём определение классов Поста.
1. Класс Р0 – это класс булевых функций, сохраняющих нуль, т.е. функций F= {f1,f2,f3,…,fn}, для которых f(0,0,…,0)=0: .
2. Класс Р1 – это класс булевых функций, сохраняющих единицу, т.е. функций F= {f1,f2,f3,…,fn}, для которых f(1,…,1)=1: .
3. Класс S – это класс самодвойственных функций: S={f|f – самодвойственная функция}.
Функция называется двойственной по отношению к функции , если .
Двойственная функция получается из исходной при замене значений всех переменных, а так же значений функции на противоположные, т.е. в таблице истинности нужно заменить 0 на 1, а 1 на 0.
Пример 8.1. Двойственной к функции является функция, соответствующая формуле , т.е. . Итак, .
Функция называется самодвойственной, если .
Пример 8.2.Покажем, что формула имеет самодвойственную функцию.
Cэтой целью убедимся, что на всех противоположных наборах значений переменных, формула принимает противоположные значения. Действительно, составив таблицу истинности
X
Y
Z
φ
Получаем , , , .
4. Класс М – это класс монотонных функций.
Булева функция f(x1,…,xn) называется монотонной, если для любых наборов нулей и единиц из условий ,…, следует . Таким образом, М={f|f – монотонная функция}.
5. Класс L – это класс линейных функций.
Булева функция f(x1,…,xn) называется линейной, если в булевом кольце функция f представима в виде , где сi .
Коэффициенты линейной функции определяются из следующих соотношений:
, , ,…, , т.е. , , , . ……(1).
Таким образом, проверка линейности сводится к нахождению коэффициентов сi по формулам 1 и сопоставлению таблиц истинности для данной формулы f(x1,…,xn) и полученной формулы .
Пример 8.3. Проверим, является ли линейной функция .
Имеем , , . Таким образом . Сопоставляя таблицы истинности формул и , убеждаемся, что они не совпадают. Вывод: функция - не линейна.
Линейность функции можно также определить с помощью следующей теоремы.
Теорема 8.1 (Жегалкина).
Всякая булева функция представима полиномом Жегалкина, т.е. в виде , где в каждом наборе (i1,i2,…,in) все ij различны, а суммирование ведётся по некоторому множеству таких несовпадающих наборов. Представление булевой функции в виде полинома Жегалкина единственно с точностью до порядка слагаемых.
Полином Жегалкина называется нелинейным (линейным), если он (не) содержит произведения переменных.
Таким образом, линейность булевой функции равносильно линейности соответствующего полинома Жегалкина.
Для получения полинома Жегалкина булевой функции, находящейся в СДНФ, используются аксиомы булевой алгебры, аксиома булева кольца и равенства, выражающие операции через операции этого булева кольца: , , , , , и т.д.
Пример 8.2. Определим линейность функции .
Имеем
Полученный полином Жегалкина является нелинейным, и, следовательно, функция также не линейна.
Если в эквивалентности формулы являются различными конституентами единицы, то их произведение равно нулю, и тогда . Следовательно, для получения полинома Жегалкина из СДНФ можно сразу заменить на .
Каждый класс Поста замкнут относительно операций замены переменных и суперпозиции, т.е. с помощью этих операций и функций, принадлежащих данному классу, можно получить только функции из этого же класса.
Пример 8.3. Определим, к каким классам Поста относится булева функция .
Решение. Так как , а , то и . Поскольку , то . Так как , то . Полином Жегалкина для функции имеет вид в силу равенства . Поэтому данная функция нелинейна. Таким образом, можно составить следующую таблицу
Функция
Классы
P0
P1
S
M
L
нет
нет
нет
нет
нет
Теорема 8.2 (Поста). Система булевых функций f тогда и только тогда является полной, когда для каждого из классов P0, P1, S, M, L в системе f найдется функция, не принадлежащая этому классу.
В силу теоремы Поста функция образует полную систему, т.е. с помощью штриха Шеффера можно получить любую булеву функцию. В частности, , .
Система булевых функций называется базисом, если она полна, а удаление любой функции из этой системы делает её неполной.
Теорема 8.3. Каждый базис содержит не более четырёх булевых функций.
Пример 8.4. Следующие системы булевых функций являются базисами: .
Широкий набор базисов открывает большие возможности при решении задач минимизации схем устройств дискретного действия, поскольку из базисных схем с помощью суперпозиций можно составить схему, соответствующую любой булевой функции.
