I §2. Предполные классы

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

1) Класс I §2. Предполные классы - student2.ru- класс функций, сохраняющих 0, т.е. функций, для которых I §2. Предполные классы - student2.ru . Замкнутость класса I §2. Предполные классы - student2.ru очевидна: если в

функцию I §2. Предполные классы - student2.ru вместо некоторых переменных

подставить функции, принадлежащие I §2. Предполные классы - student2.ru , то на нулевом наборе

аргументов все они имеют значение 0, и для внешней функции I §2. Предполные классы - student2.ru набор ее переменных будет также нулевым, откуда Z = 0.

2) Класс I §2. Предполные классы - student2.ru- класс функций, сохраняющих 1, те функций, для

которых I §2. Предполные классы - student2.ru Замкнутость I §2. Предполные классы - student2.ru устанавливается аналогично

предыдущему.

Примерами функций, принадлежащих классам I §2. Предполные классы - student2.ru , служат

функции I §2. Предполные классы - student2.ru , отрицание I §2. Предполные классы - student2.ru не принадлежит ни I §2. Предполные классы - student2.ru

функция I §2. Предполные классы - student2.ru принадлежит I §2. Предполные классы - student2.ru , но не принадлежит I §2. Предполные классы - student2.ru импликация

I §2. Предполные классы - student2.ru напротив, не принадлежит I §2. Предполные классы - student2.ru , но принадлежит I §2. Предполные классы - student2.ru

3) Для определения следующего класса введем понятие двойственности. Двойственная функциядля функции

I §2. Предполные классы - student2.ru - функция I §2. Предполные классы - student2.ru . Если на

наборе I §2. Предполные классы - student2.ru функция I §2. Предполные классы - student2.ru принимает значение I §2. Предполные классы - student2.ru , то

двойственная ей функция I §2. Предполные классы - student2.ru на противоположном

ч

наборе I §2. Предполные классы - student2.ru принимает противоположное значение I §2. Предполные классы - student2.ru

Упражнение.Проверьте, например, что двойственной функцией к

конъюнкции I §2. Предполные классы - student2.ru является дизъюнкция I §2. Предполные классы - student2.ru , константа 1

двойственна константе 0.

Для булевых функций справедлив принцип двойственности -

если в формуле F , представляющей функцию I §2. Предполные классы - student2.ru , все знаки функций заменить соответственно на знаки двойственных функций, то полученная формула I §2. Предполные классы - student2.ru будет представлять функцию I §2. Предполные классы - student2.ru , двойственную I §2. Предполные классы - student2.ru

Класс S самодвойственных функций- то есть функций таких, что I §2. Предполные классы - student2.ru . Из определения следует, что

двоичный набор значений самодвойственной функции антисимметричен относительно своей середины. Таким способом удобно проверять по таблице самодвойственность функции. Например, можно убедиться, что

одноместные функции I §2. Предполные классы - student2.ru - самодвойственные, а среди функций

двух переменных самодвойственными являются только функции с одной

несущественной переменной. Функция большинства I §2. Предполные классы - student2.ru (см

§1 гл.З) является самодвойственной

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

внешней функции также противоположны. Пусть I §2. Предполные классы - student2.ru

I §2. Предполные классы - student2.ru

I §2. Предполные классы - student2.ru i - суперпозиция этих самодвойственных функций. Тогда I §2. Предполные классы - student2.ru [поскольку

I §2. Предполные классы - student2.ru

I §2. Предполные классы - student2.ru

!' 4) В начале §1 гл.4 мы убедились в возможности представления любой функции многочленом Жегалкина.

Подмножеством множества многочленов является класс L 'линейных функций- функции вида I §2. Предполные классы - student2.ru . Здесь

I §2. Предполные классы - student2.ru - переменные, I §2. Предполные классы - student2.ru - булева константа (0 или 1).

Очевидно, что класс линейных функций - замкнутый: подстановка сумм вместо переменных представляет собой сумму; при этом некоторые пары слагаемых могут взаимно сократиться ввиду эквивалентности

I §2. Предполные классы - student2.ru

Пример:Пусть I §2. Предполные классы - student2.ru

I §2. Предполные классы - student2.ru Тогда суперпозиция I §2. Предполные классы - student2.ru

функцию I §2. Предполные классы - student2.ru подставляем функцию I §2. Предполные классы - student2.ru вместо X и функцию I §2. Предполные классы - student2.ru вместо Y ] представляет собой линейную функцию:

I §2. Предполные классы - student2.ru

5) Введем отношение частичного порядка для булевых векторов:

I §2. Предполные классы - student2.ru для

I §2. Предполные классы - student2.ru Заметим, что для булевых переменных строгое неравенство I §2. Предполные классы - student2.ru означает, что I §2. Предполные классы - student2.ru поскольку других возможностей нет.

Равенство I §2. Предполные классы - student2.ru добавляет варианты I §2. Предполные классы - student2.ru . Поэтому

аргументов все они имеют значение 0, и для внешней функции I §2. Предполные классы - student2.ru набор ее переменных будет также нулевым, откуда Z = 0.

2) Класс I §2. Предполные классы - student2.ru- класс функций, сохраняющих 1, те функций, для

которых I §2. Предполные классы - student2.ru Замкнутость I §2. Предполные классы - student2.ru устанавливается аналогично

предыдущему.

Примерами функций, принадлежащих классам I §2. Предполные классы - student2.ru , служат

функции I §2. Предполные классы - student2.ru , отрицание I §2. Предполные классы - student2.ru не принадлежит ни I §2. Предполные классы - student2.ru

функция I §2. Предполные классы - student2.ru принадлежит I §2. Предполные классы - student2.ru , но не принадлежит I §2. Предполные классы - student2.ru импликация

I §2. Предполные классы - student2.ru напротив, не принадлежит I §2. Предполные классы - student2.ru , но принадлежит I §2. Предполные классы - student2.ru

3) Для определения следующего класса введем понятие двойственности. Двойственная функциядля функции

I §2. Предполные классы - student2.ru - функция I §2. Предполные классы - student2.ru . Если на

наборе I §2. Предполные классы - student2.ru функция I §2. Предполные классы - student2.ru принимает значение I §2. Предполные классы - student2.ru , то

двойственная ей функция I §2. Предполные классы - student2.ru на противоположном

ч

наборе I §2. Предполные классы - student2.ru принимает противоположное значение I §2. Предполные классы - student2.ru

Упражнение.Проверьте, например, что двойственной функцией к

конъюнкции I §2. Предполные классы - student2.ru является дизъюнкция I §2. Предполные классы - student2.ru , константа 1

двойственна константе 0.

Для булевых функций справедлив принцип двойственности -

если в формуле F , представляющей функцию I §2. Предполные классы - student2.ru , все знаки функций заменить соответственно на знаки двойственных функций, то полученная формула I §2. Предполные классы - student2.ru будет представлять функцию I §2. Предполные классы - student2.ru , двойственную I §2. Предполные классы - student2.ru

Класс S самодвойственных функций- то есть функций таких, что I §2. Предполные классы - student2.ru . Из определения следует, что

двоичный набор значений самодвойственной функции антисимметричен относительно своей середины. Таким способом удобно проверять по таблице самодвойственность функции. Например, можно убедиться, что

одноместные функции I §2. Предполные классы - student2.ru - самодвойственные, а среди функций

двух переменных самодвойственными являются только функции с одной

несущественной переменной. Функция большинства I §2. Предполные классы - student2.ru (см

§1 гл.З) является самодвойственной

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

внешней функции также противоположны. Пусть I §2. Предполные классы - student2.ru

I §2. Предполные классы - student2.ru

I §2. Предполные классы - student2.ru i - суперпозиция этих самодвойственных функций. Тогда I §2. Предполные классы - student2.ru [поскольку

I §2. Предполные классы - student2.ru

I §2. Предполные классы - student2.ru

!' 4) В начале §1 гл.4 мы убедились в возможности представления любой функции многочленом Жегалкина.

Подмножеством множества многочленов является класс L 'линейных функций- функции вида I §2. Предполные классы - student2.ru . Здесь

I §2. Предполные классы - student2.ru - переменные, I §2. Предполные классы - student2.ru - булева константа (0 или 1).

Очевидно, что класс линейных функций - замкнутый: подстановка сумм вместо переменных представляет собой сумму; при этом некоторые пары слагаемых могут взаимно сократиться ввиду эквивалентности

I §2. Предполные классы - student2.ru

Пример:Пусть I §2. Предполные классы - student2.ru

I §2. Предполные классы - student2.ru Тогда суперпозиция I §2. Предполные классы - student2.ru

функцию I §2. Предполные классы - student2.ru подставляем функцию I §2. Предполные классы - student2.ru вместо X и функцию I §2. Предполные классы - student2.ru вместо Y ] представляет собой линейную функцию:

I §2. Предполные классы - student2.ru

5) Введем отношение частичного порядка для булевых векторов:

I §2. Предполные классы - student2.ru для

I §2. Предполные классы - student2.ru Заметим, что для булевых переменных строгое неравенство I §2. Предполные классы - student2.ru означает, что I §2. Предполные классы - student2.ru поскольку других возможностей нет.

Равенство I §2. Предполные классы - student2.ru добавляет варианты I §2. Предполные классы - student2.ru . Поэтому

неравенству I §2. Предполные классы - student2.ru удовлетворяют 3 пары I §2. Предполные классы - student2.ru и не

удовлетворяет только пара (1, 0) Можно заметить, что I §2. Предполные классы - student2.ru эквивалентно I §2. Предполные классы - student2.ru

Класс М монотонных функций- это класс функций таких, что если I §2. Предполные классы - student2.ru , то I §2. Предполные классы - student2.ru , т е. функция на большем наборе

принимает не меньшее значение.

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

Покажем, что класс монотонных функций - замкнутый Пусть функции

что I §2. Предполные классы - student2.ru и требовалось доказать.

Отметим, что для каждой упорядоченной пары (А, В) различных

классов из пяти рассмотренных предполных I §2. Предполные классы - student2.ru существует

функция, входящая в А и не входящая в В . Таблица 8 содержит такие примеры каждая функция таблицы входит в класс, соответствующий строке и не входит в класс, соответствующий столбцу Например, входит

в Л/ , но не входит в S функция-константа 0; входит в S, но не входит в L функция I §2. Предполные классы - student2.ru Из этого замечания можно сделать важный

вывод никакой из пяти классов I §2. Предполные классы - student2.ru не входит целиком ни в

какой из остальных четырех

I §2. Предполные классы - student2.ru

Наши рекомендации