Предыдущая страница реферата | 7  8  9  10  11  12  13  14  15  16  17 | Следующая страница реферата

1)S1 =((,&,(((булев базис)

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

Система S1 =((,&,(( является избыточной так как из нее можно удалить одну из функций (& или () без нарушения функциональной полноты.

Получаемые при этом системы S2 ={(,&}(и S3((,&,((обычно называют сокращенным булевым базисом .

Недостающие операции( ( в системе S2 и & в системе S3 ) могут быть выражены с помощью следствий из законов

____
Де Моргана : x1V x2= [pic]1[pic]2

_____ x1 x2= [pic]1 v[pic]2

Функциональная полнота системы булевых функций называется минимальной
,если удаление из нее какой-либо функции приводит к нарушению свойства функциональной полноты.
Системы из одной функции S4=((стрелка Пирса)

S5=|(штрих Шеффера) которые принято называть универсальным базисом.
2)Базис Жегалкина S6= {&, (, 1}

Понятие функциональной полноты системы булевых функций связано с аналогичным понятием для системы логических элементов.

Эта связь заключается в следующем :

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

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

Теорема о функциональной полноте (Пост - Яблонского).
Для того, чтобы система булевых функций была функционально полной необходимо и достаточно чтобы она содержала хотя бы одну функцию не:

1) cохраняющую константу ноль

2) cохраняющую константу единица

3) линейную функцию

4) монотонную функцию

5) самодвойственную функцию.

Замечательные классы булевых функций.
1. Булева функция называется сохраняющей константу ноль , если на нулевом наборе аргументов она принимает значение равное нулю, то есть f(0,0,0,...,0) = 0;

В противном случае функция относится к классу не cохраняющих константу ноль.

К функциям ,сохраняющим константу ноль относятся f(x1,x2)= x1 v x2 f(x1,x2)= x1 * x2

К функциям не cохраняющим константу ноль относятся f(x)=[pic] и f(x1,x2)=x1(x2

2.Булева функция называется сохраняющей константу единица , если на единичном наборе аргументов она принимает значение равное единице, то есть f(1,1,1,...,1)= 1;

В противном случае функция относится к классу не cохраняющих константу единица.

Рекомендуем скачать другие рефераты по теме: реферат на тему менеджмент, класс.



Предыдущая страница реферата | 7  8  9  10  11  12  13  14  15  16  17 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки