Законы поглощения и склеивания исключения. Законы поглощения алгебра логики

Современные компьютеры, основанные на «древних» электронно-вычислительных машинах, в качестве базовых принципов работы опираются на определенные постулаты. Они называются законы алгебры логики. Впервые подобная дисциплина была описана (конечно, не столь подробно, как в современном виде) древнегреческим ученым Аристотелем.

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

С тем чтобы лучше разобраться в теме, разберем понятия, которые помогут в дальнейшем узнать законы алгебры логики.

Пожалуй, основной термин в изучаемой дисциплине - высказывание. Это некое утверждение, которое не может быть одновременно ложным и истинным. Ему всегда присуща лишь одна из этих характеристик. При этом условно принято истинности придавать значение 1, ложности - 0, а само высказывание называть некой A, B, C. Иначе говоря, формула A=1 означает, что высказывание А истинно. С высказываниями можно поступать самым различным образом. Вкратце рассмотрим те действия, которые можно с ними совершать. Отметим также, что законы алгебры логики невозможно усвоить, не зная этих правил.

1. Дизъюнкция двух высказываний - результат операции «или». Может быть или ложной, или истинной. Используется символ «v».

2. Конъюнкция. Результатом подобного действия, совершаемого с двумя высказываниями, станет новое лишь в случае, когда оба исходных высказывания истинны. Используется операция «и», символ «^».

3. Импликация. Операция «если А, то В». Результатом является высказывание, ложное лишь в случае истинности А и ложности В. Применяется символ «->».

4. Эквиваленция. Операция «A тогда и только тогда В, когда». Данное высказывание истинно в случаях, когда обе переменные имеют одинаковые оценки. Используется символ «<->».

Существует также ряд операций, близких к импликации, но в данной статье они рассмотрены не будут.

Теперь подробным образом рассмотрим основные законы алгебры логики:

1. Коммутативный или переместительный гласит, что перемена мест логических слагаемых в операциях конъюнкции или дизъюнкции на результате не сказывается.

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

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

4. Закон де Моргана (инверсии или отрицания). Отрицание операции конъюнкции равносильно дизъюнкции отрицания исходных переменных. Отрицание от дизъюнкции, в свою очередь, равно конъюнкции отрицания тех же переменных.

5. Двойное отрицание. Отрицание некоего высказывания дважды дает в результате исходное высказывание, трижды - его отрицание.

6. Закон идемпотентности выглядит следующим образом для логического сложения: x v x v x v x = x; для умножения: x^x^x^=x.

7. Закон непротиворечия гласит: два высказывания, если они противоречивы, одновременно быть истинными не могут.

8. Закон исключения третьего. Среди двух противоречивых высказываний одно - всегда истинное, другое - ложное, третьего не дано.

9. Закон поглощения можно записать таким образом для логического сложения: x v (x^y)=x, для умножения: x^ (x v y)=x.

10. Закон склеивания. Две соседние конъюнкции способны склеиться, образовав конъюнкцию меньшего ранга. При этом та переменная, по которой исходные конъюнкции склеивались, исчезает. Пример для логического сложения:

(x^y) v (-x^y)=y.

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

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

Дискретная математика: Математическая логика

Лекция 8

Минимизация булевых функций. Метод Квайна-МакКласки

Законы алгебры Буля

В математической логике определяется специальная алгебра, алгебра Буля, содержащая операции логического умножения, логического сложения и отрицания {  ,+, - }, которые позволяет производить тождественные преобразования логических выражений. К этим законам относятся

Закон идемпотентности (одинаковости)

Закон коммутативности

a  b = b a

Закон ассоциативности

a + (b + c) = (a + b) + c

a  (b  c) = (a  b)  c

Законы дистрибутивности

Дистрибутивность конъюнкции относительно дизъюнкции

A  (b + c) = a  b + a  c

Дистрибутивность дизъюнкции относительно конъюнкции

A + b  c = (a + b)  (a + c)

акон двойного отрицания

Законы де Моргана

Законы поглощения

a + a  b = a

a  (a + b) = a

Законы, определяющие действия с логическими константами 0 и 1

a + 0 = a

a  0 = 0

a + 1 = 1

a  1 = a

1 = 0

Правомерность всех рассмотренных выше законов может быть легко доказана, например, с использованием таблиц истинности.
Дополнительные законы

Дополнительные законы алгебры Буля являются следствиями из основных законов и очень полезны при упрощении записи логических функций.
Закон склеивания

Доказательство этого тождества проводится с использованием первого закона дистрибутивности:

Доказательство этого тождества проводится с использованием второго закона дистрибутивности:

Закон Блейка-Порецкого

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

Закон свертки логического выражения

Данное тождество можно доказать, последовательно используя законы работы с логическими константами, дистрибутивности, идемпотентности и склеивания:

Упрощение логических функций

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

Задачи.

Упростить СДНФ следующих функций:

1. (a b )  c

2. (a  b )  c

Представим функцию в совершенной дизъюнктивной форме и упростим ее с помощью законов алгебры логики:

СДНФ =

Дальнейшее упрощение невозможно.

Представим функцию в совершенной дизъюнктивной форме и упростим ее с помощью законов алгебры логики:

СДНФ =
5.

Представим функцию в совершенной дизъюнктивной форме и упростим ее с помощью законов алгебры логики:

Метод Квайна-МакКласки

Минимизация логических функций можно проводить с помощью метода Квайна-МакКласски, который состоит из четырех шагов:

Представим наборы (конституенты), на которых функция истинна, в виде двоичных эквивалентов.
Упорядочим двоичные эквиваленты по ярусам (по числу единиц двоечных эквивалентов) и провести склейку (применить правило склеивания к соответствующим конституентам) наборов в соседних ярусах, получая максимальные интервалы до тех пор, пока это возможно; помечаем каждый набор, участвовавший в склейке. Склеиваются только те наборы или интервалы, различие в которых заключается только в значении одного разряда: 001 и 000, 001- и 101-, и т.д.
Построим таблицу Квайна, столбцы которой соответствуют двоичные наборы истинности функции, а строки – максимальным интервалам. Если i-ый набор покрывается j-ым интервалом, то ставим 1 на пересечении соответствующих строки и столбца, в противном случае ставим 0 или ничего.
Находим минимальное покрытие таблицы Квайна, состоящее из минимального количества максимальных интервалов, включающих в себя (покрывающих) все наборы, на которых функция истинна.

Рассмотрим функцию F1, которая истинна на наборах {1, 3, 5, 7, 11, 13, 15}. Совершенная дизъюнктивная нормальная форма данной функции равна:

Двоичные эквиваленты истинных наборов следующие:

1	0001
3	0011
5	0101
7	0111
11	1011
13	1101
15	1111

Упорядочим двоичные наборы по ярусам и проведем склейки, до тех пор, пока это возможно

0001  	00-1 	0-1
0011  	0-01 	--11
0101  	-011 	-1-1
0111   	0-11  
1101  	-101 
1011  	01-1  
1111   	11-1 
	-111  
	1-11 

Затем строим таблицу Квайна:

	0001	0011	0101	0111	1011	1101	1111
0--1	1	1	1	1
--11		1		1	1	1	1
-1-1			1	1		1	1

В нашей таблице наборы 0001 и 1011 покрываются единственно возможным образом, следовательно, покрывающие их минимальные интервалы называются обязательными и образуют ядро покрытия , т.к. должны входить в любое покрытие. В таблице соответствующие единицы подчеркнуты, интервалы {0- -1,- -11} образуют не только ядро покрытие, но и покрывают всю таблицу Квайна.
Таким образом, мы получили минимальную форму исследуемой функции в виде:

МДНФ = {0 - - 1, - - 1 1} =

Рассмотрим несколько примеров.
Задачи.

1. Найти МДНФ функции f 1 =

x1 x2 x3 x4
0 0 0 0	0
0 0 0 1	1
0 0 1 0	1
0 0 1 1	1
0 1 0 0	1
0 1 0 1	0
0 1 1 0	0
0 1 1 1	1
1 0 0 0	0
1 0 0 1	1
1 0 1 0	1
1 0 1 1	1
1 1 0 0	0
1 1 0 1	1
1 1 1 0	0
1 1 1 1	1

Совершенная ДНФ исследуемой функции имеет вид:

0001 	00-1 	-0-1
0010 	-001 	-01-
0100	001- 	--11
0011 	-010 	1-1
1010 	0-11 
1001 	-011 
0111 	101- 
1011 	10-1 
1101 	1-01 
1111 	-111 
	1-11 
	11-1 

В первом столбике присутствует набор, который не участвовал ни в одной склейке – он сам является максимальным интервалом 0100. В третьем столбике к нему добавляется еще четыре максимальных интервала: {-0-1, -01-, --11, 1--1}.

Строим таблицу Квайна:

	0001	0010	0100	0011	1010	1001	0111	1011	1101	1111
0100			1
-0-1	1					1		1	1
-01-		1		1	1			1
--11				1			1	1		1
1--1						1		1	1	1

Определим ядро покрытия, в которое войдут обязательные интервалы:

{0100, -0-1, -01-, --11}. В данном случае, ядро покрытия покрывает и всю таблицу в целом.

Минимальная дизъюнктивная нормальная форма f1 имеет вид:

2. Найти МДНФ функции f 2( x 1, x 2, x 3), которая принимает единичные значения на наборах 0,2,3,6 и 7.

Построим таблицу истинности для f 2

x1 x2 x3	F2
0 0 0	1
0 0 1	0
0 1 0	1
0 1 1	1
1 0 0	0
1 0 1	0
1 1 0	1
1 1 1	1

СДНФ =
Упорядочим двоичные наборы по ярусам и проведем склейку:

000 	0-0 	--0
010 	-00 
100 	-10 
110 	1-0 
111 	11-

В результате склейки у нас получилось всего два максимальных интервала: {11-, --0}. Без построения таблицы Квайна очевидно, что они образуют минимальное покрытие, т.к. удаление любого из этих интервалов приведет к потери наборов, на которых функция f2(x1, x2, x3) истинна. МДНФ = x1 x2 +x3.

ЛИТЕРАТУРА

Гусева А.И. Учимся информатике: задачи и методы их решения.- М.: ДИАЛОГ-МИФИ, 2003.
Горбатов В.А. Фундаментальные основы дискретной математики. - М.: Наука. Физматлит, 1999.-544с

Всего имеется пять законов алгебры логики:

1. Закон одинарных элементов

1 * X = X
0 * X = 0
1 + X = 1
0 + X = X

Этот закон алгебры логики непосредственно следует из приведённых выше выражений аксиом алгебры логики.

Верхние два выражения могут быть полезны при построении коммутаторов, ведь подавая на один из входов элемента “2И” логический ноль или единицу можно либо пропускать сигнал на выход, либо формировать на выходе нулевой потенциал.

Второй вариант использования этих выражений заключается в возможности избирательного обнуления определённых разрядов многоразрядного числа. При поразрядном применении операции "И" можно либо оставлять прежнее значение разряда, либо обнулять его, подавая на соответствующие разряды единичный или нулевой потенциал. Например, требуется обнулить 6, 3 и 1 разряды. Тогда:

В приведённом примере использования законов алгебры логики отчётливо видно, что для обнуления необходимых разрядов в маске (нижнее число) на месте соответствующих разрядов записаны нули, в остальных разрядах записаны единицы. В исходном числе (верхнее число) на месте 6 и 1 разрядов находятся единицы. После выполнения операции "И" на этих местах появляются нули. На месте третьего разряда в исходном числе находится ноль. В результирующем числе на этом месте тоже присутствует ноль. Остальные разряды, как и требовалось по условию задачи, не изменены.

Точно так же при помощи закона одинарных элементов, одного из основных законов алгебры логики, можно записывать единицы в нужные нам разряды. В этом случае необходимо воспользоваться нижними двумя выражениями закона одинарных элементов. При поразрядном применении операции "ИЛИ" можно либо оставлять прежнее значение разряда, либо обнулять его, подавая на соответствующие разряды нулевой или единичный потенциал. Пусть требуется записать единицы в 7 и 6 биты числа. Тогда:

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

Первое и последнее выражения закона одинарных элементов позволяют использовать с большим количеством входов в качестве логических элементов с меньшим количеством входов. Для этого неиспользуемые входы в схеме "И" должны быть подключены к источнику питания, как это показано на рисунке 1:

Рисунок 1. Схема "2И-НЕ", реализованная на логическом элементе "3И-НЕ"

В то же самое время неиспользуемые входы в схеме "ИЛИ" в соответствии с законом одинарных элементов должны быть подключены к общему проводу схемы, как это показано на рисунке 2.

Рисунок 2. Схема "НЕ", реализованная на элементе "2И-НЕ"

Следующими законами алгебры логики, вытекающими из аксиом алгебры логики являются законы отрицания.

2. Законы отрицания

a. Закон дополнительных элементов

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

Еще одним широко используемым законом алгебры логики является закон двойного отрицания.

b. Двойное отрицание

Закон двойного отрицания используется как для упрощения логических выражений (и как следствие упрощения и удешевления цифровых комбинаторных схем), так и для устранения инверсии сигналов после таких логических элементов как "2И-НЕ" и "2ИЛИ-НЕ". В этом случае законы алгебры логики позволяют реализовывать заданные цифровые схемы при помощи ограниченного набора логических элементов.

c. Закон отрицательной логики

Закон отрицательной логики справедлив для любого числа переменных. Этот закон алгебры логики позволяет реализовывать при помощи логических элементов "ИЛИ" и наоборот: реализовывать логическую функцию "ИЛИ" при помощи логических элементов "И". Это особенно полезно в ТТЛ схемотехнике, так как там легко реализовать логические элементы "И", но при этом достаточно сложно логические элементы "ИЛИ". Благодаря закону отрицательной логики можно реализовывать элементы "ИЛИ" на логических элементах "И". На рисунке 3 показана реализация логического элемента "2ИЛИ" на элементе " " и двух инверторах.

Рисунок 3. Логический элемент "2ИЛИ", реализованный на элементе "2И-НЕ" и двух инверторах

То же самое можно сказать и о схеме монтажного "ИЛИ". В случае необходимости его можно превратить в монтажное "И", применив инверторы на входе и выходе этой схемы.

3. Комбинационные законы

Комбинационные законы алгебры логики во многом соответствуют комбинационным законам обычной алгебры, но есть и отличия.

a. закон тавтологии (многократное повторение)

X + X + X + X = X
X * X * X * X = X

Этот закон алгебры логики позволяет использовать логические элементы с большим количеством входов в качестве логических элементов с меньшим количеством входов. Например, можно реализовать двухвходовую схему "2И" на логическом элементе "3И", как это показано на рисунке 4:

Рисунок 4. Схема "2И-НЕ", реализованная на логическом элементе "3И-НЕ"

или использовать схему "2И-НЕ" в качестве обычного инвертора, как это показано на рисунке 5:

Рисунок 5. Схема "НЕ", реализованная на логическом элементе "2И-НЕ"

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

Для уменьшения числа входов в логическом элементе лучше воспользоваться другим законом алгебры логики — законом одинарных элементов, как это было показано выше.

Продолжим рассмотрение законов алгебры логики:

b. закон переместительности

A + B + C + D = A + C + B + D

c. закон сочетательности

A + B + C + D = A + (B + C) + D = A + B + (C + D)

d. закон распределительности

X1(X2 + X3) = X1X2 + X1X3 X1 + X2X3 = (X1 + X2)(X1 + X3) = /докажем это путём раскрытия скобок/ =
= X1X1 + X1X3 + X1X2 + X2X3 = X1(1 + X3 + X2) + X2X3 = X1 + X2X3

4. Правило поглощения (одна переменная поглощает другие)

X1 + X1X2X3 =X1(1 + X2X3) = X1

5. Правило склеивания (выполняется только по одной переменной)

Также как в обычной математике в алгебре логики имеется старшинство операций. При этом первым выполняется:

Действие в скобках
Операция с одним операндом (одноместная операция) — "НЕ"
Конъюнкция — "И"
Дизъюнкция — "ИЛИ"
Сумма по модулю два.

Операции одного ранга выполняются слева направо в порядке написания логического выражения. Алгебра логики линейна и для неё справедлив принцип суперпозиции.

Литература:

Вместе со статьей "Законы алгебры логики" читают:

Любая логическая схема без памяти полностью описывается таблицей истинности... Для реализации таблицы истинности достаточно рассмотреть только те строки...
http://сайт/digital/SintSxem.php

Декодеры (дешифраторы) позволяют преобразовывать одни виды бинарных кодов в другие. Например...
http://сайт/digital/DC.php

Достаточно часто перед разработчиками цифровой аппаратуры встаёт обратная задача. Требуется преобразовать восьмиричный или десятичный линейный код в...
http://сайт/digital/Coder.php

Мультиплексорами называются устройства, которые позволяют подключать несколько входов к одному выходу...
http://сайт/digital/MS.php

Демультиплексорами называются устройства... Существенным отличием от мультиплексора является...
http://сайт/digital/DMS.php

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

Законы алгебры логики называют иногда теоремами .

В алгебре высказываний логические законы выражаются в виде равенства эквивалентных формул.

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

Справедливость части законов можно доказать, применяя инструментарий таблиц истинности.

Рисунок 1.

Примеры

Рисунок 3.

Упростим исходное выражение, используя основные законы алгебры логики:

Рисунок 4.

(закон Де Моргана, распределительный закон для И, закон идемпотенции, операция переменной с её инверсией).

Из таблицы видно, что при всех наборах значений переменных $x$ и $y$ формула на рис.2 принимает значение $1$, то есть является тождественно истинной.

Рисунок 6.

Из таблицы видно, что Исходное выражение принимает такие же значения, что и Упрощенное выражение на соответствующих значениях переменных $x$ и $y$.

Упростим выражение на рис.5, применяя основные законы алгебры логики.

Рисунок 7.

(закон Де Моргана, закон поглощения, распределительный закон для И).

Рисунок 9.

Из таблицы видно, что при всех наборах значений переменных $x$ и $y$ формула на рис.8 принимает значение $0$, то есть является тождественно ложной.

Упростим выражение, применяя законы алгебры логики:

Рисунок 10.

Рисунок 12.

(закон Де Могргана, распределительный).

Составим таблицу истинности для выражения на рис.11:

Рисунок 13.

Из таблицы видно, что выражение на рис.11 в некоторых случаях принимает значение $1$, а в некоторых - $0$, то есть является выполнимым.

(правило де Моргана, выносим за скобки общий множитель, правило операций переменной с её инверсией).

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

(вводим вспомогательный логический сомножитель

Законы алгебры высказываний

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

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

Законы алгебры высказываний (алгебры логики) - это тавтологии.

Иногда эти законы называются теоремами.

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

Первые четыре из приведенных ниже законов являются основными законами алгебры высказываний.

Закон тождества:

А=А

Всякое понятие и суждение тождественно самому себе.

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

Например, рассуждение Правильно говорят, что язык до Киева доведет, а я купил вчера копченый язык, значит, теперь смело могу идти в Киев неверно, так как первое и второе слова «язык» обозначают разные понятия.

В рассуждении: Движение вечно. Хождение в школу - движение. Следовательно, хождение в школу вечно слово «движение» используется в двух разных смыслах (первое - в философском смысле - как атрибут материи, второе - в обыденном смысле - как действие по перемещению в пространстве), что приводит к ложному выводу.

Закон непротиворечия :

В один и тот же момент времени высказывание может быть либо истинным, либо ложным, третьего не дано. Истинно либо А, либо не А. Примеры выполнения закона исключенного третьего:

1. Число 12345 либо четное, либо нечетное, третьего не дано.

2. Предприятие работает убыточно или безубыточно.

3. Эта жидкость является или не является кислотой.

Закон исключенного третьего не является законом, признаваемым всеми логиками в качестве универсального закона логики. Этот закон применяется там, где познание имеет дело с жесткой ситуацией: «либо - либо », «истина-ложь ». Там же, где встречается неопределенность (например, в рассуждениях о будущем), закон исключенного третьего часто не может быть применен.

Рассмотрим следующее высказывание: Это предложение ложно. Оно не может быть истинным, потому что в нем утверждается, что оно ложно. Но оно не может быть и ложным, потому что тогда оно было бы истинным. Это высказывание не истинно и не ложно, а потому нарушается закон исключенного третьего.

Парадокс (греч. paradoxos - неожиданный, странный) в этом примере возникает из-за того, что предложение ссылается само на себя. Другим известным парадоксом является задача о парикмахере: В одном городе парикмахер стрижет волосы всем жителям, кроме тех, кто стрижет себя сам. Кто стрижет волосы парикмахеру? В логике из-за ее формальности нет возможности получить форму такого ссылающегося самого на себя высказывания. Это еще раз подтверждает мысль о том, что с помощью алгебры логики нельзя выразить все возможные мысли и доводы. Покажем, как на основании определения эквивалентности высказываний могут быть получены остальные законы алгебры высказываний.

Например, определим, чему эквивалентно (равносильно) А (двойное отрицание А , т. е. отрицание отрицания А ).Для этого построим таблицу истинности:

По определению равносильности мы должны найти тот столбец, значения которого совпадают со значениями столбца А. Таким будет столбец А.

Таким образом, мы можем сформулировать закон двойного отрицания:

Если отрицать дважды некоторое высказывание, то в результате получается исходное высказывание. Например, высказывание А = Матроскин - кот эквивалентно высказыванию А = Неверно, что Матроскин не кот .

Аналогичным образом можно вывести и проверить следующие законы:

Свойства констант:

Законы идемпотентности:

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

Законы коммутативности:

A v B = B v A

А & В = В & А

Операнды А и В в операциях дизъюнкции и конъюнкции можно менять местами.

Законы ассоциативности:

A v(B v C) = (A v B) v C;

А & (В & C) = (A & В) & С.

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

Законы дистрибутивности:

A v (B & C) = (A v B) &(A v C)

(дистрибутивность дизъюнкции
относительно конъюнкции)

А & (B v C) = (A & B) v (А & C)

(дистрибутивность конъюнкции
относительно дизъюнкции)

Закон дистрибутивности конъюнкции относительно дизъюнкции аналогичен дистрибутивному закону в алгебре, а закон дистрибутивности дизъюнкции относительно конъюнкции аналога не имеет, он справедлив только в логике. Поэтому необходимо его доказать. Доказательство удобнее всего провести с помощью таблицы истинности:

Законы поглощения:

A v (A & B) = A

A & (A v B) = A

Проведите доказательство законов поглощения самостоятельно.

Законы де Моргана:

Словесные формулировки законов де Моргана:

Мнемоническое правило: в левой части тождества операция отрицания стоит над всем высказыванием. В правой части она как бы разрывается и отрицание стоит над каждым из простых высказываний, но одновременно меняется операция: дизъюнкция на конъюнкцию и наоборот.

Примеры выполнения закона де Моргана:

1) Высказывание Неверно, что я знаю арабский или китайский язык тождественно высказыванию Я не знаю арабского языка и не знаю китайского языка.

2) Высказывание Неверно, что я выучил урок и получил по нему двойку тождественно высказыванию Или я не выучил урок, или я не получил по нему двойку.

Замена операций импликации и эквивалентности

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

Так, заменить операцию импликации можно в соответствии со следующим правилом: