Статья:

Обобщение классов Поста на случай трехзначной логики

Конференция: XVII Студенческая международная научно-практическая конференция «Технические и математические науки. Студенческий научный форум»

Секция: Физико-математические науки

Выходные данные
Габутдинова К.С. Обобщение классов Поста на случай трехзначной логики // Технические и математические науки. Студенческий научный форум: электр. сб. ст. по мат. XVII междунар. студ. науч.-практ. конф. № 6(17). URL: https://nauchforum.ru/archive/SNF_tech/6(17).pdf (дата обращения: 29.03.2024)
Лауреаты определены. Конференция завершена
Эта статья набрала 2 голоса
Мне нравится
Дипломы
лауреатов
Сертификаты
участников
Дипломы
лауреатов
Сертификаты
участников
на печатьскачать .pdfподелиться

Обобщение классов Поста на случай трехзначной логики

Габутдинова Кадрия Сагитовна
студент, Самарский национальный исследовательский университет им. ак. С.П.Королева, РФ, г.Самара

 

Задачи

Обобщить классы Поста на случай трехзначной логики;

Доказать их замкнутость.

Функции двузначной и трехзначной логики

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

Функции двузначной логики  – это отображения вида

Функции многих переменных, каждый аргумент которых и сами функции могут принимать три значения: 0, 1 и 2. Полученные функции обозначаются .

Получилось, что функции трехзначной логики  – это отображения вида

Предполные классы

Замыканием множества булевых функций u называется множество всех суперпозиций функций класса , которое обозначается . Класс  называется функционально полным, если .

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

В классе  есть 5 предполных класса, называемых классами Поста:

1. Класс функций, сохраняющий константу 0:

2. Класс функций, сохраняющий константу 1:

3. Класс линейных функций:

4. Класс самодвойственных функций:

Говорят, что набор  предшествует набору  и пишут , если где 

5. Класс монотонных функций:

При переходе от двузначного случая к трехзначному наблюдается увеличение количества предполных классов. Таким образом, в   есть 18 предполных классов:

1. Класс функций, сохраняющий константу 0:

2. Класс функций, сохраняющий константу 1:

3. Класс функций, сохраняющий константу 2:

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

4. Класс функций, сохраняющий множество {0,1}:

5. Класс функций, сохраняющий множество {0,2}:

6. Класс функций, сохраняющий множество {1,2}:

7. Класс самодвойственных функций S:

Отрицание введено как отрицание Поста:  То есть этот класс является классом, сохраняющим отношение 

8. Класс линейных функций:

9. Класс монотонных функций M_0 относительно порядка :

10. Класс монотонных функций M_1 относительно порядка :

11. Класс монотонных функций M_2 относительно порядка 

12.  Класс  сохранения разбиения 

13. Класс  сохранения разбиения 

14. Класс  сохранения разбиения 

15. Центральный предполный класс , сохраняющий отношение 

16. Центральный предполный класс , сохраняющий отношение 

17. Центральный предполный класс , сохраняющий отношение 

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

В таблице 1 указаны строки принадлежности всех трехзначных функций, имеющих не более одной существенной переменной. Каждой функции поставим в соответствие строку принадлежности: «+», если  принадлежит соответствующему предполному классу, и «-», если  не принадлежит соответствующему предполному классу.

Таблица 1

a

b

c

T0

T1

T2

T0,1

T0,2

T1,2

S

L

M0

M1

M2

U0

U1

U2

C0

C1

C2

B

0

0

0

+

-

-

+

+

-

-

+

+

+

+

+

+

+

+

+

+

+

0

0

1

+

-

-

+

-

-

-

-

-

+

-

-

-

+

+

+

-

+

0

0

2

+

-

+

+

+

-

-

-

+

+

-

-

+

+

+

-

+

+

0

1

0

+

+

-

+

+

+

-

-

+

-

+

-

+

+

+

+

-

+

0

1

1

+

+

-

+

-

+

-

-

-

+

+

+

-

+

+

+

-

+

0

1

2

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

0

2

0

+

-

-

-

+

+

-

-

-

-

+

-

+

-

+

-

+

+

0

2

1

+

-

-

-

-

+

-

+

-

-

-

+

-

-

+

-

-

+

0

2

2

+

-

+

-

+

+

-

-

-

+

+

+

+

-

+

-

+

+

1

0

0

-

-

-

+

-

-

-

-

-

-

-

+

-

+

+

+

-

+

1

0

1

-

-

-

+

-

-

-

-

-

-

-

-

+

+

+

+

-

+

1

0

2

-

-

+

+

-

-

-

+

-

-

-

-

-

+

-

-

+

+

1

1

0

-

+

-

+

-

-

-

-

+

-

-

-

-

+

+

+

-

+

1

1

1

-

+

-

+

-

-

-

+

+

+

+

+

+

+

+

+

+

+

1

1

2

-

+

+

+

-

-

-

-

+

+

-

+

-

+

-

+

+

+

1

2

0

-

-

-

-

-

-

+

+

-

-

-

-

-

-

-

-

-

+

1

2

1

-

-

-

-

-

-

-

-

-

-

-

+

+

-

-

+

+

+

1

2

2

-

-

+

-

-

-

-

-

-

+

-

+

-

-

-

+

+

+

2

0

0

-

-

-

-

+

-

-

-

-

-

-

+

+

-

+

-

+

+

2

0

1

-

-

-

-

-

-

+

+

-

-

-

-

-

-

-

-

-

+

2

0

2

-

-

+

-

+

-

-

-

+

-

-

-

+

-

+

-

+

+

2

1

0

-

+

-

-

+

-

-

+

-

-

-

-

+

-

-

+

-

+

2

1

1

-

+

-

-

-

-

-

-

-

-

+

+

-

-

-

+

+

+

2

1

2

-

+

+

-

+

-

-

-

+

-

+

+

+

-

-

+

+

+

2

2

0

-

-

-

-

+

-

-

-

-

-

-

-

+

+

+

-

+

+

2

2

1

-

-

-

-

-

-

-

-

-

-

-

+

-

+

-

+

+

+

2

2

2

-

-

+

-

+

-

-

+

+

+

+

+

+

+

+

+

+

+

 

Доказательство замкнутости некоторых предполных классов.

- замкнутый класс.

Доказательство. Пусть дана произвольная систему функций  из  и функция . Среди переменных функций  могут встречаться и одинаковые, поэтому в качестве переменных функции  берутся все различные из них. Тогда  Следовательно, функция  также сохраняет ноль. Рассмотрен только частный случай (без переменных в качестве аргументов). Однако, поскольку тождественная функция сохраняет ноль, подстановка простых переменных эквивалентна подстановке тождественной функции, что и требовалось доказать.

Аналогично доказывается замкнутость классов 

S - замкнутый класс.

Доказательство. Пусть  и .

Тогда из принципа двойственности следует, что

                           .

Получается, что  и , что и требовалось доказать.

L - замкнутый класс.

Доказательство. Поскольку тождественная функция – линейная, достаточно рассмотреть только случай подстановки в формулы функций: пусть  и  Достаточно доказать, что . Действительно, если не учитывать слагаемых с коэффициентами , то всякую линейную функцию можно представить в виде . Если теперь вместо каждого  подставить линейное выражение, то получится снова линейное выражение или константа 0, 1 или 2.

 - замкнутый класс.

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

, откуда , следовательно , что и требовалось доказать.

Аналогично доказывается замкнутость классов  и .

Заключение

В ходе выполнения работы были обобщены классы Поста на случай трехзначной логики. Также была доказана замкнутость некоторых из них.

 

Список литературы: 
1. Г.П. Гаврилов, А.А. Сапоженко. Сборник задач по дискретной математике. Москва, Физматлит, 2005. 
2. С.В. Яблонский. Введение в дискретную математику. М.:Наука, 1979.