ИССЛЕДОВАНИЕ СТРУКТУРЫ ПЕРЕСЕЧЕНИЙ ПРЕДПОЛНЫХ ЗАМКНУТЫХ КЛАССОВ БУЛЕВЫХ ФУНКЦИЙ Левоневский Д.К.,Евневич Е.Л.

Санкт-Петербургский институт информатики и автоматизации РАН


Номер: 12-1
Год: 2015
Страницы: 23-28
Журнал: Актуальные проблемы гуманитарных и естественных наук

Ключевые слова

математическая логика, классы Поста, классы замкнутости, булевы функции, обучение, mathematical logics, Post classes, closed classes, boolean functions, education

Просмотр статьи

⛔️ (обновите страницу, если статья не отобразилась)

Аннотация к статье

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

Текст научной статьи

Введение. Математическая логика является одним из важнейших разделов математики. Тесная связь математической логики с информатикой и вычислительной техникой способствует поддержанию актуальности её задач при построении информационного общества. В данной работе будет рассмотрена одна из таких задач и показано применение её результатов в образовательной практике в соответствии с подходом продуктивного обучения [1, 10]. Материалы и методы. В математической логике замкнутым классом называется множество функций, замыкание которого относительно операции суперпозиции совпадает с ним самим [2, 18]. Американский математик Эмиль Пост определил набор классов, обладающих свойствами [3]: • ни один класс не содержится в объединении всех остальных; • любой замкнутый класс, кроме всего множества булевых функций, содержится в одном из классов Поста; • множество функций, не принадлежащее целиком ни одному из классов Поста, является полным, т. е. позволяющим выразить любую булеву функцию (критерий Поста) [4, 16]. Существует пять классов Поста - функции, сохраняющие ноль (T0), сохраняющие единицу (T1), линейные (L), монотонные (M) и самодвойственные (S) функции. Следовательно, существует 25 = 32 их всевозможных пересечений (рис. 1). Каждое из них представляет собой множество булевых функций, входящих в одни классы Поста и не входящих в другие, и само является замкнутым классом [4]. Каждое пересечение может содержать функции или быть пустым. Для доказательства того, что некоторое множество P не пусто, достаточно привести пример входящей в него функции, в то время как пустоту множества необходимо теоретически обосновать. Результаты исследования. Сведём информацию о пересечениях классов в таблицу 1 и включим в неё примеры функций. Для пустых множеств приведём обоснование пустоты, доказав теоремы. Таблица 1 Пересечения классов Поста № T0 T1 L M S Примеры функций, если они существуют 0 - - - - - Штрих Шеффера, стрелка Пирса (1 + xy, 1 + x + y + xy) 1 - - - - + Отрицание функции голосования (1 + xy + xz + yz) 2 - - - + - (нет) 3 - - - + + (нет) 4 - - + - - (нет) 5 - - + - + Отрицание (1 + x) 6 - - + + - (нет) 7 - - + + + (нет) 8 - + - - - Импликация (1 + x + xy, 1 + y + xy) 9 - + - - + (нет) 10 - + - + - (нет) 11 - + - + + (нет) 12 - + + - - Эквивалентность (1 + x + y) 13 - + + - + (нет) 14 - + + + - Тождественная единица (1) 15 - + + + + (нет) 16 + - - - - Отрицание импликации (x + xy, y + xy) 17 + - - - + (нет) 18 + - - + - (нет) 19 + - - + + (нет) 20 + - + - - Исключающее ИЛИ (x + y) 21 + - + - + (нет) 22 + - + + - Тождественный ноль (0) 23 + - + + + (нет) 24 + + - - - Функция вида x + z + xy 25 + + - - + Функция вида x + y + xy + xz + yz 26 + + - + - Конъюнкция (xy), дизъюнкция (x + y + xy) 27 + + - + + Функция голосования (xy + xz + yz) 28 + + + - - (нет) 29 + + + - + Исключающее ИЛИ от трёх переменных (x + y + z) 30 + + + + - (нет) 31 + + + + + Тождественная функция (x) Таким образом, существует 15 непустых множеств и 17 пустых. При этом все непустые множества содержат хотя бы одну функцию не более чем от трёх переменных. Рассмотрим обоснование пустоты для пересечений №№ 2-4, 6-7, 9-11, 13, 15, 17-19, 21, 23, 28 и 30. Теорема для множеств 2, 3, 6, 7. Если f монотонна, она входит хотя бы в один из классов T0 или T1. Доказательство. Пусть f монотонна и не принадлежит ни T0, ни T1. Тогда f(<0>) = 1, f(<1>) = 0. Но тогда при большем наборе аргументов <1> функция получает меньшее значение 0. Условие монотонности нарушается, противоречие. Функции, входящие в рассматриваемые множества, должны быть монотонными, но не входить ни в T0, ни в T1, что невозможно. Теорема для множества 4. Не существует линейной функции, не принадлежащей никаким другим классам Поста. Доказательство. Будем строить функцию, удовлетворяющую условию 4. Так как она линейна, её следует искать в виде: f(x1,…,xn) = a0 + a1x1 + a2x2 + … + anxn Не умаляя общности можно сказать, что все коэффициенты a1…an равны 1, т.к. переменные с нулевыми коэффициентами будут фиктивными: f(x1,…,xn) = a0 + x1 + x2 + … + xn Так как функция не сохраняет ноль, то f(0,…,0) = 1. С другой стороны, f(<0>) = a0 + 0 + … + 0 = a0, поэтому a0 = 1: f(x1,…,xn) = 1 + x1 + x2 + … + xn Так как функция не сохраняет единицу, то f(<1>) = 0. С другой стороны, f(<1>) = 1 + 1 + … + 1, где все единицы, кроме первой - значения переменных x1…xn. Эта сумма должна быть равна нулю, а значит, общее число слагаемых должно быть чётным, а число переменных - нечётным. Поэтому n будем считать нечётным числом. Проверим эту функцию на самодвойственность, построив двойственную функцию к ней: f(x1,…,xn) = 1 + x1 + x2 + … + xn f*(x1,…,xn) = (1 + x1 + x2 + … + xn)* = 0 ó x1 ó x2 ó …ó xn Будем преобразовывать f*(x1,…,xn), учитывая, что aó b = ┐(a + b) = 1 + a + b: f*(x1,…,xn) = 0 ó x1 ó x2 ó … ó xn = 1 + 0 + x1 ó x2 ó … ó xn = = 1 + 1 + x1 + x2 ó x3ó …ó xn = x1 + x2 ó x3ó …ó xn = … Таким способом мы приведём двойственную функцию к многочлену Жегалкина. В процессе преобразования свободный член многочлена будет чередоваться, но, если учесть, что n нечётно, в итоге свободный член будет равен 1, и мы получим выражение: f*(x1,…,xn) = 1 + x1 + x2 + … + xn Эта функция совпадает с исходной, а значит, функция f самодвойственна, и наша попытка построить функцию для исходного условия оказалась неудачной. Такой функции не существует. Теорема для множеств 9, 11, 13, 15, 17, 19, 21, 23. Если функция f самодвойственна, она либо сохраняет и 0, и 1, либо не сохраняет ни 0, ни 1. Доказательство. Если f самодвойственна, то возможны два варианта: f(<0>) = 0, тогда по определению самодвойственности f(<1>) = 1, функция принадлежит и T0, и T1. f(<0>) = 1, тогда f(<1>) = 0, и функция не принадлежит ни T0, ни T1. Функции, соответствующие условиям 9, 11, 13, 15, 17, 19, 21 и 23, должны быть самодвойственными, но принадлежать только одному из классов T0 и T1. Согласно доказанному выше это невозможно. Теорема для множества 10. Если f монотонна и не сохраняет 0, она тождественно равна 1. Доказательство. Пусть есть набор такой, что f() = 0. Если = <0>, функция сохраняет 0, противоречие. Если - ненулевой набор, то он больше набора <0>. На наборе <0> функция имеет значение 1, а на большем наборе - меньшее значение 0. Тогда условие монотонности нарушается - вновь противоречие. Таким образом, монотонная не сохраняющая ноль функция может оказаться только тождественной единицей. Но единица линейна, а функция из множества 10 не линейна по условию. Поэтому функции, удовлетворяющей условию для множества 10, нет. Теорема для множества 18. Если f монотонна и не сохраняет 1, она тождественно равна 0. Доказательство. Пусть есть набор такой, что f() = 1. Если = <1>, функция сохраняет 1, противоречие. Если - неединичный набор, то он меньше набора <1>. На наборе <1> функция имеет значение 0, а на меньшем наборе - большее значение 1. Тогда условие монотонности нарушается - противоречие. Таким образом, монотонная не сохраняющая единицу функция может оказаться только нулём. Но нулевая функция линейна, а функция из множества 18 не линейна по условию. Поэтому функции, удовлетворяющей условию для множества 18, нет. Теорема для 28 и 30. Не существует несамодвойственной функции, принадлежащей T0, T1 и L. Доказательство. Попробуем построить функцию, удовлетворяющую такому условию. Так как она линейна, будем искать её в виде: f(x1,…,xn) = a0 + a1x1 + a2x2 + … + anxn Без ограничения общности будем считать все коэффициенты перед переменными равными единице. Так как функция сохраняет ноль, то f(0,…,0) = 0. С другой стороны, f(0,…,0) = a0, поэтому a0 = 0. Так как функция сохраняет единицу, то f(1,…,1) = 1. С другой стороны, f(1,…,1) = 1 + 1 + … + 1, где все единицы - значения соответствующих переменных (мы учли, что a0 = 0). Чтобы f(1,…,1) равнялось единице, число единиц в правой части должно быть нечётным. Поэтому число переменных n будем считать нечётным. Функция принимает вид: f(x1,…,xn) = x1 + x2 + … + xn, n = 2k + 1, k Є N Построим двойственную функцию: f*(x1,…,xn) = x1 ó x2 ó …ó xn Учитывая, что aó b = ┐(a + b) = 1 + a + b, получаем: f*(x1,…,xn) = 1 + x1 + x2ó x3ó …ó xn = x1 + x2 + x3ó …ó xn = … Принимая во внимание нечётность n, устанавливаем, что f* имеет вид: f*(x1,…,xn) = x1 + x2 + … + xn = f(x1,…,xn) Таким образом, функция f оказалась самодвойственна, и наша попытка построить функцию, принадлежащую T0, T1 и L, но не принадлежащую S, оказалась неудачной. Теорема доказывает невозможность существования функций, принадлежащих двум пересечениям классов (T0, T1, L, M, -) и (T0, T1, L, -,-), т.к. монотонность функции в этом случае не играет роли. Практическое применение. Результаты исследования использованы при разработке интерактивного средства обучения студентов «Тренажёр по математической логике» (рис. 2). Разработанная программа позволяет студентам выполнять обучение и самоконтроль по различным задачам математической логики: исследование функций, выявление фиктивных переменных, подбор функций, отвечающих заданным условиям, преобразование булевых функций к стандартным видам - совершенным дизъюнктивным и конъюнктивным нормальным формам, многочленам Жегалкина. Результаты, полученные в этом исследовании, важны в процессе автоматической постановки задачи тренажёром, так как позволяют избежать формулировки задач, не имеющих решения (например, задача дополнить функцию голосования линейной функцией так, чтобы полученный набор функций был полным). Кроме того, исследование оказалось полезным для оптимизации алгоритмов поиска функций, удовлетворяющих заданным требованиям. Этот результат является значимым, так как большая размерность пространства функций приводит к высокой вычислительной сложности поиска, а отсечение заведомо пустых подпространств позволяет находить результат значительно быстрее. Рис. 2. Скриншот разработанного приложения Заключение. Проведённая работа позволила систематизировать информацию о пересечениях классов Поста и применить полученные знания в совершенствовании алгоритмов и в обучении. Последнее подтверждается использованием разработанного тренажёра в Санкт-Петербургском государственном электротехническом университете («ЛЭТИ») в курсе «Математическая логика и теория алгоритмов» под руководством профессора С. Н. Позднякова. В качестве продолжения исследования может быть проведена работа по определению мощности непустых пересечений классов Поста и вида функций, входящих в эти множества. Например, известно, что пересечение всех пяти классов Поста представляет собой одноэлементное множество, состоящее только из тождественной функции f(x) = x. Структура других пересечений на данный момент детально не изучена и может служить объектом дальнейших исследований.

Научные конференции

 

(c) Архив публикаций научного журнала. Полное или частичное копирование материалов сайта возможно только с письменного разрешения администрации, а также с указанием прямой активной ссылки на источник.