ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 08.11.2023
Просмотров: 20
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Тема. АСПЕКТЫ КЛАССА БУЛЕВЫХ ФУНКЦИЙ
5.1. Полином Жегалкина Полиномом (многочленом) Жегалкина от n переменных называется функция f (x
1
,x
2
,…,x n
) = a
0
x
1
x
2
…x n
⊕ a
1
x
1
x
2
…x n−1
⊕ a
1
x
1
x
2
…x n−2
x n
⊕ … ⊕
⊕a m−n x
1
⊕ … ⊕a m−1
x n
⊕a Всего здесь 2
n слагаемых. Напомним, что ⊕ означает сложение по модулю 2, коэффициенты a i
являются константами (равными нулю или единице. Теорема 5.1. Любая функция n переменных может быть представлена полиномом Жегалкина и это представление единственно. Функция f(x
1
, x
2
,…, x n
) называется линейной, если ее полином Жегалкина содержит только первые степени слагаемых. Более точно функция называется линейной, если ее можно представить в виде f (x
1
, x
2
,…, x n
) = a
0
⊕ a
1
x
1
⊕ … ⊕a n
x Построение полинома Жегалкина с помощью таблицы истинности.
1. Составить таблицу истинности данной логической формулы или булевой функции.
2. Указать в таблице строки, где формула равна 1.
3. Для каждого набора значений переменных, на котором формула имеет значение 1, выписать конъюнкции всех переменных, причем над теми переменными, которые на этом наборе равны 0, ставятся отрицания.
4. Все полученные конъюнкции нужно соединить знаками ⊕ суммы по модулю 2.
5. Все отрицания заменяем эквивалентной формулой х∼х⊕1, раскрываем скобки и упрощаем, используя формулу х⊕х∼0. Пример 5.1. Представим в виде полинома Жегалкина дизъюнкцию f(x
1
,x
2
) = x
1
∨ x
2
f (x
1
,x
2
) = x
1
∨ x
2
∼ х ∧ x
2
⊕ x
1
∧ х ⊕ x
1
∧ x
2
∼ (х ⊕ 1) ∧ x
2
⊕ x
1
∧ (х ⊕ 1) ⊕
⊕ x
1
∧ x
2
∼ x
1
∧ x
2
⊕ х ⊕ x
1
∧ x
2
⊕ х ⊕ x
1
∧ x
2
∼ x
1
∧ x
2
⊕ х ⊕ х = x
1
x
2
⊕ х ⊕ х
2
Отметим сразу, что, как видим, дизъюнкция не является линейной функцией.
5.1. Полином Жегалкина Полиномом (многочленом) Жегалкина от n переменных называется функция f (x
1
,x
2
,…,x n
) = a
0
x
1
x
2
…x n
⊕ a
1
x
1
x
2
…x n−1
⊕ a
1
x
1
x
2
…x n−2
x n
⊕ … ⊕
⊕a m−n x
1
⊕ … ⊕a m−1
x n
⊕a Всего здесь 2
n слагаемых. Напомним, что ⊕ означает сложение по модулю 2, коэффициенты a i
являются константами (равными нулю или единице. Теорема 5.1. Любая функция n переменных может быть представлена полиномом Жегалкина и это представление единственно. Функция f(x
1
, x
2
,…, x n
) называется линейной, если ее полином Жегалкина содержит только первые степени слагаемых. Более точно функция называется линейной, если ее можно представить в виде f (x
1
, x
2
,…, x n
) = a
0
⊕ a
1
x
1
⊕ … ⊕a n
x Построение полинома Жегалкина с помощью таблицы истинности.
1. Составить таблицу истинности данной логической формулы или булевой функции.
2. Указать в таблице строки, где формула равна 1.
3. Для каждого набора значений переменных, на котором формула имеет значение 1, выписать конъюнкции всех переменных, причем над теми переменными, которые на этом наборе равны 0, ставятся отрицания.
4. Все полученные конъюнкции нужно соединить знаками ⊕ суммы по модулю 2.
5. Все отрицания заменяем эквивалентной формулой х∼х⊕1, раскрываем скобки и упрощаем, используя формулу х⊕х∼0. Пример 5.1. Представим в виде полинома Жегалкина дизъюнкцию f(x
1
,x
2
) = x
1
∨ x
2
f (x
1
,x
2
) = x
1
∨ x
2
∼ х ∧ x
2
⊕ x
1
∧ х ⊕ x
1
∧ x
2
∼ (х ⊕ 1) ∧ x
2
⊕ x
1
∧ (х ⊕ 1) ⊕
⊕ x
1
∧ x
2
∼ x
1
∧ x
2
⊕ х ⊕ x
1
∧ x
2
⊕ х ⊕ x
1
∧ x
2
∼ x
1
∧ x
2
⊕ х ⊕ х = x
1
x
2
⊕ х ⊕ х
2
Отметим сразу, что, как видим, дизъюнкция не является линейной функцией.
5.2. Проблема разрешимости Все формулы алгебры логики (алгебры высказываний) делятся натри класса тождественно истинные, тождественно ложные, выполнимые. Формулу алгебры логики называют выполнимой, если она принимает значение 1 (истина) хотя бы на одном наборе значений входящих в нее переменных и не является тождественно истинной. Проблема разрешимости может быть сформулирована следующим образом существует ли способ, который позволял бы для каждой формулы алгебры логики за конечное число шагов ответить на вопрос, к какому классу эта формула принадлежит Очевидно, что сама проблема разрешимости алгебры высказываний разрешима. Действительно, для каждой логической формулы может быть записана таблица истинности, которая и даст ответ на поставленный вопрос. Однако практическое использование таблицы истинности для формулы
А(х
1
,х
2
,...,x n
) при больших n затруднительно. Существует другой способ проверки к какому классу принадлежит данная формула, этот способ основан на приведении формулы к ДНФ и КНФ. Критерий разрешимости. Для того, чтобы формула алгебры логики А была тождественна истинна (тождественно ложна, необходимо и достаточно, чтобы любая элементарная дизъюнкция (конъюнкция, входящая в КНФ (ДНФ) формулы А, содержала переменную и ее отрицание. Пример 5.2. Будет ли формула Ах уху у тождественно истинной, тождественно ложной или выполнимой Решение. Приведем формулу А к ДНФ: х → уху уху х ∧ у ∨ уху х ∧ у ∨ уху х ∧ у ∨ у. Полученная ДНФ не является тождественно ложной, так как каждая элементарная конъюнкция не содержит переменную и ее отрицание. Следовательно, исходная формула тождественно истинна или выполнима. Преобразуем данную формулу к КНФ: (х → уху уху х ∧ у ∨ уху уху уху уху у) ∼ ух. Полученная КНФ не является тождественно истинной, так как элементарная дизъюнкция не содержит переменную и ее отрицание. Следовательно, заданная формула А выполнима.
5.3. Минимизация булевых функций в классе ДНФ Каждая формула имеет конечное число вхождений переменных. Под вхождением переменной понимается место, которое переменная занимает в формуле. Задача заключается в том, чтобы для данной булевой функции f найти
ДНФ, представляющую эту функцию и имеющую наименьшее число вхождений переменных.
Элементарным произведением называется конъюнкт, в который любая переменная входит не более одного раза. Пример 5.3. Формула x
2
x
3
x
4
— элементарное произведение, а формула x
1
x
2
x
1
x
3
элементарным произведением не является. Формула ϕ(x
1
,x
2
,...,x n
) называется импликантой формулы ψ(x
1
,x
2
,...,x n
), если ϕ — элементарное произведение и ϕ∧ψ ∼ ϕ, те. для соответствующих формулами функций f
ϕ
и f
ψ
справедливо неравенство f
ϕ
≤ Формула ϕ(x
1
,x
2
,...,x n
) называется импликантой функции f, если ϕ — импликанта совершенной ДНФ, представляющей функцию f.
Импликанта формулы ψ называется простой, если после отбрасывания любой литеры из формулы ϕ не получается формула, являющаяся импликантой формулы ψ. Пример 5.4. Найдем все импликанты и простые импликанты для формулы
ϕ(x,y) = x → y. Всего имеется 8 элементарных произведений с переменными x и y. Ниже приведены их таблицы истинности Из таблиц истинности заключаем, что формулы x y, xy, xy, x, y — все импликанты формулы ϕ, а из этих импликант простыми являются формулы x и y (формула x y, например, не является простой импликантой, поскольку отбрасывая литеру y, получаем импликанту x). Дизъюнкция всех простых импликант данной формулы (функции) называется сокращенной ДНФ. Теорема 5.2. Любая булева функция, не являющаяся константой 0, представима в виде сокращенной ДНФ. В примере 5.4. функция, соответствующая формуле x → y, представима формулой x ∨ y, которая и является ее сокращенной ДНФ. Сокращенная ДНФ может содержать лишние импликанты, удаление которых не меняет таблицы истинности. Если из сокращенной ДНФ удалить все лишние импликанты, то получается ДНФ, называемая тупиковой. Выбор из всех тупиковых форм формы с наименьшим числом вхождений переменных дает минимальную ДНФ (МДНФ). Рассмотрим метод Квайна для нахождения МДНФ, представляющей данную булеву функцию. Сначала определим следующие три операции
операция полного склеивания
операция неполного склеивания
2
x
3
x
4
— элементарное произведение, а формула x
1
x
2
x
1
x
3
элементарным произведением не является. Формула ϕ(x
1
,x
2
,...,x n
) называется импликантой формулы ψ(x
1
,x
2
,...,x n
), если ϕ — элементарное произведение и ϕ∧ψ ∼ ϕ, те. для соответствующих формулами функций f
ϕ
и f
ψ
справедливо неравенство f
ϕ
≤ Формула ϕ(x
1
,x
2
,...,x n
) называется импликантой функции f, если ϕ — импликанта совершенной ДНФ, представляющей функцию f.
Импликанта формулы ψ называется простой, если после отбрасывания любой литеры из формулы ϕ не получается формула, являющаяся импликантой формулы ψ. Пример 5.4. Найдем все импликанты и простые импликанты для формулы
ϕ(x,y) = x → y. Всего имеется 8 элементарных произведений с переменными x и y. Ниже приведены их таблицы истинности Из таблиц истинности заключаем, что формулы x y, xy, xy, x, y — все импликанты формулы ϕ, а из этих импликант простыми являются формулы x и y (формула x y, например, не является простой импликантой, поскольку отбрасывая литеру y, получаем импликанту x). Дизъюнкция всех простых импликант данной формулы (функции) называется сокращенной ДНФ. Теорема 5.2. Любая булева функция, не являющаяся константой 0, представима в виде сокращенной ДНФ. В примере 5.4. функция, соответствующая формуле x → y, представима формулой x ∨ y, которая и является ее сокращенной ДНФ. Сокращенная ДНФ может содержать лишние импликанты, удаление которых не меняет таблицы истинности. Если из сокращенной ДНФ удалить все лишние импликанты, то получается ДНФ, называемая тупиковой. Выбор из всех тупиковых форм формы с наименьшим числом вхождений переменных дает минимальную ДНФ (МДНФ). Рассмотрим метод Квайна для нахождения МДНФ, представляющей данную булеву функцию. Сначала определим следующие три операции
операция полного склеивания
операция неполного склеивания
операция элементарного поглощения – Теорема 5.3. (теорема Квайна). Если, исходя из совершенной ДНФ функции, произвести всевозможные операции неполного склеивания, а затем элементарного поглощения, тов результате получится сокращенная ДНФ, те. дизъюнкция всех простых импликант. Пример 5.5. Пусть функция f(x, y, z) задана совершенной ДНФ:
ϕ
= ????y???? ∨
∨ ????yz ∨ x????z ∨ xy???? ∨ xyz. Тогда, производя в два этапа всевозможные операции неполного склеивания, а затем элементарного поглощения, имеем Таким образом, сокращенной ДНФ функции f является формула y ∨ xz. На практике при выполнении операций неполного склеивания на каждом этапе можно не писать члены, участвующие в этих операциях, а писать только результаты всевозможных полных склеиваний и конъюнкты, не участвующие нив каком склеивании. Пример 5.6. Пусть функция f(x,y,z) задана совершенной ДНФ: ϕ = x y z ∨
∨ x y z ∨ xyz ∨ xyz. Тогда, последовательно производя операции склеивания, а затем элементарного поглощения, имеем ϕ ∼ x y(z ∨ z) ∨ yz(x ∨ x) ∨ xz(y ∨ y) ∼
∼ x y ∨ yz ∨ xz. Для получения минимальной ДНФ из сокращенной ДНФ используется матрица Квайна, которая строится следующим образом. В заголовках столбцов таблицы записываются конституенты единицы совершенной ДНФ, а в заголовках строк — простые импликанты из полученной сокращенной ДНФ. В таблице звездочками отмечаются те пересечения строки столбцов, для которых конъюнкт, стоящий в заголовке строки, входит в конституенту единицы, являющейся заголовком столбца. Для примера 5.6. матрица Квайна имеет вид В тупиковую ДНФ выбирается минимальное число простых импликант, дизъюнкция которых сохраняет все конституенты единицы, те. каждый
столбец матрицы Квайна содержит звездочку, стоящую на пересечении со строкой, соответствующей одной из выбранных импликант. В качестве минимальной ДНФ выбирается тупиковая, имеющая наименьшее число вхождений переменных. В примере 5.6. по матрице Квайна находим, что минимальная ДНФ заданной функции есть x y ∨ xz. В силу принципа двойственности для булевых алгебр все приведенные понятия и рассуждения очевидным образом можно преобразовать для нахождения минимальных конъюнктивных нормальных форм (МКНФ).
5.4. Карты Карно Для формул с малым числом переменных имеется другой способ получения простых импликант (и, значит, нахождения с помощью матрицы
Квайна минимальной ДНФ). Этот способ основан на использовании так называемых карт Карно. Рис. 5.1 Рис. 5.2 Карта Карно для n переменных служит эффективным средством иллюстративного представления куба. Она содержит 2
n ячеек, каждая из которых соответствует одной из 2
n возможных комбинаций значений n логических переменных x
1
, x
2
, ..., x n
. Карта строится в виде матрицы размера
2
n−k на 2
k так, что ее столбцы соответствуют значениям переменных x
1
, ..., x k
, строки — значениям переменных x k+1
, ..., x n
, а соседние ячейки (как по вертикали, таки по горизонтали) отличаются только значением одной переменной (рис. 5.1).
5.4. Карты Карно Для формул с малым числом переменных имеется другой способ получения простых импликант (и, значит, нахождения с помощью матрицы
Квайна минимальной ДНФ). Этот способ основан на использовании так называемых карт Карно. Рис. 5.1 Рис. 5.2 Карта Карно для n переменных служит эффективным средством иллюстративного представления куба. Она содержит 2
n ячеек, каждая из которых соответствует одной из 2
n возможных комбинаций значений n логических переменных x
1
, x
2
, ..., x n
. Карта строится в виде матрицы размера
2
n−k на 2
k так, что ее столбцы соответствуют значениям переменных x
1
, ..., x k
, строки — значениям переменных x k+1
, ..., x n
, а соседние ячейки (как по вертикали, таки по горизонтали) отличаются только значением одной переменной (рис. 5.1).
На рис. 5.2 приведены карты Карно для функций трех и четырех переменных соответственно. В этих картах все ячейки, отмеченные скобкой x по строке и столбцу, представляют входные комбинации с x i
= 1, а в неотмеченных строках и столбцах ячейки соответствуют комбинациям с x i
= 0 см. риса, на котором разными способами изображена одна и та же карта. Например, на риса ячейка a соответствует набору 001 значений переменных x
1
, x
2
, x
3
. Отметим, что для каждой функции может быть построено несколько различных карт. На рис. б изображены две карты Карно для функции четырех переменных. Первая карта соответствует разбиению переменных {{x1,x2},{x3,x4}}, а вторая — {{x1},{x2,x3,x4}}. У каждой вершины куба есть ровно n смежных с ней вершин, те. вершин, отличающихся от нее только одной координатой. Поскольку в карте Карно каждая ячейка может иметь не более четырех ячеек, соседних по строке или столбцу, для представления точек, отличающихся только на одну координату, необходимо использовать и более удаленные ячейки. Например, точки b и c на рис. б отличаются только значением переменной x
3
, те. являются смежными. Булева функция может быть представлена на карте Карно выделением 1- ячеек (те. ячеек, в которых функция принимает значение, равное 1). Подразумевается, что необозначенные ячейки соответствуют точкам. На рис. 5.3 изображена карта, представляющая булеву функцию f(x,y,z), для которой f(0,0,0) = f(1,1,0) = f(1,1,1) = f(1,0,1) = 0, f(0,1,0) = f(1,0,0) = f(0,0,1)=
= f(0,1,1) = 1. Для построения импликант берутся всевозможные наборы ячеек, образующих вершины некоторого куба те точек таких, что пары соседних отличаются ровно одной координатой. Совпадающие координаты образуют набор (δ
1
,...,δ
n−k
), и требуемая импликанта имеет вид Рис. 5.3 где x j
— переменная, соответствующая значению Пример 5.7. Точки b и c на рис. б лежат в кубе, который определяет конъюнкт ????
1
????
2
????
4
. Точки {d,e,f,g} образуют куб, представляющий импликанту Таким образом, определение простых импликант функции сводится к нахождению всех кубов, которые не содержатся в кубах более высокого порядка. Пример 5.8. Простые импликанты для карты Карно, приведенной на рис.
5.3, равны ????
1
x
2
, x
1
????
2
????
3
, Пример 5.9. На рис. 5.4 показана карта Карно, простые импликанты которой имеют вид x
2
????
3
????
4
, x
1
x
2
????
3
, x
1
????
3
x
4
, x
1
????
2
x
4
, ????
2
x
3
x
4
, ????
1
x
2
????
4
, ????
1
x
3
. Заметим, что импликанты ????
1
????
2
x
3
, ????
1
x
2
x
3
, ????
1
x
3
x
4
и ????
1
x
3
????
4
не являются простыми, так как образуемые ими кубы содержатся в кубе ????
1
x
3
= 1, а в неотмеченных строках и столбцах ячейки соответствуют комбинациям с x i
= 0 см. риса, на котором разными способами изображена одна и та же карта. Например, на риса ячейка a соответствует набору 001 значений переменных x
1
, x
2
, x
3
. Отметим, что для каждой функции может быть построено несколько различных карт. На рис. б изображены две карты Карно для функции четырех переменных. Первая карта соответствует разбиению переменных {{x1,x2},{x3,x4}}, а вторая — {{x1},{x2,x3,x4}}. У каждой вершины куба есть ровно n смежных с ней вершин, те. вершин, отличающихся от нее только одной координатой. Поскольку в карте Карно каждая ячейка может иметь не более четырех ячеек, соседних по строке или столбцу, для представления точек, отличающихся только на одну координату, необходимо использовать и более удаленные ячейки. Например, точки b и c на рис. б отличаются только значением переменной x
3
, те. являются смежными. Булева функция может быть представлена на карте Карно выделением 1- ячеек (те. ячеек, в которых функция принимает значение, равное 1). Подразумевается, что необозначенные ячейки соответствуют точкам. На рис. 5.3 изображена карта, представляющая булеву функцию f(x,y,z), для которой f(0,0,0) = f(1,1,0) = f(1,1,1) = f(1,0,1) = 0, f(0,1,0) = f(1,0,0) = f(0,0,1)=
= f(0,1,1) = 1. Для построения импликант берутся всевозможные наборы ячеек, образующих вершины некоторого куба те точек таких, что пары соседних отличаются ровно одной координатой. Совпадающие координаты образуют набор (δ
1
,...,δ
n−k
), и требуемая импликанта имеет вид Рис. 5.3 где x j
— переменная, соответствующая значению Пример 5.7. Точки b и c на рис. б лежат в кубе, который определяет конъюнкт ????
1
????
2
????
4
. Точки {d,e,f,g} образуют куб, представляющий импликанту Таким образом, определение простых импликант функции сводится к нахождению всех кубов, которые не содержатся в кубах более высокого порядка. Пример 5.8. Простые импликанты для карты Карно, приведенной на рис.
5.3, равны ????
1
x
2
, x
1
????
2
????
3
, Пример 5.9. На рис. 5.4 показана карта Карно, простые импликанты которой имеют вид x
2
????
3
????
4
, x
1
x
2
????
3
, x
1
????
3
x
4
, x
1
????
2
x
4
, ????
2
x
3
x
4
, ????
1
x
2
????
4
, ????
1
x
3
. Заметим, что импликанты ????
1
????
2
x
3
, ????
1
x
2
x
3
, ????
1
x
3
x
4
и ????
1
x
3
????
4
не являются простыми, так как образуемые ими кубы содержатся в кубе ????
1
x
3
После нахождения простых импликант задача построения минимальной
ДНФ сводится к изучению матрицы Квайна. При наглядном размещении простых импликант в карте Карно удается непосредственно находить минимальную ДНФ, выбирая те простые импликанты, которые покрывают все единицы и имеют наименьшее возможное число вхождений переменных. Так, минимальной
ДНФ для функции, изображенной на рис. 5.4, является формула x
2
????
3
????
4
∨ x
1
????
3
x
4
∨ x
1
????
2
x
4
∨ ????
1
x
3
Рис. 5.4 Карты Карно применимы и для не всюду определенных функций. В этом случае выделяются x
1
максимальные кубы, покрывающие ненулевые ячейки и содержащие хотя бы одну единицу. Пример 5.10. На рис. 5.5 представлена карта Карно для частичной функции f, зависящей от трех переменных x
1
,x
2
,x
3
. Сокращенная ДНФ имеет вида МДНФ имеет вид ????
2
????
3
∨ x
1
????
3
∨ x
2
x
3
или ????
2
????
3
∨
∨ x
1
x
2
∨ x
2
x
3
Рис. 5.5 5.5. Замыкание набора функций. Базисы Пусть имеется некоторый набор (система) K, состоящий из конечного числа булевых функций. Суперпозицией функций из этого набора называется новая функция, полученная с помощью конечного числа применения двух операций можно переименовать любую переменную, входящую в функцию из
K; вместо любой переменной можно поставить функцию из набора K или уже образованную ранее суперпозицию. Суперпозицию еще иначе называют сложной функцией. Пример 5.11. Если дана одна функциях (штрих Шеффера), то ее суперпозициями, в частности, будут следующие функции x|x, x|(x|y), x|(y|z). Замыканием набора функций из K называется множество всех суперпозиций. Класс функций K называется замкнутым, если его замыкание совпадает с ним самим. Набор функций называется полным, если его замыкание совпадает со всеми логическими функциями. Иначе говоря, полный набор – это множество таких функций, через которые можно выразить все остальные булевы функции.
Неизбыточный полный набор функций называется базисом
(“неизбыточный” в этом определении означает, что если какую-то функцию удалить из набора, то этот набор перестанет быть полным.
ДНФ сводится к изучению матрицы Квайна. При наглядном размещении простых импликант в карте Карно удается непосредственно находить минимальную ДНФ, выбирая те простые импликанты, которые покрывают все единицы и имеют наименьшее возможное число вхождений переменных. Так, минимальной
ДНФ для функции, изображенной на рис. 5.4, является формула x
2
????
3
????
4
∨ x
1
????
3
x
4
∨ x
1
????
2
x
4
∨ ????
1
x
3
Рис. 5.4 Карты Карно применимы и для не всюду определенных функций. В этом случае выделяются x
1
максимальные кубы, покрывающие ненулевые ячейки и содержащие хотя бы одну единицу. Пример 5.10. На рис. 5.5 представлена карта Карно для частичной функции f, зависящей от трех переменных x
1
,x
2
,x
3
. Сокращенная ДНФ имеет вида МДНФ имеет вид ????
2
????
3
∨ x
1
????
3
∨ x
2
x
3
или ????
2
????
3
∨
∨ x
1
x
2
∨ x
2
x
3
Рис. 5.5 5.5. Замыкание набора функций. Базисы Пусть имеется некоторый набор (система) K, состоящий из конечного числа булевых функций. Суперпозицией функций из этого набора называется новая функция, полученная с помощью конечного числа применения двух операций можно переименовать любую переменную, входящую в функцию из
K; вместо любой переменной можно поставить функцию из набора K или уже образованную ранее суперпозицию. Суперпозицию еще иначе называют сложной функцией. Пример 5.11. Если дана одна функциях (штрих Шеффера), то ее суперпозициями, в частности, будут следующие функции x|x, x|(x|y), x|(y|z). Замыканием набора функций из K называется множество всех суперпозиций. Класс функций K называется замкнутым, если его замыкание совпадает с ним самим. Набор функций называется полным, если его замыкание совпадает со всеми логическими функциями. Иначе говоря, полный набор – это множество таких функций, через которые можно выразить все остальные булевы функции.
Неизбыточный полный набор функций называется базисом
(“неизбыточный” в этом определении означает, что если какую-то функцию удалить из набора, то этот набор перестанет быть полным.
Пример 5.12. Конъюнкция, дизъюнкция и отрицание (вместе) являются полным набором, ноне являются базисом, так как этот набор избыточен, поскольку с помощью правил де Моргана можно удалить, например, конъюнкцию или дизъюнкцию. Согласно теореме 5.1 любую функцию можно представить в виде полинома Жегалкина. Ясно, что набор функций конъюнкция, сложение по модулю 2 и константы 0 и 1 является полным набором, но эти четыре функции также не являются базисом, поскольку 1+1=0, и поэтому константу 0 можно исключить из полного набора (однако, для построения полиномов Жегалкина константа 0 необходима, поскольку выражение “1+1” не является полиномом
Жегалкина). Легко увидеть, что одним из способов проверки полноты какого-то набора К является проверка того, что через функции из этого набора выражаются функции другого полного набора (можно проверить, что через функции из К можно выразить конъюнкцию и отрицание или дизъюнкцию и отрицание. Существуют такие функции, что одна такая функция сама является базисом (здесь достаточно проверить только полноту, неизбыточность очевидна. Такие функции называются шефферовскими функциями. Это название связано стем, что штрих Шеффера является базисом. Напомним, что штрих Шеффера определяется следующей таблицей истинности
(не итак как очевидно x|x
= ???? , те. отрицание является суперпозицией штриха Шеффера, как и дизъюнкция x
∨y = ????|???? =(x|y)|(x|y), значит, штрих Шеффера сам является базисом. Аналогично, стрелка Пирса является шефферовской функцией. Для функций х или более переменных шефферовских функций очень много конечно, выражение других булевых функций через шефферовскую функцию большого числа переменных сложно, поэтому в технике они редко используются. Заметим, что вычислительное устройство чаще всего базируется на полном наборе функций (часто на базисах. Если в основе устройства лежат конъюнкция, дизъюнкция и отрицание, то для этих устройств важна проблема минимизации ДНФ; если в основе устройства лежат другие функции, то полезно уметь алгоритмически минимизировать выражения через эти функции. Перейдем теперь к выяснению полноты конкретных наборов функций. Для этого перечислим 5 важнейших классов функций, называемых классами Поста
1. Т – это набор всех тех логических функций, которые на нулевом наборе принимают значение 0 (Т – это класс функций, сохраняющих нуль. Те. Т – набор функций f(x
1
,...,x n
), для которых f(0,0,...,0) = 0: Т
= {f | f(0,0,...,0) =
= 0}.
2. Т – это набор всех логических функций, которые на единичном наборе принимают значение 1 (Т – это класс функций, сохраняющих единицу, те. Т
= {f | f(1,1,...,1) = 1} (заметим, что число функций от п переменных принадлежащих классам Т и Т равно 2 2n-1
).
3.
L – класс линейных функций, те. функций, для которых полином
Жегалкина содержит только первые степени переменных (число линейных функций n переменных равно п. Замечание. Если n≥ 2, то линейная функция в таблице истинности может содержать только четное число единиц. Действительно, если f(x
1
,x
2
,
,x n
)
= x
1
⊕ x
2
⊕
⊕ x n
, то легко видеть, что такая функция в таблице истинности содержит одинаковое число нулей и единица именно
2
n
/2
единиц и нулей. Добавление фиктивной переменной приводит к увеличению числа единиц (и нулей) в два раза. Нелинейная функция может иметь в таблице истинности как четное, таки нечетное число единиц.
4. Класс S – класс самодвойственных функций. Функция п переменных называется самодвойственной, если на противоположных наборах она принимает противоположные значения, те. самодвойственная функция f(x
1
,x
2
,
,x n
)
удовлетворяет условию f(x
1
,x
2
,...,x n
)
=
????(????1, ????2, . . . , Замечание. Таблица истинности самодвойственной функции не должна быть симметрична ни для одного набора значений переменных.
5. М – класс монотонных функций. Опишем класс этих функций более подробно. Пусть имеются 2 набора из п переменных s
1
= (х, х, х пи п. Будем говорить, что набор s
1 меньше набора s
2
, если все x
i
≤ y i
. Очевидно, что не все наборы из п переменных сравнимы между собой (например, при п наборы (0,1) и (1,0) несравнимы между собой. Функция от п переменных называется монотонной, если на меньшем наборе она принимает меньшее или равное значение s
1
2
f(
s
1
)
≤ f(
s
2
). Разумеется, эти неравенства должны проверяться только на сравнимых наборах. Пример 5.13. В нижеследующей таблице функции f
1
, f
2 являются монотонными функциями, а функции f
3
, f
4
– нет. Функции f
1
, f
2
являются самодвойственными, а функции f
3,
f
4
не являются.
Жегалкина). Легко увидеть, что одним из способов проверки полноты какого-то набора К является проверка того, что через функции из этого набора выражаются функции другого полного набора (можно проверить, что через функции из К можно выразить конъюнкцию и отрицание или дизъюнкцию и отрицание. Существуют такие функции, что одна такая функция сама является базисом (здесь достаточно проверить только полноту, неизбыточность очевидна. Такие функции называются шефферовскими функциями. Это название связано стем, что штрих Шеффера является базисом. Напомним, что штрих Шеффера определяется следующей таблицей истинности
(не итак как очевидно x|x
= ???? , те. отрицание является суперпозицией штриха Шеффера, как и дизъюнкция x
∨y = ????|???? =(x|y)|(x|y), значит, штрих Шеффера сам является базисом. Аналогично, стрелка Пирса является шефферовской функцией. Для функций х или более переменных шефферовских функций очень много конечно, выражение других булевых функций через шефферовскую функцию большого числа переменных сложно, поэтому в технике они редко используются. Заметим, что вычислительное устройство чаще всего базируется на полном наборе функций (часто на базисах. Если в основе устройства лежат конъюнкция, дизъюнкция и отрицание, то для этих устройств важна проблема минимизации ДНФ; если в основе устройства лежат другие функции, то полезно уметь алгоритмически минимизировать выражения через эти функции. Перейдем теперь к выяснению полноты конкретных наборов функций. Для этого перечислим 5 важнейших классов функций, называемых классами Поста
1. Т – это набор всех тех логических функций, которые на нулевом наборе принимают значение 0 (Т – это класс функций, сохраняющих нуль. Те. Т – набор функций f(x
1
,...,x n
), для которых f(0,0,...,0) = 0: Т
= {f | f(0,0,...,0) =
= 0}.
2. Т – это набор всех логических функций, которые на единичном наборе принимают значение 1 (Т – это класс функций, сохраняющих единицу, те. Т
= {f | f(1,1,...,1) = 1} (заметим, что число функций от п переменных принадлежащих классам Т и Т равно 2 2n-1
).
3.
L – класс линейных функций, те. функций, для которых полином
Жегалкина содержит только первые степени переменных (число линейных функций n переменных равно п. Замечание. Если n≥ 2, то линейная функция в таблице истинности может содержать только четное число единиц. Действительно, если f(x
1
,x
2
,
,x n
)
= x
1
⊕ x
2
⊕
⊕ x n
, то легко видеть, что такая функция в таблице истинности содержит одинаковое число нулей и единица именно
2
n
/2
единиц и нулей. Добавление фиктивной переменной приводит к увеличению числа единиц (и нулей) в два раза. Нелинейная функция может иметь в таблице истинности как четное, таки нечетное число единиц.
4. Класс S – класс самодвойственных функций. Функция п переменных называется самодвойственной, если на противоположных наборах она принимает противоположные значения, те. самодвойственная функция f(x
1
,x
2
,
,x n
)
удовлетворяет условию f(x
1
,x
2
,...,x n
)
=
????(????1, ????2, . . . , Замечание. Таблица истинности самодвойственной функции не должна быть симметрична ни для одного набора значений переменных.
5. М – класс монотонных функций. Опишем класс этих функций более подробно. Пусть имеются 2 набора из п переменных s
1
= (х, х, х пи п. Будем говорить, что набор s
1 меньше набора s
2
, если все x
i
≤ y i
. Очевидно, что не все наборы из п переменных сравнимы между собой (например, при п наборы (0,1) и (1,0) несравнимы между собой. Функция от п переменных называется монотонной, если на меньшем наборе она принимает меньшее или равное значение s
1
f(
s
1
)
≤ f(
s
2
). Разумеется, эти неравенства должны проверяться только на сравнимых наборах. Пример 5.13. В нижеследующей таблице функции f
1
, f
2 являются монотонными функциями, а функции f
3
, f
4
– нет. Функции f
1
, f
2
являются самодвойственными, а функции f
3,
f
4
не являются.
x y f
1
f
2
f
3
f
4 0
0 0 0 0 1 0
1 1 0 1 0 1
0 0 1 1 0 1
1 1 1 0 1 Замечание. Естественный порядок переменных обеспечивает тот факт, что если какой-то набор меньше другого набора, то он обязательно расположен в таблице истинности выше большего набора. Поэтому если в таблице истинности (при естественном порядке набора переменных) вверху стоят нули, а затем единицы, то эта функция точно является монотонной. Однако возможны инверсии, те. единица стоит до каких-то нулей, но функция является все равно монотонной. В этом случае наборы, соответствующие верхней единице и нижнему нулю должны быть несравнимы. Можно проверить, что функция, задаваемая таблицей истинности при естественном порядке набора переменных (00010101), является монотонной. Пример 5.14. Определим, к каким классам Поста относится булева функция f(x,y) = x|y. Так как f(0,0) = 1, а f(1,1) = 0, то f(x,y) ∉ Т и f(x,y) ∉ Т
1
Поскольку f(1,0) ≠ f(0,1), то f(x,y) ∉ S. Так как f(0,0) > f(1,1), то f(x,y) ∉ M. Полином Жегалкина для функции f(x,y) = xy имеет вид 1⊕xy в силу равенства x = 1⊕x. Поэтому данная функция нелинейна. Таким образом, можно составить таблицу принадлежности штриха Шеффера к классам Поста Функция Классы
Т
0
Т
1
L
S
M x|y нет нет нет нет нет Теорема 5.4. Классы функций Т, Т, L, M, S замкнуты. Эта теорема следует непосредственно из определения самих этих классов, а также из определения замкнутости. Таким образом, каждый класс Поста замкнут относительно операций замены переменных и суперпозиции, тес помощью этих операций из функций, принадлежащих данному классу, можно получить только функции из этого же класса. В теории булевых функций очень большое значение имеет теорема Поста, так как она дает ответ на вопрос о полноте произвольной системы. Теорема 5.5. (Теорема Поста. Для того, чтобы некоторый набор функций K был полным, необходимо и достаточно, чтобы для каждого из классов T
0
, T
1
, L, M, S в этот набор входила функция, не принадлежащая этому классу. Заметим, что необходимость в этой теореме очевидна, так как, если бы все функции из набора К входили в один из перечисленных классов, то и все
1
f
2
f
3
f
4 0
0 0 0 0 1 0
1 1 0 1 0 1
0 0 1 1 0 1
1 1 1 0 1 Замечание. Естественный порядок переменных обеспечивает тот факт, что если какой-то набор меньше другого набора, то он обязательно расположен в таблице истинности выше большего набора. Поэтому если в таблице истинности (при естественном порядке набора переменных) вверху стоят нули, а затем единицы, то эта функция точно является монотонной. Однако возможны инверсии, те. единица стоит до каких-то нулей, но функция является все равно монотонной. В этом случае наборы, соответствующие верхней единице и нижнему нулю должны быть несравнимы. Можно проверить, что функция, задаваемая таблицей истинности при естественном порядке набора переменных (00010101), является монотонной. Пример 5.14. Определим, к каким классам Поста относится булева функция f(x,y) = x|y. Так как f(0,0) = 1, а f(1,1) = 0, то f(x,y) ∉ Т и f(x,y) ∉ Т
1
Поскольку f(1,0) ≠ f(0,1), то f(x,y) ∉ S. Так как f(0,0) > f(1,1), то f(x,y) ∉ M. Полином Жегалкина для функции f(x,y) = xy имеет вид 1⊕xy в силу равенства x = 1⊕x. Поэтому данная функция нелинейна. Таким образом, можно составить таблицу принадлежности штриха Шеффера к классам Поста Функция Классы
Т
0
Т
1
L
S
M x|y нет нет нет нет нет Теорема 5.4. Классы функций Т, Т, L, M, S замкнуты. Эта теорема следует непосредственно из определения самих этих классов, а также из определения замкнутости. Таким образом, каждый класс Поста замкнут относительно операций замены переменных и суперпозиции, тес помощью этих операций из функций, принадлежащих данному классу, можно получить только функции из этого же класса. В теории булевых функций очень большое значение имеет теорема Поста, так как она дает ответ на вопрос о полноте произвольной системы. Теорема 5.5. (Теорема Поста. Для того, чтобы некоторый набор функций K был полным, необходимо и достаточно, чтобы для каждого из классов T
0
, T
1
, L, M, S в этот набор входила функция, не принадлежащая этому классу. Заметим, что необходимость в этой теореме очевидна, так как, если бы все функции из набора К входили в один из перечисленных классов, то и все
суперпозиции, а значит, и замыкание набора входило бы в этот класс, и класс К не мог быть полным. Достаточность этого утверждения доказывается довольно сложно, поэтому здесь не приводится. В силу теоремы Поста функция x|y образует полную систему, тес помощью штриха Шеффера можно получить любую булеву функцию. Из теоремы Поста следует довольно простой способ выяснения полноты некоторого набора функций. Для каждой из этих функций выясняется принадлежность к перечисленным выше классам. Результаты заносятся в так называемую таблицу Поста, где знак “+” означает принадлежность функции соответствующему классу, знак “–” означает, что функция в него не входит. В соответствии с теоремой Поста набор функций будет полным тогда и только тогда, когда в каждом столбце таблицы Поста имеется хотя бы один минус. Таким образом, из приведенной таблицы следует, что данные 4 функции образуют полный набор, но эти функции не являются базисом. Из этих функций можно образовать 2 базиса f
3
, f
1 и f
3
, f
2
. Полными наборами будут любые наборы, содержащие какой-либо базис. Непосредственно из таблицы Поста следует, что число базисных функций не может быть больше 5. На самом деле это число меньше или равно 4, что подтверждается следующей теоремой. Теорема 5.6. Каждый базис содержит не более четырех булевых функций.
Пример 5.15. Следующие системы булевых функций являются базисами
{∧,¬}, {∨,¬}, {→,¬}, {↓}, {|}, {↔,∨,0}, {⊕,∧,↔}. Широкий набор базисов открывает большие возможности при решении задач минимизации схем устройств дискретного действия, поскольку из базисных схем с помощью суперпозиций можно составить схему, соответствующую любой булевой функции.
3
, f
1 и f
3
, f
2
. Полными наборами будут любые наборы, содержащие какой-либо базис. Непосредственно из таблицы Поста следует, что число базисных функций не может быть больше 5. На самом деле это число меньше или равно 4, что подтверждается следующей теоремой. Теорема 5.6. Каждый базис содержит не более четырех булевых функций.
Пример 5.15. Следующие системы булевых функций являются базисами
{∧,¬}, {∨,¬}, {→,¬}, {↓}, {|}, {↔,∨,0}, {⊕,∧,↔}. Широкий набор базисов открывает большие возможности при решении задач минимизации схем устройств дискретного действия, поскольку из базисных схем с помощью суперпозиций можно составить схему, соответствующую любой булевой функции.