2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Получить минимальную систему ДНФ
Сообщение10.05.2011, 19:37 
Получить минимальную систему ДНФ для следующей системы полностью определённых булевых функций:
\begin{bmatrix}
x_1 & x_2 & x_3 & x_4 \\
0 & 0 & 0 & 1 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 1 & 1 \\
1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 \\
0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 \\
1 & 0 & 1 & 1
\end{bmatrix}
\begin{bmatrix}
f_1 & f_2 & f_3 \\
0 & 1 & 1 \\
1 & 1 & 0 \\
1 & 0 & 0 \\
1 & 0 & 1 \\
0 & 0 & 1 \\
0 & 1 & 1 \\
1 & 1 & 0 \\
1 & 0 & 1 \\
0 & 0 & 1
\end{bmatrix}

Помогите, пожалуйста, разобраться с решением.
сначала я сортирую данные матрицы для удобства:
\begin{bmatrix}
x_1 & x_2 & x_3 & x_4 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 1 & 1 \\
1 & 0 & 0 & 1 \\
0 & 1 & 1 & 0 \\
1 & 1 & 0 & 1 \\
1 & 0 & 1 & 1
\end{bmatrix}
\begin{bmatrix}
f_1 & f_2 & f_3 \\
1 & 0 & 1 \\
0 & 1 & 1 \\
1 & 1 & 0 \\
1 & 0 & 0 \\
1 & 0 & 1 \\
0 & 1 & 1 \\
1 & 1 & 0 \\
0 & 0 & 1 \\
0 & 0 & 1
\end{bmatrix}
Дальше склеиваю строки, но только соседние, то есть отличающиеся не более чем на одну единицу. Кажется, такие строки называют простыми импликантами.
получается:
\begin{bmatrix}
x_1 & x_2 & x_3 & x_4 \\
0 & 0 & 0 & - \\
0 & - & 0 & 0 \\
0 & 0 & - & 0 \\
0 & 0 & - & 1 \\
- & 0 & 0 & 1 \\
0 & 1 & - & 0 \\
0 & 0 & 1 & - \\
0 & - & 1 & 0 \\
- & 0 & 1 & 1 \\
1 & - & 0 & 1 \\
1 & 0 & - & 1
\end{bmatrix}
\begin{bmatrix}
f_1 & f_2 & f_3 \\
0 & 0 & 1 \\
1 & 0 & 0 \\
1 & 0 & 0 \\
0 & 0 & 1 \\
0 & 1 & 1 \\
1 & 1 & 0 \\
1 & 0 & 0 \\
1 & 0 & 0 \\
0 & 0 & 1 \\
0 & 0 & 1 \\
0 & 0 & 1
\end{bmatrix}
дальше склеиваются 2-я, 3-я, 4-я, 8-я и 11-я строки.
в результате я строю таблицу похожую на эту:
\begin{vmatrix}
\ & \ & f_1 & f_2 & f_3 \\
\ & \ & 13457 & 2367 & 125689 \\
000- & 001 & 00000 & 0000 & 110000 \\
0-00 & 100 & 11000 & 0000 & 000000 \\
00-0 & 100 & 10100 & 0000 & 000000 \\
-001 & 011 & 00000 & 1010 & 010100 \\ 
01-0 & 110 & 01001 & 0101 & 000000 \\
001- & 100 & 00110 & 0000 & 000000 \\
0-10 & 100 & 00101 & 0000 & 000000 \\
-011 & 001 & 00000 & 0000 & 001001 \\
1-01 & 001 & 00000 & 0000 & 000110
\end{vmatrix}
и теперь как-то применяя метод Квайна-МакКласки я должна это всё минимизировать.
В общем, у меня ничего не выходит. Нужна ваша помощь.
из матрицы выходит такая ДФ для $f_1$:
$\bar{x_1} \bar{x_3} \bar{x_4} \vee \bar{x_1}x_2 \bar{x_4}\vee\bar{x_1}\bar{x_2}x_3$
Верно?

 
 
 [ 1 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group