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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...»)
(Отмена правки № 1418 участника 77.132.182.157 (обсуждение))
Строка 1: Строка 1:
-
== From Ebaums Inc to MurkLoar. ==
+
== По заданным эквивалентным формулам или КС построить эквивалентное преобразование, переводящее их друг в друга с помощью основных тождеств. ==
-
We at EbaumsWorld consider you as disgrace of human race.
+
 
-
Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated.
+
=== Основные тождества ===
-
Dig yourself a grave - you will need it.
+
 
 +
==== Для формул ====
 +
* Ассоциативность
 +
** ''t''<sub>&</sub><sup>A</sup>: ''x''<sub>1</sub> & (''x''<sub>2</sub> & ''x''<sub>3</sub>) = (''x''<sub>1</sub> & ''x''<sub>2</sub>) & ''x''<sub>3</sub>
 +
** ''t''<sub>∨</sub><sup>A</sup>: ''x''<sub>1</sub> ∨ (''x''<sub>2</sub> ∨ ''x''<sub>3</sub>) = (''x''<sub>1</sub> ∨ ''x''<sub>2</sub>) ∨ ''x''<sub>3</sub>
 +
* Коммутативность
 +
** ''t''<sub>&</sub><sup>К</sup>: ''x''<sub>1</sub> & ''x''<sub>2</sub> = ''x''<sub>2</sub> & ''x''<sub>1</sub>
 +
** ''t''<sub>∨</sub><sup>К</sup>: ''x''<sub>1</sub> ∨ ''x''<sub>2</sub> = ''x''<sub>2</sub> ∨ ''x''<sub>1</sub>
 +
* Отождествление базовых переменных
 +
** ''t''<sub>&</sub><sup>ОП</sup>: ''x''<sub>2</sub> & ''x''<sub>2</sub> = ''x''<sub>2</sub>
 +
** ''t''<sub>∨</sub><sup>ОП</sup>: ''x''<sub>2</sub> ∨ ''x''<sub>2</sub> = ''x''<sub>2</sub>
 +
* Дистрибутивность
 +
** ''t''<sub>&, ∨</sub><sup>D</sup>: ''x''<sub>1</sub> & (''x''<sub>2</sub> ∨ ''x''<sub>3</sub>) = (''x''<sub>1</sub> & ''x''<sub>2</sub>) ∨ (''x''<sub>1</sub> & ''x''<sub>3</sub>)
 +
* правила де Моргана
 +
** ''t''<sub>&not;</sub><sup>M</sup>: <span style="border-top:double 3px">''x''</span> = ''x''
 +
** ''t''<sub>&</sub><sup>M</sup>: <span style="border-top:solid 1px">(''x''<sub>1</sub> & ''x''<sub>2</sub>)</span> = <span style="border-top:solid 1px">''x''</span><sub>1</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>2</sub>
 +
** ''t''<sub>∨</sub><sup>M</sup>: <span style="border-top:solid 1px">(''x''<sub>1</sub> ∨ ''x''<sub>2</sub>)</span> = <span style="border-top:solid 1px">''x''</span><sub>1</sub> & <span style="border-top:solid 1px">''x''</span><sub>2</sub>
 +
* Тождества подстановки констант
 +
** ''t''<sub>0, &</sub><sup>ПК</sup>: ''x''<sub>1</sub> & (''x''<sub>2</sub> & <span style="border-top:solid 1px">''x''</span><sub>2</sub>) = ''x''<sub>2</sub> & <span style="border-top:solid 1px">''x''</span><sub>2</sub>
 +
** ''t''<sub>0, ∨</sub><sup>ПК</sup>: ''x''<sub>1</sub> ∨ ''x''<sub>2</sub> & <span style="border-top:solid 1px">''x''</span><sub>2</sub> = ''x''<sub>1</sub>
 +
** ''t''<sub>1, &</sub><sup>ПК</sup>: ''x''<sub>1</sub> & (''x''<sub>2</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>2</sub>) = ''x''<sub>1</sub>
 +
** ''t''<sub>1, ∨</sub><sup>ПК</sup>: ''x''<sub>1</sub> ∨ (''x''<sub>2</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>2</sub>) = ''x''<sub>2</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>2</sub>
 +
* Тождество поглощения
 +
** ''t''<sup>П</sup>: ''x''<sub>1</sub> ∨ ''x''<sub>1</sub> & ''x''<sub>2</sub> = ''x''<sub>1</sub>
 +
* Тождество обобщённого склеивания
 +
** ''t''<sup>ОС</sup>: ''x''<sub>1</sub> & ''x''<sub>2</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub> & ''x''<sub>3</sub> = ''x''<sub>1</sub> & ''x''<sub>2</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub> & ''x''<sub>3</sub> ∨ ''x''<sub>2</sub> & ''x''<sub>3</sub>
 +
 
 +
==== Для контактных схем ====
 +
 
 +
===== Основные тождества =====
 +
{|style="text-align:center"
 +
!''t''<sub>1</sub>:
 +
|[[Изображение:Contact scheme t1.png|210px]]
 +
|-
 +
|colspan="2"|<hr />
 +
|-
 +
!''t''<sub>2</sub>:
 +
|[[Изображение:Contact scheme t2.png|430px]]
 +
|-
 +
|colspan="2"|<hr />
 +
|-
 +
!''t''<sub>3</sub>:
 +
|[[Изображение:Contact scheme t3.png|371px]]
 +
|-
 +
|colspan="2"|<hr />
 +
|-
 +
!''t''<sub>4</sub>:
 +
|[[Изображение:Contact scheme t4.png|377px]]
 +
|-
 +
|colspan="2"|<hr />
 +
|-
 +
!''t''<sub>5</sub>:
 +
|[[Изображение:Contact scheme t5.png|294px]]
 +
|-
 +
|colspan="2"|<hr />
 +
|-
 +
!''t''<sub>6</sub><sup>(''m'')</sup>:
 +
|[[Изображение:Contact scheme t6.png|283px]]
 +
|}
 +
 
 +
===== Вспомогательные тождества =====
 +
{|style="text-align:center"
 +
!''t''<sub>7</sub>:
 +
|[[Изображение:Contact scheme t7.png|294px]]
 +
|-
 +
|colspan="2"|<hr />
 +
|-
 +
!''t''<sub>8</sub>:
 +
|[[Изображение:Contact scheme t8.png|402px]]
 +
|-
 +
|colspan="2"|<hr />
 +
|-
 +
!''t''<sub>9</sub>:
 +
|[[Изображение:Contact scheme t9.png|224px]]
 +
|-
 +
|colspan="2"|<hr />
 +
|-
 +
!''t''<sub>10</sub>:
 +
|[[Изображение:Contact scheme t10.png|292px]]
 +
|-
 +
|colspan="2"|<hr />
 +
|-
 +
!''t''<sub>11</sub>:
 +
|[[Изображение:Contact scheme t11.png|399px]]
 +
|}
 +
 
 +
== По заданной формуле построить подобную ей формулу минимальной глубины. ==
 +
Определим для ЭК следующие величины:
 +
* ''n''<sub>i</sub> — число входящих в ЭК переменных
 +
* ''m''<sub>i</sub> — число входящих в ЭК отрицаний
 +
Тогда ''h''<sub>i</sub> = &#8968;log<sub>2</sub>(''n'' + ''m'')&#8969; — минимальная возможная глубина реализации ЭК.
 +
 
 +
Раскроем у формулы все скобки и поднимем отрицания, после чего упорядочим в полученной ДНФ элементарные конъюнкции в порядке убывания их высоты. Далее построим каждую ЭК и начнём объединять их в дизъюнкции справа налево. В результате должна получиться СФЭ с минимальной глубиной.
 +
<!-- Рисуем дерево глубины h, заменяя в нем самые левые ветки с парами листьев на отрицания переменных, далее листья на сами переменные, затем просто забиваем свободные листья единицами, а узлы — конъюнкциями, после чего проводим оптимизацию правой части по принципу s & 1 = s -->
 +
 
 +
Итоговая глубина — h<sub>fin</sub> = &#8968;log<sub>2</sub>(2<sup>h<sub>1</sub></sup> + &hellip; + 2<sup>h<sub>k</sub></sup>))&#8969;.
 +
 
 +
[[Изображение:Minimized height ec.png|thumb|160px|Итоговая СФЭ]]
 +
=== Пример ===
 +
''f'' = <span style="border-top:solid 1px">x<sub>1</sub></span>x<sub>2</sub><span style="border-top:solid 1px">x<sub>3</sub></span>x<sub>4</sub>x<sub>5</sub>.
 +
* ''n'' = 5, ''m'' = 2, h = &#8968;log<sub>2</sub>(5 + 2)&#8969; = 3
 +
f = ((<span style="border-top:solid 1px">x<sub>1</sub></span>) & (<span style="border-top:solid 1px">x<sub>3</sub></span>)) & ((x<sub>2</sub> & x<sub>4</sub>) & x<sub>5</sub>)
 +
 
 +
[[Изображение:Minimized height 1.png|thumb|320px|Упорядоченные ЭК итоговой СФЭ]]
 +
[[Изображение:Minimized height.png|thumb|320px|Итоговая СФЭ]]
 +
=== Пример ===
 +
''f'' = <span style="border-top:solid 1px">x<sub>1</sub></span> ∨ x<sub>2</sub> ∨ x<sub>4</sub>x<sub>5</sub><span style="border-top:solid 1px">x<sub>6</sub></span>x<sub>7</sub>x<sub>8</sub><span style="border-top:solid 1px">x<sub>9</sub></span> ∨ <span style="border-top:solid 1px">x</span><sub>3</sub><span style="border-top:solid 1px">x</span><sub>7</sub>
 +
*<span style="border-top:solid 1px">x<sub>1</sub></span>
 +
** ''n'' = 1, ''m'' = 1, ''h'' = &#8968;log<sub>2</sub>(1 + 1)&#8969; = 1
 +
*x<sub>2</sub>
 +
** ''n'' = 1, ''m'' = 0, ''h'' = &#8968;log<sub>2</sub>(1 + 0)&#8969; = 0
 +
* x<sub>4</sub>x<sub>5</sub><span style="border-top:solid 1px">x<sub>6</sub></span>x<sub>7</sub>x<sub>8</sub><span style="border-top:solid 1px">x<sub>9</sub></span>
 +
** ''n'' = 6, ''m'' = 2, ''h'' = &#8968;log<sub>2</sub>(6 + 2)&#8969; = 3
 +
* <span style="border-top:solid 1px">x</span><sub>3</sub><span style="border-top:solid 1px">x</span><sub>7</sub>
 +
** ''n'' = 2, ''m'' = 2, ''h'' = &#8968;log<sub>2</sub>(2 + 2)&#8969; = 2
 +
 
 +
''h''<sub>final</sub> = &#8968;log<sub>2</sub>(2<sup>1</sup> + 2<sup>0</sup> + 2<sup>3</sup> + 2<sup>2</sup>))&#8969; = &#8968;log<sub>2</sub>(15)&#8969; = 4
 +
 
 +
== По заданной формуле с поднятыми отрицаниями построить моделирующую ее &pi;-схему и обратно. ==
 +
Разбираем формулу или схему поэлементно
 +
* ''A'' ∨ ''B'' эквивалентно ветвлению, где один вариант реализует ''A'', а другой — ''B''
 +
* ''A'' & ''B'' эквивалентно последовательному соединению, где первая часть реализует ''A'', другая — ''B''.
 +
* <span style="border-top:solid 1px">''x''</span><sub>i</sub> эквивалентно контакту с меткой <span style="border-top:solid 1px">''x''</span><sub>i</sub>
 +
* ''x''<sub>i</sub> эквивалентно контакту с меткой ''x''<sub>i</sub>
 +
 
 +
=== Пример ===
 +
[[Изображение:Formula to scheme.png|400px|Исходная контактная схема]]
 +
 
 +
'''Решение:'''<br />
 +
''f'' = <span style="text-decoration:overline;">x</span><sub>6</sub><span style="text-decoration:overline;">x</span><sub>9</sub>x<sub>4</sub>x<sub>5</sub>x<sub>7</sub>x<sub>8</sub> &or; <span style="text-decoration:overline;">x</span><sub>3</sub><span style="text-decoration:overline;">x</span><sub>7</sub> &or; <span style="text-decoration:overline;">x</span><sub>1</sub> &or; x<sub>2</sub>
 +
 
 +
 
 +
{{Курс Основы Кибернетики}}

Версия 17:51, 3 февраля 2008

Содержание

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

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

Для формул

  • Ассоциативность
    • t&A: x1 & (x2 & x3) = (x1 & x2) & x3
    • t∨A: x1 ∨ (x2 ∨ x3) = (x1 ∨ x2) ∨ x3
  • Коммутативность
    • t&К: x1 & x2 = x2 & x1
    • t∨К: x1 ∨ x2 = x2 ∨ x1
  • Отождествление базовых переменных
    • t&ОП: x2 & x2 = x2
    • t∨ОП: x2 ∨ x2 = x2
  • Дистрибутивность
    • t&, ∨D: x1 & (x2 ∨ x3) = (x1 & x2) ∨ (x1 & x3)
  • правила де Моргана
    • t¬M: x = x
    • t&M: (x1 & x2) = x1 ∨ x2
    • t∨M: (x1 ∨ x2) = x1 & x2
  • Тождества подстановки констант
    • t0, &ПК: x1 & (x2 & x2) = x2 & x2
    • t0, ∨ПК: x1 ∨ x2 & x2 = x1
    • t1, &ПК: x1 & (x2 ∨ x2) = x1
    • t1, ∨ПК: x1 ∨ (x2 ∨ x2) = x2 ∨ x2
  • Тождество поглощения
    • tП: x1 ∨ x1 & x2 = x1
  • Тождество обобщённого склеивания
    • tОС: x1 & x2 ∨ x1 & x3 = x1 & x2 ∨ x1 & x3 ∨ x2 & x3

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

Основные тождества
t1:
t2:
t3:
t4:
t5:
t6(m):
Вспомогательные тождества
t7:
t8:
t9:
t10:
t11:

По заданной формуле построить подобную ей формулу минимальной глубины.

Определим для ЭК следующие величины:

  • ni — число входящих в ЭК переменных
  • mi — число входящих в ЭК отрицаний

Тогда hi = ⌈log2(n + m)⌉ — минимальная возможная глубина реализации ЭК.

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

Итоговая глубина — hfin = ⌈log2(2h1 + … + 2hk))⌉.

Итоговая СФЭ
Итоговая СФЭ

Пример

f = x1x2x3x4x5.

  • n = 5, m = 2, h = ⌈log2(5 + 2)⌉ = 3

f = ((x1) & (x3)) & ((x2 & x4) & x5)

Упорядоченные ЭК итоговой СФЭ
Упорядоченные ЭК итоговой СФЭ
Итоговая СФЭ
Итоговая СФЭ

Пример

f = x1 ∨ x2 ∨ x4x5x6x7x8x9 ∨ x3x7

  • x1
    • n = 1, m = 1, h = ⌈log2(1 + 1)⌉ = 1
  • x2
    • n = 1, m = 0, h = ⌈log2(1 + 0)⌉ = 0
  • x4x5x6x7x8x9
    • n = 6, m = 2, h = ⌈log2(6 + 2)⌉ = 3
  • x3x7
    • n = 2, m = 2, h = ⌈log2(2 + 2)⌉ = 2

hfinal = ⌈log2(21 + 20 + 23 + 22))⌉ = ⌈log2(15)⌉ = 4

По заданной формуле с поднятыми отрицаниями построить моделирующую ее π-схему и обратно.

Разбираем формулу или схему поэлементно

  • A ∨ B эквивалентно ветвлению, где один вариант реализует A, а другой — B
  • A & B эквивалентно последовательному соединению, где первая часть реализует A, другая — B.
  • xi эквивалентно контакту с меткой xi
  • xi эквивалентно контакту с меткой xi

Пример

Исходная контактная схема

Решение:
f = x6x9x4x5x7x8 ∨ x3x7 ∨ x1 ∨ x2



Основы Кибернетики

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16

Календарь

пт пт пт пт пт
Февраль
 09 16 26
Март
02 09 16 23 30
Апрель
06 13 20 27
Май
04 11 18 25

Материалы к экзамену

Экзаменационные вопросы 3 потока 2007 (new!) | Алгоритмы решения задач | Теормин | Определения

Получено с http://esyr.name/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
Личные инструменты
Разделы