Ассоциативный закон алгебры логики

Урок " Логические законы "

Логические законы и правила преобразования

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

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

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

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

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

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

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

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

Закон исключенного третьего

Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означает, что результат логического сложения высказывания и его отрицания всегда принимает значение «истина».

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

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

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

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

(переместительный)

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

(сочетательный)

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

(А & B ) & С = А & (В & С)

(А / В) / С= А / (В / С)

(распределительный )

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

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

Ø A & (A / B) = Ø A & B

A / Ø A & B = A / B

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

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

(А & В) v (А & ¬ В) = А & (В v ¬ В).

По закону исключенного третьего В v В =1, следовательно:

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

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

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

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

Объем понятия — множество предметов, каждому из которых принадлежат признаки, составляющие содержание понятия. Выделяют понятия общие и единичные.

Выделяют следующие отношения понятий по объему:

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

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

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

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

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

Высказывание — это любое предложение какого-либо языка (утверждение), содержание которого можно определить как истинное или ложное.

Всякое высказывание или истинно, или ложно; быть одновременно и тем и другим оно не может.

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

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

Высказывание называется простым (элементарным), если никакая его часть сама не является высказыванием.

Высказывание, состоящее из простых высказываний, называются составным (сложным).

Простые высказывания в алгебре логики обозначаются заглавными латинскими буквами:
А = <Аристотель — основоположник логики>,
В = <На яблонях растут бананы>.

Обоснование истинности или ложности простых высказываний решается вне алгебры логики. Например, истинность или ложность высказывания: "Сумма углов треугольника равна 180 градусов" устанавливается геометрией, причем — в геометрии Евклида это высказывание является истинным, а в геометрии Лобачевского — ложным.

Истинному высказыванию ставится в соответствие 1, ложному — 0. Таким образом, А = 1, В = 0.

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

Основные операции алгебры высказываний.

Логическая операция КОНЪЮНКЦИЯ (лат. conjunctio — связываю):

в естественном языке соответствует союзу и;
обозначение: &;
в языках программирования обозначение: and;
иное название: логическое умножение.

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

Таблица истинности конъюнкции:

А	В	А&В
0	0	0
0	1	0
1	0	0
1	1	1

Логическая операция ДИЗЪЮНКЦИЯ (лат. disjunctio — различаю):

в естественном языке соответствует союзу или;
обозначение: ;
в языках программирования обозначение: or;
иное название: логическое сложение.

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

Таблица истинности дизъюнкции:

А	В	АВ
0	0	0
0	1	1
1	0	1
1	1	1

Логическая операция ИНВЕРСИЯ (лат. inversio — переворачиваю):

в естественном языке соответствует словам "Неверно, что. " и частице не;
обозначение: не А, ;
в языках программирования обозначение: not;
иное название: отрицание.

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

Таблица истинности отрицания:

А	не А
0	1
1	0

Функция логического сложения ИЛИ (ЛогЗнач1;ЛогЗнач2;…) дает значение TRUE (Истина), только тогда, когда хотя бы один логический аргумент имеют значение TRUE (1).

Функция логического отрицания НЕ(ЛогЗнач) дает значение TRUE (Истина), когда логический аргумент имеют значение FALSE (0) и, наоборот, значение FALSE (Ложь), когда логический аргумент имеют значение TRUE (1).

Логическая операция ИМПЛИКАЦИЯ (лат. implicatio — тесно связываю):

в естественном языке соответствует обороту Если . то . ;
обозначение: ;
иное название: логическое следование.

Импликация — это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие (первое высказывание) истинно, а следствие (второе высказывание) ложно.

Таблица истинности импликации:

А	В	АВ
0	0	1
0	1	1
1	0	0
1	1	1

Логическая операция ЭКВИВАЛЕНЦИЯ (лат. аequivalens — равноценное):

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

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

Таблица истинности эквиваленции:

0 0 1 0 1 0 1 0 0 1 1 1

Логические операции имеют следующий приоритет: действия в скобках, инверсия , &, , ,

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

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

Алгоритм построения таблицы истинности:

подсчитать количество переменных n в логическом выражении;
определить число строк в таблице m = 2 n ;
подсчитать количество логических операций в формуле;
установить последовательность выполнения логических операций с учетом скобок и приоритетов;
определить количество столбцов в таблице: число переменных плюс число операций;
выписать наборы входных переменных с учетом того, что они представляют собой натуральный ряд n-разрядных двоичных чисел от 0 до 2 n -1;
провести заполнение таблицы истинности по столбикам, выполняя логические операции в соответствии с установленной в п.4 последовательностью.

Наборы входных переменных, во избежание ошибок, рекомендуют перечислять следующим образом:
а) определить количество наборов входных переменных;
б) разделить колонку значений первой переменной пополам и заполнить верхнюю часть колонки 0, а нижнюю
в) разделить колонку значений второй переменной на четыре части и заполнить каждую четверть чередующимися группами 0 или 1, начиная с группы 0;
г) продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами 0 или 1 до тех пор, пока группы 0 и 1 не будут состоять из одного символа.

Пример. Для формулы A&(B C ) построить таблицу истинности алгебраически и с использованием электронных таблиц.

Количество логических переменных 3, следовательно, количество строк в таблице истинности должно быть 2 3 = 8.

Количество логических операций в формуле 5, следовательно, количество столбцов в таблице истинности должно быть 3 + 5 = 8.

А	В	C	ВC	А & (ВC)
0	0	0	1	0
0	0	1	0	0
0	1	0	1	0
0	1	1	1	0
1	0	0	1	1
1	0	1	0	0
1	1	0	1	1
1	1	1	1	1

Логической (булевой) функцией называют функцию F(Х₁, Х₂, . Х_n), аргументы которой Х₁, Х₂, . Х_n (независимые переменные) и сама функция (зависимая переменная) принимают значения 0 или 1.

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

Логические функции могут быть заданы табличным способом или аналитически — в виде соответствующих формул.

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

Существует 16 различных логических функций от двух переменных.

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

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

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

Переместительный (коммутативный) закон:
— для логического сложения:
А B = B A;

— для логического умножения:
A & B = B & A.

Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.

Сочетательный (ассоциативный) закон:
— для логического сложения:
(A B) C = A (B C);

— для логического умножения:
(A & B) & C = A & (B & C).

При одинаковых знаках скобки можно ставить произвольно или вообще опускать.

Распределительный (дистрибутивный) закон:
— для логического сложения:
(A B) & C = (A & C) (B & C);

— для логического умножения:
(A & B) C = (A C) & (B C).

Определяет правило выноса общего высказывания за скобку.

Закон общей инверсии (законы де Моргана):
— для логического сложения:
;

— для логического умножения:
.

Закон идемпотентности ( от латинских слов idem — тот же самый и potens -сильный; дословно — равносильный):
— для логического сложения:
A A = A;

— для логического умножения:
A & A = A.

Закон означает отсутствие показателей степени.

Законы исключения констант:
— для логического сложения:
A 1 = 1, A 0 = A;

— для логического умножения:
A & 1 = A, A & 0 = 0.

Закон противоречия:
A & (не A)= 0.

Невозможно, чтобы противоречащие высказывания были одновременно истинными.

Закон исключения третьего:
A (не A) = 1.

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

Закон поглощения:
— для логического сложения:
A (A & B) = A;

— для логического умножения:
A & (A B) = A.

Закон исключения (склеивания):
— для логического сложения:
(A & B) ( & B) = B;

— для логического умножения:
(A B) & ( B) = B.

Закон контрапозиции (правило перевертывания):
(AB) = (BA).

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

Пример. Упростить логическое выражение:

Ефимова О., Морозов В., Угринович Н. Курс компьютерной технологии с основами информатики. Учебное пособие для старших классов. — М.: ООО "Издательство АСТ"; АВF, 2000 г.
Задачник-практикум по информатике. В 2-х томах/Под ред. И.Семакина, Е.Хеннера. — М.: Лаборатория Базовых Знаний, 2001 г.
Угринович Н. Информатика и информационные технологии. 10-11 класс- М.: Лаборатория Базовых Знаний, АО "Московские учебники", 2001 г.

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

Двойное отрицание исключает отрицание.

Переместительный (коммутативный) закон:

— для логического сложения:

— для логического умножения:

Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.

Сочетательный (ассоциативный) закон:

— для логического сложения:

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

— для логического умножения:

(A & B) & C = A & (B & C).

При одинаковых знаках скобки можно ставить произвольно или вообще опускать.

Распределительный (дистрибутивный) закон:

— для логического сложения:

(A ;

— для логического умножения:

Закон идемпотентности ( от латинских слов idem — тот же самый и potens -сильный; дословно — равносильный):

— для логического сложения:

— для логического умножения:

Закон означает отсутствие показателей степени.

Законы исключения констант:

— для логического сложения:

A v 1 = 1, A v 0 = A;

— для логического умножения:

A & 1 = A, A & 0 = 0.

Невозможно, чтобы противоречащие высказывания были одновременно истинными.

Закон исключения третьего:

— для логического сложения:

— для логического умножения:

Закон исключения (склеивания):

— для логического сложения:

— для логического умножения:

Закон контрапозиции (правило перевертывания):

(AB) = (BA).

Пример. Упростить логическое выражение:

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

Контрольные вопросы

1. Предмет изучения математической логики.

2. Понятия высказывания, его значений.

3. Содержание операций над высказываниями. Таблицы истинности.

4. Понятие логического выражения (составного высказывания). Примеры.

5. Основные законы математической логики. Примеры.

«>