Тема 5. Многозначные функции

Теорема Поста

Ответ на вопрос о полноте произвольной системы F булевых функций дает теорема Поста. Для ее формулировки вводятся определения классов Поста.

1) P ₀ – класс булевых функций, сохраняющих 0, т.е. функций ƒ (x ₁, x ₂,…, x _n), для которых ƒ (0,….0) = 0.

2) P ₁ – класс булевых функций, сохраняющих единицу, т.е. ƒ (x ₁, x ₂,…, x _n), для которых ƒ (1,…,1) = 1

3) S – класс самодвойственных функций

Функция ƒ⁺(x ₁, x ₂,…, x _n) называется двойственной по отношению к функции ƒ(x ₁, x ₂,…, x _n), если, т.е. функция, получающаяся из исходной путем замены значения всех переменных и значений функций на противоположные. В таблице истинности заменяется 0 на 1 и 1 на 0.

Например:

(x Ú y)⁺ = x Ù y; (x Ù y)⁺ = x; (x ̅)⁺ = x ̅.

Функция ƒ (x ₁, x ₂,…, x _n) называется самодвойственной, если ƒ⁺ (x ₁, x ₂,…, x _n) = ƒ (x ₁, x ₂,…, x _n).

4) М – класс монотонных функций.

Булева функция ƒ (x ₁, x ₂,…, x_n) называется монотонной, если для любых двух наборов (α ₁, α ₂,…, α _n) и (β ₁, β ₂,…, β_n) у которых α_i ≤ β _i для всех i = 1,…, n следует, что ƒ(α ₁, α ₂,…, α_n) ≤ ƒ (β ₁, β ₂,…, β_n).

5) L – класс линейных функций, т.е. линейных полиномов Жегалкина.

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

Теорема Поста. Для того, чтобы система функций F была полной необходимо и достаточно, чтобы она полностью не содержалась ни в одном из пяти замкнутых классов P ₀, P ₁, S, M, L.

Пример ƒ(x, y) = x | y.

Определим, к каким классам Поста относится x | y. Т.к. ƒ(0,0) = 1, а ƒ(1,1) = 0, то и. Т.к., то. Т.к. ƒ(0,0)> ƒ(1,1), то. Полином Жегалкина для данной функции имеет вид 1Å xy, т.е. эта функция нелинейна, следовательно.

Таким образом, имеем:

ФУНКЦИЯ	КЛАССЫ
P 0	P 1	S	M	L
x | y	Нет	Нет	Нет	Нет	Нет

В силу теоремы Поста функция x | y образует полную систему, т.е. с помощью штриха Шеффера можно получить любую булеву функцию.

Система булевых функций называется базисом, если она полна, а удаление любой функции из этой системы делают ее неполной.

Каждый базис содержит не более четырех булевых функций.

Примеры:

Следующие системы булевых функций являются базисами:

1) {Ù, -}; {Ú, -}; {→, -}; {|}; {↓}; {↔, Ú, 0}; {Å, Ù, ↔}.

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

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

5.1. Функции и формулы k -значной логики

Функция, аргументы и значения, которой определены на множестве истинностных значений, называется функцией k -значной логики.

Каждую функцию k -значной логики от n – аргументов можно задать в виде таблицы содержащей строк.

0 0 0
0 0 1
................	..........
0 0 k -1
0 1 0
................	...........
0 k -1 k -1

Множество всех функций k -значной логики обозначается (). Заметим, что. В частности число функций от двух переменных в равно =19683, т.е. это множество практически не обозримо. Поэтому в так же как и в, используется задание функций с помощью формул. В качестве «элементарных» в k -значной логике рассматриваются следующие функции:

1. `.

Эта функция представляет собой отрицание в смысле «циклического сдвига значений».

2. – это обобщение отрицания в смысле «зеркального отображения значений». Оно носит название отрицание Лукашевича.

3..

Эта функция также является обобщением некоторых свойств отрицания.

4..

Это характеристическая функция значения i, которая также обобщает отрицание.

5. – это обобщение конъюнкции.

6. – это есть второе обобщение конъюнкции.

7. – обобщение дизъюнкции.

8. – второе обобщение дизъюнкции.

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

Любая функция из может быть представлена в виде:

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

Данное представление является аналогом СДНФ.

5.2. Полнота и замкнутость функций k -значной логики

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

Примерами полных систем является:

1.B=.

2.B=.

3.B=.

4.B=,где.

Функция называется фуннцией Вебба представляет собой аналог функции Шеффера.

Пусть M – произвольное подмножество функции из. З амыканием M называется множество [M] всех функций из, представленных в виде формул через функции множества M`

Класс M называется (функционально) замкнутым, если замыкание [M]=M.

Таким образом, в терминах замыкания можно определить полноту системы функций, а именно B является полной системой если замыкание [B]=.

Справедлива теорема о функциональной полноте - теорема Кузнецова А.В.:

Можно построить систему замкнутых классов в - M₁, M₂,…,M_s, каждый из которых не содержит целиком ни одного из остальных классов и такую, что подсистема функций из полна тогда и только тогда, когда она целиком не содержится ни в одном из классов M₁, M₂,…,M_s. Это аналог теоремы Поста.

Теорема Кузнецова доказывает, что возможно выразить, условие полноты системы B в терминах принадлежности ее к специальным классам M₁, M₂,…,M_s, однако практическое построение классов даже при небольших k связано с трудоемкими вычислениями. Поэтому возникает вопрос о поиске других более эффективных критериев полноты. Эта цель достигается за счет введения ограничений, т.е. за счет знания дополнительной информации о системе B.

Существенными называются функции из, если они существенно зависят не менее чем от двух переменных.

Теорема Яблонского

Пусть система B функций из, где k ³ 3, содержит все функции одной переменной, принимающие не более k -1 значений. Тогда для полноты системы B необходимо и достаточно, чтобы B содержало существенную функцию, принимающую все k значений.

Следствие (критерий Слупецкого):

Пусть система B функций из, где к ³ 3, содержит все функции одной переменной. Тогда для полноты системы B необходимо и достаточно, чтобы B содержало существенную функцию, принимающую все k значений.

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

Известно, что функции из B могут быть получены из конкретных систем функций одной переменной.

Теорема 1 (Пикара).

Все функции одной переменной из могут быть порождены тремя функциями:

1),

2),

3).

Теорема 2

Все функции одной переменной из могут быть порождены k функциями

и функцией.

Теорема 3 (Мартина).

Функция из при к ³ 3 является функция Шеффера, тогда и только тогда, когда порождает все функции одной переменной принимающие не более k -1 значений.

5.3. Особенности k – значной логики

Во многом k – значная логика подобна двухзначной. В ней сохраняются многие результаты, имеющие место в двузначной логике. Однако ряд результатов, верных для функций алгебры логики, т.е. при k =2, уже не переносятся на случай, когда k ³3.

Например, как показал Пост, каждый замкнутый класс в P ₂ имеет конечный базис и поэтому, число замкнутых классов в P ₂ счетно. С другой стороны для k ³ 3 в:

а) существует замкнутый класс не имеющий базиса;

б) существует замкнутый класс имеющий счетный базис;

в) имеется бесчисленные множества различных замкнутых классов.

Дата добавления: 2014-01-11