A) элементтері болса 9 страница

В отличии от таблицы истинности, где в качестве элемента структуры выделяется строка (п.1.2), элементом структуры карты является клетка. Число строк и клеток одинаково и равно , где – число независимых переменных логической функции. Каждая клетка карты имеет координаты, соответствующие возможным значениям независимых переменных. В каждой клетке записывается значение функции. На рис. 2.5.1 приведён пример сопоставления рассматриваемых табличных форм функции двух переменных следующего вида

 
 

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

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

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

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

Пример 2.5.8.

 

 

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

Рассмотренное существо связи карты Карно с СДНФ и СКНФ используется и при обратном переходе от аналитического вида функции к её табличному представлению. Это хорошо просматривается на примерах 2.5.10 и 2.5.11.

Пример 2.5.9.

 

Пример 2.5.10.

 

 

Пример 2.5.11

Если функция задана в ДНФ (КНФ), можно преобразовать её в СДНФ (СКНФ) и, затем, построить карту Карно (примеры 2.5.10 и 2.5.11). Сформировать карту Карно можно непосредственно по ДНФ (КНФ). Например, для ДНФ, минтермы не содержащие полного набора независимых переменных, будут отражаться на карте Карно несколькими единицами. Их количество равно , где - число независимых переменных функции, - число переменных, составляющих рассматриваемый минтерм. Место расположения единиц определяется координатными границами переменных, образующих каждый из минтермов (пример 2.5.12).

 

 

Пример 2.5.12.

 

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

карт Карно.

 

Задаваемая для минимизации функция должна быть представлена только либо в СДНФ (ДНФ), либо в СКНФ (КНФ). При решении логических задач отдаётся предпочтение первой форме (её аналитический вид более компактен). Поэтому, данный метод минимизации будет изложен для представления исходной функции в СДНФ (ДНФ). Если, всё же исходная функция представлена в СКНФ (КНФ), рекомендуется сделать преобразование «СКНФ (КНФ) → СДНФ (ДНФ)» (п. 2.4).

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

Пример 2.5.13.

 

Приведённый пример позволяет отметить следующее:

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