Редактирование: Основы Кибернетики, Алгоритмы решения задач/Задачи на эквивалентные преобразования и структурное моделирование

Материал из eSyr's wiki.

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

== По заданным эквивалентным формулам или КС построить эквивалентное преобразование, переводящее их друг в друга с помощью основных тождеств. ==

=== Основные тождества ===

==== Для формул ====
* Ассоциативность
** ''t''&A: ''x''1 & (''x''2 & ''x''3) = (''x''1 & ''x''2) & ''x''3
** ''t''∨A: ''x''1 ∨ (''x''2 ∨ ''x''3) = (''x''1 ∨ ''x''2) ∨ ''x''3
* Коммутативность
** ''t''&К: ''x''1 & ''x''2 = ''x''2 & ''x''1
** ''t''∨К: ''x''1 ∨ ''x''2 = ''x''2 ∨ ''x''1
* Отождествление базовых переменных
** ''t''&ОП: ''x''2 & ''x''2 = ''x''2
** ''t''∨ОП: ''x''2 ∨ ''x''2 = ''x''2
* Дистрибутивность
** ''t''&, ∨D: ''x''1 & (''x''2 ∨ ''x''3) = (''x''1 & ''x''2) ∨ (''x''1 & ''x''3)
* правила де Моргана
** ''t''&not;M: ''x'' = ''x''
** ''t''&M: (''x''1 & ''x''2) = ''x''1 ∨ ''x''2
** ''t''∨M: (''x''1 ∨ ''x''2) = ''x''1 & ''x''2
* Тождества подстановки констант
** ''t''0, &ПК: ''x''1 & (''x''2 & ''x''2) = ''x''2 & ''x''2
** ''t''0, ∨ПК: ''x''1 ∨ ''x''2 & ''x''2 = ''x''1
** ''t''1, &ПК: ''x''1 & (''x''2 ∨ ''x''2) = ''x''1
** ''t''1, ∨ПК: ''x''1 ∨ (''x''2 ∨ ''x''2) = ''x''2 ∨ ''x''2
* Тождество поглощения
** ''t''П: ''x''1 ∨ ''x''1 & ''x''2 = ''x''1
* Тождество обобщённого склеивания
** ''t''ОС: ''x''1 & ''x''2 ∨ ''x''1 & ''x''3 = ''x''1 & ''x''2 ∨ ''x''1 & ''x''3 ∨ ''x''2 & ''x''3

==== Для контактных схем ====

===== Основные тождества =====
{|style="text-align:center"
 !''t''1:
 |[[Изображение:Contact scheme t1.png|210px]]
 |-
 |colspan="2"|<hr />
 |-
 !''t''2:
 |[[Изображение:Contact scheme t2.png|430px]]
 |-
 |colspan="2"|<hr />
 |-
 !''t''3:
 |[[Изображение:Contact scheme t3.png|371px]]
 |-
 |colspan="2"|<hr />
 |-
 !''t''4:
 |[[Изображение:Contact scheme t4.png|377px]]
 |-
 |colspan="2"|<hr />
 |-
 !''t''5:
 |[[Изображение:Contact scheme t5.png|294px]]
 |-
 |colspan="2"|<hr />
 |-
 !''t''6(''m''):
 |[[Изображение:Contact scheme t6.png|283px]]
 |}

===== Вспомогательные тождества =====
{|style="text-align:center"
 !''t''7:
 |[[Изображение:Contact scheme t7.png|294px]]
 |-
 |colspan="2"|<hr />
 |-
 !''t''8:
 |[[Изображение:Contact scheme t8.png|402px]]
 |-
 |colspan="2"|<hr />
 |-
 !''t''9:
 |[[Изображение:Contact scheme t9.png|224px]]
 |-
 |colspan="2"|<hr />
 |-
 !''t''10:
 |[[Изображение:Contact scheme t10.png|292px]]
 |-
 |colspan="2"|<hr />
 |-
 !''t''11:
 |[[Изображение:Contact scheme t11.png|399px]]
 |}

== По заданной формуле построить подобную ей формулу минимальной глубины. ==
Определим для ЭК следующие величины:
* ''n''i — число входящих в ЭК переменных
* ''m''i — число входящих в ЭК отрицаний
Тогда ''h''i = &#8968;log2(''n'' + ''m'')&#8969; — минимальная возможная глубина реализации ЭК.

Раскроем у формулы все скобки и поднимем отрицания, после чего упорядочим в полученной ДНФ элементарные конъюнкции в порядке убывания их высоты. Далее построим каждую ЭК и начнём объединять их в дизъюнкции справа налево. В результате должна получиться СФЭ с минимальной глубиной.

Итоговая глубина — hfin = &#8968;log2(2h1 + &hellip; + 2hk))&#8969;.

[[Изображение:Minimized height ec.png|thumb|160px|Итоговая СФЭ]]
=== Пример ===
''f'' = x1x2x3x4x5.
* ''n'' = 5, ''m'' = 2, h = &#8968;log2(5 + 2)&#8969; = 3
f = ((x1) & (x3)) & ((x2 & x4) & x5)

[[Изображение:Minimized height 1.png|thumb|320px|Упорядоченные ЭК итоговой СФЭ]]
[[Изображение:Minimized height.png|thumb|320px|Итоговая СФЭ]]
=== Пример ===
''f'' = x1 ∨ x2 ∨ x4x5x6x7x8x9 ∨ x3x7
*x1
** ''n'' = 1, ''m'' = 1, ''h'' = &#8968;log2(1 + 1)&#8969; = 1
*x2
** ''n'' = 1, ''m'' = 0, ''h'' = &#8968;log2(1 + 0)&#8969; = 0
* x4x5x6x7x8x9
** ''n'' = 6, ''m'' = 2, ''h'' = &#8968;log2(6 + 2)&#8969; = 3
* x3x7
** ''n'' = 2, ''m'' = 2, ''h'' = &#8968;log2(2 + 2)&#8969; = 2

''h''final = &#8968;log2(21 + 20 + 23 + 22))&#8969; = &#8968;log2(15)&#8969; = 4

== По заданной формуле с поднятыми отрицаниями построить моделирующую ее &pi;-схему и обратно. ==
Разбираем формулу или схему поэлементно
* ''A'' ∨ ''B'' эквивалентно ветвлению, где один вариант реализует ''A'', а другой — ''B''
* ''A'' & ''B'' эквивалентно последовательному соединению, где первая часть реализует ''A'', другая — ''B''.
* ''x''i эквивалентно контакту с меткой ''x''i
* ''x''i эквивалентно контакту с меткой ''x''i

=== Пример ===
[[Изображение:Formula to scheme.png|400px|Исходная контактная схема]]

'''Решение:''' 
''f'' = x6x9x4x5x7x8 &or; x3x7 &or; x1 &or; x2

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Шаблон:Курс Основы Кибернетики

Получено с http://esyr.us/wiki/%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D1%8B_%D0%9A%D0%B8%D0%B1%D0%B5%D1%80%D0%BD%D0%B5%D1%82%D0%B8%D0%BA%D0%B8%2C_%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D0%BD%D0%B0_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%BD%D0%BE%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5

@@ Строка 94: / Строка 94: @@
 Тогда ''h''<sub>i</sub> = &#8968;log<sub>2</sub>(''n'' + ''m'')&#8969; — минимальная возможная глубина реализации ЭК.
-<s>Раскроем у формулы все скобки и поднимем отрицания, после чего упорядочим в полученной ДНФ элементарные конъюнкции в порядке убывания их высоты. Далее построим каждую ЭК и начнём объединять их в дизъюнкции справа налево. В результате должна получиться СФЭ с минимальной глубиной.</s> Этого делать нельзя, т.к. строится подобная формула.
+Раскроем у формулы все скобки и поднимем отрицания, после чего упорядочим в полученной ДНФ элементарные конъюнкции в порядке убывания их высоты. Далее построим каждую ЭК и начнём объединять их в дизъюнкции справа налево. В результате должна получиться СФЭ с минимальной глубиной.
 <!-- Рисуем дерево глубины h, заменяя в нем самые левые ветки с парами листьев на отрицания переменных, далее листья на сами переменные, затем просто забиваем свободные листья единицами, а узлы — конъюнкциями, после чего проводим оптимизацию правой части по принципу s & 1 = s -->

Редактирование: Основы Кибернетики, Алгоритмы решения задач/Задачи на эквивалентные преобразования и структурное моделирование

Материал из eSyr's wiki.

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты