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

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

Версия от 16:15, 15 июня 2011; 89.178.0.82 (Обсуждение)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Содержание

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

[править] Основные тождества

[править] Для формул

  • Ассоциативность
    • t&A: x1 & (x2 & x3) = (x1 & x2) & x3
    • tA: x1 ∨ (x2x3) = (x1x2) ∨ x3
  • Коммутативность
    • t&К: x1 & x2 = x2 & x1
    • tК: x1x2 = x2x1
  • Отождествление базовых переменных
    • t&ОП: x2 & x2 = x2
    • tОП: x2x2 = x2
  • Дистрибутивность
    • t&, ∨D: x1 & (x2x3) = (x1 & x2) ∨ (x1 & x3)
  • правила де Моргана
    • t¬M: x = x
    • t&M: (x1 & x2) = x1x2
    • tM: (x1x2) = x1 & x2
  • Тождества подстановки констант
    • t0, &ПК: x1 & (x2 & x2) = x2 & x2
    • t0, ∨ПК: x1x2 & x2 = x1
    • t1, &ПК: x1 & (x2x2) = x1
    • t1, ∨ПК: x1 ∨ (x2x2) = x2x2
  • Тождество поглощения
    • tП: x1x1 & x2 = x1
  • Тождество обобщённого склеивания
    • tОС: x1 & x2x1 & x3 = x1 & x2x1 & x3x2 & 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 ∨ x4x5x6x7x8x9x3x7

  • 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

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

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

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

[править] Пример

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

Решение:
f = x6x9x4x5x7x8x3x7x1 ∨ 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!) | Алгоритмы решения задач | Теормин | Определения

Личные инструменты
Разделы