лекционный материал. Логические элементы компьютера

• Название: Логические элементы компьютера
• Дата: 03.10.2022
• Размер: 134.72 Kb.
• Имя файла: лекционный материал.docx
• Тип: Закон; #711623
• страница: 2 из 5

2. Основные законы алгебры логики. Упрощение логических формул.

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

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

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

№	Закон	Представление в алгебре логики
1	Переместительный (коммутативный)	a  b = b  a, a  b = b  a
2	Сочетательный (ассоциативный)	a  (b  c) = (a  b)  с, a  (b  c) = (a  b)  c
3	Распределительный (дистрибутивный)	a  (b  c) = (a  b)  (a  c), a  (b  c) = (a  b)  (a  c)
4	Правила де Моргана	 (a  b) = a  b,  (a  b) = a  b
5	Закон двойного отрицания (инволюции)	  а = а
6	Операции с переменной и ее инверсией	a   a = 0, a  a =1
7	Операции с константами	a  1 = 1, a  1 = a, a  0 = a, a  0 = 0
8	Законы идемпотентности	a  a = a, a  a = a
9	Законы поглощения	x  (x  y) = x, x  (x  y) = x
10	Законы склеивания	(x  y)  ( x  y) = y, (x  y)  ( x  y) = y

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

Рассмотрим на примерах некоторые приемы и способы, применяемые при упрощении логических формул.

Пример 1.

 (х  у) · (х ·  у) =  х ·  у · (х ·  у) =  х · х · у ·  у = 0 · у ·  у = 0 · у = 0
(Законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с её инверсией и правило операций с константами).

Пример 2.

 х · у  (х  у)  х =  х · у   х ·  у  х =  х · (у  у )  х =  х  х = 1
(Применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией).

Пример 3.

(х  у) · ( х  у ) · ( х   у) = (х  у) · ( х  у ) · ( х  у ) · ( х   у) = у ·  х
(Повторяется второй сомножитель, что разрешено законом идемпотенции; затем комбинируются два первых и два последних сомножителя и используется закон склеивания).

Пример 4.

 (х · у   z) =  (х · у) ·  z =  (х · у) · z
(Сначала добиваемся, чтобы знак отрицания стоял только перед отдельными переменными, а не перед их комбинациями, для этого применяем правило де Моргана; затем используем закон двойного отрицания);

Пример 5.

х · у  х · у · z  х · р · z = х · (у  у · z  z · р) = х · (у · (1  z)  z · р) =

= х · (у  z · р)

(Выносятся за скобки общие множители; применяется правило операций с константами);

Пример 6.

x · y  x · y · z  x · y · z  x ·(y · z ) = x · ( y  y · z   y · z  (y · z )) =

= x · (( y  y · z )  (y · z  (y · z )) = x · ( y  y · z  1) = x · 1 = x
(Общий множитель x выносится за скобки, комбинируются слагаемые в скобках — первое с третьим и второе с четвертым, к дизъюнкции применяется правило операции переменной с её инверсией);

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