| Закон | Для ИЛИ (v) | Для И (&) |
| Переместительный (коммутативный) | AvB=BvA | A&B=B&A |
| Сочетательный (ассоциативный) | (AvB)vC=Av(BvC) | (A&B)&C=A&(B&C) |
| Распределительный (дистрибутивный) | (AvB)&C=(A&C)v(B&C) | (A&B)vC=(AvC)&(BvC) |
| Общей инверсии (правило де Моргана) | _______ __ __ AvB=A&B | ___ _ _ A&B=AvB |
| Идемпотентности | AvA=A | A&A=A |
| Исключения констант | Av1=1 и Av0=A | A&1=A и A&0=0 |
| Противоречия | __ A&A=0 | |
| Исключения третьего | __ AvA=1 | |
| Поглощения | Av(A&B)=A | A&(AvB)=A |
| Склеивания (исключения) | _ (A&B)v(A&B)=B | _ (AvB)&(AvB)=B |
| Контрапозиции (правило перевертывания) | (A↔B)=(B↔A) | |
| Двойного отрицания | = А = А |
Под упрощением логической формулы, не содержащей операций импликации и эквиваленции, понимают равносильное преобразование, приводящее к формуле, которая: либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул, либо содержит меньшее число вхождений переменных.
Задача 7: Упростить логическую формулу: (законы алгебры логики применяются в определенной последовательности) _________________
___
(А v В v С) & А v В v С
Решение 7:
Шаг 1. Согласно закону обшей инверсии для логического сложения (первому закону де Моргана) и закону двойного отрицания:
__________________
__ ___ ____
(А v В v С) & А v В v С = (А v В v С) & (А & В & С)
Шаг 2. Согласно распределительному (дистрибутивному) закону для логического сложения:
___ ____ ____ ____ ____
(А v В v С) & (А & В & С) = (А & А) v (В & А) v (C & A) v (A & В) v
_____ ____ _____
v (B & В) v (C & B) v (А & С) v (В & С) v (С & С)
Шаг 3. Согласно закону противоречия:
____ ____
(А & А) = 0; (С & С) = 0;
Шаг 4. Согласно закону идемпотентности:
(В & В) = В
Шаг 5. Подставляем значения и, используя переместительный (коммутативный) закон и группируя слагаемые, получаем:
___ ___ ____ ____
0 v (А & В) v (А & В) v В v (С & В) v (С & В) v (С & А) v (А & С) v 0
Шаг 6. Согласно закону исключения (склеивания):
___ ___
(А & В) v (А & В) = В; (С & В) v (С & В) = В;
Шаг 7. Подставляем значения и получаем:
___ ___
0 v В v В v В v (С & А) v (А & С) v 0
Шаг 8. Согласно закону исключения констант для логического сложения и закону идемпотентности:
0 v В v 0 v В v В = В
Шаг 9. Подставляем значения и получаем:
___ ___
В v (С & А) v (А & С)
Шаг 10. Согласно распределительному (дистрибутивному) закону для логического умножения:
___ ___ ____ ___ ___ ___
(С & А) v (А & С) = (С v А) & (С v С) & (А v А) & (А v С)
Шаг 11. Согласно закону исключения третьего:
___ ___
(C v С) = 1; (А v А) = 1;
Шаг 12. Подставляем значения и окончательно получаем:
___ ___
В & А & С
Примеры: (в тексте вначале примера перечислена последовательность действий)
4. правило де Моргана, сочетательный закон, правило операций переменной с ее инверсией и правило операций с константами:
____ __ _ _ __ __ __ __ __ __ __
XvY•(X•Y)=X•Y•(X•Y)=X•X•Y•Y=0•Y•Y=0•Y=0
5. правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с ее инверсией:
__ _____ __ _ _ _ __ __
X•YvXvYvX=X•YvX•YvX=X•(YvY)vX=XvX=1
6. повторяется второй множитель, что разрешено законом идемпотентности, затем комбинируются 2 первых и 2 последних множителя и используется закон склеивания:
__ __ __ __ ___ __ ___ __
(XvY)•(XvY)•(XvY)=(XvY)•(XvY)•(XvY)•(XvY)=Y•X
_
7. вводится вспомогательный логический множитель YvY, затем комбинируются 2 крайних и 2 средних логических слагаемых и используются законы поглощения и склеивания:
__ __ __ __ __ __ __ __
X•YvX•Y•ZvX•Z=X•YvX•Y•ZvX•Z•(YvY)=X•YvX•Y•ZvX•Y•ZvX•Y•Z=
___ ___ ___ ___
=(X•YvX•Y•Z)v(X•Y•ZvX•Y•Z)=X•YvY•Z
8. начала добиваются, чтобы знак отрицания стоял только перед отдельными переменными, а не перед их комбинациями, для этого дважды применяется правило де Моргана, затем используется закон двойного отрицания: _____ _
__ ______ __ __ __
X•YvZ=X•Y•Z=(XvY)•Z
9. выносятся за скобки общие множители, применяется правило операций с константами:
X•YvX•Y•ZvX•Z•P=X•(Y•(1vZ)vZ•P)=X•(YvZ•P)
10. к отрицаниям неэлементарных формул применяется правило де Моргана, используются законы двойного отрицания и поглощения:
_______ ____________ __ ___ __
___ __ ___ __ __ ___ __ __ __ ___ ___ __
XvY•ZvXvYvZ=XvYvZvX•Y•Z=XvYvZvX•Y•Z=XvZv(YvX•Y•Z)=XvYvZ
11. общий множитель Х выносится за скобки, комбинируются слагаемые в
_______
скобках — 1-е с 3-м и 2-е с 4-м, к дизъюнкции Y•ZvY•Z применяется правило операции переменной с ее инверсией:
___ __ ______ __ ___ _______ ___ ___ _______
X•YvX•Y•ZvX•Y•ZvX•Y•Z=X•(YvY•ZvY•ZvY•Z)=X•((YvY•Z)v(Y•ZvY•Z))=
___ ____
=X•(YvY•Zv1)=X•1=X
12. используются распределительный закон для дизъюнкции, правило операции переменной с ее инверсией, правило операций с константами, переместительный закон, распределительный закон для конъюнкции:
__ ___ __ ___ ___ ___ ___ ___ __ __ __ ___ ___
(X•YvZ)•(XvY)vZ=X•Y•XvX•Y•YvZ•XvZ•YvZ=0v0vZ•XvZ•YvZ=Z•Xv(ZvZ)•(YvZ)=
___ ___ ___ ___ ___ __ ___ ___ ___ ___ ___ ___ ___
=Z•Xv1•(YvZ)=Z•XvYvZ=(Z•XvZ)vY=(ZvZ)•(XvZ)vY=1•(XvY)vY=XvYvZ
13. используются правило де Моргана, закон двойного отрицания и закон поглощения: ___ __________ ______
_______ __ _______ __
X•Y•(X•ZvX•Y•ZvZ•t)=X•Y•(X•ZvX•YvZvZ•t)=
___ ___ ___
=X•Y•(X•ZvX•YvZvZ•t)=X•YvX•Y•ZvX•Y•Z•t=X•Y
*****
_______
_______ __
14. решить уравнение: Х+А+Х+А=В
по закону Де Моргана:
___ _ _ _ _ = _ _ _
ХvА=А•В Х•АvХ•А=В Х•АvХ•А=В
_ _ _ _ _
Х•(АvА)=В АvА=1 Х=В Х=В
*****
Логический элемент компьютера — это часть электронной логической схемы, которая реализует элементарную логическую функцию. Обычно, у элементов от 2-х до 8-ми входов и 1 или 2 выхода. Работу логических элементов описывают с помощью таблиц истинности.
Задача 8: Какое количество базовых логических элементов образуют оперативную память компьютера объемом 512 Мбайт?
Решение 8: Количество базовых логических элементов в триггере – 4. Количество бит в ячейке оперативной памяти – 8.
Отсюда: 4*8*512*1024*1024=17’179’869’184 элементов.
Задача 9: Какое количество базовых логических элементов необходимо для реализации 64-разрядного сумматора двоичных чисел?
Решение 9: Для построения одноразрядного сумматора двоичных чисел необходимо 9 базовых логических элементов.
Отсюда: 9*64=576 элементов.