Логическая функция у=f(х1,х2,...,хn) задана, когда каждому набору х однозначно сопоставляется у. Количество функций, образуемых n переменными равно .
Если n = 1, то N = 4: у1 = 0,
у2 = 1,
у3 = х,
у4 = /х.
Для двух переменных n = 2 и N = 16.
В таблице 6 приведены некоторые из возможных функций при n=2
х1
х2
у1
у2
у3
у4
Таблица 6 – Логические функции двух переменных
6.1.3. Аксиомы алгебры логики
х+0=х
х×0=0
х0=х
х+1=1
х×1=х
х1=х
х+х=х
х×х=х
хх=0
х+х=1
х×х=0
хх=1
Таблица 7 – Аксиомы алгебры логики
Их можно проверить подставляя вместо х 0 или 1.
6.2.4. Правила Де-Моргана:
Любые логические функции могут быть построены с использованием только элементов "И-НЕ" или только элементов "ИЛИ-НЕ". Переход от операции "И" к операции "ИЛИ", а также обратный переход осуществляется с помощью законов дуальности (теорема де Моргана):
В предыдущей строке показана типичная ошибка,когда полагают,что произведение инверсий равно инверсии произведения этих же переменных.
Закон поглощения
х1+х1×х2 = х1(1+х2) = х1×1 = х1 х1 “поглощает” х2
6.2.5. Минимизация путем алгебраических преобразований
Пусть функция задана в виде таблицы:
х1
х2
х3
У
Таблица 8 – Функция, заданная в виде таблицы
Каждая строка таблицы представляет собой конъюнкцию переменных. Если значение переменной в данной строке равно 0, то переменная берется с инверсией.
Реализация полученного выражения с помощью элементов ”2и-не”:
Для n переменных заполняется прямоугольная таблица, содержащая 2n клеток так, чтобы в соседних клетках конъюнкции отличались не более, чем одним сомножителем.
Если минимизируемая функция при данном наборе переменных равна 1 , то в соответствующую клетку ставится 1 (нули можно не ставить). В прямоугольной таблице единицы обводятся контурами и записывается функция в виде суммы произведений, описывающих контуры. Число клеток внутри контура 2к (1,2,4,8...).
Следует покрыть все единицы возможно меньшим числом возможно более крупных блоков. Каждому блоку сопоставляется конъюнкция, записываемая следующим образом:
1)Если блок целиком лежит в единичной области переменной хi , то она включается в конъюнкцию без инверсии, если в нулевой области, то с инверсией.
2) Если блок делится точно пополам между нулевой и единичной областями хi ,то хi в конъюнкцию не включается (склеивание по хi).
Других расположений правильно выбранного блока быть не может.
Например:
а) для двух переменных ,заданных таблицей
б) для трех переменных:
6.3. Цифровые коды
6.3.1. Двоичный позиционный код
В обыденной жизни применяется десятичная система счисления, в которой используется 10 цифр от 0 до 9 и число представлено как сумма степеней числа 10. Например, число 1407 представляет сокращенную запись суммы 1*103 +4*102 +0*101 +7*100. В цифровой электронике чаще всего используется двоичная система счисления.
Двоичная (бинарная) система основана на степенях числа 2, оперирует только с двумя символами (цифрами): 0 и 1. Двоичная цифра (символ 0 и 1) является единичной элементарной информацией, которая называется битом. Биты объединяются в слова определенной длины, слово длиною в 8 бит называется байтом, В настоящее время наиболее распространены системы с байтовой организацией данных. Поскольку в двоичной системе используется два символа, она имеет основание 2 и значения, которые должны быть приписаны отдельным позициям (веса), являются степенями числа 2.
Целые числа без знака в двоичной системе счисления представляются следующим образом:
Наименьшая значащая цифра (младший разряд числа) здесь расположена справа, а слева последовательно каждая цифра представляет собой более высокий разряд, более высокую степень числа 2. Например, код 1011 представляет число
1*23+0*22+1*21+1*20=8+2+1=11
При сдвиге целого числа на одну позицию влево производится умножение на два, а при сдвиге на одну позицию вправо производится деление на 2, что обусловлено основанием этой системы счисления.
Перевод чисел из двоичной системы счисления в десятичную
Перевод выполняется путем сложения весов тех разрядов, в которых имеются единицы. Например:
.
0=х
