Math Problems Vault

Problem II.1.1 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter II.1 "The Algebra of Propositions"

(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 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter II.1 "The Algebra of Propositions"

(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 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter II.1 "The Algebra of Propositions"

(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 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter II.1 "The Algebra of Propositions"

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 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter II.1 "The Algebra of Propositions"

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 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter II.1 "The Algebra of Propositions"

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.4.1 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter II.4 "The Language of the Predicate Calculus"

(a)(b)(c)

Let $f^{1}$ be a 1-ary, $g^{2}$ a 2-ary, and $h^{3}$ a 3-ary function symbol. Are the following words terms:

?

(a)

$f^{1}(g^{2}(\nu_{0}, \nu_{1}))$ ;

(b)

$g^{2}(f^{1}(\nu_{2}), h^{3}(\nu_{0}, \nu_{1}, \nu_{2}))$ ;

(c)

$f^{1}(g^{2}(\nu_{0}), h^{3}(\nu_{0}, \nu_{1}, \nu_{2}))$ ?

Problem II.4.2 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter II.4 "The Language of the Predicate Calculus"

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

Let $f^{1}, g^{2}, h^{3}$ be as in the previous problem, $P^{1}$ a 1-ary and $Q^{3}$ a 3-ary predicate symbol. Are the following words formulas:

?

(a)

$Q^{3}(\nu_{0}, f^{1}(\nu_{1}), h^{3}(\nu_{1}, \nu_{2}, \nu_{2}))$ ;

(b)

$(P^{1}(\nu_{0}) \supset \forall \nu_{1}(Q^{3}(\nu_{0}, \nu_{1}, \nu_{2}) \& P^{1}(g^{2}(\nu_{0}, \nu_{1}))))$ ;

(c)

$Q^{3}(P^{1}(\nu_{0}), f^{1}(\nu_{1}), f^{1}(\nu_{2}))$ ;

(d)

$f^{1}(h^{3}(\nu_{0}, \nu_{1}, \nu_{2}))$ ?

Problem II.4.3 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter II.4 "The Language of the Predicate Calculus"

Show that the expression

\exists \nu _{0} \forall \nu _{1} \ldots \forall \nu _{\nu _{0}} (P(\nu _{1}) \& \ldots \& P(\nu _{\nu _{0}})),

where $P$ is a 1-ary predicate symbol, is not a formula.

?

Problem II.4.4 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter II.4 "The Language of the Predicate Calculus"

(a)(b)

Write out all subformulas of the formula:

?

(a)

$Q^{2}(f^{1}(\nu_{0}), g^{2}(\nu_{0}, \nu_{1}))$ ;

(b)

$(\exists \nu_{0} Q^{2}(\nu_{0}, \nu_{1}) \supset \neg (P^{1}(g^{2}(\nu_{0}, \nu_{1})) \& \forall \nu_{2} P^{1}(\nu_{2})))$ .

Problem II.4.5 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter II.4 "The Language of the Predicate Calculus"

(a)(b)

Describe the set of terms in one variable $\nu_{0}$ :

?

(a)

and function symbol $f^{1}$ ;

(b)

and function symbol $g^{2}$ .

Problem II.4.6 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter II.4 "The Language of the Predicate Calculus"

(a)(b)(c)

Which occurrences of variables are free and which are bound in the formulas:

?

(a)

$\forall \nu_{0}(P(\nu_{0}, \nu_{1}) \supset \forall \nu_{1} Q(\nu_{1}))$ ;

(b)

$(\forall \nu_{0} P(\nu_{0}, \nu_{1}) \supset \forall \nu_{1} R(\nu_{0}, \nu_{1}))$ ;

(c)

$(\neg \exists \nu_{2} Q(\nu_{2}, \nu_{2}) \& R(f(\nu_{1}, \nu_{2})))$ ?

Problem II.4.7 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter II.4 "The Language of the Predicate Calculus"

(a)(b)

Is the term $t$ free for $x$ in $A$ :

?

(a)

$t = f(\nu_{0}, \nu_{3})$ , $x = \nu_{1}$ , $A = \forall \nu_{0} P(\nu_{0}, \nu_{1})$ ;

(b)

$t = f(\nu_{1}, \nu_{2})$ , $x = \nu_{1}$ , $A = (P(\nu_{1}, \nu_{2}) \supset \exists \nu_{2} Q(\nu_{2}))$ ?

Problem II.4.8 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter II.4 "The Language of the Predicate Calculus"

(a)(b)(c)

Prove that:

?

(a)

a term containing no variables is free for any variable in any formula;

(b)

the variable $x$ is free for $x$ in any formula;

(c)

if $A$ contains no free occurrences of $x$ , then any term is free for $x$ in $A$ .

Syntax of logical formulas and terms

References