Материалы сайта
Это интересно
Лабораторный практикум
ХХ Основы булевой алгебры Хх.1 Основные понятия и определения Булева алгебра (БА) – раздел математической логики. Основным понятием БА является высказывание (В). Под высказыванием понимают любое предложение, про которое можно однозначно сказать, истинно оно или ложно. Высказывания подразделяются на простые и сложные. Под простым В понимают одно единственное предложение, про которое можно сказать истинно оно или ложно. Например: «Дважды два – пять», «Курица – не птица», «Путин – президент РФ». Сложным В является предложение, состоящее из нескольких простых предложений (простых В), связанных между собой какими либо логическими связями. Под логическими связями понимаются грамматические союзы типа «НЕ», «И», «ИЛИ», «ЕСЛИ …, ТО …», и т.д. Под булевой функцией (БФ) понимают сложное высказывание. Это такая функция, которая принимает лишь два значения (0 или 1). БФ всегда конечна и обозначается f, F. Простые высказывания, входящие в БФ, называются переменными или аргументами и обозначаются x, y, z, … В БА нет линейных коэффициентов, нет деления, корня, логарифма и т.д. В БА, как правило, используется двоичная арифметика, да и то не в полном объеме. Есть два типа реализации БФ: положительная логика и отрицательная логика. В положительной логике 0 (ложь) соответствует низкому уровню сигнала, а 1 (истина) – высокому. Соответственно в отрицательной логике – наоборот. БФ одной переменной называется симвилярной функцией. Существуют четыре симвилярные функции. Они приведены в таблице ХХ.1. Таблица ХХ.1 Симвилярные БФ |N | |0|1|Обозначение |Название | | |[pic] | | | | | | |[pic] | | | | | |0 |[pic] |0|0|0 |Константа нуль | |1 |[pic] |0|1|[pic] |Повторение | |2 |[pic] |1|0|[pic] |Отрицание (инверсия) | |3 |[pic] |1|1|1 |Константа единица | Хх.2 БФ двух переменных БФ двух переменных называются бинарными. Существует шестнадцать бинарных функций. Они приведены в таблице хх.2. Таблица хх.2 БФ двух переменных |0 |0 |0 |1 | |0 |0 |1 |0 | |0 |1 |0 |0 | |0 |1 |1 |1 | |1 |0 |0 |0 | |1 |0 |1 |1 | |1 |1 |0 |1 | |1 |1 |1 |1 | Составим СДНФ для F: - выделяем наборы переменных, на которых функция равна 1; - записываем для этих наборов конъюнкции, при этом если переменная равна 1, то эта переменная записывается без отрицания, если же переменная равна 0, то такая переменная записывается с отрицанием; - объединяем элементарные конъюнкции знаками дизъюнкций; - полученное выражение будет являться совершенной ДНФ. [pic]. Алгоритм нахождения СКНФ: - выделяем те наборы переменных, на которых функция равна 0; - из этих наборов переменных составляем дизъюнкции, учитывая то, что если переменная равна 0, то она записывается без отрицания, а если 1 – с отрицанием; - объединяем элементарные дизъюнкции знаками конъюнкций; - полученное выражение является совершенной КНФ. [pic]. Рангом функции называется наибольшее число переменных, входящих в ДНФ. Длиной функции называется число элементарных конъюнкций (дизъюнкций) входящих в эту функцию. Универсальными БФ называются такие БФ, при помощи которых можно описать (представить) любое логическое выражение. Кратчайшей называется функция, имеющая наименьший ранг и наименьшую длину. Хх.4 Основные законы (аксиомы) БА Булеву алгебру можно применять, зная три основные операции: «И», «ИЛИ», «НЕ». Однако полезно знать некоторые основные тождества (тавтологии), приведенные в таблице хх.4. Таблица хх.4 Основные тождества БА |N |Название |Формулировка | |1 |Коммутативности |[pic] | | |(переместительный) | | |2 |Ассоциативности |[pic] | | |(сочетательный) | | |3 |Дистрибутивности |[pic] | |4 |Соотношения абсорбции |[pic] | |5 |Теорема де Моргана |[pic] | |6 |Двойного отрицания |[pic] | |7 |Двойственности |[pic] | |8 |Пустого множества |[pic] | |9 |Универсального множества |[pic] | |10 |Склеивания |[pic] | |11 |Поглощения |[pic] | |12 |Следствие из 3 |[pic] | |13 |Обобщенный закон Клода- |[pic] | | |Шеннона | | Хх.5 Свойства функции сложения по модулю два В таблице хх.5 приведены основные свойства функции сложения по модулю два. Таблица хх.5 Свойства функции «(» |N |Название |Формулировка | |1 |Определение операции |[pic] | |2 |Коммутативности |[pic] | |3 |Ассоциативности |[pic] | |4 |Дистрибутивности |[pic] | |5 |«Закон де Моргана» |[pic] | |6 |Соотношения для [pic] |[pic] | Хх.6 Свойства стрелки Пирса и штриха Шеффера Основные свойства стрелки Пирса и штриха Шеффера приведены в таблице хх.6. Таблица хх.6 Свойства функций «(» и «/» |N |Название |Формулировка | |1 |Определение функции «(» |[pic] | |2 |Определение функции «/» |[pic] | |3 |Коммутативности |[pic] | |4 |«Закон де Моргана» |[pic] | |5 |Соотношения для [pic] |[pic] | Следует отметить, что для обеих функций не справедливы законы ассоциативности и дистрибутивности. Хх.7 Способы определения равносильности БФ Существует три метода определения равносильности БФ: - при помощь ТИ; - при помощи законов алгебры логики; - приведением к СДНФ или СКНФ. Пусть даны три функции: [pic]; [pic]; [pic]. Определим равносильность данных функций. Хх.7.1 Определение равносильности БФ с помощью ТИ Таблица хх.7 ТИ для определения равносильности F1, F2, F3 x |y |[pic] |[pic] |xy |[pic] |[pic] |[pic] |[pic] |[pic] | |0 |0 |1 |1 |0 |0 |1 |1 |1 |1 | |0 |1 |1 |0 |0 |1 |0 |1 |1 |1 | |1 |0 |0 |1 |0 |0 |0 |0 |0 |0 | |1 |1 |0 |0 |1 |0 |0 |1 |1 |1 | | Если несколько функций принимают на всех наборах одни и те же значения, то эти функции равносильны. Получаем, что F1= F2= F3. Хх.7.2 Определение равносильности БФ при помощи логических преобразований [pic]. [pic]. Получили, что F1= F2= F3. Доказательство равносильности нескольких функций данным методом является самым сложным и требует очень хорошего знания свойств и законов БФ. Хх.7.3 Определение равносильности БФ при помощи СДНФ Сразу можно сделать вывод, что F1 является СДНФ. Любую БФ, равно как и ее ДНФ можно представить в виде СДНФ. [pic]. [pic]. Получаем, что F1= F2= F3. Хх.8 Выражение одних БФ через другие Логическим элементом (ЛЭ) будем называть вентиль, описываемый какой либо простой БФ. Логической схемой (цепью, структурой) будем называть совокупность ЛЭ, соединенных между собой так, что выполняется заданный закон функционирования. Задача синтеза сложных логических схем эквивалентна представлению сложных логических функций простыми функциями, описывающими работу ЛЭ. Одна из проблем синтеза заключается в выборе типов ЛЭ, из которых должны собираться логические схемы. Набор элементов должен допускать построение любой сколь угодно сложной структуры, т.е. представлять функционально полную систему операций. Однако ясно, что построение одной логической схемы из множества ЛЭ разных типов бывает нецелесообразно. В некоторых случаях гораздо эффективнее логическая структура, составленная из однотипных элементов. БФ, при помощи которых можно выразить любую другую БФ носят название функционально полных. При проектировании их еще называют базисом. Из определений бинарных функций (таких как «(», «(», «/» и т.д.) можно заметить, что свойствами базиса обладают наборы «И – НЕ», «ИЛИ – НЕ», «И – ИЛИ – НЕ». Так мы их и будем называть: базис «И – НЕ», базис «ИЛИ – НЕ», базис «И – ИЛИ – НЕ». Но этими наборами не исчерпываются все возможные функционально полные системы. Существует также базис «(», базис «/», базис «( – И – 1» и другие. Попытаемся выразить через стрелку Пирса и штрих Шеффера основные операции БА. Дизъюнкция выражается следующим образом: [pic]; [pic]. Конъюнкция выражается как: [pic]; [pic]. Хх.9 Закон двойственности Двойственной формой БФ называется такая форма, которая получается из заданной формы путем замены дизъюнкции на конъюнкцию и конъюнкции на дизъюнкцию. Двойственная форма функции F обозначается F*. Например, для булевой функции трех переменных [pic] двойственная форма запишется в виде [pic]. Закон двойственности: если две БФ тождественны между собой, то и их двойственные формы тоже тождественны. Следует заметить, что двойственную форму необходимо отличать от инверсной. Хх.10 Функциональная декомпозиция БФ Любую заданную БФ можно представить двумя способами: - с помощью двух составляющих; - разложением на множители. При этом используется метод разложения БФ по одной, двум и более переменным. В первом случае функция [pic] представляется в виде [pic]. Во втором – в виде [pic]. ----------------------- Рисунок хх.1 Условные обозначения ЛЭ: а) дизъюнктор; б) конъюнктор; в) инвертор; г) повторитель; д) ЛЭ «(»; е) элемент «ИЛИ – НЕ»; ж) элемент «И – НЕ» Рисунок хх.2 Временные диаграммы работы ЛЭ: а) дизъюнктора; б) конъюнктора; в) элемента «(»; г) инвертора