Problem 1
Check which of the following sets are consistent. (a) \(\left\\{\neg p_{1} \wedge p_{2} \rightarrow p_{0}, p_{1} \rightarrow\left(\neg p_{1} \rightarrow p_{2}\right), p_{0} \leftrightarrow \neg p_{2}\right\\}\), (b) \(\left\\{p_{0} \rightarrow p_{1}, p_{1} \rightarrow p_{2}, p_{2} \rightarrow p_{3}, p_{3} \rightarrow \neg p_{0}\right\\}\), (c) \(\left\\{p_{0} \rightarrow p_{1}, p_{0} \wedge p_{2} \rightarrow p_{1} \wedge p_{3}, p_{0} \wedge p_{2} \wedge p_{4} \rightarrow p_{1} \wedge p_{3} \wedge p_{5}, \ldots\right\\}\)
Problem 1
Check by the truth table method which of the following propositions are tautologies (a) \((\neg \varphi \vee \psi) \leftrightarrow(\psi \rightarrow \varphi)\) (b) \(\varphi \rightarrow((\psi \rightarrow \sigma) \rightarrow((\varphi \rightarrow \psi) \rightarrow(\varphi \rightarrow \sigma)))\) (c) \((\varphi \rightarrow \neg \varphi) \leftrightarrow \neg \varphi\) (d) \(\neg(\varphi \rightarrow \neg \varphi)\) (e) \((\varphi \rightarrow(\psi \rightarrow \sigma)) \leftrightarrow((\varphi \wedge \psi) \rightarrow \sigma)\) (f) \(\varphi \vee \neg \varphi\) (principle of the excluded third) (g) \(\perp \leftrightarrow(\varphi \wedge \neg \varphi)\) (h) \(\perp \rightarrow \varphi\) (ex falso sequitur quodlibet)
Problem 2
Simplify the following propositions (i.e. find a simpler equivalent proposition). (a) \((\varphi \rightarrow \psi) \wedge \varphi\), (b) \((\varphi \rightarrow \psi) \vee \neg \varphi\), (c) \((\varphi \rightarrow \psi) \rightarrow \psi\), (d) \(\varphi \rightarrow(\varphi \wedge \psi)\), (e) \((\varphi \wedge \psi) \vee \varphi\), \((\mathrm{f})(\varphi \rightarrow \psi) \rightarrow \varphi\)
Problem 2
Show (a) \(\varphi \models \varphi\); (b) \(\varphi \models \psi\) and \(\psi \models \sigma \Rightarrow \varphi \models \sigma\); (c) \(\models \varphi \rightarrow \psi \Rightarrow \varphi \models \psi\).
Problem 2
Consider the full language \(\mathcal{L}\) with the connectives \(\wedge, \rightarrow, \perp, \leftrightarrow \vee\) and the restricted language \(\mathcal{L}^{\prime}\) with connectives \(\wedge, \rightarrow, \perp\). Using the appropriate derivation rules we get the derivability notions \(\vdash\) and \(\vdash^{\prime}\). We define an obvious translation from \(\mathcal{L}\) into \(\mathcal{L}^{\prime}\) : \(\begin{aligned} \varphi^{+} &:=\varphi \text { for atomic } \varphi \\\\(\varphi \square \psi)^{+} &:=\varphi^{+} \square \psi^{+} \text {for } \square=\wedge, \rightarrow, \end{aligned}\) \((\varphi \vee \psi)^{+}:=\neg\left(\neg \varphi^{+} \wedge \neg \varphi^{+}\right)\), where \(\neg\) is an abbreviation, \((\varphi \leftrightarrow \psi)^{+}:=\left(\varphi^{+} \rightarrow \psi^{+}\right) \wedge\left(\psi^{+} \rightarrow \varphi^{+}\right)\), $$ (\neg \varphi)^{+}:=\varphi^{+} \rightarrow \perp . $$ Show (i) \(\vdash \varphi \leftrightarrow \varphi^{+}\), (ii) \(\quad \vdash \varphi \Leftrightarrow \vdash^{\prime} \varphi^{+}\), (iii) \(\varphi^{+}=\varphi\) for \(\varphi \in \mathcal{L}^{\prime}\). (iv) Show that the full logic, is conservative over the restricted logic, i.e. for \(\varphi \in \mathcal{L}^{\prime} \vdash \varphi \Leftrightarrow \vdash^{\prime} \varphi\).
Problem 3
Show \(\quad(a) \quad \varphi \vdash \neg(\neg \varphi \wedge \psi)\), (b) \(\neg(\varphi \wedge \neg \psi), \varphi \vdash \psi\) (c) \(\neg \varphi \vdash(\varphi \rightarrow \psi) \leftrightarrow \neg \varphi\), (d) \(\vdash \varphi \Rightarrow \vdash \psi \rightarrow \varphi\), (e) \(\neg \varphi \vdash \varphi \rightarrow \psi\)
Problem 3
Show that \(\\{\neg\\}\) is not a functionally complete set of connectives. Idem for \(\\{\rightarrow, \vee\\}\) (hint: show that each formula \(\varphi\) with only \(\rightarrow\) and \(\vee\) there is a valuation \(v\) such that \(\llbracket \varphi \rrbracket=1\) ).
Problem 4
Show that the connective \(\downarrow\), with valuation function \([\varphi \downarrow \psi]=1\) iff \([\varphi]=[\psi \rrbracket=0\), forms a functionally complete set (neither \(\varphi\), nor \(\psi)\).
Problem 4
Show that the Sheffer stroke, I, forms a functionally complete set (hint: \(\models \neg \varphi \leftrightarrow \varphi \mid \varphi\) ).
Problem 5
Show that the connective \(\downarrow\), with valuation function \([\varphi \downarrow \psi]=1\) iff \([\varphi]=[\psi]=0\), forms a functionally complete set (neither \(\varphi\), nor \(\psi)\).
