- •Основы алгебры логики
- •Логические схемы и таблицы истинности
- •Алгоритм построения таблицы истинности
- •Основные законы алгебры логики
- •Согласно закону обшей инверсии для логического сложения (первому закону де Моргана) и закону двойного отрицания:
- •Согласно распределительному (дистрибутивному) закону для логического сложения:
Основные законы алгебры логики
Закон |
Для ИЛИ (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:
Согласно закону обшей инверсии для логического сложения (первому закону де Моргана) и закону двойного отрицания:
__________________
__ ___ ____
( А v В v С ) & А v В v С = ( А v В v С ) & ( А & В & С )
Согласно распределительному (дистрибутивному) закону для логического сложения:
___ ____ ____ ____ ____
( А v В v С ) & ( А & В & С ) = ( А & А ) v ( В & А ) v ( C & A ) v ( A & В ) v
_____ ____ _____
v ( B & В ) v ( C & B ) v ( А & С ) v ( В & С ) v ( С & С )
Согласно закону противоречия:
____ ____
( А & А) = 0; ( С & С) = 0;
Согласно закону идемпотентности:
( В & В ) = В
Подставляем значения и, используя переместительный (коммутативный) закон и группируя слагаемые, получаем:
___ ___ ____ ____
0 v ( А & В ) v ( А & В ) v В v ( С & В ) v ( С & В ) v ( С & А ) v ( А & С) v 0
Согласно закону исключения (склеивания):
___ ___
( А & В ) v ( А & В ) = В; ( С & В ) v ( С & В ) = В;
Подставляем значения и получаем:
___ ___
0 v В v В v В v ( С & А) v ( А & С) v 0
Согласно закону исключения констант для логического сложения и закону идемпотентности:
0 v В v 0 v В v В = В
Подставляем значения и получаем:
___ ___
В v ( С & А ) v ( А & С )
Согласно распределительному (дистрибутивному) закону для логического умножения:
___ ___ ____ ___ ___ ___
( С & А ) v ( А & С ) = ( С v А ) & ( С v С ) & ( А v А ) & ( А v С )
Согласно закону исключения третьего:
___ ___
( C v С ) = 1; ( А v А) = 1;
Подставляем значения и окончательно получаем:
___ ___
В & А & С
Примеры: (в тексте вначале примера перечислена последовательность действий)
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 элементов.