Автор Тема: Найти МДНФ и МКНФ. Карты Карно  (Прочитано 3533 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн dota2

  • Пользователь
  • Сообщений: 22
    • Просмотр профиля
Найти МДНФ и МКНФ. Карты Карно
« : Май 19, 2016, 03:58:26 pm »
Найти МДНФ и МКНФ булевой функции \(  \large 1110 1110  \) с помощью карт Карно (Карнау).

Найти минимальные ДНФ и КНФ функции \(  \large 1100 1110 0111 1111   \)с помощью карт Карно (Карнау). Помогите решить, пожалуйста. Очень нужно.
Заранее спасибо.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 4966
  • Поблагодарили: 1575 раз(а)
    • Просмотр профиля
Найти МДНФ и МКНФ. Карты Карно
« Ответ #1 : Май 25, 2016, 08:46:09 pm »
Составим карту Карно для первой функции:

\( \begin{array}{|c|c|}
\hline
 &  0 & 1   \\
\hline
0 \ 0 &  1 &  1  \\
\hline
0 \ 1 & 1 & 0  \\
\hline
1 \ 1 & 1 & 0  \\
\hline
1 \ 0 & 1 & 1  \\
\hline
\end{array}  \)

Чтобы найти минимальную ДНФ, покроем единицы прямоугольниками максимальной площади, равной неотрицательной степени двойки (см.рисунок 1). Верхняя и нижняя части карты Карно отождествляются.

Красному прямоугольнику соответствуют такие наборы значений булевых переменных:

\( \begin{array}{|c|c|}
\hline
0 &  0 & 0   \\
\hline
0  &  1 &  0  \\
\hline
 1 & 1 & 0  \\
\hline
1  & 0 & 0  \\
\hline

\end{array}  \)

Их общая часть - нуль по переменной \(  \large z  \). Значит, этим наборам соответствует элементарная конъюнкция \(  \large z'  \).

Синему квадрату соответствуют следующие наборы значений булевых переменных:

 
\( \begin{array}{|c|c|}
\hline
0 &  0 & 0   \\
\hline
0  &  0 &  1  \\
\hline
 1 & 0 & 0  \\
\hline
1  & 0 & 1  \\
\hline

\end{array}  \)

Здесь общей частью является нуль по переменной \(  \large y  \). Следовательно, получим элементарную конъюнкцию \(  \large y'  \).

Итак, минимальной ДНФ является \(  \large y' \vee z'  \).

Для отыскания минимальной КНФ покроем нули прямоугольниками максимальной площади (см. рисунок 2).

Красному прямоугольнику соответствуют такие наборы булевых переменных:

\( \begin{array}{|c|c|}
\hline
0 &  1 & 1   \\
\hline
1  &  1 &  1  \\
\hline
\end{array}  \)

Общая часть - единицы по переменным \(  \large y  \) и \(  \large z  \). Им соответствует элементарная дизъюнкция \(  \large y' \vee z'  \). Она и является минимальной КНФ.

Таким образом, минимальные ДНФ и КНФ данной булевой функции совпадают.


 
Сказали спасибо: programmizd, dota2

Оффлайн Admin

  • Администратор
  • Сообщений: 4966
  • Поблагодарили: 1575 раз(а)
    • Просмотр профиля
Найти МДНФ и МКНФ. Карты Карно
« Ответ #2 : Май 25, 2016, 09:33:48 pm »
Карта Карно для второй функции имеет следующий вид:

\( \begin{array}{|c|c|}
\hline
&  00 &  01 &  11 & 10  \\
\hline
00 &  1 &  1 & 0 & 0 \\
\hline
01 & 1 & 1 & 0 & 1 \\
\hline
11 & 1 & 1 &  1 & 1 \\
\hline
10 & 0 & 1 & 1 & 1 \\
\hline
\end{array}  \)

Покрываем единицы четырьмя квадратами \(  \large 2 \times 2  \) и одним прямоугольником \(  \large 2 \times 1  \) (см. рисунок).

Квадрату, расположенному в левом верхнем углу карты Карно соответствуют такие наборы булевых переменных:

\( \begin{array}{|c|c|}
\hline
  0 &  0 & 0 & 0 \\
\hline
 0 & 0 & 0 & 1 \\
\hline
 0 & 1 &  0 & 0 \\
\hline
 0 & 1 & 0 & 1 \\
\hline
\end{array}  \)

Их общая часть - нули по первой и третьей переменным. Следовательно, этому квадрату соответствует элементарная конъюнкция \(  \large x_1'x_3'  \).

Аналогично находим ещё четыре элементарные конъюнкции:

\(  \large x_2 x_3', \ x_1x_4, \ x_1x_3, \ x_2x_3x_4'  \).

Следовательно, минимальная ДНФ имеет вид

\(  \large x_1'x_3' \vee x_2 x_3' \vee x_1x_4 \vee x_1x_3 \vee x_2x_3x_4'  \).

Точно так же можно найти и минимальную КНФ, но покрывать прямоугольниками нужно не единицы, а нули.
 
Сказали спасибо: first