Банк задач по математике

Задача II.3.1

Построить выводы секвенций в ИС:

?

(а)

$\vdash (A \supset A)$ ;

(б)

$(A \supset B), (B \supset C) \vdash (A \supset C)$ ;

(в)

$\vdash (\neg \neg A \equiv A)$ ;

(г)

$(A \supset (B \supset C)), (A \supset B), A \vdash C$ ;

(д)

$(A \supset B), \neg B \vdash \neg A$ ;

(е)

$A, \neg B \vdash \neg (A \supset B)$ .

Задача II.3.2

Доказать правило подстановки в ИС: если выводима секвенция $A_{1}, \ldots , A_{n} \vdash B$ , $P$ --- переменная и $C$ --- любая формула, то выводима секвенция $A_{1}(P \backslash C), \ldots , A_{n}(P \backslash C) \vdash B(P \backslash C)$ .

?

Задача II.3.3

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

?

(а)

$\dfrac {\Gamma_{1} \vdash A; \ \Gamma_{2}, A \vdash B}{\Gamma_{1}, \Gamma_{2} \vdash B}$ (сечение);

(б)

$\dfrac {\Gamma , A, B \vdash C}{\Gamma , (A \& B) \vdash C}$ (объединение посылок);

(в)

$\dfrac {\Gamma , (A \& B) \vdash C}{\Gamma , A, B \vdash C}$ (расщепление посылок);

(г)

$\dfrac {\Gamma , A \vdash C; \ \Gamma , B \vdash C}{\Gamma , (A \vee B) \vdash C}$ (разбор случаев);

(д)

$\dfrac {\Gamma , A \vdash B}{\Gamma , \neg B \vdash \neg A}$ (контрапозиция);

(е)

$\dfrac {\Gamma , \neg B \vdash \neg A}{\Gamma , A \vdash B}$ (доказательство от противного);

(ж)

$\dfrac {A_{1}, \ldots , A_{n} \vdash B}{\vdash ((A_{1} \& \ldots \& A_{n}) \supset B)}$ (введение и $\supset$ );

(з)

$\dfrac {\vdash ((A_{1} \& \ldots \& A_{n}) \supset B)}{A_{1}, \ldots , A_{n} \vdash B}$ (удаление и $\neg$ ).

Задача II.3.4

Доказать, что если правило $\dfrac {\Gamma_{1} \vdash A}{\Gamma_{2} \vdash A}$ допустимо в ИС для любой формулы $A$ , то правило $\dfrac {\Gamma_{1} \vdash }{\Gamma_{2} \vdash }$ допустимо в ИС.

?

Задача II.3.5

Вывести в ИС следующие секвенции:

?

(а)

$(A \supset B), (B \supset C) \vdash (A \supset C)$ ;

(б)

$(A \supset (B \supset C)) \vdash (B \supset (A \supset C))$ ;

(в)

$(A \supset (B \supset C)) \vdash ((A \& B) \supset C)$ ;

(г)

$((A \& B) \supset C) \vdash (A \supset (B \supset C))$ ;

(д)

$(A \supset B) \vdash ((B \supset C) \supset (A \supset C))$ ;

(е)

$(A \supset B) \vdash ((C \supset A) \supset (C \supset B))$ ;

(ж)

$(A \supset B) \vdash ((C \& A) \supset (C \& B))$ ;

(з)

$(A \supset B) \vdash ((A \& C) \supset (B \& C))$ ;

(и)

$(A \supset B) \vdash ((A \vee C) \supset (B \vee C))$ ;

(к)

$(A \supset B) \vdash ((C \vee A) \supset (C \vee B))$ ;

(л)

$\neg A \vdash (A \supset B)$ ;

(м)

$A \vdash (\neg A \supset B)$ ;

(н)

$B \vdash (A \supset B)$ ;

(о)

$(A \supset B) \vdash (\neg B \supset \neg A)$ ;

(п)

$(A \supset \neg B) \vdash (B \supset \neg A)$ ;

(р)

$(\neg A \supset B) \vdash (\neg B \supset A)$ ;

(с)

$(\neg A \supset \neg B) \vdash (B \supset A)$ .

Задача II.3.6

(а)(б)(в)

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

?

(а)

$\dfrac {\Gamma , A \vdash B; \ \Gamma , B \vdash A}{\Gamma \vdash (A \equiv B)}$ ;

(б)

$\dfrac {\Gamma \vdash (A \equiv B)}{\Gamma , A \vdash B}$ ;

(в)

$\dfrac {\Gamma \vdash (A \equiv B)}{\Gamma , B \vdash A}$ .

Задача II.3.7

Вывести в ИС следующие секвенции:

?

(а)

$(A \supset B), (B \supset A) \vdash (A \equiv B)$ ;

(б)

$(A \equiv B) \vdash (A \supset B)$ ;

(в)

$(A \equiv B) \vdash (B \supset A)$ ;

(г)

$(A \equiv B), A \vdash B$ ;

(д)

$\vdash (A \equiv A)$ ;

(е)

$(A \equiv B), (B \equiv C) \vdash (A \equiv C)$ ;

(ж)

$(A \equiv B) \vdash (B \equiv A)$ ;

(з)

$(A \equiv B) \vdash (\neg A \equiv \neg B)$ ;

(и)

$(A \equiv B) \vdash ((A \& C) \equiv (B \& C))$ ;

(к)

$(A \equiv B) \vdash ((C \& A) \equiv (C \& B))$ ;

(л)

$(A \equiv B) \vdash ((A \vee C) \equiv (B \vee C))$ ;

(м)

$(A \equiv B) \vdash ((C \vee A) \equiv (C \vee B))$ ;

(н)

$(A \equiv B) \vdash ((A \supset C) \equiv (B \supset C))$ ;

(о)

$(A \equiv B) \vdash ((C \supset A) \equiv (C \supset B))$ .

Задача II.3.8

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

?

Задача II.3.9

Вывести в ИС следующие секвенции:

?

(а)

$\vdash ((A \& B) \equiv (B \& A))$ ;

(б)

$\vdash ((A \vee B) \equiv (B \vee A))$ ;

(в)

$\vdash ((A \& (B \& C)) \equiv ((A \& B) \& C))$ ;

(г)

$\vdash ((A \vee (B \vee C)) \equiv ((A \vee B) \vee C))$ ;

(д)

$\vdash ((A \& (B \vee C)) \equiv ((A \& B) \vee (A \& C)))$ ;

(е)

$\vdash ((A \vee (B \& C)) \equiv ((A \vee B) \& (A \vee C)))$ ;

(ж)

$\vdash (\neg (A \& B) \equiv (\neg A \vee \neg B))$ ;

(з)

$\vdash (\neg (A \vee B) \equiv (\neg A \& \neg B))$ ;

(и)

$\vdash ((A \supset B) \equiv (\neg A \vee B))$ ;

(к)

$\vdash (\neg A \vee A)$ ;

(л)

$\vdash ((A \supset B) \vee (B \supset A))$ .

Задача II.3.10

Пусть $A$ --- формула, а $A_{1}$ --- ее к.н.ф. (см. 1). Доказать выводимость в ИС секвенции $\vdash (A \equiv A_{1})$ .

?

Задача II.3.11

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

?

Задача II.3.12

(а)(б)(в)

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

?

(а)

если секвенция $A_{1}, \ldots , A_{n} \vdash B$ выводима в ИС, то формула $((A_{1} \& \ldots \& A_{n}) \supset B)$ тождественно истинна;

(б)

если секвенция $\vdash B$ выводима в ИС, то формула $B$ тождественно истинна;

(в)

если секвенция $A_{1}, \ldots , A_{n} \vdash$ выводима в ИС, то формула $\neg (A_{1} \& \ldots \& A_{n})$ тождественно истинна.

Задача II.3.13

Доказать, что секвенция $\vdash A$ выводима в ИС тогда и только тогда, когда $A$ тождественно истинна (теорема о полноте ИС).

?

Задача II.3.14

Выводимы ли в ИС следующие секвенции:

?

(а)

$\vdash ((P \vee Q) \supset (P \& R))$ ;

(б)

$\vdash (((P \supset Q) \supset Q) \supset P)$ ;

(в)

$\vdash (((P \supset Q) \supset Q) \supset Q)$ ;

(г)

$\vdash (\neg (P \vee \neg P) \supset (P \vee \neg P))$ ;

(д)

$P \vdash \neg (P \supset \neg P)$ ;

(е)

$(P \supset Q) \vdash (Q \supset P)$ ?

Задача II.3.15

Доказать интерполяционную теорему для ИС: если доказуема секвенция $A \vdash B$ и недоказуемы секвенции $A \vdash$ и $\vdash B$ , то существует формула $C$ , все переменные которой входят как в $A$ , так и в $B$ , такая, что доказуемы секвенции $A \vdash C$ и $C \vdash B$ (такая формула $C$ называется интерполянтом).

?

Задача II.3.16

(а)(б)

Построить интерполянты (см. задачу II.3.15) для следующих секвенций:

?

(а)

$\neg (\neg Q \vee R) \vdash (P \supset Q)$ ;

(б)

$\neg (P \supset \neg (Q \& S)) \vdash ((S \supset (P \supset R)) \supset R)$ .

Задача II.3.17

(а)(б)(в)

Являются ли выводами в ИВ следующие последовательности формул:

?

(а)

$(P \supset (P \vee Q))$ ;

(б)

$(P \supset (P \vee Q))$ , $((P \supset (P \vee Q)) \supset (P \supset (P \supset (P \vee Q))))$ , $(P \supset (P \supset (P \vee Q)))$ ;

(в)

$(P \supset (Q \supset P))$ , $((P \supset (P \vee Q)) \supset Q)$ , $Q$ ?

Задача II.3.18

(а)(б)(в)

Построить выводы следующих формул в ИВ:

?

(а)

$(P \supset P)$ ;

(б)

$((P \vee P) \supset P)$ ;

(в)

$(P \supset \neg \neg P)$ .

Задача II.3.19

Доказать, что если $A$ выводима в ИВ, то $A(P \backslash B)$ выводима в ИВ для любых переменной $P$ и формулы $B$ (правило подстановки).

?

Задача II.3.20

(а)(б)

Найти минимальное множество $\Gamma$ так, чтобы следующая последовательность была выводом в ИВ из $\Gamma$ :

?

(а)

$(P \supset (Q \supset R))$ , $P$ , $(Q \supset R)$ , $Q$ , $R$ ;

(б)

$((P \supset \neg \neg Q) \supset (\neg Q \supset \neg P))$ , $(P \supset \neg \neg Q)$ , $(\neg Q \supset \neg P)$ , $\neg Q$ , $\neg P$ .

Задача II.3.21

Доказать, что $A \vdash A$ в ИВ.

?

Задача II.3.22

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

?

(а)

$\dfrac {\Gamma \vdash A}{B, \Gamma \vdash A}$ ;

(б)

$\dfrac {B, B, \Gamma \vdash A}{B, \Gamma \vdash A}$ ;

(в)

$\dfrac {\Gamma , A, B, \Gamma_{1} \vdash C}{\Gamma , B, A, \Gamma_{1} \vdash C}$ ;

(г)

$\dfrac {\Gamma \vdash A; \ A, \Gamma_{1} \vdash B}{\Gamma , \Gamma_{1} \vdash B}$ ;

(д)

$\dfrac {A_{1}, \ldots , A_{n} \vdash B}{A_{1}(P \backslash C), \ldots , A_{n}(P \backslash C) \vdash B(P \backslash C)}$ .

Задача II.3.23

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

?

Задача II.3.24

Доказать для ИВ:

?

(а)

$\Gamma , A, B \vdash (A \& B)$ (введение );

(б)

$\Gamma , A \vdash (A \vee B)$ (введение $\vee$ );

(в)

$\Gamma , B \vdash (A \vee B)$ (введение $\vee$ );

(г)

$\dfrac {\Gamma , A \vdash B; \ \Gamma , A \vdash \neg B}{\Gamma \vdash \neg A}$ (введение $\neg$ );

(д)

$\Gamma , (A \& B) \vdash A$ (удаление );

(е)

$\Gamma , (A \& B) \vdash B$ (удаление );

(ж)

$\dfrac {\Gamma , A \vdash C; \ \Gamma , B \vdash C}{\Gamma , (A \vee B) \vdash C}$ (удаление $\vee$ );

(з)

$\Gamma , \neg \neg A \vdash A$ (удаление $\neg$ ).

Задача II.3.25

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

?

Задача II.3.26

Доказать, что в ИВ:

?

(а)

$\vdash (A \equiv A)$ ;

(б)

$(A \equiv B) \vdash (B \equiv A)$ ;

(в)

$(A \equiv B), (B \equiv C) \vdash (A \equiv C)$ ;

(г)

$(A \equiv B) \vdash (\neg A \equiv \neg B)$ ;

(д)

$(A \equiv B) \vdash ((A \& C) \equiv (B \& C))$ ;

(е)

$(A \equiv B) \vdash ((C \& A) \equiv (C \& B))$ ;

(ж)

$(A \equiv B) \vdash ((A \vee C) \equiv (B \vee C))$ ;

(з)

$(A \equiv B) \vdash ((C \vee A) \equiv (C \vee B))$ ;

(и)

$(A \equiv B) \vdash ((A \supset C) \equiv (B \supset C))$ ;

(к)

$(A \equiv B) \vdash ((C \supset A) \equiv (C \supset B))$ .

Задача II.3.27

Пусть $A$ --- формула, $B$ --- подформула формулы $A$ , $A_{1}$ --- результат замены некоторого вхождения $B$ в $A$ на формулу $B_{1}$ . Доказать теорему о замене в ИВ:

(B \equiv B_{1}) \vdash (A \equiv A_{1}).

?

Задача II.3.28

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

?

(а)

$((A \& (B \& C)) \equiv ((A \& B) \& C))$ ;

(б)

$((A \vee (B \vee C)) \equiv ((A \vee B) \vee C))$ ;

(в)

$((A \& B) \equiv (B \& A))$ ;

(г)

$((A \vee B) \equiv (B \vee A))$ ;

(д)

$((A \& (B \vee C)) \equiv ((A \& B) \vee (A \& C)))$ ;

(е)

$((A \vee (B \& C)) \equiv ((A \vee B) \& (A \vee C)))$ ;

(ж)

$((A \& A) \equiv A)$ ;

(з)

$((A \vee A) \equiv A)$ ;

(и)

$((A \vee (A \& B)) \equiv A)$ ;

(к)

$((A \& (A \vee B)) \equiv A)$ ;

(л)

$(\neg \neg A \equiv A)$ ;

(м)

$\neg (A \& \neg A)$ ;

(н)

$(A \vee \neg A)$ ;

(о)

$((A \& B) \equiv \neg (\neg A \vee \neg B))$ ;

(п)

$((A \vee B) \equiv \neg (\neg A \& \neg B))$ ;

(р)

$((A \supset B) \equiv \neg (A \& \neg B))$ ;

(с)

$((A \supset B) \equiv (\neg A \vee B))$ ;

(т)

$((A \& B) \equiv \neg (A \supset \neg B))$ ;

(у)

$((A \vee B) \equiv (\neg A \supset B))$ ;

(ф)

$(\neg (A \& B) \equiv (\neg A \vee \neg B))$ ;

(х)

$(\neg (A \vee B) \equiv (\neg A \& \neg B))$ ;

(ц)

$\vdash (\neg \neg \neg A \equiv \neg A)$ .

Задача II.3.29

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

?

Задача II.3.30

(а)(б)(в)

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

?

(а)

если секвенция $A_{1}, \ldots , A_{n} \vdash B$ выводима в ИС, то $A_{1}, \ldots , A_{n} \vdash B$ в ИВ;

(б)

если секвенция $A_{1}, \ldots , A_{n} \vdash$ выводима в ИС, то $A_{1}, \ldots , A_{n} \vdash (B \& \neg B)$ в ИВ;

(в)

если секвенция $\vdash B$ выводима в ИС, то формула $B$ выводима в ИВ.

Задача II.3.31

(а)(б)

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

?

(а)

все аксиомы ИВ тождественно истинны;

(б)

все выводимые в ИВ формулы тождественно истинны.

Задача II.3.32

Доказать теорему о полноте ИВ: каждая тождественно истинная формула выводима в ИВ.

?

Задача II.3.33

Найти такие формулы $A$ и $B$ , что из выводимости в ИВ формулы $A$ следует выводимость $B$ , но неверно, что $A \vdash B$ .

?

Задача II.3.34

Пусть $A$ --- формула и $P_{1}, \ldots , P_{n}$ --- все ее переменные. Доказать, что если $A$ невыводима в ИВ, то существуют такие формулы $B_{1}, \ldots , B_{n}$ , что в ИВ выводима формула $\neg A(P_{1} \backslash B_{1}, \ldots , P_{n} \backslash B_{n})$ .

?

Задача II.3.35

(а)(б)(в)

Пусть $A$ и $B$ --- формулы. Положим

A \approx B \rightleftharpoons \vdash (A \equiv B) \text{ в ИВ}; \qquad \left\| A\right\| \rightleftharpoons \left\{ B \mid A \approx B\right\} .

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

?

(а)

$\approx$ есть отношение эквивалентности на множестве $F$ всех формул;

(б)

фактор-множество $F / {\approx } \rightleftharpoons \left\{ \left\| A\right\| \mid A \in F\right\}$ есть булева алгебра, где $\left\| A\right\| \leq \left\| B\right\| \Leftrightarrow \vdash (A \supset B)$ в ИВ (эта алгебра называется алгеброй Линденбаума для ИВ);

(в)

$A$ выводима в ИВ тогда и только тогда, когда $\left\| A\right\|$ есть наибольший элемент 1 алгебры $F / {\approx }$ .

Задача II.3.36

Пусть $\mathfrak {B}$ --- булева алгебра. Поставим ей в соответствие логическую матрицу $\langle \mathfrak {B}; \left\{ 1\right\} , \& , \vee , \supset , \neg \rangle$ , где $x \& y = x \cap y$ , $x \vee y = x \cup y$ , $x \supset y = -x \cup y$ , $\neg x = -x$ . Доказать, что $A$ выводима в ИВ тогда и только тогда, когда $A$ общезначима во всех логических матрицах, соответствующих булевым алгебрам.

?

Задача II.3.37

(а)(б)

?

(а)

Пусть $T$ --- ультрафильтр на алгебре Линденбаума $F / {\approx }$ (см. задачу II.3.35). Для произвольной переменной $P$ положим значение $P$ равным $\text{и}$ , если $\left\| P\right\| \in T$ , и $\text{л}$ в противном случае. Доказать, что для любой формулы $A$

A \in T \Leftrightarrow A \text{ истинна при этих значениях переменных}.

(б)

Вывести из (а) теорему о полноте исчисления ИВ (см. задачу II.3.32).

Задача II.3.38

Пусть $A$ --- формула, $\Delta$ --- система формул, $M$ --- логическая матрица. Доказать, что если все формулы из $\Delta$ общезначимы в $M$ и непосредственное следствие общезначимых в $M$ формул есть общезначимая в $M$ формула, а формула $A$ не общезначима в $M$ , то $A$ независима от $\Delta$ .

?

Задача II.3.39

Пусть $M = \left\{ 0, 1, 2\right\}$ , $D = \left\{ 0\right\}$ , $x \& y = \max \left\{ x, y\right\}$ , $x \vee y = \min \left\{ x, y\right\}$ , $x \supset y = \max \left\{ 0, y - x\right\}$ , $\neg x = 2 - x$ . Доказать, что формула

A = ((P \supset (Q \supset R)) \supset ((P \supset Q) \supset (P \supset R)))

не зависит от $\Delta$ , где $\Delta = \left\{ (P \supset (Q \supset P)), ((\neg P \supset \neg Q) \supset (Q \supset P))\right\}$ , используя логическую матрицу $\langle M; D, \& , \vee , \supset , \neg \rangle$ .

?

Задача II.3.40

Доказать независимость схем исчисления ИВ.

?

Задача II.3.41

(а)(б)(в)

Пусть $L$ --- исчисление высказываний со схемами аксиом:

L1. $(A \supset (B \supset A))$ ,

L2. $((A \supset B) \supset ((A \supset (B \supset C)) \supset (A \supset C)))$ ,

L3. $((\neg A \supset \neg B) \supset (B \supset A))$

и правилом вывода $\dfrac {A; \ (A \supset B)}{B}$ .

?

(а)

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

(б)

Доказать теорему дедукции для $L$ .

(в)

Положим $(A \& B) = \neg (A \supset \neg B)$ , $(A \vee B) = (\neg A \supset B)$ . Доказать, что все выводимые в ИВ формулы выводимы в $L$ .

Задача II.3.42

(а)(б)

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

?

(а)

все выводимые в ИИВ формулы выводимы в ИВ;

(б)

$(\neg \neg P \supset P)$ , $(P \vee \neg P)$ невыводимы в ИИВ.

Задача II.3.43

Для исчисления ИИВ доказать теорему о дедукции: если $\Gamma , A \vdash_{\text{И}} B$ , то $\Gamma \vdash_{\text{И}} (A \supset B)$ .

?

Задача II.3.44

(а)(б)(в)(г)

Пусть ИИС --- исчисление секвенций, которое отличается от ИС отсутствием правила 11. Доказать, что:

?

(а)

если формула $A$ выводима в ИИВ, то секвенция $\vdash A$ выводима в ИИС;

(б)

если секвенция $A_{1}, \ldots , A_{n} \vdash B$ выводима в ИИС, то имеем $A_{1}, \ldots , A_{n} \vdash_{\text{И}} B$ ;

(в)

если секвенция $A_{1}, \ldots , A_{n} \vdash$ выводима в ИИС, то имеем $A_{1}, \ldots , A_{n} \vdash_{\text{И}} (B \& \neg B)$ ;

(г)

если секвенция $\vdash B$ выводима в ИИС, то формула $B$ выводима в ИИВ.

Задача II.3.45

(а)(б)(в)

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

?

(а)

$\vdash_{\text{И}} (A \supset \neg \neg A)$ ;

(б)

$\vdash_{\text{И}} \neg \neg (\neg \neg A \supset A)$ ;

(в)

$\neg \neg A, \neg \neg (A \supset B) \vdash_{\text{И}} \neg \neg B$ .

Задача II.3.46

Доказать, что если формула $A$ выводима в ИВ, то формула $\neg \neg A$ выводима в ИИВ.

?

Задача II.3.47

(а)(б)

Пусть $M_{n} = \left\{ 0, 1, \ldots , n\right\}$ , $D = \left\{ 0\right\}$ , $x \& y = \max (x, y)$ , $x \vee y = \min (x, y)$ ,

x \supset y = \begin{cases} 0, & \text{если } x \geq y, \\ y, & \text{если } x < y, \end{cases} \qquad \neg x = \begin{cases} 0, & \text{если } x = n, \\ n, & \text{если } x < n. \end{cases}

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

?

(а)

все выводимые в ИИВ формулы общезначимы в $M_{n} = \langle M; D, \& , \vee , \supset , \neg \rangle$ ( $n = 1, 2, \ldots$ ).

(б)

формулы

A_{n} = ((P_{1} \equiv P_{2}) \vee \ldots \vee (P_{1} \equiv P_{n + 1}) \vee \ldots \vee (P_{n} \equiv P_{n + 1}))

невыводимы в ИИВ ( $n = 1, 2, \ldots$ ).

Задача II.3.48

Пусть $M = \langle M; D, \& , \vee , \supset , \neg \rangle$ --- логическая матрица такая, что множество общезначимых в $M$ формул совпадает с множеством формул, выводимых в ИИВ. Доказать, что множество $M$ бесконечно.

?

Исчисления высказываний