Math Problems Vault

Problem II.1.1

(a)(b)(c)(d)

Determine whether the given sequence is a formula:

?

(a)

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

(b)

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

(c)

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

(d)

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

Problem II.1.2

(a)(b)

In how many ways can parentheses be inserted into the following sequence so as to obtain a formula:

?

(a)

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

(b)

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

Problem II.1.3

(a)(b)

Write out all subformulas of the formula:

?

(a)

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

(b)

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

Problem II.1.4

Prove that every formula $C$ that is not a propositional variable can be represented in one of the following forms: $\neg A$ , $(A \& B)$ , $(A \vee B)$ , $(A \supset B)$ for some formulas $A$ and $B$ .

?

Problem II.1.5

Prove that the result of replacing a given occurrence of the formula $C$ in the formula $A$ , in place of a subformula $B$ , is again a formula.

?

Problem II.1.6

Prove that the result of the substitution $A(P \backslash B)$ of the formula $B$ for the propositional variable $P$ in the formula $A$ is again a formula.

?

Problem II.1.7

Construct the truth tables for the following formulas:

?

(a)

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

(b)

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

(c)

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

(d)

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

(e)

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

(f)

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

Problem II.1.8

(a)(b)(c)

Prove the satisfiability of the formulas:

?

(a)

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

(b)

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

(c)

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

Problem II.1.9

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

(n)

(o)

(p)

(q)

(r)

(s)

(t)

(u)

Problem II.1.10

For which values of the variables $X, Y, Z, U, V, W$ are the following formulas false:

?

(a)

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

(b)

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

(c)

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

(d)

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

(e)

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

Problem II.1.11

Prove that if the formula $A$ is identically true, then the formula $A(P \backslash B)$ is identically true. (Here $P$ is a propositional variable, and $B$ is a formula.)

?

Problem II.1.12

Prove that if the formulas $A$ and $(A \supset B)$ are identically true, then the formula $B$ is identically true.

?

Problem II.1.13

(a)(b)(c)

Prove that:

?

(a)

if the formulas $(A \vee B)$ and $(\neg A \vee C)$ are identically true, then the formula $(B \vee C)$ is identically true;

(b)

if the formulas $(A \vee B)$ , $(A \supset C)$ , $(B \supset D)$ are identically true, then the formula $(C \vee D)$ is identically true;

(c)

if the formulas $(\neg A \vee B)$ , $(\neg C \vee \neg B)$ are identically true, then the formula $(A \supset \neg B)$ is identically true.

Problem II.1.14

Prove that $A \sim B$ if and only if $A \equiv B$ is identically true.

?

Problem II.1.15

(a)(b)(c)

Prove that:

?

(a)

$A \sim A$ ;

(b)

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

(c)

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

Problem II.1.16

(a)(b)(c)(d)

Prove that $A_{1} \sim A_{2}$ and $B_{1} \sim B_{2}$ imply:

?

(a)

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

(b)

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

(c)

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

(d)

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

Problem II.1.17

Prove that if $A \sim B$ , then $A(P \backslash C) \sim B(P \backslash C)$ for any formulas $A, B, C$ and variable $P$ .

?

Problem II.1.18

Prove that if $B \sim B_{1}$ and $A_{1}$ is the result of replacing some occurrence of the subformula $B$ in the formula $A$ by the formula $B_{1}$ , then $A \sim A_{1}$ .

?

Problem II.1.19

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

Problem II.1.20

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

(n)

(o)

(p)

Problem II.1.21

(a)(b)(c)

Prove that:

?

(a)

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

(b)

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

(c)

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

Problem II.1.22

Prove that for every formula there exists an equivalent formula with tight negations, i.e., a formula in which the symbol $\supset$ does not occur and negations apply only to propositional variables.

?

Problem II.1.23

(a)(b)

Prove that for every formula there exists an equivalent:

?

(a)

conjunctive normal form;

(b)

disjunctive normal form.

Problem II.1.24

(a)(b)(c)

Reduce to disjunctive and conjunctive normal form:

?

(a)

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

(b)

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

(c)

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

Problem II.1.25

Prove that if $A$ is an identically true CNF, then for every disjunct of the formula $A$ there is a variable $P$ such that $P$ and $\neg P$ both occur in this disjunct.

?

Problem II.1.26

Prove that if $A$ is an identically false DNF, then for every conjunct of the formula $A$ there is a variable $P$ such that $P$ and $\neg P$ both occur in this conjunct.

?

Problem II.1.27

Let $A$ be a formula with tight negations (see Problem II.1.22), and let $A_{1}$ be obtained from $A$ by replacing by $\vee$ , $\vee$ by , and the variables $A_{i}$ by $\neg A_{i}$ . Prove that $A_{1} \sim \neg A$ .

?

Problem II.1.28

Let $A$ and $B$ be formulas with tight negations (see Problem II.1.22), and let $A^{*}$ , $B^{*}$ be the formulas dual to $A$ and $B$ respectively ( $A^{*}$ is obtained from $A$ by replacing by $\vee$ , $\vee$ by ). Prove that $A \sim B$ implies $A^{*} \sim B^{*}$ (the duality law).

?

Problem II.1.29

Given a set of values of the variables, construct a conjunct that is true only for this set of values of the variables. (Call such a formula the conjunct corresponding to the given set of values of the variables.)

?

Problem II.1.30

Prove that every formula $A$ is equivalent to the disjunction of the conjuncts corresponding to those sets of values of the variables for which the given formula is true (see Problem II.1.29).

?

Problem II.1.31

(a)(b)

?

(a)

Prove that for every satisfiable formula there exists an equivalent p.d.n.f.

(b)

Prove that for an identically false formula there is no equivalent p.d.n.f.

Problem II.1.32

Given a set of values of the variables, construct a disjunct that is false only for this set of values of the variables. (Call such a formula the disjunct corresponding to the given set of values of the variables.)

?

Problem II.1.33

Prove that every formula $A$ is equivalent to the conjunction of the disjuncts corresponding to those sets of values of the variables for which the given formula is false (see Problem II.1.32).

?

Problem II.1.34

(a)(b)

?

(a)

Prove that for every falsifiable formula there exists an equivalent p.c.n.f.

(b)

Prove that for an identically true formula there is no equivalent p.c.n.f.

Problem II.1.35

(a)(b)(c)

Reduce to perfect disjunctive normal form, i.e., find a p.d.n.f. equivalent to the given formula:

?

(a)

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

(b)

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

(c)

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

Problem II.1.36

(a)(b)(c)

Reduce to perfect conjunctive normal form, i.e., find a p.c.n.f. equivalent to the given formula:

?

(a)

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

(b)

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

(c)

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

Problem II.1.37

(a)(b)

Construct a formula $A$ such that the given formula is identically true:

?

(a)

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

(b)

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

Problem II.1.38

Construct a formula in three variables that is true if and only if exactly two of the variables are false.

?

Problem II.1.39

Construct a formula in three variables that takes the same value as the majority (minority) of the variables.

?

Problem II.1.40

(a)(b)(c)

Construct a formula $A$ in the variables $P, Q, R$ such that:

?

(a)

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

(b)

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

(c)

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

Problem II.1.41

Prove that a formula in $n$ variables is identically true (identically false) if and only if its p.d.n.f. (p.c.n.f.) contains $2^{n}$ pairwise non-equivalent conjuncts (disjuncts).

?

Problem II.1.42

Let the formula $A$ be written in p.c.n.f. We construct a formula $B$ as follows:

we write out the conjunction of the disjuncts not occurring in $A$ ;
we change to $\vee$ , $\vee$ to , $P_{i}$ to $\neg P_{i}$ , $\neg P_{i}$ to $P_{i}$ . Prove that the formula $B$ is a p.d.n.f. of the formula $A$ .

?

Problem II.1.43

(a)(b)(c)

From the p.c.n.f. of a formula $A$ , construct:

?

(a)

the p.d.n.f. $A^{*}$ , where $A^{*}$ is dual to $A$ (see Problem II.1.28);

(b)

the p.c.n.f. of the formula $\neg A$ ;

(c)

the p.d.n.f. of the formula $\neg A$ .

Problem II.1.44

(a)(b)(c)

From the p.d.n.f. of a formula $A$ and the p.d.n.f. of a formula $B$ , construct:

?

(a)

the p.c.n.f. and p.d.n.f. of the formula $(A \vee B)$ ;

(b)

the p.c.n.f. and p.d.n.f. of the formula $(A \& B)$ ;

(c)

the p.c.n.f. and p.d.n.f. of the formula $(A \supset B)$ .

Problem II.1.45

Prove that a formula $A$ in the variables $P_{1}, \ldots , P_{k}$ is equivalent to some formula containing only , $\vee$ , $\supset$ and not containing $\neg$ , if and only if its p.c.n.f. lacks the disjunct $(\neg P_{1} \vee \ldots \vee \neg P_{k})$ .

?

Problem II.1.46

Let the formula $A$ contain no connectives other than $\equiv$ . Prove that $A$ is identically true if and only if every variable occurs in $A$ an even number of times.

?

Problem II.1.47

Let the formula $A$ contain no connectives other than $\equiv$ and $\neg$ . Prove that $A$ is identically true if and only if every variable and the negation sign occur in $A$ an even number of times.

?