\documentclass[10pt,addpoints]{exam} \usepackage[latin1]{inputenc} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{tikz} \usepackage{pgfplots} \usepackage{enumerate} \usepackage{mathrsfs} \pagestyle{head} \usepackage{hyperref} %\headrule %\header{MATH 11}{Exam 1}{Fall 2016} \begin{document} \begin{coverpages} \begin{center}\huge MATH 2510 - EXAM 2 - SPRING 2018\\ SOLUTION \end{center} \begin{flushleft}\vspace{0.5in} 22 March 2018 \\ Instructor: Tom Cuchta \end{flushleft} \textbf{Instructions:} \begin{itemize} \item Show all work, clearly and in order, if you want to get full credit. If you claim something is true \textbf{you must show work backing up your claim}. I reserve the right to take off points if I cannot see how you arrived at your answer (even if your final answer is correct). \item Justify your answers algebraically whenever possible to ensure full credit. \item Circle or otherwise indicate your final answers. \item Please keep your written answers brief; be clear and to the point. \item Good luck! \end{itemize} \vspace*{10pt} \end{coverpages} \begin{questions} \question[20] Write the proof. \begin{parts} \part[10] Let $\mathcal{F}=\{\neg A \rightarrow (C \wedge D), A \rightarrow B, \neg B \}$. Write a proof to show $\mathcal{F} \vdash C$. \\ \textit{Solution}: \\ \begin{tabular}{|l|l|} \hline Statement & Justification \\ \hline 1. $\mathcal{F} \vdash \neg A \rightarrow (C \wedge D)$ & Assumption \\ 2. $\mathcal{F} \vdash A \rightarrow B$ & Assumption \\ 3. $\mathcal{F} \vdash \neg B$ & Assumption \\ 4. $\mathcal{F} \vdash \neg A \vee B$ & $\rightarrow$-definition on 2 \\ 5. $\mathcal{F} \vdash B \vee \neg A$ & $\vee$-symmetry on 4 \\ 6. $\mathcal{F} \vdash \neg A$ & 2nd $\vee$-modus ponens on 3 and 5 \\ 7. $\mathcal{F} \vdash C \wedge D$ & $\rightarrow$-elimination on 1 and 6 \\ 8. $\mathcal{F} \vdash C$ & $\wedge$-elimination\\ \hline \end{tabular} \part[10] Let $\mathcal{F}=\{P\wedge Q, P \rightarrow \neg (Q \wedge R), S \rightarrow R\}$. Write a proof to show $\mathcal{F} \vdash \neg S$. \\ \textit{Solution}: \\ \begin{tabular}{|l|l|} \hline Statement & Justification \\ \hline 1. $\mathcal{F} \vdash P \wedge Q$ & Assumption \\ 2. $\mathcal{F} \vdash P \rightarrow \neg (Q \wedge R)$ & Assumption \\ 3. $\mathcal{F} \vdash S \rightarrow R$ & Assumption \\ 4. $\mathcal{F} \vdash P$ & $\wedge$-elimination on 1 \\ 5. $\mathcal{F} \vdash Q \wedge P$ & $\wedge$-symmetry on 1 \\ 6. $\mathcal{F} \vdash Q$ & $\wedge$-elimination on 5 \\ 7. $\mathcal{F} \vdash \neg (Q \wedge R)$ & $\rightarrow$-elimination on 2 and 4 \\ 8. $\mathcal{F} \vdash \neg Q \vee \neg R$ & DeMorgan law on 7 \\ 9. $\mathcal{F} \vdash \neg R$ & $\vee$-modus ponens on 6 and 8 \\ 10. $\mathcal{F} \vdash \neg S \vee R$ & $\rightarrow$-definition on 3 \\ 11. $\mathcal{F} \vdash R \vee \neg S$ & $\vee$-symmetry on 10 \\ 12. $\mathcal{F} \vdash \neg S$ & $\vee$-modus ponens on 9 and 11 \\ \hline \end{tabular} \end{parts} \question[16] Use the Horn algorithm to decide if the formula is satisfiable or not. \begin{parts} \part[8] $(T \rightarrow A) \wedge ((B \wedge C) \rightarrow D) \wedge ((B \wedge A) \rightarrow E) \wedge (B \rightarrow \bot)$ \\ \textit{Solution}: We mark $A$ since $T \rightarrow A$ appears. We do not mark anything else. Therefore it \textbf{is satisfiable} since $B \rightarrow \bot$ appears but $B$ is not marked. \part[8] $(T \rightarrow A) \wedge (T \rightarrow C) \wedge ((A \wedge D) \rightarrow E) \wedge ((B \wedge C) \rightarrow F) \wedge (E \rightarrow \bot) \wedge ((A \wedge C) \rightarrow B) \wedge ((B \wedge C) \rightarrow D)$ \\ \textit{Solution}: Since $T \rightarrow A$ and $T \rightarrow C$ appear, we mark $A$ and $C$. Now since $(A \wedge C) \rightarrow B$, we mark $B$. Now since $(B \wedge C) \rightarrow D$ and $(B \wedge C) \rightarrow D$ appears, we mark $D$ and $F$. Since $(A \wedge D) \rightarrow E$ appears, we mark $E$. Finally, since $E \rightarrow \bot$ appears, we must conclude that the formula is \textbf{not satisfiable}. \end{parts} \question[16] Let $A$, $B$, and $C$ be definable subsets of a structure $M$ corresponding to the formulas $\phi$, $\psi$, and $\eta$, respectively. \begin{parts} \part[8] Show that $A \cap B \cup C$ is a definable subset of $M$. \\ \textit{Solution}: $A \cap B \cup C$ is the subset corresponding to the formula $\phi \wedge \psi \vee \eta$ \part[8] Show that $A \cup (B \setminus C)$ is definable. (note: recall $B \setminus C = \{ x \in B \colon x \not\in C \}$). \\ \textit{Solution}: $A \cup (B \setminus C)$ is the subset corresponding to the formula $\phi \vee (\psi \cap \neg \eta)$ \end{parts} \question[16] Consider the vocabulary $\mathcal{V}=\{+,\mathbf{1}\}$. Consider the structure $M=(\mathbb{Z}|+,\mathbf{1})$, where $+$ is interpreted in the usual way and $\mathbf{1}$ is interpreted as the integer $1$. \begin{parts} \part[8] Write a $\mathcal{V}$-formula that expresses ``$3+2=1$" (note: 3 and 2 are not in your vocabulary!). \\ \textit{Solution}: $(1+1+1) + (1+1) = 1$ \part[8] Write a $\mathcal{V}$-formula $\epsilon(a)$ that expresses ``$a+1=2$". \\ \textit{Solution}: $a + 1 = 1+1$ \end{parts} \question[16] Write down a vocabulary and a structure that models the formula. \begin{parts} \part[8] $\forall x \exists y(P(x,y) \vee N(x,y))$ \\ \textit{Solution}: $M=(\mathbb{Z}|P,N)$ where $P(x,y)$ is interpreted to mean $x \leq y$ and $N(x,y)$ is interpreted to mean $x \geq y$. \part[8] $\exists x (P(x) \wedge L(x,3))$ \\ \textit{Solution}: $M=(\mathbb{R}|P,L)$ where $3$ is interpreted as the real number $3$, $P(x)$ is interpeted to mean $x > 0$, and $L(x,3)$ is interpreted to mean $x < 3$. \end{parts} \question[16] In the following problems, a sentence, a vocabulary $\mathcal{V}$, and a $\mathcal{V}$-structure are given. You are asked to write a $\mathcal{V}$-formula to express the sentence. \begin{parts} \part[8] In the mathematical theory of topology, the following sentence is a theorem: \begin{center}``All closed sets that are both closed and a subset of a compact set are also compact."\end{center} Consider the vocabulary $\mathcal{V}=\{C,K,S\}$ where $C$ is a unary relation, $K$ is a unary relation, and $S$ is a binary relation. Consider the structure $\textbf{T}=(\tau|C,K,S)$, where $\tau$ denotes some collection of sets. Interpret $C(x)$ as ``$x$ is closed set", interpret $K(x)$ as ``$x$ is a compact set", and interpret $S(x,y)$ as ``$x$ is a subset of $y$". Write a $\mathcal{V}$-formula that expresses the sentence. \\ \textit{Solution}: $$\forall x \forall y ( (C(x) \wedge K(y) \wedge S(x,y)) \rightarrow K(x))$$ \part[8] Fermat's theorem on sums of two squares states, for natural numbers $p$, $x$, and $y$ (note: the natural numbers are $\mathbb{N}=\{1,2,3,\ldots\}$): \begin{center}``If $p$ is an odd prime number, then $p=x^2+y^2$ if and only if $p = 1 \mod 4$."\end{center} Consider a vocabulary $\mathcal{V}=\{O,P,M,+,{}^2,\mathbf{1},\mathbf{4}\}$ where $O$ and $P$ are unary relations, $M$ is a ternary relation, $+$ is a binary function, ${}^2$ is a unary function, and $1$ and $4$ are constants. Consider the structure $\textbf{M}=(\mathbb{N} | O,P,M,+,{}^2,\mathbf{1},\mathbf{4})$ where $+$ and ${}^2$ are interpreted in the usual way and we write $a+b$ instead of $+(a,b)$ and we write $a^2$ instead of ${}^2(a)$. Interpret $\mathbf{1}$ as the natural number $1$ and interpret $\mathbf{4}$ as the natural number $4$. Also interpret $O(a)$ as meaning ``$a$ is odd", $P(a)$ meaning ``$a$ is prime", and $M(a,b,c)$ meaning $a = b \mod c$. Write a $\mathcal{V}$-formula that expresses Fermat's theorem on sums of two squares. \\ \textit{Solution}: $$\forall p \forall x \forall y ( (O(p) \wedge P(p)) \rightarrow (p=x^2+y^2) \leftrightarrow M(p,1,4))$$ \vfill \end{parts} \end{questions} \newpage \vspace*{-200pt} \begin{center}\begin{figure}\begin{tabular}{|l|l|l|} \hline Premise & Conclusion & Name \\ \hline $G \in \mathcal{F}$ & $\mathcal{F} \vdash G$ & Assumption \\ $\mathcal{F} \vdash G$ and $\mathcal{F} \subset \mathcal{F}'$ & $\mathcal{F}' \subset G$ & Monotonicity \\ $\mathcal{F} \vdash G$ & $\mathcal{F} \vdash \neg \neg G$ & Double negation \\ $\mathcal{F} \vdash F$, $\mathcal{F} \vdash G$ & $\mathcal{F} \vdash (F \wedge G)$ & $\wedge$-introduction \\ $\mathcal{F} \vdash (F \wedge G)$ & $\mathcal{F} \vdash F$ & $\wedge$-elimination \\ $\mathcal{F} \vdash (F \wedge G)$ & $\mathcal{F} \vdash (G \wedge F)$ & $\wedge$-symmetry \\ $\mathcal{F} \vdash F$ & $\mathcal{F} \vdash (F \vee G)$ & $\vee$-introduction \\ $\mathcal{F} \vdash (F \vee G),$ && \\ $\mathcal{F} \cup \{F\} \vdash H, \mathcal{F} \cup \{G\} \vdash H$ & $\mathcal{F} \vdash H$ & $\vee$-elimination \\ $\mathcal{F} \vdash (F \vee G)$ & $\mathcal{F} \vdash (G \vee F)$ & $\vee$-symmetry \\ $\mathcal{F} \cup \{F\} \vdash G$ & $\mathcal{F} \vdash F \rightarrow G$ & $\rightarrow$-introduction \\ $\mathcal{F} \vdash (F \rightarrow G), \mathcal{F} \vdash F$ & $\mathcal{F} \vdash G$ & $\rightarrow$-elimination \\ $\mathcal{F} \vdash F$ & $\mathcal{F} \vdash (F)$ & $(,)$-introduction \\ $\mathcal{F} \vdash (F)$ & $\mathcal{F} \vdash F$ & $(,)$-elimination \\ $\mathcal{F} \vdash ((F \wedge G) \wedge H)$ & $\mathcal{F} \vdash (F \wedge G \wedge H)$ & $\wedge$-parentheses rule \\ $\mathcal{F} \vdash ((F \vee G) \vee H)$ & $\mathcal{F} \vdash (F \vee G \vee H)$ & $\vee$-parentheses rule \\ \hline \end{tabular} \caption{Table 1.5 -- proof system for propositional logic} \end{figure}\end{center} \begin{center}\begin{figure}\begin{tabular}{|l|l|l|} \hline Rule & Name \\ \hline $\mathcal{F} \vdash (F \vee G)$ if and only if $\mathcal{F} \vdash \neg (\neg F \wedge \neg G)$ & $\vee$-definition \\ $\mathcal{F} \vdash (F \rightarrow G)$ if and only if $\mathcal{F} \vdash (\neg F \vee G)$ & $\rightarrow$-definition \\ $\mathcal{F} \vdash (F \leftrightarrow G)$ if and only if both $\mathcal{F} \vdash (F \rightarrow G)$ and $\mathcal{F} \vdash (G \rightarrow F)$ & $\leftrightarrow$-definition \\ \hline \end{tabular} \caption{Table 1.6 -- proof system for propositional logic} \end{figure}\end{center} \begin{center}\begin{figure}\begin{tabular}{|l|l|l|l|} \hline Premise & Conclusion & Name & Source \\ \hline $\mathcal{F} \vdash (\neg F \vee G), \mathcal{F} \vdash F$ & $\mathcal{F} \vdash G$ & $\vee$-modus ponens & pg. 16 in text \\ $\mathcal{F} \vdash (F \vee G), \mathcal{F} \vdash \neg F$ & $\mathcal{F} \vdash G$ & 2nd $\vee$-modus ponens & 20 Feb 2018 class \\ none & $\mathcal{F} \vdash (\neg G \vee G)$ & Tautology rule & Example 1.32 \\ $\mathcal{F} \vdash (F \wedge \neg F)$ & $\mathcal{F} \vdash G$ & Contradiction rule & Example 1.33 \\ $\mathcal{F} \cup \{F\} \vdash G$ & $\mathcal{F} \cup \{\neg G\} \vdash \neg F$ & Contrapositive & Example 1.34 \\ $\mathcal{F} \cup \{F\} \vdash G, \mathcal{F} \cup \{\neg F\} \vdash G$ & $\mathcal{F} \vdash G$ & Proof by cases & Example 1.35 \\ $\mathcal{F} \cup \{F\} \vdash G, \mathcal{F} \cup \{F\} \vdash \neg G$ & $\mathcal{F} \vdash \neg F$ & Proof by contradiction & Example 1.36 \\ $\mathcal{F} \vdash \neg (F \vee G)$ & $\mathcal{F} \vdash \neg F \wedge \neg G$ & deMorgan & Proposition 1.44 \\ $\mathcal{F} \vdash \neg F \wedge \neg G$ & $\mathcal{F} \vdash \neg (F \vee G)$ & deMorgan & Proposition 1.44 \\ $\mathcal{F} \vdash \neg (F \wedge G)$ & $\mathcal{F} \vdash \neg F \vee \neg G$ & deMorgan & Proposition 1.44 \\ $\mathcal{F} \vdash \neg F \vee \neg G$ & $\mathcal{F} \vdash \neg (F \wedge G)$ & deMorgan & Proposition 1.44 \\ $\mathcal{F} \vdash F \wedge (G \vee H)$ & $\mathcal{F} \vdash ((F \wedge G) \vee (F \wedge H))$ & $\wedge$-distributivity & Proposition 1.45 \\ $\mathcal{F} \vdash ((F \wedge G) \vee (F \wedge H))$ & $\mathcal{F} \vdash F \wedge (G \vee H)$ & $\wedge$-distributivity & Proposition 1.45 \\ $\mathcal{F} \vdash (F \vee (G \wedge H))$ & $\mathcal{F} \vdash ((F \vee G) \wedge (F \vee H))$ & $\vee$-distributivity & Proposition 1.46 \\ $\mathcal{F} \vdash ((F \vee G) \wedge (F \vee H))$ & $\mathcal{F} \vdash (F \vee (G \wedge H))$ & $\vee$-distributivity & Proposition 1.46 \\ \hline \end{tabular} \caption{Further rules derived for propositional logic}\end{figure}\end{center} \vspace*{2in} Let $\phi(x_1,\ldots,x_n)$ be a $\mathcal{V}$-formula and let $M$ be a $\mathcal{V}$-structure with underlying set $\mathscr{U}$. The definable subset of the formula $\phi(x_1,\ldots,x_n)$ is the subset of $\mathscr{U}^n$ consisting of all $(b_1,\ldots,b_n)$ for which $M \vDash \phi(b_1,\ldots,b_n)$. \\ \underline{Horn Algorithm} \\ \textbf{Step 1}: Mark each atomic formula $A$ in the list that is in a subformula of the form $(T \rightarrow A)$. \\ \textbf{Step 2}: If there is a subformula of the form $(A1 \wedge A2\wedge \ldots \wedge Am) \rightarrow C$ where each $A_i$ has been marked and $C$ has not been marked, then mark $C$. Repeat this step until there are no subformulas of this form and then proceed to step 3. \\ \textbf{Step 3}: Consider the subformulas of the form $(A_1 \wedge A_2\wedge \ldots \wedge A_m) \rightarrow \bot$. If there exists such a subformula where each $A_i$ has been marked, then conclude ``No, H is not satisfiable." Otherwise, conclude ``Yes, H is satisfiable." \end{document}