hw-theory.tex

\documentclass[10pt,a4paper,oneside]{article}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{enumerate}
\usepackage{stmaryrd}
\usepackage[left=2cm,right=2cm,top=2cm,bottom=2cm,bindingoffset=0cm]{geometry}
\usepackage{proof}
\newcommand{\gq}[1]{\texttt{<<}#1\texttt{>>}}
\newcommand{\ogq}[1]{\overline{\texttt{<<}#1\texttt{>>}}}
\begin{document}

\begin{center}{\Large\textsc{\textbf{Теоретические (``малые'') домашние задания}}}\\
             \it Математическая логика, ИТМО, М3234-М3239, весна 2018 года\end{center}

\section*{Домашнее задание №1: <<знакомство с исчислением высказываний>>}

Докажите при любых подстановках метапеременных $\alpha$, $\beta$ и $\gamma$:
\begin{enumerate}
\item $\vdash\alpha\&\beta\rightarrow\beta\&\alpha$
\item $\vdash\alpha \rightarrow \neg\neg \alpha$
\item $\vdash\alpha\&(\beta\vee\gamma) \rightarrow (\alpha\vee\beta)\&(\alpha\vee\gamma)$
\item $\vdash\neg(\alpha\&\beta) \rightarrow \neg\alpha\vee\neg\beta$
\item $\vdash(\alpha\rightarrow\beta)\rightarrow(\neg\beta\rightarrow\neg\alpha)$
\end{enumerate}

\section*{Домашнее задание №2: <<теорема о полноте исчисления высказываний>>}

В данном домашнем задании вам будет предложено доказать несколько
важных лемм, используемых в теореме о полноте исчисления
высказываний. Подробнее с этой теоремой можно ознакомиться в конспекте курса,
глава 5. В решениях можно пользоваться всем ранее доказанным
на парах и в других домашних заданиях.

\begin{enumerate}
\item Докажите при любых значениях метапеременных $\alpha$, $\beta$:
\begin{enumerate}
\item $\alpha,\beta \vdash \alpha\&\beta$
\item $\neg\alpha,\beta \vdash \neg(\alpha\&\beta)$
\item $\alpha,\neg\beta \vdash \neg(\alpha\&\beta)$
\item $\neg\alpha,\neg\beta \vdash \neg(\alpha\&\beta)$
\item $\alpha,\beta \vdash \alpha\vee\beta$
\item $\neg\alpha,\beta \vdash \alpha\vee\beta$
\item $\alpha,\neg\beta \vdash \alpha\vee\beta$
\item $\neg\alpha,\neg\beta \vdash \neg(\alpha\vee\beta)$
\item $\alpha,\beta \vdash \alpha\rightarrow\beta$
\item $\alpha,\neg\beta \vdash \neg(\alpha\rightarrow\beta)$
\item $\neg\alpha,\beta \vdash \alpha\rightarrow\beta$
\item $\neg\alpha,\neg\beta \vdash \alpha\rightarrow\beta$
\item $\neg\alpha \vdash \neg\alpha$
\item $\alpha \vdash \neg\neg\alpha$
\end{enumerate}

\item Докажите, что при любых значениях метапеременной $\alpha$ 
справедливо $\vdash \alpha\vee\neg\alpha$

\item Докажите, что при любых списках формул $\Gamma$ и $\Delta$ и при любых
значениях метапеременных $\gamma$,$\delta$,$\zeta$
если $\Gamma \vdash \gamma$, $\Delta \vdash \delta$ и $\gamma,\delta\vdash\zeta$,
то $\Gamma,\Delta\vdash\zeta$

\item Докажите, что если $\Gamma, \rho \vdash \alpha$ и $\Gamma, \neg\rho \vdash \alpha$,
то $\Gamma \vdash \alpha$
\end{enumerate}

\section*{Домашнее задание №3: <<интуиционистское исчисление высказываний>>}

Введём обозначение: нижним индексом у <<турникета>> будем указывать логику, в которой 
проводится доказательство. Если высказывание $\alpha$ доказуемо в интуиционистской логике,
будем писать $\vdash_\texttt{И}\alpha$, если в классической --- $\vdash_\texttt{К}\alpha$.

\begin{enumerate}

\item Напомним, как на лекции определялась оценка высказываний интуиционистского 
исчисления на топологическом пространстве $\langle X, \Omega \rangle$:

\begin{tabular}{l}\\
$\llbracket \alpha \& \beta \rrbracket = \llbracket \alpha \rrbracket \cap \llbracket \beta \rrbracket$\\
$\llbracket \alpha \vee \beta \rrbracket = \llbracket \alpha \rrbracket \cup \llbracket \beta \rrbracket$\\
$\llbracket \alpha \rightarrow \beta \rrbracket = \mathrm{int}(\mathrm{c}(\llbracket \alpha \rrbracket) \cup \llbracket \beta \rrbracket)$\\
$\llbracket \neg \alpha \rrbracket = \mathrm{int}(\mathrm{c}(\llbracket \alpha \rrbracket))$
\end{tabular}

Также, положим, что высказывание $\alpha$ истинно, если $\llbracket\alpha\rrbracket = X$
(т.е. любое доказуемое высказывание неизбежно имеет оценку, равную всему пространству).
Докажите, что так опеределённая оценка корректна.

\item Докажите теорему Гливенко: $\vdash_\texttt{К}\alpha$ тогда и только тогда, когда
$\vdash_\texttt{И}\neg\neg\alpha$. Чтобы это сделать, сперва докажите три вспомогательных
утверждения:
\begin{enumerate}
\item $\vdash_\texttt{И}\neg\neg\alpha$, если $\alpha$ --- некоторая аксиома интуиционистского
исчисления высказываний.
\item При любом $\alpha$ выполнено $\vdash_\texttt{И}\neg\neg(\neg\neg\alpha \rightarrow \alpha)$
\item При любых $\alpha$ и $\beta$, если $\vdash_\texttt{И}\neg\neg\alpha$ и
$\vdash_\texttt{И}\neg\neg(\alpha\rightarrow\beta)$, то $\vdash_\texttt{И}\neg\neg\beta$
\end{enumerate}

\item Покажите с помощью опровергающего примера, что в интуиционистской логике не выполнено:
\begin{enumerate}
\item $\vdash_\texttt{И}\neg\neg P\rightarrow P$
\item $\vdash_\texttt{И}((P\rightarrow Q)\rightarrow P)\rightarrow P$
 (<<закон Пирса>>)
\end{enumerate}

\item (Задача Куратовского) Будем применять к множеству в некоторой топологии различные 
последовательности операций $\mathrm{int}$ и $\mathrm{cl}$ и смотреть на получившиеся
результаты. Некоторые множества будут
совпадать: скажем, всегда $\mathrm{int}A = \mathrm{int}(\mathrm{int}A)$, а некоторые будут
различны. Сколько вообще возможно получить различных множеств таким способом?

\end{enumerate}

\section*{Классное-домашнее задание №4: <<Алгебры Гейтинга и Линденбаума>>}

Прежде чем приступить к формулировке заданий, напомним некоторые определения с лекций.
Мы рассматриваем интуиционистское исчисление высказываний, пусть все высказывания этого 
исчисления образуют множество $F$.

\begin{enumerate}
\item Будем писать $\alpha\sqsubseteq^*\beta$, если $\alpha\vdash\beta$.
\item Будем писать $\alpha\approx\beta$, если $\alpha\vdash\beta$ и $\beta\vdash\alpha$
\item Пусть задано некоторое отношение эквивалентности $R$, тогда имеют место следующие определения:
\begin{itemize}
\item $[\alpha]_R = \{\beta\in F \mid R(\alpha,\beta) \}$.
Нижний индекс у квадратных скобок мы будем опускать, если ясно,
о каком отношении идёт речь.
\item \emph{(фактор-множество)} $F/R = \{[\alpha]_R \mid \alpha \in F \}$.
\end{itemize}
\item Рассмотрим фактор-множество $F/\!\!\approx$. Будем писать 
$[\alpha]_\approx\sqsubseteq[\beta]_\approx$, если $\alpha_1\sqsubseteq^*\beta_1$
при всех $\alpha_1\in[\alpha]_\approx$ и $\beta_1\in[\beta]_\approx$. 
\item Дистрибутивная решётка --- решётка, в которой при любых значениях $a$, $b$ и $c$
выполнено $(a+b)\cdot c = (a \cdot c) + (b \cdot c)$
\item Импликативная решётка --- решётка, в которой для любых элементов $a$ и $b$ определена
операция псевдодополнения ($a\rightarrow b = \max \{c \mid a\cdot c\le b\}$)
\item Алгебра Гейтинга --- импликативная решётка с $0$.
\end{enumerate}

\subsection*{Задания}

\begin{enumerate}
\item Покажите, что $[\alpha]_R=[\beta]_R$ тогда и только тогда, когда $R(\alpha,\beta)$.
\item Покажите, что $[\alpha]_R$ и $[\beta]_R$ либо совпадают, либо не пересекаются.
\item Покажите, что если при некоторых $\alpha$, $\alpha_1$, $\beta$, $\beta_1$ 
выполнено $\alpha_1\in[\alpha]_\approx$, $\beta_1\in[\beta]_\approx$ и 
$\alpha_1\sqsubseteq^*\beta_1$, то $[\alpha]_\approx\sqsubseteq[\beta]_\approx$. 
\item Покажите, что $(\sqsubseteq^*)$ является отношением предпорядка, а $(\sqsubseteq)$ --- отношением
порядка.
\item Покажите, что $F/\!\!\approx$ с отношением $\sqsubseteq$ является: (а) решёткой, (б) импликативной
решёткой, (в) алгеброй Гейтинга.
\end{enumerate}

\section*{Домашнее задание №5: <<Алгебры Гейтинга и Линденбаума, часть 2>>}

\begin{enumerate}
\item Рассмотрим некоторую модель Крипке на множестве миров $W$ с отношением
порядка $\sqsubseteq$. Рассмотрим топологическое пространство
$\langle W, \{s\subseteq W \mid a \in s \;\textrm{и}\; a \sqsubseteq b \;\textrm{влечёт}\; b \in s\}\rangle$;
иными словами, открытые множества --- все множества, содержащие с элементом все большие его.
Рассмотрим алгебру Гейтинга, построенную по данному топологическому пространству:
элементы алгебры --- все открытые множества, упорядоченные включением.
За $\llbracket P \rrbracket$ возьмём множество всех миров, на которых переменная $P$ вынуждена
(поясните, почему это --- открытое множество).
Тогда покажите, что $W_k \Vdash \alpha \vee \beta$ (а также: $\alpha\&\beta$, $\alpha\rightarrow\beta$,
$\neg\alpha$) тогда и только тогда, когда
$W_k \in \llbracket \alpha \rrbracket \cup \llbracket \beta \rrbracket$
(соответственно: $\llbracket\alpha\rrbracket\cap\llbracket \beta \rrbracket$,
$\mathrm{int}(\mathrm{c}(\llbracket\alpha\rrbracket)\cup\llbracket \beta \rrbracket)$,
$\mathrm{int}(\mathrm{c}(\llbracket\alpha\rrbracket))$).
С использованием этого восполните все пробелы в доказательстве 
того, что модели Крипке --- частный случай алгебр Гейтинга.
\item Из общего определения, данного на лекции, на основе операций в алгебре Гейтинга $A$ 
определите формально операции $(+)$, $(\cdot)$, $(\rightarrow)$, $(\sim)$ в $\Gamma(A)$.
\item Постройте опровергающие модели Крипке для следующих формул:
$P\vee\neg P$, $((P\rightarrow Q)\rightarrow P)\rightarrow P$, 
$(P\rightarrow Q)\vee(P\rightarrow\neg Q)$
\item Будем рассматривать модели Крипке, в которых отношения между мирами образуют дерево
(у двух миров не бывает одного и того же потомка). Укажите формулу, для которой не 
существует опровергающей модели Крипке с глубиной дерева меньше $2$, $3$, $n$.
\item Покажите, что любая импликативная решётка является дистрибутивной решёткой.
\item Покажите следующие свойства алгебр Гейтинга:
\begin{enumerate}
\item При любых $a$ и $b$ выполнено $a\cdot (a\rightarrow b) \le b$.
\item При любых $a$, $b$ и $c$ верно, что $a\cdot c \le b$ влечёт $c \le a \rightarrow b$.
\item При любых $a$ и $b$ верно, что $a \le b$ выполнено тогда и только тогда, когда $a \rightarrow b = 1$.
\item При любых $a$ и $b$ верно, что $b \le a \rightarrow b$
\item При любых $a$, $b$ и $c$ выполнено $a\rightarrow b \le (a\rightarrow (b \rightarrow c)) \rightarrow (a\rightarrow c)$
\item При любых $a$, $b$ и $c$ выполнено $a\rightarrow c \le (b\rightarrow c) \rightarrow (a+b \rightarrow c)$
\end{enumerate}
\item Пользуясь предыдущими пунктами, покажите, что алгебры Гейтинга являются 
корректными моделями ИИВ.
\end{enumerate}

\section*{Домашнее задание №6: <<Исчисление предикатов>>}

\begin{enumerate}
\item (Вдогонку к заданию №5) В предыдущем дз было доказано, что 
при любых $a$, $b$ и $c$ верно, что $a\cdot c \le b$ влечёт 
$c \le a \rightarrow b$. Справедливо ли обратное утверждение: 
$c \le a \rightarrow b$ всегда влечёт $a\cdot c \le b$? Докажите его,
либо предложите контрпример.

\item Предложите формулы $\phi$ (и $\psi$ при необходимости) 
и модель $M$ для исчисления предикатов (формулы и модели могут быть 
разными для каждого случая), такие, что:
\begin{enumerate}
\item При нарушении ограничений на свободу для подстановки некорректна 
аксиома 11: $$\llbracket(\forall x.\phi)\rightarrow(\phi[x := \theta])\rrbracket_M = \mbox{Л}$$
\item При нарушении ограничений некорректна аксиома 12:
$$\llbracket(\phi[x := \theta])\rightarrow(\exists x.\phi)\rrbracket_M = \mbox{Л}$$
\item При нарушении ограничений на вхождение переменных некорректно правило
введения квантора всеобщности: если $\vdash \psi\rightarrow\phi$, то
$$\llbracket \psi\rightarrow\forall x.\phi\rrbracket = \mbox{Л}$$
\item При нарушении ограничений на вхождение переменных некорректно правило
введения квантора существования: если $\vdash \phi\rightarrow\psi$, то
$$\llbracket (\exists x.\phi)\rightarrow\psi\rrbracket = \mbox{Л}$$
\end{enumerate}
\item Докажите, что $(\exists x.\phi)\rightarrow\psi\vdash(\forall x.\phi)\rightarrow\psi$.
\item Докажите, что каковы бы ни были формула $\phi$ и переменная $x$, всегда
выполнено $\phi \vdash \forall x.\phi$.
\item Чтобы доказать теорему о дедукции для исчисления предикатов, 
мы следуем тому же принципу, что и в исчислении высказываний: из 
доказательства $\delta_1, \dots, \delta_n$ строим схему доказательства
$\alpha\rightarrow\delta_1, \dots, \alpha\rightarrow\delta_n$, в которой
затем последовательно заполняем все <<дыры>>.

При заполнении дыр мы разбираемся, как получено текущее высказывание
$\delta_k$ --- является ли оно аксиомой, предположением $\alpha$ или
результатом применения правил.

Если речь идёт про первые два случая, они доказываются идентично исчислению
высказываний. Однако, в исчислении предикатов используются два новых
правила, для которых в исчислении высказываний не было аналогов.
В данном задании требуется построить недостающие доказательства для этих
правил. 

Докажите, что если в условиях теоремы о дедукции для предикатов
мы уже построили из доказательства $\delta_1, \dots, \delta_{k-1}$
доказательство 
$\dots, \alpha\rightarrow\delta_1, \dots, \alpha\rightarrow\delta_{k-1}$, то:
\begin{enumerate}
\item если $\delta_k$ получено по правилу введения всеобщности, 
мы можем достроить недостающие шаги и доказать $\alpha\rightarrow\delta_k$;
\item то же справедливо для правила введения существования.
\end{enumerate}

\item Рассмотрим следующие четыре формулы: $\forall x.\forall y.\phi$,
$\forall x.\exists y.\phi$, $\exists x.\forall y.\phi$, $\exists x.\exists y.\phi$.
Какие из них следуют из каких? Для каждой пары предложите либо доказательство
в исчислении предикатов, либо контрпример.
\item Рассмотрим формулы $\exists x.\forall y.\phi$ и $\forall y.\exists x.\phi$.
Следует ли какая-нибудь из этих формул из другой?
Для каждой пары предложите либо доказательство в исчислении предикатов, 
либо контрпример.

\end{enumerate}

\section*{Домашнее задание №7: Теорема Гёделя о полноте}

Для доказательства теоремы Гёделя о полноте нам потребуется для произвольной формулы $F$ уметь находить такую формулу $G$, что  $F \vdash G$, и в $G$ все кванторы находятся снаружи, т.е. например $\forall x\exists z\forall y (P(x, f(y)) \rightarrow H(z, g(x, y, z)))$ --- подходящий нам вид. Приведение к такому виду мы будем делать в три этапа.
\begin{enumerate}
	\item На первом этапе выкинем все импликации, для этого докажем следующую лемму:
    \begin {enumerate}
		\item $\phi \rightarrow \psi \vdash \neg \phi \vee \psi$
    \end{enumerate}
q
    \item На втором этапе научимся строить доказательство $F \vdash F'$, где в $F'$ знак отрицания может находиться только непосредственно перед предикатом. Здесь нам потребуется доказать следующую парочку лемм:
  \begin{enumerate}
      \item $\neg(\phi \vee \psi) \vdash (\neg \phi) \wedge (\neg \psi)$
      \item $\neg(\phi \wedge \psi) \vdash (\neg \phi) \vee (\neg \psi)$
      \item $\neg\neg \phi \vdash \phi$
      \item $\neg(\exists x.\phi) \vdash \forall x.\neg\phi$
      \item $\neg(\forall x.\phi) \vdash \exists x.\neg\phi$
  \end{enumerate}

  \item На последнем этапе вынесем кванторы наружу. Для этого нам потребуется ещё несколько лемм.
  \textit{Замечание: здесь мы считаем, что если переменная $x$ под квантором, то она не входит свободно во вторую часть формулы. Например: если формула имеет вид $(\forall x.\phi) \vee \psi$, то мы всегда можем преобразовать её в формулу $(\forall y.\phi[x:=y]) \vee \psi$, где $y$ не входит свободно в $\psi$}
  \begin{enumerate}
      \item $(\exists x.\phi) \vee \psi \vdash \exists x.(\phi \vee \psi)$
      \item $(\forall x.\phi) \vee \psi \vdash \forall x.(\phi \vee \psi)$
      \item $(\exists x.\phi) \wedge \psi \vdash \exists x.(\phi \wedge \psi)$
      \item $(\forall x.\phi) \wedge \psi \vdash \forall x.(\phi \wedge \psi)$

      \item $\phi \vee (\exists x.\psi) \vdash \exists x.(\phi \vee \psi)$
      \item $\phi \vee (\forall x.\psi) \vdash \forall x.(\phi \vee \psi)$
      \item $\phi \wedge (\exists x.\psi) \vdash \exists x.(\phi \wedge \psi)$q
      \item $\phi \wedge (\forall x.\psi) \vdash \forall x.(\phi \wedge \psi)$
  \end{enumerate}


\end{enumerate}

\section*{Домашнее задание №8: Формальная арифметика и рекурсивные функции}

\begin{enumerate}
\item Докажите, что следующие функции являются примитивно-рекурсивными: сложение, умножение,
ограниченное вычитание единицы (ограниченное потому, что $0-1=0$), ограниченное вычитание,
целочисленное деление, остаток от деления, частичный логарифм 
($\mathrm{plog}_a(x)$ --- это $\max \{t \in \mathbb{N}_0 \mid x \mathop{\raisebox{-2pt}{\vdots}} a^t \}$).

\item Постройте в формальной арифметике доказательства $2+2=4$, $2 \cdot 2 = 4$, $a=a$, 
$a+1=a'$, $\exists x.a+x=a$, $\neg\exists x.1+x=0$.
\end{enumerate}

\section*{Домашнее задание №9: Формальная арифметика, гёделева нумерация}

\begin{enumerate}

\item
Пусть $a \le b$ обозначает $\exists c.a+c = b$. Тогда в формальной арифметике докажите следующие формулы:
\begin{enumerate}
\item $a=b \rightarrow a+c=b+c$
\item $s = r \rightarrow t \cdot s = t \cdot r$
\item $a=c \rightarrow a \le c$
\item $a \le c \rightarrow a \le c'$
\item $a=b \& c=0 \rightarrow a+c=b+0$
\item $a=b \& c=\overline{1} \rightarrow a+c=b+\overline{1}$
\item $a=b \& c=d \rightarrow a+c=b+d$
\item $s + t = r + t \rightarrow s = r$
\item $t+s=0 \rightarrow t = 0 \& s = 0$
\item $t+s=\overline{1} \rightarrow (t=0 \& s=\overline{1}) \vee (t=\overline{1} \& s = 0)$
\item $(\neg t = 0) \rightarrow (s \cdot t = 0 \rightarrow s = 0)$
\end{enumerate}

\item Напишите рекурсивную функцию \verb!Pair!, строящую по двум числам $a$ и $b$ их упорядоченную 
пару $2^a \cdot 3^b$.

\item Напишите рекурсивную функцию, берущую первый и второй элемент упорядоченной пары:
$fst(2^a \cdot 3^b) = a$, $snd(2^a \cdot 3^b) = b$.

\item Напишите рекурсивную функцию \verb!Num!, строящую по натуральному числу $n$ гёделев номер
его записи в формальной арифметике ($\ulcorner\overline{n}\urcorner$).

\item Напишите рекурсивную функцию, вычисляющую длину строчки по её гёделеву номеру.

\end{enumerate}

\end{document}