English version of this page
На главную страницу
Официальный сайт кафедры Математической теории интеллектуальных систем и лабораторий Проблем теоретической кибернетики и Математичеких проблем искусственного интеллекта механико-математического факультета МГУ им. М. В. Ломоносова
На первую страницу сайта Новости Кафедра Сотрудники Учеба Наука Исследования Журнал Культура Канал кафедры МаТИС в Телеграм

Сотрудники :: Гасанов Эльяр Эльдарович :: Публикации Гасанова Э.Э.

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

Гасанов Э.Э., Шакиров А.А.
Кафедра математической теории интеллектуальных систем, механико-математический факультет МГУ им М.В.Ломоносова

Пусть $R$ и $N$ – множества действительных и натуральных чисел, соответственно; $E_2 = \{0,1\}.$

$R^2$ – двумерное евклидово пространство и $B^n $ – единичный $n – $мерный куб.

Пусть $U=\{u_{1},u_{2},\dots,u_{n},\dots\}$ и $W=\{w_{1},w_{2},\dots,w_{n},\dots\}$ – алфавиты переменных принимающих значения из $R,$ и из $E_2,$ соответственно. Далее для простоты вместо $u_{n}$ и $w_{n}$ будем использовать знаки $x,y,$ и $X,Y,$ соответственно, возможно, с индексами.

Пусть $X_{1}\land X_{2},X_{1}\lor X_{2},\lnot X$ суть булевы функции, называемые, соответственно, конъюнкцией, дизъюнкцией и отрицанием и $B$ – множество этих функций.

Обычным образом введем понятие формулы над $B.$

Пусть ${\Phi}_{B}$ – множество всех формул над $B$ и ${\Phi}_{B}(X_{1},\dots,X_{n})$ (или просто $ {\Phi}_{B}(n)$) – множество всех формул над $B$, реализующих функции, существенно зависящие от переменных $X_{1},\dots,X_{n}$.

Формулы ${\cal A}$ и ${\cal B}$ из ${\Phi}_{B}$ называются равными, если они реализуют равные функции. Это отношение равенства разбивает ${\Phi}_{B}$ на классы эквивалентности ${\cal D},$ которые содержат точно все формулы, которые реализуют равные функции.

Открытое множество в $R^2$ будем называть также областью или фигурой.

Рассмотрим множество базисных фигур в $R^2$ ${\cal G}=\{G_1,G_2,\dots ,G_m\}.$ Каждой фигуре $G_i$ сопоставим предикат $p_i(x_1,x_2),$ областью истинности которого является $G_i$, $i=1,2,\dots,m.$

Пусть ${\cal P} = \{p_1(x_1,x_2),p_2(x_1,x_2),\dots , p_m(x_1,x_2)\}$ и ${\cal A}(X_{1},X_{2},\dots,X_{n})\in {\Phi}_{B}(n).$ Подставим в ${\cal A}$ вместо каждой переменной $X_{i}$ предикат $p_{j}$ из ${\cal P}$. Данную операцию назовем полной подстановкой (или просто подстановкой), и полученное выражение ${\cal A}(p_{1},p_{2},\dots,p_{m})$ назовем ${\cal P}$-формулой.

Поскольку описания фигуры $G$ как в виде открытого подмножество плоскости, так и в виде предиката $p$, область истинности которого есть это подмножество $G$, являются тавтологичными, то мы далее будем использовать предикат $p$ для обозначения фигуры $G$ и будем говорить "фигура $p$" несмотря на то, что $p$ – предикат, описывающий фигуру $G$.

Каждая ${\cal P}$-формула ${\cal A}(p_{1},p_{2},\dots,p_{m})$ задает некий предикат, или что то же самое некую фигуру.

Фигуры ${\cal F}_1$ и ${\cal F}_2$ называются равными (пишем ${\cal F}_1={\cal F}_2),$ если они совпадают в $R^2$ как множества.

${\cal P}$-формулы ${\cal A}({\cal P})$ и ${\cal B}({\cal P})$ назовем ${\cal P}$-равными (пишем ${\cal A}({\cal P})\stackrel{\cal P}{=} {\cal B}({\cal P}))$, если они задают равные фигуры.

Пусть $M$ – некоторое подмножество множества всех $m$-подстановок ${\Pi}^m$.

Формулы ${\cal A}$ и ${\cal B}$ называются $(M,{\cal P})$-равными, (пишем ${\cal A}\stackrel{M,{\cal P}}{=} {\cal B}$), если при любой соответственно одинаковой подстановке $\pi\in M$ в них предикатов из ${\cal P}$ вместо переменных получаемые ${\cal P}$-формулы являются ${\cal P}$-равными.

Отношение $(M,{\cal P})$-равенства на множестве ${\Phi}_B(n)$ разбивает это множество на классы эквивалентности ${\cal D}_{M,{\cal P}},$ которые содержат точно все такие формулы, которые являются $(M,{\cal P})$-равными.

Будем говорить, что множество базисных фигур ${\cal P}$ обладает $M$-свойством, если отношения равенства булевских формул и $(M,{\cal P})$-равенства эквивалентны, т. е. разбиения ${\cal D}$ и ${\cal D}_{M,{\cal P}}$ совпадают, или, что то же самое, для любых двух формул ${\cal A},{\cal B}\in {\Phi}_B(n)$ верно ${\cal A}\stackrel{M,{\cal P}}{=} {\cal B}$ тогда и только тогда, когда ${\cal A} = {\cal B}.$

Множество всех граничных точек фигуры $p$ назовем границей $\partial p$ фигуры $p.$

Не имеющую самопересечений замкнутую ломаную, состоящую из $n$ отрезков, назовем $n – $угольником.

Область в $R^2,$ граница которой является $n – $угольником, называется $n – $угольной областью. Заметим, что для любого невырожденного $n – $угольника существует две $n – $угольные области, границей которых он является (внешняя и внутренняя).

Если $p$ некоторая фигура, то обозначим

\begin{displaymath} h(p) = \left\{\begin{array}{ll} 1,&\mbox{ если $p\not\equiv 0$,} \\ 0,&\mbox{ если $p \equiv 0$.} \end{array}\right. \end{displaymath}

Пусть $p$ – некоторая фигура. Через $p^1$ обозначим фигуру $p$, а через $p^0$ – дополнение к фигуре $p$, т.е. фигуру ${\overline p}$.

Пусть

\begin{displaymath} \pi = \left( \begin{array}{cccc}1 & 2 & \dots & m \\ i_1 & i_2 & \dots & i_m \end{array} \right) \mbox{–-} \end{displaymath}

$m$-подстановка из $\Pi^m$ и ${\cal P}=\{p_1,\dots,p_m\}$ – множество базисных фигур. Тогда булевскую функцию

\begin{displaymath}{\Omega}^{\cal P}_{\pi}({\alpha}_1,\dots,{\alpha}_m)= h(p^{{... ...1}\cap p^{{\alpha}_2}_{i_2}\cap\dots \cap p^{{\alpha}_m}_{i_m})\end{displaymath}

назовем определяющей функцией множества базисных фигур ${\cal P}$ относительно подстановки $\pi.$

Пусть $ M = \{{\pi}_1,\dots,{\pi}_k\}\subseteq \Pi^m$ и ${\cal P}=\{p_1,p_2,\dots ,p_m\}$ – множество базисных фигур, тогда булевскую функцию

\begin{displaymath}{\chi}^{{\cal P}}_M = {\Omega}^{{\cal P}}_{{\pi}_1}\lor {\Ome... ...{\cal P}}_{{\pi}_2}\lor\dots\lor {\Omega}^{{\cal P}}_{{\pi}_k} \end{displaymath}

назовем определяющей функцией множества базисных фигур ${\cal P}$ относительно множества подстановок $M$.

 

Теорема 1   Пусть $ M \subseteq \Pi^m,$ тогда множество базисных фигур ${\cal P}=\{p_1,p_2,\dots ,p_m\}$ обладает $M$-свойством тогда и только тогда, когда

\begin{displaymath}{\chi}^{{\cal P}}_M \equiv 1.\end{displaymath}

 

Теорема 2   Для любого $n$ из $N$ если $M\subseteq \Pi^n$ и $\vert M \vert = 1,$ то существует такое множество базисных фигур ${\cal P}_n=\{p_1,p_2,\dots,p_n\},$ обладающее $M$-свойством, что для каждого $i\in\{1,2,\dots,n\}$ фигура $p_i$ является $m_i – $угольной областью, где

\begin{displaymath} m_i = \left\{\begin{array}{ll}4, &\mbox{ если $i=1,2,3$}\\ 2^{i-1}-m_{i-1}, &\mbox{ если $i>3.$} \end{array}\right. \end{displaymath}

 

Теорема 3   Для любого $m$ из $N$ существует такое число $n$ в $N$, что если $M\subseteq \Pi^n$ и $\vert M \vert = 1,$ то никакое множество базисных фигур ${\cal P}_n=\{p_1,p_2,\dots,p_n\},$ где при $i = 1,2,\dots,n$ каждая область $p_i$ является $k_i – $угольной и $k_i\leq m$, не может обладать $M$-свойством.

Обозначим через $\varepsilon$ следующую подстановку

\begin{displaymath} \varepsilon = \left( \begin{array}{cccc}1 & 2 & \dots & m \\ 1 & 2 & \dots & m \end{array} \right). \end{displaymath}

 

Теорема 4   Для любого $n$ из $N$ и произвольного множества базисных фигур ${\cal P}=\{p_1,p_2,\dots,p_n\}$ справедливо ${\chi}^{{\cal P}}_{\Pi^n} \equiv 1$ тогда и только тогда, когда на каждом слое куба $B^n $ существует хотя бы один набор ${\stackrel{\sim}{\alpha}}$ такой, что ${\Omega}^{{\cal P}}_{\varepsilon} ({\stackrel{\sim}{\alpha}}) = 1.$

 

Теорема 5   Для любого $n$ из $N$ и произвольного множества базисных фигур ${\cal P}_n=\{p_1,p_2,\dots,p_n\},$ такого, что $p_{n}\subset p_{n-1}\subset\dots\subset p_{1},$ справедливо, что ${\cal P}_n$ обладает $\Pi^n$-свойством.

Труды II Международной конференции "Дискретные модели в теории управляющих систем", Красновидово, (23–28 июня 1997 г.), – М: Диалог-МГУ, 1997,

Наверх

   © 2001- г. Кафедра Математической теории интеллектуальных систем, лаборатория ПТК, лаборатория МПИИ Написать вебмастеру   
Последние новости - в телеграм-канале кафедры МаТИС: Канал кафедры МаТИС в Телеграм Rambler's Top100 Рейтинг@Mail.ru