Главная/

Радиоэлектроника, компьютеры и периферийные устройства. /

Вычислительныемашины и системы. Первый семестр.

наглядное представление для простых функций. Приведем в качестве примера наиболее часто встречающиеся функции от одной и двух переменных: 1) Переменная x: f(x) = x 2) Инверсия переменной x (функция НЕ): я4_ f(x) = x 3) Константа нуля: f(x) = 0 4) Константа единицы: f(x) = 1 .. - 2 - 5) Дизъюнкция (функция ИЛИ): f(xя41я0,xя42я0) = xя41я0 V xя42 Может встречаться другое обозначение: f(xя41я0,xя42я0) = xя41я0 | xя42я0. Таблица истинности (соответствия) для этой функции имеет вид: ЪДДДДДВДДДДДВДДДДДДДДДї і xя41я0 і xя42я0 і xя41я0 V xя42я0 і ГДДДДДЕДДДДДЕДДДДДДДДДґ і 0 і 0 і 0 і і 0 і 1 і 1 і і 1 і 0 і 1 і і 1 і 1 і 1 і АДДДДДБДДДДДБДДДДДДДДДЩ 6) Конъюнкция (функция И): f(xя41я0,xя42я0) = xя41я0 я5.я0 xя42 Может встречаться другое обозначение: f(xя41я0,xя42я0) = xя41я0 & xя42я0. Таблица истинности для этой функции имеет вид: ЪДДДДДВДДДДДВДДДДДДДДДї і xя41я0 і xя42я0 і xя41я0 я5.я0 xя42я0 і ГДДДДДЕДДДДДЕДДДДДДДДДґ і 0 і 0 і 0 і і 0 і 1 і 0 і і 1 і 0 і 0 і і 1 і 1 і 1 і АДДДДДБДДДДДБДДДДДДДДДЩ 7) Функция ИЛИ-НЕ: я4_______ f(xя41я0,xя42я0) = xя41я0 V xя42 Таблица истинности для этой функции имеет вид: ЪДДДДДВДДДДДВДДДДДДДДДї і xя41я0 і xя42я0 і xя41я0 V xя42я0 і ГДДДДДЕДДДДДЕДДДДДДДДДґ і 0 і 0 і 1 і і 0 і 1 і 0 і і 1 і 0 і 0 і і 1 і 1 і 0 і АДДДДДБДДДДДБДДДДДДДДДЩ .. - 3 - 8) Функция И-НЕ: я4_______ f(xя41я0,xя42я0) = xя41я0 я5.я0 xя42 Таблица истинности для этой функции имеет вид: ЪДДДДДВДДДДДВДДДДДДДДДї і xя41я0 і xя42я0 і xя41я0 V xя42я0 і ГДДДДДЕДДДДДЕДДДДДДДДДґ і 0 і 0 і 0 і і 0 і 1 і 1 і і 1 і 0 і 1 і і 1 і 1 і 1 і АДДДДДБДДДДДБДДДДДДДДДЩ 9) Функция ИСКЛЮЧАЮЩЕЕ ИЛИ (сумма по модулю 2): f(xя41я0,xя42я0) = mod2(xя41я0,xя42я0) Таблица истинности для этой функции имеет вид: ЪДДДДДВДДДДДВДДДДДДДДДДДДДї і xя41я0 і xя42я0 і mod2(x1,x2) і ГДДДДДЕДДДДДЕДДДДДДДДДДДДДґ і 0 і 0 і 0 і і 0 і 1 і 1 і і 1 і 0 і 1 і і 1 і 1 і 0 і АДДДДДБДДДДДБДДДДДДДДДДДДДЩ я2Аксиомы алгебры логики В алгебре логики определено отношение эквивалентности (=) и три операции: дизъюнкция, конъюнкция и отрицание. Отношение эквивалентности удовлетворяет следующим свойствам: x=x - рефлексивность; если x=y, то y=x - симметричность; если x=y и y=z, то x=z - транзитивность. Из отношения эквивалентности сле- дуетя2 принцип подстановкия0: если x=y, то в любой формуле, содержа- щей x, вместо x можно подставить y, и будет получена эквивалент- ная формула. Алгебра логики определяется следующей системой аксиом: x = 0, если x я7-я0 1я7 ) я78я0 (1) x = 1, если x я7-я0 0я7 0 1 V 1 = 1я7 ) я78я0 (2) 0я5 .я0 0 = 0я7 0 . - 4 - 0 V 0 = 0я7 ) я78я0 (3) 1 я5.я0 1 = 1я7 0 0 V 1 = 1 V 0 = 1я7 ) я78я0 (4) 0я5 .я0 1 = 1я5 . я00 = 0я7 0 я4_ 0 = 1я7 ) я4_я0 я78я0 (5) 1 = 0я7 0 Аксиома (1) утверждает, что в алгебре логики рассматриваются только двоичные переменные, аксиомы (2)-(4) определяют операции конъюнкции и дизъюнкции, а аксиома 5 - операцию отрицания. Если в аксиомах (2)-(5), заданных парами утверждений, произ- вести взаимную замену операций дизъюнкции и конъюнкции, а также элементов 0 и 1, то из одного утверждения пары будет получено другое. Это свойство называется принципом двойственности. я2Теоремы алгебры логики С помощью аксиом алгебры логики можно доказать целый ряд те- орем и тождеств. Одним из эффективных методов доказательства тео- рем являетсяя2 метод переборая0 всех значений переменных: если теоре- ма истинна, то при подстановке любых значений переменных в обе части выражения, формулирующего утверждение теоремы, должно полу- читься тождество. Методом перебора можно убедиться в справедливости следующих теорем: идемпотентные законы x V x = xя7 ) я78 x я5.я0 x = xя7 0 коммутативные законы x V y = y V xя7 ) я78 x я5.я0 y = y я5.я0 xя7 0 ассоциативные законы (x V y) V z = x V (y V z)я7 ) я78 (x я5.я0 y) я5.я0 z = x я5.я0 (y я5.я0 z)я7 0 .. - 5 - дистрибутивные законы x я5.я0 (y V z) = x я5.я0 y V x я5.я0 zя7 ) я78 x V y я5.я0 z = (x V y)я5.я0(x V z)я7 0 законы отрицанияя4 _ x V x = 1я7 ) я4_я0 я78 x я5.я0 x = 0я7 0 0 V x = xя7 ) я78 1 я5.я0 x = xя7 0 1 V x = 1я7 ) я78 0 я5.я0 x = 0я7 0 законы двойственности (теоремы де Моргана) я4_____ _ _ x V y = x я5. я0yя7 ) я4_____я0 я4_я0 я4_я0 я78 x я5.я0 y = x V yя7 0 закон двойного отрицанияя4 я0 я4 _____ я7(я0 я4_я7 ) я72я0 xя7 2я0 = x я79 0 законы поглощения x V x я5.я0 y = xя7 ) я78 xя5.я0(x V y) = xя7 0 операции склеиванияя4 _ x я5.я0 y V x я5.я0 y = xя7 я0 я7) я4_я0 я78 (x V y)я5.я0(x V y) =я7 я0x я70 операции обобщенного склеивания я4_ _ xя5.я0y V xя5.я0z V yя5.я0z = xя5.я0y V xя5.я0z я5 я7) я4_я0 я5 я4_я5 я0 я78 (x V y)я5.я0(x V z)я5.я0(y V z) =я7 я0(x V y)я5.я0(x V z) я70 я4_ x V x я5.я0 y = x V yя7 ) я4_я0 я78 xя5.я0(x V y) = xя7 я5.я0 y я70