Что такое самодвойственная функция

Что такое самодвойственная функция

Определение. Булева функция f(x₁, …, x_n) самодвойственна (принадлежит классу S), если она равна двойственной себе функции, то есть

Примеры. Мажоритарная функция самодвойственна:

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

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

Достаточное условие несамодвойственности булевой функции. Если число единиц в столбце значений функции не совпадает с числом нулей, то функция не является самодвойственной.

Примеры. Рассмотрим три булевы функции.

Для функции f(x,y,z) выполняется достаточное условие несамодвойственности. Для остальных оно не выполняется, при этом функция g(x,y,z) несамодвойственна, так как на первом и последнем наборах принимает одинаковые значения, а функция h(x,y,z) самодвойственна. •

Пример. Из всех 16 булевых функций двух аргументов x₁, x₂ 4 функции (2 2 2 –1 ) принадлежат классу S: тождественные функции x₁ и x₂ и их инверсии x ₁ и x ₂. •

Теорема о замкнутости класса S. Множество всех самодвойственных булевых функций является замкнутым классом.

Доказательство. Рассмотрим суперпозицию любых булевых функций из S, то есть функцию

и покажем, что она самодвойственна. Пользуясь принципом двойственности, получим функцию, двойственную f(x₁, …, x_n).

[ учтем, что каждая из функций, образующих суперпозицию, самодвойственна ]

Итак, мы показали, что f * (x₁, …, x_n)=f(x₁, …, x_n), значит, f(x₁, …, x_n) самодвойственна, и класс S замкнут. •

Лемма о несамодвойственной булевой функции. Если булева функция несамодвойственна, то из нее подстановкой вместо аргументов переменной x и ее инверсии x можно получить либо константу 0, либо константу 1.

Доказательство. Рассмотрим несамодвойственную булеву функцию f(x₁, …, x_n). Для нее существует такой набор a₁… a_n, что

Заменим каждый аргумент x_i функции f(x₁, …, x_n на x a _i, (подстановка переменной x и ее инверсии x допустима по условию теоремы). В результате получим функцию одного аргумента

Но набор a₁… a_n выбран так, что правые части равны, следовательно, g(0)=g(1), и константа получена. •

Примеры. Рассмотрим функцию f(y,z) = y ↓ z. Она несамодвойственна, так как на противоположных наборах 01 и 10 принимает одно и то же значение 0. В качестве набора a₁a₂ возьмем набор 01. Положим y=x 0 = x и z=x 1 =x, получим

Аналогично, рассмотрев функцию h(y,z)=y/z, которая на тех же противоположных наборах принимает значение 1, получим:

Источник

САМОДВОЙСТВЕННЫЕ ФУНКЦИИ

СПЕЦИАЛЬНЫЕ КЛАССЫ БУЛЕВСКИХ

ФУНКЦИЙ

ОПРЕДЕЛЕНИЕ

Множество функций B называется замкнутым классом, если [B] = B.

Например, множество <x, > является замкнутым классом. Рассмотрим пять специальных классов булевских функций, свойства которых будут использованы при нахождении простых необходимых и достаточных условий полноты произвольных систем функций в P₂.

ФУНКЦИИ, СОХРАНЯЮЩИЕ НОЛЬ

Обозначим как Т₀ множество всех таких булевских функций, которые на нулевом наборе значений переменных принимают значение 0.

О таких функциях говорят, что они сохраняют 0, т.е. множество б.ф., сохраняющих ноль, это:

Т₀ = <f(x₁. x _n) ½ f(0. 0) = 0>.

Сформулируем простейшие свойства класса T₀.

1. Класс T₀ является замкнутым классом функций.

Проведем обоснование этого свойства в соответствии с определением понятия формулы над классом функций.

ФУНКЦИИ, СОХРАНЯЮЩИЕ ЕДИНИЦУ

Класс T₁ является замкнутым и содержит различных функций n переменных. Последние свойства могут быть обоснованы аналогично тому, как это делалось для класса T₁.

САМОДВОЙСТВЕННЫЕ ФУНКЦИИ

Двоичные наборы и называются противоположными наборами.

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

Тогда, пусть и — произвольные противоположные наборы. Для определенности будем считать, что s₁ =0.

ОПРЕДЕЛЕНИЕ

Двойственная функция к заданной функции f обозначается как f*.

Нетрудно проверить, что , , .

Кроме того, легко убедиться в справедливости следующего свойства: функция, двойственная к двойственной функции, совпадает с исходной функцией, т.е. справедливо равенство: f** = f.

ОПРЕДЕЛЕНИЕ

Функция f называется самодвойственной, если f = f*.

То есть всякая самодвойственная функция на любых двух противоположных наборах значений переменных принимает противоположные значения. Примерами самодвойственных функций являются тождественная функция f(x) = x и отрицание f(x) = .

Множество всех самодвойственных функций обозначается как S.

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

1. Выпишем столбец значений f в обратном порядке.

2. В полученном столбце выполним замену всякого значения в нем на противоположное значение.

Если функция f задана формулой, то для получения формульного представления функции f* можно воспользоваться следующей теоремой.

ТЕОРЕМА 4.7 (О формуле для двойственной функции)

Доказательство

Докажем теорему индукцией по глубине формулы U.

1. Базис индукции.Покажем, что если f = , то представляется формулой . Запишем цепочку равенств:

=

=

= .

2. Индуктивное предположение. Предположим, что доказываемое в свойство выполняется для всех формул, глубина которых не превосходит n.

Тогда аналогично доказательству базиса индукции можно показать, что = .

Поскольку всякая функция представляется формулой , то представляется формулой , т.е. формулой U( . ).

Источник

Раздел 1. Математическая логика

Тема 1. Логика высказываний

Тема 2. Булевы функции

В этой теме рассматриваются всюду определенные функции, заданные на множестве B=<0,1>. Такие функции называются булевыми. Основная цель темы – доказать критерий полноты класса функций – теорему Поста.

§1. Замкнутость и полнота

§2. Самодвойственные функции

Этот и два следующих параграфа посвящены рассмотрению трех конкретных классов функций: самодвойственных, монотонных и линейных.

Определение. Функция g(x₁,…,x_n) называется двойственной k f(x₁,…,x_n), если выполняется равенство

Например, x × y двойственна x Ú y, и наоборот. Это следует из равенств x × y= n ( n (x) Ú n (y) и x Ú y= n ( n (x) × n (y)), которые мы уже приводили. Функция x ® y двойственна функции n (x)&y, поскольку n ( n (x) ® n (y)= n [ n ( n (x)) Ú n (y)]= n (x Ú n (y)) = n (x)&y. Отметим, что первое равенство выполняется на основании закона 20, второе 19 и третье 18 и 19.

Определение. Функция f(x₁,…,x_n) называется самодвойственной, если выполняется равенство

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

Приведем примеры. Легко видеть, что самодвойственными функциями являются тождественная функция и отрицание: n [ e ( n (x))]= n [ n (x)]=x= e (x), n [ n ( n (x))]= n (x). В то же время, произведение x × y самодвойственной не является, поскольку двойственно дизъюнкции x Ú y и x × y ¹ x Ú y. Можно показать, что никакая функция от двух переменных, существенно зависящая от каждого аргумента, самодвойственной не является. В качестве еще одного примера самодвойственной функции приведем функцию

Последнее равенство выполняется на основании закона поглощения.

Отметим, что равенство (1) из определения самодвойственности равносильно равенству n (f(x₁,…,x_n))=f( n (x₁),…, n (x_n)). (2)

Класс всех самодвойственных функций обозначим буквой S. Убедимся в том, что S – замкнутый класс. Как уже отмечалось, S содержит e (x). Пусть f(x₁,…,x_n) Î S и y₁,…,y_n – новый набор переменных. Тогда поскольку равенство f(x₁,…,x_n)= n [f( n (x₁),…, n (x_n)] выполняется для всех значений переменных x₁,…,x_n, то n [f( n (y₁),…, n (y_n)]=f(y₁,…,y_n). Следовательно, f(y₁,…,y_n) Î S и S – замкнут относительно переименования аргументов. Возьмем теперь функции f(x₁,…,x_k), g₁(x₁,…,x_n),…, g_k(x₁,…,x_n) из S. Поскольку эти функции принадлежат S, то, используя равенство (2), получаем, что

В силу равенства (2), h(x₁,…,x_n) – самодвойственная функция. Следовательно, класс S замкнут относительно суперпозиции.

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

Лемма. Пусть f(x₁,…,x_n) – несамодвойственная функция. Тогда замыкание класса K=1,…,x_n), n (x)> содержит константы q (x) и i (x).

Доказательство. Поскольку f(x₁,…,x_n) – несамодвойственная функция, то существуют a₁,…,a_n Î B такие, что

Множество B содержит только два элемента. Поэтому из этого неравенства следует равенство

Для удобства обозначений предположим, что a₁,…,a_k=0, a_k+1,…, a_n=1. Тогда последнее равенство можно записать так:

где точка с запятой отделяет k-ый аргумент от (k+1)-го.

Заметим, что g(x) принадлежит [K]. Имеем равенства

Следовательно, g(x) – одна из констант, принадлежащая [K]. Поскольку K содержит отрицание, то и другая константа принадлежит [K].

В заключение параграфа рассмотрим пример решения задачи на распознавание самодвойственности: определить, будет ли функция f(x₁,x₂)=x₂ × (x₂ ® x₁) самодвойственной? (Впрочем, мы уже знаем, что f(x₁,x₂) несамодвойственна, но надо это доказать). Для получения ответа на вопрос составим таблицу, задающую функции f(x₁,x₂) и n (f( n (x₁), n (x₂)). (см. таблицу 2.4)

Мы видим, что f(x₁,x₂) ¹ n (f( n (x₁), n (x₂)), например при x₁=0, x₂=1. Следовательно, функция f(x₁,x₂) самодвойственной не является. (Для того, чтобы сделать заключение о несамодвойственности, можно было, конечно, прервать составление таблицы на второй строке.

§3. Монотонные функции

§4. Линейные функции

§5. Критерий полноты

Задачи

Ответы, указания и решения

Тема 3. Логика предикатов

Тема 4. Метод резолюций

Раздел 2. Теория графов

Источник

Самодвойственность. Класс S

Функции f (`х n ) и g (`х n ) двойственны (f = g * ), если они принимают противоположные значения на обратных наборах значений переменных f(`х n ) =`g (`х n* ).

Определение. Функция f (`х n ) называется самодвойственной, если f = f *

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

Пример. Проверить самодвойственность функций:

Решение.Проверку производим по векторам истинности с использованием описанного выше их свойства для самодвойственных функций.

а) Делим вектор истинности функции Øх на две половины: (1÷ 0). Поскольку в первой половине один символ (1), то симметричное отражение дает его же. Инвертируя его, получим символ 0, который совпадает со второй половиной вектора. Следовательно, отрицание — самодвойственная функция.

б) Вектор истинности функции`х ¯ у делим на две половины: (00÷ 10). Симметричное отражение первой половины относительно разделяющей черты не меняет ее. После инвертирования получим последовательность (11), которая не совпадает со второй половиной вектора истинности (10). Поэтому`х ¯ у — не самодвойственная функция.

в) Делим вектор истинности на две половины (0010÷1011). Симметрично отразим первую половину относительно разделяющей черты — (0100) и инвертируем ее — (1011). Полученная последовательность совпала со второй половиной вектора истинности, следовательно, рассмотренная функция — самодвойственная.

Ответ: функции а) Øх и в) (00101011) — самодвойственны, функция б)`х¯у — нет.

Рассмотрим самодвойственность элементарных функций с учетом числа переменных n в них.

n=0. Константы 0 и 1 не являются самодвойственными.

n=2. Ни одна из элементарных функций не входит в S. Все двухместные самодвойственные функции f (х,у)имеют одну фиктивную переменную и сводятся к функциям х, у, Øх, Øу.

Следовательно, для получения самодвойственных функций, имеющих две существенных переменных, необходимо рассматривать n ³ 3.

Источник

Самодвойственная функция

Самодвойственных функций является булевой функции, двойственный к себе. двойной функцией для f <\свойства стиль отображения значение f>, является функция f ∗ = f <\свойства стиль отображения значение Ф^<*>=<\оверлайн >>. следовательно, функция f <\свойства стиль отображения значение f>это самодвойственных если f = f <\свойства стиль отображения значение <\оверлайн >=f> (<ф>>=ф>) другими словами. собственн-двойная функция на противоположных наборах значений аргументов принимает противоположные значения.
Множество самодвойственных функций обозначается S. комплект S является замкнутым классом. действительно, если функции f x 1., x n (х), f 1 x 1 (Ф 1 х 1)., x n (х)., f k x 1 (Ф К Х 1)., x n (х) <\свойства стиль отображения значение fx_<1>,\лдоц,x_ не<н>,f_<1>x_ не<1>,\лдоц,x_ не<н>,\лдоц,f_<к>x_ не<1>,\лдоц,x_ не<н>> собственн-двойная функция g x 1., x n = f 1 x 1 (х п = ф 1 х 1)., x n (х)., f k x 1 (Ф К Х 1)., x Н) <\свойства стиль отображения значение gx_<1>,\лдоц x_ не<н>=ff_<1>x_ не<1>,\лдоц x_ не<н>,\лдоц,f_<к>x_ не<1>,\лдоц x_ не<н>)> тоже самодвойственных: g x 1., x n = f (н =) f 1 x (Ф 1) 1., x n., f k x (Ф К) 1., x Н) = f 1 x 1., x n (х)., f k x 1., x Н) = f 1 x 1 (ф 1 х 1)., x n (х)., f k x 1 (Ф К Х 1)., x Н) = g x 1., x n (х) <\свойства стиль отображения значение <\оверлайн <г>><\оверлайн <х>>_<1>,\лдоц<\оверлайн <х>>_<н>=<\оверлайн <Ф>>f_<1><\оверлайн <х>>_<1>,\лдоц<\оверлайн <х>>_<Н>,\лдоц,f_<к><\оверлайн <х>>_<1>,\лдоц<\оверлайн <х>>_<н>)=<\оверлайн <Ф>><\оверлайн <Ф>>_<1>x_ не<1>,\лдоц x_ не<н>,\лдоц<\оверлайн >_x_<1>,\ldots,x_)=ff_<1>x_<1>,\ldots,x_,\ldots,f_x_<1>,\ldots,x_)=gx_<1>,\ldots,x_>. S класс предпол.
Примеры самодвойственных функций: x, x, x ∧ y ∨ x ∧ z ∨ y ∧ z <\свойства стиль отображения значение х,<\оверлайн <х>>,х\клин г\ви\х клин з\ви г\клин z>. В свою очередь, конъюнкции, дизъюнкции и константы не самодвойственных.

Источник