3.5. Упражнения Функциональная полнота

Определить, образует ли заданная функция функционально полный базис. Если нет, то какие функции необходимо добавить, чтобы они вместе с заданной функцией образовали базис?

1. f = (abc) ca ;

2. f = (abcd)v(ab)d ;

3. f = a bc va bc vabc vabc ;

4. f = a bc va b c v abc vabc ;

5. f = (ab)cv (avbvc)  abc;

6. f = (cb)v ac(bd)vd&(⌐(ca));

7. f = ((ab) ac)&(cb). 

Синтез схем

1. Построить схему для заданной пары функций методом факторизации в классическом базисе {2И, 2ИЛИ, НЕ} (в скобках – число элементов в схеме).

1. {f1 =abc v a b c v ac, f2= abc v a b c } (не более 7 эл-тов);

2. {f1 =ac v bс v d (b v c), f2 = a bd v ad v cd v ab d } (не более 8 эл-тов);

3. {f1= ab va b с v ab c), f2 = a v ab v cd v ab d } (не более 4 эл-тов);

4. {f1= ab va b с v ab c, f2 = a (ab) v ab c } (не более 4 эл-тов);

5. {f1= ab vb c v ab c, f2 = a b v a b c v a bc } (не более 5 эл-тов);

6. {f1 = ab va b c v a bc, f2= a b c } (не более 5 эл-тов);

7. {f1 = (ab va b c v a bc), f2 = a v a b v b c } (не более 5 эл-тов).

2. Построить схему для заданной функции методом декомпозиции в классическом базисе {2И, 2ИЛИ, НЕ}, используя разложение К. Шеннона

1. {f = (01101001000111101010010100011110)};

2. {f = (00111101110000100101000110101110)};

3. {f = (00101101000111101010010100011110)};

4. {f = (10011101011000100101000110101110)};

5. {f = (00011101111000100101000110101110)};

6. {f = (11011101001000100101000110101110)};

7. {f = (11010010001011010101101010100101)};

8. {f = 10100101000111101010010100011110) }).

3. Построить схему для заданной функции методом декомпозиции в монофункциональном базисе {3И-НЕ}

1. {f: T1 = (001, 010, 100)};

2. {f: T1 = (001, 010, 100, 111)};

3. {f: T1 = (000, 011, 100, 110)};

4. {f: T1 = (000, 011, 100)};

5. {f: T1 = (010, 100, 101)};

6. {f: T1 = (000, 110, 101)};

7. {f: T1 = (000, 011, 101)}.

4. Построить методом факторизации в классическом базисе {2И, 2ИЛИ, НЕ} плоскую схему с внешним доступом для заданной пары функций

1. {f1 = a b c v a b c, f2= a bc v a b c } (не более 6 эл-тов);

2. {f1 =a vb a, f2= (a b)c v c } (не более 6 эл-тов);

3. {f1 = (b  a)d v d, f2= (a b)c v c} (не более 6 эл-тов);

4. {f1= a bc v abc v a b c, f2= abc v ac v bc} (не более 7 эл-тов);

5. {f1 = bc v ab v a c, f2= bc v ab } (не более 5 эл-тов);

6. {f1 = ab v a c, f2=  (b a v b) } (не более 7 эл-тов).

4. Эксперименты над автоматами

4.1. Построение диагностических деревьев

Реакция нетривиального автомата S на определенные воздействия не предсказуема, если состояние S не известно; с другой стороны, эта реакция всегда может быть предсказана, если начальное состояние известно. Таким образом, одна из основных задач анализа конечных автоматов состоит в том, чтобы распознать состояние исследуемого автомата. После того как состояние распознано, можно определить поведение автомата при всех дальнейших условиях, и могут быть предприняты шаги по введению автомата в различные режимы работы, желательные для исследователя. Существуют две наиболее важные задачи распознавания состояния:

• Задача определения начального состояния автомата (т.е. состояния, в котором находится автомат, когда он предоставляется исследователю);

• Задача распознавания конечного состояния автомата (т.е. состояния, в котором находится автомат, когда завершены испытательные операции, проводимые исследователем).

Решение любой из этих задач составляет решение основной задачи приведения автомата к виду, предсказуемому для исследователя. Инструментом решения этих задач является эксперимент.

Эксперимент - это процесс приложения входных последовательно-стей к автоматам, наблюдения получаемых выходных последовательно-стей и вывода заключений, основанных на этих наблюдениях. Предполагается, что автомат, над которым проводится эксперимент, описан известными таблицами переходов и выходов, и в нём доступны входные и выходные полюса. Заключения следует делать только на основе приложенных воздействий, наблюдаемых реакций и таблиц.

Различают два типа экспериментов:

• Безусловные эксперименты, когда прикладываемая входная последовательность полностью определена заранее.

• Условные эксперименты, когда прикладываемая входная последовательность состоит из двух или более подпоследовательностей, причем каждая подпоследовательность (исключая первую) определена на основании реакций, вызываемых предыдущими подпоследовательностями.

Преимущество условных экспериментов состоит в том, что они могут быть относительно короче; но безусловные эксперименты легче построить, чем условные.

Один автомат называется копией другого, если оба автомата имеют одинаковые таблицы переходов и если они находятся в одном и том же состоянии перед началом эксперимента. Эксперименты могут быть классифицированы по числу требуемых для их проведения экземпляров исследуемого автомата.

Простые эксперименты, когда требуется единственный экземпляр автомата.

Кратные эксперименты, когда требуется более чем один экземпляр автомата.

Так как большинство автоматов, встречающихся в практике, имеются в единственном экземпляре, простые эксперименты предпочтительнее кратных.

Длина эксперимента принимается как общее число входных символов, прикладываемых в процессе проведения эксперимента.

Порядок эксперимента принимается как число входных подпоследовательностей (т.е. последовательностей, разделенных операциями принятия решений), из которых состоит эксперимент.

Кратность эксперимента есть число экземпляров автомата, требующихся при исследовании. Длина, порядок и кратность эксперимента могут рассматриваться как грубые меры его стоимости.