5. Минимизация логических функций методом Квайна – Мак-Класки Метод Карно позволяет минимизировать логические функции с относительно малым числом переменных.

Презентация:



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

Минимизация булевых функций Карты Карно, метод Квайна- Мак-Класки, метод неопределенных коэффициентов.
ДИСКРЕТНАЯ МАТЕМАТИКА Домашняя работа. Пример. Решение предоставлено в 2009 уч. г. Eduard Shustrov (099443FAY) Alexander Sudnitson Tallinn University of.
Булевы переменные и функции Булевыми переменными называются переменные, принимающие значение 0 или 1. Булевы (или логические) функции оперируют с булевыми.
Построение логических выражений по таблице истинности Курсовая работа Евстафьева Алексея, гимн.5, 2002 г.
ДИСКРЕТНАЯ МАТЕМАТИКА F.4 МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ Alexander Sudnitson Tallinn University of Technology.
Найдите функции xyf (x, y) xy
Определение логического выражения по таблице истинности Презентация по информатике ученицы 8 «а» класса Матвеевой Анастасии.
Консультация 2 27 март 2012 Информатика и ИКТ ЕГЭ 2012.
A B C.
Решение В Сколько различных решений имеет уравнение: K+L=1 и L M N=0 KL Если L=1, то второе уравнение имеет 3 решения 2. Если.
7. Элементы логических схем (логические элементы) Электрическую схему, обрабатывающую двоичные коды называют дигитальной схемой. Составляющими частями.
Логические основы вычислительной техники. Таблицы истинности Таблицей истинности называют таблицу значений логической функции для разных сочетаний значений.
Код Хемминга A {1}{3}{5}{7}{9}{11}= 0; B {2}{3}{6}{7}{11}= 0;{10} C {4}{5}{6}{7}= 0;{12} D.
Логические переменные и логические функции. Буквы, обозначающие высказывания, можно рассматривать как имена логических переменных, так как ими можно заменить.
7. Элементы логических схем (логические элементы) Электрическую схему, обрабатывающую двоичные коды называют дигитальной схемой. Составляющими частями.
Числовая и логическая информация Системы счисления Введение в математическую логику Развёрнутая форма записи числа Перевод целых чисел из одной системы.
Основные понятия алгебры логики Лямин Андрей Владимирович.
Метод Квайна-МакКласки. Выпишем наборы, на которых функция принимает единичное значение.
Математическая логика Ненашев Дмитрий Александрович Кафедра высшей математики Научный руководитель: Денискина Е.А. Факультет двигателей летательных аппаратов.
Транксрипт:

5. Минимизация логических функций методом Квайна – Мак-Класки Метод Карно позволяет минимизировать логические функции с относительно малым числом переменных. Кроме того метод является визуальным и сложным для алгоритмизации. Метод минимизации Квайна – Мак-Класки (далее просто Мак-Класки) является систематичным и его легко алгоритмизировать. Кроме того в нем отсутствуют ограничения на число переменных логической функции.

Метод Мак-Класки состоит из двух основных этапов: 1.Нахождение всех простых импликант логической функции, используя правило склеивания 2. Минимизации полученного множества простых импликант (задача нахождения оптимального покрытия) 10. Законы склеивания: a)(A & B) (A & B) A b)(A B) & (A B) A

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

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

1-ый этап – нахождение всех простых импликант логической функции. Пример 5.1 пусть задана логическая функция f (X 1, X 2, X 3, Х 4 ) = (0,1,2,5,6,7,8,9,10,14) 1 Найти МДНФ методом Мак-Класки. Решение: Выпишем двоичные векторы области единиц логической функции и найдем их индексы V 1 (X 1, X 2, X 3,Х 4 ) ={(0000), (0001), (0010), (0101), (0110), (0111), (1000), (1001), (1010), (1110),} Разделим двоичные векторы на секции в соответствии с их индексами, получим таблицу:

индексинтервал Таблица интервалов: Склеиваем между собой ближайшие векторы соседних секций пока это возможно.

индексинтервалиндексинтер- вал индексинтервалобозн A A A Все оставшиеся не склеенными интервалы образуют множество всех простых импликант логической функции. А1 А2 А3

2-ой этап – минимизация полученного множества простых импликант логической функции. Импли- кант A1 0-01xx A2 01-1xx A3 011-xx A4 -00-xxxx A5 -0-0xxxx A6 --10xxxx Вся область единиц должна быть покрыта простыми импликантами (в каждом столбце хотя бы один «х»), и их должно быть минимальное количество.

Оптимальное покрытие: А2, А4, А6. МДНФ: А2 А4 А6 = X 1 &X 2 &X 4 X 2 & X 3 X 3 & X 4.

Сходство методов Мак-Класки и Карно: 1.Векторы соседних клеток карты Карно = векторы соседних секций таблицы склеивания метода Мак- Класки. 2.Объдинение в контуры на карте Карно = склеивание в методе Мак-Класки. 3.Нахождение МДНФ и МКНФ методом Мак-Класки отличаются между собой по таким же принципам как и в методе Карно.

= (X 1 X 2 X 4 ) & ( X 1 X 2 X 3 ) & ( X 3 X 4 )