Савельвев А.Я. Основы информатики

Подождите немного. Документ загружается.

2 5 Аналитическое представление функций алгебры логики

Аналогично с функцией Шеффера для функции Пирса (Вебба) неспра-

ведливы свойства ассоциативности и дистрибутивности. Метод доказатель-

ства такой же, как и в предыдущем случае.

Надо заметить также, что д:,

-1

лг^

д:,

д:2, т. е. функция Пирса равно-

сильна функции НЕ~~ИЛИ. Здесь также равносильность функций не ведет

к наличию одинаковых свойств у этих функций.

2.5. Аналитическое представление функций алгебры логики

Существует много способов задания логических функций. Ранее был

рассмотрен табличный способ, при котором каждому набору значений пе-

ременных в таблице истинности указывается значение самой логической

функции. !>roT способ нагляден и может быть применен для записи функ-

ций от любого количества переменных. Однако при анализе свойств функ-

ций алгебры ;югики (ФАЛ) такая запись не является компактной. Проще

выглядит аналитическая запись в виде формул.

Рассмотрим фиксированный набор переменных {x^^Xj,

.^-уХ,,},

на ко-

тором задана функция алгебры логики. Так как любая переменная

X, -

|0,1},

то набор значений переменных фактически представляет собой

пекоюрое двоичное число. Представим, что номером набора будет произ-

вольное двоичное число /, получаемое следующим образом:

• /-2""'х,+2"~^д:2+--- + ^«- (2-10)

Пус!ь имеется функция ФХх^, Х2,^.-,х„):

О,

если номер набора равен /;

Ф, .

[I,

если номер набора не равен /.

Функцию Ф, называют шерл^ол^.

Дизъюнктивный терм (макстерм) — терм, связывающий все перемен-

ные,

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

(иногда в литературе используется термин «конституэнта нуля»).

Например,

Фт = Xf

v Xj v х^ v х^; Ф^ = л:, v Хз.

Конъюнктивный терм (минтерм) — терм, связывающий переменные,

представле1Н1ые в прямой или инверсной форме, знаком конъюнкции (ино-

гда в литературе исггользуется термин «конституэнта единицы»). Обознача-

ется минтерм следующим образом:

2 Автомат как основной элемент информационных систем

р =

I, если номер набора равен /

[о,

если номер набора не равен /.

Например, f\

XiX2Xj^x^;

F^^=x^X2X^.

Ранг терма г определяется количеством переменных, входящих в дан-

ный терм. Например, для минтерма /^^ =

х^Х2ХуХ^х^

г = 5 , и для макстерма

02 =

Х^

Х2

Ху

г = 3

На основании вышесказанного можно сформулировать следующую

теорему.

Теорема. Любая таблично задсшиая ФАЛ может быть пред-

ставлена аналитически в виде

/(х,,д:2,--.,^„) = /^ vF; v...v7^, =vF,, (2.il)

те i — номера наборов, на которых функция равна 1; v

-—

эиак дичьюик-

ции, объединяющий все термы F^, равные единице.

В самом деле, если на каком-либо наборе функция /(л,", х], v*) - 1.

!о вследствие того, что

xvl-1,

в правой части выраже»Н1я (2.И) всегда

найдется элемент, равный единице; если же на наборе i функция

./(л:,',

J:J,

..., х*) = 0, то в правой части не найдется ни одною ^jreMenia,

равного 1, так как OvOv...vO-0.

Таким образом, каждому набору /, для которого / - 1, соогве1с1вует

элемент F, = \, а наборам /, на которых /, = О, не соответствует ни одного

элемента F, = \. Поэтому таблица истинности однозначно о1ображае1ся

аналитической записью вида (2.11), которую в дальнейшем будем называть

объединением термов.

Нормальная дизъюнктивная форма (ИДФ) — объединение термов,

включающее минтермы переменного ранга.

Количество всех термов, входящих в состав (2.11), равно количеству

единичных строк таблицы.

Пример 2.4, Записать в аналитическом виде функцию, задампуго таблицей 2 9

1 а б

ц а

•»2

j;i

f(x,.x-^,x,)

л.

-«)

/Oi.b.^i)

2 5 Аналитическое представление функций алгебры логики

Решение,На основании теоремы эту функцию можно записать в аналитической форме:

f(x,. JT,, jr,) = f

(О,

о, 0)

f (0,1,1)

(I,

0,0) =

1|?2?]

+ Ji^iJi) +

х,Х2^,.

Omfiem /(jj, Х;, jr,)-JjJ^^j +J,ji:2^i

x^XjXy.

Для представления ФАЛ в (2.11) используется совокупность термов,

объединенных знаками дизъюнкции (v или +). Можно использовать также

другую э;гементарную логическую операцию. Сформулируем основные

требования к этой операции.

Требование 1: если какой-либо терм /^ = I, то функция/должна быть

равна единице.

Требование 2: если какой-либо терм /;= О, то функция /может быть

равна единице.

Необходимо, чтобы при значениях термов F,=0 функция/была равна

HyjHO.

1 аблнчное представление искомой логической операции имеет вид

таблиц 2.10 н 2.11.

17"

аблииа 2-10

'"^

= V

аб л и ца 2.11

Д = ®

1аким обрачом, получили, что искомой функцией, кроме функции

ИЛИ, може! быгь функция разноименности и при этом справедливым ста-

Н0ВИ1СЯ такое следствие из теоремы (2.11):

С л е л с т в и е : любая таблично заданная ФАЛ может быть представле-

на в следук)1цей аншгигической форме:

f{x,,X2,...,xJ = F^AF2^...^Fk^ (2.12)

где итк Л обозначает операции v, ®.

Требования

и 2 можно обобщить и потребовать, чтобы аналитическое

11редс1авление нулевых и единичных строчек таблицы различалось и чтобы

выгголнялось взаимно-однозначное соответствие межд^ нулевой единичной

строкой и /ермом.

Требование 3: если какой-либо терм Ф, =

, то функция/должна быть

равна пулю.

Автомат как основной элемент информационных систем

Требование 4: если все термы Ф, = О, то функция / = 1.

Выполняя эти требования, можно прийти к двум другим возможным

функциям: конъюнкции и равнозначности (табл. 2.12 и 2.13).

Таблица 2.12

ф,

Таблица 2.13

Теорема. Любая таблично заданная ФАЛ малсет быть задана в

аналитической форме:

Дх„х2,...,х„)

Ф,&Ф^&...&Ф^, (2.13)

где к — количество двоичных наборов, для которых Ф = О.

Нормальная конъюнктивная форма (НКФ) — объединение термов

(2.13),

включающее в себя макстермы разных рангов.

Следствие: любая таблично заданная ФАЛ может быть ггредсывлена

в аналитической форме:

/(х„х^,...,х„)

Ф,^Ф-,^...'^Ф^.

(2.14)

где к- количество нулевых значений функции.

2.6. Совершенные нормальные формы

Нормальные конъюнктивная, дизъюнктивная формы не дают одно-

значного представления функции. Такое представление [Юлучаегся только

при совершенных нормальных формах (СНФ).

Введем обозначения х" =х, *' = х .

Тогда в общем виде переменная может быть задана как некоторая

функция

\х, если а = 1;

X =\_

X, если а = О,

(2.15)

При этом

X = ох

ад:,

(2.16)

где а —двоичная переменная.

2.6. Совершенные нормальные формы

Рассмотрим КОНЪЮНКЦИЮ вида x^^Xj^ ...х^", гт {а,,а2, ...,ot„} пред-

ставляет собой двоичный набор; число наборов равно 2" , т. е.

О О ...

О О

О О ...

О !

О О ... О I О

О О ... О ! I

и т.

д.

Если задагь всем а, значение О и I, то можно получить, например,

дизъюнкцию вида

v-v"'.v"^

•••^»"

^-'^"-'^т •••^„ '^ х^х\ ...x'^j V х^х\ ...х„_^х„ V ...V x^X2:.x„,{2.\l)

где V -— символ обобщенной дизъюнкции по единичным строкам.

Тогда справедлива следующая теорема.

Теорема. Любая ФАЛ может быть представлена в виде

fix^,X2,...,x^,...,xJ = vx^'x2' ...х^^/(а^...а^х^^^...х„). (2.18)

Выражение (2.18) называют разложением функции алгебры логи-

ки по к переменным.

Доказательство. Прежде всего определим, при каких условиях

выполняется равенство х" =

(Очевидно, ч^го это имеег место при

д:

= а. В самом деле, если х

<х,

то а*^ = аа

-+•

аа = а

-+•

а = !; если

д:

= а

то а** = аа

аа

аа = О.

С учетом ГЮГО, что д:" =! при х

а., можно утверждать, что

конъюнкция вида х,"'д:^*

•••^,?"

равна единице при д:, =aj,

-Vj -iXj-.-x,, =а„.

Эти равенства можно подставить в правую часть выражения

(2.18).

В результате vxJ*'д:"^ •••^Т /(л^и-^2'•••'•^^ft'•••••-^у.) ~

^ /(.Y|,

.Y2

Xj,...,

х„), что и требовалось доказать.

Следствие 1: если

А:

= !, то функция алгебры логики представляет-

ся в виде

/(Х|,

JTj,...,

^„) = -^i/CU

^2^

•••>

•*^н)'^

•^1/(0, л:^, -•-, х„). (2.19)

Следствие 2: если

А:

- и, то любая ФАЛ может быть представлена в

виде

/(д:,,

Xj, ...,х„) = \ух^'х2^ ...х"". (2.20)

Автомат как основной элемент информационных систем

Совершенная нормальная дизъюнктивная форма (СНДФ) — ФАЛ, за-

данная в виде (2.20).

Рассмотрим основные свойства СНДФ:

в СНДФ нет двух одинаковых миитермов;

в СНДФ ни один минтерм не содержит двух одинаковых множителей

(переменных);

в СНДФ ни один минтерм не содержит вместе с переменной и ее отри-

цание.

На основании этих свойств можно предложить следующий алгоритм

получения СНДФ из таблицы истинности:

Положить номер строки в таблице / = 1, номер элемента в строке 7 = 1.

Выбрать из таблицы набор с номером /. Если / = 1, то перейти к

п. 3, если / * I, — к п. 5.

Сформировать терм /^

Выбрать элемент строки с номерому.

Если X, =

0, то /^ := /^ л х^,

то F

:= ^^

л X,.

Вычислить 7 :=

+ 1. Если i < «, то перейти к п. 3, если

> и, — к и. 5.

Вычислить / := /

1. Если / < 2", то перейти к п. 2, если

> 2", — к [i. 6.

6. Конец.

Пример

2.S.

Представить

функцию,

заданную таблицей 2,14.

СИДФ,

Таблица 2.14

Т|

"г

Решение, Решение проводится

соответствии с вышеприведенным алгоритмом

Ответ /(.г,,

j^.

х^)^х^х^х^ + jCjjc^^i + х^х^х^,

Рассмотрим СНФ для других функций.

Пусть имеется терм вида Ф, = д:"' v х^^ v... v х"", где

[о,

если номер набора равен i;

Ф,=

I, если номер набора не равен г.

2 6. Совершенные нормальные формы

Если X,

= а,

можны случаи;

\) х,={)

а, =0

а, =1

л:"'

= X -^0

и а, — текущий элемент двоичного набора, то тогда воз-

2)д:,

=0 3)x, =1

а, =

а, =0

а,

0 а, =

*,"' = *, =

J^°' = X =

4) х, =

а, =1

а, =0

х^'

=х = 0.

В случае, когда х"' =

для х, -а,, терм Ф, можно использовать в

представлении (2.13) и (2.14).

Теорема. Любая ФАЛ, кроме абсолютно истинной функции,

лголсет быть представлена в совершенной конъюнктивной нормаль-

ной

форме

(СКНФ):

/(х,,Х2,..., д:^)-л(д:"' v д:"= V...V д:""). (2.2!)

Для представления логической функции используются операции И,

ИЛИ, НЕ(л, v,l).

Следствие: любая ФАЛ, кроме конституэнты !, может быть пред-

ставлена в виде

/(X,, Хз,..., х^) = ~(х"' ...vx"' V... vx""). (2.22)

Здесь используются операции неравнозначности, дизъюнкции, отрица-

ния

{-г

, V , 1

Пример 2.6.

laid

СКИФ для функции (см. табл. 2.1!).

Ре

111

е и и е , Решение проводится по формуле (2.2!)

'>io представление более

ромоздкое, чем представление этой функции в СНДФ, так как

в таблице много

cipoK,

для которых /==

В рассмотренных ранее объединениях термов были использованы для

записи термов /^,, и Ф,^ операции ИЛИ, НЕ, а также И, НЕ. Можно исполь-

зовать также набор из импликации (->) и отрицания (НЕ).

Способы преобразования НФ в СНФ. Совершенная нормаль-

ная форма огличаеюя от нормальной формы (НФ) тем, что всегда содержит

термы только максимального ранга и Дает однозиачное представление

функции.

Произвольная нормальная дизъюнктивная форма (НДФ) переводится в

СНДФ CJreдy^oшим образом.

2 Автомат как основной элемент информационных систем

Пусть /„ф = /^ . Тогда

/с„ф=/=;д:,

vf;^,,

(2.23)

где X,

~—

переменная, которая не входит в данный терм F,.

Пример 2.7. Логическую функцию, заданную

НДФ

f(x,,

JCj, Х-^, JC4) =

XjX'2'^

ДГ2^з^4'^

^1^3

•'^4^

X^XjXjX^

Fi F^ Fi

преобразовать в СНДФ.

Решение. Воспользуемся tipncMOM рфеобразования (2.23) поочередно

термам

Х^Х2 (^3

.?,

) =

Х^Х^Х^

Х|.Г,

Jj ,

Оба члена полученного выражения умножим

на

(jr^

J^)

В результате гюлучим

/•|

Х^Х^Х-^Х^

Х^Х2Х'^Х^

Х^Х^Х^Х^

Х^Х^ХуХ^

Аналогично,

= х^х^х^

V (д:, V jc,)

х^х^х^х^

Jc,^2-^3*4

••

i(i^3-'^4

(•'^l

"^ •*'2

) =

-^1-^2^3-^4

JC|^2'''3-*'4

•

После приведения подобных членов определяем СНДФ.

Ответ: /(дг,.

Лг,

-'^э- -'^4)

•*! -'^2

^з ^4 '^ ^i ^2 -^з-*'4

•*(

^г ^з ^•t ^-'^i

^г^г

-*'4

'^•'^i ^2 -^з

-^4

VX| ДГ2 ^3 ^4 ^ ^1 ^3 -^3 -^4 '^ ^1 -^^2 •'^З ^А -

Если максимальный ранг для функции равен г, а минимальный ран) у-го

терма равен к, ю преобразование (2.23) необходимо применить ку-му терму

{г-к) раз.

Произвольная НКФ переводится в СКНФ путем следующего преобра-

зования.

Пусть/нкф=Ф|. Тогда

/сикФ = '^1 V x,Xi = (Ф, V

)(Ф, V ж,). (2.24)

Пример 2.8. Преобразовать

СКНФ логическую функцию

f{X\

-г 2. -^3

) =

(^1

Xj)(X2

)

(J^i

Л;

JTj

) .

Ф|

Ф: Ф)

Решение. Применяем правило преобразований (2.24) поочередно к термам Ф^

Ф^

•

Ф, =(д:|

VJ:;)'^^

=(-^1

VJC2

УДГЗ)(Л|

VJCJ

VS^);

Ф2

=(J:J VX3)VJ:|X|

(J:, V JTJ

У1З)(Х|

V JTJ V

J,).

После упрощений СКНФ примет окончательный вид.

Ответ:

/С1СНФ(-^1'-^2'^з)

(^i ^

Д^г

д;,К-1С,

дг^

УХЗ)(1, УДГЗ

VJ,).

2 7 Системы функций алгебры логики

2.7. Системы функций алгебры логики

Рассмотрим теорему Жегалкина, которая играет важную роль в алгебре

логики.

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

ставлена многочленом вида f(x^, Х2,..., х„) =

kQ@

k^x^@ к2Х2® ...@

Ф*,„|Х|*2 Ф*»*2^1*з Ф--® *n+m^i*2*n'•"'^ *, —Коэффициенты, при-

нимающие значения

или 1.

Теорема Жегалкина дает возможность представить любую логическую

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

CyuieCTByeT несколько классов ФАЛ, которые также важны для логи-

ческо!

о анализа.

Класс линейных функций (Kj,). Булева функция называется линей-

ной,

если она представляется полиномом первой степени:

/(х,,Х2,...,х„) = ка®к,х,®к2Х2®...®к„х„.

KojHi4ecTBo линейных функций равно 2"^ . Например, для и - 2 коли-

чес

во линейных функции равно восьми, т. е.

1) У|(Х|,-т,) = 0;2) f2(x,,X2)

x,;J)

f,(x„X2)

X2;4)

f,(x„X2)

х,®Х2;

5) y,{V|,.v,) = l®^;6) f„(x„X2)

l®X2;l)

f^(x^,X2)

^®x^®X2•,

8)Л(-«|,^2) = 1-

Класс функций, сохраняющих нуль (К„). Если функция на нуле-

вом наборе неременных равна нулю, то говорят, что функция сохраняет

нуль:

/(0,0,...,0) = 0.

^1ля двух неременных (табл. 2.15) такими функциями являются

/|' 72' ,А' fi- /5'.Аб'/7' Л

•

Класс функций, сохраняющих единицу (К,). Если функция на еди-

ничном наборе переменных равна единице, то говорят, что такая функция

со.чраняет единицу:

/(1,1,...,

1) = 1. Для двух переменных такими функ-

циями являются ./2,/4,Л,/8,/|о,/|2,У|4./|б (см. табл. 2.15).

Класс монотонных функции (К„). Функция алгебры логики называ-

йся монотонной, если при ;гюбом возрастании набора значения этой функ-

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

функции .А,./г.л,/б,л./и (см. табл. 2.15).

2. Автомат как основной элемент информационных систем

Таблица 2.15

Функция

л.

/|0

/и

/|2

/п

/,4

/IS

/к,

0|Ч.,

()

Кл

к„

Классы

К|

к„

Кс

Класс самодвийствениых функций (К,). Функция алгебры

JIOIHKH

является самодвойственной, если на каждой паре противоположных набо-

ров она принимает противоположные значения, т. е.

/(*1,ДГ2,...,ДГ„)

/(*|,ЛГ2,...,ДГ„).

Для двух переменных такими функциями являются /4, Л, ./^р Уп •

Все названные выше классы функций обладают замечательным свой-

ством: любая функция алгебры логики, полученная с помощью операции

суперпозиции и подстановки из функций одного класса, обязательно будет

принадлежать этому же классу.

Базисом называется полная система ФАЛ, с помощью которой любая

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