Упрощение выражений с помощью карт
Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Упрощение выражений с помощью карт





Карты позволяют упростить логические выражения. Главное при этом – сохранение истинностных значений исходной функции. Упрощение состоит в считывании функции с карты с применением основных логических правил (правило IV, табл. 2.14).

Для упрощения применяется определенный способ объединения ячеек, при котором формируются более крупные группы из ячеек карты.

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

(2.11.1).

Карта этой функции приведена на рис. 2.32.

AB      
CD     2,4
         
    1,3,6
  6,7   1,2,5 1,2,3,4, 5,6,7

Рис. 2.32. Карта функции .

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

(2.11.2).

Некоторые ячейки заполнялись более одного раза, например, угловая нижняя ячейка заполнялась семь раз, а считывается только один раз согласно правилу 1 табл. 2.14.

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

Карта предоставляет возможности для упрощений. Для упрощений используется приём комбинирования любых двух соседних ячеек. Это приём называют также системой изменения одной переменной. Результатом комбинирования является сокращение букв, которые представлены одновременно и с отрицанием и без отрицания.

На рис. 2.33 представлен один из возможных вариантов попарного комбинирования ячеек.

В результате комбинирования получим функцию:

(2.11.3)

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



 

AB      
CD    
         
  1  
   

Рис. 2.33. Попарное комбинирование ячеек карты,

представленной на рис. 2.32

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

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

Попарное комбинирование основано на прямом применении правила IV таб. 2.14.

Можно выбирать комбинации из четырёх не пустых соседних ячеек. В принципе допускаются любые комбинации соседних ячеек, число которых составляет какую-либо степень двух.

На рис. 2.34 показан один из возможных вариантов комбинирования с комбинированием четырёх ячеек.

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

. (2.11.4)

Рассмотреть другие варианты комбинирования ячеек по четыре (Решить задачи 5 и 6 из контрольных вопросов и задач).

 

AB      
CD    
         
  1  
   

Рис. 2.34. Попарное комбинирование ячеек карты,

представленной на рис. 2.32

Анализ задач с пятью и шестью переменными более сложен. Для тех, кому будет необходимо решать такие задачи, потребуется более глубокое изучение алгебры логики, для чего можно обратиться к следующим публикациям: Браун Д.Б., 1979;. Обухов В. Е., 1992; Шевелев Ю. П., 2000; Ерош, И. Л., 2001; Коледов Л. В., 2000; Валов, Г. М., 2000; Фридлендер, Б. И., 2005.

AB      
CD    
         
  1  
   

Рис. 2.35. Попарное комбинирование ячеек карты,

представленной на рис. 2.32

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

В результате проведенного комбинирования (объединения двух ячеек по две и четырёх ячеек) получаем функцию:

. (2.11.4)

Рассмотреть другие варианты комбинирования ячеек по четыре (Решить задачи 5 и 6 из контрольных вопросов и задач).

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









Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2018 zdamsam.ru Размещенные материалы защищены законодательством РФ.