24 lines
2.0 KiB
Markdown
24 lines
2.0 KiB
Markdown
Схемы из функциональных элементов. Сложность и глубина схем. Способы построения схем в стандартном базисе.
|
||
|
||
# Схемы из функциональных элементов
|
||
**СФЭ** (Схема из функциональных элементов) - ациклический орграф, содержащий вершины двух типов:
|
||
1. **Входные** (источники) - к вершине приписан уникальный символ переменной
|
||
2. **Функциональные** (гейты) - приписан символ логической функции. [[1 курс/2 семестр/Дискретка/Билеты/7#^3dbfa3|Полустепень захода]] совпадает с числом аргументов соответствующей функции1
|
||
Для гейтов используется ограниченный набор функций:
|
||
- **Стандартный** - $\wedge, \vee, \bar{}$
|
||
- **Базис Жегалкина** - $\oplus, \wedge, 1$
|
||
# Сложность и глубина схем
|
||
- **Сложность схемы** - число гейтов в схеме
|
||
- **Схемная сложность** функции ($L(f)$) - наименьшая сложность схемы, вычисляющий функцию
|
||
- **$L(n)$** - наибольшая системная сложность функции от n переменных
|
||
|
||
> [!Заметка]
|
||
> $L(f)$ и $L(n)$ зависят от базиса
|
||
>
|
||
|
||
- **Глубина схемы** - наибольшая длина ориентированного пути, с началом во входной вершине
|
||
|
||
# Способы построения схем в стандартном базисе
|
||
1. Использование нормальных форм
|
||
2. [[1 курс/2 семестр/Дискретка/Билеты/3#Разложение функции по переменной|Разложение по переменной]]
|