Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Топ:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного...
Интересное:
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Дисциплины:
2017-10-11 | 409 |
5.00
из
|
Заказать работу |
|
|
Определение 1.4.8. Система переключательных функций называется функционально полной, если с помощью функций, входящих в эту систему, применяя операции суперпозиции и подстановки, можно получить любую, сколь угодно сложную переключательную функцию.
Теорема о функциональной полноте. Для того чтобы система переключательных функций была функционально полной, необходимо и достаточно, чтобы эта система включала:
хотя бы одну переключательную функцию, не сохраняющую нуль;
хотя бы одну переключательную функцию, не сохраняющую единицу;
хотя бы одну нелинейную переключательную функцию:
хотя бы одну немонотонную переключательную функцию;
хотя бы одну несамодвойственную переключательную функцию.
Таблица 1.6
Переключательные функции двух аргументов
x | Линейные (TL) | Сохраняющие 0 (T0) | Сохраняющие 1 (T1) | Монотонные (TM) | Самодвойственные (Ts) | ||||
y | |||||||||
f0(x,y) | * | * | * | ||||||
f1(x,y) | * | * | * | ||||||
f2(x,y) | * | ||||||||
f3(x,y) | * | * | * | * | * | ||||
f4(x,y) | * | ||||||||
f5(x,y) | * | * | * | * | * | ||||
f6(x,y) | * | * | |||||||
f7(x,y) | * | * | * | ||||||
f8(x,y) | |||||||||
f9(x,y) | * | * | |||||||
f10(x,y) | * | * | |||||||
f11(x,y) | * | ||||||||
f12(x,y) | * | * | |||||||
f13(x,y) | * | ||||||||
f14(x,y) | |||||||||
f15(x,y) | * | * | * |
Может показаться, что любая функционально полная система должна содержать не менее пяти переключательных функций. Однако ввиду того, что многие переключательные функции удовлетворяют одновременно нескольким требованиям, предъявляемым теоремой о функциональной полноте, количество независимых переключательных функций, входящих в функционально полную систему, всегда меньше пяти[2].
|
В функционально полную систему переключательных функций двух аргументов в соответствии с теоремой о функциональной полноте должны входить такие функции, которые совместно перекрывают клетками без крестиков колонки TL, T0, T1, TM, TS (табл. 1.6). Из переключательных функций, сведенных в табл. 1.6, можно составить различные функционально полные системы. Рассмотрим некоторые из них.
f14 (х, у)=х½ у; эта переключательная функция одна обладает свойством функциональной полноты, так как является нелинейной, немонотонной, несамодвойственной, не сохраняет нуль и единицу. Следовательно, любая переключательная функция может быть представлена через функции f14 (х, у), и поэтому любая сложная функция может быть представлена через эту функцию;
f8 (х, у)=х¯ у; эта функция, так же как и функция f14 (х, у), одна обладает свойством функциональной полноты;
f13 (х, у)=x®y и f0 (х, у)=0 или f11 (х, у)=y® x и f0 (х, у)=0, т. е. импликация и константа нуль;
f6 (х, у)=хÅ у; f1 (х, у)=xÙ y и f15 (х, у)=1, т. е. сумма по модулю два, произведение и константа единица. Функциональная полнота этой системы следует не только из теоремы о функциональной полноте, но и из доказанной ранее теоремы Жегалкина (см. п. 1.3.2).
В связи с тем, что существует большое число различных функционально полных систем переключательных функций, возникает проблема выбора функционально полной системы, представляющей наибольший практический интерес.
Функционально полные системы логических функций.
Из множества функционально полных наборов рассмотрим только те, которые имеют наибольшее практическое значение.
|
Основная функционально полная система логических функций.
Наибольшее распространение получил набор, в состав которого входят три логические функции:
· f10 – инверсия (логическая связь НЕ, логическое отрицание);
· f1 – конъюнкция (логическая связь И, логическое умножение),
· f7 – дизъюнкция (логическая связь ИЛИ, логическое сложение).
Этот набор получил название функционально полной системы логических функций (ОФПС). Из теоремы о функциональной полноте следует, что основная функционально полная система логических функций является избыточной, так как условиям теоремы отвечают наборы функций f10 и f1 или f10 и f7. Свойства этих функций были рассмотрены ранее.
Из определения представления переключательной функции в виде дизъюнктивной или конъюнктивной нормальной формы следует, что эти представления реализуются в основной функционально полной системе логических функций.
|
|
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!