Учебное пособие к практическим занятиям по ТДУ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА

КРАСНОЯРСКИЙ ИНСТИТУТ ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА –

ФИЛИАЛ ГОСУДАРСТВЕННОГО ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ИРКУТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ» в г. КРАСНОЯРСКЕ











СБОРНИК ЗАДАЧ ПО АЛГЕБРЕ ЛОГИКИ

УЧЕБНОЕ ПОСОБИЕ
к практическим занятиям
по курсу «Теория дискретных устройств»

(рукопись)

















Красноярск 2014
УДК 62.50

Туйгунова А.Г., Худоногов И.А. Сборник задач по алгебре логики: Учебное пособие к практическим занятиям по курсу «Теория дискретных устройств». – Красноярск: КрИЖТ ИрГУПС, 2014. – 49 с.

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

Ил. 26. Табл. 16. Библиогр. 8 назв.


Авторы: А.Г. Туйгунова, канд. техн. наук, доцент кафедры «Транспортные системы» КрИЖТ ИрГУПС;
И.А. Худоногов, д-р техн. наук, профессор кафедры «Электроснабжение железнодорожного транспорта» ИрГУПС














ОГЛАВЛЕНИЕ 13 TOC \o "1-3" \u 14
ВВЕДЕНИЕ 13 PAGEREF _Toc315351276 \h 14415
1. СПОСОБЫ ЗАДАНИЯ ФУКЦИИ АЛГЕБРЫ ЛОГИКИ 13 PAGEREF _Toc315351277 \h 14515
2. МИНИМИЗАЦИя ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ 13 PAGEREF _Toc315351278 \h 141215
3. Преобразование логических функций 13 PAGEREF _Toc315351279 \h 142615
4. ПРЕДСТАВЛЕНИЕ ФАЛ В РАЗЛИЧНЫХ БАЗИСАХ 13 PAGEREF _Toc315351280 \h 142715
5. Реализация ФАЛ на контактных и бесконтактных элементах 13 PAGEREF _Toc315351281 \h 142815
6. СИНТЕЗ КОМБИНАЦИОННЫХ СХЕМ 13 PAGEREF _Toc315351282 \h 143515
6.1. Синтез комбинационных схем с несколькими выходами 13 PAGEREF _Toc315351283 \h 143515
6.2. Синтез специальных комбинационных схем 13 PAGEREF _Toc315351284 \h 144015
Задания для самостоятельной работы 13 PAGEREF _Toc315351285 \h 144415
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 13 PAGEREF _Toc315351286 \h 144915
15 Введение
Сборник задач рассматривается как учебное пособие для упражнений и практических знаний по разделу «Теория дискретных устройств» соответствующей программы учебной дисциплины.
Сборник задач состоит из семи разделов. Первый раздел позволяет закрепить знания по способам задания и основным законам функций алгебры логики (ФАЛ). Задачи минимизации полностью определенных логических выражений ФАЛ приведены во втором разделе. Третий раздел посвящен преобразованию и упрощению булевых выражений. В четвертом разделе показано представление ФАЛ в различных базисах. Способ реализации ФАЛ на релейно-контактных схемах приведен в пятом разделе. В шестом разделе показан синтез комбинационных схем с несколькими выходами. В седьмом разделе приведены примеры для самостоятельного углубления знаний студентами в теории булевых функций. Решение задач позволит студенту освоить методику формализации содержательной постановки задачи в виде булевого уравнения, логической диаграммы или релейно-контактной схемы и овладеть приемами решения задач.
СПОСОБЫ ЗАДАНИЯ ФУКЦИИ АЛГЕБРЫ ЛОГИКИ
Методы анализа и синтеза всех классов дискретных автоматов строят на базе алгебры логики. Алгебра логики ( это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними. Начало алгебры логики было положено ирландским математиком Д.Булем (1815(1864).
Функцию f (х1, х2, ..., хп) называют функцией алгебры логики (ФАЛ), если она, как и ее переменные (аргументы), может принимать только два значения: логического 0 и логической 1. Переменные ФАЛ сопоставляют со значениями сигналов на входах дискретного автомата, а значения функции алгебры логики ( со значениями сигналов на его выходах.
Реальные дискретные автоматы имеют конечное число входов, следовательно, число переменных у соответствующих ФАЛ также конечно. Так как переменные ФАЛ могут принимать только два значения, область определения любой ФАЛ конечна.
Базисом называют полную систему функций алгебры логики. Минимальный базис состоит из такого набора функций, исключение из которого любой функции превращает этот набор в неполную систему функций. Наиболее удобным для представления в виде логического выражения функций алгебры логики является базис, содержащий конъюнкцию, дизъюнкцию и инверсию (И, ИЛИ, НЕ). Этот базис называют основным. Минимальный базис включает в себя две функции: И, НЕ или ИЛИ, НЕ, однако использование трех функций упрощает логическое описание, а в ряде случаев и построение дискретных устройств железнодорожной автоматики, телемеханики и связи.
Для начального представления функций обычно применяют основной базис И, ИЛИ, НЕ независимо от того, какой базис будет использован для построения дискретного устройства.
Решение вопросов анализа и синтеза схем дискретных устройств железнодорожной автоматики, телемеханики и связи связано с преобразованием выражений, которые содержат ФАЛ основного базиса. Запись, содержащая двоичные переменные, соединенные знаками логического сложения, умножения и инверсии, называют логическим выражением. Такое выражение однозначно определяет комбинационное устройство, построенное на элементах И, ИЛИ, НЕ.
При табличном способе ФАЛ задают таблицей ее значений в зависимости от значений переменных. Таблицу, в которой для всех наборов переменных приводятся значения ФАЛ, называют таблицей истинности. Например, в таблице 1 заданы две ФАЛ трех переменных: f (x1, х2, ..., хn) и
· (х1, x2, ..., хn).

Таблица 1
Номер
x1
х2
х 3
f

·

0
0
0
0
0
1

1
0
0
1
1
0

2
0
1
0
0
0

3
0
1
1
1
0

4
1
0
0
0
1

5
1
0
1
0
0

6
1
1
0
0
1

7
1
1
1
1
1


Совокупность значений переменных называют набором (точкой). Каждому набору переменных соответствует определенное значение функции. Если ФАЛ содержит п переменных, двоичные числа будут разрядные и, следовательно, общее число наборов определяется по формуле k = 2п. При трех аргументах можно образовать восемь наборов. Следовательно, приведенные в табл. 1 функции f (x1, х2, ..., хп) и
· (х1, x2, ..., хп) определены на восьми наборах. При этом каждый набор представляет собой трехразрядное двоичное число.
При каждом наборе переменных возможны два значения ФАЛ: логического 0 или 1. Поэтому в соответствие каждой ФАЛ можно поставить k-разрядное двоичное число. Значит, число функций алгебры логики п аргументов определяется формулой 2k. При п переменных таблица содержит 2п строк (по числу наборов), п столбцов (по числу переменных) и один столбец значений функции, соответствующих каждому набору (сочетанию) аргументов.
При графическом способе наборам значений переменных ФАЛ сопоставляются точки п-мерного пространства. Множество 2п наборов определяет множество вершин п-мерного единичного куба. Вершинам куба соответствуют наборы значений переменных и приписаны значения функции на этих наборах, т.е. областью определения ФАЛ, зависящей от п переменных, является множество вершин единичного п-мерного куба. Куб называют единичным, так как каждое его ребро соединяет вершины, наборы которых различаются одной переменной. Функции f (x1, х2, ..., хп) и
· (х1, x2, ..., хп) ( заданные таблицей истинности (см. табл. 1), можно задать графически (рис. 1).
При координатном способе функцию задают в виде координатной карты состояний, которую называют картой Карно. Карты представляют собой прямоугольные таблицы, разделенные горизонтальными и вертикальными линиями на клетки. Общее число клеток соответствует числу наборов функции. Все переменные функции разбивают на две группы, Одна группа переменных определяет выбор строки, другая ( столбца. На пересечении строки и столбца находится клетка, в которую записывают значение функции при соответствующем наборе переменных. Аргументы разделяются на группы так, чтобы в соседних клетках наборы различались только значением одной переменной. Карты Карно для двух, трех и четырех и пяти переменных приведены соответственно на рис. 2,а, б, в, г. В каждую из клеток карты Карно трех переменных вписаны значения функции f (x1, х2, ..., хп) заданной таблицей истинности (см. табл. 1). На рис. 3 в скобках в каждой из клеток карты Карно проставлены десятичные номера соответствующих наборов.

13 EMBED Visio.Drawing.11 1415

Рисунок 1 ( Графическое задание ФАЛ

При числовом способе каждому набору переменных ставят в соответствие определенное число в двоичной системе исчисления и присваивают соответствующий номер. Переменным x1, х2, ..., хп приписывают соответственно веса 213 EMBED Equation.3 1415,213 EMBED Equation.3 1415,,213 EMBED Equation.3 1415,213 EMBED Equation.3 1415. Функцию задают в виде десятичных номеров тех наборов переменных, на которых она принимает значение 1. Поскольку номер внутреннего состояния зависит от присвоенных переменным весов условимся записывать эти переменные в порядке уменьшения весов. Такую запись называют базой системы нумерации. Так, например, если имеются три переменные x1, х2, х3, причем переменной x1 присвоен вес 22, переменной х2 – 21, а переменной х3 ( 20, то база системы нумерации будет x1, х2, х3.
В тех случаях, когда при некоторых наборах аргументов значения функции «безразличны» (не определены), при задании ФАЛ табличным, координатным и графическим способами на таком наборе проставляются знаки «~» или «Ш» (рис. 4).
13 EMBED Visio.Drawing.11 1415
13 EMBED Visio.Drawing.11 1415

13 EMBED Visio.Drawing.11 1415


13 EMBED Visio.Drawing.11 1415


Рисунок 2 ( Координатный способ задания ФАЛ:
а) для двух аргументов; б) для трех аргументов;
в, г) для четырех аргументов
13 EMBED Visio.Drawing.11 1415



Рисунок 3 ( Задание ФАЛ трех переменных координатным способом


13 EMBED Visio.Drawing.11 1415
Рисунок 4 ( Табличное задание не полностью определенной функции

При числовом способе задания не полностью определенной функции указываются множества наборов, при которых ФАЛ принимает значения 1 (обязательные номера), и наборов, при которых функция равна 0 (запрещенные номера) или ее значения безразличны (условные номера):

13 EMBED Equation.3 141513 EMBED Equation.3 1415.
или
13 EMBED Equation.3 1415

Функции f (x1, х2, ..., хп) и
· (х1, x2, ..., хп), приведенные в табл.1, могут быть заданы числовым способом:

13 EMBED Equation.3 1415; 13 EMBED Equation.3 1415.

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


Таблица 2 ( Перечень логических операций, используемых при записи логических выражений
Обозначение логических операций
Таблица
истинности
Как
читается
Название
операции


Х1

0

0

1

1




Х2

0

1

0

1



Х1 Х2
Х1
· Х2
Х1 & Х2

0

0

0

1

Х1 и Х2
Конъюнкция;
логическое И ;
логическое произведение

Х1
· Х2
Х1 + Х2


0

1

1

1

Х1 или Х2
Дизъюнкция;
логическое ИЛИ;
логическая сумма

Х113 EMBED Equation.3 1415Х2
13 EMBED Equation.3 1415 + Х2
Х1 Х2


1

1

0

1

Если Х1, то Х2;
Х1 влечет Х2;
Х1 имплицирует Х2

Импликация

Х1~Х2
Х1
·Х2
Х1Х2


1

0

0

0

Х1 эквивалентно Х2
Эквивалентность;
функция равнозначности


Х113 EMBED PBrush 1415Х2


0

1

1

0

или Х1 или Х2;
Х1 неэквивалентно Х2

Функция неэквивалентности;
функция неравнозначности;
исключающее ИЛИ;
сумма по модулю 2

Х1
·Х2
Х113 EMBED Equation.3 14Х215 Х1Х2


0

0

1

0

Х1 запрет по Х2;
Х1, но не Х2
Запрет;
отрицание импликации


Х1
· Х2

1

1

1

0

Х1 и Х2 не совместны
Штрих-Шеффера;
логическое И-НЕ;
отрицание конъюнкции


Х1 Х2

1

0

0

0

не Х1 не Х2
Стрелка Пирса;
логическое И-НЕ;
отрицание дизъюнкции

13 EMBED Equation.3 1415 13 EMBED PBrush 1415 13 EMBED Equation.3 1415
Х
1
0

не Х
Инверсия;
логическое отрицание;
логическое НЕ


У
0
1





Алгебраическое выражение может быть составлено из наборов аргументов, на которых функция принимает значение 1, или из наборов аргументов, на которых она принимает значение 0.
Например, можно записать ФАЛ трех аргументов в виде:

f = (13 EMBED Equation.3 1415)

ИЛИ

f = 13 EMBED Equation.3 1415
Задание: напишите аналитические выражения для функций f (x1, х2, ..., хп) и
· (х1, x2, ..., хп), заданных таблицей истинности (см. табл. 1).
В системах железнодорожной автоматики, телемеханики и связи могут применяться дискретные устройства, закон функционирования которых определен не полностью. В таких устройствах некоторые комбинации сигналов на входы никогда не подаются. Эти комбинации входных сигналов называют неиспользуемыми. Для неиспользуемых входных комбинаций выходные сигналы не определены.
Если значение ФАЛ определено на всех возможных наборах значений ее переменных, то ее называют полностью определенной. В случае числового задания не полностью определенной функции номера неиспользуемых наборов заключают в скобки:

13 EMBED Equation.3 1415.

В булевой алгебре действуют следующие законы:
переместительный (коммутативный):

13 EMBED Equation.3 1415 и13 EMBED Equation.3 1415;

сочетательный (ассоциативный):

13 EMBED Equation.3 1415 и13 EMBED Equation.3 1415;

распределительный (дистрибутивный):

13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415.
нулевого множества:

13 EMBED Equation.3 1415;

единичного множества:

13 EMBED Equation.3 1415;
логического нуля:
13 EMBED Equation.3 1415;

логической единицы:

13 EMBED Equation.3 1415;

повторения:

13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415;

двойного отрицания:

13 EMBED Equation.3 1415;


склеивания:

13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415;

поглощения:

13 EMBED Equation.3 1415;

инверсии, правило де Моргана:

13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415.


МИНИМИЗАЦИя ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ
Методы минимизации основываются на законах алгебры логики, позволяющих осуществлять преобразования алгебраических выражений (формул) с целью получения упрощенных минимальных форм функций.
Важным этапом синтеза сложных дискретных устройств железнодорожной автоматики, телемеханики и связи является определение способа соединения между собой логических элементов, обеспечивающих работу устройства телемеханики в соответствии с заданным законом функционирования. На этом этапе требуется представить функцию алгебры логики устройства через функции выбранной полной системы (базиса).
Важной задачей является упрощение выражений для ФАЛ с целью получения такого вида формулы, при котором построенный в соответствии с ней автомат отличался бы минимальным расходом логических элементов на его изготовление.
Любая функция алгебры логики выражается через исходные функции неоднозначно. Поэтому требуется найти такую форму ее представления, которая позволяет построить наиболее простую электрическую схему для синтеза более сложных функциональных импульсных устройств, составляющих систему телемеханики. При решении этой задачи заданную функцию алгебры логики дискретного устройства вначале оказывается удобным представить в некоторой исходной канонической форме, которую называют нормальной, а затем преобразовать ее так, чтобы она соответствовала наиболее простой электрической схеме с учетом выбранного базиса логических элементов.
Каноническими формами представления функций алгебры логики являются совершенная дизъюнктивная нормальная форма (СДНФ) и совершенная конъюнктивная нормальная форма (СКНФ).
Совершенная дизъюнктивная нормальная форма ФАЛ представляет собой дизъюнкцию специально вводимых вспомогательных функций ( конституент единицы (минтермов), которые равны 1 на тех же наборах, что и заданная функция. СДНФ представляет собой алгебраическое выражение, которое принимает значение, равное 1 на тех наборах переменных, на которых значение заданной функции равно 1. Конституентой единицы называют функцию, которая принимает значение 1 на одном из всех возможных наборов переменных. В табл.1 приведены функций f (x1, х2, х3) и
· (х1, x2, х3) трех аргументов. Среди них имеется конституенты единицы: наборы 1, 3, 7 для функции f (x1, х2, х3) и наборы 0, 4, 6, 7 для
· (х1, x2, х3). Количество конституент единицы заданного числа переменных п, как следует из определения, совпадает с числом различных наборов К=2п. Для составления алгебраического выражения, принимающего значение, равное 1, на всех наборах, на которых функция равна 1, следует взять дизъюнкцию конституент, соответствующих этим наборам;
Дизъюнктивной нормальной формой (ДНФ) называется такая форма представления функции, когда она выражается дизъюнкцией простых конъюнкций аргументов или их инверсий:

13 EMBED Equation.3 1415.

Если в каждой конъюнкции ДНФ присутствуют все аргументы функции, то такая форма носит название СДНФ:

13 EMBED Equation.3 1415.

Для перехода от ДНФ к СДНФ необходимо в каждой из ее членов путем умножения их на выражения вида 13 EMBED Equation.3 1415ввести недостающие аргументы:

13 EMBED Equation.3 1415.

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

13 EMBED Equation.3 1415.

Если каждый член КНФ содержит все аргументы, то такая форма будет совершенной конъюнктивной нормальной формой

13 EMBED Equation.3 1415.

Для перехода от КНФ к СКНФ необходимо к каждому члену КНФ прибавить выражение вида 13 EMBED Equation.3 1415где хi ( недостающий аргумент:

13 EMBED Equation.3 1415

Для получения СКНФ из таблицы истинности необходимо представить в виде инверсий наборы аргументов, при которых функция принимает значения 0, и соединить их знаками конъюнкции.
По каноническим формам (СДНФ и СКНФ) могут быть непосредственно построены логические устройства, однако, как правило, в этих случаях схемы содержат большое количество элементов и прежде, чем составлять логические схемы, производят упрощение (минимизацию) функций.
Наиболее детально разработаны методы решения канонической задачи минимизации ФАЛ, которая заключается в нахождении формы функции, содержащей минимальное число вхождений переменных. Такие формы называют минимальными.
Под минимизацией понимают процесс нахождения такого эквивалентного выражения логической функции, которое содержит минимальное число вхождений переменных. Хотя в общем случае под минимизацией может иметься в виду получение выражений с минимальным числом инверсных переменных либо с минимальным числом вхождений какой-либо одной переменной. Большинство методов минимизации ориентированы на получение минимальных ДНФ (минимальных КНФ), однако доказано, что минимальное выражение в классе ДНФ будет также минимальным, либо отличаться от минимального на одно вхождение переменной в классе других форм функции.
Исходными формами функции при решении канонической задачи минимизации являются ее СДНФ и СКНФ. Если функция задана в другой форме, последнюю преобразуют в СДНФ или СКНФ. как это было показано ранее. Рассмотрим минимизацию функций, заданных в дизъюнктивной нормальной форме.
Минимальной ДНФ (МДНФ) называют такую запись функции, которая содержит самое минимальное число переменных по сравнению со всеми другими ДНФ, эквивалентными данной функции. Существуют различные методы минимизации ФАЛ. Все они основаны на попарном склеивании соседних конституент, отличающихся значениями только одной переменной, применяя закон склеивания. В одну конституенту переменная входит в прямой форме, в другую ( в инверсной. Две соседние конституенты склеиваются по различающейся переменной, что приводит к замене их одной конъюнкцией с числом переменных, на единицу меньшим, чем в исходных конституентах.
Конъюнкции, получаемые в результате склеивания двух соседних конституент, называют импликантами. Различные импликанты с одинаковым числом переменных в свою очередь могут оказаться соседними, что позволяет склеивать их между собой. Процесс многоступенчатого склеивании приводит к получению импликант, которые не склеиваются с другими. Такие импликанты называются простыми.
Импликанта, полученная в результате склеивания некоторого множества конституент покрывает (поглощает) эти конституенты. Так, импликанта может покрывать несколько исходных конституент, каждая из которых содержит, например, четыре переменные.
Наиболее эффективна минимизация булевых функций с помощью карт Карно. До сих пор существует ошибочное мнение, что этим методом можно решать задачи для функций от не более, чем 6 аргументов. На самом деле карты Карно могут применяться для функций даже от 8-12 переменных. Этот метод минимизации функции производится посредством таблицы, которая называется картой Карно. Карта Карно – это таблица, содержащая 2n ячеек. Количество клеток в карте Карно равно количеству строк в таблице истинности. Каждая клетка соответствует одной строке таблицы. Комбинации входных переменных распределяются по двум сторонам прямоугольника, а соответствующие значения функции в клетках таблицы, находящихся на пересечении строк и столбцов, соответствующих выбранным состояниям переменных. Каждой ячейке соответствует определенный набор переменных и указывается какое значение на этом наборе принимает функция. Причем соседние ячейки отличаются значением только одной переменной, что позволяет минимизировать ДНФ, используя закон склеивания. Метод Карно основан на законе склеивания. Склеиваются наборы, отличающиеся друг от друга лишь значением одного разряда. Такие наборы называются соседними, и они соответствуют соседним клеткам карты Карно. Формируются такие наборы (коды Грея) по принципу симметрии), объединяя ячейки по 2n в прямоугольники, которые называются контурами. Соседними являются крайние верхние и крайние слева и справа. Необходимо стремиться к тому, чтобы контуры содержали как можно больше ячеек. А количество контуров должно быть минимально возможным. При создании контуров одну и туже ячейку (конъюнкцию) можно включать в несколько контуров в соответствии закона идемпотентности (повторное действие над объектом не изменяет его). Каждому контуру соответствует конъюнкция. При соединении двух ячеек исключается одна переменная, четырех – две, восьми – три и т.д. При объединении ячеек исключаются, согласно закона склеивания, переменные, которые входят в конъюнкции с разными значениями.
Упрощение выражений булевых функций (минимизация) основывается на понятии несущественности переменных. Переменная называется несущественной на паре наборов, если при изменении ее значения на противоположное булева функция сохраняет свое значение. Например, для булевой функции трех переменных:

13 EMBED Equation.3 1415
по дистрибутивному закону:

13 EMBED Equation.3 1415.

Таким образом, две конъюнкции, содержащие несущественную переменную, заменяются одной, в которой несущественная переменная отсутствует.
Приведем основные определения, используемые при минимизации булевых функций. Данные определения используют понятия нормальных (канонических) форм булевых функций.
Число переменных, входящих в элементарную конъюнкцию (для ДНФ) или в элементарную дизъюнкцию (для КНФ) называется ее рангом.
В основе любых методов минимизации лежит операция склеивания. Два элементарных произведения одного ранга (для ДНФ) или элементарных сумм одного ранга (для КНФ) склеиваются, если они различаются только по одной переменной.
Операция, показанная выражениями  13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 называется полным склеиванием, а операция, выраженная в следующем виде:

13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415,

называется неполным склеиванием (для ДНФ).
Импликантой ( называется элементарное произведение, равное 1 на одном или нескольких наборах, где данная функция равна 1, и равное 0 на всех наборах, где данная функция равна 0. Импликанта покрывает один или несколько минтермов рассматриваемой булевой функции. Обычно, импликанта ( это результат склеивания соответствующих минтермов или импликант.
Простая импликанта ( это импликанта, которая содержит хотя бы минтерм функции, но перестает быть импликантой после удаления любого аргумента (иными словами, это импликанта, к которой не нельзя применить операцию склеивания).
Сокращенная ДНФ - это дизъюнкция всех простых импликант.
Переменные в строках и столбцах располагаются так, чтобы соседние клетки карты Карно различались только в одном разряде переменных, т.е были соседними. Поэтому значения переменных в столбцах и в строках карты образуют соседний код Грея. Такой способ представления очень удобен для наглядности при минимизации булевых функций. Карта Карно 4 переменных, с точки зрения определения "соседства" переменных, геометрически представляет собой пространственную фигуру тор или, проще говоря, "бублик".
Метод карт Карно применим к минимизации булевых функций до 6-ти переменных (до 4 переменных на плоскости) и до 6 ( в трехмерной интерпретации.
Если исходная функция задана в виде какой-либо формулы, наборы, на которых функция равна 1, определяют методом перебора переменных, при этом обеспечивается развертывание формулы в СДНФ. В заполненной карте Карно наглядно отображаются соседние конституенты: им соответствуют 1, расположенные в соседних клетках. Все клетки, содержащие 1, объединяются в замкнутые области, каждая область должна представлять собой прямоугольник с числом клеток 2, 4, 8. Области могут пересекаться, и одни и те же клетки могут входить в разные области. Соседними клетками являются не только клетки, расположенные рядом по горизонтали и вертикали, но и клетки, находящиеся на противоположных границах карты.
При охвате клеток замкнутыми областями следует стремиться к минимальному числу областей, каждая из которых содержала бы возможно большее число клеток. Каждый член МДНФ составляют лишь из тех переменных, которые для соответствующей области имеют одно значение: без инверсии или с инверсией. Если переменная для одной клетки области имеет значение без инверсии, а для другой клетки этой области (с инверсией, она в соответствующем члене МДНФ не присутствует.
Для получения минимальной конъюнктивной нормальной формы функции замкнутыми областями охватываются клетки с нулевыми значениями функции и при записи членов МКНФ берутся инверсные значения переменных с неизменным значением в пределах соответствующих областей.
Правила минимизации с использованием карт Карно:
1. В карте Карно группы единиц (для получения ДНФ) и группы нулей (для получения КНФ) необходимо обвести четырехугольными контурами. Внутри контура должны находится только одноименные значения функции. Этот процесс соответствует операции склеивания или нахождения импликант данной функции.
2. Количество клеток внутри контура должно быть целой степенью двойки (1, 2, 4,8, 16...).
3. При проведении контуров крайние строки карты (верхние и нижние, левые и правые), а также угловые клетки, считаются соседними (для карт до 4-х переменных).
4. Каждый контур должен включать максимально возможное количество клеток. В этом случае он будет соответствовать простой импликанте.
5. Все единицы (нули) в карте (даже одиночные) должны быть охвачены контурами. Любая единица (нуль) может входить в контуры произвольное количество раз.
6. Множество контуров, покрывающих все 1 (0) функции образуют тупиковую ДНФ (КНФ). Целью минимизации является нахождение минимальной из множества тупиковых форм.
7. В элементарной конъюнкции (дизъюнкции), которая соответствует одному контуру, остаются только те переменные, значение которых не изменяется внутри обведенного контура. Переменные булевой функции входят в элементарную коньюнкцию (для значений функции 1) без инверсии, если их значение на соответствующих координатах равно 1 и с инверсией - если 0. Для значений булевой функции, равных 0, записываются элементарные дизъюнкции, куда переменные входят без инверсии, если их значение на соответствующих координатах равно 0 и с инверсией - если 1.
Если рассматривать запись результатов минимизации в кубическом виде, то при минимизации булевой функции по единичным значениям, каждой конъюнкции ранга R соответствует куб ранга R, где каждой переменной без инверсии соответствует 1 в кубе, переменной с инверсией ( 0, а на месте отсутствующей переменной ставиться X . Полученное множество кубов образует единичное покрытие C1 (соответствующее ДНФ). При минимизации булевой функции по нулевым значениям и представлении результатов минимизации в кубическом виде, нулевое покрытие C0 формируется на основе обратной ДНФ , которая является инверсной функцией по отношению к КНФ (способ построения инверсных функций и пример инверсных функций для f ( 1,3,5,6,7 ) = 1. Отметим, что обратная ДНФ строится на основе КНФ. Таким образом, каждой дизъюнкции ранга R (из КНФ) соответствует куб ранга R, где каждой переменной без инверсии соответствует 0 в кубе, переменной с инверсией ( 1, а на месте отсутствующей переменной ставиться X . Полученное множество кубов образует нулевое покрытие C0.
В качестве примера рассмотрим минимизацию булевых функций трех переменных   f (1,3,5,6,7) = 1   и четырех переменных f ( 3,7,11,12,13,14,15) = 1.
На рис. 5, а, б показано получение аналитических и кубических результатов минимизации булевой функции с использованием карт Карно.

13 EMBED Visio.Drawing.11 1415

Рисунок 5, а ( Карта Карно трех аргументов

13 EMBED Visio.Drawing.11 1415
Рисунок 5, б ( Получение аналитических и кубических результатов
минимизации булевой функции трех переменных с использованием карт Карно

На рис. 6 показан процесс минимизации и получения аналитических и кубических выражений при минимизации булевой функции четырех переменных.

13 EMBED Visio.Drawing.11 1415
13 EMBED Visio.Drawing.11 1415
Рисунок 6 ( Получение аналитических и кубических результатов
минимизации булевой функции четырех переменных
с использованием карт Карно

Исходя из способа кодировки переменных в строках и столбцах карты Карно соседним кодом Грея, с учетом сохранения "физического" соседства соседних клеток карты, на плоскости можно изобразить карту до 4-х переменных включительно. В реальной работе с булевыми функциями большего числа переменных также могут использоваться карты Карно, имеющие специальную форму.
Метод минимизации булевых функций с использованием карт Карно является одним из самых наглядных и удобных с позиций инженерной практики.
Интервалом l-го ранга называется подмножество вершин двоичного n-мерного куба, соответствующее элементарной конъюнкции l-го ранга.
Покрытием l-го ранга называется подмножество клеток карты Карно n-го порядка, соответствующее элементарной конъюнкции l-го ранга.
При задании булевой функции в виде ДНФ, будет задано и множество ее единичных значений, что будет соответствовать комбинации интервалов на пространственном кубе или комбинации покрытий на карте Карно.
Например, рассмотрим функцию трех переменных:

13 EMBED Equation.3 1415.

ДНФ содержит три конъюнкции, которые представляются следующими интервалами (рис. 7.). На карте Карно получатся следующие покрытия (рис. 8.). Таким образом, существует взаимно однозначное соответствие между ДНФ, интервалами пространственного куба и покрытиями на карте Карно.




Рисунок 7 ( ДНФ, содержащая три конъюнкции
Рисунок 8 ( Карта Карно ДНФ
нестандартная


Задача нахождения МДНФ может быть сформулирована как задача построения такого множества покрытий единичных значений булевой функции, при котором сложность ДНФ будет минимальной.
Графически это означает, что необходимо и достаточно найти множество покрытий минимального ранга, представляющих множество единичных значений булевой функции.
МДНФ для рассматриваемой функции можно построить из трех интервалов второго ранга на пространственной решетке, что соответствует трем покрытиям 2-го ранга на карте Карно (рис. 9, рис. 10.).
В правильности графического способа минимизации легко убедиться, выполнив некоторые аналитические преобразования в соответствии с законами алгебры логики.
Построение МДНФ является неоднозначным процессом, так как для данной функции может существовать несколько МДНФ, и сам процесс выбора покрытий строго не формализован.
Однако, как уже отмечалось графический метод хорошо работает для логических функций первой группы и в принципе, может применяться для функций 3-й группы, что вполне приемлемо в инженерной практике.




Рисунок 9 ( МДНФ
рассматриваемой функции
Рисунок 10 ( Карта Карно МДНФ карта нестандартная


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

13 EMBED Equation.3 1415

Возможность поглощения следует из очевидных равенств:

13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415.

Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных к склейке с последующим поглощением, что для больших форм может оказаться достаточно сложной задачей. Карты Карно предоставляют наглядный способ отыскания таких термов.
Как известно, булевы функции n переменных, представленные в виде СДНФ или СКНФ могут иметь в своём составе 2n различных термов. Все эти члены составляют некоторую структуру, топологически эквивалентную n–мерному кубу, причём любые два терма, соединённые ребром, пригодны для склейки и поглощения.
На рис. 11 изображена простая таблица истинности для функции из двух переменных, соответствующий этой таблице 2-мерный куб (квадрат), а также 2-мерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов:


13 EMBED Visio.Drawing.11 1415

Рисунок 11 ( Таблица истинности для функции двух переменных,
соответствующий этой таблице 2-мерный квадрат,
2-мерный куб с обозначением членов СДНФ
и карта Карно группировки термов

Для случая функции трёх переменных имеют дело с трёхмерным кубом (рис. 12). Это сложнее и менее наглядно, но технически возможно.



Рисунок 12 ( Графический и координатный способ представления функции двух переменных

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

13 EMBED Equation.3 1415

В общем случае можно сказать, что 2n термов, принадлежащие одной n –мерной грани гиперкуба, склеиваются в один терм, при этом поглощаются n переменных.
Для упрощения работы с булевыми функциями большого числа переменных был предложен следующий удобный приём. Куб, представляющий собой структуру термов, разворачивается на плоскости как показано на рис. 13.



Рисунок 13 ( Развертывание на плоскости
куба, представляющего собой структуру термов

Таким образом, появляется возможность представлять булевы функции с числом переменных больше двух в виде плоской таблицы. При этом следует помнить, что порядок кодов термов в таблице (00 01 11 10) не соответствует порядку следования двоичных чисел, а клетки, находящиеся в крайних столбцах таблицы, соседствуют между собой.
Аналогичным образом можно работать с функциями четырёх, пяти и более переменных. Примеры таблиц для n1 =4 и n2 =5 приведены на рис. 14. Для этих таблиц следует помнить, что соседними являются клетки, находящиеся в соответственных клетках крайних столбцов и соответственных клетках верхней и нижней строки.



Рисунок 14 ( Развертывание на плоскости функций
четырех и пяти переменных

Пример. Минимизировать функцию

13 EMBED Equation.3 1415

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

13 EMBED Equation.3 1415
Полученное выражение представляет собой сокращенную форму заданной функции, а члены его ( простые импликанты. Переход от сокращенной формы к минимальной осуществляется с помощью импликантной матрицы, представленной в виде табл. 3.

Таблица 3 ( Импликантная матрица

Простые
импликанты
Члены СДНФ


13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

13 EMBED Equation.3 1415
Ч
Ч





13 EMBED Equation.3 1415
Ч

Ч




13 EMBED Equation.3 1415


Ч
Ч



13 EMBED Equation.3 1415



Ч
Ч


13 EMBED Equation.3 1415




Ч
Ч

В таблице отмечаются столбцы членов СДНФ, поглощаемых отдельными простыми импликантами. По таблице определяются импликанты, которые не могут быть исключены из сокращенной формы (составляют ядро функции). К ним относятся такие, для которых в таблице имеется хотя бы один столбец, перекрываемый только данной импликантой. В приведенном примере ядро составляют импликанты 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415. Только ими перекрываются второй и шестой столбцы матрицы. Теперь для получения минимальной формы следует выбрать минимальное количество из оставшихся импликант, чтобы перекрыть еще не перекрытые столбцы (четвертый и третий в нашем примере). В рассматриваемом случае такой импликантой будет

13 EMBED Equation.3 1415.

Тогда минимальная дизъюнктивная нормальная форма (МДНФ) заданной функции:

13 EMBED Equation.3 1415

При применении метода Квайна для получения минимальной конъюнктивной нормальной формы (МКНФ) логической функции операции склеивания и поглощения имеют вид:

13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

а минимизация проводится в том же порядке, что и для СДНФ.
Пример. Минимизировать СКНФ функции

13 EMBED Equation.3 1415.

Склеиваемые члены: первый и третий (результат 13 EMBED Equation.3 1415); второй и четвертый (результат 13 EMBED Equation.3 1415); третий и четвертый (результат 13 EMBED Equation.3 1415).
После проведения операции склеивания получим:

13 EMBED Equation.3 1415
Импликантная матрица для рассматриваемой функции представляется табл. 4.
Все столбцы перекрываются двумя импликантами 13 EMBED Equation.3 1415и 13 EMBED Equation.3 1415. Следовательно, МКНФ функций будет

13 EMBED Equation.3 1415.


Таблица 4 ( Импликантная матрица

Простые
импликанты
Члены СКНФ


13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

13 EMBED Equation.3 1415
Ч

Ч


13 EMBED Equation.3 1415

Ч

Ч

13 EMBED Equation.3 1415


Ч
Ч



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

Таблица 5( Истинность ФАЛ трёх аргументов

x1
0
1
0
1
0
1
0
1

x2
0
0
1
1
0
0
1
1

x3
0
0
0
0
1
1
1
1

f
0
1
1
0
1
1
1
0


Тогда СДНФ функции, когда f = 1

13 EMBED Equation.3 1415

СКНФ этой же функции, когда f = 0

13 EMBED Equation.3 1415

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

13 EMBED Equation.3 1415

Требуется данную функцию выразить в СКНФ.
Недостающими комбинациями аргументов являются:

13 EMBED Equation.3 1415 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415

Запишем их в виде СДНФ и проивертируем полученное выражение:

13 EMBED Equation.3 1415

В результате получим заданную функцию в СКНФ.
Пример. Если заданна функция в СКНФ:

13 EMBED Equation.3 1415

то в этом случае недостающее до полного набора комбинации аргументов записываются в форме СКНФ и полученное выражение инвертируется:

13 EMBED Equation.3 1415

Таким образом, осуществлен переход от СКНФ к СДНФ.


ПРЕДСТАВЛЕНИЕ ФАЛ В РАЗЛИЧНЫХ БАЗИСАХ
Любую логическую функцию можно записать в базисе И, ИЛИ, НЕ, как суперпозицию функций этой системы:

13 EMBED Equation.3 1415

Система ФАЛ {И, ИЛИ, НЕ} является функционально полной, но не минимальной.
Минимальной функционально полной системой, называется такая система, исключение из которой хотя бы одной функции делает систему неполной. К ним относятся системы функций {И, НЕ} и {ИЛИ, НЕ}.
Для того чтобы приведенную выше функцию записать в базисе {И, НЕ}, необходимо в выражении функции заменить конъюнкции дизъюнкциями, а для записи функции в базисе {ИЛИ, НЕ} дизъюнкции заменяются конъюнкциями. Указанные преобразования выполняются на основании закона двойного отрицания и правила де Моргана:
13 EMBED Equation.3 1415 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415

Пример. Выразить функцию

13 EMBED Equation.3 1415

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

13 EMBED Equation.3 1415

Теперь для перехода к базису {ИЛИ, НЕ} дважды проинвертируем каждый член полученного выражения

13 EMBED Equation.3 1415

Чтобы заданную функцию записать в базисе {ИЛИ, НЕ}, инвертируем дважды ее ДНФ

13 EMBED Equation.3 1415

Таким образом, от базиса {И, ИЛИ, НЕ} можно перейти к минимальным полным базисам {И, НЕ} и {ИЛИ, НЕ}.


Реализация ФАЛ на контактных и бесконтактных элементах
Контактные дискретные элементы. Исполнительным органом этих элементов является механический контакт между двумя пружинами, приводимыми в соприкосновение механическим перемещением одной из них. Реагирующим органом у контактных элементов могут быть обмотки, создающие магнитное поле, воздействующее через якорь или другие устройства на контактные пружины; всевозможные механизмы (кнопки, ключи и т. п.), осуществляющие механическое воздействие на контактные пружины при перемещении.
В зависимости от конструкции существуют контактные элементы с памятью и без памяти. Память достигается за счет механического или магнитного удержания элемента в определенном состоянии.
Наиболее распространенным контактным дискретным элементом является электромагнитное реле (рис. 15). Реагирующим органом реле, воспринимающим внешнее воздействие в виде электрического тока, служит обмотка 3, исполнительным органом, выдающим выходные сигналы (0 ( цепь разомкнута, 1 ( цепь замкнута) ( контакт 1. Промежуточный орган, передающий воздействие от реагирующего органа к исполнительному, имеет сердечник 5, ярмо 4 и подвижную часть 2, называемую якорем, которая приводится в действие электромагнитным потоком и воздействует на контакт 1. Реле может содержать от одной до восьми контактных групп. Притяжение якоря к сердечнику и замыкание контактов называют срабатыванием реле.


13 EMBED Visio.Drawing.11 1415
Рисунок 15 ( Электромагнитное реле


Фронтовой контакт (рис. 16, а), называемый нормально разомкнутым, или замыкающим, в исходном состоянии разомкнут: под воздействием якоря пружина изгибается и контакт замыкается. Тыловой контакт (рис. 16, б), называемый нормально замкнутым, или размыкающим, в исходном стоянии замкнут. При срабатывании реле контакт размыкается. Переключающий контакт (рис. 16, в) состоит из комбинации замыкающего и размыкающего контактов. При срабатывании реле движение якоря вызывает размыкание одного и замыкание другого контакта. Контакты обладают двусторонней проводимостью, что является их особенностью. В принципиальных схемах обмотки и контакты реле обозначают прописными буквами.

13 EMBED Visio.Drawing.11 1415

Рисунок 16 ( Условное обозначение контактов

Бесконтактные дискретные элементы. Действие этих элементов основано на нелинейном изменении проводимости под влиянием напряжения, тока или магнитного поля, воздействующих на элемент. Например, если на диод (рис. 17) подается напряжение прямой полярности (входной сигнал х=1), сопротивление составляет несколько омов, он открыт, напряжения на выходе и входе равны (выходной сигнал х=1). При подаче на вход напряжения обратной полярности (входной сигнал х=0) сопротивление диода становится очень большим, диод закрыт, значение напряжения на выходе близко к нулю (выходной сигнал z=0). Как видно, у рассмотренного элемента состояние выхода повторяет состояние входа. Такие элементы называют повторителями.
Транзисторы в дискретных устройствах используются в режиме переключения. Транзистор может иметь два состояния: закрытое, соответствующее максимальному сопротивлению между эмиттером и коллектором, и открытое, при котором сопротивление между эмиттером и коллектором минимальное. Переключение транзистора из одного состояния в другое обеспечивается изменением входного сигнала.

13 EMBED Visio.Drawing.11 1415

Рисунок 17 ( Схема дискретного элемента на диоде

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

13 EMBED Visio.Drawing.11 1415
13 EMBED Visio.Drawing.11 1415


Рисунок 18 ( Схема дискретного элемента на транзисторе

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

Таблица 6 ( Релейно-контактные схемы логических элементов и функций

Схема
Условное
обозначение
логического
элемента, функция
Релейно-контактная схема

1
2
3

13 EMBED Visio.Drawing.11 1415

13 EMBED Visio.Drawing.11 1415
13 EMBED Equation.3 1415

13 EMBED Visio.Drawing.11 1415

13 EMBED Visio.Drawing.11 1415


13 EMBED Visio.Drawing.11 1415

13 EMBED Equation.3 1415


13 EMBED Visio.Drawing.11 1415


13 EMBED Visio.Drawing.11 1415
13 EMBED Visio.Drawing.11 1415
13 EMBED Equation.3 1415


13 EMBED Visio.Drawing.11 1415

13 EMBED Visio.Drawing.11 1415
13 EMBED Visio.Drawing.11 1415
13 EMBED Equation.3 1415


13 EMBED Visio.Drawing.11 1415
13 EMBED Visio.Drawing.11 1415
13 EMBED Equation.3 1415

13 EMBED Visio.Drawing.11 1415

Продолжение таблицы 6

1
2
3

13 EMBED Visio.Drawing.11 1415
13 EMBED Visio.Drawing.11 1415

13 EMBED Equation.3 1415

13 EMBED Visio.Drawing.11 1415




13 EMBED Equation.3 1415
13 EMBED Visio.Drawing.11 1415


На рис. 19 представлена схема на бесконтактных ЛЭ, реализующая эту же функцию в базисе {И, ИЛИ, НЕ} (рис. 20), а на рис. 21 и рис. 22 – в базисах {И, НЕ} и {ИЛИ, НЕ} соответственно.
Реализация ФАЛ в базисах {И, НЕ} и {ИЛИ, НЕ} удобна тем, что в этих случаях используются однотипные ЛЭ, а следовательно, упрощается монтаж и регулировка схем.


13 EMBED Visio.Drawing.11 1415
Рисунок 19 ( Реализация МДНФ на релейно-контактных элементах

13 EMBED Visio.Drawing.11 1415Рисунок 20 – Реализация ФАЛ в базисе {И, ИЛИ, НЕ}
на бесконтактных ЛЭ




13 EMBED Visio.Drawing.11 1415
Рисунок 21 – Реализация ФАЛ в базисе {ИЛИ, НЕ}
на бесконтактных ЛЭ




13 EMBED Visio.Drawing.11 1415
Рисунок 22– Реализация ФАЛ в базисе {И, НЕ}
на бесконтактных ЛЭ


СИНТЕЗ КОМБИНАЦИОННЫХ СХЕМ
Синтез комбинационных схем с несколькими выходами
В предыдущей главе рассматривались примеры синтеза комбинационных схем с одним выходом на контактных и бесконтактных элементах. Однако в общем случае комбинационные схемы могут иметь m входов и п выходов, т.е. могут реализовать n функций вида

13 EMBED Equation.3 1415

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

13 EMBED Equation.3 1415,
или
13 EMBED Equation.3 1415

где М ( подмножество состояний схемы, при которых функция Zi, принимает значение 1 (обязательное подмножество);
N ( условное подмножество или подмножество состояний схемы, при которых значение выходной функции Z (безразлично);
Q ( подмножество состояний схемы, при которых Zi = 0 (запрещенное подмножество);
В ( база или набор аргументов ФАЛ.
Пример. Пусть комбинационная схема задана таблицей истинности (табл. 7).

Таблица 7 ( Таблица истинности функции трех аргументов для двух ФАЛ

Номер
состояния
с
b
a
Z1
Z2

0
0
0
0
1
0

1
0
0
1
1
1

2
0
1
0
0
1

3
0
1
1
0
0

4
1
0
0
1
1

5
1
0
1
~
1

6
1
1
0
0
1

7
1
1
1
~
0


Так как значения Z1, в 5 и 7 состояниях неопределены (безразличны), то функция Z1, может быть задана в виде:

13 EMBED Equation.3 1415

или

13 EMBED Equation.3 1415.

Поскольку значения Z1 в 5 и 7 состояниях безразличны, то мы можем считать их равными 0 или 1 так, чтобы максимально упростить схему. Следовательно, аналитическая запись для Z1 может быть следующей:

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

В дальнейшем можно минимизировать каждую функцию известными методами и построить комбинационную схему путем синтеза двух разделенных цепей, реализующих приведенные функции Z1 и Z2.
Однако применение такого способа при синтезе комбинационных схем с несколькими выходами может быть не рациональным, поскольку, если даже каждая из цепей будет построена минимальным образом, в целом логическое устройство может оказаться не минимальным.
Принцип получения минимальной схемы сводится к нахождению минимального набора членов с минимальным количеством букв, достаточного для описания всех формируемых данным устройством функций.
Рассмотрим метод построения минимальной комбинационной схемы с тремя выходами, способ функционирования которой задан табл. 8.

Таблица 8 ( Истинность для трех ФАЛ

x1
0
0
0
0
1
1
1
1

x2
0
0
1
1
0
0
1
1

x3
0
1
0
1
0
1
0
1

Z1
0
0
1
1
0
1
1
0

Z2
0
1
1
0
0
1
0
1

Z3
0
1
1
1
1
0
1
0


Порядок минимизации следующий:
1. Записываем в табл. 9 наборы аргументов, на которых хотя бы одна функция принимает значение 1. В правой части таблицы указываются сами функции.

Таблица 9 ( Члены СДНФ функций

13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

13 EMBED Equation.3 1415
13 EMBED Equation.3 1415


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

Таблица 10 ( Результаты операций склеивания

13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

Продолжение таблицы 10
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

13 EMBED Equation.3 1415
13 EMBED Equation.3 1415


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

Таблица 11 ( Импликантная матрица
Импликанты
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415


Z2
Z3
Z1
Z2
Z3
Z1
Z3
Z3
Z1
Z2
Z1
Z3
Z2

13 EMBED Equation.3 1415

Ч




Ч







13 EMBED Equation.3 1415
Ч








Ч




13 EMBED Equation.3 1415


Ч

Ч





Ч
Ч


13 EMBED Equation.3 1415


Ч

Ч
Ч
Ч







13 EMBED Equation.3 1415







Ч



Ч


13 EMBED Equation.3 1415









Ч


Ч

13 EMBED Equation.3 1415


Ч
Ч
Ч









13 EMBED Equation.3 1415








Ч
Ч





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

Таблица 12 ( Таблица импликант и функций
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

Продолжение таблицы 12
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

13 EMBED Equation.3 1415
13 EMBED Equation.3 1415


5. Записываем выражения для выходов комбинационной схемы:

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415.

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

13 EMBED Visio.Drawing.11 1415

Рисунок 23 – Реализация комбинационной схемы на релейно-контактных элементах

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

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

Проинвертировав дважды выражения для Z, мы получим функции, реализовать которые будет удобно в базисе {И, НЕ):

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415


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

13 EMBED Visio.Drawing.11 1415

Рисунок 24 ( Условное обозначение шифратора


Наиболее распространён способ двоичного представления (кодирования) десятичных цифр в так называемом коде 8421 (название кода составлено из весовых коэффициентов разрядов двоичного числа). Наряду с этим кодом при двоичном кодировании десятичных цифр используются различные другие коды, наиболее используемые из которых приведены в табл. 13.

Таблица 13 ( Двоичное кодирование десятичной цифры
Десятичная
цифра

Двоичное кодирование десятичной цифры


код 8421
код 2421
код 2 из 5
код с изб. 3
код 3а + 2
код 7421

0
0000
0000
11000
0011
00010
0000

1
0001
0001
01100
0100
00101
0001

2
0010
0010
00110
0101
01000
0010

3
0011
0011
00011
0110
01011
0011

4
0100
0100
10001
0111
01110
0100

5
0101
1011
10100
1000
10001
0101

6
0110О
1100
01010
1001
10100
0110

7
0111
1101
00101
1010
10111
1000

8
1000
1110
10010
1011
11010
1001

9
1001
1111
01001
1100
11101
1010


В коде 7421 любая кодовая комбинация содержит не более двух единиц. В коде 2 из 5 все кодовые комбинации содержат точно две единицы. Это свойство используется для обнаружения ошибочных комбинаций (ошибочное распознавание любого из символов принятой кодовой комбинации изменяет число единиц в этой комбинации).
Пары десятичных цифр, сумма которых равна девяти, составляют цифры, взаимно дополняющие друг друга до девяти (0 и 9, 1 и 8, 2 и 7,...). В коде 2421 и коде с избытком 3 кодовая комбинация, соответствующая любой из десятичных цифр, представляет собой инверсию комбинации, соответствующей ее дополнению до девяти. Например, в коде 2421 паре взаимно дополняющих до девяти цифр 2 и 7 соответствуют комбинации 0010 и 1101, каждая из которых образуется как инверсия другой. Это свойство упрощает выполнение в цифровых устройствах арифметических операций над десятичными числами. Таким же свойством дополнения до девяти обладает код 3а + 2. Кроме того, этот код имеет и другое полезное свойство – любая пара кодовых комбинаций отличается не менее чем в двух разрядах, что позволяет обнаруживать ошибочные комбинации (ошибка, изменяющая цифру одного разряда любой из кодовых комбинаций, приводит к так называемой запрещенной комбинации, не используемой для представления десятичных цифр в этом коде).
Двоичный код может быть любым из всей такой системы двоичных кодов. В нашем примере это код 8421. Представление десятичных чисел в двоичном коде 8421 приведено в табл. 14.

Таблица 14 ( Кодирование десятичных чисел в коде 8421
Число
x1
x2
x3
x4

0
0
0
0
0

1
1
0
0
0

2
0
1
0
0

3
1
1
0
0

4
0
0
1
0

5
1
0
1
0

6
0
1
1
0

7
1
1
1
0

8
0
0
0
1

9
1
0
0
1


Шифратор может иметь и инверсные выходы. Выражения для всех выходов х через входные переменные у запишем из табл. 13:

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

Схема шифратора показана на рис. 25. и рис. 26.

13 EMBED Visio.Drawing.11 1415

Рисунок 25 - Реализация шифратора в базисе {И, ИЛИ, НЕ}
на бесконтактных ЛЭ

13 EMBED Visio.Drawing.11 1415

Рисунок 26 - Реализация шифратора в базисе {ИЛИ, НЕ}
на бесконтактных ЛЭ
Задания для самостоятельной работы
Задание 1.
1.1. Задать в виде таблицы истинности ФАЛ трех переменных
а) которая принимает значение тогда и только тогда, когда
равен нулю один и только один из ее аргументов;
равен единице два и только два из ее аргументов;
равны единице хотя бы два из ее аргументов;
равен единице хотя бы один из ее аргументов.
б) которая принимает значение единицы тогда и только тогда, когда
равны единице не более одного из ее аргументов;
равны нулю более одного из ее аргументов.
1.2. Задать в виде таблицы истинности следующие ФАЛ:
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415.
1.3. Доказать с использованием таблиц истинности законы алгебры логики (раздел 1).
1.4. Доказать с использованием таблиц истинности следующие равенства:
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
x13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415;
13 QUOTE 1415.

Задание 2. Функция задана в табл. 15 (согласно варианта).
2.1. Представить функцию:
а) таблицей истинности;
б) совершенной дизъюнктивной нормальной формой;
в) совершенной конъюнктивной нормальной формой.

Таблица 15
№ варианта
Функция

1
13 EMBED Equation.3 1415

2
13 EMBED Equation.3 1415

3
13 EMBED Equation.3 1415

4
13 EMBED Equation.3 1415

5
13 EMBED Equation.3 1415

6
13 EMBED Equation.3 1415

7
13 EMBED Equation.3 1415

8
13 EMBED Equation.3 1415

9
13 EMBED Equation.3 1415

10
13 EMBED Equation.3 1415

11
13 EMBED Equation.3 1415

12
13 EMBED Equation.3 1415

13
13 EMBED Equation.3 1415

14
13 EMBED Equation.3 1415

15
13 EMBED Equation.3 1415

16
13 EMBED Equation.3 1415

17
13 EMBED Equation.3 1415

Продолжение таблицы 15
18
13 EMBED Equation.3 1415

19
13 EMBED Equation.3 1415

20
13 EMBED Equation.3 1415

21
13 EMBED Equation.3 1415

22
13 EMBED Equation.3 1415

23
13 EMBED Equation.3 1415

24
13 EMBED Equation.3 1415

25
13 EMBED Equation.3 1415


2.2. Минимизировать функцию:
a) алгебраическим методом;
б) методом Карно.
2.3. Записать заданную функцию в базисах {И-НЕ} и {ИЛИ-НЕ}.

Задание 3. Функция задана в табл. 16 (согласно варианта).


Таблица 16

№ варианта
Функция

1
2

1
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

2
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

3
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

4
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

5
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

6
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

Продолжение таблицы 16
7
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

8
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

9
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

10
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

11
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

12
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

13
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

14
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

15
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

16
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

17
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

18
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

19
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

Продолжение таблицы 16
20
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

21
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

22
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

23
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

24
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415


3.1. Для булевых выражений табл. 15 выполнить следующие преобразования:
1) построить релейно-контактную схему, соответствующую заданной ФАЛ;
2) упростить заданную ФАЛ контактной цепи;
3) построить релейно-контактную схему, соответствующую полученной упрощенной ФАЛ контактной цепи;
4) начертить функциональную схему, соответствующую ис-ходной и упрощенной ФАЛ и выполненную на элементах, реализующих логические функции отрицания, конъюнкции и дизъюнкции;
3.2. Построить релейно-контактные схемы, реализующие следующие ФАЛ:
а) x y
б) x y
в) x 13 EMBED PBrush 1415 y
г) x y
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Туйгунова А.Г. Сборник задач по алгебре логики: Учебное пособие к практическим занятиям по курсу “Автоматизация систем электроснабжения” / Туйгунова А.Г., Худоногов И.А. – Красноярск: КрИЖТ ИрГУПС, 2012. – 49 с.
2. Слюзов Ю. И. Синтез дискретных устройств железнодорожной автоматики и телемеханики: методические указания по курсу «Теория дискретных устройств железнодорожной автоматики и телемеханики и связи / Ю.И. Слюзов, В.Я. Требин. – Омск: ОмИИТ, 1987, – 54 с.
3. Поспелов Д.А. Логические методы анализа и синтеза схем / Д.А. Поспелов. – изд. 2-е перераб. и доп., М.: Энергия, 1968. – 228 с.
4. Теория передачи сигналов на железнодорожном транспорте: учеб. для вузов ж.-д. трансп. / Г.В. Горелов [и др.]. – М.: Транспорт, 2001. – 415 с.
5. Калабеков Б.А. Цифровые устройства и микропроцессорные системы: учеб. для техникумов связи / Б.А. Калабеков. – М.: Горячая линия – Телеком, 2002. – 336 с.
6. Браммер Ю.А. Импульсные и цифровые устройства: учеб. для студентов сред. спец. учеб. заведений / Ю.А.Браммер, И.Н. Пащук. –
7-е изд., пераб. и доп. – М.: Высш. шк., 2003 – 351 с.
7. Хоуп Г. Проектирование цифровых вычислительных устройств на интегральных схемах / Г. Хоуп. – М.: Мир, 1984 . – 400 с.
8. Опарин Г.А. Сборник задач по алгебре логики: Методическое пособие к практическим занятиям по курсу «Теория дискретных устройств автоматики и телемеханики».– Иркутск: ИрГУПС, 2003. – 26 с.









13 PAGE \* MERGEFORMAT 14215







Root EntryTIMES NEW ROMAN
Times New RomanTIMES NEW ROMAN
Times New Roman 
·
·
·
·
·я
·Н
·
·
·
·!Ђ
·
·
·
·
·
·3
·
·
·я Fi
·
·
·Ш
·
·
·
·Юf
·
·Z
·
·
·
·м
·мo
·
·
·
·
·
·
·ET
·
·
·
·
·
·
·m Fi
·
·
·Ш
·
·
·
·Юf
·
·я
·
·
·
·м
·мo
·
·
·
·
·
·\
·
·AD
·
·
·
·
·am F
·
·
·
·Ш
·м
·
·Юf
·ия
·
·
·
·
·
·мo
·
·
·
·
·
·\
·
·
·
·
·
·
·ц
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
· 
·
·л
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·!
·
·
·
·
·a
·
·
·
·
·a Ne
·
·
·
·
·
·
·E
·
·і
·
·
·
·
·
·
·
·S Fa
·
·
·
·
·
·
·*
·я 1
·
·
·
·я пк
·
·
·
·
·Wh
·
·
·
·1px
·
·
·
·
·gn t
·
·
· b
·
·
·
·
·
·
·
·
·
·
·
·
·
·рая
·
·лив
·
· (5
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
· 
·
·
·
·Об
·
·
·
·
·я до
·

·р
·
·
·
·Ro
·
·
·
·
·
·
·
·
·
·
·
·Ar
·
·
·
·
·
·
·Є
·
·
·
·
·
·k
·
·
·
·15а
·
·
·
·
·'ue f
·
·
·
·
·
·
·Те
·
·
·
·зн
·
·
·
·
·
·
·
·
·gn t
·
·
· b
·
·
·
·
·
·
·
·
·
·
·кст
·
·
·
·
·
·
·
·ы
·
·6
·р
·
·
·
·Si
·
·
·
·e
·
·
·lac
·
·6
·р
·
·
·
·Че
·
·
·
·
· л
·
·
·
·
·
·
·сEquation NativeEquation NativeEquation NativeEquation Native 
·
·
·
·
·я
·Н
·
·
·
·!Ђ
·
·
·
·
·
·3
·
·
·я Fi
·
·
·Ш
·
·
·
·Юf
·
·Z
·
·
·
·м
·мo
·
·
·
·
·
·\R
·ФS
·
·ц
·
·
·
·
·m Fi
·
·
·Ш
·
·
·
·Юf
·
·я
·
·
·
·м
·мo
·
·
·
·
·
·\T
·
·
·
·Ъ
·ц
·
·
·Їа а
·
·
·
·
·
·
·
·
·
·
·@§
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·ух
·
·
·
·
·о
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·уз
·
·
·
·
·ц
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·#
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·є
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·ec
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·N
·
·
·
·
·
·
·
·
·
·*
·
·
·з
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·Ђ
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·a Ne
·
·
·
·
·
·
·E
·
·і
·
·
·
·
·
·
·
·S Fa
·
·
·
·
·
·
·*
·я 1
·
·
·
·я пк
·
·
·
·
·Wh
·
·
·
·1px
·
·
·
·
·gn t
·
·
· b
·
·
·
·
·
·
·
·
·
·
·
·
·
·рая
·
·лив
·
· (5
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
· 
·
·
·
·Об
·
·
·
·
·я до
·

·р
·
·
·
·Ro
·
·
·
·
·
·
·
·
·
·
·
·Ar
·
·
·
·
·
·
·Є
·
·
·
·
·
·k
·
·
·
·15а
·
·
·
·
·'ue f
·
·
·
·
·
·
·Те
·
·
·
·зн
·
·
·
·
·
·
·
·
·gn t
·
·
· b
·
·
·
·
·
·
·
·
·
·
·кст
·
·
·
·
·
·
·
·ы
·
·6
·р
·
·
·
·Si
·
·
·
·e
·
·
·lac
·
·6
·р
·
·
·
·Че
·
·
·
·
· л
·
·
·
·
·
·
·с  
·
·
·
·
·я
·Н
·
·
·
·!Ђ
·
·
·
·
·
·3
·
·
·3 пк
·
·
·
·
·Bl
·
·
·
·3p
·
·
·
·
·
·
·
·
·
·рая
·
·лив
·
·ay f
·
·an f
·
·d fi
·n d
·
·
·
·
·
·
·я пк
·
·
·
·
·Wh
·
·
·
·3px
·
·
·
·
·gn t
·
·
· w
·
·
· 8p
·
·
·
·
·
·
·
·кст
·
·
·
·
·
·
·
·ы
·
·8
·р
·
·
·
·Si
·
·
·
·e
·
·
·lac
·
·8
·
·
·
·
·
·Се
·
·
·
·
·
·
·
·
·
·
·
·
·0%
·
·
·
·
·50
·
·Gra
·
·fi
·
·gn t
·
·
· b
·
·
·
·
·
·
·
·5 пк
·
·
·
·
·Bl
·
·
·
·5p
·
·
·
·
·
·
·
·
·
·
·
·кст
·
·
·
·
·
·
·
·
·
·
·gn t
·
·
· w
·
·
·  
·
·
·
·
·я
·Н
·
·
·
·!Ђ
·
·
·
·
·
·3
·
·
·яm F
·
·
·
·и
·
·
·
·
·
·
·м
·
·Ю
·
·и
·
·
·
·Ш
·1
·
·
·04
·
·
·
·
·
·Ъ
·
·.
·
·«
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·єя
·
·
·
·Pro
·
·am F
·
·
·
·и
·
·
·
·
·
·
·м
·
·Ю
·
·и
·
·
·
·Ш
·1
·
·ї04
·
·яRAN
·Ъ
·
·
·
·S«
·
·
·
·
·
·
·
·
·
·Г
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·!
·
·
·
·
·a
·
·
·
·"
·
·
·
·
·
·
·
·S PG
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·a Ne
·
·
·
·
·
·
·E
·
·і
·
·
·
·
·
·
·
·S Fa
·
·
·
·
·
·
·*
·3 пк
·
·
·
·
·Bl
·
·
·
·3p
·
·
·
·
·
·
·
·
·
·рая
·
·лив
·
·ay f
·
·an f
·
·d fi
·n d
·
·
·
·
·
·
·я пк
·
·
·
·
·Wh
·
·
·
·3px
·
·
·
·
·gn t
·
·
· w
·
·
· 8p
·
·
·
·
·
·
·
·кст
·
·
·
·
·
·
·
·ы
·
·8
·р
·
·
·
·Si
·
·
·
·e
·
·
·lac
·
·8
·
·
·
·
·
·Се
·
·
·
·
·
·
·
·
·
·
·
·
·0%
·
·
·
·
·50
·
·Gra
·
·fi
·
·gn t
·
·
· b
·
·
·
·
·
·
·
·5 пк
·
·
·
·
·Bl
·
·
·
·5p
·
·
·
·
·
·
·
·
·
·
·
·кст
·
·
·
·
·
·
·
·
·
·
·gn t
·
·
· w
·
·
· 
·
·
·
·
·я
·Н
·
·
·
·!Ђ
·
·
·
·
·
·3
·
·
·S PG
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·3 пк
·
·
·
·
·Bl
·
·
·
·3p
·
·
·
·
·
·
·
·
·
·рая
·
·лив
·
·ay f
·
·an f
·
·d fi
·n d
·
·
·
·
·
·
·я пк
·
·
·
·
·Wh
·
·
·
·3px
·
·
·
·
·gn t
·
·
· w
·
·
· 8p
·
·
·
·
·
·
·
·кст
·
·
·
·
·
·
·
·ы
·
·8
·р
·
·
·
·Si
·
·
·
·e
·
·
·lac
·
·8
·
·
·
·
·
·Се
·
·
·
·
·
·
·
·
·
·
·
·
·0%
·
·
·
·
·50
·
·Gra
·
·fi
·
·gn t
·
·
· b
·
·
·
·
·
·
·
·5 пк
·
·
·
·
·Bl
·
·
·
·5p
·
·
·
·
·
·
·
·
·
·
·
·кст
·
·
·
·
·
·
·
·
·
·
·gn t
·
·
· w
·
·
· 
·
·
·
·
·я
·Н
·
·
·
·!Ђ
·
·
·
·
·
·3
·
·
·я Fi
·
·
·Ш
·
·
·
·Юf
·
·Z
·
·
·
·м
·мo
·
·
·
·
·
·
·ET
·
·
·
·
·
·
·m Fi
·
·
·Ш
·
·
·
·Юf
·
·я
·
·
·
·м
·мo
·
·
·
·
·
·\
·
·AD
·
·
·
·
·am F
·
·
·
·Ш
·м
·
·Юf
·ия
·
·
·
·
·
·мo
·
·
·
·
·
·\
·
·
·
·
·
·
·ц
·
·
·
·
·
·
·
·
·
·
·
·
·Г
·
·
·
·
·
·на а
·
·
·
·
·
·
·
·
·
·
·
·S PG
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·3 пк
·
·
·
·
·Bl
·
·
·
·3p
·
·
·
·
·
·
·
·
·
·рая
·
·лив
·
·ay f
·
·an f
·
·d fi
·n d
·
·
·
·
·
·
·я пк
·
·
·
·
·Wh
·
·
·
·3px
·
·
·
·
·gn t
·
·
· w
·
·
· 8p
·
·
·
·
·
·
·
·кст
·
·
·
·
·
·
·
·ы
·
·8
·р
·
·
·
·Si
·
·
·
·e
·
·
·lac
·
·8
·
·
·
·
·
·Се
·
·
·
·
·
·
·
·
·
·
·
·
·0%
·
·
·
·
·50
·
·Gra
·
·fi
·
·gn t
·
·
· b
·
·
·
·
·
·
·
·5 пк
·
·
·
·
·Bl
·
·
·
·5p
·
·
·
·
·
·
·
·
·
·
·
·кст
·
·
·
·
·
·
·
·
·
·
·gn t
·
·
· w
·
·
·TIMES NEW ROMAN
Times New Roman 
·
·
·
·
·я
·Н
·
·
·
·!Ђ
·
·
·
·
·
·3
·
·
·я Fi
·
·
·Ш
·
·
·
·Юf
·
·Z
·
·
·
·м
·мo
·
·
·
·
·
·\R
·ФS
·
·ц
·
·
·
·
·m Fi
·
·
·Ш
·
·
·
·Юf
·
·я
·
·
·
·м
·мo
·
·
·
·
·
·\T
·
·
·
·Ъ
·ц
·
·
·Їа а
·
·
·
·
·
·
·
·
·
·
·@§
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·ух
·
·
·
·
·о
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·уз
·
·
·
·
·ц
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·%
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·…
·
·
·
·
·
·
·
·
·
·
·
·G
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·е
·
·
·л
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·а
·ш
·
·
·
·
·
·
·
·с
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·N
·
·
·
·
·M
·
·
·
·*
·
·
·з
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·Ђ
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·Й
·
·
·
·
·
·„
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·a Ne
·
·
·
·
·
·
·E
·
·і
·
·
·
·
·
·
·
·S Fa
·
·
·
·
·
·
·*
·я 1
·
·
·
·я пк
·
·
·
·
·Wh
·
·
·
·1px
·
·
·
·
·gn t
·
·
· b
·
·
·
·
·
·
·
·
·
·
·
·
·
·рая
·
·лив
·
· (5
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
· 
·
·
·
·Об
·
·
·
·
·я до
·

·р
·
·
·
·Ro
·
·
·
·
·
·
·
·
·
·
·
·Ar
·
·
·
·
·
·
·Є
·
·
·
·
·
·k
·
·
·
·15а
·
·
·
·
·'ue f
·
·
·
·
·
·
·Те
·
·
·
·зн
·
·
·
·
·
·
·
·
·gn t
·
·
· b
·
·
·
·
·
·
·
·
·
·
·кст
·
·
·
·
·
·
·
·ы
·
·6
·р
·
·
·
·Si
·
·
·
·e
·
·
·lac
·
·6
·р
·
·
·
·Че
·
·
·
·
· л
·
·
·
·
·
·
·сEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native

Приложенные файлы

  • doc 10769967
    Размер файла: 4 MB Загрузок: 3

Добавить комментарий