Автор Тема: Минимизировать функции  (Прочитано 831 раз)

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

Оффлайн Валерия

  • Пользователь
  • Сообщений: 5
    • Просмотр профиля
Минимизировать функции
« : Ноябрь 06, 2015, 01:54:20 pm »
Минимизировать функции по картам Карно и найти сложность по Квайну:
       а) Найти мин. сумму                     б) Найти мин. произведение
 

Оффлайн phobos

  • Модератор
  • Сообщений: 95
  • Поблагодарили: 85 раз(а)
    • Просмотр профиля
Re: Минимизировать функции
« Ответ #1 : Ноябрь 11, 2015, 02:12:58 pm »
Под мин. суммой и мин. произведением понимаются минимальные ДНФ и КНФ соответственно? На второй карте функция  частично определена?

Оффлайн Admin

  • Администратор
  • Сообщений: 5246
  • Поблагодарили: 1587 раз(а)
    • Просмотр профиля
Re: Минимизировать функции
« Ответ #2 : Ноябрь 11, 2015, 03:25:48 pm »
Так это карты Карно для функций четырёх переменных...

1) Найдём минимальную ДНФ первой функции. Для этого склеим области с числом единиц, равным \(  \large 2^n \), где \(  \large n \in \mathbb{N} \cup 0 \), причём будем выбирать области как можно большей площади, так, чтобы количество областей было минимальным. Учтём , что карта Карно наклеена на тор. Для области, выделенной красным цветом, имеем следующие конъюнкции: \(  \large x_1'x_2x_3'x_4, \ x_1'x_2x_3x_4 \). Выбираем переменные (или их отрицания), общие для этих конъюнкций: \(  \large x_1'x_2x_4 \). Для области, выделенной зелёным: \(  \large x_1x_2'x_3'x_4', \ x_1'x_2'x_3x_4' \ \Rightarrow \ x_2'x_4' \). Для синей области: \(  \large x_1x_2x_3'x_4', \ x_1x_2x_3x_4' \ \Rightarrow \ x_1x_2x_4' \). Наконец, для жёлтой области: \(  \large x_1x_2'x_3x_4 \). Соединяя полученные конюнкции знаком дизъюнкции, получим минимальную ДНФ булевой функции: \(  \large x_1'x_2x_4 \vee x_2'x_4' \vee x_1x_2x_4' \vee x_1x_2'x_3x_4 \).

Под мин. суммой и мин. произведением понимаются минимальные ДНФ и КНФ соответственно? На второй карте функция  частично определена?

Скорее всего, да.

2) Cложностью по Квайну булевой функции называется количество переменных в аналитическом выражении функции. В данном случае сложность равна 9.
 

Оффлайн phobos

  • Модератор
  • Сообщений: 95
  • Поблагодарили: 85 раз(а)
    • Просмотр профиля
Re: Минимизировать функции
« Ответ #3 : Ноябрь 12, 2015, 03:00:41 am »
Немного поправлю решение Admin'а. Зеленые области таким образом нельзя склеивать, так как на них набора не являются соседними (отличаются более чем в одной координате).

\(  \large I_{1}=\begin{Bmatrix}\ (0101)\\ (0111)\\\end{Bmatrix}\rightarrow K_{1}=x_{1}'x_{2}x_{4}; \)
\(  \large I_{2}=\begin{Bmatrix}\ (1100)\\ (1000)\\\end{Bmatrix}\rightarrow K_{2}=x_{1}x_{3}'x_{4}'; \)
\(  \large I_{3}=\begin{Bmatrix}\ (1100)\\ (1110)\\\end{Bmatrix}\rightarrow K_{3}=x_{1}x_{2}x_{4}'; \)
\(  \large I_{4}=\begin{Bmatrix}\ (0010)\\\end{Bmatrix}\rightarrow K_{4}=x_{1}'x_{2}'x_{3}x_{4}'; \)
\(  \large I_{5}=\begin{Bmatrix}\ (1011)\\\end{Bmatrix}\rightarrow K_{5}=x_{1}x_{2}'x_{3}x_{4}; \)

Все найденные конъюнкции \(  \large K_{1},K_{2},K_{3},K_{4},K_{5} \) входят в минимальную ДНФ.
 
Сказали спасибо: Admin

Оффлайн Admin

  • Администратор
  • Сообщений: 5246
  • Поблагодарили: 1587 раз(а)
    • Просмотр профиля
Re: Минимизировать функции
« Ответ #4 : Ноябрь 12, 2015, 10:41:26 am »
Немного поправлю решение Admin'а. Зеленые области таким образом нельзя склеивать, так как на них набора не являются соседними (отличаются более чем в одной координате).

phobos, спасибо. Немного подзабыл карты Карно...