Редактирование: Основы Кибернетики, Алгоритмы решения задач/Задачи на синтез схем
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 3: | Строка 3: | ||
=== Простейшие методы === | === Простейшие методы === | ||
==== Промежуточные действия ==== | ==== Промежуточные действия ==== | ||
- | * Если ФАЛ представлена в виде таблицы, то построим по ней совершенную ДНФ (как объединение всех возможных случаев, когда она равна 1). | + | * Если ФАЛ представлена в виде таблицы, то построим по ней сокращённую(может совершенную????) ДНФ (как объединение всех возможных случаев, когда она равна 1). |
* Если ФАЛ представлена в виде формулы, преобразуем ее, чтобы остались только функции базиса Б<sub>0</sub>. Кроме того, поднимаем все отрицания (они должны стоять только над переменными, но не над бо́льшими кусками выражения). | * Если ФАЛ представлена в виде формулы, преобразуем ее, чтобы остались только функции базиса Б<sub>0</sub>. Кроме того, поднимаем все отрицания (они должны стоять только над переменными, но не над бо́льшими кусками выражения). | ||
Строка 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),<strike>(1111)</strike>} |
- | *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} |
==== Получение СФЭ ==== | ==== Получение СФЭ ==== | ||
Строка 49: | Строка 49: | ||
==== Получение КС ==== | ==== Получение КС ==== | ||
Обозначаем все элементы всех множеств узлами КС. | Обозначаем все элементы всех множеств узлами КС. | ||
- | *если g(x<sub>i+1</sub>,...x<sub>n</sub>)=h(0,x<sub>i+1</sub>,...x<sub>n</sub>), то | + | *если g(x<sub>i+1</sub>,...x<sub>n</sub>)=h(0,x<sub>i+1</sub>,...x<sub>n</sub>), то соединаям g и h контактом с меткой <span style="border-top:solid 1px">x<sub>i</sub></span> |
- | *если g(x<sub>i+1</sub>,...x<sub>n</sub>)=h(1,x<sub>i+1</sub>,...x<sub>n</sub>), то | + | *если g(x<sub>i+1</sub>,...x<sub>n</sub>)=h(1,x<sub>i+1</sub>,...x<sub>n</sub>), то соединаям g и h контактом с меткой x<sub>i</sub> |
После этого удаляем вершину с меткой 0 и все ведущие в нее контакты. Вершину с меткой 1, а также F<sub>1</sub>,...,F<sub>k</sub> помечаем как входы КС. | После этого удаляем вершину с меткой 0 и все ведущие в нее контакты. Вершину с меткой 1, а также F<sub>1</sub>,...,F<sub>k</sub> помечаем как входы КС. | ||