Исчисления предикатов

Доказать, что любая секвенция, выводимая в ИС, выводима в ИПС.

Пусть $A_{1}, \ldots , A_{n}, A$ --- формулы ИС, $B$ --- формула ИПС, $A'_{1}, \ldots , A'_{n}, A'$ --- формулы, полученные из $A_{1}, \ldots , A_{n}, A$ в результате подстановки $B$ вместо пропозициональной переменной $P$. Доказать, что если секвенция $A_{1}, \ldots , A_{n} \vdash A$ выводима в ИС, то $A'_{1}, \ldots , A'_{n} \vdash A'$ выводима в ИПС.

Доказать, что правила из задач II.3.3 и II.3.6 допустимы в ИПС.

Пусть $y$ не входит свободно в $A(x)$, $y$ свободно для $x$ в $A(x)$, $A(y)$ получается из $A(x)$ заменой всех свободных вхождений $x$ на $y$. Построить выводы в ИПС секвенций:

Пусть $y$ свободно для $x$ в формулах $A_{1}(x), \ldots , A_{n}(x), B(x)$. Доказать, что если в ИПС выводима $A_{1}(x), \ldots , A_{n}(x) \vdash B(x)$, то выводима $A_{1}(y), \ldots , A_{n}(y) \vdash B(y)$.

Пусть $A$ не содержит свободных вхождений $x$. Доказать выводимость в ИПС секвенций:

Доказать, что в ИПС выводимы секвенции:

Пусть $A$ --- формула, $B$ --- подформула формулы $A$, $A_{1}$ --- результат замены некоторого вхождения $B$ в $A$ на формулу $B_{1}$, $x_{1}, \ldots , x_{n}$ --- все свободные переменные формул $A$ и $A_{1}$. Доказать, что в ИПС выводима секвенция $\forall x_{1}, \ldots , \forall x_{n} (B \equiv B_{1}) \vdash (A \equiv A_{1})$ (теорема о замене для ИПС).

Доказать, что для любой формулы $A$ существует пренексная нормальная форма $A'$ такая, что $\vdash (A \equiv A')$ выводима в ИПС.

Найти пренексную нормальную форму для следующих формул:

Пусть $A$ --- формула, построенная из атомных формул и их отрицаний с помощью , $\vee$ и кванторов $\forall$ и $\exists$ по любым переменным. Пусть $A^{+}$ --- результат одновременной замены в $A$ на $\vee$, $\vee$ на , $\forall$ на $\exists$, $\exists$ на $\forall$, атомных формул их отрицаниями. Доказать, что в ИПС выводима секвенция $\vdash (A^{+} \equiv \neg A)$.

Пусть $A$ --- формула, построенная из атомных формул и их отрицаний с помощью , $\vee$ и кванторов $\forall$ и $\exists$ по любым переменным. Пусть $A'$ --- результат одновременной замены в $A$ на $\vee$, $\vee$ на , $\forall$ на $\exists$, $\exists$ на $\forall$, атомных формул их отрицаниями. Доказать, что в ИПС:

Показать, что квазивывод в ИП из пустого множества формул есть вывод в ИП.

Являются ли выводами в ИП последовательности:

Каким требованиям должна удовлетворять формула $A(x)$, чтобы следующая последовательность была выводом в ИП:

Доказать, что если $A_{1}, \ldots , A_{n}, A$ --- формулы ИВ, $B$ --- формула ИП, $P$ --- пропозициональная переменная и $A_{1}, \ldots , A_{n} \vdash A$ в ИВ, то $A_{1}(P \backslash B), \ldots , A_{n}(P \backslash B) \vdash A(P \backslash B)$ в ИП.

Построить выводы формул в ИП:

Является ли выводом из $\Gamma = \left\{ (C \supset A(x))\right\}$ в ИП, где $C$ не содержит свободных вхождений $x$, последовательность формул:

Построить выводы из $\Gamma = \left\{ \forall x (A(x) \supset B(x))\right\}$ в ИП следующих формул:

Доказать, что следующие правила допустимы в ИП:

Доказать теорему о дедукции в ИП: если $\Gamma , A \vdash B$, то $\Gamma \vdash (A \supset B)$.

Доказать, что если в ИП $\Gamma \vdash A$ и $\Gamma , A \vdash B$, то $\Gamma \vdash B$.

Доказать, что утверждение задачи II.3.24 из 3 справедливо в ИП.

Доказать следующие правила:

Доказать, что формула $A(x)$ выводима в ИП тогда и только тогда, когда выводима формула $\forall x \, A(x)$.

Пусть $z_{1}, \ldots , z_{n}$ не входят связанно в $A(z_{1}, \ldots , z_{n})$ и в $B(z_{1}, \ldots , z_{n})$ и пусть $A(z_{1}, \ldots , z_{n}) \vdash B(z_{1}, \ldots , z_{n})$ в ИП. Доказать, что существует вывод $B(z_{1}, \ldots , z_{n})$ из $A(z_{1}, \ldots , z_{n})$ в ИП, в который $z_{1}, \ldots , z_{n}$ не входят ни разу в связанном виде.

Пусть $z_{1}, \ldots , z_{n}$ не входят связанно в $A(z_{1}, \ldots , z_{n})$ и в $B(z_{1}, \ldots , z_{n})$; $x_{1}, \ldots , x_{n}$ --- переменные, не входящие связанно в $A(z_{1}, \ldots , z_{n})$ и в $B(z_{1}, \ldots , z_{n})$. Доказать, что

Пусть $\Gamma$ --- множество формул сигнатуры $\sigma$, $A$ --- формула сигнатуры $\sigma$. Доказать, что если $\Gamma \vdash A$ в ИП, то существует вывод $A$ из $\Gamma$ в ИП, состоящий лишь из формул сигнатуры $\sigma$.

Доказать, что если формула $A$ выводима в ИП, то секвенция $\vdash A$ выводима в ИПС.

Доказать, что:

Пусть $A$ --- формула, $B$ --- подформула формулы $A$, $A'$ --- результат замены некоторого вхождения $B$ в $A$ на формулу $B'$. Доказать, что если $\vdash (B \equiv B')$, то $\vdash (A \equiv A')$ (теорема о замене для ИП).

Доказать, что если $\Gamma \vdash A$ в ИП, то $\Gamma \vDash A$.

Доказать, что все выводимые в ИП формулы тождественно истинны.

Доказать, что если множество формул $\Gamma$ выполнимо, то оно непротиворечиво. (Множество $\Gamma$ выполнимо, если существуют алгебраическая система $\mathfrak {M}$ и значения в $\mathfrak {M}$ свободных переменных такие, что все формулы из $\Gamma$ истинны при этих значениях переменных.)

Доказать, что множество формул $\Gamma$ противоречиво тогда и только тогда, когда любая формула выводима в ИП из $\Gamma$.

Доказать, что если множества формул $T_{0}, T_{1}, T_{2}, \ldots$ непротиворечивы и $T_{i} \subseteq T_{i + 1}$ ($i = 0, 1, 2, \ldots$), то $\bigcup_{i \in \mathbb {N}} T_{i}$ --- непротиворечивое множество формул.

Доказать теорему Линденбаума: любое непротиворечивое множество формул $T$ можно расширить до полного непротиворечивого множества той же сигнатуры.

Пусть множество $\Gamma$ формул сигнатуры $\sigma$ полно и удовлетворяет условию: для любой формулы сигнатуры $\sigma$ с одной свободной переменной $x$, если $\Gamma \vdash \exists x \, A(x)$, то $\Gamma \vdash A(t)$ для некоторого замкнутого терма $t$ сигнатуры $\sigma$. Доказать, что:

Пусть множество $\Gamma \cup \left\{ \exists x \, A(x)\right\}$ непротиворечиво. Доказать, что если переменная $y$ не входит в $\Gamma$ и в $\exists x \, A(x)$, то множество $\Gamma \cup \left\{ \exists x \, A(x), A(y)\right\}$ непротиворечиво.

Доказать, что любое непротиворечивое множество предложений выполнимо (теорема о существовании модели).

Доказать теорему Левенгейма--Скулема: любое выполнимое множество предложений выполнимо в некоторой счетной алгебраической системе.

Доказать, что если предложение $A$ невыводимо в ИП, то $\neg A$ выполнимо на натуральных числах.

Доказать, что формула $A$ тождественно истинна тогда и только тогда, когда $A$ выводима в ИП (теорема Гёделя о полноте ИП).

Показать, что если предложение $A$ истинно во всех системах на натуральных числах, то $A$ тождественно истинно.

Доказать, что если предложение $A$ выполнимо в некоторой системе, то $A$ выполнимо на натуральных числах.

Доказать, что если предложение $A$ истинно на всякой системе, на которой истинны формулы счетного множества $\Gamma$, то $\Gamma \vdash A$.

Доказать, что если множество предложений $\Gamma$ счетно и каждое конечное подмножество $\Gamma_{1} \subseteq \Gamma$ выполнимо, то все множество $\Gamma$ выполнимо (локальная теорема Мальцева).

Доказать, что если отрицание любой конъюнкции конечного числа предложений счетного множества $\Gamma$ недоказуемо в ИП, то множество $\Gamma$ выполнимо.

Доказать для любого предложения $A$ и любого счетного множества $\Gamma$

(теорема адекватности).

Доказать, что если $\Gamma$ --- счетное множество предложений и $\Gamma \vdash A$, то $\Gamma_{1} \vdash A$ для некоторого конечного подмножества $\Gamma_{1} \subseteq \Gamma$ (теорема Мальцева о компактности).

Доказать, что для того, чтобы $A$ была выводима в ИП, недостаточно, чтобы $A$ была истинной на всех конечных системах.

Пусть $A$ --- бескванторная формула ИП. Доказать, что $A$ выводима в ИП тогда и только тогда, когда $A$ выводима лишь из аксиом 1--10 по правилу I.

Выводимы ли в ИП формулы: