Файл: Дроздов Е.А. Многопрограммные цифровые вычислительные машины.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 11.04.2024

Просмотров: 300

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Переместительный закон, или закон коммутативности, для ло­ гического сложения: дизъюнкция Х\ и х2 равносильна дизъюнк­ ции Л'2 и Xi.

*1 V а2 = *2 V *1-

(3

Переместительный закон, или закон коммутативности, для ло­ гического умножения: конъюнкция Х\ и х2 равносильна конъюнк­

ции Х2 и Xi.

(3.4)

Ху Х2 = х 2х 1.

Сочетательный закон, или закон ассоциативности, для логиче­ ского сложения: дизъюнкция вида (*iVx2) V-^з равносильна дизъ­

юнкции вида XiV (a2\ / as).

 

(Xi V х г) \J х й = х 1 у ( х 2 V а3).

(3.5

Сочетательный закон, или закон ассоциативности, для логиче­

ского умножения:

конъюнкция

вида (xix2 )x3 равносильна конъюнк­

ции xi(x2x3).

 

 

(3.

 

{ х 1х 2) х й = х 1 { х 2х й).

Первый распределительный,

или первый дистрибутивный,

за­

кон: конъюнкция

вида Ai (x2 V a3) равносильна дизъюнкции

вида

(хух2) V {х\хъ), или логическое

умножение дистрибутивно относи­

тельно логического сложения.

 

 

 

Ху { Х2 V А3) =

(AjA'j) V (AjAj).

(3.

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

В алгебре логики, как и в обычной алгебре, принимается, что действие умножения предшествует действию сложения, т. е. ло­ гическое умножение связывает двоичные переменные и формулы сильнее логического сложения. Это также позволяет упростить запись логических формул и соотношений. Так, соотношение (3,7)

можно записать в следующем

виде:

х х { х 2 V а 3) =

ХуХ2 V Ху Хя.

Второй распределительный, или второй дистрибутивный, закон: дизъюнкция вида Х\Х2хг равносильна конъюнкции вида {х{ V хг) XI X (X| V *3). или логическое сложение дистрибутивно относительно логического умножения.

Ху V а 2а 3 = (Ху V А2) {Ху V А3).

(3.8)

78

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

Закон инверсии для логического сложения: отрицание дизъюнк­ ции двух логических переменных равносильно конъюнкции их от­ рицаний.

Х 1 V х 2 — Х 1Х2Ш

(3

Закон инверсии для логического сложения распространяется и на формулы с любым числом логических переменных, соединенных знаком логического сложения. Его аналитическая форма в этом случае записывается так;

 

( £ • * * ) = Д *£•

(3-10)

Законинверсии

для логическЪгоумножения:

отрицание

конъюнкции двухлогических переменныхравносильно дизъюнк­ ции их отрицаний.

х 1 х 2 = х 1\/ х 2.

(3.11)

Этот закон распространяется на формулы с любым числом логических переменных, соединенных знаком логического умно­ жения:

(д*1) (ЗЛ2)

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

сти [16].

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

записи таких соотношений пользуются, ’кроме того,

понятиями

всегда истинных и всегда ложных'высказываний.

 

Всегда истинные высказывания: х V

1= I; х \/ х = 1;

всегда лож­

ные высказывания:

х - 0= 0; х - х = 0 .

высказывания — это такие

Всегда истинные

и всегда ложные

сложные высказывания, которые остаются истинными или лож­ ными независимо от значений истинности составляющих их про­ стых высказываний. Величины 1 и 0 являются константами, выра­

79

жающими, по существу, соответственно всегда истинный н всегда ложные высказывания.

Обобщение понятий всегда истинных и всегда ложных выска­

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

 

н у 1 =

1,

Н- 0 =

0,

 

H \ J H =

1,

я - я =

о,

(ЗЛЗ)

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

Из соотношений (3.13) выводятся следующие правила.

Если логическая сумма двоичных переменных (формул) содер­ жит хотя бы одну пару слагаемых, из которых одно есть некоторая переменная (формула), а другое-— ее отрицание, то она является тождественно истинной:

М V *5 V V *4 = 1.

Если логическое произведение двоичных переменных содержит хотя бы одну пару множителей, из которых один есть некоторая переменная (формула), а другой — ее отрицание, то оно является тождественно ложным:

ЯГ Я 2-Я 4-Я 2 = 0.

§3.4. Формы логических функций

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

F{xu хъ . . . , хп) = Н и

(3.14)

где Н\ — формула алгебры логики, представляющая собой опреде­

ленное соединение переменных X i ( i = 1,

2,

..., п)

и их групп знака­

ми конъюнкции, дизъюнкции и отрицания.

(3.14)

правила эквива­

Применяя к правой части выражения

лентных преобразований, получим:

 

 

 

F ( x u х?,. . . . хп) —Нъ

 

F{xlt

хъ . . . , х п) =

Я 3,

 

F (лу,

Х4, . ■•) х п)

Нт,

 

где # 2, #з, . . Нт— формулы, эквивалентные

Н\.

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

80

щие

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

для

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

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

тарной

дизъюнкции.

Элемента1рной конъюнкцией Q называется логическое произве­

дение

переменных и их отрицаний. Так, Q = xix2x3x^x5 является

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

Число переменных,

составляющих элементарную конъюнкцию,

называется

ее ра нг ом.

Если, например, произведена запись

Qk"', то это

означает,

что

некоторая k-я. конъюнкция имеет п-й

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

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

отрицания. Н_апрнмер, конъюнкции четвертого ранга Q(4) = x 1 x 2 x ax i

и= x lx 2 x ix i являются соседними.

Конъюнкция т-го ранга называется и з о л и р о в а н н о й по отношению к данному множеству конъюнкций такого же т-го ранга, если внутри этого множества нет ни одной конъюнкции, со­

седней с заданной. Например, конъюнкция Qi” = x 1 x 2x 3x i яв­ ляется изолированной jno отношению к конъюнкциям Q ^ ^ x ^ x ^ ,

СЙ0 = x lx 2 x sx i, Ql,'} = x xx 2 x zx ,t так как ни Qг4), ни <3з4), ни О44) не

является соседней с Q\ .

Аналогично понятию элементарной конъюнкции вводится поня­ тие элементарной дизъюнкции.

Элементарной дизъюнкцией D называется логическая сумма ин­ версированных или неинверсированных переменных, причем каж­

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

К элемен­

тарным относится, например, дизъюнкция D = x t V х 2

V -Ч) V x i•

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

Определение. Формула, эквивалентная данной формуле и пред­ ставляющая собой логическую сумму элементарных конъюнкций,

Смотрите также файлы