Мендельсон, упражнения, логика высказываний

[beroal]

Проверьте, пожалуйста, выполнение упражнений из учебника Мендельсона (английское 6-е издание). Это не составление таблиц истинности и не писание доказательств в объектной теории.

$L$ — классическая логика высказываний.

Упражнение 1.50. Пусть $\mathscr B$ — пропозициональная форма, не являющаяся тавтологией. Построим теорию $L^+$, добавив к $L$ в качестве новых аксиом все формулы, которые можно получить из $\mathscr B $, подставляя на места пропозициональных букв в $\mathscr B $ произвольные формы (с тем, однако, условием, чтобы на места всех вхождений одной и той же буквы подставлялась одна и та же формула). Показать, что теория $L^+$ противоречива.

Доказательство. Так как $\mathscr B$ не тавтология, существует распределение истинностных значений $v$ для пропозициональных букв, входящих в $\mathscr B$, при котором $\mathscr B$ примет значение Л. Пусть $\mathscr B'$ получена из $\mathscr B$ с помощью подстановки вместо пропозициональной буквы $B$ $A_1\implies A_1$, если $v(B)$ есть И, и $\lnot(A_1\implies A_1)$, если $v(B)$ есть Л. $A_1\implies A_1$ и $\lnot(A_1\implies A_1)$ принимают значения И и Л соответственно при любом распределении истинностных значений. Следовательно, $\lnot\mathscr B'$ принимает значения И при любом распределении истинностных значений, то есть является тавтологией. По предложению 1.14 (теорема о полноте) $\vdash_L \lnot\mathscr B'$. $\mathscr B'$ принадлежит $L^+$ по её определению. Следовательно, $L^+$ противоречива. $\qedsymbol$

Упражнение 1.52. (Мак-Кинси — Тарский, 1948.) Рассмотрим аксиоматическую теорию $P$, в которой имеется единственная бинарная связка $*$, единственное правило вывода — modus ponens (т. е. $\mathscr C$ следует из $\mathscr B * \mathscr C$ и $\mathscr B$) и аксиомами служат все формулы вида $\mathscr B * \mathscr B$. Доказать, что $P$ не является подходящей ни для какой (конечной) многозначной логики.

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

• Докажем, что множество теорем $P$ равно множеству всех формул $P$ вида $\mathscr B * \mathscr B $.
  
  ($\subseteq$) Допустим, существует вывод $\mathscr C $. Докажем, что $\mathscr C = \mathscr E * \mathscr E $ для некоторого $\mathscr E$.
  
  • Если $\mathscr C $ обоснована аксиомой, то доказано.
    
  • Если $\mathscr C $ обоснована modus ponens, тогда существуют более короткие выводы $\mathscr B * \mathscr C$ и $\mathscr B$. По индукции, $\mathscr B * \mathscr C = \mathscr E * \mathscr E$ для некоторого $\mathscr E$, $\mathscr B = \mathscr E$, $\mathscr C = \mathscr E$, $\mathscr B = \mathscr C$. По индукции, $\mathscr B = \mathscr E * \mathscr E$ для некоторого $\mathscr E$. Доказано.
    
  
  ($\supseteq$) Для любой формулы вида $\mathscr B * \mathscr B $ существует её вывод, состоящий из одного применения аксиомы.
  
  Доказано.
  
  
• Будем работать в такой конечной многозначной логике, что $P$ подходит для неё. Поскольку $A_1*A_1$ есть теорема $P$, для любого истинностного значения $x$ интерпретация $*$ на $x$ и $x$ принимает выделенное значение логики. Достаточно доказать, что существуют разные формулы $\mathscr B$ и $\mathscr C$ с одинаковой интерпретацией. Тогда при любом распределении истинностных значений букв, входящих в $\mathscr B$ и $\mathscr C$, $\mathscr B$ и $\mathscr C$ принимают одинаковые истинностные значения и $\mathscr B*\mathscr C$ принимает выделенное значение логики. Поскольку $P$ подходит, $\mathscr B*\mathscr C$ есть теорема $P$. Но для любого $\mathscr E$ $\mathscr B*\mathscr C\not=\mathscr E * \mathscr E$. Противоречие.
  
  Докажем, что существуют разные формулы с одинаковой интерпретацией. Пусть $I$ есть функция, которая отображает формулу в интерпретацию этой формулы и область определения которой — множество всех формул, в которые входит пропозициональная буква $A_1$ и только она.
  
  • Пусть $X$ есть множество всех истинностных значений логики. Область значений $I$ есть $X\to X$. Поскольку $X$ конечно, область значений $I$ конечна.
    
  • Область определения $I$ бесконечна. Докажем это. Рекурсивно определим функцию $f$ из $\mathbb{N} $: $f(0) = A_1$, $f(n+1) = A_1*f(n)$. $\mathbb{N} $ бесконечно, $f$ инъективна, область значений $f$ бесконечна, область значений $f$ включена в область определения $I$. Доказано.
    
  Следовательно, $I$ не инъективна. Следовательно, существуют формулы $\mathscr B$ и $\mathscr C$, $\mathscr B\not=\mathscr C$ и $I(\mathscr B)=I(\mathscr C)$ (их интерпретация одинакова). Доказано.

$\qedsymbol$

$L_I$ — интуиционистская логика высказываний.

В упражнении 1.60.a определены $(n+1)$-значные модели интуиционистской логики высказываний. Их я буду использовать. Осторожно, в русском издании (1971) в этом определении ошибка.

Теорема М.2. Для любых формул $\mathscr B $ и $\mathscr C $, значение $\mathscr B\implies \mathscr C$ равно $0$ тогда и только тогда, когда значение $\mathscr B$ нестрого больше, чем значение $\mathscr C$.

Доказательство. [Допустим, значение $\mathscr B$ меньше, чем значение $\mathscr C$. Значение $\mathscr C$ не $0$. По определению модели логики, значение $\mathscr B\implies \mathscr C$ равно значению $\mathscr C$, то есть не $0$.] [Допустим, значение $\mathscr B$ нестрого больше, чем значение $\mathscr C$. По определению модели логики, значение $\mathscr B\implies \mathscr C$ равно $0$.] $\qedsymbol$

Теорема М.0. Для любых формул $\mathscr B $ и $\mathscr C $, значение $\mathscr B\iff \mathscr C $ равно $0$ тогда и только тогда, когда значения $\mathscr B$ и $\mathscr C$ равны.

Доказательство. Эта формула после раскрытия определений становится $(\mathscr B\implies \mathscr C)\land(\mathscr C\implies \mathscr B)$. По определению модели логики, значение этой формулы равно $0$ тогда и только тогда, когда $\mathscr B\implies \mathscr C$ равно $0$ и значение $\mathscr C\implies \mathscr B$ равно $0$. Согласно теореме М.2, это эквивалентно тому, что значение $\mathscr B$ нестрого больше, чем значение $\mathscr C$, и значение $\mathscr C$ нестрого больше, чем значение $\mathscr B$. Это эквивалентно тому, что значения $\mathscr B$ и $\mathscr C$ равны. $\qedsymbol$

Упражнение 1.60.c. Для любого $m$ формула $\bigvee_{i\in[1;m], j\in[1;m], i\not=j} A_i\iff A_j $ (М.1) не является теоремой $L_I$.

Доказательство. Рассмотрим формулу М.1. Используем $m$-значную модель логики. Положим такое распределение истинностных значений, что для любого $i$ значение $A_i$ равно $i-1$. Каждый элемент дизъюнкции в формуле М.1 есть такой $A_i\iff A_j $, что $i\not=j$, тогда значения $A_i$ и $A_j$ разные, значение этого элемента дизъюнкции не $0$ согласно теореме М.0. По определению модели логики, значение М.1 не $0$. Следовательно, формула М.1 не выделенна, поэтому не является теоремой $L_I$ согласно упражнению 1.60.a. $\qedsymbol$

Упражнение 1.60.d. (Гёдель, 1933.) Теория $L_I$ не является подходящей ни для какой конечной многозначной логики.

Доказательство. [Дана $(n+1)$-значная модель логики. Рассмотрим формулу М.1 для $m$, равного $n+2$. [Дано распределение истинностных значений $v$ для пропозициональных букв, входящих в М.1. То есть $v$ есть функция из $[1;n+2]$ в $\{A_i|i\in[0;n]\}$. Размер области значений $v$ равен $n+2$, размер кодомена $v$ равен $n+1$, $v$ не инъективна. Существуют такие $i$ и $j$, что $v$ определена на них, $i\not=j $ и $v(A_i)=v(A_j)$. $A_i\iff A_j $ есть один из элементов дизъюнкции в М.1 и его значение равно $0$ согласно теореме М.0. Значение М.1 равно $0$ по определению модели логики.] Следовательно, такая версия М.1 выделенна в данной модели логики. Согласно упражнению 1.60.c, она не является теоремой $L_I$. $L_I$ не является подходящей для данной модели логики.] Следовательно, $L_I$ не является подходящей ни для какой конечной многозначной модели логики. $\qedsymbol$

[Xaositect]

Верно.