Функциональная полнота

Классы функций

Минимизация ФАЛ

Разложение функций

Задачи Контрольные вопросы и задания

5.8.1. Представление функций

Задача 1. Для функций, описанных выше, постройте представление их в виде СДНФ.

Задача 2. Для функций, описанных в первой задаче, постройте разложение Шеннона по переменной b и определите существенную зависимость от переменной с.

Задача 1. Для функций, описанных в разд. 5.8.1, постройте СДНФ. Используя операции склеивания и поглощения, найдите минимальные ДНФ. Найдите минимальные ДНФ через карты Карно.

Задача 2. Для функций задачи 1 получите ДНФ следующим образом. Каждую из элементарных функций представьте в виде ДНФ, затем эти формулы подставьте в описания функций, раскройте скобки и сделайте необходимые преобразования, используя свойства функций: коммутативность, дистрибутивность, правило де Моргана и др.

Задача 3. Используя карты Карно, запишите в виде ДНФ самую сложную функцию от 4 переменных. Используя вынесение за скобки (свойство дистрибуции операций конъюнкции и дизъюнкции), запишите эту функцию в скобочной форме.

Монотонные функции

Задача 1. Выпишите все монотонные функции, существенно зависимые от трёх переменных. Если в одну группу отнести функции, получающиеся одна из другой переименованием переменных, то сколько групп будет в этом множестве? (ПримерПример. Функции (хуÚz) , (xzÚy) и (yzÚx) будут в одной группе).

Задача 2. Являются ли монотонными следующие функции:

Вариант 1. ((а->bb) Å (bb~cc))->dd

Вариант 2. (aa Å bb)->(bb->cc) Ù (`ddÚbbccaa);

Вариант 3. ((aa->bb)->cc) Ú`aaddcc) Å (aa Å bb);

Вариант 4. (`aa->bb) Å (bb->aacc) Ú (aa->cc);

Вариант 5. ((aa->`bb)->cc) Ú aa`ddcc) Å (`aaÅbb);

Вариант 6. ((dd->bb)->cc) Ú`aaddcc) Å (`aa Å bb);

Вариант 7. ((dd->bb) Å (`bb~cc)) Å dd;

Вариант 8. ((а Å bb) Å (bbÚdd))->bbdd.

Самодвойственные функции

Задача 3. Проверьте, являются ли самодвойственными функции задачи 2.

Задача 4. Перечислите все самодвойственные функции, сущест­венно зависящие от трёх переменных.

Так же, как в задаче 1, определите, сколько групп в этом множестве.

Линейные функции.

Задача 5. Постройте полиномы Жегалкина для простейших функций.

Задача 6. Постройте полином Жегалкина для следующих функций:.

1. ((а->bb)&(bb~cc))->dd

2. (aaÚ`bb)->(bb->cc)Ù(`ddÚbbccaa);

3. ((aa->bb)->cc)Ú`aaddcc)Ú(aaÅbb);

4. ((aa ->`bb)->cc)Ú`aa`ddcc)Ú(`aaÅbb);

5. ((dd ->bb) ->cc) Ú`aaddcc) Å (`aaÚbb);

6. ((dd ->bb) Å (`bb~cc)) Ú`dd

7. ((а Å bb) Å (bbÚdd))>(`bb`×dd)

Задача 1. Постройте функции шефферовского типа, существенно зависящие от трёх переменных.

Задача 2. Являются ли функцияфункции, приведённые вышениже, функцией функциями шефферовского типа? Если нет, то какую функцию для каждой из нихк ней необходимо добавить, чтобы ониа образовалиа функционально полный базис?

Вариант 1: f=<01101001>;

Вариант 2: f=<00010011>;

Вариант 3: f=<00101011>;

Вариант 4: f=<10010110>;

Вариант 5: f=<11001010>;

Вариант 6: f=<01110100>;

Вариант 7: f=><00010111>;

Вариант 8: f=<10011100>;

Вариант 9: f=<11010000>