отношение следования

[GlobalMiwka]

Здравствуйте.

В книге Клини "Математическая логика"

Теорема 1. (Подстановка вместо атомов.) Пусть $E$-формула в которую входят только атомы $P_1,...,P_n$, а $E^*$ - формула, полученная из $E$ одновременной подстановкой формул $A_1,...,A_n$ вместо $P_1,...,P_n$ соответственно. Если $\models E$, то $\models E^*$ ($\models E$ - общезначимость)

Теорема 8. (1) $A\models B$ тогда и только тогда, когда $\models A \rightarrow B$ (2) при $m \geq 1: A_1,A_2,...,A_{m-1},A_m \models B$ тогда и только тогда, когда $A_1,Aф_2,...,A_{m-1}\models A_m \rightarrow B$ ($\models$ - значит следует)

Задача 7.3. Докажите, что в обозначениях теоремы 1 (при $m+1$ формулах) если $A_1,A_2,...,A_{m-1},A_m \models B$, то $A_1^*,A_2^*,...,A_{m-1}^*,A_m^* \models B^*$ (Указание: воспользоваться следствием теоремы 8, а именно: $A_1,A_2,...,A_{m-1},A_m \models B \equiv \models A_1\rightarrow (...(A_{m-1}\rightarrow (A_m\rightarrow B))...)$)

Если вместо атомов в формулах $A_1,A_2,...,A_{m-1},A_m,B$ подставить формулы в результате которых получится меньшее число атомов нежели в исходных таблицах истинности, то может получиться, что будут выбраны строки, в которых не содержатся строки, в которых все значения в столбцах $A_1^*,A_2^*,...,A_{m-1}^*,A_m^*, B^*$ истинны, как тогда получится следование?

[arseniiv]

GlobalMiwka в сообщении #1431003 писал(а):

Если вместо атомов в формулах $A_1,A_2,...,A_{m-1},A_m,B$ подставить формулы в результате которых получится меньшее число атомов нежели в исходных таблицах истинности, то может получиться, что будут выбраны строки, в которых не содержатся строки, в которых все значения в столбцах $A_1^*,A_2^*,...,A_{m-1}^*,A_m^*, B^*$ истинны, как тогда получится следование?

Честно говоря, вы могли бы сформулировать более понятно, это пришлось секунд тридцать распутывать.

А вы проверьте, что если в таблице истинности для исходных формул не было строк $(A_1,\ldots,A_m, B) = (1,\ldots,1,0)$, то и в таблице для результатов подстановки тоже не будет строк $(A^*_1,\ldots,A^*_m, B^*) = (1,\ldots,1,0)$. Может быть от противного будет доказать удобно.

[GlobalMiwka]

Что-то не совсем ясно. Допустим для $A_1,A_2,...,A_{m-1},A_m,B$ существует $10$ атомов, т.е. $2^{10}$ комбинаций сочетаний $10$ атомов, а после подстановки получится, скажем, $8$ атомов, тогда будет $2^8$ комбинаций, что если эти $2^8$ комбинаций не содержат ни одной строки с истинностными значениями для всех $A_1^*,A_2^*,...,A_{m-1}^*,A_m^*, B^*$ ? Неужели не может быть так, что после подстановки в формуле $A_1$ атомов какой-нибудь формулой она $A_1^*$ не может быть ложной всегда ?

[arseniiv]

Если она будет ложной всегда, это как раз не страшно, и да, такое возможно: $P\wedge Q$ иногда истинна, но $P\wedge\neg P$ тождественно ложна. Страшнее было бы, если $B^*$ будет ложной при том, что все $A^*_i$ истинны, но если с $B, A_i$ такого не случалось, то не случится и тут.

[GlobalMiwka]

Почему не страшно? Допустим как у вас $A_i = P\wedge Q$ заменим $P,Q$ на $S,\neg S$ получим $S\wedge \neg S \equiv 0$, тогда не выполняется условие, что существует срока $(A_1,\ldots,A_m, B) = (1,\ldots,1,1)$. Мне не ясен ход ваших мыслей. Как использовать следствие $A_1,A_2,...,A_{m-1},A_m \models B \equiv \models A_1\rightarrow (...(A_{m-1}\rightarrow (A_m\rightarrow B))...)$ мне не совсем ясно. Мне ясно лишь, что $\models A_1^*\rightarrow (...(A_{m-1}^*\rightarrow (A_m^*\rightarrow B^*))...)$ - тождественно истинна, общезначима.

[arseniiv]

GlobalMiwka в сообщении #1431063 писал(а):

тогда не выполняется условие, что существует срока $(A_1,\ldots,A_m, B) = (1,\ldots,1,1)$

А для чего это нужно? Для логического следования не нужно, для него нужно только чтобы не было строк $(1,\ldots,1,\mathbf0)$, все остальные могут быть в любом количестве.

[GlobalMiwka]

В книге "Пусть теперь нам даны $m$ формул. Переходя от случая $m=1$ к общему говорим, что "$B$ является следствием из формул $A_1,\cdots ,A_m$ (в исчислении высказывания или в силу исчисления высказывания) и пишем $A_1,\cdots ,A_m\models B$, если в таблицах истинности на входах которых перечень $P_1,\cdots ,P_n$ атомов, входящих в одну или более из формул $A_1,\cdots , A_m,B$ формула $B$ даёт $t$ во всех строках, в которых формулы $A_1\cdots ,A_m$ одновременно дают $t$. Символ $\models$ можно читать как "влечет", "влекут".

[GlobalMiwka]

Вот в доказательстве теоремы 8 первой части говорится: "Обратно, если $\models A\rightarrow B$, то $A\rightarrow B$ дает $t$ во всех строках, где $A$ дает $t$ (и, конечно, во всех остальных строках). Следовательно по таблице для импликации $B$ должна давать $t$ во всех тех строках, где $A$ дает $t$, а это значит, что $A\models B$". Вопрос возникает, а почему $A$ должна принимать именно 2 значения, что если после подстановки $A^*$ всегда ложная, как тогда получится $A^*\models B^*$ ?

[arseniiv]

GlobalMiwka в сообщении #1431141 писал(а):

Вопрос возникает, а почему $A$ должна принимать именно 2 значения, что если после подстановки $A^*$ всегда ложная, как тогда получится $A^*\models B^*$ ?

Так ещё раз, ничего страшного не произойдёт. Если $X = 0$, то $(X\to Y) = 1$. Так что если $A^*$ тождественно ложна, $A^*\vDash C$ для любой $C$, в том числе для $C\equiv B^*$.

[GlobalMiwka]

т.е. нет надобности, чтобы в таблицах истинности формул $A_1,\cdots ,A_m$ была строка, где все значения $t$ ? Тогда пользуясь следствием теоремы 8. получаем тавтологию $\models A_1\rightarrow (...(A_{m-1}\rightarrow (A_m\rightarrow B))...)$ затем применяем теорему 1 и получаем тавтологию $\models A_1^*\rightarrow (...(A_{m-1}^*\rightarrow (A_m^*\rightarrow B^*))...)$ далее снова применяя следствие теоремы 8 получаем $A_1^*,A_2^*,...,A_{m-1}^*,A_m^* \models B^*$.

Далее в книге пишется, что следующие фразы равносильны:

1. $\models A \rightarrow B$
2. $A\models B$
3. $\vdash A\rightarrow B$
4. $A\vdash B$

2 и 4 выражения равносильны, но в выражении 4 $A$ предполагается имеющим истинное значение, а согласно вам получается, что $A$ в выражении 2 может быть ложью всегда.

[arseniiv]

GlobalMiwka в сообщении #1431265 писал(а):

т.е. нет надобности, чтобы в таблицах истинности формул $A_1,\cdots ,A_m$ была строка, где все значения $t$ ?

Совершенно.

GlobalMiwka в сообщении #1431265 писал(а):

Тогда пользуясь следствием теоремы 8. получаем тавтологию $\models A_1\rightarrow (...(A_{m-1}\rightarrow (A_m\rightarrow B))...)$ затем применяем теорему 1 и получаем тавтологию $\models A_1^*\rightarrow (...(A_{m-1}^*\rightarrow (A_m^*\rightarrow B^*))...)$ далее снова применяя следствие теоремы 8 получаем $A_1^*,A_2^*,...,A_{m-1}^*,A_m^* \models B^*$.

Да, так проще всего получить.

GlobalMiwka в сообщении #1431265 писал(а):

но в выражении 4 $A$ предполагается имеющим истинное значение

Нет, не так. Когда мы делаем вывод, мы вообще не вычисляем значения истинности — они ведь при этом не нужны; кроме того если бы мы даже это делали, мы заведомо отбрасывали бы случаи, когда $A$ ложно, т. к. это наша гипотеза, и это как раз и иллюстрируется связью $\vdash$ с $\vDash$: чтобы узнать, есть ли логическое следование $A_1,\ldots\vdash B$, мы, можно сказать, принимаем все $A_i$ истинными (ведь строки, где какое-то из них имеет значение 0, нам не интересны — нам нужно только чтобы везде, где все $A_i$ истинны, было истинным и $B$) — и чтобы узнать о выводимости $A\vdash B$, мы позволяем себе использовать $A$ наравне с аксиомами. Две вполне аналогичные вещи.

[GlobalMiwka]

Ясно, спасибо за ваше потраченное время.