Дискретная математика Булева алгебра
 Скачать 211.23 Kb.
|
|
Дискретная математика Булева алгебра Булева алгебра Булевы операции – это конъюнкция ( ), дизъюнкция ( ) и отрицание (¬). Булева алгебра – это множество логических функций с введенными на нем булевыми операциями. Формулы, представляющие одну и ту же функцию называются равносильными (эквивалентными). Закон коммутативности Закон ассоциативности Закон де Моргана Закон дистрибутивности Закон исключенного третьего Закон уничтожения кратности Закон противоречия Закон двойного отрицания Закон поглощения Свойства констант Основные эквивалентности Закон простого склеивания Закон расщепления Основные эквивалентности Первый закон обобщенного склеивания Второй закон обобщенного склеивания Основные эквивалентности Эквивалентность Основные эквивалентности Сложение по модулю 2 Основные эквивалентности Импликация Утверждение о единственности СДНФ логической функции СДНФ любой логической функции единственна с точностью до порядка элементарных конъюнкций и порядка элементов в конъюнкциях. Единственная логическая функция, не имеющая СДНФ, функция –константа 0. Пусть и равносильные формулы. Тогда существует последовательность эквивалентных преобразований, переводящих одну эквивалентную формулу в другую. Доказательство: Так как формулы и равносильны, то они представляю одну функцию . У каждой функции единственна СДНФ. Приведем и к СДНФ. Доказательство: Обратим второе преобразование. Получим последовательность преобразований, переводящих в Теорема о представимости логической функции булевой формулой Любая логическая функция представима булевой формулой. Доказательство: У каждой функции существует СДНФ – булева формула. Функция константа 0 может быть выражена булевой формулой вида: |