Problem 6
Show that \(\mid\) and \(\downarrow\) are the only binary connectives \(\$$ such that \)\\{\$\\}$ is functionally complete.
Problem 7
Show in the system with \(\vee\) as a primitive connective $$ \begin{aligned} &\vdash(\varphi \rightarrow \psi) \leftrightarrow(\neg \varphi \vee \psi) \\ &\vdash(\varphi \rightarrow \psi) \vee(\psi \rightarrow \varphi) \end{aligned} $$
Problem 8
Let the ternary connective \(\$$ be defined by \)\llbracket \$\left(\varphi_{1}, \varphi_{2}, \varphi_{3}\right) \rrbracket=1 \Leftrightarrow\( \)\left.\llbracket \varphi_{1} \rrbracket+\llbracket \varphi_{2}\right]+\left[\varphi_{3}\right] \geq 2\( (the majority connective). Express \)\$$ in terms of \(\vee\) and \(\neg\).
Problem 8
The size, \(s(\mathcal{D})\), of a derivation is the number of proposition occurrences in \(\mathcal{D}\). Give an inductive definition of \(s(\mathcal{D})\). Show that one can prove properties of derivations by it induction on the size.
Problem 10
Show that the relation "is a subformula of" is transitive.
Problem 10
Determine conjunctive and disjunctive normal forms for \(\neg(\varphi \leftrightarrow \psi)\), \(((\varphi \rightarrow \psi) \rightarrow \psi) \rightarrow \psi,(\varphi \rightarrow(\varphi \wedge \neg \psi)) \wedge(\psi \rightarrow(\psi \wedge \neg \varphi))\)
Problem 11
Give a criterion for a conjunctive normal form to be a tautology.
Problem 12
$$ \begin{aligned} &\text { Prove } \ \backslash_{i \leq n} \varphi_{i} \vee M_{j \leq m} \psi_{j} \approx \prod_{i \leq n} \atop \bigwedge_{j \leq m}\left(\varphi_{i} \vee \psi_{j}\right) \text { and } \\ &\bigvee_{i \leq n} \varphi_{i} \wedge \bigvee_{j \leq m} \psi_{j} \approx \underset{i \leq n \atop j \leq m}{\bigvee}\left(\varphi_{i} \wedge \psi_{j}\right) \end{aligned} $$
