Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Обработка карт

⇐ Предыдущая12345678910Следующая ⇒


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

  *     *  
       
*

*

x5

x4 x4

x3 x3

   
*

               
x2
*

       
*

   
*       x2  
*

       
                   
*

 
x1         x1                

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

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

При склеивании клеток выпадает переменных, т.е. останется переменных.

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

                   
             
  11 12           11     12  
13 14           13 14    
15 16         15 16    
      17     17     18  
                   
             
11 12 13       11     12  
      14 15       13     14  
  16            
17 18 19         15   16  
                     

                 
           
11 12 13 14       11 12   13  
  15 16   17         14  
18 19 110     15      
111     112     16   17 18  
                     

Обратите внимание, что в последней карте нет смысла объединять клетки 1, 3, 6, 8, ибо оставшиеся клетки приходится объединять с ними же.

x 5 x 5

                            x 4    
                       
          1             1       1  
                                1  
                             
                                   
                                   

x 5 x 5

            x 4                 x 4    
              x 3             x 3
                         
                                       
                                   
                                   
                                   

x 5 x 5

            x 4           x 4    
                 
                                 
                                   
                                 
                  1              
                                   

x 5 x 5

            x 4                 x 4      
              x 3            
      1 1                    
                                     
                                       
                                     

7 абсолютно минимальные представления

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

Определение 7-1. Q представляет собой минимальное представление для функции f, если не существует в базисе {-, &, } представления более минимального, чем Q, каким бы способом ни получилось это выражение.

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

Пример 1-7. Для функции

найдена МДНФ вида: .

Если вынести за скобки x 1, то получим абсолютно минимальное представление: .

Замечание 1-4. Отметим, что МДНФ зачастую не дает абсолютно минимального представления. В ряде случаев МКНФ оказывается “меньше” МДНФ. Поэтому для получения абсолютно минимальных представлений ФАЛ необходимо из них выбрать наименьшее.

Методы получения МКНФ двойственны методам получения МДНФ.

ГЛАВА 2.ПРЕОБРАЗОВАНИЯ И МИНИМИЗАЦИЯ В БАЗИСЕ СОСТОЯЩЕМ ИЗ ФУНКЦИИ ВЕББА ИЛИ ИЗ ФУНКЦИИ ШЕФФЕРА. [†]

Проблема минимизации ФАЛ может быть сформирована и для случая любого другого базиса. Функции Вебба (Пирса) и Шеффера образуют базисы, состоящие только из одной функции. Будем называть такие базисы монофункциональными.

В последнее время возник большой интерес к моно-функциональным базисам. Поэтому рассмотрим их более подробно. Оба базиса обладают одинаковыми свойствами, поэтому рассмотрим задачу минимизации ФАЛ лишь для одного из них – базиса из функции Вебба. Для упрощения записи в дальнейшем будем использовать знак (стрелка Пирса) взамен знака для обозначения функции Вебба (о).

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

По аналогии с двуместными, введем с помощью таблицы n -местные функции Вебба и Шеффера:

x 1 x 2 x3 . . . xn -1 Xn Wn Sn
      . . .        
      . . .        
      . . .        
- - - - - - - - - -
- - - - - - - - - -
      . . .        
      . . .        
      . . .        

При n =2 из этой таблицы получаются двухместные функции Вебба и Шеффера, а при n =1 обе функции вырождаются в функцию отрицания. Поэтому в дальнейшем будем вместо и x / x писать соответственно .

Для введенных функций справедлив переместительный закон и несправедлив сочетательный закон.

Справедливы следующие соотношения:

(2-1)

При раскрытии скобок получим:

(2-2)

Заметим, что если l или m равны единице, то эти соотношения выразятся несколько иначе. Например, при l =1:

(2-3)

Наконец, приведем соотношения, показывающие связь между многоместными функциями Вебба и Шеффера и являющиеся аналогами формул де Моргана:

(2-4).

Справедливость всех вышеприведенных соотношений можно установить при помощи таблиц истинности ФАЛ.

В дальнейшем в основном будем рассматривать базис, построенный на основе многоместной функции Вебба.

Известно [11], что любую ФАЛ можно представить:

,

если выбрать -характеристические функции единицы для множества Т 0 номеров наборов, на которых функция f обращается в нуль:

Применяя последнее из соотношений (2-1), получаем одну из двух совершенных нормальных форм в базисе Вебба:

(2-5)

Если использовать характеристические функции единицы для множества T 1 номеров наборов, на которых функция f обращается в единицу, то получится другая совершенная нормальная форма. Она проще предыдущей, если у функции в таблице истинности нулей больше, чем единиц:

(2-6)

Для получения аналогичных нормальных форм в базисе Шеффера можно использовать характеристические функции нуля.

Перейдем теперь к аналитическому выражению характеристических функций единицы в базисе Вебба. Для любой характеристической функции единицы в базисе {-, &, } может быть получено выражение через конституенту единицы:

Если применить последнее из соотношений (2-1), то

(2-7)

и мы можем написать, что

и получить выражение для характеристической функции единицы:

(2-8)

при условии, что

.

Теперь мы можем сформулировать алгоритм перехода от табличного задания функции к ее записи в виде совершенной нормальной формы вбазисе n -местной функции Вебба вида, например, (2-5):

1. Выбрать в таблице задания функции все наборы аргументов, на которых функция обращается в нуль.

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

3. Все полученные выражения характеристических функций объединяются k -местной операцией Вебба, где k – количество нулей заданной функции.

Пример 2-1. Построить совершенную нормальную форму вида (2-5) для следующей таблично заданной функции:

               
               
               
               

в соответствии с алгоритмом получаем:
⇐ Предыдущая12345678910Следующая ⇒


Дата публикования: 2015-02-22; Прочитано: 378 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!

studopedia.org - Студопедия.Орг - 2014-2025 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.008 с)...