41)Алгебра логики. Упрощение логических выражений.

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

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

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

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

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

2) : к отрицаниям формул применяется правило де Моргана; используются законы двойного отрицания и склеивания.

42) Алгебра логики. Функциональные схемы.

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

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

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

Закон де Моргана (Если существует операция логического умножения двух и более элементов, операция «и»—(A&B), то для того, чтобы найти обратное от всего суждения~(A&B), необходимо найти обратное от каждого элемента и объединить их операцией логического сложения,операцией «или»— (~A+~B). Закон работает аналогично в обратном направлении:~(A+B)= (~A&~B)) . Докажем его с помощью диаграммы эйлера-венна.

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

Для визуального представления правой части равенства выполним последовательно: заштрихуем область для отображения инверсии (¬А) серым цветом и аналогично область ¬В также серым цветом; затем для отображения конъюнкции нужно взять пересечение этих серых областей (результат наложения представлен черным цветом):Видим, что области для отображения левой и правой части равны. Что и требовалось доказать.