\(\newcommand{\footnotename}{footnote}\)
\(\def \LWRfootnote {1}\)
\(\newcommand {\footnote }[2][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\newcommand {\footnotemark }[1][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\let \LWRorighspace \hspace \)
\(\renewcommand {\hspace }{\ifstar \LWRorighspace \LWRorighspace }\)
\(\newcommand {\TextOrMath }[2]{#2}\)
\(\newcommand {\mathnormal }[1]{{#1}}\)
\(\newcommand \ensuremath [1]{#1}\)
\(\newcommand {\LWRframebox }[2][]{\fbox {#2}} \newcommand {\framebox }[1][]{\LWRframebox } \)
\(\newcommand {\setlength }[2]{}\)
\(\newcommand {\addtolength }[2]{}\)
\(\newcommand {\setcounter }[2]{}\)
\(\newcommand {\addtocounter }[2]{}\)
\(\newcommand {\arabic }[1]{}\)
\(\newcommand {\number }[1]{}\)
\(\newcommand {\noalign }[1]{\text {#1}\notag \\}\)
\(\newcommand {\cline }[1]{}\)
\(\newcommand {\directlua }[1]{\text {(directlua)}}\)
\(\newcommand {\luatexdirectlua }[1]{\text {(directlua)}}\)
\(\newcommand {\protect }{}\)
\(\def \LWRabsorbnumber #1 {}\)
\(\def \LWRabsorbquotenumber "#1 {}\)
\(\newcommand {\LWRabsorboption }[1][]{}\)
\(\newcommand {\LWRabsorbtwooptions }[1][]{\LWRabsorboption }\)
\(\def \mathchar {\ifnextchar "\LWRabsorbquotenumber \LWRabsorbnumber }\)
\(\def \mathcode #1={\mathchar }\)
\(\let \delcode \mathcode \)
\(\let \delimiter \mathchar \)
\(\def \oe {\unicode {x0153}}\)
\(\def \OE {\unicode {x0152}}\)
\(\def \ae {\unicode {x00E6}}\)
\(\def \AE {\unicode {x00C6}}\)
\(\def \aa {\unicode {x00E5}}\)
\(\def \AA {\unicode {x00C5}}\)
\(\def \o {\unicode {x00F8}}\)
\(\def \O {\unicode {x00D8}}\)
\(\def \l {\unicode {x0142}}\)
\(\def \L {\unicode {x0141}}\)
\(\def \ss {\unicode {x00DF}}\)
\(\def \SS {\unicode {x1E9E}}\)
\(\def \dag {\unicode {x2020}}\)
\(\def \ddag {\unicode {x2021}}\)
\(\def \P {\unicode {x00B6}}\)
\(\def \copyright {\unicode {x00A9}}\)
\(\def \pounds {\unicode {x00A3}}\)
\(\let \LWRref \ref \)
\(\renewcommand {\ref }{\ifstar \LWRref \LWRref }\)
\( \newcommand {\multicolumn }[3]{#3}\)
\(\require {textcomp}\)
\(\newcommand {\toprule }[1][]{\hline }\)
\(\let \midrule \toprule \)
\(\let \bottomrule \toprule \)
\(\def \LWRbooktabscmidruleparen (#1)#2{}\)
\(\newcommand {\LWRbooktabscmidrulenoparen }[1]{}\)
\(\newcommand {\cmidrule }[1][]{\ifnextchar (\LWRbooktabscmidruleparen \LWRbooktabscmidrulenoparen }\)
\(\newcommand {\morecmidrules }{}\)
\(\newcommand {\specialrule }[3]{\hline }\)
\(\newcommand {\addlinespace }[1][]{}\)
\(\def \LWRpagenote {1}\)
\(\newcommand {\pagenote }[2][\LWRpagenote ]{{}^{\mathrm {#1}}}\)
\(\require {colortbl}\)
\(\let \LWRorigcolumncolor \columncolor \)
\(\renewcommand {\columncolor }[2][named]{\LWRorigcolumncolor [#1]{#2}\LWRabsorbtwooptions }\)
\(\let \LWRorigrowcolor \rowcolor \)
\(\renewcommand {\rowcolor }[2][named]{\LWRorigrowcolor [#1]{#2}\LWRabsorbtwooptions }\)
\(\let \LWRorigcellcolor \cellcolor \)
\(\renewcommand {\cellcolor }[2][named]{\LWRorigcellcolor [#1]{#2}\LWRabsorbtwooptions }\)
\(\require {cancel}\)
\(\newcommand {\intertext }[1]{\text {#1}\notag \\}\)
\(\let \Hat \hat \)
\(\let \Check \check \)
\(\let \Tilde \tilde \)
\(\let \Acute \acute \)
\(\let \Grave \grave \)
\(\let \Dot \dot \)
\(\let \Ddot \ddot \)
\(\let \Breve \breve \)
\(\let \Bar \bar \)
\(\let \Vec \vec \)
\(\require {mathtools}\)
\(\newcommand {\vcentcolon }{\mathrel {\unicode {x2236}}}\)
\(\newcommand {\approxcolon }{\approx \vcentcolon }\)
\(\newcommand {\Approxcolon }{\approx \dblcolon }\)
\(\newcommand {\simcolon }{\sim \vcentcolon }\)
\(\newcommand {\Simcolon }{\sim \dblcolon }\)
\(\newcommand {\dashcolon }{\mathrel {-}\vcentcolon }\)
\(\newcommand {\Dashcolon }{\mathrel {-}\dblcolon }\)
\(\newcommand {\colondash }{\vcentcolon \mathrel {-}}\)
\(\newcommand {\Colondash }{\dblcolon \mathrel {-}}\)
\(\newenvironment {crampedsubarray}[1]{}{}\)
\(\newcommand {\smashoperator }[2][]{#2\limits }\)
\(\newcommand {\SwapAboveDisplaySkip }{}\)
\(\newcommand {\LaTeXunderbrace }[1]{\underbrace {#1}}\)
\(\newcommand {\LaTeXoverbrace }[1]{\overbrace {#1}}\)
\(\Newextarrow \xLongleftarrow {10,10}{0x21D0}\)
\(\Newextarrow \xLongrightarrow {10,10}{0x21D2}\)
\(\let \xlongleftarrow \xleftarrow \)
\(\let \xlongrightarrow \xrightarrow \)
\(\newcommand {\LWRmultlined }[1][]{\begin {multline*}}\)
\(\newenvironment {multlined}[1][]{\LWRmultlined }{\end {multline*}}\)
\(\let \LWRorigshoveleft \shoveleft \)
\(\renewcommand {\shoveleft }[1][]{\LWRorigshoveleft }\)
\(\let \LWRorigshoveright \shoveright \)
\(\renewcommand {\shoveright }[1][]{\LWRorigshoveright }\)
\(\newcommand {\shortintertext }[1]{\text {#1}\notag \\}\)
\(\newcommand {\LWRnicearrayarray }[1]{\begin {array}{#1}}\)
\(\def \LWRnicearrayarrayopt #1[#2] {\begin {array}{#1}}\)
\(\newenvironment {NiceArray}[2][]{\ifnextchar [{\LWRnicearrayarrayopt {#2}}{\LWRnicearrayarray {#2}}}{\end {array}}\)
\(\newcommand {\LWRnicearraywithdelimtwo }[2][]{\ifnextchar [{\LWRnicearrayarrayopt {#2}}{\LWRnicearrayarray {#2}}}\)
\(\newenvironment {NiceArrayWithDelims}[2]{\def \LWRnicearrayrightdelim {\right #2}\left #1\LWRnicearraywithdelimtwo }{\end {array}\LWRnicearrayrightdelim }\)
\(\newenvironment {pNiceArray} {\begin {NiceArrayWithDelims}{(}{)}} {\end {NiceArrayWithDelims}} \)
\(\newenvironment {bNiceArray} {\begin {NiceArrayWithDelims}{[}{]}} {\end {NiceArrayWithDelims}} \)
\(\newenvironment {BNiceArray} {\begin {NiceArrayWithDelims}{\{}{\}}} {\end {NiceArrayWithDelims}} \)
\(\newenvironment {vNiceArray} {\begin {NiceArrayWithDelims}{\vert }{\vert }} {\end {NiceArrayWithDelims}} \)
\(\newenvironment {VNiceArray} {\begin {NiceArrayWithDelims}{\Vert }{\Vert }} {\end {NiceArrayWithDelims}} \)
\(\newenvironment {NiceMatrix}[1][]{\begin {matrix}}{\end {matrix}}\)
\(\newenvironment {pNiceMatrix}[1][]{\begin {pmatrix}}{\end {pmatrix}}\)
\(\newenvironment {bNiceMatrix}[1][]{\begin {bmatrix}}{\end {bmatrix}}\)
\(\newenvironment {BNiceMatrix}[1][]{\begin {Bmatrix}}{\end {Bmatrix}}\)
\(\newenvironment {vNiceMatrix}[1][]{\begin {vmatrix}}{\end {vmatrix}}\)
\(\newenvironment {VNiceMatrix}[1][]{\begin {Vmatrix}}{\end {Vmatrix}}\)
\(\newcommand {\LWRnicematrixBlock }[1]{#1}\)
\(\def \LWRnicematrixBlockopt <#1>#2{#2}\)
\(\newcommand {\Block }[2][]{\ifnextchar <\LWRnicematrixBlockopt \LWRnicematrixBlock }\)
\(\newcommand {\diagbox }[2]{\begin {array}{l}\hfill \quad #2\\\hline #1\quad \hfill \end {array}}\)
\(\let \hdottedline \hdashline \)
\(\newcommand {\Hline }[1][]{\hline }\)
\(\newcommand {\CodeBefore }{}\)
\(\newcommand {\Body }{}\)
\(\newcommand {\CodeAfter }{}\)
\(\newcommand {\line }[3][]{}\)
\(\newcommand {\RowStyle }[2][]{}\)
\(\newcommand {\LWRSubMatrix }[1][]{}\)
\(\newcommand {\SubMatrix }[4]{\LWRSubMatrix }\)
\(\newcommand {\OverBrace }[4][]{}\)
\(\newcommand {\UnderBrace }[4][]{}\)
\(\newcommand {\HBrace }[3][]{}\)
\(\newcommand {\VBrace }[3][]{}\)
\(\newcommand {\ShowCellNames }{}\)
\(\newcommand {\tabularnote }[2][]{}\)
\(\newcommand {\cellcolor }[3][]{}\)
\(\newcommand {\rowcolor }[3][]{}\)
\(\newcommand {\LWRrowcolors }[1][]{}\)
\(\newcommand {\rowcolors }[4][]{\LWRrowcolors }\)
\(\newcommand {\rowlistcolors }[3][]{\LWRrowcolors }\)
\(\newcommand {\columncolor }[3][]{}\)
\(\newcommand {\rectanglecolor }[4][]{}\)
\(\newcommand {\arraycolor }[2][]{}\)
\(\newcommand {\chessboardcolors }[3][]{}\)
\(\newcommand {\ldots }[1][]{\dots }\)
\(\newcommand {\Cdots }[1][]{\cdots }\)
\(\newcommand {\Vdots }[1][]{\vdots }\)
\(\newcommand {\Ddots }[1][]{\ddots }\)
\(\newcommand {\Iddots }[1][]{\mathinner {\unicode {x22F0}}}\)
\(\newcommand {\Hdotsfor }[1]{\ldots }\)
\(\newcommand {\Vdotsfor }[1]{\vdots }\)
\(\newcommand {\AutoNiceMatrix }[2]{\text {(AutoNiceMatrix #1)}}\)
\(\let \pAutoNiceMatrix \AutoNiceMatrix \)
\(\let \bAutoNiceMatrix \AutoNiceMatrix \)
\(\let \BAutoNiceMatrix \AutoNiceMatrix \)
\(\let \vAutoNiceMatrix \AutoNiceMatrix \)
\(\let \VAutoNiceMatrix \AutoNiceMatrix \)
\(\newcommand {\tcbset }[1]{}\)
\(\newcommand {\tcbsetforeverylayer }[1]{}\)
\(\newcommand {\tcbox }[2][]{\boxed {\text {#2}}}\)
\(\newcommand {\tcboxfit }[2][]{\boxed {#2}}\)
\(\newcommand {\tcblower }{}\)
\(\newcommand {\tcbline }{}\)
\(\newcommand {\tcbtitle }{}\)
\(\newcommand {\tcbsubtitle [2][]{\mathrm {#2}}}\)
\(\newcommand {\tcboxmath }[2][]{\boxed {#2}}\)
\(\newcommand {\tcbhighmath }[2][]{\boxed {#2}}\)
This exam has 26 questions, for a total of 100 points. Place your name on the answersheet (last page). Place proofs on the blank space on the answersheet.
0.1 Multiple Choice: Concepts and terminology
Q1. What is a derivation of \(\phi \) from \(\Gamma \) using \(\mathbf {PD}\)?
-
1. *A derivation of \(\phi \) is a finite string of formulas from a set \(\Gamma \) of \(\mathbf {PL}\) wffs where (i) the last formula in the string is \(\phi \) and (ii) each wff in the set is either a premise, an assumption, or is the result of the preceding wffs and the
deductive apparatus.
-
2. A derivation of \(\phi \) is a finite string of wffs starting with some premises \(\mathbf {A, B, C, \ldots }\) and ending with \(\phi \).
-
3. A derivation of \(\phi \) is a finite string of wffs starting with some premises \(\mathbf {A, B, C, \ldots }\) or assumptions and ending with \(\phi \).
-
4. A derivation of \(\phi \) is an infinite string of formulas from a set \(\Gamma \) of \(\mathbf {PL}\) wffs where (i) the last formula in the string is \(\phi \) and (ii) each wff in the set is either a premise, an assumption, or
is the result of the preceding wffs and the deductive apparatus.
Q2. What is a deductive apparatus for \(\mathbf {PL}\)?
-
1. It is a set of rules that allow individuals to reason from facts (experience) to general laws, e.g. laws of nature.
-
2. It is a set of rules of reason that all people use to reason from one proposition to another, including, but not limited to, hypothetical and probabilistic reasoning.
-
3. a set of rules that state that the rows in a proof need to be numbered.
-
4. *a set of derivation rules that express which wffs \(\phi \) can be written after which wffs \(\psi \) in a derivation.
Q3. In logic, there are two notions of logical consequence (entailment). The first notion is the semantic (model-theoretic) notion, which says that \(\phi \) is a logical consequence of \(\Gamma \) if and only if there is no interpretation of the members of \(\Gamma \) and
\(\phi \) such that all of the members of \(\Gamma \) are true and \(\phi \) is false. What is the other notion of logical consequence?
-
1. the semi-semantic notion of logical consequence (entailment). This notion says that \(\phi \) is a semi-semantic consequence of \(\Gamma \) if and only if it is impossible for the premises to be true and the conclusion false, defined in
terms of truth tables and trees.
-
2. the intuitive notion of logical consequence (entailment). This notion says that \(\phi \) is a logical consequence of \(\Gamma \) if and only if \(\phi \) intuitively follows from \(\Gamma \)
-
3. the legal notion of logical consequence (entailment). This notion says that \(\phi \) is a logical consequence of \(\Gamma \) if and only if \(\phi \) would be accepted in a court of law or some practical matter.
-
4. *the syntactic (proof-theoretic) notion of logical consequence (entailment). This notion says that \(\phi \) is a logical consequence of \(\Gamma \) if and only if there is a derivation of \(\phi \) from \(\Gamma \)
-
5. none of the above
Write the abbreviation of the derivation rule that permits the step in the proof below.
Q4. From \(X\) to \(X\) --- Answer: \(R\)
Q5. From \(A\wedge X\) to \(X\) --- Answer: \(\wedge E\)
Q6. From \(\neg A\) and \(B\) to \(\neg A\wedge B\) --- Answer: \(\wedge I\)
Q7. From \(\neg \neg B\wedge \neg X\) to \(\neg \neg B\) --- Answer: \(\wedge E\)
Q8. From \(Z\rightarrow M\) and \(\neg Q\) to \((Z\rightarrow M)\wedge \neg Q\) --- Answer: \(\wedge I\)
Q9. From \(\neg Q\rightarrow S\) and \(\neg Q\) to \(S\). --- Answer: \(\rightarrow E\)
Q10. From \((B\rightarrow Q)\leftrightarrow M\) and \(M\) to \(B\rightarrow Q\) --- Answer: \(\leftrightarrow E\)
Q11. From \(S\rightarrow L\) and \(\neg L\) to \(\neg S\) --- Answer: \(MT\)
Q12. From \(X\rightarrow \neg Z\) and \(\neg Z\rightarrow M\) to \(X\rightarrow M\) --- Answer: \(HS\)
Q13. From \(S\wedge T\) to \(X\vee (S\wedge T)\) --- Answer: \(\vee I\)
Q14. From \(V\vee P\) and \(\neg P\) to \(V\) --- Answer: \(DS\)
Q15. From \(A\rightarrow B\) to \(\neg A\vee B\) --- Answer: \(IMP\)
Q16. From \(\neg (A\vee B)\) to \(\neg A\wedge \neg B\) --- Answer: \(DeM\)
Q17. From \(W\) to \(\neg \neg W\) --- Answer: \(DN\)
Q18. What rule allows you to derive \(\neg A\) from (1) an assumption \(A\) and (2) \(B\) and \(\neg B\) within the subproof started by \(A\)? --- Answer: \(\neg I\)
Q19. What derivation rule is best described as follows: if \((P\rightarrow Q)\wedge Q\) is on a line of the proof, then it is legitimate to derive \(P\rightarrow Q\) on a line and it is legitimate to derive \(Q\) on another line. --- Answer: \(\wedge E\)
Q20. From \(A\vee B\) and two subproofs \(C\) is derived. The first subproof is where \(A\) is assumed and \(C\) is derived. The second subproof is where \(B\) is assumed and \(C\) is derived. --- Answer: \(\vee E\)
0.2 Proofs
Solve the following proofs. Be sure to setup the proof correctly, number all lines, and clearly indicate how each line is justified using the rules from the deductive apparatus.
Q21. \((A\wedge \neg W)\wedge \neg S, T\wedge \neg R, S\vee R \vdash \neg W\wedge \neg R\)
--- Answer: \((A\wedge \neg W)\wedge \neg S, T\wedge \neg R, S\vee R \vdash \neg W\wedge \neg R\)
Q22. \((P\vee \neg W)\rightarrow \neg B, \neg W\vdash \neg L\vee \neg B\)
--- Answer: \((P\vee \neg W)\rightarrow \neg B, \neg W\vdash \neg L\vee \neg B\)
Q23. \(W\rightarrow D, \neg C\rightarrow D, W\vee \neg C\vdash \neg \neg D\)
--- Answer: \(W\rightarrow D, \neg C\rightarrow D, W\vee \neg C\vdash \neg \neg D\)
Q24. \(B\leftrightarrow \neg B\vdash \neg (A\vee C)\)
--- Answer: \(B\leftrightarrow \neg B\vdash \neg (A\vee C)\)
Q25. \(\vdash \neg (W\rightarrow Q)\rightarrow \neg Q\)
--- Answer: \(\vdash \neg (W\rightarrow Q)\rightarrow \neg Q\)
Q26. \(\vdash \neg (P\vee Q)\rightarrow (R\rightarrow \neg Q)\)
--- Answer: \(\vdash \neg (P\vee Q)\rightarrow (R\rightarrow \neg Q)\)
