Редактирование: Основы Кибернетики, Алгоритмы решения задач/Задачи на синтез схем
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 18: | Строка 18: | ||
=== Метод каскадов === | === Метод каскадов === | ||
==== Промежуточные действия ==== | ==== Промежуточные действия ==== | ||
- | Пусть у нас имеются булевы функции F<sub>1</sub>(x<sub>1</sub>, x<sub>2</sub>, | + | Пусть у нас имеются булевы функции F<sub>1</sub>(x<sub>1</sub>,x<sub>2</sub>,...x<sub>n</sub>),...,F<sub>k</sub>(x<sub>1</sub>,x<sub>2</sub>,...x<sub>n</sub>), зависящие от n переменных. Обозначим следующее множество: |
- | M<sub>0</sub> = {F<sub>1</sub>(x<sub>1</sub>, x<sub>2</sub>, | + | M<sub>0</sub> = {F<sub>1</sub>(x<sub>1</sub>,x<sub>2</sub>,...x<sub>n</sub>),...,F<sub>k</sub>(x<sub>1</sub>,x<sub>2</sub>,...x<sub>n</sub>)}. |
В простейшем случае, в нем одна функция. Воспользуемся следующим приемом: | В простейшем случае, в нем одна функция. Воспользуемся следующим приемом: | ||
- | F(x<sub>1</sub>, x<sub>2</sub>, | + | F(x<sub>1</sub>,x<sub>2</sub>,...x<sub>n</sub>)=x<sub>1</sub>*F(1,x<sub>2</sub>,...x<sub>n</sub>)V <span style="border-top:solid 1px">x<sub>1</sub></span>*F(0,x<sub>2</sub>,...x<sub>n</sub>) |
- | Тогда определим правило построения следующих множеств (M<sub>1</sub>, M<sub>2</sub>, | + | Тогда определим правило построения следующих множеств (M<sub>1</sub>,M<sub>2</sub>,...,M<sub>n</sub>): |
- | M<sub>i+1</sub> = {g(0,x<sub>i+1</sub>, | + | M<sub>i+1</sub> = {g(0,x<sub>i+1</sub>,...x<sub>n</sub>)|g∈M<sub>i</sub>} U {g(1,x<sub>i+1</sub>,...x<sub>n</sub>)|g∈M<sub>i</sub>}. |
Если функция представлена строкой значений, то формируем новое множество из левых и правых половин. | Если функция представлена строкой значений, то формируем новое множество из левых и правых половин. | ||
Если функция представлена формулой, то подставляем в нее x<sub>i</sub>=0 и x<sub>i</sub>=1 и упрощаем. | Если функция представлена формулой, то подставляем в нее x<sub>i</sub>=0 и x<sub>i</sub>=1 и упрощаем. | ||
Строка 30: | Строка 30: | ||
f<sub>1</sub>(x<sub>1</sub>,x<sub>2</sub>,x<sub>3</sub>,x<sub>4</sub>)=(1000 0010 1111 1000) | f<sub>1</sub>(x<sub>1</sub>,x<sub>2</sub>,x<sub>3</sub>,x<sub>4</sub>)=(1000 0010 1111 1000) | ||
f<sub>2</sub>(x<sub>1</sub>,x<sub>2</sub>,x<sub>3</sub>,x<sub>4</sub>)=(1000 1111 0010 1000) | f<sub>2</sub>(x<sub>1</sub>,x<sub>2</sub>,x<sub>3</sub>,x<sub>4</sub>)=(1000 1111 0010 1000) | ||
- | *M<sub>0</sub> = {(1000 0010 1111 1000),(1000 1111 0010 1000)} | + | *M<sub>0</sub>={(1000 0010 1111 1000),(1000 1111 0010 1000)} |
- | *M<sub>1</sub> = {(1000 0010),(1111 1000),(1000 1111),(0010 1000)} | + | *M<sub>1</sub>={(1000 0010),(1111 1000),(1000 1111),(0010 1000)} |
- | *M<sub>2</sub> = {(1000),(0010),(1111)} | + | *M<sub>2</sub>={(1000),(0010),(1111)} |
- | *M<sub>3</sub> = {(10),<strike>(00)</strike>,<strike>(11)</strike>} | + | *M<sub>3</sub>={(10),<strike>(00)</strike>,<strike>(11)</strike>} |
- | *M<sub>4</sub> = {0,1} | + | *M<sub>4</sub>={0,1} |
==== Получение СФЭ ==== | ==== Получение СФЭ ==== |