Лабораторная работа №6 Минимизация логических функций



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

Лабораторная работа №6 Минимизация логических функций



Лабораторная работа №6 Минимизация логических функций

Цель работы

· Освоить понятия минимизации логических функций (ЛФ).

· Научиться мимнимизировать ЛФ методом Квайна-Мак-Класски.

· Научиться мимнимизировать ЛФ с помощью карт Карно.

Теоретические сведения

 

Определение. Минимальная форма (МКФ и МДФ) представления ФЛ это форма, которая содержит минимальное количество термов и переменных в термах, и не должна допускать последующих упрощений.

Например, функция x1+ x2 может быть упрощена, если применить распределительный закон: x1x2+x3=(x1+x3)(x23), тогда

x1+ x2=( +x1)(x12)=x1 +x1x1+ х2+x1x2=

=0+x12( +x1)=x12.

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

Метод Квайна-Мак-Класски

 

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

Метод Квайна состоит из последовательного выполнения нескольких этапов.

1-й этап. Нахождение первичных импликант.

Все минтермы данной функции сравниваются попарно. Если минтермы отличаются одной координатой типа Fхi+F =F, то выписывается конъюнкция F, являющаяся минтермом (r+l)-гo ранга. Минтермы r-го ранга, для которых произошло склеивание, отмечаются.

Другими словами, нахождение простых импликант сводится к построению комплекса кубов

K(f) = К0 К1 К2 Кr.

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

Этап заканчивается, когда ни один (r+1)-куб не может быть построен. При этом, все неотмеченные кубы комплекса K(f) тоже являются простыми импликантами и входят в покрытие C(f) функции f.

Пример. Пусть задана функция

F(х12345)= (0,1,2,3,4,5,14,15,16,17,18,19,21,23,31)

Для упрощения, 0-кубы упорядочивают по числу 1-ых координат (см. рисунок 6.3).

Рис. 6.3-Комплекс кубов

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

2-й этап. Составление таблиц покрытий.

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

 

 

Таблица 6.1-Таблица покрытий комплекса кубов

  Вершины 0-кубов    
Импликанты
X00XX 00X0X X0X01 10XX1 1X111 + + + ++ +   + + +     ++ +   ++   +     ++ +     +       +   +   ++     +  
                                                           

3-й этап. Определение существенных импликант.

Если в столбце таблицы покрытий имеется только одна метка, то первичная импликанта, стоящая в соответствующей строке, является существенной импликантой, и ее выписывают в новое минимальное покрытие C(f). Из таблицы покрытий исключаются строки, соответствующие существенным импликантам и столбцы минтермов, покрываемым этими существенными импликантами. Покрытие будет иметь вид :

 

C(f) = .

В результате упрощения, получим новую таблицу 6.2

Таблица 6.2-Покрытия

импликанты
X0X01 10XX1 + +

4-й этап. Вычеркивание лишних столбцов.

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

5-й этап. Вычеркивание простых лишних импликант.

Если после вычеркивания столбцов в таблице появляются строки без меток, то импликанты этих строк вычеркиваются.

6-й этап. Выбор минимального покрытия.

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

В нашем примере выбирается импликанта Х0Х01 ( или 10ХХ1, т.к. цены СA одинаковы).

Таким образом, покрытие функции имеет вид:

С(f) =

и определяет минимальную ДНФ

f = + + x2x3x4 + x5+x1x3x4x5..

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

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

Соседние клетки

 

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

 


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

Для минимизации функций с числом переменных больше 7 карты Карно практически не применяются.

После определения соседних клеток, их объединяют контурами объединения.

 

Задание.

1. Представить ЛФ в виде СДНФ.

2. Мимнимизировать ЛФ методом Квайна-Мак-Класски.

3. Мимнимизировать ЛФ с помощью карт Карно.

4. Построить схему для ЛФ в минимальной форме.

 

Индивидуальные задания:

x1
x2
x3
x4
                                 

Лабораторная работа №6 Минимизация логических функций

Цель работы

· Освоить понятия минимизации логических функций (ЛФ).

· Научиться мимнимизировать ЛФ методом Квайна-Мак-Класски.

· Научиться мимнимизировать ЛФ с помощью карт Карно.

Теоретические сведения

 

Определение. Минимальная форма (МКФ и МДФ) представления ФЛ это форма, которая содержит минимальное количество термов и переменных в термах, и не должна допускать последующих упрощений.

Например, функция x1+ x2 может быть упрощена, если применить распределительный закон: x1x2+x3=(x1+x3)(x23), тогда

x1+ x2=( +x1)(x12)=x1 +x1x1+ х2+x1x2=

=0+x12( +x1)=x12.

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



Последнее изменение этой страницы: 2016-12-26; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 44.192.254.246 (0.014 с.)