Построение формул алгебры логики по заданной таблице истинности

3.6 Построение формул алгебры логики по заданной таблице истинности

Пусть F – двоичная функция от n переменных. Предположим, что F не равна тождественно нулю. Пусть T₁, T₂,…, T_k – все точки ее определения, в которых F=1. Можно доказать, что справедлива следующая формула:

,

где , j=1,2,…, k,

Построить функцию F можно и по-другому. Если функция F не равна тождественно единице и S₁, S₂,…, S_m – все точки области ее определения, в которых F=0, то справедлива формула:

,

где , j=1,2,…, m.

Из приведенных формул видно, что любую двоичную функцию можно записать, используя лишь операции ¬, , .

Основная конъюнкция – это конъюнкция основных высказываний переменных или их отрицаний. Например, .

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

Конъюнктивной нормальной формой (КНФ) данной формулы называется формула, равносильная данной и представленная в виде конъюнкции основных дизъюнкций. Например, (A+B) (A+C+B) (D+A).

Дизъюнктивной нормальной формой (ДНФ) данной формулы называется формула, равносильная данной и представленная в виде дизъюнкции основных конъюнкций. Например, AB+C+AC.

Теорема 1. Для того чтобы формула алгебры высказываний была тождественно истинной, необходимо и достаточно, чтобы ее КНФ содержала в каждой элементарной дизъюнкции некоторое высказывание и его отрицание.

Теорема 2. Для того чтобы формула алгебры высказываний была тождественно ложной, необходимо и достаточно, чтобы ее ДНФ содержала в каждой элементарной конъюнкции некоторое высказывание и его отрицание.

Совершенные дизъюнктивные, конъюнктивные и полиномиальные нормальные формы представления переключательных (логических) функций. Многообразие формул, посредством которых может быть выражена любая логическая функция, определяет многообразие форм логических функций, т. е. способов их записи путем применения к переменным и их группам элементарных логических операций. Наиболее удобными для практического использования оказываются совершенные нормальные формы представления сложных логических функций. В алгебре логики доказывают, что любая логическая функция F (A, B, C,…, N) может быть представлена только одной совершенной дизъюнктивной нормальной формой (кроме константы нуль) или только одной совершенной конъюнктивной нормальной формой (кроме константы единица).

Пусть функция X=F (A, B, C) задана таблицей 4. Запись функции Х в виде логической суммы (дизъюнкции) логических произведений (конъюнкций) переменных, для которых значение функции Х равно 1, и является совершенной дизъюнктивной нормальной формой (СДНФ) представления логической функции.

Таблица 4

A	B	C	X
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

СДНФ логической функции следует находить в такой последовательности:

1) составить произведения переменных для строк таблицы истинности, в которых Х равна 1. Если значение переменной (А, В или С) в строке равно 0, то в произведении записывается отрицание этой переменной;

2) написать сумму произведений, для которых функция Х равна 1. Полученная сумма и является СДНФ. В общем виде

, (1)

Это правило называют правилом записи переключательной функции по единицам. Согласно этому правилу, данные табл. 4 описываются аналитическим выражением, связывающим все наборы переменных, для которых Х=1, в виде:

. (2)

Запись функции Х в виде логического произведения (конъюнкции) логических сумм (дизъюнкций) переменных, для которых функция Х равна 0, является совершенной конъюнктивной нормальной формой (СКНФ) представления логической функции.

Для табл. 4 аналитическое выражение в СДНФ, связывающее все наборы переменных, для которых Х=0, имеет вид:

. (3)

Для представления логической функции Х в СКНФ произведем операцию отрицания левой и правой частей равенства (3)

и на основании законов двойного отрицания и инверсии

. (4)

СКНФ логической функции, согласно (4), следует находить в такой последовательности:

1) составить логические суммы переменных для строк таблицы истинности, в которых функция Х равна 0. Если значение переменной (А, В или С) в строке равно 1, то в сумме записывается отрицание этой переменной;

2) написать логическое произведение составленных логических сумм. Полученное произведение и является СКНФ. В общем виде:

, (5)

где F_i – сложные дизъюнкции.

Это правило также называют правилом построения переключательной функции по нулям.

Кроме представления функций в виде СДНФ и СКНФ используют и совершенную полиномиальную нормальную форму СПНФ. Вместо дизъюнкции может быть записана функция сложения по модулю два (сумма Жегалкина):

, (6)

где F_i – сложные конъюнкции.

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

Нормальные формы представления переключательной функции иногда называют стандартными (табл. 5).

Таблица 5

f	A 0011 B 0101	Название функции	Обозначение функции	СДНФ	СКНФ
f0	0000	Константа нуль	0	Не имеет
f1	0001	Логическое произведение, конъюнкция
f2	0010	Функция запрета по В
f3	0011	Переменная А
f4	0100	Функция запрета по А
f5	0101	Переменная В
f6	0110	Сумма по мо дулю 2, логическая неравнозначность
f7	0111	Логическое сложение, дизъюнкция
f8	1000	Операция (стрелка) Пирса, операция Вебба
f9	1001	Эквивалентность, логическая равнозначность
f10	1010	Инверсия В
f11	1011	Импликация от В к А
f12	1100	Инверсия А
f13	1101	Импликация от А к В
f14	1110	Операция (штрих) Шеффера
f15	1111	Константа единица	1		Не имеет

Многочленом Жегалкина называется многочлен, являющийся суммой константы 0 или 1 и различных одночленов, в которые все переменные входят не выше, чем в первой степени.

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

J =.

Представим, например, в виде полинома выражение вида X₁X₂. Для этого проведем следующие рассуждения.

Пусть

 

X₁X₂ = aX₁X₂+bX₁+cX₂+k,

где а, b, с, k – неопределенные коэффициенты.

При X₁ = X₂ = 0 имеем k = 0. При Х₁ = 1, X₂= 0 имеем b= 1. При Х₁= 0, Х₂= 1 имеем с= 1. При X₁=Х₂= 1 имеем а + b + с = 1, т. е. а = -1. Таким образом, получаем:

 

X₁X₂ = – X₁X₂+ X₁+ X₂.

СПНФ образуется путем замены в СДНФ:  на + и  на

1  х.

,

,

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

.

Подобное упрощение, которое называется минимизацией логической функции, можно осуществить и по отношению к СДНФ и СКНФ.

Таблица 6

			y
0	0	0	0
1	0	0	1
0	1	0	0
1	1	0	1
0	0	1	1
1	0	1	0
0	1	1	0
1	1	1	1

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

,

и для СКНФ, т. е. минимальную КНФ:

.

После того, как найдены минимальные нормальные формы (МНФ), их рекомендуется проверить на всех наборах аргументов . Переменные  или  часто называют термами. Именно полный набор из n термов образует конституенту. В процессе же минимизации некоторые термы из конституент пропадут. Тогда оставшуюся часть дизъюнкта или конъюнкта называют импликантой.

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

Контрольные вопросы и упражнения

1. Дайте определение логической функции многих переменных.

2. Что такое вектор значений булевой функции? Приведите пример построения таблицы истинности логической функции многих переменных.

3. Сколько существует булевых функций от n переменных?

4. Что такое ДНФ и КНФ?

5. Каков алгоритм построения СДНФ? Приведите пример построения СДНФ.

6. Каков алгоритм построения СКНФ? Приведите пример построения СКНФ.

7. Составьте СКНФ и СДНФ для функции .

8. Приведите пример построения СПНФ.

3.7 Некоторые замкнутые классы (классы Поста). Понятие базиса

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

Пусть К⁰={f₁(x_1,…,x_k1), f₂(x_1,…,x_k2),…, f_m(x_1,…,x_km)} – конечная система булевых функций. Функция f называется элементарной суперпозицией (суперпозицией ранга 1) функций f₁, f₂,…, f_m, если f может быть получена одним из следующих способов:

а) переименованием некоторой переменной x_j какой-нибудь функции f_i;

б) подстановкой некоторой функции  вместо какой-либо переменной x_j любой из функций .

Суперпозиции ранга 1 образуют класс функций К¹. Класс функций, получающийся из функций класса K^s-1 суперпозицией ранга s‑1 с помощью элементарных суперпозиций, называется классом функций K^s суперпозиций ранга s. Суперпозициями функций из К⁰ называются функции, входящие в какой-то из классов K^s.

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

В современном компьютере цифрами являются ноль и единица. Следовательно, команды, которые выполняет процессор, суть булевы функции. Мы уже видели, что любая булева функция реализуется через конъюнкцию, дизъюнкцию и отрицание. Следовательно, можно построить нужный процессор, имея в распоряжении элементы, реализующие . Далее рассмотрим вопрос: существуют ли (и если существуют, то какие) другие системы булевых функций, обладающие тем свойством, что с их помощью можно выразить все другие функции. Рассмотрим некоторые замкнутые классы (классы Поста), их пять.

1. Класс функций, сохраняющих константу нуль (обозначается T₀ или P₀):

 

T₀:={f | f (0,0,…, 0)=0}.

К этому классу относятся, например, функции ; ; ; .

2. Класс функций, сохраняющих константу единица (обозначается T₁ или P₁):

 

T₁:={f | f (1,1,…, 1)=1}.

К нему относятся все нечетные функции.

3. Класс самодвойственных функций (обозначается T_* или S):

T_*:={f | f^*};

Пример  и .

Функция  называется двойственной по отношению к функции , если . Двойственная функция получается из исходной при замене значений всех переменных, а также значений функции на противоположные, т. е. в таблице истинности нужно заменить 0 на 1, 1 на 0.

Пример. Двойственной к функции  является функция, соответствующая формуле , т. е.  или : . Аналогично , .

 

Принцип двойственности:

Если ,

то .

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

Этот принцип удобен при нахождении двойственных функций, представленных формулами, содержащими лишь конъюнкции, дизъюнкции и отрицание. В этом случае в исходной формуле конъюнкции заменяются на дизъюнкции, а дизъюнкции – на конъюнкции. Таким образом, ДНФ соответствует КНФ, КНФ – ДНФ, СДНФ – СКНФ, СКНФ – СДНФ.

Пример. ,

если , то и .

Функция  называется самодвойственной, если .

Пример. Покажем, что формула  задает самодвойственную функцию.

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

	x	y	z
0	0	0	0
0	0	0	1
0	0	1	0
1	0	1	1
0	1	0	0
1	1	0	1
1	1	1	0
1	1	1	1

Получаем , , , .

4. Класс монотонных функций (обозначается T_Mили M):

, где , , , .

5. Класс линейных функций (обозначается T_Lили L):

.

Эквивалентность является линейной функцией . Стрелка Пирса – нет, .

, , ,…, ,

т. е.

, ,…, . (7)

Таким образом, проверка линейности сводится к нахождению коэффициентов  по формулам (7) и сопоставлению таблиц истинности данной формулы  и полученной формулы .

Пример. Проверим, является ли линейной функция . Имеем , , . Таким образом, . Сопоставляя таблицы истинности формул  и , убеждаемся, что они не совпадают. Вывод: функция  нелинейна.

Линейность функции можно также определить с помощью следующей теоремы.

Теорема Жегалкина. Всякая булева функция  представима полиномом Жегалкина, т. е. в виде , где в каждом наборе (i₁,…, i_k) все i_j различны, а суммирование ведется по некоторому множеству таких несовпадающих наборов. Представление булевой функции в виде полинома Жегалкина единственно с точностью до порядка слагаемых.

Полином Жегалкина называется нелинейным (линейным), если он (не) содержит произведения переменных.

Таким образом, линейность булевой функции равносильна линейности соответствующего полинома Жегалкина.

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

Пример. Определим линейность функции .

Имеем

Полученный полином Жегалкина является нелинейным, и, следовательно, функция f также нелинейна.

Заметим, что если в эквивалентности  формулы  являются различными конституентами единицы, то их произведение  равно 0, и тогда . Следовательно, для получения полинома Жегалкина из СДНФ можно сразу заменить .

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

Пример. Определим, к каким классам Поста относится булева функция .

Так как f (0,0)=1, а f (1,1)=0, то  и . Поскольку , то . Так как f (0,0)>f (1,1), то . Полином Жегалкина для функции  имеет вид  в силу равенства . Поэтому данная функция нелинейна. Таким образом, можно составить следующую таблицу

Таблица функций

Функция	Классы
	Р0	Р1	S	М	L
х | у	Нет	Нет	Нет	Нет	Нет

Теорема Поста. Система F булевых функций тогда и только тогда является полной, когда для каждого из классов P₀, P₁, S, M, L в системе F найдется функция, не принадлежащая этому классу.

В силу теоремы Поста функция х | у образует полную систему, т. е. с помощью штриха Шеффера можно получить любую булеву функцию. В частности, .

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

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

Доказательство. Предположим, что существует базис F, состоящий более чем из четырех функций. По теореме Поста тогда получаем, что F состоит ровно из пяти функций, каждая из которых не принадлежит ровно одному классу Поста. Пусть f – функция из F, не принадлежащая классу Р₀. Тогда, с одной стороны, f (0,0,…, 0)=1, а, с другой – из  следует, что f (1,1,…, 1)=1. Это означает, что f не является самодвойственной функцией, что противоречит предположению.

Пример. Следующие системы булевых функций являются базисами: .

Таблица 7

Обоснование	Базис
; следовательно,	{И, НЕ} – конъюнктивный базис
; следовательно,	{ИЛИ, НЕ} – дизъюнктивный базис
;	{И, , 1} – базис Жегалкина
; следовательно, ;	{|} – базис Шеффера
; следовательно, ;	{} – базис Пирса

Пример.

Конъюнкции, то есть все функции вида , тоже составляют замкнутый класс. Очевидно, однако, что, например, функцию, которая на наборе (0,0,…, 0) имеет значение 1, нельзя представить суперпозицией таких функций. Таким образом, {И} не является базисом, следовательно, конъюнктивный базис {И, НЕ} является минимальным.

Рассмотрим более подробно базис Жегалкина.

Алгебра Жегалкина и линейные функции

Алгебра Жегалкина – это алгебра над множеством двух бинарных булевых функций (И, ) и нульарной функции 1. Легко проверить следующие соотношения в этой алгебре:

;

;

;

.

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

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

Контрольные вопросы и упражнения

1. Дайте определение полной системе булевых функций.

2. Перечислите классы Поста.

3. Дайте определение двойственной функции. Приведите примеры.

4. Дайте определение самодвойственной функции. Приведите примеры.

5. Постройте полином Жегалкина для функции «стрелка Пирса».

6. Сформулируйте теорему Поста.

7. Что такое базис? Приведите примеры базисов.

3.8 Методы минимизации логических функций

Наиболее употребляемая операция при минимизации функций – это операция склеивания.

 

AB+ ĀB=B (A+ Ā)=B.

Рассмотрим три наиболее распространенных метода минимизации.