![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Булевых функций
Конструктивный подход к доказательству функциональной полноты некоторой системы булевых функций основан на доказательстве реализуемости функций булева базиса с помощью функций этой системы [1-12]. При этом естественно предполагать, и это действительно так, что булев базис образует функционально полную систему. Система булевых функций S={y1,y2,...,ym} называется функционально полной, если с помощью функций этой системы можно выразить любую сколь угодно сложную булеву функцию с использованием метода суперпозиции, возможно многократно. Под суперпозицией в отношении булевых функций понимается подстановка одних функций в другие вместо их аргумента. Примерами полных систем являются: 1. S1 ={-, Обоснованность утверждения о функциональной полноте этой системы базируется на возможности представления любой булевой функции в нормальной форме, которая является комбинацией операций отрицания, конъюнкции и дизъюнкции, применительно к аргументу этой функции. Система S1 ={-, Получаемые при этом системы S2 ={-, Недостающие операции (Ú в системе S2 и Функциональная полнота системы булевых функций называется минимальной, если удаление из нее какой-либо функции приводит к нарушению свойства функциональной полноты. 2. Системы из одной функции S4=¯(стрелка Пирса), S5=|(штрих Шеффера), которые принято называть универсальным базисом. 3. Базис Жегалкина S6= { Понятие функциональной полноты системы булевых функций связано с аналогичным понятием для системы логических элементов. Эта связь заключается в следующем. Если каждой функции из некоторой функционально полной системы сопоставить логический элемент, реализующий эту функцию, то система логических элементов соответствующая некоторой функционально полной системе булевых функций естественным образом оказывается тоже функционально полной . При решении задачи синтеза комбинационных схем с использованием функционально полной системы логических элементов можно построить комбинационную схему, реализующую любую заданную, сколь угодно сложную булеву функцию. Доказательство функциональной полноты некоторой системы булевых функций можно осуществлять одним из двух способов: для того, чтобы система булевых функций была функционально полной необходимо и достаточно чтобы она содержала хотя бы одну функцию НЕ: а) cохраняющую константу ноль; б) cохраняющую константу единица; в) линейную функцию; г) монотонную функцию; д) самодвойственную функцию.
|