аргументов и соответствующие им значения функции в таблицу, получают табличное задание ФАЛ f(x1, x2, ... , xn ) - таблицу истинности ФАЛ (таблица 4).

Таблица 4 Табличное задание ФАЛ

x1	x2	…	xn	f(x1,x2,…xn )
0	0	…..	0	1
0	0	…..	1	0
..	..	…..	…	…
1	1	1	1	1

Теорема 1: Число различных ФАЛ, зависящих от n аргументов, конечно и

равно 22n .

Теорема 2: Число всех ФАЛ, существенно зависящих от n – аргументов конечно и определяется следующим рекуррентным соотношением:

Аn = 22n -Cnn − 1 Аn-1 - Cnn − 2 Аn-2 -… -Cn1 А1 – А0 ,

где Аi - число ФАЛ , существенно зависящих от i – аргументов, Сin – число сочетаний из n – элементов по i.

Например, необходимо определить А3 для трех аргументов:

А3 = 223 - C32 А2 - C31 А1 – А0 ,

Предварительно необходимо определить А0, А1, А2. А0=2 и А1=2. Зная А0 и А1 можно вычислить А2:

А2 = 222 - C21 А1 - А0 = 16 -2·2 – 2 = 10.

Отсюда:

А3 = 223 - C32 А2 - C31 А1 - А0 = 256 –3·10 - 3· 2 – 2 = 218.

Таким образом из 256 ФАЛ, которые можно определить на наборах из трех переменных х1 , х2 , х3 только 218 ФАЛ существенно зависят от всех трех аргументов.

Элементарные ФАЛ. Среди ФАЛ выделяют 11 простых функций, получивших название элементарных, которые играют большую роль в построении теории функций алгебры логики и ее приложениях:

f1=0 (функция константы «0»); f2=1 (функция константы «1»); f3=x (функция тождественности); f4= x (инверсия, отрицание);

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

f5 = x1 x2(дизъюнкция). f6=x1 x2= x1&x2(конъюнкция).

f7= x1↓x2 = x1 x2(стрелка Пирса). f8= x1/x2 = x1 x2 (функция Шеффера).

37

Таблица 5 Элементарные функции

x x2		f5	f6	f7	f8	f9	f10	f11
1
0	0	0	0	1	1	0	1	1
0	1	1	0	0	1	1	0	1
1	0	1	0	0	1	1	0	0
1	1	1	1	0	0	0	1	1

f 9=x1 x2(сложение по модулю 2). f10=x1≡ x2(функция тождественности).

f11=x1→x2(импликация, следствие).

Элементарные функции обладают определенными свойствами, которые рассматриваются ниже.

Для дизъюнкции и конъюнкции справедливы:

1) переместительный закон (свойство коммутативности): х1 х2 = х2

х1, х1 х2 = х2 х1; 2) сочетательный закон (свойство ассоциативности): х1 (х2 х3 ) = ( х1

х2 ) х3 , х1 ( х2 х3 ) = ( х1 х2 ) х3 ; 3) распределительный закон (свойство дистрибутивности): для

конъюнкции относительно дизъюнкции: х1 ( х2 х3 ) = ( х1 х2 ) ( х1 х3 ); для дизъюнкции относительно конъюнкции: х1 ( х2 х3 ) = ( х1 х2 ) ( х1 х3 ). Распределительный закон определяет правила раскрытия скобок логических выражений (или взятия в скобки). Придавая значению х всевозможные значения , можно убедиться в справедливости следующих выражений: х х = х; х 1 = 1; х 0 = х; х x = 1; х х = х; х

1 = х; х 0 = 0; х x = 0; х = x . Сравнивая значения левых и правых частей выражений на всевозможных наборах значений аргументов можно убедиться в справедливости соотношений, известных как законы де Моргана:

x1 x2 = x1 x2 ; x1 x2 = x1 x2

Из законов де Моргана вытекают следствия: x1 x2 = x1 x2 ; x1 x2 = x1 x2 .

Законы де Моргана, а следовательно и следствия из них справедливы для любого количества переменных:

х1 х2 … хп =

х1 х2 … хп =

x1 x2 xn ;...

x1 x2 xn ....

Функцию сложения по модулю 2 можно представить следующим образом:

х1 х2 = х1 x 2 x 1 х2 = ( х1 х2 ) ( x 1 x 2 ) .

Для функции сложения по модулю 2 справедливы:

1)переместительный закон: х1 х2 = х2 х1;

2)сочетательный закон: х1 ( х2 х3 ) = ( х1 х2 ) х3;

3)распределительный закон: х1 ( х2 х3 ) = ( х1 х2 ) ( х1 х3 ).

Для этой функции справедливы также соотношения: х х = 0; х x = 1;

х 1 = x ; х 0 = х.

38

Функцию импликации можно представить в виде: х1 → х2 = x 1 х2 . Для этой функции справедливы следующие соотношения :

х1 → х2 =

2 →

1;

х→ х= 1;

х→

=

; х→ 1 = 1;

x

x

x

x

х→ 0 =

;

0 → х= 1; 1 → х= х.

x

Функция Шеффера

является логическим отрицанием функции

конъюнкции: х1/х2= x1 x2 . Для нее справедливы следующие соотношения: х / х

= x ; х/ x = 1; х / 1= x ; х/0= 1.

Переместительный закон справедлив для функции Шеффера только для

двух переменных:				х1 / х2 = х2 / х1 .
Используя свойства функции Шеффера можно получить некоторые
формулы преобразования логических выражений:
х1 х2 =					= (х1 / х2 )/( х1 / х2 ) ;
	x1 / x2
x1 x2 =					=		1 /		2 = (х1 / х1 )/( х2 / х2 ).
		x1		x2		x		x

Функция Пирса (Вебба) является отрицанием функции дизъюнкции:

х1↓ х2 = x1 x2 = x1 x2 .

Для этой элементарной функции справедливы следующие соотношения:

х↓х =		; х↓		=0;	х↓0 =		; х↓1 = 0 .
	x		x			x
	Функция Пирса (Вебба) подчиняется только переместительному закону:
х1 ↓ х2 = х2 ↓ х1.					дизъюнкции,			конъюнкции, логического отрицания и Пирса
	Функции
(Вебба) связаны между собой:								х1 х2 =	x1 ↓ x2	= ( х1↓ х2 )↓( х1↓х2 ) ;

x1 x2 = x1 x2 = ( х1↓ х1 )↓( х2↓ х2 ) .

Рассмотренные элементарные функции позволяют строить новые ФАЛ двумя основными путями: путем перенумерации аргументов и путем подстановки в функцию новых функций вместо аргументов. Функцию,

полученную из функций f1 , f2 ,…, fk

путем многократного применения этих

двух операций, называют суперпозицией функций f1 , f2 ,…, fk.

Основные классы ФАЛ:

1.

Класс функций, сохраняющих константу нуля: функции, которые на

нулевом наборе переменных принимаю значение 0. К0: f

(0,0,...,0)=0. Число

таких функций равно 22 n − 1 . К классу К0 относятся: 0, ,&, .

2.

Класс функций, сохраняющих константу единица: функции, которые

на единичном наборе переменных принимаю

значение 1. К1: f(1,1,...,1)=1.

Число таких функций равно 22 n − 1 .

К классу К1 относятся: 1, ,&,→, ≡ .

3.

Класс самодвойственных функций: все функции, для которых

справедливо:

U

: f ( x

, x

... x

( x

, x

... x

) . Число таких

1

2

n

) = f

1

2

n

функций равно: U= 22 n − 1 .

4.

Класс линейных функций:

к этому классу относятся все функции,

которые могут быть выражены в виде полинома: L: f ( x1 , x2 ,…, xn ) = C1 x1 C2 x2 … Cn xn , где Ci = 0 или Ci = 1. Общее количество функций - 2n+1 .

39

5. Класс симметричных функций: к этому классу относятся все функции, для которых справедливо соотношение: S: f ( x1 , x2 ,…, xn ) = f ( у1 , у2 ,…, уn ), где у1 , у2 ,…, уn - любая перестановка аргументов x1 , x2 ,…, xn ( к классу симметричных функций относятся все функции , для которых справедлив переместительный закон).

6. Класс монотонных функций: функция	f ( x1 , x2 ,…, xn )	называется
монотонной, если для любых двух наборов х' ,	х'' при условии,	что х' ≥ х''

справедливо соотношение: M: f ( х' ) ≥ f ( х'' ). К классу M относятся: ,&,→. Полные системы ФАЛ. Любая ФАЛ, полученная с помощью операции

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

, fk) называется функционально полной в классе R или базисом класса R. Базис является минимальным, если удаление хотя бы одной функции, образующей этот базис, превращает систему функций в неполную.

В дальнейшем под классом R будет пониматься класс, образуемый всеми

функциями от n переменных, т.е. 22 n - функциями.

Можно определить несколько полных систем ФАЛ (базисов): система функций дизъюнкции, конъюнкции и отрицания; система функций дизъюнкции и отрицания; система функций конъюнкции и отрицания; функция Шеффера; функция Вебба (Пирса) и т.д. Четыре последние системы являются минимальными базисами. Понятия полноты и минимального базиса являются фундаментальными понятиями алгебры логики, имеющими большое теоретическое и прикладное значение.

Теорема Пост-Яблонского: для того, чтобы система функций была полной необходимо и достаточно, чтобы она содержала следующие функции:

1)не сохраняющую константу «0»;

2)не сохраняющую константу «1»;

3)не являющуюся самодвойственной;

4)не являющуюся линейной;

5)не являющуюся монотонной.

Способы задания функций алгебры логики (ФАЛ), запись ФАЛ в СДНФ (СКНФ), их преобразование. Любую функцию алгебры логики можно выразить суперпозицией некоторых элементарных функций, образующих базис. В этом случае получают достаточно компактное представление ФАЛ в виде логического выражения − аналитическое представление ФАЛ. Наиболее распространен для аналитического представления ФАЛ базис, состоящий из элементарных функций дизъюнкции, конъюнкции и логического отрицания (булев базис): { , , }.

Среди логических функций можно выделить функции, которые обращаются в единицу лишь на каком-либо одном наборе аргументов и в нуль на всех остальных (2п−1) наборах. Такие функции получили название

40

конституент единицы. Из элементарных функций к ним относятся: функция конъюнкции, функция Пирса (Вебба), функция отрицания.

Из определения конституенты единицы следует, что для задания логических функций типа конституенты единицы от п−аргументов, достаточно задать один набор аргументов, обращающий ее в единицу. Для этого составляется конъюнктивный терм (минитерм), связывающий переменные x1, x2, ... , xn , представленные в прямой или инверсной форме, знаком конъюнкции. Терм должен обращаться в единицу только на одном наборе, а на остальных наборах − в нуль. Для этого те переменные, которые в указанном наборе равны нулю, берутся со знаком инверсии, остальные − без знака инверсии.

Если αi − значение переменной xi в наборе, то в общем виде можно

	f (x1 , x 2 ,..., x n) = xα1				2 ...	xαn n =	n
записать				1 xα2			xα2 i ,
							i =1
где	xαi =		, если αi	= 0	и	xαi = xi	если αi = 1.
		xi

В случае наличия нескольких наборов, на которых логическая функция обращается в единицу, необходимо задать все эти наборы. Составляются для каждого набора конституенты единицы (минитермы), которые объединяются знаком дизъюнкции. В результате получается логическое выражение − аналитическое представление ФАЛ

f (x1, x2 ,..., xn) = xα1 1 xα2 2 ... xαn n ,

1

где − указание, что дизъюнкция берется только по тем наборам, на

1

которых функция принимает значение единицы.

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

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

Основная литература: 1[174:194] , 2[8:11]. Дополнительная литература: 4[57:65], 5[43:44], 7[190:199].

Контрольные вопросы:

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

2.Назовите элементарные ФАЛ и их основные свойства.

3.Перечислите основные классы ФАЛ, дайте определение каждому классу.

4.Дайте определение конституент “1” и “0”.

5.Дайте определение функционально полных систем ФАЛ, приведите примеры.

41

Тема 8.

Минимизация ФАЛ.

Для получения кратчайшей или минимальной аналитической записи ФАЛ представляют в дизъюнктивной совершенной нормальной форме, а затем применяют правила склеивания и поглощения.

Правило склеивания для конъюнктивных термов. Дизъюнкцию двух соседних минитермов ранга r можно заменить элементарным минитермом ранга r−1, являющимся общей частью исходных термов (например, у = х1 х2 x 3 х1

х2 х3 = х1 х2).

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

мер, у = х1 х2 х3 х1 х2 = х1 х2).

Правила склеивания и поглощения основываются на свойствах элементарных функций.

Пример. Получить МДНФ функции f( х1 , х2 , х3 ) , если она принимает значение единицы на наборах 001 , 100 , 101 , 111.

Записывается СДНФ функции и преобразовывается

f ( х1 , х2 , х3 ) = x1 x2 x3 x1 x2 x3 x1 x2 x3 х1 х2 х3 = x 2 х3 х1 x 2 х1 х3 .

Наиболее наглядным и простым является метод минимизации с использованием карт Вейча – Карно. Карта (диаграмма) Вейча – Карно – это прямоугольник с 2п клетками, где п должно равняться количеству аргументов функции. Каждая клетка соответствует определенному набору аргументов, если

п – четное, то каждая сторона прямоугольника имеет 2п/2 клеток. Если п – нечетное, то одна сторона имеет 2(п-1)/2 клеток, другая 2(п+1)/2 клеток.

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

В графическом методе представления ФАЛ и поглощение и склеивание выполняются графически (визуально). При этом стараются склеить как можно большее количество «1», соответствующих 0–кубам, руководствуясь ниже приведенными правилами. Две соседние «1» образуют 1–куб, обозначаемый конъюнкцией переменных, в которой отсутствует переменная, изменяющая свое значение. Четыре соседние «1» образуют 2–куб, в обозначении которого отсутствуют уже 2 переменные. Восемь соседних «1» образуют 3–куб, в конъюнкции переменных отсутствуют уже 3 переменные.

Пример. Получить МДНФ полностью определенной ФАЛ f( x1 , x2 , x3 ) = V F (0,1,2,6,7,10,14), используя графический метод представления ФАЛ.

1

Решение: Функция f(x1,x2,x3,,x4 ) графически представлена с помощью диаграммы Вейча-Карно на рисунке 8. На рисунке 8 видно, что четыре единицы в нижнем ряду являются соседними и образуют 2–куб – x3 x 4 . Оставшиеся не-

покрытыми три единицы можно покрыть двумя 1–кубами: x 1 x 2 x 3 и x 1x2 x3.

42

МДНФ заданной функции f ( x1, x2, x3, x4 ) = x3 x 4 x 1 x 2 x 3 x 1 x2 x3.

x1x2	00	01	11	10
x3 x4
00	1
01	1
11		1	1
10	1	1		1

Рисунок 8 Получение минимальной нормальной формы МДНФ непосредственно из

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

При минимизации по методу Квайна предполагается, что исходная функция задана СДНФ. Выполняется попарное сравнение всех термов, входящих в СДНФ, с целью выполнения операции склеивания по какой-либо переменной Fхi F x i = F, где F – терм ранга r = n–1. Таким образом, удается понизить ранг термов с r = n до r = n–1. Полученные термы меньшего ранга также могут склеиваться. Эта процедура продолжается до тех пор, пока это склеивание возможно для термов любого ранга. Термы, которые не участвовали в операциях склеивания, называют первичными импликантами. Множество первичных импликант, соединенных знаком дизъюнкции, не всегда представляет из себя МДНФ. Поэтому полученное множество первичных импликант упрощается за счет отбрасывания некоторых первичных импликант. Первичный импликант отбрасывается, если это не приводит к нарушению эквивалентности функции. Недостатком метода Квайна является необходимость полного попарного сравнения термов с целью склеивания. Мак-Класки в 1956 г. предложил записывать

конъюнктивные термы x1α 1 x 2α 2...x nα n в виде наборов двоичных переменных

α1α2 … αп. Это позволило избежать громоздкости в записи термов и уменьшить количество попарных сравнений при выполнении склеивания. Дело в том, что все наборы переменных α1α2 … αп, можно разбить по числу единиц в них на непересекающиеся группы. В i-ю группу войдут все наборы, содержащие по i единиц. Сравнение наборов в этом случае необходимо выполнять только между двумя соседними группами (i–1)-й и i-й, i-й и (i+1)-й. Наборы, входящие в несоседние группы будут отличаться, как минимум, на две входящие в них единицы. Поэтому вероятность их склеивания равна нулю. Ниже излагается формализованный алгоритм Квайна с учетом модернизации Мак-Класки (метод Квайна – Мак-Класки), разбитый на этапы.

Этап 1. Нахождение первичных импликант.

43

Все термы, входящие в СДНФ, {m}, выписываются в виде наборов двоичных переменных α1α2 … αп по группам ( по числу имеющихся в них единиц). Между наборами соседних групп осуществляется склеивание. Переменная, по которой осуществлено склеивание, заменяется на 'х'. Результаты склеивания также записываются по группам, которые сравниваются с целью склеивания. Этот процесс сравнения и склеивания продолжается до получения таких групп, которые между собой не склеиваются. Все термы, не участвующие в операциях склеивания, образуют множество первичных импликант {λ}.

Этап 2. Составление импликантной матрицы.

Составляется матрица, в которой строки отмечаются первичными импли-

кантами, столбцы – исходными термами. На пересечении i-й строки и	j-го
столбца ставится метка, если первичный импликант λi входит в терм тj	( λi
покрывает тj ).
Этап 3. Нахождение существенных импликант.

Если в каком-либо столбце импликантной матрицы имеется только одна метка, то первичная импликанта, соответствующая этой метке, является существенной, так как без нее не будет получено все множество заданных термов {m}. Существенные импликанты обязательно должны входить в МДНФ. Столбцы, соответствующие термам, покрываемым существенными импликантами, вычеркиваются из импликантной матрицы, также как и строки с существенными импликантами.

Этап 4 Вычеркивание лишних первичных импликант После выполнения предыдущего этапа в импликантной матрице могут

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

Этап 5 Получение минимального покрытия Исследуется полученная после вычеркивания столбцов и строк

импликантная матрица. Из оставшихся строк выбирается такая совокупность первичных импликант, которая покрывает все оставшиеся исходные термы. При нескольких вариантах выбирается такая их совокупность, чтобы обеспечить минимальное суммарное число букв в выбранных первичных импликантах. К ним присоединяются существенные импликанты и осуществляется переход от записи первичных импликант к конъюнктивным термам разного ранга. Объединяя последние знаком дизъюнкции, получают МДНФ.

Пример. Получить МДНФ логической функции f(х1 , х2 , х3 ), используя метод Квайна – Мак-Класки.

f(х1 , х2 , х3 ) = x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 .

Множество термов {000, 001, 100, 101, 111} разбивается на несколько

групп	К00 = {000},	1 группа	К01 =	{001,100} ,
0 группа
2 группа	К02 = {101},	3 группа	К03 =	{111} .

44

Этап 1 Нахождение первичных импликант (символом * будут

отмечаться термы, участвующие в операциях склеивания)

а) Сравниваются

К00 = {000*} и К01 = {001*,100*}.

Результат склеивания К10 =

{00х, х00}.

Сравниваются К01 = {001*,100*} и

К02 = {101*}.

Результат склеивания К11 =

{х01 , 10х}.

Сравниваются К02 = {101*}

и К03 = {111*}.

Результат склеивания К12 = {1х1}.

Все исходные термы участвовали в склеивании, поэтому ни один из них

не является первичным импликантом.

б) Сравниваются К10 = {000*,х00*}

и К11 = {х01*,10х*}.

Результат склеивания К02 =

{х0х, х0х}.

Сравниваются

К11 =

{х01,10х}

и

К12 =

{1х1} ,

в этих группах

отсутствуют склеиваемые минитермы.

В К12

терм {1х1}

не отмечен ни разу символом *. Следовательно, он

и является первичным импликантом второго ранга λ′= {1x1}.

в) К20

не поддается сравнению и склеиванию.

Поэтому полученный

2−куб является первичным импликантом λ″= {х0х}.

Все множество первичных импликант λ = λ′ λ″:

λ = {1x1, x0x}.

Этап 2 Составление импликантной матрицы

Импликантная матрица будет иметь 2

строки

и

5

столбцов. Она с

проставленными метками представлена таблицей 6.

Таблица 6 – Импликантная матрица

000

001

100

101

111

1х1

V

V

x0х

V

V

V

V

Этап 3 Нахождение существенных импликант В импликантной матрице имеется 4 столбца с одной меткой. Этим меткам

соответствуют существенные импликанты 1х1, х0х. Из таблицы 3 вычеркиваются столбцы–термы, покрываемые существенными импликантами 1х1, х0х и соответствующие им строки. В результате все столбцы и строки таблицы вычеркиваются.

Этап 4 Вычеркивание лишних первичных импликант. В данном примере они отсутствуют.

Этап 5 Переходя к конъюнктивным термам получаем МДНФ:

f(х1 , х2 , х3 ) = х1 х3 x 2 .

Различают полностью определенные ФАЛ и неполностью определенные ФАЛ. К последним относят ФАЛ, значения которых определены не на всех наборах аргументов. Такие наборы называются безразличными и при минимизации ФАЛ на этих наборах может принимать любое значение.

Основная литература: 1[192:194, 196:203, 230:232].

45