Методичка

Закон склеивания состоит в том, что переменная исключается, если она входит в члены дизъюнкции (конъюнкции) с разными знаками, а остальные элементы дизъюнкции (конъюнкции) с ней одинаковы.

a b a b a; a a b ab;

a b a b a c ... a x a; ab ab a;

ab ab ab ba а; ab ab ac ... ax a

3.5 Тавтологии. Равносильные формулы

Логические формулы (ЛФ), значения которых для любого набора переменных есть 1 (соответственно 0) будем называть тождественно истинными формулами, или тавтологиями (тождественно-ложными ЛФ или противоречиями).

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

1.	| = х х 1										- закон тождества
2.	| = ⌐( x x ) 1										- закон противоречия
3.	| = x x 1									- закон исключенного третьего
4.	| = x х 1										- закон двойного отрицания
5.	| = x x = x | x x x 1- закон идемпотентности
	| x y x y
6.	| x y x y									-законы де Моргана
7.	| = x y y x 1									- закон контрапозиции
8.	| = x y y z x z 1- закон транзитивности импликации
(закон силлогизма)
9.	| = x y x y									1	- закон противоположности

10.| = x y y z (x z) 1- закон транзитивности эквиваленции Законы 1-3 выражают законы формальной логики, выведенные Аристо-

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

В силу законов идемпотентности в алгебре логики нет показателей степени и коэффициентов (idem - "то же", potentia - сила).

31

A B B A

Смысл законов де Моргана можно выразить так: отрицание дизъюнкции равно конъюнкции отрицаний и vice versa. Согласно закону контрапозиции

два предложения вида A B и B A одновременно истинны или одновременно ложны.

Две ЛФ A x1 , x2 ,..., xn и B x1 , x 2 ,..., x n назовем равносильными, если для любых наборов x1 , x 2 ,..., xn они принимают одинаковые значения.

Это обозначается А В и читается "А равносильно В" (равносильность – бинарное отношение, оно рефлексивно, симметрично и транзитивно).

Теорема 1. А В тогда и только тогда, когда | = А В. Убедимся, что теорема верна, если докажем необходимость: если А В, то | = А В; достаточность: если | = А В, то А В. Справедливость этих утверждений вытекает непосредственно из определений.

Принцип двойственности: Если две формулы, (не содержащие знаков, и ) равносильны, то двойственные им формулы равносильны.

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

(X 0 = Х 1).

Обратные и противоположные теоремы. Для каждого предложения,

формализованного импликацией А В, можно составить три таких предложения В А, A B и B A . Предложение В А называется обратным

данному, предложения A B противоположным данному и B A обратно противоположным. Для всякой теоремы вида "если А, то В" можно сформулировать обратное ей предложение "если В, то А". Однако не для всякой теоремы предложение ей обратное является истинным. Например: "если два прямоугольника конгруэнтны, то их площади равны", обратное: "Если площади двух прямоугольников равны, то они конгруэнтны" - неверно. Если А В теорема, то А есть достаточное условие В, а В необходимое условие А. Если оба взаимообратных предложения А В и В А теоремы, т.е. предложение А В теорема, то В является необходимым и достаточным условием А, а А достаточным и необходимым условием В (если два квадрата конгруэнтны...). Если А В теорема, а В А нет, то А - достаточное, но не необходимое условие В, а В - необходимое, но не достаточное условие А.

Для всякой теоремы А В, можно составить противоположное пред-

ложение A B , которое может быть истинным, но может и не быть истинным. Чтобы убедиться в этом, надо составить таблицу истинности.

Согласно закону контрапозиции два предложения вида одновременно истинны или ложны. Вместо данной теоремы можно доказать обратно противоположную теорему.

32

3.6 Полнота системы логических функций. Логический базис.

При использовании аналитических форм представления логических функций широко используется принцип суперпозиции, заключающийся в замене одних аргументов данной функции другими. Например, если аргументы функции Z = Z(X, Y) являются в свою очередь функциями других аргументов

X = Х(a, b) и Y = Y(c, d), то можно записать Z = Z(a, b, c, d).

Система S логических функций f0, f1, f2, … , fk называется функционально полной, если любую функцию алгебры логики можно представить в аналитической форме через эти функции. Как известно,

любое сложное высказывание можно представить в виде выражения, в которое входят простые высказывания (переменные хi), операции дизъюнкции, конъюнкции, отрицания и, быть может, скобки (,). Рассмотрим, каким свойствам должны удовлетворять операции, с помощью которых можно выражать любое сложное высказывание.

Система S называется полной в Pk, если любая функция fi, fi Pk представима в виде суперпозиции этой системы, и минимальным базисом, если теряется полнота S при удалении хотя бы одной функции, где Pk – k- значная логика.

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

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

1. Функция, сохраняющая константу нуль.

(Если функция на "0" наборе аргументов равна 0, то она называется функцией, сохраняющей константу нуль. f (0,0,...,0) 0 ).

2. Функция, сохраняющая константу 1.

(Если функция на "1" наборе аргументов равна 1, то она называется функцией, сохраняющей константу "1". f (1,1,...,1) 1 ).

3. Линейная функция

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

f K0	K1X1 K 2 X2 ... K n Xn , где Кi
			0	0	0
K 0 , K1	,..., K n	0	0	1	1
			1	0	1
		1 могут принимать только два значения	1	1	0
		33

- знак сложения по модулю 2.

mod 2, M2, таблица сложения по модулю 2.

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

К0	К1	К2	Вид полинома
0	0	0	Константа 0
0	0	1	Х2
0	1	0	Х1
0	1	1	Х1 Х2
1	0	0	Константа 1
1	0	1	1 Х2 = ⌐Х2
1	1	0	1 Х1=⌐Х1
1	1	1	1 Х1 Х2=Х1 ↔Х2

4. Монотонная функция

Набор аргументов является возрастающим, если он является старшим, хотя бы в одном из разрядов.

возрастании значений аргументов.
Пример:	01 – младший набор		11 - старший набор
00 - младший 10 - старший
0011 – младший набор		1011 –старший набор
01

Функция называется монотонной, если она возрастает при любом

	10
		несравнимый набор

5. Самодвойственные функции.

Два набора аргументов называются противоположными, если значения всех аргументов у них противоположны.

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

Определим теперь пять классов булевых функций:

1.Классом K0 булевых функций fi (X1 , X2 ,..., Xn ) сохраняющих константу 0, называется множество функций вида К0={f i(X1 , X2 ,..., Xn ) /(fi (0,0,...,0) 0}

f0,f1,f2,f3,f4,f5,f6,f7 – функции, сохраняющие константу 0.

2.Классом K1 булевых функций fi (X1 , X2 ,..., Xn ) сохраняющих константу 1, называется множество функций вида К1={f i(X1 , X2 ,..., Xn ) /f i(1,1,...,1) 1}.

f1,f3,f5,f7,f9,f11,f13,f15 – функции, сохраняющие константу 1.

34

3. Классом Kл линейных булевых функций fi (X1 , X2 ,..., Xn )

называется

множество функций вида Кл=

fi (X1 , X2 ,..., Xn ) / fi

(X1 , X2 ,..., Xn ) C0

Ci Xi

, где

С0, Сi = (0,1); - знак операции «сложение по модулю 2».

f0 , f3 , f5 , f6 , f9 , f10 , f12 , f15 - линейные функции.

4. Классом Км монотонных булевых функций fi (X1 , X2 ,..., Xn ) называется

множество булевых функций вида:

*

* ,..., * ) (

) ( *

{ f

( X

1

, X

2

,..., X

n

) /(

,

1

,

2

,...,

n

i

, i 1, n)

1

1

2

n

i

Км= f ( * , * ,..., * )

f (

1

,

2

,...,

n

)}

1

2

n

f0, f1,f3,f5, f7,f15- монотонные функции.

5. Классом Kс самодвойственных булевых функций fi (X1 , X2 ,..., Xn ) называется множество булевых функций вида

Кс= fi (X1 , X2 ,..., Xn ) / fi (X1 , X2 ,..., Xn ) f (X1 , X2 ,..., Xn ) .

Функция самодвойственная, если на любой паре противоположных наборов функция принимает противоположные значения. Эти разряды соответствуют инверсным наборам Х1 Х2: 00-11, 01-01, 10-10 , 11-00.

f3 , f5 , f10 , f12 - самодвойственные функции.

Критерий полноты Поста-Яблонского.

Теорема о функциональной полноте была сформулирована в 1921 г. американским ученым Эмилем Постом и доказана советским ученым Яблонским С.В.

Система S булевых функций fi является полной тогда и только тогда, когда в системе S выполняются 5 условий:

1)существует функция fi S, не сохраняющая константу нуль: fi K0;

2)существует функция fi S, не сохраняющая константу 1: fi K1;

3)существует нелинейная функция в системе S: fi Kл;

4)существует не самодвойственная функция в системе S: fi Kс;

5)существует немонотонная функция в системе S: fi Kм.

Построим все булевы функции от двух переменных (табл.3.3.).

										Таблица 3.3
переменные								булевы функции
X1	X2	f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Индекс i функциональной переменной fi i=1,…,15 равен десятичному эквиваленту двоичного набора этой функции, читаемому сверху вниз.

f0 (X1 , X 2 ) 0 - константа 0 или функция «никогда».

f1 (X1 , X2 ) X1 & X2 - конъюнкция или логическое умножение.

35

f15 (X1 , X2 ) 1

f2 ( X1 , X 2 ) X1 X 2 X1 X 2 - прямая (левая) коимпликация (читается

«неправда, что если X1 то X2»),префикс «ко» – от латинского conversus - обратный. Иногда эту функцию называют запрет по х2, что видно из формулы.

f3 (X1 , X2 ) X1

f4 (X1 , X 2 ) X1 X 2 X1 X 2 - правая коимпликация (читается «неправда, что если X2 то X1»). Иногда эту функцию называют обратная коимпликация или запрет по х1.

f5 (X1 , X2 ) X2
f6 (X1 , X2 ) X1				X2 - сложение по модулю 2 (неравнозначность).
f7 (X1 , X2 ) X1				X2						- дизъюнкция.
f8 (X1 , X2 ) X1				X2						X1 X2 - стрелка Пирса, функция Вебба.
f9 (X1 , X2 ) X1					X2 - эквивалентность.
f10 (X1 , X 2 ) X 2					- отрицание X2.
f11 (X1 , X2 ) X2					X1					X1 X2 - обратная импликация («если X2 то X1»).
f12 (X1 , X2 ) X1					- отрицание X1.
f13 (X1 , X2 ) X2					X2					X1 X2 - прямая импликация («если X1 то X2»).
f14 (X1 , X2 ) X1					X2					X1 / X2 - штрих Шеффера.

Константа 1 или функция «всегда».

Для порождения всех базисов в P2 построим двумерную таблицу, каждой строке которой взаимно однозначно сопоставим 16 функций, столбцу - класс, и в клетке (i, j) ставим 1, если i -функция не принадлежит j классу (табл. 3.4).

Таблица 3.4

Номер		Классы функций
функции fi	К0	К1	Kл	Kм	Kс
0		1			1
1			1		1
2		1	1	1	1
3
4		1	1	1	1
5
6		1		1	1
7			1		1
8	1	1	1	1	1
9	1			1	1
10	1	1		1
11	1		1	1	1
12	1	1		1
13	1		1	1	1
14	1	1	1	1	1
15	1				1

36

fi (X1 , X2 ,..., Xn ) =K1 K2 … Km

Из таблицы видно, что существуют отдельные функции, которые удовлетворяют всем критериям полноты Поста-Яблонского и реализуют покрытие всех классов. Другие функции совместно покрывают все классы. Каждое, указанное ниже, покрытие порождает логический базис Bi.

П1 = {f8} B1 – базис Вебба;

П2 = {f14} B2 – базис Шеффера;

П3 = { f13,f0} B3 = { , 0} – импликативный базис;

П4 = {f1, f12} B4 = {& } – конъюнктивный базис Буля; П5 = { f7,f12} B5 = { } – дизъюнктивный базис Буля; П6 = { f6, , f1, f15} B6 = { , &, 1} – базис Жегалкина; П7 = {f13, f12} B6 = { , } – базис Фреге.

Всего можно построить 17 покрытий или логических базисов. Наиболее часто приходится использовать базис Шеффера.

3.7 Дизъюнктивная нормальная форма и конъюнктивная нормальная форма.

Элементарной конъюнкцией n переменных называется конъюнкция переменных или их отрицаний. Примером элементарной конъюнкции

являются выражения вида К1= x1x2x3 или К2=x 1x 2⌐x3 или К3= x1⌐x2x3 . Аналогично элементарной дизъюнкцией n переменных называется

дизъюнкция переменных или их отрицаний. Примером элементарной дизъюнкции являются выражения вида D1= x1 x2 ⌐ x3 или D2=x1 ⌐ x2

⌐ x3 или D3=⌐ x1 x2 x3.

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

(СДНФ).

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

fi (X1 , X2 ,..., Xn ) =D1&D2&…&Dm

Если же каждый член КНФ от n аргументов содержит все эти n аргументов, часть из которых входит в него с инверсией, а часть – без нее, то такая форма

37

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

Рассмотрим произвольную логическую функцию от n аргументов типа конституенты единицы. Как известно, конституента единицы полностью определяется заданием набора, обращающего ее в единицу. В этом наборе некоторые аргументы могут быть равны 1, а остальные равны 0. Составим конъюнкцию от всех n аргументов, причем те аргументы, которые в указанном наборе равны 0, возьмем с инверсией, а аргументы, равные 1 без инверсии. Если все аргументы будут соответствовать заданному набору, то на нем функция обратится в конъюнкцию n единиц и будет равна единице. Для всех остальных наборов хотя бы один из аргументов отличается от заданного набора, и, следовательно, хотя бы один член конъюнкции, а значит, и вся конъюнкция превратится в 0.

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

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

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

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

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

38

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

1)Каждое логическое слагаемое формулы содержит все переменные, входящее в функцию.

2)Все логические слагаемые формулы различны.

3)Ни одно логическое слагаемое формулы не содержит одновременно переменную и ее отрицание.

4)Ни одно логическое слагаемое не содержит одну и ту же переменную дважды.

Пусть, например, функция F(x1,x2,x3)					имеет следующую таблицу
истинности:
x1		x2	x3		F(x1,x2,x3)
0		0	0		1
0		0	1		0
0		1	0		1
0		1	1		0
1		0	0		0
1		0	1		1
1		1	0		1
1		1	1		0

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

F(x1,x2,x3) СДНФ= ⌐ x1⌐x2⌐x3 ⌐x1x2⌐x3 x1⌐x2x3 x1x2⌐x3

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

F(x1,x2,x3) СКНФ=( x1 x2 ⌐ x3)( x1 ⌐ x2 ⌐ x3)( ⌐ x1 x2 x3)( ⌐ x1 ⌐ x2 ⌐ x3)

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

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

39

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

Аналитические методы минимизации

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

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

(склеивание по А) часто применяют неполное склеивание, при котором оба члена, учувствовавших в склеивании (или один из них),остаются и могут склеиваться с другими членами СДНФ, неполное склеивание может быть рассмотрено как сочетание закона склеивания и идемпотентности. Пример синтеза полного сумматора:

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

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

40