Что такое функционально полная система логических элементов

13

Большая Энциклопедия Нефти и Газа

Функционально полная система логических элементов — это такой набор элементов, используя который можно реализовать любую сколь угодно сложную логическую функцию. Поскольку любая логическая функция представляет собой комбинацию простейших функций — дизъюнкции, конъюнкции и инверсии, то набор из элементов трех типов, реализующих соответственно функции И, ИЛИ и НЕ, естественно, является функционально полным. Например, функцию ab — — ab можно реализовать с помощью двух ячеек НЕ ( они нужны, чтобы получить инверсии а и Ь), двух ячеек И, необходимых для того, чтобы получить логические произведения аЪ и ab, и ячейки ИЛИ, суммирующей эти произведения.  [1]

Функционально полная система логических элементов — это такой набор элементов, используя который можно реализовать любую сколь угодно сложную логическую функцию. Ввиду того, что 1 любая логическая функция представляет собой комбинацию простейших функций — дизъюнкции, конъюнкции и инверсии, набор из элементов ИЛИ, И, НЕ является функционально полным.  [3]

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

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

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

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

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

Анализ и синтез электронных узлов и операционных блоков ЦВМ и ВС на основе выбранного базиса функционально полной системы логических элементов . Исходными данными для этого этапа разработки служат характеристики устройств ЦВМ и ВС, определенные во время синтеза их логических структур, а также информация о доступной электронно-технологической базе их производства.  [10]

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

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

Так как любая сложная логическая функция может быть выражена с помощью логических — функций ( И, ИЛИ, НЕ), то система-функций ( И, ИЛИ, НЕ) называется функционально полной системой логических элементов . Количество типов вспомогательных элементов выбирается с учетом особенностей логических элементов, используемых в ЭЦВМ. Например, в управляющих ЭЦВМ в систему элементов входит некоторое число аналоговых элементов. Это связано с передачей и обработкой информации представленной в непрерывной форме.  [13]

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

1.3. Функционально полные системы логических функций (базис)

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

Базис — это полная система логических функций, с помощью которой можно описать сколь угодно сложный закон функционирования. К базису относится система функций И, ИЛИ, НЕ (базис 1), свойства которого были изучены Булем. Базисами являются также системы, содержащие функции И, НЕ (базис 2), ИЛИ, НЕ (базис 3), состояние из функций Шеффера И — НЕ (Базис 4) и функции Пирса ИЛИ — НЕ (базис 5). Это перечисление показывает, что базисы могут быть избыточными (базис 1) и минимальными (базисы 4,5).

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

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

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

Например, функция f (X₁,X₂, . Xn) = X₁ + X₂ является минимальной формой, и наоборот, функция X₁ + ₁X₂ может быть упрощена, если к этому выражению применить второй распределительный закон, т.е. ₁ + X₁X₂ = (₁ + X₁)(X₁ + X₂) = X₁ + X₂.

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

1.4. Основные законы и эквивалентности для логических операций

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

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

В алгебре логики определено отношение эквивалентности (=), которое удовлетворяет следующим свойствам:

Х = Х — рефлексивность; если X = Y, то Y = X — симметричность; если X = Y, Y = Z, то X = Z — транзитивность. Из отношения эквивалентности следует принцип подстановки: если X = Y, то в любой формуле, содержащей X, вместо X можно подставить Y и будет получена эквивалентная формула.

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

Используя основные положения алгебры логики, нетрудно убедиться в справедливости следующих аксиом. Пусть Х — некоторая логическая переменная X = (0,1). Тогда:

1. X = , что означает возможность исключения из логического выражения всех членов, имеющих двойное отрицание, заменив их исходной величиной.

2

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

3. Из таблицы истинности для логического сложения (+,), логического умножения (∙,) и логического отрицания () можно получить следующие аксиомы:

Функциональная полнота системы. Понятие базиса и базисного элемента

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

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

Аналогично любой логический элемент можно реализовать на элементах ИЛИ – НЕ и И-НЕ

Этот факт позволяет считать элементы Шеффера и Пирса базисными

Входная характеристика позволяет рассчитать условия согласования при подключении к входу какого – либо источника сигнала; передаточная – определяет порог срабатывания (значение напряжений, соответствующих логическим «1 и 0», и помехоустойчивость при работе друг на друга

К основным параметрам ЛИС относятся:

1. Быстродействие – время реакции на изменение сигнала на входе.

2. Коэффициент объединения по входу К_ОБ – число входов, с помощью которых реализуется логическая функция. ().

3. Коэффициент разветвления по выходу – Характеризует нагрузочную способность и показывает

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

4. Помехоустойчивость — максимальное значение помехи на входе, при которой сохраняется нормальная

5. Потребляемая мощность – мощность, потребляемая в состоянии «1» и «0».

Типы логик по виду схемотехнической реализации

Транзисторно – резисторная логика

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

Эмиттерно связанной логики (ЭСЛ).

Серия обладает высоким быстродействием, т.к. транзисторы в схеме работают в ненасыщенном режиме..

малое выходное сопротивление обеспечивает согласование выходных и входных уровней логических элементов при их совместной работе и возможность непосредственно подавать сигнал в кабель с волновым сопротивлением 50 Ом. Однако плохо стыкуется с элементами серии ТТЛ. Широкого применения не нашла

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

В настоящий момент наиболее широкое применение приобрели микросхемы ТТЛ с диодами Шотки

(ТТЛШ) и микросхемы на МДП структурах.. последние делятся на одноканальные, в которых и МДП транзистор и МДП резистор имеют канал одного «р» или «n» типа, и комплементарные, в которых используется пара МДП транзисторов с каналами разного типа. Последние предпочтительнее, так как их отличает высокая технологичность, малая потребляемая мощность и высокая степень интеграции

Технология производства транзисторов с р- n переходом и транзисторов МДП структуры похожи, на

число операций при изготовлении транзисторов с МДП структурой меньше. Это сказывается на стоимости

микросхем КМДП серии в лучшую сторону.

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:

Функционально полные системы логических функций

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

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

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

f = х₁ + х₂ = =

В наборе (ИЛИ, НЕ) функцию И можно выполнить через операции ИЛИ и НЕ следующим образом: f = х₁ + х₂ = = .

Таким образом, набор функций (И, ИЛИ, НЕ) обладает избыточностью.

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

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

Например, ЛФ f = ₃ + х₃ в соответствии с описанными действиями при­водится к виду

f = =

По этому выражению логическая функция реализуется на элементах И—НЕ в соответствии с рис. 3.8.

Для реализации ЛФ в базисе ИЛИ—НЕ необходимо записать её сначало в КНФ. Выполнив далее двойное отрицание и применив закон отрицания, получим искомую форму.

Например, ЛФ f = (х₁+ ₂)( ₁ + х₃)( ₁+ х₂) в соответствии с этим примет вид

f = =

По этому выражению логическая функция реализуется на элементах ИЛИ—НЕ в соответствии с рис. 3.9.

3.3.1 Метод непосредственных преобразований

Метод Карно-Вейча

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

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

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

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

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

3.3.1 Метод непосредственных преобразований

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

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

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

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

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

Метод Квайна применяется к функциям, задан­ным в СДНФ (возможно задание и в СКНФ), и проводится, как правило, в два этапа.

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

Например, конъюнкции _{1 2}х_{3 4}, и ₁х₂х_{3 4} имеют общую часть А = ₁х_{3 4} и склеиваются по переменной х₂. В результате склеивания получим из конъюнкций ранга п=4, конъюнкции ₁х_{3 4}, и ₁х_{3 4} ранга п — 1 = 3.

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

Результатом выполнения последовательности попарного сравнения и склеивания конъюнкций ранга п является группа конъюнкций ранга п —1 и непомеченные конъюнкции ранга г. Непомеченные конъюнкции ранга п не участ­вовали в склеивании, следовательно, являются простыми импликантами и включаются в сокращенную ДНФ.

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

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

Рассмотрим реализацию первого этапа на примере функцииЛФ f

f = + + + + (3.5)

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

Анализируя в выражении всевозможные пары конъюнкций 1-2, 1-3, 1-4, 1-5, 2-3, 2-4, 2-5, 3-4, 3-5, 4-5, находим, что операция склеивания выпол­няется между парами 1-3 по х₁, 2-5 по х₁, 3-4 по х₃, 4-5 по х₂.

Таким образом, все конъюнкции исходной СДНФ участвуют в склеивании и помечаются подчеркиванием. 1 2 3 4

Теперь исходная СДНФ (3.5) записывается в виде f = _{2 3} + х₂х₃ + х_{1 2} + х₁x₃. (3.6)

Продолжая для выражения (3.6) процедуру склеивания, сравниваем попарно конъюнкции 1-2, 1-3, 1-4, 2-3, 2-4 и 3-4. Эти пары конъюнкций между собой не скле­иваются. Поэтому полученная запись ЛФ (3.6) представ­ляет собой сокращенную ДНФ исходной ЛФ (3.5), содер­жащей только простые импликанты.

Второй этап заключается в переходе от сокращенной ДНФ к тупиковым ДНФ и выборе среди них МДНФ.

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

Воз­можны случаи, когда в сокращенной форме нет лишних простых импликант. Тогда сокращенная ДНФ является тупиковой.

Для выявления лишних простых импликант строится импликантная матрица, которая называется также матри­цей (таблицей) покрытий. Каждая строка импликантной матрицы соответствует одной простой импликанте, а столбцы — конституантам единицы, которыми они и помечаются. Для рассматриваемого примера импли­кантная матрица приведена в табл. 3.14.

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

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

Например, простая импликанта _{2 3} входящая в сокращенную ДНФ (3.6) рассматриваемого примера, является собственной частью конституант единиц и , и поэтому в строке с данной простой импли­кантой (табл. 3.13) поставлены две пометки X в соответ­ствующих колонках. Аналогично размечены другие стро­ки табл. 3.13.

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

-В импликантной таблице условно вычеркивается строка с проверяемой простой импликан­той вместе с соответствующими пометками в строке.

-Если при этом окажется, что в каждом столбце импли­кантной таблицы остается, хотя бы по одной пометке, проверяемая импликанта является лишней и ее следует удалить.

-Оставшиеся простые импликанты покрывают все единичные значения ЛФ.

-Испытание каждой последую­щей простой импликанты возможно лишь после удаления уже выявленных лишних простых импликант.

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

Из табл. 3.13 видно, что только простая импликанта 1 обеспечивает единичное значение ЛФ на наборе 000, а импликанта 2 — на наборе 011 (соответствующие этим наборам столбцы обозначены конституантами единицы и ), поэтому эти простые импликанты обя­зательно войдут во все тупиковые ДНФ.

Простую импликанту 3 можно считать лишней. Однако, если ее сохра­нить, лишней можно считать простую импликанту 4.

Таким образом, для ЛФ возможны две тупиковые формы:

f_1т = />₂ />₃ + х₂х₃ + х₁x₃, (3.7)

в которую не включена лишняя импликанта х_{1 2}

и f_2т = _{2 3} + х₂х₃ + х_{1 2}, (3.8)

в которую не вошла лишняя импликанта x₁x₃.

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

Например, можно считать f_min = f_1т = />₂ />₃ + х₂х₃ + х₁ x₃.

Эта ЛФ реализует­ся схемой с ценой С = 9 (3 х 2 + 3 = 9).

Пример 4. Логическую функцию F в виде СДНФ F = х₂ +х₁ +х₁ х₃+х₁х₂ +x₁x₂x₃ можно минимизировать следующим образом:

1. Добавим к данной функции слагаемое х₁х₂ , которое уже есть в данной функции, используя правило 3 (x ∙ x = x).

F = х₂ + х₁ + х₁ х₃ +х₁х₂ + x₁x₂x₃ + х₁х₂

2. Применим метод склеивания (правило 11) к одинаково подчеркнутым элементарным конъюнкциям (x ∙ y + ∙ y = y):

Для х₁ и х₁ х₃ по х₃ -получим х₁

Для х₂ и х₁х₂ х₁ -получим х₂ ;

Для х₁х₂ и x₁x₂x₃ по х₃ -получим x₁x₂.

Результат склеивания: F = х₂ + х₁ + x₁x₂

3. Применим тот же метод склеивания для двух последних элементарных конъюнкций:

Для х₁ и x₁x₂ по х₂ -получим х₁

Окончательный результат: Fmin =F_T = х₂ + x₁

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

Пример5. Найти минимальную форму функции, заданной СДНФ

F(a, b,c) =а c + c + + + ab = abc.

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

F(a,b,c) = + c + ac + ab + b + .

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

Очевидно, что анализируемой функции отвечают две минимальных нормаль­ных формы F₂ (a,b,c) и F₃

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

1. Сначала к членам СКНФ применяют операцию полного склеивания.

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

3. Приводят подобные члены и применяют операцию поглощения.

4. Полученную таким способом ДНФ минимизируют в указанном выше по­рядке.

Метод Карно-Вейча

Метод диаграмм Вейча (карт Карно) удобен для минимизации ЛФ, содержащих обычно не более пяти переменных.

Метод диаграмм Вейча, усовершенствованный Карно, применяется в том слу­чае, если число аргументов не более 5. Представляют собой определенную таблицу истинности и отличаются друг от друга способом обозначения строк и столбцов таблицы истинности.

Число клеток карты Карно определяет­ся величиной 2 n , где п равняется числу входных переменных, с разметкой строк и столбцов переменными.

Например, если переменных 3 (n = 3), то (2 3 = 8) клеток -8.

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

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

Входные переменные располагаются по внешним сторонам карты напротив ее строк и столбцов. При этом значение каждой из входных переменных относит­ся ко всей строке или столбцу и равняется 1, если напротив строки (столбца) стоит под скобкой обозначение этой переменной; для других строк (столбцов) значение этой переменной равняется 0.

х2	/>2
х1
/>1

Диаграмма Вейча для двух переменных х₁ и х_2.

Переменных -2. Число клеток: 2 2 = 4

х2х3	х2 3	2 3	2х3
х1
1

Диаграмма Вейча для трех переменных х₁, х₂ и х₃

Переменных -3. Число клеток: 2 3 = 8

х3х4	х3 4	3 4	3х4
х1х2
х1 2
1 2
1х2

Диаграмма Вейча для четырех переменных х₁, х₂, х₃ и х₄

Переменных -4. Число клеток: 2 4 = 16

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

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

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

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

-количество клеток с 1 должно выражаться величиной 2 i , где i = 0, 1, 2, … (т.е. 1, 2, 4, 8 и т.д.);

— 1 в крайних клетках одного столбца или одной строки могут включаться в один контур;

-каждый контур должен включать как можно большее число клеток с 1, а общее число контуров должно быть как можно меньшим.

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

Пример 1. Минимизировать ЛФ F = х₂ + х₁ + ₁ с помощью диаграмм Вейча.

х2	/>2
х1
/>1

1. Заполняем диаграмму Вейча для двух переменных.

х2	/>2
х1	1
/>1

1. Проводим два контура, охватывающие клетки с единицами.

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

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

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

4. Следовательно, ЛФ будет иметь МДНФ: F = />₁ + />₂.

Пример 2. Минимизировать ЛФ F =х₁х₂+х₁ х₃+ ₁ х₃+ ₁х₂ с помощью диаграмм Вейча.

1. Приводим логическую функцию к СДНФ:

F = х₁х₂ (х₃+ ) + х₁ х₃+ ₁ х₃ + ₁х₂ = х₁х₂х₃ + х₁х₂ + х₁ х₃+ ₁ х₃ + ₁х₂

х2х3	х2 3	2 3	2х3
х1
1

2. Заполняем диаграмму Вейча для трех переменных.

х2х3	х2 3	2 3	2х3
х1
1

3. Проводим три контура, охватывающие клетки с 1.

1 контур (зеленый) –охватывает клетки х₁х₂х₃ и х₁ х₃

2 контур (красный) –охватывает клетки х₁х_{2 1} х₃

3 контур (красный) –охватывает клетки х₁ х_{3 1} х₃

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

Для 1 контура это —	х1х
Для 2 контура это —	х2
Для 3 контура это —	х3

5. Следовательно, ЛФ будет иметь МДНФ: F = х₁х₃ + х₂ + х₃

В этом примере вместо 1 контура можно было провести контур охватывающий конъюнкции х₁х₂х₃ и х₁х₂ , тогда МДНФ имела бы вид: F = х₁х₂ + х₂ + х₃. Таким образом, для этой функции возможны две тупиковые формы, равноценные по числу букв и слагаемых, и каждую из них можно выбрать для построения комбинационной схемы.

Карты Карно

Для минимизации функции с числом переменных n ≤ 6 используют карты Карно.

Число клеток карты Карно определяет­ся величиной 2 n , где п равняется числу входных переменных, с разметкой строк и столбцов переменными.

Например, если переменных 3 (n = 3), то (2 3 = 8) значит клеток -8.

Карты Карно для функции трех переменных F(х₁ х₂, х₃) показаны на рис. 3.10.

· Строки карты отмече­ны значениями переменной х_{1 ,} а столбцы -значениями переменных х₂, х₃.

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

· Клетки карты Карно часто нумеруют десятичными цифрами — номе­рами наборов (рис. 3.10, в).

· При минимизации для каждого минтерма, входящего в СДНФ функции, ставит­ся единица, а другие клетки не заполняются.

Рисунок 3.10 – Карты Карно для функций трех переменных

Например, заполнение карты Карно для функции, заданной табл. 3.12, показано на рис. 3.6, г.

Таблица 3.12 — Функции трех перемен­ных Р(X1 X2 X3)
№ строки	X1	Х2	X3	P

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

Например, на рис. 3.6, г минтермы X₃ и Х₂ Х₃ (клетки с номерами 1 и 3) отличаются значением переменной Х₂, поэтому они склеиваются по ней и представляются конъюнкцией двух переменных Х₃.

Аналогично для минтермов Х₁ и Х₁ Х₂ (номера клеток 4 и 6) склеивание происходит по переменной Х₂ и получают конъюнкцию Х₁ .

В результате минимизации функции Р(Х₁ Х₂, Х₃) получают ее минимальное выражение

Р = Х₃ v Х₂ Х₃ v Х₁ .