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

§ 3.2. Логические связи, операции, функции

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

Л о г и ч е с к а я с в я з ь НЕ, или л о г и ч е с к о е о т р и ц а н и е

Отрицанием высказывания р называется такое сложное выска­ зывание Р, которое истинно, когда р ложно, и ложно, когда р

истинно.

Эта логическая связь записывается (обозначается) так:

Р = Р,

что читается следующим образом: «Р есть (эквивалентно) не р»

П

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

Р\ (х ) = х.

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

Л о г и ч е с к а я с в я з ь ИЛИ, или д и з ъ ю н к ц и я в ы с к а з ы в а н и й , ил и л о г и ч е с к о е с л о ж е н и е

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

Эта логическая связь обозначается с помощью знака сложения или с помощью специального знака:

Р = р + <7, или Р = р \ / q.

Читается любая из записей рассматриваемой логической связи ■так: «Р есть р или q».

При дальнейшем изложении материала логическая связь ИЛИ обозначается знаком «V»-

Рассматривая дизъюнкцию как некоторую логическую функдию, запишем для этого случая, что

Р2 {хи х 2) = х 1 V x2.

Логическая связь ИЛИ может применяться одновременно ко многим исходным высказываниям.- ^ этом случае образованное сложное высказывание Р= р\\/РъУ - V Рп ложно только тогда, когда

.ложны все исходные высказывания p ,( t'= 1, 2, . .., п). Аналогично функция

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

сложное высказывание Р. которое истинно только в том случае, когда истинны и р и q: во всех остальных случаях высказывание Р ложно. . .

73

Эта логическая связь обозначается с помощью знака умноже­ ния или с помощью специальных знаков:

Р — р-сL или P = pq, или Р = р /\q, или P — p&q.

Читается любая из записей рассматриваемой логической связи так: «Р есть р и q».

При дальнейшем изложении материала логическая связь И обозначается в виде произведения; используется также знак «Д».

Рассматривая конъюнкцию как некоторую логическую функ­ цию, запишем для этого случая, что

F* (*i, х 2) = х гх 2.

Логическая связь И может применяться одновременно ко мно­ гим исходным высказываниям. В этом случае образованное слож­ ное высказывание Р — р\р2 ... рп истинно только тогда, когда истинны все исходные высказывания /7,-(/=1, 2, ..., п). Аналогично

функция

П

Р (Aj, А2, . . . , А'„) = X i X 2 . . . Х п = А Х (

1=1

имеет значение единицы только тогда, когда все переменные Xi имеют значения единицы. Она имеет значение нуля тогда, когда хотя бы одна из переменных а,- имеет значение нуля (см. данные табл. 3.1).

И м п л и к а ц и я д в у х в ы с к а з ы в а н и й

Импликация двух высказываний р и q представляет собой сложное высказывание Р, которое ложно в том и только том слу1 чае, когда р истинно, a q ложно.

Эта связь обозначается так:

P = p-+q,

что читается: «Р есть, если р, то q», или «Р есть из р сле­

дует q».

Рассматривая импликацию как некоторую логическую функ­ цию, запишем для этого случая, что

Р А Х1. а2) = а1-> а2.

Р а в н о з н а ч н о с т ь д в у х в ы с к а з ы в а н и й

Равнозначность двух высказываний р и q представляет собой сложное высказывание Р, которое истинно, когда значения истин­

P = s p o o q t

что читается: «Р есть р равнозначно q».

74

Рассматривая равнозначность как некоторую логическую функ­ цию, запишем для этого случая, что

Р 5 ( х ь х 2) = х 1 ы х 2.

О п е р а ц и я ( с т р е л к а ) П и р с а

Операция Пирса над высказываниями р и q приводит к слож­ ному высказыванию Р, которое истинно в том и только том слу­ чае, когда ложны р и q.

Эта операция записывается следующим образом:

Р = Р 1 <7,

или

Fa (•*!> * 2 ) = * 1 1 * 2 .

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

Несовместность двух высказываний р и q представляет собой сложное высказывание Р, которое ложно в том и только том слу­ чае, когда истинны р и q.

Эта логическая связь записывается так:

Р = р f q,

что читается: «Р есть р несовместно q».

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

F\ (хи х 2) = х г f *2-

О п е р а ц и я з а п р е т а

Операция запрета над высказываниями р и q приводит к слож­ ному высказыванию Р, которое истинно в том и только том слу­ чае, когда р истинно, a q ложно.

Эта операция записывается следующим образом:

P = p + - q ,

или

Fs (-^i) ^2) ■х± <—х 2.

Л о г и ч е с к а я с в я з ь ИЛИ — ИЛИ, или о т р и ц а н и е р а в н о з н а ч н о с т и д в у х в ы с к а з ы в а н и й ,

или н е р а в н о з н а ч н о с т ь

Отрицание равнозначности двух высказываний р и q представ­ ляет собой сложное высказывание Р, которое истинно, когда зна­ чения истинности р и q не совпадают, и ложно, когда значения истинности р и q совпадают.

75

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

Отрицание равнозначности записывается так:

P = p ^ q , Ил и Я = /7оо <7,

что читается так: «Р есть р неравнозначно q», или «Р есть или р, или <7».

Рассматривая неравнозначность как некоторую логическую функцию, запишем для этого случая, что

Л 9 U i . * 2 ) = * 1 ~

Логическую связь ИЛИ — ИЛИ можно рассматривать как ло­ гическую операцию сложения по модулю два (mod 2 ), которая ана­ логична арифметическому сложению одноразрядных двоичных чи­ сел без переноса в старший разряд. Логическая операция сложе­ ния по mod 2 часто обозначается знаком «®». Поэтому функцию Fg(x\, х2) можно выразить так:

Рд(хи х 2) = х 1 Ф х 2.

Рассмотренные функции F2 + F9 могут строиться применитель­ но к различным сочетаниям переменных. Однако во всех случаях их смысл остается таким же, как и в случае их построения для двух логических переменных.

Сопоставляя значения функций F2 -t-F9, приведенные в табл. 3.1^ устанавливаем, что F2 и F6, F3 и F7, F4 и Fs, F5 и Fg попарно взаим­ но инверсны, т. е. являются отрицанием одна другой, принимая на одних и тех же наборах переменных противоположные значения ис­ тинности:

=Fs = Ла, или x ,соx 2 = л;,:®x 2, x i cvx2 = x 1 <£>x2.

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

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

76

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

Для выражения сложных логических функций достаточно ис­ пользовать не все элементарные функции, а только ту или иную часть их, называемую системой. Система элементарных функций Fu F2, .... Fh называется ф у н к ц и о н а л ь н о по л но й , если любую функцию алгебры логики можно записать в виде формулы через функции F\, F.........F^ Таким образом, полная система представ­ ляет собой набор элементарных функций, позволяющий выражать любые сложные логические функции; как правило, этот набор яв­

3) F3 (хь х2) = XjX2; F j (х) = х ; 4) Д6 (jclt х 2) = х { I х2;

5) F, (хи ха) = Ху t х2.

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

Элементарные логические функции Fi-hFg выражаются через функции первой полной системы так:

F^ (хь х 2) = х, -> х2 = х, v х2 = х ух2,

§ 3.3. Основные законы алгебры логики

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

77