Минимизация булевых функций

Минимальная ДНФ
ДНФ, содержащая наименьшее общее число вхождений переменных по сравнению со всеми равносильными ей ДНФ.
Минимальная КНФ
КНФ, содеращая наименьшее общее число вхождений переменных по сравнению со всеми равносильными ей КНФ.

Основной метод минимизации – операции попарного неполного склеивания и элементарного поглощения.

\[ \;\overline{x_1}\;x_2x_3x_4 \vee\;\overline{x_1}\;x_2\;\overline{x_3}\;x_4 \]

\[=\;\overline{x_1}\;x_2x_4 (x_3 \vee\;\overline{x_3}\;)\]

\[=\;\overline{x_1}\;x_2x_4 \mathbin{\&}1\]

\[= \;\overline{x_1}\;x_2x_4.\]

\[(\;\overline{x_1}\;\vee x_2\vee x_3\vee x_4) (\;\overline{x_1}\;\vee x_2\vee\;\overline{x_3}\;\vee x_4)\]

\[ = \;\overline{x_1}\;\vee x_2\vee x_4\vee x_3\;\overline{x_3}\; \]

\[ = \;\overline{x_1}\;\vee x_2\vee x_4\vee 0 \]

\[ = \;\overline{x_1}\;\vee x_2\vee x_4. \]

Минимизирующие карты Карно

1952 Эдвард Вейч, 1953 Морис Карно

Карта Карно
Графический способ минимизации булевых функций. Рассматривается как построенная соответствующим образом таблица истинности функции.

Можно рассматривать как определенную плоскую развертку n-мерного булева куба.

Булевы функции \(N\) переменных в СДНФ/СКНФ, могут иметь \(2^N\) членов.

Структура элементарных членов топологически эквивалентна \(N\)-мерному кубу. Аргументы – \(N\)-мерный вектор.

\(x_1\) \(x_2\) \(f(x_1,x_2)\)
0 0 0
0 1 0
1 0 1
1 1 1

 

0 01 1 11 0 00 1 10

СДНФ

0 x̅₁x₂ 1 x₁x₂ 0 x̅₁x̅₂ 1 x₁x̅₂

СКНФ

0 x₁∨x̅₂ 1 x̅₁∨x̅₂ 0 x₁∨x₂ 1 x̅₁∨x₂

СДНФ

0 x̅₁x₂ 1 x₁x₂ 0 x̅₁x̅₂ 1 x₁x̅₂

СКНФ

0 x₁∨x̅₂ 1 x̅₁∨x̅₂ 0 x₁∨x₂ 1 x̅₁∨x₂

Члены на одной грани можно склеить. Если составляется ДНФ, то рассматриваем вершины \(f=1\). Для КНФ – \(f=0\).

В случае функции трёх переменных приходится иметь дело с трёхмерным кубом.

Возможны более сложные конфигурации: напр. 4 члена на одной грани куба

\(\;\overline{x_1}\;\;\overline{x_2}\;\;\overline{x_3}\; \vee x_1\;\overline{x_2}\;\;\overline{x_3}\; \vee\;\overline{x_1}\;\;\overline{x_2}\;x_3 \vee x_1\;\overline{x_2}\;x_3 \\= \;\overline{x_2}\; (\;\overline{x_1}\;\;\overline{x_3}\; \vee\;\overline{x_1}\;x_3 \vee x_1\;\overline{x_3}\; \vee x_1x_3) \\ = \;\overline{x_2}\; (\;\overline{x_1}\; \vee x_1)(\;\overline{x_3}\; \vee x_3) = \;\overline{x_2}\;\)

В общем случае, \(2^K\) членов на \(K\)–мерной грани гиперкуба склеиваются в один член с поглощением \(K\) переменных.

Карта Карно – плоская развёртка гиперкуба. Например:

1 x̅₁x̅₂x̅₃ 1 x̅₁x̅₂x₃ 0 x̅₁x₂x₃ 0 x̅₁x₂x̅₃ 0 x₁x₂x₃ 0 x₁x₂x̅₃ 1 x₁x̅₂x₃ 1 x₁x̅₂x̅₃

Представляется в виде таблицы

\(_{x_3}\backslash^{x_1x_2}\) \(00\) \(01\) \(11\) \(10\)
\(0\) \(1\) \(0\) \(0\) \(1\)
\(1\) \(1\) \(0\) \(0\) \(1\)

Левые ячейки топологически смежны правым.

  • На одной \(K\)-мерной грани – \(2^K\) вершин.
  • Выбираются группы по \(2^K\) смежных ячеек, в результат входят только переменные, неизменные в рамках группы.
  • Общее число членов – число групп.
  • Число неизменных переменных убывает с ростом числа элементов в группе.
  • Выбираются группы максимального размера.
  • Одна комбинация переменных может входить в несколько групп.
\(_{x_3x_4}\backslash^{x_1x_2}\) \(00\) \(01\) \(11\) \(10\)
\(00\) \(f(0000)\) \(f(0100)\) \(f(1100)\) \(f(1000)\)
\(01\) \(f(0001)\) \(f(0101)\) \(f(1101)\) \(f(1001)\)
\(11\) \(f(0011)\) \(f(0111)\) \(f(1111)\) \(f(1011)\)
\(10\) \(f(0010)\) \(f(0110)\) \(f(1110)\) \(f(1010)\)

Возможно для функций 5 и 6 переменных, но сложнее. Для более 6 переменных – непрактично.

Пример

x₃x₄\x₁x₂ 00 01 11 10
00 1 1 0 0
01 1 0 0 0
11 0 1 1 0
10 1 1 1 0
x̅₁x̅₂ x̅₁x₂ x₁x₂ x₁x̅₂
x̅₃x̅₄ 1 1 0 0
x̅₃x₄ 1 0 0 0
x₃x₄ 0 1 1 0
x₃x̅₄ 1 1 1 0

\(\;\overline{x_1}\;\;\overline{x_2}\;\;\overline{x_3}\;\)

\(\vee\)\({x_2}{x_3}\)

\(\vee\)\(\;\overline{x_1}\;\;\overline{x_4}\;\)

Метод Куайна-МакКласки

  • На основе того же аппарата.
  • Более практичен для большого числа переменных.
  • Два шага: склейка, редукция

Склейка

  1. Элементарные члены записываются в двоичной форме в таблицу
  2. Группируются по количеству единиц
  3. Члены, отличающиеся одним битом склеиваются. Бит заменяется на “-”. Рассматриваются только члены из соседних групп
  4. Нельзя склеить? Пометить "*".
  5. Алгоритм повторяется с шага 3, “-”≠“0”, “-”≠“1”.
  6. Из членов “*” составляется сокращенная форма (не обязательно минимальная).

Редукция

  1. Таблица, строки – члены сокращённой формы, столбцы – члены совершенной.
  2. В ячейках “×”, если член сокращённой формы поглощает член совершенной формы (т.е. если заголовок строки является частью заголовка столбца)
  3. Выбираются столбцы, содержащие ровно 1 “×”. Соответствующие члены сокращённой формы составляют ядро, должны войти в минимальную форму.
  4. Если ядро не перекрывает все столбцы, включаются несколько членов сокращённой формы вне ядра, чтобы перекрыть все столбцы.

Пример

n x₁ x₂ x₃ x₄ f
0 0 0 0 0 1
1 0 0 0 1 1
2 0 0 1 0 1
3 0 0 1 1 1
4 0 1 0 0 0
5 0 1 0 1 1
6 0 1 1 0 0
7 0 1 1 1 1
n x₁ x₂ x₃ x₄ f
8 1 0 0 0 1
9 1 0 0 1 0
10 1 0 1 0 1
11 1 0 1 1 0
12 1 1 0 0 1
13 1 1 0 1 1
14 1 1 1 0 0
15 1 1 1 1 1

Члены СДНФ

n x₁ x₂ x₃ x₄ f
0 0 0 0 0 1
1 0 0 0 1 1
2 0 0 1 0 1
3 0 0 1 1 1
5 0 1 0 1 1
7 0 1 1 1 1
n x₁ x₂ x₃ x₄ f
8 1 0 0 0 1
10 1 0 1 0 1
12 1 1 0 0 1
13 1 1 0 1 1
15 1 1 1 1 1

Группировка

n x₁ x₂ x₃ x₄
0 0 0 0 0
3 0 0 1 1
5 0 1 0 1
10 1 0 1 0
12 1 1 0 0
15 1 1 1 1
n x₁ x₂ x₃ x₄
1 0 0 0 1
2 0 0 1 0
8 1 0 0 0
7 0 1 1 1
13 1 1 0 1

Склейка 1

n x₁ x₂ x₃ x₄
0,1 0 0 0 -
0,2 0 0 - 0
0,8 - 0 0 0
13,12* 1 1 0 -
7,5 0 1 - 1
7,3 0 - 1 1
13,5 - 1 0 1
n x₁ x₂ x₃ x₄
2,3 0 0 1 -
1,3 0 0 - 1
8,10 1 0 - 0
1,5 0 - 0 1
8,12* 1 - 0 0
2,10 - 0 1 0
15,13 1 1 - 1
15,7 - 1 1 1

Склейка 2

n x₁ x₂ x₃ x₄
0,1,2,3 * 0 0 - -
0,2,8,10 * - 0 - 0
1,3,7,5 * 0 - - 1
7,5,13,15 * - 1 - 1
n x₁ x₂ x₃ x₄
13,12* 1 1 0 -
8,12* 1 - 0 0

Редукция

0 1 2 3 5 7 8 10 12 13 15 f
12,13 × × x₁x₂x̅₃
8,12 × × x₁x̅₃x̅₄
0,1,2,3 × × × × x̅₁x̅₂
0,2,8,10 × × × × x̅₂x̅₄
5,7,13,15 × × × × x₂x₄
1,3,5,7 × × × × x̅₁x₄

Редукция

0 1 2 3 5 7 8 10 12 13 15 f
12,13 × × x₁x₂x̅₃
8,12 × × x₁x̅₃x̅₄
0,1,2,3 × × × × x̅₁x̅₂
0,2,8,10 × × × ⊗ x̅₂x̅₄
5,7,13,15 × × × ⊗ x₂x₄
1,3,5,7 × × × × x̅₁x₄

Редукция

0 1 2 3 5 7 8 10 12 13 15 f
12,13 × × x₁x₂x̅₃
8,12 × × x₁x̅₃x̅₄
0,1,2,3 × × × × x̅₁x̅₂
0,2,8,10 × × × ⊗ x̅₂x̅₄
5,7,13,15 × × × ⊗ x₂x₄
1,3,5,7 × × × × x̅₁x₄

Редукция

0 1 2 3 5 7 8 10 12 13 15 f
12,13 × × x₁x₂x̅₃
8,12 × × x₁x̅₃x̅₄
0,1,2,3 × × × × x̅₁x̅₂
0,2,8,10 × × × ⊗ x̅₂x̅₄
5,7,13,15 × × × ⊗ x₂x₄
1,3,5,7 × × × × x̅₁x₄

\[ f = \;\overline{x_2}\;\;\overline{x_4}\; \vee {x_2}{x_4} \vee \;\overline{x_1}\;\;\overline{x_2}\; \vee {x_1}{x_2}\;\overline{x_3}\; \]

\[ f = \;\overline{x_2}\;\;\overline{x_4}\; \vee{x_2}{x_4} \vee\;\overline{x_1}\;{x_4} \vee{x_1}\;\overline{x_3}\;\;\overline{x_4}\; \]

x₃x₄\x₁x₂ 00 01 11 10
00 1 1 1
01 1 1 1
11 1 1 1
10 1 1

\[ f = \;\overline{x_2}\;\;\overline{x_4}\; \\\vee{x_2}{x_4} \\\vee\;\overline{x_1}\;\;\overline{x_2}\; \\\vee{x_1}{x_2}\;\overline{x_3}\; \]

x₃x₄\x₁x₂ 00 01 11 10
00 1 1 1
01 1 1 1
11 1 1 1
10 1 1

\[ f = \;\overline{x_2}\;\;\overline{x_4}\; \\\vee{x_2}{x_4} \\\vee\;\overline{x_1}\;{x_4} \\\vee{x_1}\;\overline{x_3}\;\;\overline{x_4}\; \]