Законы булевой алгебры

Законы булевой алгебры Законы булевой алгебры (алгебры логики) отражают связи, существующие между логическими операциями, которые выполняются над логическими переменными. Ниже приведены аксиомы и основные законы булевой алгебры. Аксиомы булевой алгебры: 1) 0 ⋅ 1 = 0 ; 2) 1 ⋅ 0 = 0 ; 3) 1 ⋅ 1 = 1 ; 4) 0 ⋅ 0 = 0 ; 5) 1 + 1 = 1 ; 6) 0 + 1 = 1 ; 7) 1 + 0 = 1 ; 8) 0 + 0 = 0 . Основные законы булевой алгебры: 1. Закон нулевого множества: x + 0 = x ; x ⋅ 0 = 0 . 2. Закон универсального множества: x + 1 = 1 ; x ⋅ 1 = x . 3. Закон повторения (тавтологии): x + x = x ; x ⋅ x = x . 4. Закон дополнительности: x + x = 1 ; x ⋅ x = 0 . 5. Закон двойной инверсии: x = x . 6. Коммутативный (переместительный) закон: x + y = y + x ; x ⋅ y = y ⋅ x . 7. Ассоциативный (сочетательный) закон: ( x + y ) + z = x + ( y + z ) ; ( x ⋅ y) ⋅ z = x ⋅ ( y ⋅ z ) . 8. Закон инверсии (правило де Моргана): x + y = x ⋅ y ; x ⋅ y = x + y . 9. Закон поглощения: x + x ⋅ y = x ; x ( x + y ) = x . 10. Распределительный закон: x + y ⋅ z = ( x + y )( x + z ) ; x ( y + z ) = x ⋅ y + x ⋅ z . 11. Закон свертки: x + x ⋅ y = ( x + y ) ; x ( x + y ) = x ⋅ y . 12. Закон склеивания: x ⋅ y + x ⋅ y = x ; ( x + y )( x + y ) = x . Задание для самостоятельной работы. Доказать справедливость перечисленных выше законов булевой алгебры подстановкой непосредственных значений для логических (булевых) переменных. Дизъюнктивная и конъюнктивная нормальные формы логических функций При представлении логической функции математическим выражением используют дизъюнктивную и конъюнктивную нормальные формы. Дизъюнктивной нормальной формой (ДНФ) называется логическая сумма элементарных логических произведений, в каждое из которых аргумент или его инверсия (отрицание) входят один раз. ДНФ может быть получена из таблицы истинности следующим образом: для каждого набора аргументов, на котором функция равна «логической 1» записывают элементарные произведения переменных, причём переменные, значения которых равно «логическому 0», записывают с инверсией. Полученные произведения, называемые минтермами, суммируют. Конъюнктивной нормальной формой (КНФ) называется логическое произведение элементарных логических сумм, в каждую из которых аргумент или его инверсия входят один раз. КНФ может быть получена из таблицы истинности следующим образом: для каждого набора аргументов, на котором функция равна «логическому 0» записывают элементарные суммы переменных, причём переменные, значения которых равно «логической 1», записывают с инверсией. Полученные суммы, называемые макстермами, объединяют операцией логического умножения. Пример. Задана логическая функция трёх переменных, которая равна «логической 1» в случае, если хотя бы две из входных переменных равны «логической 1». Таблица истинности для данной логической функции приведена ниже (таблица 12). Таблица 12 Таблица истинности логической функции трёх переменных X10 x2 x1 x0 y 1 2 3 4 5 6 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Дизъюнктивная нормальная форма для данной логической функции имеет следующий вид: y ( x 2 , x1 , x0 ) = x 2 ⋅ x1 ⋅ x0 + x 2 ⋅ x1 ⋅ x0 + x 2 ⋅ x1 ⋅ x0 + x2 ⋅ x1 ⋅ x0 . Эта ДНФ является совершенной дизъюнктивной нормальной формой (СДНФ), так как каждое элементарное произведение (минтерм, или конституэнта единицы), участвующее в суммировании, содержит все переменные. Конъюнктивная нормальная форма для данной логической функции имеет следующий вид: y ( x 2 , x1 , x 0 ) = ( x 2 + x1 + x0 )( x 2 + x1 + x0 )( x 2 + x1 + x 0 )( x 2 + x1 + x0 ) . Эта КНФ также является совершенной конъюнктивной нормальной формой (СКНФ), так как каждая элементарная сумма (макстерм, или конституэнта нуля) содержит все переменные.