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

[Merkader]

Помогите, пожалуйста, разобраться в методе Квайна-МакКласки. В контрольной по дискретной математике нужно решить задачу применив этот метод.

В качестве примера в книге рассматривается булева функция, заданая следующей матрицей:
x_1 \ x_2 \ x_3 \ x_4 \\ \ \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{bmatrix}
Первый этап выполняется путём применения операции простого склеивания над конъюнкциями.
Данную матрицу упорядочивают и склеивают конъюнкции, при этом помечая те, которые склеиваются (верно я понимаю?)
C_0= \begin{bmatrix} x_1 & x_2 & x_3 & x_4 \\ 0 & 0 & 0 & 0 & * \\ 0 & 0 & 1 & 0 & * \\ 1 & 0 & 0 & 0 & * \\ 0 & 0 & 1 & 1 & * \\ 1 & 0 & 0 & 1 & * \\ 0 & 1 & 1 & 1 & * \\ 1 & 0 & 1 & 1 & * \\ 1 & 1 & 1 & 1 & * \end{bmatrix}

C_1= \begin{bmatrix} \ x_1 & x_2 & x_3 & x_4 \\ 0 \ & 0 \ & - \ & 0 \\ - \ & 0 \ & 0 \ & 0 \\ 0 \ & 0 \ & 1 \ & - \\ 1 \ & 0 \ & 0 \ & - \\ 0 \ & - \ & 1 \ & 1 & * \\ - \ & 0 \ & 1 \ & 1 & * \\ 1 \ & 0 \ & - \ & 1 \\ - \ & 1 \ & 1 \ & 1 & * \\ 1 \ & - \ & 1 \ & 1 & * \end{bmatrix}
почему склеивается только или именно 5-я, 6-я, 8-я и 9-я строка? почему нельзя склеить 1-ю и 2-ю или любые другие строки?
C_2= { \begin{bmatrix} x_1 & x_2 & x_3 & x_4 \\ - & - & 1 & 1 \end{bmatrix}}
само склеивание мне понятно.
понятно, что в результате вышеперечисленного получается матрица из С_1 и С_2
x_1 \ x_2 \ x_3 \ x_4 \\ \begin{bmatrix} 0 & 0 & - & 0 \\ - & 0 & 0 & 0 \\ 0 & 0 & 1 & - \\ 1 & 0 & 0 & - \\ 1 & 0 & - & 1 \\ - & - & 1 & 1 \end{bmatrix}
Далее применяется задача о кратчайшем покрытии
x_1 \ x_2 \ x_3 \ x_4 \\ \begin{bmatrix} 0 & 0 & 0 & 0 & a_1 \\ 0 & 0 & 1 & 0 & a_2 \\ 1 & 0 & 0 & 0 & a_3 \\ 0 & 0 & 1 & 1 & a_4 \\ 1 & 0 & 0 & 1 & a_5 \\ 0 & 1 & 1 & 1 & a_6 \\ 1 & 0 & 1 & 1 & a_7 \\ 1 & 1 & 1 & 1 & a_8 \end{bmatrix}

x_1 \ \ x_2 \ \ x_3 \ \ x_4 \\ \begin{bmatrix} 0 & 0 & - & 0 & B_1 \\ - & 0 & 0 & 0 & B_2 \\ 0 & 0 & 1 & - & B_3 \\ 1 & 0 & 0 & - & B_4 \\ 1 & 0 & - & 1 & B_5 \\ - & - & 1 & 1 & B_6 \end{bmatrix}
Помогите, пожалуйста, понять и разобраться.
Вот матрица, которую в результате этого получают:
{\begin{bmatrix} a_1 & a_2 & a_3 & a_4 & a_5 & a_6 & a_7 & a_8 \\ 1 \ & 1 \ & 0 \ & 0 \ & 0 \ & 0 \ & 0 \ & 0 & B_1 \\ 1 \ & 0 \ & 1 \ & 0 \ & 0 \ & 0 \ & 0 \ & 0 & B_2 \\ 0 \ & 1 \ & 0 \ & 1 \ & 0 \ & 0 \ & 0 \ & 0 & B_3 \\ 0 \ & 0 \ & 1 \ & 0 \ & 1 \ & 0 \ & 0 \ & 0 & B_4 \\ 0 \ & 0 \ & 0 \ & 0 \ & 1 \ & 0 \ & 1 \ & 0 & B_5 \\ 0 \ & 0 \ & 0 \ & 1 \ & 0 \ & 1 \ & 1 \ & 1 & B_6 \end{bmatrix}}
далее выделяются строки и покрываемые ими столбцы -- это мне более ли менее ясно на данном примере. В своей задаче, возможно, вызовет трудности.

[Tlalok]

Merkader в сообщении #444042 писал(а):

почему склеивается только или именно 5-я, 6-я, 8-я и 9-я строка? почему нельзя склеить 1-ю и 2-ю или любые другие строки?

Склеиваются те строки, которые отличаются ОДНИМ значением.
$Ax \vee A\overline x = A$

[Merkader]

почему тогда не склеить первую и третью? тоже на одно значение отличаются...
как разобраться?

[Tlalok]

Нет, они отличаются друг от друга в принципе.За нулями и единицами стоят переменные булевой функции. Каждый нолик это $\overline x_i$, а каждая единичка это $x_i$.
Склеиваются только в том случае, если набор переменных одинаков.
5-ая и 9-ая строки склеиваются
$\overline {{x_1}} {x_3}{x_4} \vee {x_1}{x_3}{x_4} = {{x_3}{x_4}}$
1-ая и 3-ая строки не склеиваются
$\overline {{x_1}} \overline {{x_2}} {x_4} \vee \overline {{x_1}} \overline {{x_2}} {x_3}$