Логические основы цифровыхустройств

Алгебра логики (алгебра Буля)

Алгебра логики изучает связь между переменными параметрами, принимающими только два значения:

    "1" - логическая единица или "0" - логический нуль.

Основные понятия алгебры логики

Закон исключенного третьего

Если х ¹ 1, то х = 0, если х ¹ 0, то х = 1.

Логическая функция у=f(х₁,х₂,...,х_n) задана, когда каждому набору х однозначно сопоставляется у. Количество функций, образуемых n переменными равно .

Если n = 1, то N = 4:       у₁ = 0,

                  у₂ = 1,

                  у₃ = х,

                                           у₄ = /х.

Для двух переменных n = 2 и N = 16.

 

 В таблице 6 приведены некоторые из возможных функций при n=2

 

х1	х2	у1	у2	у3	у4
0	0	0	0	1	0
0	1	1	0	1	1
1	0	1	0	1	1
1	1	1	1	0	0

 

Таблица 6 – Логические функции двух переменных

6.1.3. Аксиомы алгебры логики

 

х+0=х	х×0=0	х 0=х
х+1=1	х×1=х	х 1=х
х+х=х	х×х=х	х х=0
х+х=1	х×х=0	х х=1

 

Таблица 7 – Аксиомы алгебры логики

 

Их можно проверить подставляя вместо х 0 или 1.

6.2.4. Правила Де-Моргана:

 

Любые логические функции могут быть построены с использованием только элементов "И-НЕ" или только элементов "ИЛИ-НЕ". Переход от операции "И" к операции "ИЛИ", а также обратный переход осуществляется с помощью законов дуальности (теорема де Моргана):

 

В предыдущей строке показана типичная ошибка,когда полагают,что произведение инверсий равно инверсии произведения этих же переменных.                      

Закон поглощения

   х₁+х₁×х₂ = х₁(1+х₂) = х₁×1 = х₁ х₁“поглощает” х₂

 

6.2.5. Минимизация путем алгебраических преобразований

 

Пусть функция задана в виде таблицы:

х1	х2	х3	У
0	0	1	1
0	1	1	1
1	1	1	1

 

Таблица 8 – Функция, заданная в виде таблицы

 

Каждая строка таблицы представляет собой конъюнкцию переменных. Если значение переменной в данной строке равно 0, то переменная берется с инверсией.

 

Реализация полученного выражения с помощью элементов ”2и-не”:

 

Рисунок 2.5 – Реализация функции, заданной таблицей       

6.1.6. Минимизация с помощью диаграмм Карно

Правило построения диаграммы Карно

 

 Для n переменных заполняется прямоугольная таблица, содержащая 2ⁿ клеток так, чтобы в соседних клетках конъюнкции отличались не более, чем одним сомножителем.

Если минимизируемая функция при данном наборе переменных равна 1, то в соответствующую клетку ставится 1 (нули можно не ставить). В прямоугольной таблице единицы обводятся контурами и записывается функция в виде суммы произведений, описывающих контуры. Число клеток внутри контура 2^к (1,2,4,8...).

Следует покрыть все единицы возможно меньшим числом возможно более крупных блоков. Каждому блоку сопоставляется конъюнкция, записываемая следующим образом:

     1)Если блок целиком лежит в единичной области переменной х_i, то она включается в конъюнкцию без инверсии, если в нулевой области, то с инверсией.

2) Если блок делится точно пополам между нулевой и единичной областями х_i,то х_i в конъюнкцию не включается (склеивание по х_i).

Других расположений правильно выбранного блока быть не может.

Например:

 

а) для двух переменных,заданных таблицей

 

 

 б) для трех переменных:

 

6.3. Цифровые коды

 

 

ЛОГИЧЕСКИЕ ОСНОВЫ ЦИФРОВЫХУСТРОЙСТВ

Основы алгебрылогики

Основой построения любого устройства, использующего цифровую информа- цию, являются элементы двух типов: логические и запоминающие. Логические эле- менты выполняют простейшие логические операции над цифровой информацией, а запоминающие – ее хранят.

Логическая операция состоит в преобразовании по определенным правилам входной информации в выходную. Сигналы на входах и выходах логических элемен- тов обычно являются двоичными (бинарными), т. е. принимают лишь два значения, символически обозначаемые как 0 и 1. Поэтому их также называют двоичными пере- менными и обозначают буквами латинского алфавита (входные сигналы xl, x2,..., xn, а результат операции, т. е. выходной сигнал – у). Переменная х может принимать два значения: либо х = 1 (событие истинно), либо х = 0 (событие ложно). Эти переменные называются также булевыми по имени английского математика Дж. Булля, который в середине XIX века разработал основные положения алгебры логики.

Различные логические переменные могут быть связаны функциональными за- висимостями. Например, y = f(x1, x2) указывает на функциональную зависимость ло- гической переменной у от логических переменных х1 и х2, называемых аргументами (или входными переменными).