Сотрудники :: Гасанов Эльяр Эльдарович :: Публикации Гасанова Э.Э.
К вопросу о предикатной эквивалентности формул алгебры логики
Гасанов Э.Э., Шакиров А.А. Кафедра математической теории интеллектуальных систем,
механико-математический факультет МГУ им М.В.Ломоносова
Пусть и – множества действительных и натуральных чисел,
соответственно;
– двумерное евклидово пространство и
– единичный мерный куб.
Пусть
и
– алфавиты переменных
принимающих значения из и из соответственно.
Далее для простоты
вместо и будем использовать знаки и
соответственно, возможно, с индексами.
Пусть
суть булевы функции,
называемые,
соответственно, конъюнкцией, дизъюнкцией и отрицанием и –
множество этих функций.
Обычным образом введем понятие формулы над
Пусть – множество всех формул над
и
(или просто
) – множество
всех формул над , реализующих функции, существенно зависящие
от переменных
.
Формулы и из
называются равными, если они реализуют
равные функции. Это отношение равенства
разбивает на классы эквивалентности
которые содержат точно все формулы, которые реализуют равные функции.
Открытое множество в будем называть также областью
или фигурой.
Рассмотрим множество базисных фигур в
Каждой фигуре сопоставим предикат
областью истинности которого является ,
Пусть
и
Подставим в вместо каждой
переменной предикат из .
Данную операцию назовем полной подстановкой (или просто подстановкой),
и полученное выражение
назовем -формулой.
Поскольку описания фигуры как в виде открытого подмножество
плоскости, так и в виде предиката , область истинности которого есть
это подмножество , являются тавтологичными, то мы далее
будем использовать предикат для обозначения фигуры
и будем говорить "фигура " несмотря на то, что –
предикат, описывающий фигуру .
Каждая -формула
задает некий предикат, или что то же самое
некую фигуру.
Фигуры и
называются равными (пишем
если они совпадают в как множества.
-формулы
и
назовем
-равными
(пишем
,
если они задают равные фигуры.
Пусть – некоторое подмножество
множества всех -подстановок .
Формулы и называются -равными,
(пишем
),
если при любой соответственно одинаковой подстановке
в них предикатов из вместо переменных
получаемые -формулы являются
-равными.
Отношение -равенства
на множестве разбивает
это множество на классы эквивалентности
которые содержат точно все такие формулы, которые являются
-равными.
Будем говорить, что множество базисных фигур
обладает -свойством, если отношения равенства булевских формул
и -равенства эквивалентны, т. е.
разбиения и
совпадают,
или, что то же самое,
для любых двух формул
верно
тогда и только тогда, когда
Множество всех граничных точек фигуры назовем границей
фигуры
Не имеющую самопересечений замкнутую ломаную, состоящую из
отрезков, назовем
угольником.
Область в граница которой является угольником, называется
угольной областью.
Заметим, что для любого невырожденного угольника
существует две угольные области, границей которых он
является (внешняя и внутренняя).
Если некоторая фигура, то обозначим
Пусть – некоторая фигура. Через обозначим фигуру ,
а через – дополнение к фигуре , т.е. фигуру
.
Пусть
-подстановка из и
–
множество базисных фигур.
Тогда булевскую функцию
назовем определяющей функцией множества базисных фигур
относительно подстановки
Пусть
и
– множество базисных фигур,
тогда булевскую функцию
назовем определяющей функцией множества базисных фигур
относительно множества подстановок .
Теорема 1
Пусть
![$ M \subseteq \Pi^m,$](images/kvoproprekv/img71.gif) тогда
множество базисных фигур
![${\cal P}=\{p_1,p_2,\dots ,p_m\}$](images/kvoproprekv/img69.gif)
обладает ![$M$](images/kvoproprekv/img43.gif) -свойством
тогда и только
тогда, когда
Теорема 2
Для любого ![$n$](images/kvoproprekv/img57.gif) из ![$N$](images/kvoproprekv/img2.gif)
если
![$M\subseteq \Pi^n$](images/kvoproprekv/img73.gif) и
![$\vert M \vert = 1,$](images/kvoproprekv/img74.gif) то
существует такое множество базисных фигур
![${\cal P}_n=\{p_1,p_2,\dots,p_n\},$](images/kvoproprekv/img75.gif)
обладающее ![$M$](images/kvoproprekv/img43.gif) -свойством, что для каждого
![$i\in\{1,2,\dots,n\}$](images/kvoproprekv/img76.gif)
фигура ![$p_i$](images/kvoproprekv/img77.gif) является
![$m_i – $](images/kvoproprekv/img78.gif) угольной областью, где
Теорема 3
Для любого ![$m$](images/kvoproprekv/img44.gif) из ![$N$](images/kvoproprekv/img2.gif) существует такое число ![$n$](images/kvoproprekv/img57.gif) в ![$N$](images/kvoproprekv/img2.gif) , что
если
![$M\subseteq \Pi^n$](images/kvoproprekv/img73.gif) и
![$\vert M \vert = 1,$](images/kvoproprekv/img74.gif) то
никакое
множество базисных фигур
![${\cal P}_n=\{p_1,p_2,\dots,p_n\},$](images/kvoproprekv/img75.gif)
где при
![$i = 1,2,\dots,n$](images/kvoproprekv/img80.gif)
каждая область ![$p_i$](images/kvoproprekv/img77.gif) является ![$k_i – $](images/kvoproprekv/img81.gif) угольной и ![$k_i\leq m$](images/kvoproprekv/img82.gif) ,
не может обладать ![$M$](images/kvoproprekv/img43.gif) -свойством.
Обозначим через следующую подстановку
Теорема 4
Для любого ![$n$](images/kvoproprekv/img57.gif) из ![$N$](images/kvoproprekv/img2.gif) и произвольного множества базисных фигур
![${\cal P}=\{p_1,p_2,\dots,p_n\}$](images/kvoproprekv/img85.gif) справедливо
![${\chi}^{{\cal P}}_{\Pi^n} \equiv 1$](images/kvoproprekv/img86.gif) тогда и только тогда, когда
на каждом слое куба ![$B^n $](images/kvoproprekv/img5.gif) существует хотя бы один набор
![${\stackrel{\sim}{\alpha}}$](images/kvoproprekv/img87.gif) такой, что
Теорема 5
Для любого ![$n$](images/kvoproprekv/img57.gif) из ![$N$](images/kvoproprekv/img2.gif) и произвольного множества базисных фигур
![${\cal P}_n=\{p_1,p_2,\dots,p_n\},$](images/kvoproprekv/img75.gif) такого, что
![$p_{n}\subset p_{n-1}\subset\dots\subset p_{1},$](images/kvoproprekv/img89.gif)
справедливо, что ![${\cal P}_n$](images/kvoproprekv/img90.gif) обладает ![$\Pi^n$](images/kvoproprekv/img91.gif) -свойством.
Труды II Международной конференции "Дискретные модели в теории управляющих систем", Красновидово, (23–28 июня 1997 г.), – М: Диалог-МГУ, 1997,
Наверх
|