Cтраница 1
Система булевых вектор-функций полна в Р % тогда и только тогда, когда она целиком не содержится ни в одном из предполных в Р % классов. [1]
В главе III изучаются замкнутые классы булевых вектор-функций - новое перспективное направление в теории булевых функций. Основное содержание главы III концентрируется вокруг проблемы полноты, которая, в отличие от проблемы полноты для булевых функций, решается альтернативным образом на основе теории Галуа для прямых произведений алгебр Поста. [2]
Теоремы, сформулированные и доказанные выше, выполнили основную теоретическую задачу - показали возможность таких методов синтеза, когда при реализации любой булевой вектор-функции число активных элементов может быть меньше общего числа элементов схемы. Однако эти методы синтеза ориентированы на выяснение общих закономерностей синтеза и поэтому, как правило, неэффективны, когда необходимо реализовать конкретную булеву функцию схемой, имеющей небольшое число активных элементов. В то же время такая задача вызывает заметный интерес в практике реального проектирования, и вот почему. [3]
В, е и по всем схемам в базисе В, е, реализующим вектор-функцию fn m, а максимум - по всем булевым вектор-функциям fn m - ( Активность вычисления будем называть удельной активностью, если заданы функции удельной активности элемента. [4]
Из традиционно исследуемых задач остановимся на следующих: задан базис из ненадежных ( в смысле определений, данных выше) и идеальных элементов. Необходимо для любой заданной булевой вектор-функции дать метод синтеза схем в этом базисе, надежно реализующих заданную вектор-функцию. При этом задаются ограничения на общее число элементов в схеме и отдельно на число идеальных элементов. Что точно означает надежная реализация, будет оговорено особо. [5]
Изложено новое компактное доказательство конечной порождаемости всех классов Поста и дано описание решетки классов Поста. Рассмотрено предикатное задание классов Поста и приведено определение классов Поста в терминах некоторых стандартных предикатов. Изложены основы теории Галуа для алгебры булевых функций. Введены булевы вектор-функции, с использованием соответствий Галуа решена проблема полноты для класса всех булевых вектор-функций. Рассмотрены некоторые сильные операторы замыкания, которые приводят к конечным решеткам замкнутых классов. [6]
Все это поставило вопрос о современном компактном изложении результатов Поста, которое было бы доступно для первоначального знакомства с предметом и, с другой стороны, представляло бы основу для дальнейших исследований в этом направлении. Кроме того, на фоне нового изложения результатов Поста возникла потребность дать введение в круг идей и результатов, которые связаны с замкнутыми классами булевых функций, но пока мало представлены в литературе. Имеется в виду прежде всего предикатное задание классов Поста, теория Галуа для алгебр Поста, замкнутые классы булевых вектор-функций, различные обобщения оператора замыкания. [7]