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

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

Содержание 1 По заданным эквивалентным формулам или КС построить эквивалентное преобразование, переводящее их друг в друга с помощью основных тождеств. 1.1 Основные тождества 1.1.1 Для формул 1.1.2 Для контактных схем 1.1.2.1 Основные тождества 1.1.2.2 Вспомогательные тождества 2 По заданной формуле построить подобную ей формулу минимальной глубины. 2.1 Пример 2.2 Пример 3 По заданной формуле с поднятыми отрицаниями построить моделирующую ее π-схему и обратно. 3.1 Пример

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

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

Для формул

• Ассоциативность
  • t_&^A: x₁ & (x₂ & x₃) = (x₁ & x₂) & x₃
  • t_∨^A: x₁ ∨ (x₂ ∨ x₃) = (x₁ ∨ x₂) ∨ x₃
• Коммутативность
  • t_&^К: x₁ & x₂ = x₂ & x₁
  • t_∨^К: x₁ ∨ x₂ = x₂ ∨ x₁
• Отождествление базовых переменных
  • t_&^ОП: x₂ & x₂ = x₂
  • t_∨^ОП: x₂ ∨ x₂ = x₂
• Дистрибутивность
  • t_{&, ∨}^D: x₁ & (x₂ ∨ x₃) = (x₁ & x₂) ∨ (x₁ & x₃)
• правила де Моргана
  • t_¬^M: x = x
  • t_&^M: (x₁ & x₂) = x₁ ∨ x₂
  • t_∨^M: (x₁ ∨ x₂) = x₁ & x₂
• Тождества подстановки констант
  • t_{0, &}^ПК: x₁ & (x₂ & x₂) = x₂ & x₂
  • t_{0, ∨}^ПК: x₁ ∨ x₂ & x₂ = x₁
  • t_{1, &}^ПК: x₁ & (x₂ ∨ x₂) = x₁
  • t_{1, ∨}^ПК: x₁ ∨ (x₂ ∨ x₂) = x₂ ∨ x₂
• Тождество поглощения
  • t^П: x₁ ∨ x₁ & x₂ = x₁
• Тождество обобщённого склеивания
  • t^ОС: x₁ & x₂ ∨ x₁ & x₃ = x₁ & x₂ ∨ x₁ & x₃ ∨ x₂ & x₃

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

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

t1:
t2:
t3:
t4:
t5:
t6(m):

Вспомогательные тождества

t7:
t8:
t9:
t10:
t11:

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

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

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

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

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

Итоговая глубина — h_fin = ⌈log₂(2^h₁ + … + 2^h_k))⌉.

Пример

f = x₁x₂x₃x₄x₅.

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

f = ((x₁) & (x₃)) & ((x₂ & x₄) & x₅)

Пример

f = x₁ ∨ x₂ ∨ x₄x₅x₆x₇x₈x₉ ∨ x₃x₇

• x₁
  • n = 1, m = 1, h = ⌈log₂(1 + 1)⌉ = 1
• x₂
  • n = 1, m = 0, h = ⌈log₂(1 + 0)⌉ = 0
• x₄x₅x₆x₇x₈x₉
  • n = 6, m = 2, h = ⌈log₂(6 + 2)⌉ = 3
• x₃x₇
  • n = 2, m = 2, h = ⌈log₂(2 + 2)⌉ = 2

h_final = ⌈log₂(2¹ + 2⁰ + 2³ + 2²))⌉ = ⌈log₂(15)⌉ = 4

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

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

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

Пример

Решение:
f = x₆x₉x₄x₅x₇x₈ ∨ x₃x₇ ∨ x₁ ∨ x₂