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

Раздел 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. Теория графов

Источник

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

Определение. Булева функция 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, получим:

Источник

Полные системы функций. Теорема Поста о полной системе функций

Содержание

Полные системы функций [ править ]

Американский математик Эмиль Пост сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:

Замкнутые классы булевых функций [ править ]

Количество линейных функций от [math]n[/math] переменных равно [math]

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

Формулировка и доказательство критерия Поста [ править ]

Необходимость.

Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора [math]K[/math] входили в один из перечисленных классов, то и все суперпозиции, а, значит, и замыкание набора входило бы в этот класс, и набор [math]K[/math] не мог бы быть полным.

Достаточность.

Докажем, что если набор [math]K[/math] не содержится полностью ни в одном из данных классов, то он является полным.

Таким образом, возможны четыре варианта:

Рассмотрим несколько вариантов:

Значит, полученные функции образуют полную систему, поскольку с их помощью можно выразить любую булеву функцию. Из этого следует, что K — полная система функций, что и требовалось доказать.[math]\triangleleft[/math]

Примеры [ править ]

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

Широко известны такие полные системы булевых функций:

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

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

Теорема о максимальном числе функций в базисе: максимально возможное число булевых функций в базисе — четыре.

Иногда говорят о системе функций, полной в некотором замкнутом классе, и, соответственно, о базисе этого класса. Например, систему [math]\left\<\oplus,1\right\>[/math] можно назвать базисом класса линейных функций.

Источник

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

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

ФУНКЦИЙ

ОПРЕДЕЛЕНИЕ

Множество функций 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( . ).

Источник