double arrow

Інтуїтивний метод спрощення системи ДНФ за матричною формою

Метод Барті-Полянського громіздкий для ручної мінімізації булевих функцій. Ґрунтуючись на матричному представленні системи булевих функцій і максимальних інтервалів методу Закревського, можна знаходити досить гарні розв’язання за матричними формами.

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

Нижче наведені дві послідовності (відповідно у табл. 31.3, 31.3, 31.4 і 31.5, 31.6, 31.7, а також сукупності простих імплікант) виділення інтервалів, що забезпечують одержання оптимального розв’язання для системи булевих функцій.

Таблиця 31.3

      x2 x2
    x1 x1  
    · I   · II
x3|       ·

Таблиця 31.4

      x2 x2
    x1 x1  
  · IV · I  
x3| ·   · III  

Таблиця 31.5

      x2 x2
    x1 x1  
· IV   · II
x3| ·   · III ·

x1`x2`x3 /f1f2, x1x2x3 /f2f3, `x1`x2 /f2f3, `x1x2 /f1f3

Таблиця 31.6

        x2 x2
      x1 x1  
      · ·
  x3| · · · ·
x4| x3|     ·  
x4|   ·      

Таблиця 31.7

        x2 x2
      x1 x1  
      · ·  
  x3|   ·  
x4| x3| · · ·  
x4|   ·      

x1`x3`x4 /f1f2, x1x2x3 /f1f2, `x1`x2`x3x4 /f1f2, x3`x4 /f1, `x2x3x4 /

f1 = x1`x3`x4 Ú x1x2x3 Ú `x1`x2`x3x4 Ú x3`x4

f2 = x1`x3`x4 Ú x1x2x3 Ú `x1`x2`x3x4 Ú `x2x3x4.

Контрольні запитання

1. Що називається найкоротшою й мінімальною ДНФ системи булевих функцій?

2. Що позначають ярлики кон'юнкцій булевих функцій?

3. Що називається простою імплікантою системи булевих функцій?

4. Як використати систему булевих функцій для синтезу КС?

5. Як склеюють набори з ярликами для системи булевих функцій?

6. Які кроки присутні у формуліровці методу Барті-Полянського?

7. Як використати інтуїтивний метод спрощення систем ДНФ за матричною формою?


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: