Logical matrices and many-valued semantics

[6/83%]

Show

LaTeX

Show LaTeX

Problem II.3.38 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter II.3 "Propositional Calculi"

Let $A$ be a formula, $\Delta$ a system of formulas, and $M$ a logical matrix. Prove that if all formulas of $\Delta$ are generally valid in $M$ , and a direct consequence of formulas generally valid in $M$ is a formula generally valid in $M$ , while the formula $A$ is not generally valid in $M$ , then $A$ is independent of $\Delta$ .

Problem II.3.39 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter II.3 "Propositional Calculi"

Let $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$ . Prove that the formula

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

is independent of $\Delta$ , where $\Delta = \left\{ (P \supset (Q \supset P)), ((\neg P \supset \neg Q) \supset (Q \supset P))\right\}$ , using the logical matrix $\langle M; D, \& , \vee , \supset , \neg \rangle$ .

Problem II.3.40 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter II.3 "Propositional Calculi"

Prove the independence of the axiom schemes of the calculus PC.

Problem II.3.41 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter II.3 "Propositional Calculi"

(a)(b)(c)

Let $L$ be the propositional calculus with axiom schemes:

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))$

and rule of inference $\dfrac {A; \ (A \supset B)}{B}$ .

(a)

Prove that every formula derivable in $L$ is also derivable in PC.

(b)

Prove the deduction theorem for $L$ .

(c)

Set $(A \& B) = \neg (A \supset \neg B)$ , $(A \vee B) = (\neg A \supset B)$ . Prove that every formula derivable in PC is derivable in $L$ .

Problem II.3.47 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter II.3 "Propositional Calculi"

(a)(b)

Let $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{if } x \geq y, \\ y, & \text{if } x < y, \end{cases} \qquad \neg x = \begin{cases} 0, & \text{if } x = n, \\ n, & \text{if } x < n. \end{cases}

Prove that:

(a)

every formula derivable in IPC is generally valid in $M_{n} = \langle M; D, \& , \vee , \supset , \neg \rangle$ ( $n = 1, 2, \ldots$ ).

(b)

the formulas

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}))

are not derivable in IPC ( $n = 1, 2, \ldots$ ).

Problem II.3.48 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter II.3 "Propositional Calculi"

Let $M = \langle M; D, \& , \vee , \supset , \neg \rangle$ be a logical matrix such that the set of formulas generally valid in $M$ coincides with the set of formulas derivable in IPC. Prove that the set $M$ is infinite.

References

[LaMa02] Lavrov I.A., Maksimova L.L. Задачи по теории множеств, математической логике и теории алгоритмов. 5-е изд., Физматлит, 2002.