Совершенная конъюнктивная нормальная форма и тавтологии

[creative]

Цитата начала параграфа 8 первой главы из книги "Основы теоретической логики" Гильберта, Аккермана:

Цитата:

§ 8. Дополнительные замечания к проблеме всегда-истиннсти (*) и выполнимости.

Установленную в предыдущем параграфе совершенную нормальную форму (*) для выражения, которое состоит из основных высказываний $X_1, X_2, ..., X_n$, мы будем также называть кратко разложением выражения по $X_1, X_2, ..., X_n$.
Пусть теперь нам дано некоторое сложное высказывание, в котором содержаться, кроме $X_1, X_2, ..., X_n$, ещё основные высказывания $Y_1, Y_2, ..., Y_m$. И в этом случае мы можем говорить в известном смысле о разложении по $X_1, ..., X_n$. А именно, можно представить выражение в виде конъюнкции, у которой каждый конъюнктивный член является дизъюнкцией выражения, зависящего только от $Y_1, Y_2, ..., Y_m$, и одной из конституент (**) от $X_1, X_2, ..., X_n$.
Доказательство очень простое. Достаточно лишь разложить выражение по всем имеющимся основным высказываниям, т.е. по X_1, ..., $X_n, Y_1, ..., Y_m$, и соединить вместе члены, содержащие одинаковые по отношению к $X_1, X_2, ..., X_n$ конституенты.

* - под всегда-истинностью высказывания подразумевается тавтология
** - тут имеется ввиду совершенная конъюнктивная нормальная форма
*** - конституент в данном случае означает конъюнктивный член совершенной конъюнктивной нормальной формы

Вопросы:

1) Что вообще автор хотел этим сказать?

2) Что тут значит фраза "в известном смысле" в предложении И в этом случае мы можем говорить в известном смысле о разложении по $X_1, ..., X_n$?

3) В предложении:

А именно, можно представить выражение в виде конъюнкции, у которой каждый конъюнктивный член является дизъюнкцией выражения, зависящего только от $Y_1, Y_2, ..., Y_m$, и одной из конституент от $X_1, X_2, ..., X_n$.

Значит ли это, что:

выражение можно представить в виде несовершенной конъюнктивной нормальной формы, где каждый конъюнктивный член содержит дизъюнкцию всех $Y_1, Y_2, ..., Y_m$ (где, могут быть повторения любого $Y_i$, так как вся форма несовершенна, но они должны быть обязательно все) и в этом же конъюнктивном члене к нему прикреплен конституент (то есть член от совершенной формы) от $X_1, X_2, ..., X_n$

Или же это значит, что:

в этой несовершенной нормальной форме, каждый конъюнктивный член построен так, что вне зависимости от значений основных высказываний $X_1, X_2, ..., X_n$, результат таблицы истинности определяет только та часть члена, в которой фигурирует $Y_1, Y_2, ..., Y_m$

?

4) Что тут значит фраза содержащие одинаковые по отношению?

5) Или как называется именно эта теорема и где её можно найти? Обычно когда мне что-то непонятно, то я смотрю это же у другого автора, но именно это утверждение я не нашел.

[Xaositect]

Этот отрывок не про какую-то КНФ, а про вот такое разложение:
$f(x_1,\dots,x_n,y_1,\dots,y_m) = \prod\limits_{\sigma\in\mathbb{B}^n}(x_1^{\sigma_1}\vee x_2^{\sigma_2}\vee\dots\vee x_n^{\sigma_n}\vee f_\sigma(y_1,\dots,y_m))$

[creative]

Xaositect в сообщении #400864 писал(а):

Этот отрывок не про какую-то КНФ, а про вот такое разложение:
$f(x_1,\dots,x_n,y_1,\dots,y_m) = \prod\limits_{\sigma\in\mathbb{B}^n}(x_1^{\sigma_1}\vee x_2^{\sigma_2}\vee\dots\vee x_n^{\sigma_n}\vee f_\sigma(y_1,\dots,y_m))$

Спасибо! Для полноты информации: Что из себя представляет множество $\mathbb{B}^n$ (похоже на нотацию у В. И. Игошина) и как интерпретируется $f_\sigma()$? Или из какого источника данное разложение с такой нотацией?

[Xaositect]

$\mathbb{B}^n$ - это булев куб, множество всех двоичных наборов длины $n$, еще обозначается $E_2^n$ часто в русской литературе.
$f_{\sigma}(y_1,\dots,y_n) = f(\bar{\sigma}_1,\dots,\bar{\sigma}_n,y_1,\dots,y_n)$

Двойственное разложение $f(x_1,\dots,x_n) = \bigvee\limits_{\sigma\in\mathbb{B}^n} x_1^{\sigma_1}\dots x_n^{\sigma_n}f'_{\sigma}(y_1,\dots,y_n)$ достаточно часто используется, а на это я ссылку так сходу не дам. Возможно, мимоходом упоминается в учебнике Яблонского, не помню.

[creative]

Xaositect

Спасибо.
Ещё уточнение: Эти определения функции $f()$ есть рекурретность (т.е. в $f()$ как я понял выражено через саму себя)?

[Xaositect]

Так.
Утверждение звучит так: для любой функции $f$ от $n+m$ переменных можно подобрать $2^n$ функций $f_{\sigma},\sigma\in \mathbb{B}^n$ от $m$ переменных, что разложение из моего первого поста справедливо (для любых $x,y$)

А в своем втором посте я написал уже явную формулу, которая позволяет это сделать.

-- Вс янв 16, 2011 23:02:41 --

Вот у Вас там написано:

Цитата:

А именно, можно представить выражение в виде конъюнкции, у которой каждый конъюнктивный член является дизъюнкцией выражения, зависящего только от $Y_1,\dots,Y_m$, и одной из конституент (**) от $X_1,\dots,X_n$.

$f_{\sigma}(y_1,\dots,y_m)$ -- это "выражение, зависящее только от $Y_1,\dots,Y_m$", а $x^{\sigma_1}\vee\dots\vee x_n^{\sigma_n}$ - это конституэнта.

[creative]

То есть это свободное выражение от $\forall Y$.

Буду разбираться.