Таблица истинности

Название

функции

Условное обозначение

Алгебраическое

выражение

Функция

x₁

0

0

1

1

x₂

0

1

0

1

СДНФ

СКНФ

1

2

3

4

5

6

7

8

9

f₀

0

0

0

0

Константа нуль

0

f₁

0

0

0

1

Конъюнкция

x₁ x₂

f₂

0

0

1

0

Запрет по x₂

x₁ x₂

x₁ x₂

f₃

0

0

1

1

Тождественность x₁

x₁

f₄

0

1

0

0

Запрет по x₁

x₂ x₁

x₂ x₁

f₅

0

1

0

1

Тождественность x₂

x₂

f₆

0

1

1

0

Исключающее ИЛИ Сумма по модулю 2

x₁ x₂

f₇

0

1

1

1

Дизъюнкция

x₁ Ú x₂

x₁ + x₂

f₈

1

0

0

0

Стрелка Пирса

x₁ ¯ x₂

f₉

1

0

0

1

Равнозначность

x₁ ~ x₂

f₁₀

1

0

1

0

Инверсия x₂

f₁₁

1

0

1

1

Импликация

от x₂ к x₁

x₂ ® x₁

f₁₂

1

1

0

0

Инверсия x₁

f₁₃

1

1

0

1

Импликация

от x₁ к x₂

x₁ ® x₂

f₁₄

1

1

1

0

Штрих Шеффера

x₁ / x₂

f₁₅

1

1

1

1

Константа единицы

1

x₁

x₂

0

1

0

Рис.1.1 Карта Карно для логической функции двух аргументов.

Рис.1.2 Карта Карно для логической функции трех аргументов.

Рис. 1.3 Карта Карно для логической функции четырех аргументов.

Рис.1.4 Карта Карно для логической функции пяти переменных.

Между представлением логической функции в табличной (таблица истинности), алгебраической (в виде СДНФ) и графической (на карте Карно) формах имеется однозначное соответствие. Логическая функция на карте Карно представляется совокупностью клеток, заполненных 1, инверсия этой функции представляется совокупностью пустых клеток (или заполненных 0).

Для логических функций с числом переменных n ³ 6 наглядность карт Карно теряется и поэтому такие функции представляются в виде композиции функции меньшего числа переменных:

,

где x₁ - выделяемая переменная;

функции получаются из функции f подстановкой значений x₁=0 и x₁=1.

В качестве выделяемой может использоваться любая переменная. Например,

Процесс выделения более простых функций называется декомпозицией. Полученные функции f₀ и f₁ могут подвергаться дальнейшей декомпозиции.

1.2 Логические операции

Множество логических функций n переменных можно образовать посредством трех основных логических операций:

1. Логическое отрицание (инверсия);

2. Логическое сложение (дизъюнкция);

3. Логическое умножение (конъюнкция).

Более сложные логические преобразования можно свести к указанным операциям [4]. Логические функции подчиняются принципу дуальности (двойственности) - теоремы Де Моргана; согласно которому операции конъюнкции и дизъюнкции допускают взаимную замену, если одновременно поменять логическую 1 на 0, 0 на 1, знак Ú (+) на Ù(×), а Ù(×) на Ú (+), где Ú или + - обозначение операции дизъюнкции; Ù или × - обозначение операции конъюнкции.

1.3 Аксиомы булевой алгебры

Булева алгебра базируется на нескольких аксиомах, из которых выводят основные законы для преобразований с двоичными переменными (табл. 1.6, 1.7)

Таблица 1.6

Аксиомы булевой алгебры

конъюнкция	дизъюнкция
0×0=0	0+0=0
0×1=0	0+1=1
1×1=1	1+1=1

x×0=0	x+0=x
x×1=x	x+1=1
x×x=x	x+x=x

Таблица 1.7

Законы булевой алгебры

1.5 Некоторые полезные соотношения

1.6 Минимизация логических функций с помощью карт Карно

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

При проведении контуров придерживаются правил:

1. контур должен быть прямоугольным;

2. внутри контура должны быть только клетки, заполненные единицами;

3. число клеток, находящихся внутри контура, должно быть целой степенью числа 2, т.е. можно склеивать 1, 2, 4, 8,... членов;

4. одни и те же клетки, заполненные единицами, могут входить в несколько контуров;

5. при проведении контуров самая нижняя и самая верхняя строки таблицы считаются соседними, то же - для крайнего левого и крайнего правого столбцов;

6. число контуров должно быть как можно меньшим, а сами контуры как можно большим.

Пример 1.6. Провести минимизацию логической функции, заданной в форме СДНФ,с помощью карты Карно (рис.1.5).

Рис.1.5 Карта Карно.

Решение. С помощью преобразований, выполняемых по законам булевой алгебры, и с учетом объединенных на карте Карно клеток, получают минимизированное выражение (МДНФ) логической функции:

;

,

.

В рассмотренном примере двум клеткам первого объединения соответствуют минтермы, имеющие две общие переменные

.

Поэтому дизъюнкция этих минтермов равна этим двум общим переменным: .

Четырем клеткам второго объединения соответствуют минтермы имеющие одну общую переменную :

Дизъюнкция этих минтермов также равна общей переменной .

Чем больше клеток входит в объединение, тем меньше переменных входит в соответствующий конъюнктивный член, т.е. проще МДНФ.

Процесс получения алгебраического выражения логической функции, представленной на карте Карно, сводится к считыванию объединений клеток. При этом каждое объединение клеток считывают в виде конъюнктивного члена, в который входят переменные или их инверсии, общие для всех минтермов, соответствующих этим клеткам.

Необъединенные клетки считывают в виде записанных в них минтермов.

Число конъюнктивных членов в МДНФ равно сумме объединений и необъединенных клеток.

Пример 1.7. Логическая функция задана табл.1.8

Таблица 1.8

Таблица истинности

Найти СДНФ этой функции, и провести минимизацию с помощью карты Карно.

Решение: 1. Находят минтермы:

2. Логическая функция в форме СДНФ:

.

3. Карта Карно логической функции (рис.1.6)

Рис.1.6 Карта Карно логической функции

4. Получают МДНФ функции

.

Пример 1.8. Минимизировать с помощью карты Карно (рис.1.7) логическую функцию, заданную в форме СДНФ:

Рис.1.7 Карта Карно

Решение: МДНФ функции:

.

Пример 1.9. Минимизировать с помощью карты Карно (рис.1.8) заданную в форме СДНФ логическую функцию:

.

Рис.1.8 Карта Карно:

Решение: МДНФ функции:

1.7 Аналитические методы минимизации логических функций

Эти методы базируются на применении основных законов булевой алгебры.

Алгоритм получения МДНФ логической функции:

1. Логическая функция представляется в СДНФ. Причем, если она задана таблицей истинности, то представляют путем записи “по единицам”; если она задана алгебраической произвольной дизъюнктивной форме - путем применения операций развертывания, формул Де Моргана и др.

1. В полученном СДНФ проводят все возможные операции неполного склеивания и затем поглощения. В результате получают сокращенную дизъюнктивную нормальную форму, т.е. дизъюнкцию самых коротких из всех возможных элементарных произведений (простые импликанты), входящие в данную логическую функцию.

2. Находят минимальные дизъюнктивные нормальные формы по импликантной матрице.

Импликантная матрица - это таблица, на вертикальные и горизонтальные входы которой записывают соответственно члены СДНФ и простые импликанты заданной логической функции.

Клетки импликантной матрицы, образованные пересечением строк с импликантами и столбцов с поглощательными ими членами СДНФ, отмечают крестиками [5].

МДНФ находят как дизъюнкцию минимального числа импликант, которые совместно накрывают крестиками все колонки импликантной матрицы.

Пример 1.10. Минимизировать логическую функцию:

Решение: 1. Функция задана в алгебраической форме, применяя операции развертывания

получают СДНФ, содержащую шесть членов:

2. Операции склеивания проводят в следующем порядке:

1. выполняются все возможные склеивания 1-ого члена с остальными;

2. выполняются все возможные склеивания 2-ого члена с остальными, кроме 1-ого;

3. выполняются все возможные склеивания 3-ого члена с остальными, кроме 1-ого и второго и т.д.

Склеиваться могут только те члены, у которых число переменных с отрицаниями отличается на единицу. Результаты склеивания и поглощения:

Звездочками отмечают те члены СДНФ, которые поглощаются произведениями, образовавшимися после склеивания.

В рассматриваемом примере поглощаются все шесть исходных членов, поэтому СДНФ заданной функции имеет вид:

К этому выражению операции склеивания и поглощения применить нельзя, и, следовательно, оно является сокращенной дизъюнктивной нормальной формой логической функции, а его члены - простыми импликантами.

3. Строят для заданной функции импликантную матрицу (табл.1.9)

Таблица 1.9

Импликантная матрица

Для получения МДНФ необходимо найти минимальное число импликант, которые совместно накрывают крестиками все столбцы импликантной матрицы:

Сложность логической функции определяется числом переменных входящих в ее выражение: в заданной функции 14, в минимальной - 9.

Первый алгоритм получения МКНФ логической функции:

1. Логическую функцию представляют в СКНФ. Причем, если она задана таблицей истинности, то ее записывают “ по нулям”; если она задана алгебраически в произвольной конъюктивной форме, то для записи в СКНФ выполняют все возможные операции развертывания.

2. В полученной СКНФ выполняют все возможные операции неполного склеивания и затем поглощения. В результате получают сокращенную конъюнктивную нормальную форму, члены которой являются простыми макстермами.

3. МКНФ находят по макстермной матрице.

Пример 1.11. Логическая функция задана табл.1.10

Таблица 1.10

Таблица истинности

Найти МКНФ этой функции.

Решение:

1. Выписывают заданную функцию в СКНФ “по нулям” таблицы истинности:

2. Проводят операции склеивания и поглощения:

В данном примере поглощаются все четыре члена исходного выражения и, следовательно, СКНФ

3. Макстермная матрица задана табл.1.11

Таблица 1.11

Макстермная матрица

4. МКНФ логической функции:

.

Второй алгоритм получения МКНФ логической функции:

1. Логическая функция представляется в СДНФ заданной функцией, взятой с отрицанием.

Если функция задана таблицей истинности, то выписывают ряд произведений всех аргументов и соединяют их знаками дизъюнкции; количество произведений должно равняться числу наборов, на которых заданная функция обращается в нуль; под каждым произведением записывают набор аргументов, на которых функция равна нулю, и над аргументами, равными нулю, ставят знаки отрицания. Если функция заданна алгебраически в произвольной форме, то сначала находят ее СДНФ, а затем записывают дизъюнкцию всех произведений аргументов, которые не вошли в СДНФ.Находят МДНФ по рассмотренному выше алгоритму. От полученной МДНФ берут отрицание и, после преобразований по формулам Де Моргана, получают МКНФ.

Пример 1.12. Найти МКНФ, функции заданной табл.1.12

Таблица 1.12

Таблица истинности

Решение: 1. СДНФ, взятая с отрицанием:

2. Результаты склеивания и поглощения:

3. МДНФ, взятая с отрицанием:

4. Взяв от обеих частей последнего равенства отрицание и применив формулу Де Моргана, получают МКНФ логической функции:

.

1.8 Логический базис

Любую логическую функцию можно представить в виде СДНФ или СКНФ, т.е. с помощью соответствующей комбинации простейших логических функций И, ИЛИ, НЕ. Такой набор простейших логических функций называют функционально полным или логическим базисом.

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

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

.

В результате получим минимальные базисы: И, НЕ и ИЛИ, НЕ.

2 Логические элементы, образующие логический базис

2.1 Конъюнктур (элемент И)

Конъюнктур - реализует операцию “логическое умножение”. Схема имеет два или больше входов и один выход. На выходе сигнал “1” появляется тогда и только тогда, когда на все входы одновременно воздействуют входные сигналы “1” рис. 2.1.

Логика работы конъюнктура на три входа представлена табл.2.1

Таблица 2.1

Таблица состояний конъюнктура

Логическое уравнение работы конъюнктура:

.

Знаки (×), (L) соответствуют конъюнкции и читаются как союз И.

Если на вход конъюнктура поступают сигналы в разные моменты времени и разной длительности, то сигнал на входе определяется как результат пересечения входных сигналов (рис. 2.2)

Таким образом , где i=1,2,... ,n

С точки зрения физической реализации конъюнктуры могут быть выполнены на различных “вентильных” компонентах (диодах, транзисторах и др.)

Функцию И реализуют, например, соединенные последовательно замыкающие контакты нескольких реле. Цепь в этом случае будет замкнута только тогда, когда сработают все реле.

2.2 Дизъюнктор (элемент ИЛИ)

Дизъюнктор - реализует операцию "логическое сложение". Схема имеет два или больше входов. На выходе сигнал "1" появляется тогда, когда хотя бы на один вход воздействует сигнал "1"(рис.2.3).

Логика работы дизъюнктора на три входа представлена табл.2.2

Таблица 2.2

Таблица состояний дизъюнктора

Логическое уравнение работы дизъюнктора: у=х₁+х₂+х₃ или . Знаки (+), () соответствуют дизъюнкции и читаются как союз ИЛИ. Если на вход дизъюнктора поступают сигналы в разные моменты времени и разной длительности, то сигнал на выходе определяется как результат объединения входных сигналов (рис.2.4).

Таким образом, .

С точки зрения физической реализации дизъюнкторы могут быть выполнены на различных "вентильных" компонентах (диодах, транзисторах и др.). Функцию ИЛИ реализуют, например, содиненные параллельно замыкающие контакты нескольких реле. Цепь в этом случае будет замкнута, если сработает хотя бы одно реле.

3. Инвертор (элемент НЕ)

Инвертор - реализует операцию "логическое отрицание". Схема имеет один вход и один выход. На выходе сигнал "1" имеет место в случае, если на входе будет сигнал "0"(рис.2.5).

Рис. 2.5 Условные изображения инвертора на функциональных схемах: Х-вход, У-выход

Логика работы инвертора представлена табл.2.3

Таблица 2.3

Таблица состояний инвертора

Логическое уравнение работы инвертора:

Уравнение читается: У равняется не Х.

С точки зрения физической реализации наибольшее распространение получили инверторы на транзисторах.

Функцию НЕ реализует, например, размыкающий контакт реле. При срабатывании реле цепь, в которую входит этот контакт, будет размыкаться.

2.4 Элемент Шеффера (элемент И-НЕ)

Элемент Шеффера - реализует операцию логическое умножение с отрицанием. На выходе сигнал "1" имеет место всегда, кроме случая, когда сигналы "1" на всех входах совпадают (рис. 2.6).

Рис. 2.6 Условное изображение элемента Шеффера на функциональных схемах: х₁, х₂, х_n - входы (минимальное число входов - два); y - выход.

Логика работы элемента Шеффера на три входа представлена табл.2.4

Таблица 2.4

Таблица состояний элемента Шеффера

Логическое уравнение работы элемента Шеффера:

Уравнение позволяет представить логическую схему элемента Шеффера в виде(рис.2.7).

Рис. 2.7 Представление логической схемы элемента Шеффера в виде последовательного соединения конъюнктора и инвертора.

2.5 Элемент Пирса (элемент ИЛИ-НЕ)

Элемент Пирса - реализует операцию логическое сложение с отрицанием. На выходе сигнал "1" имеет место только в случае, если на всех входах одновременно будет сигнал "0" (рис.2.8).

Логика работы элемента Пирса на три входа представлена табл.2.5

Таблица 2.5

Таблица состояний элемента Пирса

Логическое уравнение работы элемента Пирса:

Поэтому логическую схему элемента Пирса можно представить рис.2.8

Рис. 2.8 Представление логической схемы элемента Пирса в виде последовательного соединения дизъюнктора и инвертора.

2.6 Функциональная полнота элементов Шеффера (И-НЕ) и Пирса (ИЛИ-НЕ)

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

а) Функция НЕ:

б) Функция И:

в) Функция ИЛИ:

То же сделаем для элемента Пирса (рис.2.10).

а) Функция НЕ:

б) Функция И:

в) Функция ИЛИ:

Рис. 2.10 Способы построения на основе элемента Пирса логических цепей И, ИЛИ, НЕ.

3. Взаимное соответствие логической функции и логической схемы

По заданной логической функции f(х₁, х₂, х₃,...,х_n) можно составить электрическую схему, которая будет преобразовывать логические сигналы х₁, х₂, х₃,...,х_n согласно указанной функции.

Различают схемы:

1. структурные;

2. функциональные;

3. принципиальные (полные).

Структурная схема определяет основные функциональные части, их назначение и взаимосвязи. Структурная схема концентрирует в себе все наиболее важное и существенное о составе, структуре и функциях электронного устройства (ЭУ). Электронным устройством называют любую совокупность взаимодействующих электрорадиоэлементов, предназначенную для выполнения заданной функции.

Функциональная схема разъясняет процессы, протекающие в отдельных цепях или в целом ЭУ. Она занимает промежуточное место между структурной и принципиальной схемами. Цепи, в которых хотят разъяснить процессы, показывают так же подробно, как и на принципиальной схеме, а другие функциональные части изображают в виде прямоугольников, как и на структурной схеме.

Принципиальная (полная) схема определяет полный состав элементов и связей между ними и дает детальное представление о принципах работы ЭУ.

Существуют два уровня, на которых разрабатывают указанные три вида схем:

1. микроуровень;

2. макроуровень.

На микроуровне разрабатывают схемы для интегральных микросхем (ИМС). Эти схемы создают разработчики ИМС, они входят в состав документации на ИМС и приводятся в справочниках и технической литературе.

К структурным схемам цифровых ИМС относят схемы, на которых представлены ее части, более крупные, чем функциональные элементы. Функциональный элемент - наименьшая единица функциональной структуры, которая при технической реализации может быть выполнена в виде электрической законченной схемы, выполняющей определенную функцию. Структурные схемы разрабатывают для больших (БИС) и сверхбольших (СБИС) интегральных схем. На этом уровне интеграции разработка функциональных схем для использования лишена смысла ввиду их сложности. О правильности функционирования БИС и СБИС судят по значениям логических сигналов на их выходах при тестировании.

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

Функции, выполняемые логическими элементами и триггерами, могут быть определены по их условным графическим обозначениям. К функциональным относятся такие схемы, на которых одна из нескольких одинаковых частей показана на уровне логических элементов (и триггеров), и остальные - в виде более крупных структур.

Структурная и функциональная схемы не дают представления о физических процессах в логических элементах. Эти представления для каждой серии ИМС дают принципиальные схемы их базовых логических элементов.

На схемах логические элементы по ГОСТ 2.743-82 "Обозначения условные графические в схемах. Элементы цифровой техники" изображают прямоугольником, в верхней части которого указывают символ функции: & для И; 1 для ИЛИ. Инверторные входы и выходы выделяются кружком у вывода. Выводы питания и общий не показывают.

Рассмотрим порядок составления функциональной схемы (рис.3.1) по заданной логической функции, например,

1-й этап - получить отрицание от переменных х₁, х₂, х₃.

2-й этап - получить дизъюнкцию , конъюнкции и .

3-й этап - получить конъюнкцию х₁().

4-й этап - получить заданную логическую функцию.

Рис. 3.1 Функциональная схема.

Проектирование функциональных схем сводится к последовательным формальным процедурам, которые могут быть реализованы на ЭВМ. Способ соединения логических элементов функциональной схемы определяется последовательностью выполнения логических операций в заданной логической функции. Последовательность выполнения этих операций удобно разбить на ряд этапов. В каждый этап включают те операции, которые можно проводить в произвольной последовательности.

Пример 3.1. Синтезировать в базисе И, ИЛИ, НЕ и в базисе И-НЕ, ИЛИ-НЕ устройство, сигнал на выходе которого равен 1 только в том случае, когда на его двух входах (х₁ и х₂) действуют различные сигналы (узел неравнозначности, сумматор по модулю два).

Решение: 1. Таблица истинности в соответствии со словесным описанием работы устройства:

2.Для перехода от табличного представления функции к алгебраическому в формах СДНФ и СКНФ каждому набору переменных ставятся в соответствие минтермы (m_i) и макстермы (M_i):

3. СДНФ функции:

,

где q=2ⁿ, n - число переменных.

4. СКНФ функции:

.

Применив правило Де Моргана:, получим:

4. Функциональная схема для функции, представленной в СДНФ, в базисе И, ИЛИ, НЕ (рис.3.2).




Рис. 3.2 Функциональная схема устройства в базисе И, ИЛИ, НЕ

6. Функциональная схема для функции, представленной в СКНФ, в базисе И, ИЛИ, НЕ (рис.3.3).




Рис. 3.3 Функциональная схема устройства в базисе И, ИЛИ, НЕ

7. Для использования базиса И-НЕ, ИЛИ-НЕ преобразовывают далее полученные логические функции. Применяют закон двойной инверсии:





В соответствии с законами Де Моргана (инверсии; принципа дуальности, двойственности):

;

.

8. Функциональная схема для реализации функции f₁ (рис.3.4).



Рис.3.4 Функциональная схема для реализации функции f₁

9. Функциональная схема для реализации функции f₂ (рис.3.5).



Рис.3.5 Функциональная схема для реализации функции f₂

Пример 3.2. Синтезировать в базисе И, ИЛИ, НЕ и в базисе И-НЕ, ИЛИ-НЕ устройство, сигнал на выходе которого равен 1, только в том случае, когда на его двух входах (х₁, х₂) действуют одинаковые сигналы (узел равнозначности).

Решение. 1. Таблица истинности в соответствии со словесным описанием работы устройства:

х1	х2	f
0	0	1
0	1	0
1	0	0
1	1	1

2. Определяют минтермы m_i и макстермы M_i:

х1	х2	mi	Mi	f
0	0			1
0	1			0
1	0			0
1	1			1

3. СДНФ функции:

.

Применив закон Де Моргана, получают:

.

4. СКНФ функции:

.

В соответствии с законом Де Моргана:

.

5. Функциональная схема для f₁ (рис.3.6).



Рис.3.6 Функциональная схема для f₁

6. Функциональная схема для (рис.3.7).



Рис. 3.7 Функциональная схема для

7. Функциональная схема для f₂ (рис.3.8).



Рис. 3.8 Функциональная схема для f₂

8. Функциональная схема для (рис.3.9).



Рис.3.9 Функциональная схема для

Все четыре функциональные схемы логически равноценны.

Пример 3.3. Устройство с четырьмя входами должно работать так, чтобы на выходе появился сигнал 1, когда не менее чем на трех входах будут одновременно сигналы 1. Синтезировать устройство на элементах И, ИЛИ, НЕ.

Решение. 1. Таблица истинности в соответствии со словесным описанием работы устройства:

Таблица 3.1

Таблица истинности

Номер набора	х1	х2	х3	х4	f
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	0
6	0	1	1	0	0
7	0	1	1	1	1
8	1	0	0	0	0
9	1	0	0	1	0
10	1	0	1	0	0
11	1	0	1	1	1
12	1	1	0	0	0
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	1

2. Запишем СДНФ функции на основе ее единичных наборов:

.

3.Для минимизации функции применим карту Карно (рис.3.10).

х1х2 х3х4	00	01	11	10
00	0	0	0	0
01	0	0	1	0
11	0	1	1	1
10	0	0

1

0

Рис. 3.10 Карта Карно

4. МНДФ функции:

.

5. Функциональная схема устройства (рис.3.11).



Рис.3.11 Функциональная схема устройства

Пример 3.4. Синтезировать мажоритарный элемент на три входа в базисе ИЛИ-НЕ. У такого элемента значение выходного сигнала совпадает с значением большинства входных.

Решение. 1. Таблица истинности в соответствии со словесным описанием работы элемента:

x1	x2	х3	у
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

2. СДНФ функции на основе ее единичных наборов:

.

3. Для минимизации функции применим карту Карно (рис.3.12).

х1х2 х3	00	01	11	10
0	0	0	1	0
1	0	1	1	1

Рис.3.12 Карта Карно

4. МДНФ функции:

.

5. МКНФ функции:

.

6. Для реализации функции в базисе И-НЕ и в базисе ИЛИ-НЕ преобразуем функцию в соответствии с законом Де Моргана:

; .

7. Функциональная схема для функции f₁ в базисе И-НЕ (рис.3.13).



Рис.3.13 Функциональная схема для функции f₁ в базисе И-НЕ

8. Функциональная схема для функции f₂ в базисе ИЛИ-НЕ (рис.3.14).



Рис.3.14 Функциональная схема для функции f₂ в базисе ИЛИ-НЕ

4. Особенности синтеза схем с запрещенными комбинациями

Иногда применяют устройства, закон функционирования которых определен неполностью. В таких устройствах некоторые комбинации сигналов на входы никогда не подаются (запрещены).

Работа устройств с запрещенными комбинациями входных сигналов описывается неполностью определенными логическими функциями, значения которых определены не на всех наборах аргументов.

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

Обычно логической функции на запрещенных наборах придают такие значения, при которых она приобретает наиболее простой вид.

При минимизации логической функции безразличные наборы входных переменных в соответствующих клетках карты Карно обозначают знаком Х. В объединения включают те клетки, отмеченные Х, которые дают расширение объединений и уменьшение их количества.

5. Типовые комбинационные схемы

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

Поэтому не может быть речи о синтезе комбинационных схем только в базисах И, ИЛИ, НЕ, или ИЛИ-НЕ, а также И-НЕ, а следует наиболее полно использовать функциональные возможности всех логических элементов.

Для успешного синтеза цифровых узлов следует знать функционирование типовых комбинационных схем, выпускаемых промышленностью в виде интегральных микросхем, и которые синтезированы, как правило, в логических базисах И, ИЛИ, НЕ, или ИЛИ-НЕ, а также И-НЕ.

5.1 Мультиплексоры

Мультиплексор (коммутатор) - комбинационное многовходовое устройство с одним выходом.

Входы подразделяются на:

1. информационные х₁, х₂, х₃,..., х_n;

2. управляющие (адресные) v₁, v₂, v₃,..., v_m;

где n - число информационных входов,

m - число управляющих (адресных) входов.

Обычно n=2^m.

Код (адрес), поступающий на управляющие входы, определяет один из информационных входов, значение переменной которого передается на выход у.

Адреса представляют в двоичном коде и им присваивают номер j. Каждому адресу с номером j соответствует свой информационный вход x_j, сигнал с которого при данном адресе проходит на выход.

Основным назначением мультиплексора является коммутация n=2^m входных сигналов на один выход.

В соответствии с назначением составим таблицу истинности для мультиплексора, содержащего, например, четыре информационных входа: х₁, х₂, х₃, х₄, которые могут коммутироваться двумя управляющими (адресными) входами (табл.5.1).

Таблица 5.1

Таблица истинности мультиплексора

Адресные переменные		Информационные Переменные				Выход у
v1	v2	x1	x2	x3	X4	y
0	0	1				1
0	1		1			1
1	0			1		1
1	1				1	1
0	0	0				0
0	1		0			0
1	0			0		0
1	1				0	0

Незаполненные клетки соответствуют значениям информационных переменных, не влияющих на значение выходного сигнала у. Так как каждому адресу соответствует свой информационный вход, то таблицу истинности можно представить в виде (табл.5.2).

Таблица 5.2

Преобразованная таблица истинности мультиплексора

Адресные переменные		Информационные переменные				Выход у
v1	v2	x1	x2	x3	x4	y
0	0	х1				х1
0	1		х2			х2
1	0			х3		х3
1	1				х4	х4

Работа мультиплексора описывается при этом логической функцией:

,

а его функциональная схема дана на (рис.5.1).



Рис. 5.1. Функциональная схема мультиплексора.

Функция, реализуемая мультиплексором, в общем виде может быть представлена в виде СДНФ:

.

5.2 Синтез комбинационных схем на мультиплексорах

Кроме основного назначения (коммутация сигналов) мультиплексоры используют для построения постоянных запоминающих устройств (ПЗУ) объемом 2^m+1 бит и для синтеза комбинационных логических схем. При этом можно синтезировать различных логических функций от (m+1) логических переменных. Например, на мультиплексоре с n=4 и m=2 входами реализуется любая логическая функция от трех переменных, т.к. для трех переменных существует различных функций.

При построении ПЗУ на информационные входы мультиплексора подают не изменяющиеся во времени сигналы 0 и 1. Считывание данных сигналов производится подачей соответствующих сигналов на адресные (управляющие) входы.

В этом случае мультиплексор реализует некоторую наперед заданную функцию, представленную в совершенной дизъюктивной нормальной форме (СДНФ), как следует из представленной выше логической функции мультиплексора.

Основной задачей при синтезе комбинационных логических схем на мультиплексорах является оптимальный выбор переменных, подаваемых на его управляющие (адресные) входы.

Критерием оптимальности выбора адресных переменных может служить количество сигналов 0 и 1, подаваемых при этом на информационные входы.

Правило выбора адресных переменных рассмотрим для двух случаев.

Пусть логическая функция задана табл.5.3

Таблица 5.3

Таблица истинности

х1	х2	х3	f
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Выделим из логических переменных переменную х₃. Одинаковые комбинации оставшихся переменных х₁ х₂ представим в виде групп (отделены в таблице истинности двойными горизонтальными линиями).

Выберем в качестве адресных (управляющих) переменных переменные х₁ и х₂. При коде v₁v₂=x₁x₂=00 на выход мультиплексора коммутируется вход Х₁. Если на вход Х₁ подать переменную х₃, то на выходе получим значение логической функции при х₁х₂=00. Это удобно отразить в табл.5.4

Таблица 5.4

Таблица истинности

Адресные переменные		Информационные переменные				Выход
v1 x1	v2 x2	X1	X2	X3	X4	f
0	0	x3				x3
0	1
1	0			0		0
1	1				1	1

При коде v₁v₂=x₁x₂=01 на выход коммутируется вход Х₂. В соответствии с таблицей истинности логической функции, на этот вход следует подать .

При коде v₁v₂=x₁x₂=10 на выход коммутируется вход x₃. В соответствии с таблицей истинности логической функции, на этот вход следует подать "0".

При коде v₁v₂=x₁x₂=11 на выход коммутируется вход x₄. В соответствии с таблицей истинности логической функции, на этот вход следует подать "1" (рис. 5.2).




Рис. 5.2 Пример синтеза комбинационной схемы на мультиплексоре.

На мультиплексорах можно реализовывать совместно две функции. При этом отыскивают те переменные, которые суммарно входят в МДНФ функций наибольшее число раз. Например, заданы МДНФ двух функций:



.

Таблица истинности для них выглядит следующим образом:

x1	x2	x3	x4	f1	f2
0