Лекция "Основные законы алгебры логики"

тема 1 вопрос 13 Основные законы алгебры логики Основные законы и аксиомы АЛ позволяют проводить эквивалентные преобразования функций,  записанных с помощью элементарных логических функций (полный логический базис)  AND, OR, NO, приводить их к удобному для дальнейшего использования виду и упрощать запись.  Для доказательства нижеприведенных свойств и аксиом алгебры логики можно использовать  таблицы истинности элементарных логических действий или другие способы. 1. Свойства констант. a ∙ 0 = 0 a + 0 = а a ∙ 1 = а a + 1 = 1 Доказательство из таблиц истинности элементарных функций:  0 and 0 = 0; 0 and 0 = 0; 0 or 0 = 0; 1 or 0 = 1 0 and 1 = 0; 1 and 1 = 1; 0 or 1 = 1; 1 or 1 = 1 2. Инволютивность отрицаний. a'' = а 3. Комплементарность. a ∙ a' = 0; a + a' = 1 Доказательство: 0 and 1 = 0; 1 and 0 = 0; 0 or 1 = 1; 1 or 0 = 1 4. Идемпотентный закон. a ∙ a = а а + а = а Доказательство: 0 and 0 = 0; 1 and 1 = 1 0 or 0 = 0; 1 or 1 = 1 5. Переместительный закон (коммутативность). а + в = в + а а ∙ в = в ∙ а От перемены мест слагаемых или множителей результат не меняется. 6. Сочетательный закон (ассоциативность). (а + в) + с = а + (в + с); (а ∙ в) ∙с = а∙ (в ∙ с) Если над аргументами функции выполняются однотипные логические действия, то их можно  произвольно группировать, изменяя последовательность действий. 7. Закон Блейка ­ Порецкого. а + (a` ∙ в) = а + в а∙ (a` + в) = а ∙ в 8. Закон поглощения. а + а∙в = а∙ (1 + в) = а а∙ (a + в) = а + ав = а Вынесем общий множитель a. Зная, что 1 + в = 1, получим: а ∙ 1 = а 9. Распределительный закон (дистрибутивность). а(в + с) = ав + ас; а + вс = (а + в)(а + с)       10. Закон склеивания.        ав + ав' = а;                                                 (а + в)(а + в') = а Если один из аргументов изменяется при неизменном результате (функции),  то этот аргумент можно исключить из выражения. Это один из самых важных законов,  часто используемых для минимизации логических функций.     11. Правило де Mоргана.  Это правило преобразования одного логического действия в другое (AND в OR и, наоборот, OR в  AND).  Для этого необходимо изменить логическое действие и инвертировать все аргументы и все выражение  в целом. а + в + с + .... + z = ( а'в'с'...z' )' авс... = ( а' + в' + с' + ... + z' )' 4.2. Основные законы алгебры логики и правила преобразования логических выражений В алгебре логики имеются законы, которые записываются в виде соотношений. Логические законы  позволяют производить равносильные (эквивалентные) преобразования логических выражений.Преобразования называются равносильными, если истинные значения исходной и полученной после  преобразования логической функции совпадают при любых значениях входящих в них логических  переменных. Для простоты записи приведем основные законы алгебры логики для двух логических переменных А и  В. Эти законы распространяются и на другие логические переменные. 1. Закон противоречия: 2. Закон исключенного третьего: 3. Закон двойного отрицания: 4. Законы де Моргана: 5. Законы повторения: A & A = A; A v A = A; В & В = В; В v В = В. 6. Законы поглощения: A ? (A & B) = A; A & (A ? B) = A. 7. Законы исключения констант: A ? 1 = 1; A ? 0 = A; A & 1 = A; A & 0 = 0; B ? 1 = 1; B ? 0 = B; B & 1 = B; B & 0 = 0. 8. Законы склеивания: 9. Закон контрапозиции: (A ? B) = (B ? A). Для логических переменных справедливы и общематематические законы. Для простоты записи  приведем общематематические законы для трех логических переменных A, В и С: 1. Коммутативный закон: A & B = B & A; A ? B = B ? A. 2. Ассоциативный закон: A & (B & C) = (A & B) & C; A ? (B ? C) = (A ? B) ? C. 3. Дистрибутивный закон: A & (B ? C) = (A & B) ? (A & C). Как уже отмечалось, с помощью законов алгебры логики можно производить равносильные  преобразования логических выражений с целью их упрощения. В алгебре логики на основе принятого  соглашения установлены следующие правила (приоритеты) для выполнения логических операций:  первыми выполняются операции в скобках, затем в следующем порядке: инверсия (отрицание),  конъюнкция ( & ), дизъюнкция (v), импликация (?), эквиваленция (?) Выполним преобразование, например, логической функции применив соответствующие законы алгебры логики.