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

Например, пара взаимодополняющихдо девяти цифр 2 и 7 соответствуют комбинации 0101 и 1010, каждая из которыхобразуется как инверсия другой. Код 3а+2 тоже обладает свойством дополнения додевяти, что упрощает выполнение в цифровых устройствах операции наддесятичными числами.При представлении алфавитно-цифровой информации – букв, цифр и другихзнаков применяются различные варианты кодирования символов. Наиболеераспространенным является представление алфавитно-цифровой информации спомощью восьми разрядных слов – байтов.

С помощью байта можно закодировать256 различных символов.1.4.Алгебра логикаВ алгебре логики рассматриваются следующие компоненты:7- переменные, могут принимать только два значения 0 и 1, переменныебудем обозначать латинскими буквами x,y,z…, а также x0,x1,…xn,y0,y1,…yn и т.д.;- отношение эквивалентности (равенства «=»), удовлетворяет следующимсвойствам:- рефлексивность – x=x;- симметричность – если x=y то y=x;- транзитивность – если x=y и y=z то x=z, отсюда следует принцип, еслиx=y, то в любой формуле, содержащей x, в место x можно подставить y,и в результате будет получена эквивалентная формула;- три операции:- дизъюнкция, операция ИЛИ, логическое сложение. Обозначают знаком∨ или +;- конъюнкция, опе6рация И, логическое умножение, обозначаетсязнаком ∧, или &, или *, или опускается;- отрицание, инверсия, операция НЕ, обозначается чертой надпеременной, или над элементами 0 и 1, или над операциями с охватомвсех переменных входящих в операцию ( X , Y , или 1, 0, или X  Y );1.4.1. Аксиомы алгебры логикиx  0, если x  1x  1, если x  00  0  01*1  1 0  11  0(1.1)(1.3)11  1 0 * 0  00  1  1  0  11* 0  0 *1  0 (1.2)(1.4)(1.5)Формула (1.1) – утверждает, что в алгебре логики рассматриваются толькодвоичные переменные.Формулы (1.2)-(1.4) – определяют операции дизъюнкции и конъюнкции.Формула (1.5) – определяет операцию отрицания.1.4.2.

Теоремы и тождества алгебры логикиНа основании аксиом алгебры логики можно вывести ряд теорем и законов.1. Идемпотентные законыx  x  xx* x  x(от лат. idem — такой же и potens — степень)(1.6)82. Коммутативные законыx  y  y  xx* y  y* x (1.7)3. Ассоциативные законы( x  y )  z  x  ( y  z )( x * y) * z  x * ( y * z ) (1.8)4. Дистрибутивные законыx * ( y  z)  x * y  x * z x  y * z  ( x  y)(x  z )(1.9)5. Законы отрицанияx  x  1x * x  0(1.10)0  x  x1* x  x 1  x  10 * x  0(1.11)(1.12)6.

Законы двойственности (теоремы де Моргана)x  y  x * y xy  x  y 7. Закон двойного отрицания(1.13)( x)  x  x (1.14)8. Законы поглощенияx  xy  x x * ( x  y)  x(1.15)9. Операции склеиванияxy  x y  x ( x  y )( x  y )  x (1.16)x  xy  x  yx( x  y )  xy (1.17)Большинство теорем, а также аксиом записаны парами. При внимательномизучении пар можно вывести принцип двойственности – если в тождествепроизвести взаимные замены операций дизъюнкции и конъюнкции, а такжеэлементы 0 и 1, если они имеются, то получим тоже тождество. Такое свойствоназывается принципом двойственности.f(v,0,l/+,&)=g(v,0,/+,&) где v=(xn-1,...,x0) то справедливо также тождество:f(v,l,0/&,+)=g(v,l,0/&,+)9Все теоремы могут быть доказаны аналитически или методом перебора.1.

Метод перебора – тождество (1.13)XY00011011x yx* y0  0  0 10 1  1  01 0  1  011  1  00 * 0  1*1  10 *1  1* 0  01* 0  0 *1  01*1  0 * 0  02. Аналитический метод – тождество (1.17)x  xy  x  yx  x y  x(1  y )  x y  x  xy  x y  xx  xy  x y  x x  ( x  x) x  ( x  x) y  x  yПорядок выполнения операций:- отрицание слагаемой или сомножителя;- конъюнкция сомножителей;- дизъюнкция слагаемых;- общее отрицание дизъюнкции или конъюнкции.1.5.Логические функцииЛогическая функция – это логическое выражение, состоящее из логическихпеременных связанных между собой с помощью операций алгебры логики.В соответствии с выше приведенными аксиомами (1.1)-(1.5) функция можетпринимать в зависимости от значений переменных xp только два значения 0 и 1.Для функции n переменных xn-1,…,x0 будем использовать общее обозначениеFv   f xn1 ,..., x0  где v=(xn-1,…,x0) каждая переменная xp (p=0,1,2,…,n) можетпринимать только два значения 0 и 1.

Поэтому число всех возможных комбинацийзначений xn-1,…,x0 конечно и равно 2n.В общем виде конкретное значение переменной xp (0 или 1) будемобозначать через ep. Символами i, j и т.п. будем обозначать порядковыедесятичные числа. en-1…ep…e0 – обобщающая запись двоичного числа, где ep = 0или 1, и являются элементами алгебры логики если они используются в качествезначений переменных, для этих элементов не существует соотношений больше илименьше.1.5.1.

Область определения логических функцийОбластьюсовокупностьопределенияфункцииnпеременныхxn-1,…,x0являетсяточек10n-мерного пространства, причем каждая из точек задается определеннойкомбинацией значений этих переменных xn1  en1 ..., x p  e p ..., x0  e0 где ep =0 или 1,(p=0,1,2,…,n-1).Например – пусть есть некая функция 4х переменных n=4 то одна из точекопределения этой функции Vi =(en-1…ep…e0) где i=en-1…ep…e0 (например,Vi=1100).Из этих соотношений видно, что точки определения можно посчитать попорядкуот 0 до 2n как в двоичном счете, так и десятичном и в любом другом.

Поэтомуобласть определения функции f(v) n переменных имеет 2n точек т.е.V  V0 , V1 ,..., V2 n 1 Для задания функции f(v) следует указать ее значения во всех точках областиопределения т.е. следует задать значения f(vi)=0 или 1 где i=0,1,2,…,2n-1. Всовокупности эти значения представляют некое двоичное число из 2n разрядов т.к.имеется всего 2 2 различных 2n разрядных двоичных чисел, то и число различныхnфункций n переменных равно 2 2 .Функции n переменных могут зависеть не от всех переменных xn-1…x0.

Такиефункции называются вырожденными.Также функция может быть задана как во всех точках определения, так и нево всех:- функция n переменных f(v) называется полностью определенной, если еезначения f(vi)=0 или 1 заданы во всех 2n точках Vi области определения;- если же значение функции не задано хотя бы в одной точки Vi, то онаназывается не полностью определенной, это означает, что функция вэтой точке может иметь значение 1 или 0 – и это не важно – такоезначение будем называть коэффициентом с;- если значения функции не заданы во всех точках Vi, то она называетсяполностью неопределенной.n1.5.2.

Таблица истинностиТак как область определения любой функции n переменных конечна 2n точекона может быть задана таблицей значений f(vi)=0 или 1 которые она принимает вточках vi, где i=0,1,…,2n-1. Такие таблицы называются таблицами истинности.Например: функция 2х переменныхVi точкиопределенияфункцииV0Значения точекопределения функции(значения e1,e0переменных функцииx1,x0)00Значениефункции f(v) вточкахопределения111V1V2V30110110001.5.3. Логические функции одной переменнойРазберем параметры таких функций:- n=1 – число переменных;- m=2 – число точек определения;- N=4 – число всех функций одной переменной.Рассмотрим каждую функцию:1.

f 0  0– нулевая функция.2. f1  x– функция повторения.3. f 2  x– функция отрицания.4. f 3  1– единичная функция.Таблица истинности функций одной переменнойf0  0f3  1f1  xf2  xVix00000111101011.5.4. Логические функции двух переменныхРассмотрим параметры функций:- n=2 – число переменных;- m=4 – число точек определения;- N=16 – число всех функций двух переменных.Таблица истинности всех функций двух переменныхVi x1,x0 f 0 f1 f 2 f 3 f 4 f 5 f 6 f 7 f 8 f 90 00 0 1 0 1 0 1 0 1 0 11 01 0 0 1 1 0 0 1 1 0 02 10 0 0 0 0 1 1 1 1 0 03 11 0 0 0 0 0 0 0 0 1 1f10f11f12f13f14f15010111010011101101111111Значительный интерес представляют невырожденные функции, которыеразберем подробно:1. Функция логического умножения (конъюнкция).f 8  x1 x0 – логическое умножение, описывает работу логического элементаИ.Vi x1,x0 f 8x0x1f 8  x1 x01201230001101100012.

Функция логического сложения (дизъюнкция)f14  x1  x0 – логическое сложение, описывает работу логическогоэлемента ИЛИ.Vi x1,x0 f14x00 00 0f14  x1  x01 01 12 10 1x13 11 13. Функциясложениенеравнозначность)помодулюдва(исключающееИЛИ,f 6  x1  x0  x0 x1  x0 x1 – сложение по модулю два, применяется дляарифметического сложенияVi x1,x0 f 6x00 00 01 01 12 10 1x13 11 0f 6  x1 x0  x0 x14. Функция Пирса логическое сложение с отрицанием, отрицаниедизъюнкции (стрелка Пирса ИЛИ-НЕ)f1  x1  x0  x0  x1 – логическое сложение с отрицанием ИЛИ-НЕVi x1,x0 f1x00 00 1f1  x1  x01 01 02 10 03 11 0x15.

Функция Шеффера, отрицание от логического умножения (штрихШеффера И-НЕ)f 7  x1  x0  x0 x1 – логическое умножение с отрицанием И-НЕVi x1,x0 f 7x0x1f 7  x1 x0130123000110111110Функции двух переменных исключительно важны в силу того, что любаялогическая функция n переменных может быть получена из них методомсуперпозиции – подстановкой этих функций в место переменных в другиефункции.1.5.5. Теоремы разложенияВ теории логических функций особо важное значение имеет теоремаразложения Шеннона: любую функцию F(v) можно разложить по переменной xp вформе:f xn1 ,...,x p ,...,x0   x p  f xn1 ,...,0,...,x0   x p  f xn1 ,...,1,...,x0 По принципу двойственности получается двойственная теорема разложения:f xn1 ,...,x p ,...,x0   x p  f xn1 ,...,1,...,x0   x p  f xn1 ,...,0,...,x0 С теоремой разложения связаны тождестваx p  f xn1 ,...,x p ,...,x0   x p  f xn1 ,...,0,...,x0 x p  f xn1 ,..., x p ,..., x0   x p  f  xn1 ,...,1,..., x0 x p  f xn1 ,...,x p ,...,x0   x p  f xn1 ,...,1,...,x0 x p  f xn1 ,..., x p ,..., x0   x p  f  xn1 ,..., 0,..., x0 1.6.Представление логической функции в виде СДНФ и СКНФЛогическая функция дизъюнктивной формы (ДФ): - представляет собойдизъюнкции отдельных членов, каждой из которых, в свою очередь, есть некотораяфункция, содержащая только конъюнкции и инверсии.f  x2 x1  x2 x0  x2 x1 x0 - где f функция 3х переменных.Логическая функция дизъюнктивной нормальной формы (ДНФ): форма представления дизъюнктивной функции, в которой инверсия применяется14лишь непосредственно к аргументам (переменным), но не к более сложнымфункциям от этих аргументов.f  x2 x1  x1 x0  x1 - где f функция 3х переменных.Логическая функция совершенной дизъюнктивной нормальной формы(СДНФ): - если каждый член дизъюнктивной нормальной функции от nаргументов содержит все эти n аргументы, часть из которых входит в него синверсией, а часть без нее.f  x2 x1 x0  x2 x1 x0  x2 x1 x0 - где f функция 3х переменных.Логическая функция конъюнктивной формы (КФ): - представляет собойконъюнкцию отдельных членов, каждой из которых, в свою очередь, естьнекоторая функция, содержащая только дизъюнкции и инверсии.f  x2  x0  x1  x0 x2  x1  x0 - где f функция 3х переменных.Логическая функция конъюнктивной нормальной формы (КНФ): форма представления конъюнктивной функции, в которой инверсия применяетсялишь непосредственно к аргументам (переменным), но не к более сложнымфункциям от этих аргументов.f  x1  x0 x2  x0 x1 - где f функция 3х переменных.Логическая функция совершенной конъюнктивной нормальной формы(СКНФ): - если каждый член конъюнктивной нормальной функции от nаргументов содержит все эти n аргументы, часть из которых входит в него синверсией, а часть без нее.f  x2  x1  x0 x2  x1  x0 x2  x1  x0  - где f функция 3х переменных.1.6.1.