Головна

Найпростіші методи синтезу

  1. I. 2.4. Принципи та методи дослідження сучасної психології
  2. I. Методи перехоплення.
  3. I. Найпростіші тригонометричні рівняння
  4. I. Суб'єктивні методи дослідження ендокринної системи.
  5. I. Суб'єктивні методи дослідження кровотворної системи.
  6. I. Суб'єктивні методи дослідження органів жовчовиділення і підшлункової залози.
  7. I. Суб'єктивні методи дослідження органів сечовиділення.

1. Метод синтезу, заснований на моделюванні СДНФ.

2. Модифікація попереднього методу, що полягає у спільній реалізації кон'юнкція.

Метод синтезу, заснований на моделюванні СДНФ, наочно описали при доведенні теореми 1 (рис. 2).

Далі опишемо наступний метод, що полягає у спільній реалізації кон'юнкція (лема).

Позначимо через L  (F / G) мінімальну складність схеми (в базисі Б), яку треба приєднати до схеми, що реалізує функцію G, щоб отримана схема реалізувала функцію F. Очевидно, що

L  (F) L  (G) + L  (F / G). (2)

У нашому випадку Б = (  , &, -).

нехай Qn (x1, ..., Xn) = {X1s1& ... & Xnsn} - Система всіх 2n кон'юнкція від змінних x1, ..., Xn.

Лемма. L (Qn) ~ 2n (Складність реалізацій всіх кон'юнкція від n змінних).

Доведення. кон'юнкцію x1s1& ... & Xnsn можна розбити на 2 частини:

x1s1& ... & Xmsm і xm+1sm+1& ... & Xnsn.

Очевидно, що кожна кон'юнкція x1s1& ... & Xnsn з Q  (x  , ..., X  ) Є кон'юнкція двох кон'юнкція: x1s1& ... & Xmsm з Q  (x  , ..., X  ) І xm+1sm+1& ... & Xnsn з Qn-m (xm+1, ..., Xn).

Тому (згідно рис. 4)

L (Q  / Q  , Q  ) ? 2  . (3)

Мал. 4

З (1) випливає, що

L (Q  ) ? (2m-1) * 2  ? m * 2 ,

L (Q  ) ? [2 (n-m) -1] * 2  ? (n-m) * 2 .

Тому, з огляду на (2) і (3), маємо L (Q  ) ? L (Q  ) + L (Q  ) + L (Q  / Q  , Q  ) ? m * 2  + (N-m) * 2  +2 .

Покладемо тепер m = [  ]. Тоді m * 2 ?  * 2 ,

~
 (N-m) * 2  ? (  +1) * 2  . Значить, L (Q )  <2n.

З іншого боку, очевидно, що при n ? 2 L (Q  ) ?2  , Так як кожна кон'юнкція реалізується на виході деякого елемента.

Таким чином, L (Q  ) ~ 2n. Лема доведена.

~
~
Зауваження. Використовуючи лему, можна вдосконалити попередній метод синтезу, замінивши в схемі на малюнку 2 верхню частину схеми, що реалізує кон'юнкції окремо, схемою, що реалізує їх спільно. При цьому для будь-якої функції f (x1, ..., Xn), F  , Маємо: L (f)  L (Q  ) + 2  , Так як L (Q  ) ~ 2  , То L (f) <2 * 2  . Значить, L (n) <2 * 2 .




Попередня   33   34   35   36   37   38   39   40   41   42   43   44   45   46   47   48   Наступна

Лінійні функції і їх властивості | принцип подвійності | Самодвоїстих функції, їх властивості | Лемма про несамодвойственной функції | Монотонні функції, їх властивості | Лемма про немонотонної функції | передповний клас функцій алгебри логіки | Подання про результати Посту | Завдання для самостійної роботи | Схеми з функціональних елементів |

© um.co.ua - учбові матеріали та реферати