Відмінності між версіями «Алгоритм Блейка»

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
[перевірена версія][очікує на перевірку]
м (правопис)
 
(Не показано 3 проміжні версії 2 користувачів)
Рядок 1: Рядок 1:
'''Алгоритм Блейка''' — [[алгоритм]] отримання скороченої [[диз'юнктивна нормальна форма|диз'юнктивної нормальної форми]] (ДНФ) булевої функції із довільної ДНФ.
+
'''Алгоритм Блейка''' — [[алгоритм]] отримання скороченої [[диз'юнктивна нормальна форма|диз'юнктивної нормальної форми]] (ДНФ) булевої функції із довільної ДНФ.
   
 
Алгоритм оснований на теоремі Блейка:
 
Алгоритм оснований на теоремі Блейка:
:Якщо в довільній ДНФ [[булева функція|булевої функції]] виконати всі можливі узагальнені зклеювання, а потім усунути всі елементарні поглинання, то в результаті отримаємо скорочена ДНФ функції.
+
: Якщо в довільній ДНФ [[булева функція|булевої функції]] виконати всі можливі узагальнені зклеювання, а потім усунути всі елементарні поглинання, то в результаті отримаємо скорочену ДНФ функції.
   
 
Операція узагальненого зклеювання полягає в застосуванні тотожного співвідношення
 
Операція узагальненого зклеювання полягає в застосуванні тотожного співвідношення
: ''AC'' ∨ ''B''¬''C'' = ''A''¬''C'' ∨ ''B''¬''C'' ∨ ''AB'',
+
: ''AC'' ∨ ''B''¬''C'' = '''' ∨ ''B''¬''C'' ∨ ''AB'',
 
яке не змінює значення булевої функції.
 
яке не змінює значення булевої функції.
   
 
В ряді випадків алгоритм Блейка визначає мінімальну форму булевої функції:
 
В ряді випадків алгоритм Блейка визначає мінімальну форму булевої функції:
* якщо скорочена ДНФ булевої функції не містить заперечувань змінних, то вона є одночасно мінімальною формою, притому єдиною;
+
* якщо скорочена ДНФ булевої функції не містить заперечувань змінних, то вона є одночасно мінімальною формою, при тому єдиною;
 
* якщо в простих імплікантах скороченої ДНФ всі змінні містяться тільки з запереченням, то вона буде і мінімальною.
 
* якщо в простих імплікантах скороченої ДНФ всі змінні містяться тільки з запереченням, то вона буде і мінімальною.
 
Тільки монотонні булеві функції мають скорочені ДНФ, які не мітять заперечень змінних.
 
Тільки монотонні булеві функції мають скорочені ДНФ, які не мітять заперечень змінних.

Поточна версія на 10:55, 25 квітня 2021

Алгоритм Блейка — алгоритм отримання скороченої диз'юнктивної нормальної форми (ДНФ) булевої функції із довільної ДНФ.

Алгоритм оснований на теоремі Блейка:

Якщо в довільній ДНФ булевої функції виконати всі можливі узагальнені зклеювання, а потім усунути всі елементарні поглинання, то в результаті отримаємо скорочену ДНФ функції.

Операція узагальненого зклеювання полягає в застосуванні тотожного співвідношення

ACB¬C = B¬CAB,

яке не змінює значення булевої функції.

В ряді випадків алгоритм Блейка визначає мінімальну форму булевої функції:

  • якщо скорочена ДНФ булевої функції не містить заперечувань змінних, то вона є одночасно мінімальною формою, при тому єдиною;
  • якщо в простих імплікантах скороченої ДНФ всі змінні містяться тільки з запереченням, то вона буде і мінімальною.

Тільки монотонні булеві функції мають скорочені ДНФ, які не мітять заперечень змінних.

Алгоритм Блейка застосовують при мінімізації булевих функцій для отримання їхніх простих імплікант.

Джерела інформації[ред. | ред. код]

Див. також[ред. | ред. код]