metod_15.03.04_atppp_oaip_ump_2016 (Методические документы), страница 8

множество возможных значений функции;3) правило соответствия, согласно которому каждому значению аргумента изобласти определения ставится в соответствие значение функции – y = F(x), y –функция, x – аргумент, F – правило соответствия.Функция одной или нескольких переменных, область определения которой заданамножеством М, а область значений описывается множеством {0,1} называетсяпредикатом.Предикат, аргументы которого могут принимать только значения 0 или 1(определены на множестве {0,1}) называется булевой функцией.Таким образом, булевой или переключательной функцией называется функция,принимающая только значения 0 или 1 и аргументы которой также могутпринимать только значения 0 или 1.Булевы функции могут быть заданы специальными таблицами истинности илианалитически в виде специальных высказывательных форм, называемых булевымиформами с использованием логических операций.32В математике операциями называют такие функции, области значений которыхсовпадают с областями определения их аргументов (бинарные операции сложения,вычитания, умножения, деления и унарная операция изменения знака).В математической логике также имеются несколько бинарных операций и однаунарная – отрицание.Операция НЕ (логическое отрицание, инверсия).

Отрицанием высказыванияА называется операция, результат Х которой истинен, когда А ложно, и ложен, когдаА истинно. Отрицание обозначается следующим образом:Х=Ā, которая читается так: Х есть инверсия от А. Таблица истинности, отражающаяеё значения при всевозможных комбинациях логических переменных, в неё входящих,и диаграмма Венна имеют вид:АХНЕ011 0X = AX=AЭлектронная схема, реализующая операцию отрицания, называетсяинвертором или схемой НЕ. Её условное графическое изображение имеет вид:ВходАХ = ĀВыход1На выходе элемента НЕ появляется сигнал при его отсутствии на входе.Операция ИЛИ (логическое сложение, дизъюнкция). Это логическая операция наддвумя переменными (А и В), результат Х которой истинен, если хотя бы одна изсоставляющих его переменных истинна.

Операция ИЛИ обозначается символом «»,который соответствует союзу «или»; знаком «+», обозначающим логическое сложение:Х = А  В, или Х = А + В.Таблица истинности, отражающая её значения, и диаграмма Венна имеют вид:А0011В0101AХ0111ИЛИB33Электронная схема, реализующая операцию ИЛИ, называется логической схемойразделительной схемой. Её условное графическоеИЛИ, дизъюнктором илиизображение имеет вид:АХ = А ВВходы1ВВыходНа выходе элемента ИЛИ сигнал соответствующий 1 появляется в том случае, еслиесть сигнал 1 хотя бы одном из его входов.

Следует отметить, что операция ИЛИсправедлива для любого числа логических переменных, т.е.Х= А  В  С ...  N.Операция И (логическое умножение, конъюнкция). Это логическая операция наддвумя переменными А и В, результат Х которой истинен, если истинны значения обеихпеременных. Операция И обозначается символом «», который соответствует союзу«и» или знаком умножения «», обозначающим логическое умножение:Х= А  В, или Х= А & В.Таблица истинности, отражающая её значения, и диаграмма Венна имеют вид:А0011ИВ0101Х0001A& BЭлектронная схема, реализующая операцию И, называется логической схемойИ, конъюнктором или схемой совпадения.

Условное графическое обозначениеэлемента И имеет вид:Х=АВВходыАВ&ВыходНа выходе элемента И сигнал, соответствующий 1, появляется только в том случае,если есть сигналы на всех его входах. Следует отметить, что операция И справедливадля любого числа логических переменных, т.е. Х= А  В  С ...  N.34Элементарные функции алгебры логики находятся в определённой связи друг сдругом, что отражается на уровне аксиом, свойств и законов.1. Аксиомы алгебры логики.а.

Х = ⌐ (Х) — отрицание отрицания; б. Х + Х = Х, Х  Х =Х – правила подобных преобразований;в. Х + 0 = Х;г. Х + 1 = 1;д. Х  0 = 0;е. Х  1 = Х;ж. Х Х = 0;з. Х +Х = 1;2.Свойства дизъюнкции и конъюнкции.а. Свойство ассоциативности (сочетательный закон):Х1+ (Х2+ Х3)= (Х1+ Х2) + Х3Х1* (Х2* Х3)= (Х1* Х2) * Х3б. Свойство коммутативности (переместительный закон):Х1 + Х2= Х2 + Х1Х1 * Х2= Х2 * Х1в. Свойство дистрибутивности (распределительный закон):Х1 + (Х2 + Х3)= Х1 Х2 + Х1Х3Х1 + x2Х3 = (Х1 + Х2)(Х1+ Х3)= Х1Х1+ Х1Х3+ Х2Х1+ Х2Х3= Х1(1+Х3+Х2) + Х2Х3=Х1+ Х2Х3; т.к.

1+Х3=1 и 1+Х2=1, Х*Х =Х .3.Законы поглощения.Х1+ Х1Х2=Х1(1+ Х2)=Х1, т.к. 1+ Х2=1Х1(Х1+ Х2)= Х1Х1+ Х1Х1=Х1+ Х1Х1=Х1; т.к. Х1Х1=Х1.4. Законы двойственности для сложения и умножения (законы де Моргана).A B = A  BA B = A  Bа. Проверка законов двойственности______Х10011Х20101Х11110Х2____(Х1) (Х2)111035______Х1+Х21000____(Х1) * (Х2)1000Совершенные нормальные формыПусть P и Q – некоторые высказывания. Тогда можно образовать сложныевысказывания P или Q, P и Q, не P, введя операции дизъюнкции (ИЛИ), конъюнкции(И) и отрицания (НЕ).Электронные схемы, реализующие эти операции, называют логическимиэлементами. На основе логических элементов строятся более сложные узлы и агрегаты,работа которых может быть описана посредством алгебры логики, т.е. с помощьюпереключательных (булевых) функций.В самом общем случае сколь угодно сложная логическая функция может бытьпредставлена следующей формулой:f(X1,X2, ... ,Xn),где X1,X2, ...

,Xn- логические переменные, принимающие значения 0 или 1.Логические переменные могут быть действительными и фиктивными. ПеременнаяХ действительна, если значение функции, куда она входит, изменяется при изменениизначения этой переменной.

В противном случае она фиктивна.Логические функции многих переменных могут задаваться таблично.Рассмотрим табличное определение функции трёх переменных:Х100001111Х200110011Х301010101F(Х1, Х2, Х3)00111100Из таблицы видно, что переменные Х1, Х2 - действительные, а переменная Х3 фиктивная, т.к. справедливо соотношение f(X1,X2, 0) = (X1,X2, 1), при любыхкомбинациях Х1 и Х2. Переменную X3 можно сократить из выражения булевойфункции. Следовательно, для функций алгебры логики существует возможностьсокращать (расширять) количество переменных устранением (введением) фиктивных.Булевы функции могут задаваться аналитически, т.е.

в виде формул. При этомсложные логические функции можно выражать через более простые логическиефункции. Минимальный набор простых логических функций, посредством которогоможет быть представлена любая ФАЛ, называется логическим базисом или полнойсистемой. Базис минимален, если удаление хотя бы одной функции превращаетсистему ФАЛ в не полную. Примеры базисной системы функций: (И, НЕ); (ИЛИ, НЕ).На практике намного удобней использовать не минимальный базис И, ИЛИ, НЕ.Любая таблично заданная логическая функция f (x1, x2,…. xn) может выражатьсячерез набор конъюнктивных и дизъюнктивных термов или импликант:f (x1, x2,…. xn) = F1  F2  …  Fn = Ф1  Ф2  …  Фm, где36Fi = x1x2…xn – конъюнктивный терм - произведение переменных и их отрицаний;Фj = x1 x2 …xn - дизъюнктивный терм - сумма переменных и их отрицаний. Еслитерм ФАЛ содержит полный набор переменных, связанных операцией конъюнкции, онносит название минтерм (конституента 1).

Термы ФАЛ, состоящие из полного наборапеременных, связанных операциями дизъюнкции, называются макстермами(конституенты 0).Представление ФАЛ в аналитическом виде возможно в дизъюнктивной нормальнойформе и в конъюнктивной нормальной форме.Дизъюнктивная нормальная форма (ДНФ) – это сумма минтермов (ДНФ несодержит скобок).Конъюнктивная нормальная форма (КНФ) – это произведение макстермов.Всякая сложная логическая функция может быть сведена к различным ДНФили КНФ. Однозначное соответствие между функцией алгебры логики и еепредставлением в дизъюнктивной или конъюнктивной нормальной формеобеспечивается только в одном случае – когда все конъюнкции ДНФ (термы)составлены из полного числа переменных или когда каждая дизъюнкция КНФсодержит максимальное число переменных.

Такие ДНФ и КНФ носят названиясовершенной дизъюнктивной нормальной формы и, соответственно, совершеннойконъюнктивной нормальной формы (СДНФ и СКНФ).Алгоритм получения СНДФ из таблицы истинности, задающей функцию:1. Выбрать из таблицы набор переменных (x1,x2, ... ,xn) для которого справедливосоотношение f(x1,x2, ...

,xn) = 1.2. Сформировать из этого набора переменных и их отрицаний минтерм, т.е.произведение переменных или их отрицаний: если переменная набора имеетнулевое значение, то она берется с отрицанием; переменные, имеющие единичныезначения в данном наборе не инвертируются.3. Повторить пункты 1 и 2 для всех других наборов таблицы, где логическаяфункция равна 1.4. Построить СДНФ путем логического суммирования полученных минтермов.Аналогично определяется алгоритм для получения СКНФ:1. Выбрать из таблицы набор переменных (x1,x2, ... ,xn), для которого справедливосоотношение f(x1,x2, ... ,xn) = 0.2. Сформировать макстерм, т.е.

дизъюнктивный набор переменных и их отрицаний:если переменная данного набора равна 0, то она включается в сумму безотрицания, а при равенстве 1 она инвертируется.3. Повторить пункты 1 и 2 для всех наборов переменных, где значение функцииравно 0.4. Построить СКНФ из полученных дизъюнкций переменных и их отрицаний путемлогического умножения.Пример. По таблице истинности построить СДНФ и СКНФ.СДНФ (f) = 000  010  100  101  110 = X1X2 X3 X1 X2X3  X1X2 X3  X1 X2 X3  X1 X2 X3. СКНФ (f) = 001  011  111 = (X1  X2 X3) (X1 X2 X3) (X1 X2 X3).37X1X2X30 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1f (X1,X2…Xn)10101110Упрощение логических функцийСовершенные нормальные формы однозначно представляют ФАЛ.