Полные системы булевых функций

СОДЕРЖАНИЕ

1. Полные системы булевых функций

2. Сокращенные и тупиковые дизъюнктивные нормальные формы

3. Алгоритм Квайна и Мак-Класки минимизации булевой функции

4. Геометрическое представление логических функций

5. Геометрический метод минимизации булевых функций        

6. Минимизация булевой функции с помощью карты Карно

7. Построение оптимальных контактно-релейных схем

Упражнения

Библиографический список

Полные системы булевых функций

Напомним, что булевой функцией называют функцию , у которой все независимые аргументы  и сама функция являются логическими переменными, принимающими только два значения: 0 и 1. Эти функции могут быть заданы аналитически в виде пропозициональной формулы (ПФ) геометрически или с помощью таблиц истинности. Например, все элементарные булевы функции двух переменных представлены таблицей истинности 1.

Таблица 1

№	X1= 0 X2= 0	0 1	1 0	1 1	fk (X1, X2)
1	0	0	0	0	f1 = 0
2	0	0	0	1
3	0	0	1	0
4	0	0	1	1
5	0	1	0	0
6	0	1	0	1
7	0	1	1	0
8	0	1	1	1
9	1	0	0	0
10	1	0	0	1
11	1	0	1	0
12	1	0	1	1
13	1	1	0	0
14	1	1	0	1
15	1	1	1	0
16	1	1	1	1

Функция f₁ называется нулевой; f₁₆ – единичной; f₂ – конъюнкцией; f₈ – дизъюнкцией; f₁₁ и f₁₃ – отрицаниями Х₁ и Х₂ соответственно; f₁₂ и f₁₄ – импликациями; f₃ и f₅ – коимпликациями; f₁₀ – эквиваленцией; f₇ – сложением по модулю два или разделительной дизъюнкцией; f₉ – стрелкой Пирса (функцией Вебба); f₁₅ – штрихом (функцией) Шеффера.

Функцию, полученную из элементарных путем перенумерации аргументов и подстановки вместо аргументов в некоторых других булевых функций, называют суперпозицией функций. Нетрудно убедиться, что любая булева функция от n аргументов является суперпозицией элементарных функций, заданных табл. 1. Например, функция

является суперпозицией элементарных функций: отрицания, дизъюнкции, конъюнкции и импликации.

Система булевых функций называется полной, если любая булева функция является суперпозицией этих функций.

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

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

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

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

Согласно этому определению система булевых функций  не является базисом. Действительно, применяя законы де-Моргана

, ,

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

Для проверки полноты заданной системы булевых функций может быть использовано следующее очевидное утверждение:

Если система  - полная и любая из функций f₁, f₂,...,f_m может быть выражена с помощью суперпозиций через функции g₁, g₂,…, g_k, то система  также полная.

Пример 1. Доказать полноту системы .

Для доказательства воспользуемся системой , полнота которой уже доказана, эти функции можно выразить через g₁ и g₂ по формулам:

f₁=g₁, ,

следовательно система функций  является полной.

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

Функция f = (Х₁,Х₂,...,Х_n) называется функцией, сохраняющей константу 0 (1 ), если

f(0,0, ...0) = 0, (f(l, 1....1) = 1).

Функция f (X₁,X₂,...,X_n) называется самодвойственной, если

f (X₁,X₂,..., X_n) = .

Функция f (X₁,X₂,...,X_n) называется монотонной, если для любых двух наборов X = (X₁,X₂,…,X_n) и Y = (Y_l, Y₂,...,Y_n), таких, что X Y (для любого i X_i Y_i) имеет место неравенство:

f (X₁,X₂,..., X_n)  f (Y_l, Y₂,...,Y_n).

Функция f (X₁,X₂,..., X_n) называется линейной, если

f (X₁,X₂,..., X_n) = ,

где .

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

Например, из табл. 1 следует, что f₂ = X₁ÙX₂ и f₈ = X₁ÚX₂ – функции, сохраняющие константу 0; f₁₀ = X₁↔X₂ – функция, не сохраняющая константу 0, но сохраняющая константу 1; f₇ = X₁ X₂ - несамодвойственная функция; f₂, f_g – монотонные функции; f₁₄ = X₁→X₂ – немонотонная функция, так как монотонность нарушается на набоpax (0, 0) и (1, 0); f₃ - нелинейная функция, так как соответствующий ей многочлен Жегалкина X₁ + X₂ + X₁X₂ – нелинеен.

Теорема Поста. Система D = {f₁, f₂, ... f_m} булевых функций является полной тогда и только тогда, когда среди функций этой системы существуют: функция, не сохраняющая константу 0, функция, не сохраняющая константу 1, а также нелинейная, несамодвойственная и немонотонная функции.

Пример 2. Доказать полноту системы .

Решение. Пусть K₀ – класс функций, сохраняющих константу 0; К₁ – класс функций, сохраняющих константу 1; К_л, K_c, К_м – классы линейных, самодвойственных и монотонных функций соответственно.

Составим таблицу Поста следующего вида.

Таблица 2

№	φi	K0	К1	Кл	Kc	Км
1	X1  X2	+	–	+	–	–
2	X1 Ú X2	+	+	–	–	+
3	1	–	+	+	–	–

Знак "+",стоящий на пересечении i- й строки и j-гo столбца этой таблицы, показывает, что функция φ_i – принадлежит соответствующему классу, записанному в j-ом столбце,

Из табл. 1 видим, что φ₁ = f₇не сохраняет константу 1 и не является монотонной, φ₂=f₈ – нелинейная и несамодвойственная функция, φ₃ = f₁₆ не сохраняет константу 0. Следовательно, все условия теоремы Поста выполнены, и заданная система  является полной.

Пример 3. Доказать, что система {|} является базисом.

Решение. Рассматриваемая система состоит из одной функции f₁₅ (функции Шеффера). Из табл. 1 видим, что f₁₅ – функция, не сохраняющая 0 и 1, немонотонная (монотонность нарушается на наборах (1, 0) и (1, 1),несамодвойственная, так как , a двойственная функция  нелинейная, так как многочлен Жегалкина для этой функции имеет вид: 1 + X₁X₂. Следовательно, система {f₁₅} = {|} удовлетворяет всем условиям теоремы Поста и является базисом.

Исследуя различные наборы функций, можно показать, что для множества булевых функций двух переменных существуют 17 различных базисов, в каждом из которых нельзя вычеркнуть ни одну функцию без потери полноты. Наиболее распространенными из них являются конъюнктивный базис Буля , дизъюнктивный базис Буля . импликативныи базис . базис Шеффера {|}, базис Жегалкина .

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