Основные понятия булевой алгебры

Дискретная математика Основные понятия булевой алгебры Преподаватель: Шилова З.В. 1 Тема: Основные понятия булевой алгебры Цель лекции – изучить основные положения теории булевых функций для использования точных методов анализа и синтеза при проектировании компьютерных систем Содержание: • Булевы переменные и функции • Двоичные наборы • Основные логические операции • Таблицы истинности • Законы булевой алгебры • ДНФ и КНФ • СДНФ и СКНФ • Аналогия с алгеброй множеств Кантора 2 Термины Базовые понятия: множество законы (ассоциативный, коммутативный, элиминации, др.), бинарные и унарные операции, алгебра, двоичная система счисления изоморфизм структура Ключевые слова:  булева переменная  булева функция  логические операции (дизъюнкция, конъюнкция, инверсия, импликация, сумма по модулю два, эквивалентность)  дизъюнктивная нормальная форма (ДНФ)  конъюнктивная нормальная форма (КНФ) 3 Историческая справка Родился в Линкольне 1849 – профессор математики Куинс-Колледжа в Корке (Ирландия) За работы в области высшего анализа получил Королевскую медаль 1854 – основное произведение «Исследование законов мышления» Предпринял попытку построить формальную логику в виде некоторого «исчисления», «алгебры» Джордж Буль (XIXв.) В современной алгебре встречаются булевы кольца, булевы алгебры — алгебраические системы, законы которых берут свое начало от исчисления Буля В общей топологии – булево пространство В математических проблемах управляющих систем − булевы разброс, разложение 4 Структура математической логики Математическая логика – раздел математики, посвященный изучению математических доказательств и вопросов оснований математики Исчисление высказываний и исчисление предикатов Математическая логика Исчисление высказываний Исчисление предикатов Исчисление высказываний – вступительный раздел математической логики, в котором рассматриваются логические операции над высказываниями 5 Булевы переменные и булевы функции      В алгебре логики интересуются лишь истинностным значением высказываний Обозначения: 1 (истина) 0 (ложь) Каждой логической операции соответствует функция, принимающая значения 0, 1, аргументы которой также принимают значения 0, 1 Def: логическая (булева) переменная x{0, 1} Def: логическая (булева) или функция алгебры логики (ФАЛ) f(x1, x2, …, xn){0, 1} 6 Двоичные наборы      Переменные булевой функции образуют наборы из нулей и единиц. Такие наборы называют двоичными Сколько двоичных наборов имеет функция f(x1, x2, …,xn) от n переменных? Булева функция от n переменных определена на 2n двоичных наборах Переход от десятичной к двоичной системе счисления: 6 2 –6 3 0 –2 1 2 1(6)10=(110)2 7 Двоичные наборы для функций от двух и трех переменных f(x1, x2) № набора 1 2 3 f(x1, x2, x3) x1 1 1 x2 1 1 № набора 1 2 3 4 5 6 7 x1 1 1 1 1 x2 1 1 1 1 x3 1 1 1 1 8 Логические операции Название Дизъюнкция (логическое сложение) Конъюнкция (логическое умножение) Инверсия (отрицание) Импликация Эквивалентность Сумма по модулю 2 (исключающее ИЛИ) Обозначение  (+) Чтение ИЛИ  (&, •) И – (¬)    НЕ ВЛЕЧЕТ эквивалентно сумма по модулю 2 9 Логические переменные А=«Солнце светит для всех» А истинно, А=1 В=«Все ученики любят информатику» В ложно, В=0 С=«Некоторые из учеников любят информатику» С истинно, С=1 Логические операции И, ИЛИ, НЕ Сложное высказывание получается объединением простых высказываний базовыми логическими операциями. А=«На улице холодно» В=«На улице идет дождь» С=«На улице холодно и идет дождь» С=А И В Логическая операция – способ построения сложного высказывания из данных высказываний, при котором значение истинности сложного высказывания полностью определяется значениями истинности исходных высказываний. Логическое отрицание инверсия «переворачиваю» Добавляется частица НЕ к сказуемому или используется оборот речи «Неверно, что...» А=«У меня есть приставка Денди» Инверсия А=«У меня нет приставки Денди» НЕ А, ¬А, NOT A А ¬А 1 1 Инверсия высказывания истина, когда высказывание ложно, и ложна тогда, когда высказывание истинно. Логическое умножение конъюнкция «связываю» Соединение двух высказываний с помощью союза И А=«На автостоянке стоит «Мерседес» В=«На автостоянке стоят «Жигули» А конъюнкция В=«На автостоянке стоят «Мерседес» и «Жигули» А И В, А٨В, А&В, А·В, А AND В А В А٨В Конъюнкция двух высказываний истина тогда, когда оба высказывания истины, и ложна 1 тогда, когда хотя бы одно 1 высказывание ложно. 1 1 1 Логическое сложение дизъюнкция «различаю» Соединение двух высказываний с помощью союза ИЛИ А=«На автостоянке стоит «Мерседес» В=«На автостоянке стоят «Жигули» А дизъюнкция В= «На автостоянке стоят «Мерседес» или «Жигули» А ИЛИ В, А۷В, А/В, А+ В, А OR В А В А۷В Дизъюнкция двух высказываний ложна тогда, когда оба высказывания ложны, и истина 1 1 тогда, когда хотя бы одно 1 1 высказывание истинно. 1 1 1 Логическое следование импликация «тесно связываю» Соединение двух высказываний с помощью союза оборота речи «Если …, то …» А=«На улице дождь» В=«Асфальт мокрый» А импликация В= «Если на улице дождь, то асфальт мокрый» А → В, А=>В А В А→В Импликация двух высказываний 1 ложна тогда, когда из истинного 1 1 1 1 1 1 высказывания следует ложное. Логическое равенство эквивалентность «равноценное» Соединение двух высказываний с помощью союза оборота речи «…тогда и только тогда, когда …» А=«Число делится на 3 без остатка» В=«Сумма цифр числа делится на 3» А эквивалентно В=«Число кратно 3 тогда и только тогда, когда сумма его цифр делится на 3» А ≡ В, АВ А В А≡В Эквивалентность двух 1 высказываний истина тогда, когда 1 оба высказывания истинны или ложны. 1 1 1 1 Определение логических операций. Таблицы истинности Логические операции – логические функции Таблицы истинности № набора x y 1 1 2 1 3 1 1 х xy xy 1 1 1 1 1 1 1 1 1 1 1 1 1 xy xy xy 17 Пример № набора 1 2 3 4 5 6 7 x 1 1 1 1 y 1 1 1 1 z xy z 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 1 1 0 h(x,y,z)= (xy) z 1 1 1 1 18 Законы и тождества алгебры логики Название Коммутативность Ассоциативность Дистрибутивность Идемпотентность Действия с константами Инволюция Формула xy=yx, xy=yx (xy)z= x(yz), (xy)z= x(yz) (xy)z=xzyz, xyz=(xz)(yz) xx=x, xx=x x0=x, x0=0, x1=1, x1=x, xx=1, xx=0 x=x 19 Законы и тождества алгебры логики Название Формула Закон де Моргана Элиминация Склеивание Законы Блэйка-Порецкого xy=x y, xy=xy (xy)x=x, xyx=x (xy)(xy)=x, xyxy=x х(хy)=xy, xxy=xy  Связь эквивалентности  с дизъюнкцией, конъюнкцией и отрицанием: xy = xy  x y  Связь импликации с отрицанием и дизъюнкцией: xy =x  y 20 Доказательство дистрибутивного закона при помощи таблиц истинности: xy  z = (x  z) (y  z) № набора 1 2 3 4 5 6 7 x y z xy xy  z xz yz (x  z)(y  z) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 LHS RHS  Таким образом, показано: LHS=RHS 21 ДНФ и КНФ Термин Обозначение Первичный терм x ii x i , i  1,  x i , i  0. x1, x1 (1 ,  2 , ...,  n ) Двоичный набор Элементарная конъюнкция (ЭК) ДНФ x11 Элементарная дизъюнкция (ЭД) x11 КНФ Пример & x 2 2 & ... & x n n n  & x ii i 1 n x1x2x3x1x2  ( & x ii ) i 1  x 2 2  ...  x n n n &( i 1 i xi ) (0,1,1,0,1) x1x2x3x4 n  i 1 x ii x1x2x3x4 (x1x2x3)(x1 x2) 22 Совершенные ДНФ и КНФ (СДНФ и СКНФ)   Def: Совершенной ДНФ (СДНФ) называется ДНФ, в которой нет равных элементарных конъюнкций и все элементарные конъюнкции содержат одни и те же переменные, причем каждую – только один раз (включая вхождения под знаком отрицания). Def: Совершенная КНФ (СКНФ) определяется как такая КНФ, в которой нет одинаковых сомножителей; все сомножители содержат одни и те же переменные, причем каждую переменную – только один раз. 23 Пример получения СДНФ и СКНФ x1 x2 x3 f(x1, x2, x3) x1 x2 x3 f(x1, x2, x3) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 f СДНФ (x1 , x 2 , x 3 )  x1x 2 x 3  x1x 2 x 3  x1x 2 x 3  x1x 2 x 3 f СКНФ ( x1 , x 2 , x 3 )  ( x1  x 2  x 3 )(x1  x 2  x 3 )(x1  x 2  x 3 )(x1  x 2  x 3 ) 24 Теорема Шеннона Любая булева функция f0 представима в виде разложения Шеннона: f ( x1 , x 2 ,..., x k , x k 1 , ..., x n )   k ( & x ii )  f (1 ,  2 ,...,  k , x k 1 , ..., x n ) ( 1 , 2 ,..., k ) i 1 Следствие Предельное разложение Шеннона (k=n) булевой функции f0 имеет вид k f ( x1 , x 2 ,..., x k , x k 1 , ..., x n )   ( & x ii ) ( 1 , 2 ,..., n ), i 1 f ( 1 , 2 ,..., n ) 1 25 Выводы Всякая ФАЛ может быть реализована формулой, оперирующей символами , , ¬, скобками и знаком равенства Любая булева функция может быть представлена в виде ДНФ, КНФ, СДНФ, СКНФ ДНФ КНФ СДНФ СКНФ ДНФ и КНФ есть сокращенная форма записи СДНФ и СКНФ (таблицы истинности) ДНФ есть наиболее распространенная форма описания цифровых систем, максимально приближенная к аппаратурной реализации 26 Тест-задание Заполнить таблицу истинности для пяти функций: № набора x y z xy (xy)z xz yz xzyz 1 2 3 4 5 6 7 27 Аналогия с алгеброй множеств Кантора Теория множеств Множество элементов М Операция пересечение  Булева алгебра Элемент X {0,1} Операция И (  – конъюнкция) Операция объединение  Операция ИЛИ (  – дизъюнкция) Операция дополнение – Пустое множество  Универсум – множество всех элементов U Операция инверсия – 0-элемент 1-элемент 28