Категории: ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника |
Основные законы булевой алгебрыК основным законам (тождествам, правилам) булевой алгебры относятся: 1. Коммутативные (переместительные) законы: 2. Ассоциативные (сочетательные) законы: 3. Дистрибутивные (распределительные) законы: 4. Закон двойного отрицания: 5. Законы тавтологии (идемпотентности): 6. Законы нулевого элемента: 7. Законы единичного элемента: 8. Законы дополнительного элемента. В булевой алгебре дополнительным элементом по отношению к а является отрицание 9. Законы двойственности (де Моргана): Следствия: 10. Законы поглощения: 11. Правила сокращения: Следствия: 12. Правила склеивания: Комментарии к законам булевой алгебры 1. Для доказательства законов можно использовать: а) метод совершенной индукции, б) одни законы для доказательства других законов. Метод совершенной индукции состоит в доказательстве эквивалентности левой и правой частей на всем множестве наборов аргументов. Для этого составляются таблицы истинности левой и правой частей с последующим их сравнением. 2. Большинство законов задается парой соотношений (дуальность законов булевой алгебры). При этом одно соотношение можно получить из другого, заменив операции конъюнкции на дизъюнкцию или дизъюнкцию на конъюнкцию. В законах, в которых участвуют логические константы (0 и 1), они заменяются на противоположные значения. 3. Некоторые законы можно распространять на произвольное число элементов. 4. В любом законе любую букву можно заменить на произвольное логическое выражение. 5. Законы применяются для упрощения булевых функций.
Разнообразие булевых функций Булевы функции от одной переменной приведены в табл.2.1.
Таблица 2.1. Булевы функции от одной переменной Булева функция от n аргументов f n(Х) называется вырожденной по аргументу xi, если ее значение не зависит от этого аргумента, то есть для всех наборов аргументов имеет место равенство: f(x1, x2, ... , xi-1, 0, xi+1, ... , xn) = f(x1, x2, xi-1, 1, xi+1, ... , xn). Невырожденные функции от двух переменных с добавлением функции отрицания принято называть базовыми функциями булевой алгебры. С учетом обращаемости некоторых базовых функций по отношению к своим аргументам, их общее количество равно девяти. Среди функций от одной переменной содержатся две вырожденные: логический ноль и логическая единица. Булевы функций от двух переменных приведены в табл.2.2. Среди функций от двух переменных шесть вырожденных функций, к которым относятся: · логический ноль; · логическая единица; · функция повторения аргументов x1 и x2; · отрицание аргументов x1 и x2.
Некоторые функции от трех переменных представлены в табл. 2.3.
Замечание. Функции сумма по модулю 2 и исключающее ИЛИ для трех аргументов являются неэквивалентными.
Утверждение. Общее число разнообразных булевых функций, в том числе и вырожденных, от n аргументов равно .
Таблица 2.2. Булевы функции от двух переменных
Таблица 2.3. Некоторые функции от трех переменных |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-06-09 lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда... |