Разработка устройства логического управления (контроллер) промышленного назначения с “гибкой” (программируемой) логикой

Общая структурная схема устройств такого типа приведена на рис.1.8,а. Управляемая схемой связей содержит набор соединительных линий и управляемые элементы связи ЭС₁¸ЭС_k, которые обеспечивают различные схемы соединений этих линий. Настройка схемы связей заключается в установке определенных элементов связи в проводящее состояние, а остальных – в непроводящее состояние.

Разработано около двадцати различных технологий настройки схемы связей. К основным из них относятся: установка металлических и полупроводниковых перемычек, диодов или транзисторов на заключительных стадиях изготовления ИС; установка плавных перемычек, пережигаемых пользователем после изготовления ИС;

Рис.1.8

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

Энергозависимые элементы связи могут сохранять свое состояние после отключения питания, а энергозависимые требуют постоянной подачи управляющих сигналов. Электрически программируемые элементы связи сохраняют установленное состояние в течение 10³-10⁴ часов, а число циклов программирования может достигать 10⁴. Для хранения значений управляющих сигналов в схему связей могут быть введены элементы памяти ЭП₁¸ЭП_к.

Пример ЦА с элементами связи, управляемыми специальными сигналами v₁, v₂, показан на рис.1.8,б. При подаче на ЭС₁ (ЭС₂) управляющего сигнала v₁=1, (v₂=1) элемент устанавливается в проводящее состояние, а при v₁=0, (v₂=0) находится в непроводящем состоянии. Тогда:

ЦА такого типа называются многофункциональными элементами (МФЭ) или многофункциональными модулями (МФМ). Группа входов V={v₁,v₂} называется входом кода операции (КОП). МФЭ может содержать сотни и тысячи функциональных элементов, а число входов кода операции ограничено числом управляющих входов порядка 15¸20.

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

Одной из схем, получивших широкое распространение, является матричная управляемая схема (рис.1.8,в). Такая схема на ИС легко реализуется в виде системы горизонтальных и вертикальных линий с элементами связи в каждой точке пересечения. Число таких линий на кристалле БИС и СБИС может достигать нескольких сотен. Состояние элементов связи определяется матрицей настройки

.

При с_i^J=1, элемент ЭС_i^j находится в проводящем состоянии. На рис.1.8,в элементы связи ЭС₁¹, ЭС₁⁴, ЭС₂⁵, ЭС₃², ЭС₃⁶, ЭС₄³ находятся в проводящем состоянии, что показано точкой на пересечении линий. Остальные элементы находятся в непроводящем состоянии. Матрица настройки

соответствует реализации

Z₆=2X₁-X₂.

Установка состояний ЭС₁¹¸ЭС₄⁶ в соответствии с другой матрицей настройки ||c_ij|| приводит к изменению функций ЦА. ЦА и ИС с такой структурой называются матичными и находят широкое применение. Они могут выпускаться серийно, что обуславливает их низкую стоимость. Снижаются затраты на проектирование и изготовление ЦА. Но сложность реализуемых функций ограничивается числом элементов ЦА.

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

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

Принцип последовательного выполнения операций обработки информации начал применяться в механических и электромеханических счетных машинах (арифмометрах и табуляторах) и нашел дальнейшее развитие в ЭВМ. Массовое применение этого принципа для построения разнообразных ЦА началось с момента изобретения микропроцессоров (МП) в 1971 г. И серийного выпуска микропроцессорных БИС. Удалось естественным образом разделить ЦА на функционально законченные универсальные модули, реализовать их в виде БИС и СБИС, создать стандартные средства объединения модулей.

Представление ЦА в виде совокупности управляющего (микропрограммного) и операционного автоматов было предложено академиком Виктором Михайловичем Глушковым, который основал и проработал долгие годы директором Института Кибернетики АН СССР в г. Киеве. В своей монографии “Синтез цифровых автоматов” (1963г.) и последующих работах В.М. Глушков провел глубокие теоретические исследования ЦА с такой структурой.

Общая структура ЦА с управлением последовательностью операций приведена на рис. 1.11 и включает операционное устройство (ОУ) и устройство управления (УУ) последовательностью операций.

Рис. 1.11

На МФЭ возложена реализация набора операций F={F₁,F ₂, …,F _k}, а элементы памяти ЭП₁, …,ЭП_N предназначены для временного хранения результатов выполнения операций, входных кодов Х₁, …,X_m и выходных кодов Z₁, …, Z_n. Операции в МФЭ могут выполняться над различными комбинациями Х₁, …,X_m и содержимого ЭП₁, …,ЭП_N.

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

К= <КОП,А,В.С>,

где КОП – код операции над А и В, выполняемой в МФЭ;

С – место размещения результата.

Например, выполнение команды < , X₁, X₂, ЭП₁> вызывает сложение кодов со входов Х₁, Х₂ и запись результата в элемент памяти ЭП₁. А и В выбираются управляемой схемой связей ОУ из множества Х₁, …, Х_m, ЭП₁, …, ЭП_N, а результат операций С схемой связей пересылается в один из элементов памяти ЭП₁, …, ЭП_N или на один из выходов Z₁, …, Z_n.

Для функции

Z₁=2X₁-X₂ 2X₃

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

K₁= < , X₁, X₃, ЭП₁>;

K₂=< ЭП₁, ЭП₁, ЭП₂>;

K=<-, ЭП₂, X₂, Z₁>.

Такая последовательность команд называется программой. В результате выполнения программы получаем требуемую функциональную зависимость между Z₁, …, Z_n и X₁, …, X_m.

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

Последовательность выполнения команд, увеличивает время реализации функций и тем больше, чем длиннее программа. А длинна программы зависит от сложности операций выполняемых МФЭ, числа элементов памяти, сложности схемы связей ОУ, т. е. от набора команд. Таким образом, при усложнении ОУ упрощается УУ (уменьшается число формируемых команд), уменьшается время реализации функций и наоборот. Но сложность МФЭ и сложность схемы связей ограничена.

Общее число N_k команд легко вычислить по формуле:

N_k=K×N_А×N_В×N_С,

где K – число операций;

N_À – число источников А;

N_В – число источников В;

N_С – число приемников результата С.

Уже при K=m=n=N=10 получаем N_k= 80 000.

При большом числе K, m, n и N управление ОУ становится очень сложным, число разрядов команды достигает десятков и сотен. С целью получения приемлемой сложности ОУ и УУ функции управления разделяются на два уровня (рис. 1.12).

1. Управление всеми доступными элементами ОУ происходит под действием наборов управляющих сигналов – микрокоманд, формируемых микропрограммными устройствами управления (МПУУ).

Рис. 1.12

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

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

Команды от ПУУ преобразуются в МПУУ в последовательность микрокоманд. Эта последовательность может изменяться в зависимости от признаков выполнения микрокоманд X_мк. Автоматы с такой структурой будем называть цифровыми автоматами с программным управлением.

Для ПУУ совокупность МПУУ и ОУ является псевдооперационным устройством с признаками X_K.

МПУУ часто используется самостоятельно в качестве контроллера, а совместно с ОУ – для построения ЦА средней сложности при повышенных требованиях к быстродействию. Для сохранения микрокоманд в МПУУ с гибкой логикой используется запоминающее устройство микрокоманд (ЗУМК). Считывания их в определенной последовательности с учетом признаков X_Мк выполняет БВМК – блок выборки микрокоманд (рис. 1.12). Автомат включающий МППУ и ОУ, назовем цифровым автоматом с микропрограммным управлением.

Структура современных ЦА с программным управлением приведена на рис. 1.13. По сравнению с ранее рассмотренной она имеет ряд особенностей, которые состоят в следующем.

Рис. 1.13

1. Схема связей ОУ упорядочена и представляет собой набор линий (шин), по которым различные элементы обмениваются данными. Такой набор линий и правил обмена по ним называется интерфейсом.

2. ПУУ включает блок выборки команд (БВК) и запоминающее устройство команд (ЗУК). Совокупность БВК, МПУУ, МФЭ, ограниченного набора элементов памяти ЭП₁, …,ЭП_l и внутренний интерфейс составляют центральное процессорное устройство (ЦПУ).

ЦПУ имеет интерфейс памяти и ввода-вывода, по которому производится считывание команд из ЗУК, обмен с ОЗУ и ПЗУ, ввод X₁, …, X_m и вывод Z₁, …, Z_n.

3. Информация со входов X₁, …,X_m с помощью устройств ввода УВв₁, …, УВв_mb вводится в ЦПУ и ОЗУ для дальнейшей обработки, а выходная информация из ЦПУ, ОЗУ или ПЗУ выводится на Z, ₁ …, Z_n через устройство вывода УВыв₁, …, УВыв_n. Такая структурная организация позволяет легко изменить число входов и выходов . На практике часто используются универсальные устройства ввода-вывода (УВВ), у которых каждая линия может быть настроена либо на ввод либо на вывод.

ЦПУ может быть выполнено на одном или нескольких кристаллах БИС. В этом случае оно будет называться микропроцессором. ЗУК, ОЗУ и ПЗУ, УВВ₁, …, УВВ_m, УВыв₁, …, УВыв_m представляют собой функционально законченные узлы и реализуются на серийных БИС.

Модульность структуры ЦА достигается благодаря унификации интерфейса, а функциональная гибкость обусловлена возможностью программирования и микропрограммирования путем смены программ в ЗУК и микропрограмм в ЗУМК, БИС и СБИС памяти позволяют хранить огромное число команд и микрокоманд.

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

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

Изменение соотношения между программной и схемной реализацией функций в ЦА позволяет оптимизировать сложность и быстродействие устройств. Реализация функций программными средствами позволяет значительно уменьшить сложность схем цифровых автоматов. Это обусловлено массовым выпуском БИС ЗУ, их низкой стоимостью и большой информационной емкостью, а также возможностью однокристальной реализации автоматов. Однако схемная реализация функций позволяет получить более высокое быстродействие ЦА.

ВЫВОДЫ К ГЛАВЕ 1

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

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

3. Закон функционирования ЦА с канонической структурой описывается двумя основными функциями – функцией переходов, определяющей порядок смены состояний автомата, и функций выходов, задающей порядок выдачи выходных сигналов в зависимости от состояния памяти и входных сигналов.

4. Решение задачи синтеза оптимальной структуры цифрового автомата существенно зависит от правильного выбора соотношения функций со схемой (аппаратной), программной или (и) микропрограммной реализацией. Программная реализация функций позволяет в большинстве случаев уменьшить сложность автомата, но про этом чаще всего (в отличие от схемной реализации) снижается быстродействие ЦА.

КОНТРОЛЬНЫЕ ВОПРОСЫ К ГЛАВЕ 1

1. Чем определяется число состояний цифрового автомата?

2. В чем отличие цифровых автоматов Мили и Мура?

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

4. В чем состоит физический смысл допущений, принимаемых при построении теории цифровых автоматов?

5. Каким образом задается математическое описание автомата?

6. По каким признакам могут классифицироваться цифровые устройства?

7. В чем состоит принципиальное отличие между: ЦА со схемной реализацией и ЦА с управлением последовательностью операций, автоматами с “жесткой” и “гибкой” логикой?

ЛИТЕРАТУРА К ГЛАВЕ 1

1.1. Глушков В.М. Синтез цифровых автоматов. – М.: Физматгиз, 1962.

1.2. Дискретные устройства АСУ. / Под ред. Тимонькина Г. Н., Харченко В. С. – Мо СССР, 1990.

1.3. Баранов С.И. синтез микропрограммных автоматов. – Л.: Энергия, 1974.

1.4. Майоров С.А., Новиков Г.И. Структура электронных вычислительных машин. Л.: Машиностроение, 1979.

1.5. Шевкопляс Б. В. Микропроцессорные структуры. Инженерные решения. – М.: Радио и связь, 1985.

1.6. Балашов Е. П. и др. Многофункциональный синтез систем. – М.: Радио и связь, 1985.

1.7. Балашов Е. П. др. Многофункциональные регулярные вычислительные структуры. – М.: Сов. Радио, 1978.

1.8. Каляев А. В. Микропроцессорные системы с программируемой архитектурой. – М.: Радио и связь, 1984.

1.9. Пупырев Е. И. Перестраиваемые автоматы и микропроцессорные системы. – М.: Наука, 1985.

ГЛАВА 2

В математической логике основными понятиями являются логическая переменная и логическая функция.

Логическими переменными называются знаки (символы), которые принимают различные значения из соответствующей области. Такие переменные будем обозначать, например, буквами латинского алфавита: x₁, x₂, …, x_i, или y₁,y₂, …, y_i, или z₁, z₂, …, z_k. Область значений переменных может быть различной: нуль и единица {0,1}; нуль, плюс единица и минус единица {0, 1,-1}; нуль, единица, два {0,1,2} и др. Если область значений логических переменных содержит два значения, то такие логические переменные называют двоичными или булевыми, если же она содержит три значения, то их называют троичными, а если она содержит четыре более значений, то их называют многозначными переменными. Будем рассматривать только двоичные (булевы) переменные и под выражением “двоичные переменные” будем понимать логические двоичные переменные.

Совокупности значений переменных образуют наборы значений переменных, или просто наборы. Наборы значений логических переменных можно представить в виде двоичных чисел или в виде эквивалентов двоичных чисел. Например, переменные x₁, x₂, x₃, x₄ в зависимости от принимаемых значений образуют наборы: 0000, 0001, 0010,0011,0100,0101,0110,0111,1000, …,1111.

В общем виде набор значений переменных запишем как

,

где (j=1,2, …,n) обозначает конкретное значение переменой x_j и равно либо 0, либо 1. Если каждая переменная принимает два значения, а число переменных равно n, то число различных наборов равно 2ⁿ . Переменные и наборы играют важную роль в понятии “логическая функция”.

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

Для обозначения логических функций будем пользоваться записями вида f(x), f(x_n, x_n-1, …, x₂, x₁), y_i(x), z(x), u(x) и другими, где в скобках указываются переменные, от которых зависит логическая функция.

Различные значения переменных логической функции образуют наборы значений этой функции. Наборы значений переменных зависят от порядка расположения переменных, поэтому для однозначного задания наборов введем порядок размещения переменных в наборе. Если не оговорено особо, переменные в наборе будем располагать справа налево в порядке возрастания индексов переменных. Например, набор w_i =1101 означает, что переменных в наборе четыре и переменные x₁=1, x₂=0, x₃= x₄=1.

Совокупность наборов, на которых определена логическая функция, образует область отправления (задания) этой функции. Для логической функции от n переменных эта область содержит 2 различных наборов. Множество значений, на которых определена логическая функция, образует область прибытия. Область прибытия булевых функций содержит два значения: “0” и “1”.

Определим число различных логических функций от n переменных. Из n переменных можно образовать 2ⁿ различных наборов.

На каждом наборе логическая функция может принимать значение либо 0, либо 1 независимо от ее значения на других наборах. Отсюда число различных логических функций определяется как произведение 2ⁿ чисел 2, т.е. N=2^{2 n} (таблица 2.1).

Таблица 2.1

Таблица соответствия логических функций, зависящих от n переменных

Число различных логических функций возрастает с увеличением числа переменных и уже для функций пяти переменных составит огромное число – 4 294 966 296.

Всякая функция от меньшего числа переменных автоматически входит в число функций от большего числа переменных. Логическая функция f(x_n, …, x₂,x₁,) существенно зависит от переменной x_i, если имеет место соотношение

f(x_n, …, x_{i 1}, 0, x_i-1, …, x₁)¹f(x_n, …, x_{i 1}, 1, x_i-1, …, x₁,).

В противном случае говорят, что функция f(x_n, …, x₂,x₁,) не зависит существенно от переменной x_i, т.е. x_i есть фиктивная переменная.

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

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

Наряду с функциями, значения которых определены на всех 2ⁿ наборах, нередко возникает необходимость рассмотрения функций, значения которых определены только для части наборов. Наборы переменных, на которых значение функции не определено, будем называть неопределенными наборами. Логические функции, значения которых определены только на части наборов переменных, будем называть неполностью определенными функциями. Значения функций на условных наборах могут выбираться произвольным образом. В связи с этим неполностью определенную логическую функцию можно рассматривать как семейство полностью определенных логических функций, отличающихся друг от друга значениями на условных наборах. Если логическая функция содержит k условных наборов, то ей соответствует семейство, состоящее из 2^k различных полностью определенных функций, рабочие и запрещенные наборы которых полностью совпадают.

2.2. Способы задания логической функции

Для задания логической функции необходимо указать однозначное соответствие между наборами переменных и значениями функции (0 или 1). Логические функции могут быть заданы:

– словесным описанием;

– таблицами соответствия;

– номерами единичных и нулевых (неопределенных) наборов;

– формулами (аналитическими выражениями).

При словесном описании логической функции должны быть перечислены совокупности единичных и нулевых (неопределенных) наборов или указаны их характерные свойства. Например, логическая функция трех переменных задана единичными и нулевыми наборами. Единичные наборы переменных содержат две или более переменных, равных единице (011, 110, 101, 111), а все остальные наборы (000, 001, 010, 100) являются нулевыми.

Задание логических функций таблицами соответствия может быть выполнено несколькими вариантами. Для задания логической функции строится таблица, число строк которой равно числу различных наборов значений переменных, а число столбцов равно n 1. Первые n столбцов обозначаются символами переменных от которых зависит функция, а (n 1)-й столбец обозначается символом функции. В каждую строку такой таблицы записываются набор значений переменных и соответствующее ему значение функции. Например, функция трех переменных z(x) задана таблицей соответствия 2.2. Такую таблицу называют одновходовой таблицей соответствия.

Таблица 2.2

Таблица соответствия полностью и неполностью определенных логических функций z(x) и u(x)

При задании неполностью определенных функций таблицами соответствия значения функции на условных наборах будем обозначать “-“ или “~” как показано в таблице соответствия 2.2 для логической функции u(x).

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

Более компактным табличным способом задания логических функций является использование двухвходовых таблиц соответствия. Для построения такой таблицы переменные, от которых зависит логическая функция, разделяются на две примерно равные группы. Для образования групп переменных определяются всевозможные наборы их значений. Строки таблицы в произвольном порядке обозначаются наборами переменных первой группы, а столбцы таблицы – наборами переменных второй группы. Каждая клетка такой таблицы соответствует одному набору значений переменных, от которых зависит функция. В каждой клетке таблицы проставляется значение функции на соответствующем ей наборе значений переменных. Количество клеток такой таблицы соответствует числу всевозможных наборов значений переменных. Примером двухуровневой таблицы является таблица 2.3 в которой задана неполностью определенная логическая функция трех переменных u(x).

Таблица 2.3

Двухвходовая таблица соответствия для логической функции u(x)

u(x)

Удобным способом задания логических функций является использование номеров единичных, нулевых или неопределенных наборов. Для этой цели любой набор будем рассматривать как представление целого неотрицательного числа в двоичной системе счисления, которая также оперирует с цифрами “0” и “1”. Целое число в двоичной системе счисления можно представить эквивалентным ему числом в десятичной или восьмеричной системах счисления. Эти числа будем называть номерами наборов в двоичной, восьмеричной или десятичной системах счисления, что позволит записывать в компактной форме наборы значений переменных логической функции. При этом будем полагать, что в двоичном числе младший разряд расположен справа. Например, набор 10011 может быть представлен десятичным числом

1×2⁴ 0×2³ 0×2² 1×2¹ 1×2⁰=19,

а набор 1110 – числом

1×2³ 1×2² 1×2¹ 0×2=14.

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

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

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

Для однозначного задания двоичного набора значений переменных необходимо указать его номер, систему счисления, в которой задан номер, порядок расположения переменных и размерность, т.е. количество переменных логических функций. Так, например, десятичному числу 25 соответствует набор 11001 при размерности 5 или набор 0011001 при размерности 7.

Условимся при задании логической функции номерами единичные наборы записывать в квадратных скобках, нулевые в круглых скобках, а неопределенные – в фигурных скобках. При задании логической функции номерами единичных и нулевых наборов первыми после квадратной скобки указываются номера единичных наборов, а затем в круглых скобках – номера нулевых наборов. За последней скобкой указывается основание системы счисления. Например логическая функция z(x) (таблица 2.2) может быть задана номерами единичных и нулевых наборов в виде

z(x₃, x_2, x₁)=[3, 5, 6, 7 (0, 1, 2, 4)]₁₀.

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

u(x₃, x_2, x₁)=[1, 5, {3, 4,6}]₁₀.

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

u(x₃, x_2, x₁)=[0, 2, 7 (3, 4, 6)]₁₀.

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

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

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

Рассмотрим эти функции.

При n=0 имеются две различных функции: f₀=0 и f₁=1. Функция f₀=0 называется константой 0, а функция f₁=1 называется константой 1.

При n=1 имеются четыре логические функции (таблица 2.4).

Таблица 2.4

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

Функции f₀(x) и f₃(x) фактически не зависят от x:

f₀(x)º0; f₃(x)º1,

т.е. совпадают с функциями нуля переменных.

Значение функции f₁(x) совпадает со значением переменной:

f₁(x)=x

Это функция повторения.

Значение функции f₂(x) противоположно (инверсно) значению переменной x:

f₂(x) = .

Функцию f₂(x) называют функцией отрицания (инверсией, функцией НЕ). Отметим, что для каждой функции одной переменной существует инверсная ей функция:

f₀(x) =`f<sub>3</sub>(x) ; f<sub>3</sub>(x) =`f₀(x);

f₁(x) =`f<sub>2</sub>(x); f<sub>2</sub>(x) =`f₁(x);

Таблица 2.5

Элементарные логические функции, зависящие от двух переменных

Логические функции двух переменных приведены в таблице 2.5. Очевидно, что функции

f₀(x) = 0; f₃(x) =`x<sub>2</sub> ; f<sub>5</sub>(x) =`x₁ ;

f₁₀(x)=x₁; f₁₂(x)=x₂; f₁₅(x)=1

являются элементарными функциями, зависящими от одной переменной. Это вырожденные функции. Остальные десять функций зависят от двух переменных. Функция f₈(x₁, x₂), принимающая значение 1 на наборе 11, а на остальных наборах равная 0, носит название конъюнкции x₁ и x₂ (логическая функция И). Для ее обозначения будем применять точку или вообще опускать всякий знак (символ) между переменными x₁ и x₂, т.е.

f₈(x₁, x₂)= x₁x₂.

Функция f₁₄(x₁, x₂), принимающая значение 1, когда хотя бы одна из переменных равна единице, носит название дизъюнкции x₁ и х₂ (логическая функция ИЛИ). Для ее обозначения будем применять символ “Ú” между переменными х₁ и х₂ т.е.

f₁₄(x₁x₂)= x₁Ú x₂.

Функция f₁(x₁, x₂), принимающая значение 1на наборе 00, а на остальных наборах равная 0, носит название функции Пирса или функции ИЛИ-НЕ. Для ее обозначения применяется символ ¯ между переменными х₁ и х₂ т.е.

f₁(x₁, x₂)= x₁ ¯ x₂.

Функция f₇(x₁, x₂), принимающая значение 0 на наборе 11, а на остальных наборах равная 1, носит название функции Шеффера, или функции И-НЕ. Для ее обозначения применяется символ / между переменными х₁ и х₂ т.е.

f₇(x₁, x₂)= x₁ / x₂.

Функция f₉(x₁, x₂), принимающая значение 1только тогда, когда значения х₁ и х₂ совпадают, носит название функции эквивалентности. Для ее обозначения используется символ ~ между переменными х₁ и х₂ т.е.

f₉(x₁, x₂)= x₁ ~ x₂.

Функция f₆(x₁, x₂), принимающая значение 1только тогда, когда значения х₁ и х₂ противоположны, носит название функции сложения по модулю два (неэквивалентности, неравнозначности). Для ее обозначения используется символ Å между переменными х₁ и х₂ т.е.

f₆(x₁, x₂)= x₁ Å x₂.

Функция f₁₁(x₁, x₂) и f₁₃(x₁, x₂) принимающие значение 0 только на наборах 01 или 10 соответственно, а на остальных наборах равные 1, носят название функции импликации х₂ в х₁ или х₁ и х₂. Для обозначения этих функций применяется символ “®”между переменными х₂ и х₁ или х₁ и х₂ т.е.

f₁₁(x₁, x₂)= x₂® x₁;

f₁₃(x₁, x₂)= x₁® x₂.

Функция f₂(x₁, x₂) и f₄(x₁, x₂) принимающие значения 1 только на наборах 10 или 01 соответственно, а на остальных наборах равные нулю, носят название функций запрета х₂ или х₁ и записываются следующим образом:

f₂(x₁, x₂)= x₁ x₂;

f₄(x₁, x₂)= x₂ x₁.

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

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

Функцию f_{k 1}(x), полученную из функций f₁(x), f₂(x), …, f_k(x), путем применения (возможно многократного) принципа суперпозиции, будем называть суперпозицией функций f₁(x), f₂(x), …, f_k(x). При этом для записи сложных функций, кроме введенных знаков, будем использовать скобки. Например имея элементарные функции

f₁(x)=x₁x₂;

f₂(x)=x₃Åx₄,

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

f₃(x)=x₁(x₃Åx₄);

f₄(x)= (x₁x₂)Åx₄.

Функция f₃(x) получена путем подстановки в функцию f₁(x) вместо переменной х₂ функции f₂(x). Функция f₄(x) получена из функции f₂(x) путем подстановки вместо переменной х₃ логической функции f₁(x).

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

Рассмотрим связи между некоторыми элементарными функциями.

Из таблицы 2.5 следует, что функция f₁(x) на всех наборах принимает значения, противоположные функции f₁₄(x).

Используя принцип суперпозиции, запишем

= =.

Приведем без пояснения некоторые широко применяемые соотношения, связывающие элементарные функции:

= ;

= ;

= ;

= ;

= ;

= ;

= ;

= ;

;

= .

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

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

Функционально полная система логических функций f₁(x), f₂(x), …,f_s(x) называется минимальной, если удаление из нее хотя бы одной функции превращает систему в неполную. При рассмотрении совокупности логических функций f₁(x), f₂(x), …,f_s(x) возникает вопрос, как установить, является ли данная совокупность функций полной. Ответ на этот вопрос дает теорема о функциональной полноте (теорема Поста-Яблонского), которая устанавливает необходимые и достаточные условия функциональной полноты произвольной совокупности логических функций [1].

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

– функция Шеффера (И-НЕ);

– функция Пирса (ИЛИ-НЕ);

– функция И и НЕ;

– функция ИЛИ и НЕ;

– функция импликации и константы 0 и т.д.

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

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

– равнозначность и дизъюнкция;

– импликация;

– сумма по модулю два и дизъюнкция.

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

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

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

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

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

С другой стороны, увеличение числа различных логических функций, реализуемых элементами, приводит к увеличению стоимости выпускаемых систем логических элементов. Отсюда следует, что существует оптимальное количество различных элементов, входящих в систему, позволяющее получить цифровые устройства минимальной стоимости. В настоящее время состав функционально полных систем логических элементов, выпускаемых промышленностью, определяется из опыта проектирования цифровых устройств, так как точных методов определения оптимальных совокупностей логических элементов не найдено. При начертании схем цифровых устройств используются условные графические обозначения логических элементов, которые установлены ГОСТом ЕСКД 2.743-82. На рис. 2.1 приведены условные графические обозначения наиболее распространенных логических элементов. Размеры

Рис. 2.1

логических элементов на схеме определяются ГОСТ и варьируются в зависимости от числа входов, выходов элементов и формата чертежа.

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

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

В настоящее время отечественной промышленностью выпускается множество серий цифровых интегральных микросхем. Типичным представителем цифровых интегральных микросхем является серия К155. Интегральные микросхемы серии К155 являются потенциальными транзистор-транзисторными схемами. В состав серии входят логические элементы, реализующие логические функции И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ, И-ИЛИ-НЕ и др. Некоторые из этих элементов входят в состав серии в виде нескольких модификаций, отличающихся числом схем в одном корпусе, количеством входов на одну схему и нагрузочными характеристиками. Помимо указанных логических элементов в состав серии входят расширители входов, элементы памяти и более сложные цифровые устройства [2]. Элементы И-НЕ, входящие в состав серии, имеют условные обозначения ЛА, перед которыми указывается номер серии, а после – номер модификации, например: К155ЛА1, К155ЛА2 и др. В основу всех модификаций элемента И-НЕ положена одна и та же схема со сложным инвертором.

На рис. 2.2,а приведена принципиальная электрическая схема элемента К155ЛА1. На рис.2.2,б показано условное графическое обозначение этого элемента. Каждый элемент содержит две одинаковые трехвходовые логические схемы И-НЕ, имеющие два дополнительных вывода, обеспечивающих подключение схем-расширителей. Логическая схема включает микроэмиттерный транзистор V1 который вместе с резистором R1, образует логическую схему И. Транзисторы V2, V3, V4, V5 и резисторы R2, R3, R4, образуют схему сложного инвертора.

Рис. 2.2

Рассмотрим работу схемы.

Если напряжение на одном из входов схемы не превышает 0,8 В (т.е. на один из входов схемы подан низкий потенциал), то весь ток, текущий через резистор R1, ответвляется на входную цепь схемы. При этом напряжение на базе транзистора V2 составляет несколько десятков милливольт, (т.е. оно равно сумме падений напряжений на переходе коллектор-эмиттер выходного транзистора предыдущего каскада). Поэтому транзисторы V2 и V5 закрыты, а транзистор V3 открыт. Выходное напряжение схемы в этом случае близко к напряжению питания (³2,3 В).

Если на все входы многоэмиттерного транзистора V1 подан высокий потенциал (³1,7 В), то ток, протекающий через резистор R1, ответвляется через базу транзистора V2. Поэтому транзисторы V2 и V5 открыты, а транзистор V3 закрыт, так как напряжение между коллекторами транзисторов V2 и V5 оказывается ниже, чем суммарный порог отпирания транзисторов V3 и V4. Транзистор V4 включен в схему в качестве смещающегося диода. В этом случае через коллекторно-эмиттерный переход транзистора протекают только входные токи схем нагрузок.

Основное назначение транзистора V4 состоит в надежном запирании транзистора V3 при насыщенном состоянии транзисторов V2, V5. Это позволяет уменьшить мощность, потребляемую схемой в этом режиме, а также снизить требования к коэффициенту усиления транзистора V5.

Одна из важных особенностей схемы заключается в том, что при переключении схемы во время переходного процесса оказываются одновременно открытыми транзисторы V2, V3, V4, V5. Это приводит к увеличению тока в цепи питания и потребляемой мощности в момент переключения. Поэтому логические устройства, построенные на этих элементах, в статическом состоянии потребляют меньшую мощность, чем при переключении.

С помощью рассмотренного элемента могут быть реализованы логические функции типа

,

где b_i – конъюнкция, реализуемая схемой расширителя, при подключении его к основной схеме;

l – число подключенных расширителей.

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

Элементы-расширители имеют условное обозначение ЛП и самостоятельно логическую функцию не реализуют. Элементы-расширители строятся на базе многоэмиттерного транзистора и при подключении ко входам А, В основных элементов реализуют конъюнкции входных сигналов.

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

ВЫВОДЫ К ГЛАВЕ 2

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

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

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

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

КОНТРОЛЬНЫЕ ВОПРОСЫ К ГЛАВЕ 2

1. Какая функция называется двоичной логической функцией?

2. Какие типы наборов переменных имеет логическая функция и каково их суммарное число?

3. Сколько логических функций существует для трех логических переменных? Приведите пример вырожденной логической функции трех переменных.

4. Что можно сказать о полностью определенных логических функциях трех переменных f₁ и f₂, заданных таблицами 2.6 и 2.7?

Таблица 2.6

Таблица соответствия логической функции f₁(x)

Таблица 2.7

Таблица соответствия логической функции f₂(x)

5. Запишите в числовом виде логическую функцию z(x), заданную таблицей 2.8.

Таблица 2.8

Двухходовая таблица соответствия логической функции z(x)

Z(x)

6. В чем состоит практическое значение теоремы Поста-Яблонского?

7. Каким образом на практике реализуются элементарные логические функции одной переменной?

8. Определите значение выходного сигнала z₁ логического элемента, показанного на рис. 2.2,б, если x₁=x₂=1, x₃=0 а с помощью расширителя (входы А и В) реализуется конъюнкция b₁=1.

ЛИТЕРАТУРА К ГЛАВЕ 2

2.1. Яблонский С. В. Введение в дискретную математику. – М.: Наука, 1979.

2.2. Корнейчук В. И., Тарасенко В.П., Мишинский Ю. Н. Вычислительные устройства на микросхемах.- Киев: Техника, 1986.

2.3. Дискретные устройства АСУ. / Под ред. Тимонькина Г. Н., Харченко В. С. – Мо СССР, 1990.

2.4. Применение интегральных микросхем в электронной вычислительной технике: Справ./Под ред. Б. Н. Файзулаева, Б.В. Тарабрина. – М.: Радио и связь, 1986.

ГЛАВА 3

ПРЕОБРАЗОВАНИЕ ЛОГИЧЕСКИХ ФУНКЦИЙ

Одним из основных способов задания логических функций является их представление в виде аналитических выражений (формул). Достоинством такого способа задания является возможность проведения эквивалентных преобразований логических функций. Во введенной алгебре (3.1) основными аналитическими формами представления логических функций являются дизъюнктивная и конъюнктивная формы.

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

Предварительно введем понятие элементарной конъюнкции.

Элементарной конъюнкцией называется выражение вида

,

содержащее множество попарно различных переменных или их отрицаний. При этом под х поднимается либо сама переменная х, либо ее отрицание х.

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

;

представляют собой дизъюнкции элементарных конъюнкций. Следовательно, они записаны в дизъюнктивной форме.

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

– использования правил инверсии, если операция отрицания применена к логическому выражению;

– раскрытия скобок;

– исключения в конъюнкциях повторяющихся переменных или их отрицаний;

– удаление всех одинаковых элементарных конъюнкций, кроме одной;

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

Справедливость перечисленных операций вытекает из основных аксиом и тождественных соотношений алгебры логики.

Пример 3.1. Преобразуем к дизъюнктивной нормальной форме логическую функцию: .

Используем правило инверсии. Тогда

.

Раскроем в полученном выражении скобки

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

.

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

Преобразование ДНФ к совершенной форме ДНФ осуществляется путем выполнения следующих операций:

– умножения каждой элементарной конъюнкции на дизъюнкции переменных и их отрицаний, если они не входят в данную элементарную конъюнкцию;

– раскрытия скобок;

– удаления всех одинаковых элементарных конъюнкций, кроме одной.

Пример 3.2.Преобразуем к СДНФ логическую функцию

.

Так как рассматриваемая функция зависит от трех переменных х₁, х₂, х₃, первую конъюнкцию умножим на выражение , а вторую – на :

.

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

.

В СДНФ может быть представлена любая логическая функция, кроме тождественно равной нулю (f(x)º0).

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

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

Логическая функция константы единицы в СДНФ представляется дизъюнкцией 2ⁿ конституент единицы.

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

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

Пример 3.3.Для логической функции z(х), заданной таблицей соответствия 2.2, определим совершенную дизъюнктивную нормальную форму.

Для четвертой строки таблицы, которая соответствует единичному набору функции 011, найдем конституенту единицы `х₃х₂х₁.

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

.

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

Введем понятие элементарной дизъюнкции.

Элементарной дизъюнкцией называется выражение вида

,

содержащее множество попарно различных переменных или их отрицаний.

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

представляют собой конъюнкции элементарных дизъюнкций. Следовательно, они записаны в конъюнктивной нормальной форме.

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

– использования правила инверсии, если операция отрицания применена к логическому выражению;

-использования аксиомы дистрибутивности относительно умножения:

;

-использования операции поглощения:

;

– исключения в дизъюнкциях повторяющихся переменных или их отрицаний;

– удаления всех одинаковых элементарных дизъюнкций, кроме одной;

-удаления всех дизъюнкций, в которые одновременно входят переменная и ее отрицание.

Справедливость перечисленных операций вытекает из основных аксиом и тождественных соотношений алгебры логики.

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

Преобразование КНФ к совершенной КНФ осуществляется путем выполнения следующих операций:

– прибавления к каждой элементарной дизъюнкции конъюнкций переменных и их отрицаний, если они не входят в данную элементарную дизъюнкцию;

– использования аксиомы дистрибутивности;

-удаление всех одинаковых элементарных дизъюнкций, кроме одной.

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

тождественно равной единице ( ). Отличительным свойством совершенной КНФ является то, что представление в ней логической функции единственно.

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

Логическая функция константа нуля в совершенной КНФ представляется конъюнкцией 2nконституент нуля. Сформулируем правило составления СКНФ логической функции по таблице соответствия.

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

Пример 3.4.Для логической функции z(x), заданной таблицей соответствия 2.2, определим совершенную конъюнктивную форму.

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

.

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

При построении цифровых устройств, реализующих заданные

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

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

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

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

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

3.4.1. Основные понятия и определения

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

Рассмотрим три полностью определенные функции f(x), g(x) и d(x). Функция f(x) определена на множестве единичных наборов M₁[f(x)] и множестве нулевых наборов M₀[f(x)].

Функция g(x) определена на множестве единичных наборов M₁[g(x)], а функция d(x) – на множестве нулевых наборов M₀[d(x)].

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

M₁[g(x)]Í M₁[f(x)].

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

M₀[d(x)]Í M₀[f(x)].

Например, логическая функция g(x)= является импликантой логической функции

,

так как множество M₁[g(x)] составляют наборы 100 110, которые входят в множество M₁[f(x)]. Аналогично логическая функция является имплицентой этой же логической функции f(x), так как множество M₀[d(x)]составляют наборы 001 и 011, которые входят во множество M₀[f(x)].

Простой импликантой функции f(x) называется любая элементарная функция g(x), являющаяся импликантой этой функции и обладающая тем свойством, что никакая ее собственная часть (т.е. конъюнкция, получаемая из элементарной путем исключения одной или нескольких переменных или их отрицаний) уже не является импликантой данной функции.

Следует обратить внимание, что простой импликантой может быть только элементарная конъюнкция. Докажем это утверждение.

Пусть есть импликанта функции f(x), т.е.

M₁[g(x)]Í M₁[f(x)],

где

M₁[g(x)]= M₁[g1(x)] .

Отсюда следует, что

M₁[g1(x)]Í M₁[f(x)];

M₁[g2(x)]Í M₁[f(x)].

Следовательно, функции и также являются импликантами функции f(x), а поэтому функция g(x) не может быть простой импликантой. Например, для логической функции

функция является простой импликантой, так как после исключения из переменной получим импликанту .

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

,

функция является простой имплицентой, а функция не является простой имплицентой, так как после исключения из переменной получим более короткую имплиценту ( .

Предположим, что на некотором наборе значений переменных логическая функция принимает значение , равное единице (нулю). Условимся, что эта 1 (0) накрывается импликантой g(x) (имплицентой d(x) функции , если на наборе импликанта g(x) (имплицента ) также равна единице (нулю).

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

Пусть система импликант , ,. . . , является полной системой импликант функции . Тогда

. . . = .

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

. . . = ,

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

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

простыми импликантами являются

;

;

,

а сокращенная ДНФ этой функции имеет вид

= .

Для этой же функции простыми имлицентами являются

;

;

,

а сокращенная КНФ этой функции имеет вид

.

Представление любой логической функции в виде сокращенной ДНФ (КНФ) является единственным.

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

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

=

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

;

,

а ТДНФ этой функции имеет вид

= .

Приведенная система имплицент этой функции включает:

;

,

а ТКНФ этой функции имеет вид

.

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

При решении практических задач синтеза дискретных устройств широко

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

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

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

Простой импликантой неполностью определенной функции будем называть всякую простую импликанту функции .

Простой имплицентой неполностью определенной функции будем называть всякую простую имплиценту функции .

Простую импликанту (имплиценту) неполностью определенной функции будем называть существенной, если она накрывает хотя бы один единичный (нулевой) набор этой функции. Например, неполностью определенная функция [1, 2, 3, 6, 7, 10, 12 (11, 13, 16, 17)] содержит условные наборы {0, 4, 5, 14, 15} . Тогда [0, 1, 2, 3, 4, 5, 6, 7, 10, 12, 14, 15 (11, 13, 16, 17)] , а [1, 2, 3, 6, 7, 10, 12, (0, 4, 5, 11, 13, 14, 15, 16, 17)] .

Для функции простыми имликантами являются

;

;

.

Эти же конъюнкции являются простыми импликантами функции , однако импликанта является несущественной, так как накрывает только неопределенные наборы 4, 5, 14, 15 функции .

Для функции простыми имплицентами являются

; ;

; .

Эти же дизъюнкции являются простыми имплицентами функции , однако имплиценты и являются несущественными, так как накрывают только неопределенные наборы функции .

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

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

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

= = .

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

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

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

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

[01, 02, 04, 05, 13, 17 {9, 10, 14}] .

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

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

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

При решении задач минимизации логических функций важную роль играют понятия простой импликанты (имплиценты) логической функции. Установим эквивалентные им геометрические образы (контуры) на карте Карно. Обратимся к логической функции . Конъюнкции и являются импликантами этой функции. Определим рабочие и условные наборы функции , которые накрываются этими импликантами, и построим на карте Карно (рис. 3.1,а) контуры, которые охватывают клетки, соответствующие этим наборам. Импликанте соответствует контур 1, а импликанте – контур2.

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

Если импликантой логической функции является элементарная конъюнкция, то в соответствующий ей контур войдут клетки соседних наборов, допускающих склеивание. Такие контуры мы будем называть правильными контурами карты Карно. Правильные контуры могут включать 1, 2, 4, . . . , 2 клеток карты Карно, соответствующих единичным или единичным и неопределенным наборам логической функции. Соседним клеткам карты Карно поставлены в соответствие соседние наборы и поэтому на картах Карно легко различаются правильные контуры. На рис. 3.1,б показаны примеры правильных 1, 2, 4 и 8-клеточных правильных контуров для карты Карно, соответствующей логической функции пяти переменных.

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

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

а б в

Рис. 3.2 Типичные двухклеточные (а), четырехклеточные (б) и восьмиклеточные (в) контуры на картах Карно четырех переменных

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

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

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

Пример 3.5.Определим выражение для простой импликанты, соответствующей максимальному правильному контуру 1 (рис. 3.2,б). В пределах рассматриваемого контура сохраняют свои значения переменные и . Следовательно, простая импликанта имеет вид

.

Проведя аналогичные рассуждения для контуров 2 и 3 (рис. 3.2,б), простые импликанты можно представить в виде

;

.

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

Правило получения сокращенной и тупиковой дизъюнктивных нормальных форм состоит в следующем.

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

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

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

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

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

Пример 3.6.Определим тупиковые ДНФ логической функции, заданной на карте Карно (рис. 3.3, а). На рис. 3.3,б,в показаны карты Карно, на которых выделены совокупности контуров, соответствующие двум различным тупиковым формам логической функции. Найдем соответствующие выделенным контурам простые импликанты и запишем две тупиковые формы данной логической функции:

= ;

= .

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

а б в

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

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

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

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

а б

Рис. 3.4. Совокупности максимальных правильных контуров, соответствующие

простым имплицентам , (а) и функции (б)

Соответствующие им простые импликанты имеют вид

;

.

Сформулируем правило получения сокращенной и тупиковой конъюнктивных нормальной форм.

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

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

Пример 3.7.Определим тупиковую КНФ логической функции, заданной на карте Карно (рис. 3.1, б).

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

= .

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

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

Для определения всех приведенных систем простых импликант широко используются импликантные (имплицентные) таблицы.

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

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

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

Пример 3.8.Определим тупиковую ДНФ логической функции, для которой задана импликантная таблица 3.1.

Таблица 3.1

Импликантная таблица к примеру 3.8

В рассматриваемом примере только один единичный набор 10 покрывается одной импликантой А. Следовательно, импликанта А образует ядро логической функции. Оставшиеся единичные наборы 57, 62, 76, 77 покрываются парами импликант С, F или Е, F. Перечисленные пары простых импликант образуют минимальные совокупности, покрывающие указанные единичные наборы, так как исключение любой импликанты приводит к тому, что часть наборов окажется непокрытой. Таким образом, в результате анализа таблицы 3.1 определены две приведенные системы простых импликант логической функции :

A, C, F и A, E, F.

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

;

.

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

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

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

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

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

3. Полученное таким образом выражение Ф преобразуется в соответствии с аксиомами и тождествами алгебры логики к дизъюнктивной нормальной форме.

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

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

Ф= .

Преобразуем это выражение к виду

Ф= .

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

;

;

;

.

Сравним полученные тупиковые ДНФ функции найдем ее минимальную ДНФ:

.

Пример 3.10.Определим минимальную КНФ логической функции, заданной имплицентной таблицей 3.2.

Таблица 3.2

Имплицентная таблица к примеру 3.10

Для отыскания всех тупиковых КНФ логической функции по имплицентной таблице составим логическое выражение и преобразуем его:

Ф= .

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

Тупиковые КНФ функции имеют вид:

;

;

;

.

Сравнив полученные тупиковые КНФ логической функции по числу букв, убедимся, что она имеет две минимальные формы: и .

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

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

ВЫВОДЫ К ГЛАВЕ 3

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

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

3. Существует большое число методов минимизации логических функций, отличающихся исходной формой представления, схемой преобразования и формой представления результата. Область целесообразного применения методов минимизации, позволяющих вручную получить абсолютно минимальные ДНФ или КНФ логических функций (методы карт Карно, решетки соседних чисел, таблично-аналитический метод и др.), ограничивается функциями, зависящими от 5-6 переменных. Для решения задач минимизации функций большего числа переменных могут быть использованы метод поразрядного сравнения [3.3] или машинные алгоритмы реализации различных методов.

КОНТРОЛЬНЫЕ ВОПРОСЫ К ГЛАВЕ 3

1. Докажите с помощью аксиом алгебры логики справедливость тождественных соотношений

,

.

2. Чем отличается ДНФ от совершенной ДНФ ?

3. Чем отличается импликанта от простой импликанты ?

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

5. Перечислите основные этапы минимизации логических функций.

6. Как связаны длина простой импликанты (имплиценты) и размер максимального правильного контура на карте Карно ?

7. Чем отличаются алгоритмы нахождения сокращенной и тупиковой формы функции на карте Карно ?

8. В каком виде должна быть задана функция для ее минимизации с помощью импликантных таблиц ?

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

ЛИТЕРАТУРА К ГЛАВЕ 3

3.1. Г л у ш к о в В. М. Синтез цифровых автоматов М.; Физматгиз, 1962..

3.2. П о с п е л о в Д. А. Логические методы анализа и синтеза схем М.; Энергия, 1974.

3.3. З а к р е в с к и й Д. А. Логический синтез каскадных схем М; Наука, 1981.

3.4. Т и м о н ь к и н Г. Н., Х а р ч е н к о В. С. Математические основы теории дискретных устройств МО СССР, 1981.