Цифровая схемотехника
г(й,ц,у)ъйм(цду)оц |
(1.5) |
Порядок выполнения операций определяется иерархией. В первую очередь выполняется операция отрицание, следующая в иерархии – конъюнкция, на третьем месте – операции дизъюнкция и сложение по модулю два. Далее идут все остальные операции. Скобки применяют для изменения порядка выполнения операций.
Одну и ту же функцию можно записать аналитически различными способами, выражая ее через определенные выше элементарные функции. Но для записи функций алгебры логики не обязательно использовать все вышеприведенные операции. Можно доказать, что ограниченный набор некоторых операций (или даже всего одной) позволяет записывать любую, сколь угодно сложную функцию алгебры логики. Такой набор операций называется функционально полной системой или базисом. Базисами являются, например, наборы операций:
дизъюнкция, конъюнкция и отрицание;
импликация и константа 0;
запрет и константа 1;
штрих Шеффера;
стрелка Пирса.
Базис, состоящий из операций дизъюнкция, конъюнкция и отрицание называют основным, именно для него разработаны методы минимизации функций.
Минимальным базисом называется такой базис, для которого исключение хотя бы одной из составляющих его функций превращает данную систему функций в неполную. Можно показать, что основной базис является функционально излишним. Минимальным будет базис, состоящий только из операций дизъюнкция и отрицание или только из операций конъюнкция и отрицание.
1.4. Свойства операций алгебры логики
Для упрощения формул необходимо прежде всего рассмотреть свойства основных операций. Так как область определения любой функции алгебры логики ограничена, то доказать равносильность можно просто путем перебора всех возможных наборов аргументов.
Чаще всего для записи и преобразования формул алгебры логики используют основной базис, поэтому рассмотрим более подробно свойства (или законы) операций дизъюнкция, конъюнкция и отрицание.
1.4.1. Свойства операции отрицание |
|
a) Закон двойного отрицания: |
|
еъП |
(1.6) |
Докажем по таблице истинности (табл. 1.14):
12
е |
п |
П |
|
|
|
0 |
1 |
0 |
1 |
0 |
1 |
Комбинационные схемы
Табл. 1.14
b) Если еън, то ЕъН. Доказательство (табл. 1.15):
Табл. 1.15
е |
н |
Е |
Н |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
Следствие:
Если еъН, то Еън,
т.е. знак отрицания, стоящий над всем выражением, можно переносить в другую часть равносильности.
1.4.2. Свойства операций конъюнкция и дизъюнкция |
|
a) Законы нулевого множества: |
|
ем0ъе |
(1.7) |
ес0ъ0 |
(1.8) |
b) Законы универсального множества: |
|
ем1ъ1 |
(1.9) |
ес1ъе |
(1.10) |
c) Законы идемпотентности: |
|
емеъе |
(1.11) |
есеъе |
(1.12) |
Обобщая для случая n аргументов, получим: |
|
емемимеъе |
|
есесисеъе |
|
d) Закон исключенного третьего: |
|
емЕъ1 |
(1.13) |
e) Закон логического противоречия: |
|
есЕ=0 |
(1.14) |
f) Коммутативные законы: |
|
ймцъцмй |
(1.15) |
йсцъцсй |
(1.16) |
g) Ассоциативные законы: |
|
йм(цму)ъ(ймц)муъймцму |
(1.17) |
й(цу)ъ(йц)уъйцу |
(1.18) |
Доказательство по таблице истинности (табл. 1.16):
13
Цифровая схемотехника
|
|
|
|
|
|
|
Табл. 1.16 |
|
|
|
|
|
|
|
|
|
|
x1 |
x2 |
x3 |
x2 x3 |
x1 x2 |
x1 (x2 x3) |
(x1 x2) x3 |
x1 x2 x3 |
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
h) Дистрибутивные законы |
|
конъюнкции относительно дизъюнкции: |
|
й(цму)ъйцмйу |
(1.19) |
дизъюнкции относительно конъюнкции: |
|
ймцуъ(ймц)(йму) |
(1.20) |
Доказательство по таблице истинности. Дистрибутивные законы используются для раскрытия скобок, группировки, вынесения за скобки и т.д., например:
abмacъa(bмc) (1.21) (aмb)(aмc)ъaмbc (1.22)
i) Законы де Моргана:
Операции конъюнкции и дизъюнкции связаны между собой:
|
ЙСЦъЙмЦ |
|
(1.23) |
|||
или |
|
|
|
|
|
|
|
ЙМЦъЙсЦ |
|
(1.24) |
|||
Доказательство по таблице истинности (табл. 1.17): |
||||||
|
|
|
|
|
|
Табл. 1.17 |
|
й |
ц |
йц |
ЙЦ |
ЙмЦ |
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
1 |
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
1 |
1 |
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
1 |
1 |
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
0 |
|
|
|
|
|
|
|
|
Этот закон легко обобщить для случая n аргументов:
ЙЦИЕnъфмымимпn ЙМЦМИМЕnъфсысиспn
Пример применения:
_________
фмымвъйцу
14
|
Комбинационные схемы |
|
|
|
|
j) Правила склеивания: |
|
|
AемAпъA |
(1.25) |
|
(Aме)(Aмп)ъA |
(1.26) |
|
Доказательство: |
|
|
AемAпъA(емп)ъAс1ъA |
|
|
k) Правила поглощения: |
|
|
ABмA≡A |
(1.27) |
|
(AмB)A≡A |
(1.28) |
|
Доказательство:
ABмA≡A(Bм1)≡Aс1≡A
Необходимо заметить, что правила склеивания и поглощения могут быть применены и в обратном направлении, т.е.
A≡AмAB |
(1.29) |
A≡AxмAп |
(1.30) |
1.4.3. Свойства операций штрих Шеффера и стрелка Пирса
Для операций штрих Шеффера и стрелка Пирса справедлив коммутативный закон и несправедлив ассоциативный закон (доказа-
тельство по таблице истинности): |
|
йоцъцой |
(1.31) |
йлцъцлй |
(1.32) |
йо(цоу)Ъ(йоц)луЪйоцоу |
(1.33) |
йл(цлу)Ъ(йлц)луЪйлцлу |
(1.34) |
Операции штрих Шеффера и стрелка Пирса могут быть выражены через функции конъюнкции, дизъюнкции и отрицания (доказательство по таблице истинности):
йоцъЙЦъЙмЦ |
(1.35) |
йлцъЙМЦъфы |
(1.36) |
Операции отрицание, конъюнкция и дизъюнкция можно выразить через операцию штрих Шеффера.
Отрицание:
пъеое (доказательство по табл. 1.18) |
(1.37) |
е |
еое |
п |
|
|
|
0 |
1 |
1 |
|
|
|
1 |
0 |
0 |
Конъюнкция:
йцъЙЦъЙОЦъ(йоц)о(йоц)
Дизъюнкция:
ймцъФЫъфоыъ(йой)о(цоц)
Табл. 1.18
(1.38)
(1.39)
15