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

Задача II.1.1

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

Определить, является ли данная последовательность формулой:

?

(а)

$(P_{0} \& P_{1}) P_{2} \neg P_{3}$ ;

(б)

$(P_{0} \& P_{1}) \supset P_{2}$ ;

(в)

$((P_{3} \supset P_{0}) \& \neg P_{0})$ ;

(г)

$(((\neg P_{0}) \supset P_{1}) \supset \neg (P_{2} \vee P_{3}))$ .

Задача II.1.2

(а)(б)

Сколькими способами можно расставить скобки в последовательности, чтобы получилась формула:

?

(а)

$P_{0} \supset \neg P_{1} \vee P_{2} \& P_{0}$ ;

(б)

$P_{1} \supset P_{2} \supset P_{3} \supset \neg P_{1} \supset \neg P_{2}$ ?

Задача II.1.3

(а)(б)

Выписать все подформулы формулы:

?

(а)

$(((P_{0} \supset P_{1}) \& (P_{2} \supset P_{3})) \supset (\neg P_{1} \vee P_{3}))$ ;

(б)

$((P_{0} \supset P_{1}) \supset ((P_{0} \supset \neg P_{1}) \supset \neg P_{1}))$ .

Задача II.1.4

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

?

Задача II.1.5

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

?

Задача II.1.6

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

?

Задача II.1.7

Построить таблицы истинности для следующих формул:

?

(а)

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

(б)

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

(в)

$((P \& (Q \supset P)) \supset \neg P)$ ;

(г)

$(((P \& \neg Q) \supset Q) \supset (P \supset Q))$ ;

(д)

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

(е)

$((P \& (Q \vee \neg P)) \& ((\neg Q \supset P) \vee Q))$ .

Задача II.1.8

(а)(б)(в)

Доказать выполнимость формул:

?

(а)

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

(б)

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

(в)

$((Q \supset (P \& R)) \& \neg ((P \vee R) \supset Q))$ .

Задача II.1.9

Доказать тождественную истинность формул:

?

(а)

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

(б)

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

(в)

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

(г)

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

(д)

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

(е)

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

(ж)

$(P \vee \neg P)$ ;

(з)

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

(и)

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

(к)

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

(л)

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

(м)

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

(н)

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

(о)

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

(п)

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

(р)

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

(с)

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

(т)

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

(у)

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

(ф)

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

(х)

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

Задача II.1.10

При каких значениях переменных $X, Y, Z, U, V, W$ ложны следующие формулы:

?

(а)

$(((X \supset (Y \& Z)) \supset (\neg Y \supset \neg X)) \supset \neg Y)$ ;

(б)

$((X \& Y) \vee (X \& Z) \vee (Y \& Z) \vee (U \& V) \vee (U \& W) \vee (V \& W) \vee (\neg X \& \neg U))$ ;

(в)

$(((X \vee Y) \vee Z) \supset ((X \vee Y) \& (X \vee Z)))$ ;

(г)

$(((X \vee Y) \& ((Y \vee Z) \& (Z \vee X))) \supset ((X \& Y) \& Z))$ ;

(д)

$((X \vee Y) \supset ((\neg X \& Y) \vee (X \& \neg Y)))$ ?

Задача II.1.11

Доказать, что если формула $A$ тождественно истинна, то формула $A(P \backslash B)$ тождественно истинна. (Здесь $P$ --- пропозициональная переменная, а $B$ --- формула.)

?

Задача II.1.12

Доказать, что если формулы $A$ и $(A \supset B)$ тождественно истинны, то формула $B$ тождественно истинна.

?

Задача II.1.13

(а)(б)(в)

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

?

(а)

если формулы $(A \vee B)$ и $(\neg A \vee C)$ тождественно истинны, то формула $(B \vee C)$ тождественно истинна;

(б)

если формулы $(A \vee B)$ , $(A \supset C)$ , $(B \supset D)$ тождественно истинны, то формула $(C \vee D)$ тождественно истинна;

(в)

если формулы $(\neg A \vee B)$ , $(\neg C \vee \neg B)$ тождественно истинны, то формула $(A \supset \neg B)$ тождественно истинна.

Задача II.1.14

Доказать, что $A \sim B$ тогда и только тогда, когда $A \equiv B$ тождественно истинна.

?

Задача II.1.15

(а)(б)(в)

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

?

(а)

$A \sim A$ ;

(б)

$A \sim B \Rightarrow B \sim A$ ;

(в)

( $A \sim B$ и $B \sim C$ ) $\Rightarrow A \sim C$ .

Задача II.1.16

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

Доказать, что из $A_{1} \sim A_{2}$ и $B_{1} \sim B_{2}$ следует:

?

(а)

$\neg A_{1} \sim \neg A_{2}$ ;

(б)

$(A_{1} \& B_{1}) \sim (A_{2} \& B_{2})$ ;

(в)

$(A_{1} \vee B_{1}) \sim (A_{2} \vee B_{2})$ ;

(г)

$(A_{1} \supset B_{1}) \sim (A_{2} \supset B_{2})$ .

Задача II.1.17

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

?

Задача II.1.18

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

?

Задача II.1.19

Доказать эквивалентности:

?

(а)

$(P \& P) \sim P$ ;

(б)

$(P \& Q) \sim (Q \& P)$ ;

(в)

$(P \& (Q \& R)) \sim ((P \& Q) \& R)$ ;

(г)

$(P \& (Q \vee R)) \sim ((P \& Q) \vee (P \& R))$ ;

(д)

$(P \& (Q \vee P)) \sim P$ ;

(е)

$(P \vee P) \sim P$ ;

(ж)

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

(з)

$(P \vee (Q \vee R)) \sim ((P \vee Q) \vee R)$ ;

(и)

$(P \vee (Q \& R)) \sim ((P \vee Q) \& (P \vee R))$ ;

(к)

$(P \vee (Q \& P)) \sim P$ .

Задача II.1.20

Доказать эквивалентности:

?

(а)

$\neg \neg A \sim A$ ;

(б)

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

(в)

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

(г)

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

(д)

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

(е)

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

(ж)

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

(з)

$(A \supset \neg A) \sim \neg A$ ;

(и)

$((A \vee B) \& (A \vee C) \& (B \vee D) \& (C \vee D)) \sim ((A \& D) \vee (B \& C))$ ;

(к)

$(A \& (A \vee C) \& (B \vee C)) \sim ((A \& D) \vee (B \& C))$ ;

(л)

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

(м)

$((A \vee B) \& (B \vee C) \& (C \vee D)) \sim ((A \& C) \vee (B \& C) \vee (B \& D))$ ;

(н)

$((A \vee B \vee C) \& (B \vee C \vee D) \& (C \vee D \vee A)) \sim ((A \& B) \vee (A \& D) \vee (B \& D) \vee C)$ ;

(о)

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

(п)

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

(р)

$(A \vee (\neg A \& B)) \sim (A \vee B)$ .

Задача II.1.21

(а)(б)(в)

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

?

(а)

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

(б)

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

(в)

$(A \equiv B) \sim (B \equiv A)$ .

Задача II.1.22

Доказать, что для любой формулы существует эквивалентная ей формула с тесными отрицаниями, т.е. формула, в которой нет символа $\supset$ и отрицания относятся только к пропозициональным переменным.

?

Задача II.1.23

(а)(б)

Доказать, что для любой формулы существует эквивалентная ей:

?

(а)

конъюнктивная нормальная форма;

(б)

дизъюнктивная нормальная форма.

Задача II.1.24

(а)(б)(в)

Привести к дизъюнктивной и конъюнктивной нормальным формам:

?

(а)

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

(б)

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

(в)

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

Задача II.1.25

Доказать, что если $A$ есть тождественно истинная к.н.ф., то для любого дизъюнкта формулы $A$ существует переменная $P$ такая, что $P$ и $\neg P$ входят в этот дизъюнкт.

?

Задача II.1.26

Доказать, что если $A$ есть тождественно ложная д.н.ф., то для любого конъюнкта формулы $A$ существует переменная $P$ такая, что $P$ и $\neg P$ входят в этот конъюнкт.

?

Задача II.1.27

Пусть $A$ --- формула с тесными отрицаниями (см. задачу II.1.22) и $A_{1}$ получается из $A$ заменой на $\vee$ , $\vee$ на и переменных $A_{i}$ на $\neg A_{i}$ . Доказать, что $A_{1} \sim \neg A$ .

?

Задача II.1.28

Пусть $A$ и $B$ --- формулы с тесными отрицаниями (см. задачу II.1.22) и $A^{*}$ , $B^{*}$ --- формулы, двойственные к $A$ и $B$ соответственно ( $A^{*}$ получается из $A$ заменой на $\vee$ , $\vee$ на ). Доказать, что из $A \sim B$ следует $A^{*} \sim B^{*}$ (закон двойственности).

?

Задача II.1.29

По данному набору значений переменных построить конъюнкт, истинный только для этого набора значений переменных. (Назовем такую формулу конъюнктом, соответствующим данному набору значений переменных.)

?

Задача II.1.30

Доказать, что всякая формула $A$ эквивалентна дизъюнкции конъюнктов, соответствующих тем наборам значений переменных, при которых данная формула истинна (см. задачу II.1.29).

?

Задача II.1.31

(а)(б)

?

(а)

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

(б)

Доказать, что для тождественно ложной формулы не существует эквивалентной ей с.д.н.ф.

Задача II.1.32

По данному набору значений переменных построить дизъюнкт, ложный только для этого набора значений переменных. (Назовем такую формулу дизъюнктом, соответствующим данному набору значений переменных.)

?

Задача II.1.33

Доказать, что всякая формула $A$ эквивалентна конъюнкции дизъюнктов, соответствующих тем наборам значений переменных, при которых данная формула ложна (см. задачу II.1.32).

?

Задача II.1.34

(а)(б)

?

(а)

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

(б)

Доказать, что для тождественно истинной формулы не существует эквивалентная ей с.к.н.ф.

Задача II.1.35

(а)(б)(в)

Привести к совершенной дизъюнктивной нормальной форме, т.е. найти с.д.н.ф., эквивалентную данной формуле:

?

(а)

$((\neg P \supset \neg Q) \supset ((Q \& R) \supset (P \& R)))$ ;

(б)

$(((P \supset Q) \supset \neg P) \supset (P \supset (Q \& P)))$ ;

(в)

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

Задача II.1.36

(а)(б)(в)

Привести к совершенной конъюнктивной нормальной форме, т.е. найти с.к.н.ф., эквивалентную данной формуле:

?

(а)

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

(б)

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

(в)

$(\neg (P \& (Q \vee R)) \supset ((P \& Q) \vee R))$ .

Задача II.1.37

(а)(б)

Построить формулу $A$ такую, чтобы данная формула была тождественно истинной:

?

(а)

$(((A \& Q) \supset \neg P) \supset ((P \supset \neg Q) \supset A))$ ;

(б)

$(((R \supset (\neg Q \& P)) \supset A) \supset (A \& (P \supset Q) \& R))$ .

Задача II.1.38

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

?

Задача II.1.39

Построить формулу от трех переменных, которая принимает такое же значение, как и большинство (меньшинство) переменных.

?

Задача II.1.40

(а)(б)(в)

Построить формулу $A$ от переменных $P, Q, R$ так, чтобы:

?

(а)

$(P \& A) \sim (P \& Q)$ и $(P \vee A) \sim (P \vee R)$ ;

(б)

$(R \supset A) \sim (R \supset (P \& Q))$ и $(A \supset R) \sim (\neg (P \vee Q) \supset R)$ ;

(в)

$(P \supset A) \sim (Q \supset (\neg P \vee R))$ и $((R \supset Q) \supset P) \sim (\neg P \supset \neg A)$ .

Задача II.1.41

Доказать, что формула от $n$ переменных является тождественно истинной (тождественно ложной) формулой тогда и только тогда, когда ее с.д.н.ф. (с.к.н.ф.) содержит $2^{n}$ попарно не эквивалентных конъюнктов (дизъюнктов).

?

Задача II.1.42

Пусть формула $A$ записана в с.к.н.ф. Строим формулу $B$ следующим образом:

выписываем конъюнкцию дизъюнктов, не входящих в $A$ ;
меняем на $\vee$ , $\vee$ на , $P_{i}$ на $\neg P_{i}$ , $\neg P_{i}$ на $P_{i}$ . Доказать, что формула $B$ --- с.д.н.ф. формулы $A$ .

?

Задача II.1.43

(а)(б)(в)

По с.к.н.ф. формулы $A$ построить:

?

(а)

с.д.н.ф. $A^{*}$ , где $A^{*}$ --- двойственная к $A$ (см. задачу II.1.28);

(б)

с.к.н.ф. формулы $\neg A$ ;

(в)

с.д.н.ф. формулы $\neg A$ .

Задача II.1.44

(а)(б)(в)

По с.д.н.ф. формулы $A$ и с.д.н.ф. формулы $B$ построить:

?

(а)

с.к.н.ф. и с.д.н.ф. формулы $(A \vee B)$ ;

(б)

с.к.н.ф. и с.д.н.ф. формулы $(A \& B)$ ;

(в)

с.к.н.ф. и с.д.н.ф. формулы $(A \supset B)$ .

Задача II.1.45

Доказать, что формула $A$ от переменных $P_{1}, \ldots , P_{k}$ эквивалентна некоторой формуле, содержащей лишь , $\vee$ , $\supset$ и не содержащей $\neg$ , тогда и только тогда, когда в ее с.к.н.ф. отсутствует дизъюнкт $(\neg P_{1} \vee \ldots \vee \neg P_{k})$ .

?

Задача II.1.46

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

?

Задача II.1.47

Пусть формула $A$ не содержит других связок, кроме $\equiv$ и $\neg$ . Доказать, что $A$ является тождественно истинной тогда и только тогда, когда каждая переменная и знак отрицания входят в $A$ четное число раз.

?

Алгебра высказываний