Математическая логика и теория алгоритмов. Галуев Г.А. - 19 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 19 из 64
© 2003 Галуев Геннадий Анатольевич
На рисунке 3 представлен пример комбинационной схемы:
Рис.3
Здесь глубина схемы равна 3 и её максимальная задержка 3
τ .
Пропозиционная форма описывающая логику работы этой схемы имеет вид:
Z=((X
1
∨X
2
)&(X
1
∨X
3
))&((X
2
∨X
4
)&(X
3
∨X
4
))
Также, как и для рассмотренных выше электрических схем, для комбинационных
схем важное значение имеют задачи анализа и синтеза таких схем на основе аппара-
та исчисления высказываний.
В результате решения задачи анализа комбинационной схемы требуется полу-
чить представление каждого выходного сигнала в виде пропозиционной формы, где в
качестве пропозиционных букв используются
символьные обозначения входных сиг-
налов. Для указанной выше комбинационной схемы мы эту задачу уже решили.
В результате решения задачи синтеза комбинационной схемы по заданным таб-
лично (таблица истинности) или в виде пропозиционных форм истинностным функци-
ям, отражающим зависимость выходных сигналов Z от значений входных сигналов X,
нужно построить комбинационную схему реализующую эти функции
. На этапе синте-
за комбинационной схемы решается также задача её максимального упрощения, т.е.
оптимизации.
Рассмотрим полученную в результате анализа комбинационной схемы (см. рис.3)
пропозиционную форму и попробуем её упростить, используя аппарат исчисления
высказываний.
((X
1
∨X
2
)&(X
1
∨X
3
))&((X
2
∨X
4
)&(X
3
∨X
4
))↔((X
1
∨X
2
)&X
1
∨(X
1
∨X
2
)&X
3
)&((X
2
∨X
4
)&X
3
∨(X
2
∨X
4
)&X
4
) ↔ (X
1
∨X
1
&X
3
∨X
2
&X
3
) & (X
2
&X
3
∨X
4
&X
3
∨X
4
) ↔ ((X
1
∨X
2
)&X
3
) & (X
2
&(X
3
∨X
4
)) ↔ (X
1
∨X
2
&X
3
)
& (X
2
&X
3
∨X
4
) ↔ (X
1
∨X
2
&X
3
) & (X
2
&X
3
)∨(X
1
∨X
2
&X
3
)&X
4
↔ (X
1
&X
2
&X
3
)∨(X
2
&X
3
) & (X
2
&X
3
) ∨
(X
1
&X
4
) ∨ (X
2
&X
3
&X
4
) ↔ (X
1
&X
2
&X
3
∨X
2
&X
3
) ∨ X
1
& X
4
∨ X
2
& X
3
& X
4
↔ X
2
& X
3
∨ X
1
& X
4
∨
X
2
& X
3
& X
4
↔ X
2
& X
3
∨ X
1
& X
4
&
&
&
1
1
1
1
4
X
3
X
2
X
1
X
)A()B()C()D(
Z

Страницы