Минимизация логических функций онлайн: Построение таблицы истинности онлайн | СКНФ | СДНФ | Полином Жегалкина | Таблица истинности булевой функции онлайн

Содержание

Минимизация логических функций — презентация онлайн

Похожие презентации:

Минимизиция ФАЛ. Задача. Методы. Табличный метод Метод Квайна-Мак-Класски. Метод неопределенных коэффициентов

Лекция 8. Минимизация. Элементы математической логики и теории автоматов (продолжение)

Метод Квайна

Получение схемы логического элемента по итоговым значениям логической функции с использованием СДНФ ИЛИ СКНФ

Базовые логические функции. Основные понятия алгебры логики

Основные положения булевой алгебры

Логические основы ЭВМ

Совершенные конъюнктивные и дизъюнктивные нормальные формы

Синтез комбинационных схем

Таблицы истинности логических функций

1. Минимизация логических функций

2. Метод Квайна

• Метод Квайна — способ представления
функции в ДНФ или КНФ с минимальным
количеством членов и минимальным
набором переменных.
Преобразование функции можно разделить
на два этапа:
– на первом этапе осуществляется переход от
канонической формы (СДНФ или СКНФ) к так
называемой сокращённой форме;
– на втором этапе — переход от сокращённой
формы к минимальной форме.

4. Первый этап (получение сокращённой формы).

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

• Пример 1. Пусть
• Тогда 1-я и 2-я строки не покрывают
матрицу M:
• а 1-я и 3-я строки – являются покрытием
матрицы M:
• ПРИМЕР.
• Найдем МДНФ формулы:
• Во-первых, осуществим всевозможные
склеивания
• В результате СкДНФ имеет вид:
• А импликантная матрица имеет вид
• По данной импликантной матрице можно
выбрать следующие МДНФ

17. Метод минимизирующих карт.

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

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

24. Метод минимизации с помощью карт Вейча.

Метод минимизации с помощью карт Вейча.

• Алгоритм метода карт Вейча включает в себя следующие
этапы:
• Заданная формула приводится к СДНФ.
• Составляется карта Вейча. Карта Вейча – это таблица всех
возможных комбинаций значений переменных. В
соответствующие ячейки заносятся единицы,
соответствующие конституентам СДНФ.
• Единицы, стоящие по вертикали и горизонтали,
объединяются (по 2 , по 4 , по 8 и т.д.). Объединение
единиц соответствует операциям склеивания и
поглощения. Иначе говоря, формируются максимальные
подкубы.
• Для каждого объединения выписываются конъюнкции из
элементов, общих для каждой единицы, входящих в
объединение.
• Полученные конъюнкции составляют МДНФ.
• Карты Вейча удобны при поиске МДНФ
функций двух, трех и четырех переменных.
• Пример для n=2.
• Функция задана
• Пример для n=3.
• Функция задана
• Пример для n=4.
• Функция задана СДНФ

English Русский Правила

Минимизация булевых функций методом Гиперкубов / Хабр

Nostr

000Z» title=»2011-03-10, 18:38″>10 мар 2011 в 18:38

Время на прочтение 2 мин

Количество просмотров

16K

Алгоритмы *

Из песочницы

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

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

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

Метод заключается в применении известных правил Склеивания и поглощения.

Перед описанием алгоритма объясню почему метод называется методом гиперкубов.
Возьмем произвольную функцию f, M1(f) – единичное множество. Проще говоря, множество наборов переменныx, на которых функция обращается в верное высказывание.
Гиперкуб – это множество M1(f).
Коньюнктивный одночлен – импликанта, если М1(K) входит в M1(f).
Импликанту называют простой, если не существует другого K2, что M1(K) содержится в M1(K2), говоря простым языком – соответствует самому большому гиперкубу.

Основные этапы данного метода

Построить таблицу истинности.
Выписать все гиперкубы из M1(f) и импликанты.
Взять простые импликанты.
Построить таблицу накрытия.
Из оставшихся простых импликантов создать тупиковую ДНФ.

Возьмем в качестве примера следующую булеву функцию.

Построим таблицу истинности для нее:

Выпишем все гиперкубы, лежащие в M1(f) и соответствующие им импликанты:

Выбираем простые импликанты и строим таблицу их накрытия:

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

Минимизация логических функций

Введение

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

Некоторые ресурсы минимизации

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

Карно, М. «Метод карты для синтеза комбинационных логических схем», Trans. AIEE, часть. я, том. 72, нет. 9, pp. 593-599 , 1953. Цитируется в книгах Кохави и Маккласки, перечисленных ниже.
Кохави, З. Переключение и теория конечных автоматов , Нью-Йорк: McGraw-Hill, 1970.
McCluskey, EJ, Introduction to Theory of Switching Circuits , New York: McGraw-Hill, 1965

Зачем сворачивать?

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

y = Σ(x, … )

, где « (x, … ) » — набор из логических переменных (переменных, которые может принимать только значения ноль и единица).

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

Чтобы оценить важность минимизации, рассмотрим две сети в Рис. 1 и 2 . Оба ведут себя одинаково! Независимо от того, какой узор из единиц и нулей вы поместив в a , b и c на рис. 1, значение, полученное при y , будет в точности равно совпадают, если вы поместите один и тот же шаблон значений в соответствующие входные данные на рис. 2. Однако сеть на рис. 2 использует гораздо меньше вентилей, и используемые им вентили проще (имеют меньшие разветвления), чем вентили на рис.

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

Рисунок 1

Рисунок 2

Общие сведения и терминология

Переменные в выражении в правой части логического уравнения являются входными проводами к логическому сеть. Левая часть логического уравнения — это выходной провод сети.
Любое логическое уравнение или комбинационная логическая сеть могут быть полностью и точно охарактеризованы таблица истинности . В таблице истинности перечислены все возможные комбинации значений входных переменных, а соответствующее выходное значение функции для каждой комбинации. Есть 2 ⁿ рядов в таблица истинности для функции или сети с n входными переменными, поэтому не всегда практично составить целую таблицу истинности. Но для относительно небольших значений n таблица истинности дает удобный способ точного описания функции или поведения сети. Примечание Всегда перечисляйте комбинации входных значений в двоичном порядке подсчета сверху вниз ( 000, 001, 010, 011, … ).
Каждая строка таблицы истинности с единицей в выходном столбце называется minterm . Удобный способ для представления таблицы истинности нужно рассматривать каждую комбинацию входных переменных как двоичное число и перечислять номера строк, которые являются minterms.
В этом документе в качестве рабочего примера используется функция со следующей таблицей истинности:
и б с Д
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
Эту таблицу истинности также можно представить в виде списка минтермов, [ 1, 2, 4, 5, 6, 7 ].
То есть, таблица истинности имеет 1 в столбце Y для строк, где двоичное число представлено значениями a, b, c — одно из чисел, указанных в квадратных скобках. Две другие строки (0 и 3) имеют 0 в Y столбец и, таким образом, не являются минтермами.
Один из стандартных способов представления любой логической функции называется «сумма произведений» (SOP) или, более формально дизъюнктивная нормальная форма . В таком виде функция записывается как логическое ИЛИ (обозначается по +) набора терминов И, по одному на минтерм.
Например, дизъюнктивная нормальная форма для нашего примера функции будет:
```
          Y = a'b'c + a'bc' + ab'c' + ab'c + abc' + abc
         
```
Существует также конъюнктивная нормальная форма , , которая представляет выражение как произведение сумм, а не чем в виде суммы произведений. Материал, представленный ниже, может быть расширен для работы с конъюнктивными нормальными формами. а не дизъюнктивные нормальные формы. Мы оставим это как одно из тех классических «упражнений, для студента», и иметь дело только с дизъюнктивными нормальными формами.
Литерал — это переменная, которая либо дополняется, либо не дополняется в термине продукта. Минтермс в нашем примерная функция имеет в общей сложности шесть литералов: a, a’, b, b’, c и c’. Сеть на рис. 2 использует только 5 литералы, потому что a’ не используется. В дизъюнктивной нормальной форме функции каждый член произведения имеет один литерал для каждой переменной. (6 литералов для 3 переменных в нашем примере функции.)
На рис. 1 реализована наша примерная функция и показано преобразование дизъюнктивной функции нормальной формы. непосредственно в логическую сеть. Процедура перевода следующая:
1. Используйте инверторы для генерации всех возможных литералов (шесть вертикальных проводов слева на рис. 1).
2. Нарисуйте вентиль И для каждого минтерма. Разветвление (количество входов) каждого вентиля И равно числу входных переменных.
3. Соедините выходы всех логических элементов И с одним логическим элементом ИЛИ.
4. Соедините входы каждого вентиля И с шаблоном литералов таким образом, чтобы он генерировал 1 когда шаблон входных значений соответствует конкретному назначенному ему минтерму.
Минимальная форма логического выражения — это та, которая реализует выражение с минимальным числом литералов. и условия продукта, насколько это возможно. Может быть более одной минимальной формы выражения; если есть только один минимальная форма, эта форма минимум.
Существует много правил алгебраической обработки логических выражений, но есть только одно правило, которое вам нужно, чтобы минимизировать функцию, когда она находится в дизъюнктивной нормальной форме: правило дополнение .
Правило дополнения гласит, что (x + x’) всегда истинно (1), поэтому любые два члена в форме (x + x x’)Y можно свести просто к Y без изменения его значения. Другой способ сказать это состоит в том, что два продукта термины можно упростить, если единственное различие между ними состоит в значении ровно одной переменной, и в этом случае эту переменную можно исключить из обоих терминов, чтобы получить эквивалентный один термин. Например, ab’c + a’b’c эквивалентно (a + a’)b’c, что совпадает с термином одного продукта, b’c.

и	б	с	Д
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

Карты Карно

Карта Карно — это графический способ минимизации логического значения. выражение, основанное на правиле дополнительности. Это хорошо работает, если есть 2, 3 или 4 переменные, но их использование становится запутанным или невозможным для выражений с большим количеством переменных.

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

На рис. 3 показано, как minterms в таблицах истинности помещаются в сетку карты Карно как для 3, так и для 4 переменных выражения.

Рисунок 3

Глядя на карту с тремя переменными слева на рис. 3, обратите внимание, что minterm 0 (000 ₂ ) чуть выше minterm 4 (100 ₂ ). Такое расположение означает, что если оба minterms 0 и 4 встречаются в функции, первая переменная (с именем и в рис. 3) появляется как в истинном, так и в дополненном виде и может быть устранено. Верхний ряд карты Карно помечен a’ и нижний ряд с a : Появляются любые минтермы в верхнем ряду есть буквальные a’ в них, и любые minterms в нижнем ряду есть буквальное число и . В то же обратите внимание, что каждый столбец имеет одинаковые значения для переменных б и с . Кроме того, столбцы расположены в порядке так что только одна переменная изменяет значение при переходе от одного столбца к другому. следующий. Таким образом, первые два столбца отличаются значением c , второй и третий столбцы отличаются значением b , а третий и четвертый столбцы отличаются значением c снова. Кроме того, первый и четвертый столбцы «рядом» друг с другом, потому что они отличаются от друг друга только в значении b .

В правой части рис. 3 показано, что этот же шаблон (соседние столбцов отличаются значением одной переменной) относится к строк карты Карно тоже: первая и вторая строки та карта отличается значением b , вторая и третья отличаются значением a , третья и четвертая отличаются значение b , а первый и четвертый отличаются значение a .

На рис. 4 показан пример нашей функции в виде Карта Карно. Minterms 1 и 2 находятся во втором и четвертом столбцах. верхнего ряда, а минтермы 4, 5, 7 и 6 — слева направо. прямо в четырех столбцах нижнего ряда.

Рисунок 4

Карта Карно используется для получения минимальной суммы произведений реализация выражения путем рисования прямоугольников вокруг групп соседних минтермов на карте; каждый прямоугольник будет соответствовать один термин произведения, а полное выражение будет построено как ИЛИ (сумма) всех терминов продукта. Цель состоит в том, чтобы иметь как можно меньше условия продукта, насколько это возможно, а это означает, что каждый термин продукта будет учитывать как можно больше минтермов.

Вот правила рисования прямоугольников:

Каждый минтерм должен быть внутри хотя бы одного прямоугольника, но внутри прямоугольников не должно быть нулей.
Каждый прямоугольник должен быть как можно больше.
Прямоугольники могут включать в себя ячейки как в крайний левый и крайний правый столбцы. так же для верха и низа ряды.
Количество минтермов, заключенных в прямоугольник, должно быть степенью из двух (1, 2, 4, 8 или 16 минтермов для карт с 4 переменными).
Некоторые функции имеют условия «безразлично», которые комбинации входных данных, которые никогда не произойдут, что приводит к случаям где не имеет значения, является ли выход нулевым или один. Где эти безразличные условия появляются в Karnaugh Карта (обычно обозначается крестиком вместо единиц или нулей), они могут быть включены в прямоугольники или не включены в зависимости от того, что сделает прямоугольников как можно меньше и как можно больше.

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

Рисунок 5

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

y = a + b’c + bc’

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

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

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

Рисунок 6

Алгебраическая минимизация

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

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

———————————————— ————— | Проход 0: a’b’c + a’bc’ + ab’c’ + ab’c + abc’ + abc | ————————————————— ————- ————————————————— ————- | Проход 1: a’b’c + ab’c сводится к b’c | | a’bc’ + abc’ сводится к bc’ | | ab’c + ab’c’ сводится к ab’ | | abc’ + abc сводится к ab | ————————————————— ————- | b’c + bc’ + ab’ + ab | ————————————————— ————- ————————————————— ————- | Проход 2: ab’ + ab сводится к | ————————————————— ————- | а + b’c + bc’ | ————————————————— ————-

Правила, которым необходимо следовать для каждого прохода:

Каждый термин, присутствующий в одном проходе, должен быть объединен с другим срок если можно.
Любые термины, которые не могут быть объединены, переносятся вперед без изменений до следующего прохода.
Термин, который уже использовался один раз в проходе, должен быть используется снова, если это позволяет сократить еще один термин. Для например, в проходе 1 выше ab’c используется дважды, и поэтому абв’.

Правилу повторного использования терминов в проходе соответствует обведение некоторые минтермы более одного раза на карте Карно. Два минтерма которые повторно используются в проходе 1 выше, точно такие же два, которые дважды обведены кружком на карте Карно на рис. 5.

После определения основных импликантов выражения необходимо выбрать минимальное их множество. Выбор минимального подмножества основных импликантов основывается на понятии минтермов, являющихся «покрытые» первичными импликантами. Для нашей примерной функции главная импликанта и охватывают минтермы 4, 5, 6 и 7; в простая импликанта b’c покрывает минтермы 1 и 5, и подразумеваемый bc’ покрывает minterms 2 и 6. В этом примере нам нужны все три основных импликанта, чтобы охватить все минтермы как минимум один раз, а выражение, показанное в конце прохода 2, является минимизированным форма для нашего образца функции.

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

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

Для каждого минтерма, который покрывается только одним основным импликантом, эта первичная импликанта должна быть включена в минимальную форму. Эти minterms называются существенными простыми импликантами , потому что они важно включить их в минимизацию.
Для нашего образца функции покрыты minterms 2, 3 и 4. ровно одной простой импликантой, поэтому все три простых импликанты необходимы, есть только одна минимизированная форма, и больше нечего делать.
Составьте список всех минтермов, на которые не распространяется ни один из существенные первичные импликанты.
Составьте список неиспользованных простых импликантов. Упорядочить этот список по количество литералов, содержащихся в каждой простой импликанте.
Если какие-либо оставшиеся минтермы покрываются только одним из оставшиеся простые импликанты, соответствующие простые импликанты должны быть добавлены к минимизации, и все минтермы, которые они охватывают, должны быть удалены из списка непокрытых минтермов.
Если есть непокрытые минтермы, добавьте неиспользованный прайм связано с наименьшим количеством литералов для минимизации, и удалите все минтермы, на которые распространяется этот основной импликант из списка непокрытых минтермов.
Если два или более простых импликанта имеют одинаково малое количество литералы, существует более одного минимального решения. Нахождение их all включает в себя систематическую замену каждого связанного простого числа импликанты в различные минимальные формы, являющиеся сгенерировано.
Удалите все основные импликанты, которые не покрывают ни одного из оставшиеся минтермы из списка неиспользованных простых импликантов.
Повторяйте предыдущие три шага, пока все минтермы не будут покрытый.

Отказ от ответственности! Приведенный здесь алгоритм основан на метод «диаграммы» Куайна-МакКласки, описанный в (McClusky, 1965) и в (Кохави, 1970). Но это не совсем то же самое, что процедура, указанная в этих ссылках, и может не привести к такому же результату. Результаты. Однако он должен производить полностью минимизированную функцию.

Доступны две версии программы минимизации. первый был разработан в 2000 году. Его нужно вызывать из команды приглашение, такое как Windows «DOS Window» или приглашение оболочки L/Unix. вторая версия была разработана в 2005 году, и ее до сих пор можно запускать с командная строка, но также может быть запущена с помощью графического пользователя интерфейс. Для обеих версий требуется среда выполнения Java (JRE). доступен на Java от Sun Microsystems Веб-сайт. Первая версия программы будет работать с JRE версии 1.3 или новее и, вероятно, работает с некоторыми более старыми JRE как хорошо. Второй версии определенно нужна JRE версии 1.5 или позже.

Скачать любую версию программы:

Minimize.jar: Текущая версию программы. Требуется JRE 1.5 или более поздней версии. Включает исходный код.
Minimize.zip: предыдущая версия программы. для исключающего ИЛИ и ‘ для постфиксного НЕ. Вы также можете использовать логические константы 0 и 1, и вы можете использовать круглые скобки для управления порядок оценки. При вводе номеров minterm вместо выражения, используйте пробелы или запятые для разделения чисел.
Когда вы вводите выражение или список minterm, свернутый результат алгоритма появляется сразу под полем ввода. Эта строка автоматически копируется в системный буфер обмена и может при необходимости вставить в другое приложение. (нет визуального указание на то, что результирующая строка была выбрана, но она можно вставить .)
Таблица Minterm непосредственно под свернутым результатом показывает minterms для суммы продуктов формы выражения, которое вы ввели. В левом столбце термины продукта показаны в виде номеров строк таблицы истинности. а правый столбец показывает термины продукта алгебраически. Премьер Импликантная таблица ниже, которая показывает каждый минимизированный член продукта в первый столбец и список полных терминов продукта, каждый из которых сведен к минимуму термин «покрывает» (подразумевает) во второй колонке.
В правой части окна показаны этапы обработки программа выполнила минимизацию. (Или сообщение об ошибке если вы ввели недопустимое выражение.) Это информация, которая записывается в консоль при запуске любой версии программы из командной строки.
Используйте кнопку «Новое окно», если хотите одновременно видны несколько минимизаций. Размер, форма и внутренние части последнего окна, из которого вы вышли, будут повторно использованы, если вы снова запустить программу.
Вы также можете запустить графический интерфейс из командной строки с помощью команды java -jar Minimize.jar . Если вы хотите запустите версию командной строки, команда:
java -cp Minimize.jar MinimizedTable
.
См. описание старой версии программы ниже для синтаксис <выражение или список minterm> .
Предыдущая версия
Откройте окно командной строки на вашем компьютере и измените на каталог, в который вы скачали Minimize. zip. Команда для запуска программа:
java -cp Minimize.zip Minimize <выражение или minterm list>
Логическое выражение, которое вы вводите в командной строке, должно использовать следующий синтаксис:
- Поместите все выражение в кавычки, чтобы пробелы и другие символы, такие как звездочки, не будут изменены интерпретатором команд. 9для исключающего ИЛИ. Вы можете опустить *. То есть ab равно a*b.
- Используйте ‘ для дополнения после элемента, который будет дополнен.
- И имеет приоритет над ИЛИ и XOR. Последние два будут оцениваются в порядке справа налево. Используйте скобки для контроля порядок оценки.
- Пробелы не действуют.
- Можно использовать константные литералы 0 и 1.
Кроме того, вы можете написать список номеров minterm на командная строка. Между числами должны быть пробелы, но не должно быть запятых. Наибольшее число minterm, которое вы укажете, будет определять количество переменные в выражении и количество строк в результирующем таблица истинности. Например:
java -cp Minimize.zip Minimize 4 6
В таблице истинности должны быть три переменные и 8 строк, чтобы включить эти два minterms. Переменные будут автоматически названы а, б и в. 9с» Поиск одной минимизации Минтерм Числа: [1,2,4,5,6,7] Уменьшено ab’c и a’b’c до b’c в проходе 1. Уменьшено abc’ и a’bc’ до bc’ в проходе 1. Уменьшено ab’c и ab’c’ до ab’ в проходе 1. Уменьшено abc’ и ab’c’ до ac’ в проходе 1. Уменьшено abc и ab’c до ac в проходе 1. Уменьшено abc и abc’ до ab в проходе 1. Невозможно уменьшить b’c на проходе 2 Невозможно уменьшить bc’ на проходе 2 Уменьшено ab и ab’ до a в проходе 2. Невозможно уменьшить b’c на проходе 3 Невозможно уменьшить bc’ в проходе 3 Невозможно уменьшить a в проходе 3 Minterm 1 покрывается 1 основным импликантом. Minterm 2 покрывается 1 основным импликантом. с Сумма произведений: a’b’c + a’bc’ + ab’c’ + ab’c + abc’ + abc Основные импликанты: [a: ab’c’, ab’c, abc’, abc], [b’c: a’b’c, ab’c], [bc’: a’bc’, abc’] Минимизировано: b’c + bc’ + a $ java -cp Minimize.zip Свернуть «aa’+b1» Поиск одной минимизации Номера Минтерма: [1,3] Уменьшено ab и a’b до b в проходе 1. Не удалось уменьшить b на проходе 2 Minterm 1 покрывается 1 основным импликантом. Minterm 3 покрывается 1 основным импликантом. Выражение: а*а’+b*1 Сумма произведений: a’b + ab Основные импликанты: [b: a’b, ab] Свернуто: б $
Булева алгебра и минимизация-2 Учебные заметки для экзаменов GATE и компьютерных наук
Серия тестов
Прия Упадхьяй раздел математической логики или алгебры, в котором значение переменных является двоичным, т. е. может быть либо 0, либо 1, также обозначаемым как ложное и истинное соответственно. Булева алгебра используется для упрощения и анализа цифровых логических схем. Булева алгебра была введена Джорджем Булем в 1854 г.
Любая цифровая схема может быть реализована и представлена с помощью булевых функций, но проблема заключается в том, что количество литералов, используемых в исходной булевой функции, обычно велико, и если эта функция реализована с использованием логических вентилей, это увеличит сложность и стоимость системы. Булевы функции напрямую связаны со сложностью алгебраического выражения, с помощью которого мы реализовывали функцию.
Чтобы уменьшить сложность, нам нужна упрощенная версия алгебраического логического выражения. Итак, процесс минимизации и упрощения алгебраического выражения известен как минимизация. Минимизация важна для снижения стоимости и сложности схемы.
Читать полностью
Булева алгебра и минимизация
Булева алгебра — это раздел математической логики или алгебры, в котором значение переменных является двоичным, т. Булева алгебра используется для упрощения и анализа цифровых логических схем. Булева алгебра была введена Джорджем Булем в 1854 году.
Любая цифровая схема может быть реализована и представлена с использованием булевых функций, но проблема заключается в том, что литералы, используемые в исходной булевой функции, обычно высоки, и если эта функция реализована с использованием логических вентилей, она будет увеличить сложность и стоимость системы. Булевы функции напрямую связаны со сложностью алгебраического выражения, с помощью которого мы реализовывали функцию.
Чтобы уменьшить сложность, нам нужна упрощенная версия алгебраического логического выражения. Итак, процесс минимизации и упрощения алгебраического выражения известен как минимизация. Минимизация важна для снижения стоимости и сложности схемы.
Способы представления функций:
- Канонические выражения
  - Форма POS
  - Форма СОП
- Упрощенные выражения Canon