Exam 2 - Practice Exam
July 25, 2025
This exam has 34 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 Definitions, Concepts, and Basic Mechanics
Q1. What is a decision procedure?
-
1. It is the actual decision a human being makes with respect to whether an argument has a particular logical property, e.g. judging an argument to be valid or invalid.
-
2. It is a step-by-step procedure used by logicians to translate a sentence from a natural language (e.g. English) into a formal language (e.g. propositional logic).
-
3. It is a psychological procedure whereby people made decisions about whether an argument is good or bad.
-
4. *A mechanical method that determines (in a finite number of steps) whether a proposition, set of propositions, or argument has a certain logical property.
Q2. A set of wffs \(\{A, B, C, D\}\) semantically entails \(Q\) if and only if what? That is, \(A, B, C, D\models Q\) if and only if what?
-
1. there is an interpretation such that each of the members (wffs) of \(\{A, B, C, D\}\) are true and \(Q\) is false.
-
2. there is at least two interpretations such that each of the members (wffs) of \(\{A, B, C, D\}\) are true and \(Q\) is false.
-
3. there is no interpretation such that each of the members (wffs) of \(\{A, B, C, D\}\) are false and \(Q\) is true.
-
4. *there is no interpretation such that each of the members (wffs) of \(\{A, B, C, D\}\) are true and \(Q\) is false.
Q3. What advantage does the truth table and truth tree tests have over the imagination test for validity?
-
1. the truth table/tree tests are poetic; they take into account the spirit of human nature
-
2. If an argument is deductively valid in English, then the truth table/tree method will always correctly determine whether it is (in fact) valid in the language of propositional logic (PL).
-
3. If an argument is persuasive in English, then the table/tree methods will tell us whether we ought to be persuaded by them.
-
4. *The truth table/tree tests are mechanical (decision procedures)
Q4. How many truth tree tests are required to determine whether a wff is contingent? Write the number. --- Answer: 2
Q5. How many truth tree tests are required to determine if an argument is valid (semantic entailment). Write the number. --- Answer: 1
0.2 Determining the truth of wffs
Determine the truth value (write T or F on the answersheet). Note that in some cases you don't need to know all of the truth values for some (or all) of the propositional letters.
Q6. Suppose \(\mathscr {I}(Q)=T\), what is \(v(\neg \neg Q)\)? --- Answer: T
Q7. Suppose \(\mathscr {I}(P)=F\) and \(\mathscr {I}(Q)=F\), what is \(v(\neg P\rightarrow \neg Q)\)? --- Answer: T
Q8. Suppose \(\mathscr {I}(P)=T\) and \(\mathscr {I}(Q)=F\), what is \(v(P\leftrightarrow \neg Q)\)? --- Answer: T
Q9. Suppose \(\mathscr {I}(P)=T, \mathscr {I}(Q)=F, \mathscr {I}(R)=F\), what is \(v(P\vee \neg Q)\vee \neg R\)? --- Answer: T
Q10. Suppose \(\mathscr {I}(P)=T, \mathscr {I}(Q)=F, \mathscr {I}(R)=F\), what is \(v(P\rightarrow Q)\vee \neg R\)? --- Answer: T
Q11. What is the truth value of \(A\vee \neg A\) --- Answer: T
Q12. Suppose \(\mathscr {I}(Q)=F\), what is \(v(Q\wedge R)\)? --- Answer: F
Q13. What is the truth value of \(P\rightarrow \neg \neg P\) --- Answer: T
Q14. \(\mathscr {I}(P)=T\), \(\mathscr {I}(R)=F\), and \(\mathscr {I}(Q)=F\), determine the truth value of \((P\rightarrow Q)\wedge \neg R\) --- Answer: F
Q15. Suppose \(\mathscr {I}(R)=F\), what is \(v(P\leftrightarrow Q)\wedge R\)? --- Answer: F
Q16. What is the truth value of \(\neg A\wedge A\)? --- Answer: F
Q17. Suppose \(\mathscr {I}(Q)=T\), what is \(v(A\wedge \neg Q)\)? --- Answer: F
0.3 Truth-tree decomposition rules
Write the abbreviation (e.g. \(\wedge D\)) for the decomposition rule that should be used on wffs below. Indicate only the first decomposition rule that would be used.
Q18. \(\neg A\vee B\) --- Answer: \(\vee D\)
Q19. \(\neg A\vee \neg Q\)? --- Answer: \(\vee D\)
Q20. \(A\wedge \neg B\) --- Answer: \(\wedge D\)
Q21. \(\neg \neg Z\) --- Answer: \(\neg \neg D\)
Q22. \(\neg A\rightarrow \neg B\) --- Answer: \(\rightarrow D\)
Q23. \(\neg A\leftrightarrow B\) --- Answer: \(\leftrightarrow D\)
Q24. \(\neg B\wedge \neg R\) --- Answer: \(\wedge D\)
Q25. \(\neg \neg (Z\vee R)\) --- Answer: \(\neg \neg D\)
Q26. \(\neg (Z\wedge R)\) --- Answer: \(\neg \wedge D\)
Q27. \(\neg (R\leftrightarrow \neg R)\) --- Answer: \(\neg \leftrightarrow D\)
Q28. \(\neg S\rightarrow R\) --- Answer: \(\rightarrow D\)
Q29. \(\neg R\leftrightarrow \neg R\)? --- Answer: \(\leftrightarrow D\)
Q30. \(\neg (S\rightarrow \neg \neg Y)\)? --- Answer: \(\neg \rightarrow D\)
0.4 Truth table and tree Construction
Q31. On the answer sheet, construct a truth table for the following proposition and determine whether it is a contingency, tautology, or contradiction: \(P\rightarrow \neg (Q\wedge \neg P)\). To receive full credit, you must (i) construct the entire truth table (each row and each T and F), (ii) label whether it is a contingency, tautology, or contradiction, and (iii) clearly explain why the table shows the wff in question has the property you say it does. --- Answer: The wff is a tautology. Notice that under the main operator, there are only Ts, indicating that this wff is true under every interpretation.
| P | Q | P | \(\rightarrow \) | \(\neg \) | (Q | \(\wedge \) | \(\neg \) | P) | |
| T | T | T | T | T | T | F | F | T | |
| T | F | T | T | T | F | F | F | T | |
| F | T | F | T | F | T | T | T | F | |
| F | F | F | T | T | F | F | T | F |
Q32. On the answer sheet, construct a truth tree for the following set of wffs and determine whether the set is a contingency, tautology, or contradiction: \(\neg (A\rightarrow C)\wedge \neg (D\wedge \neg Q)\). To receive full credit, you must (i) construct the entire truth tree, (ii) label whether it is a contingency, tautology, or contradiction, and (iii) explain your answer (state why it is the a contingency, tautology, or contradiction). --- Answer: Answer may vary, but the tree for this wff shows the wff is a contingency. It is a contingency since the tree test for contradiction shows that it is not a contradiction, while the tr ee test for tautology shows that it is not a tautology. Since a wff is exactly one of the following (contingency, tautology, contradiction), the wff is a contingency.
Test for contradiction:
Test for tautology:
Q33. On the answer sheet, determine whether the following set of wffs is consistent or inconsistent using either a truth table or a truth tree: \((S\wedge P)\rightarrow (Q\rightarrow R), L\vee (\neg M\rightarrow E), P\wedge (L\wedge \neg P), (A\vee B)\wedge (C\wedge D)\). To receive full credit, you must (i) construct the truth table/tree to a degree to clearly show that the property (full completed row, tree decomposed sufficiently), (ii) label whether it is a consistent or inconsistent, and (iii) if the set of wffs is consistent, write out the interpretation or identify the row (e.g. \(\mathscr {I}(P)=T, \mathscr {I}(Q)=F\)) demonstrating consistency. --- Answer: The set is inconsistent. It is shown to be inconsistent because the tree closes, indicating that there is no interpretation where all of the wffs are true. If you chose to do a truth table, then you must provide a table for each interpretation. Since there are 10 distinct propositional letters, your tree should have \(2^{10}\) rows. If you chose to do a tree, then you must show that the tree closes (similar to the tree below):
Q34. On the answer sheet, construct either a truth table or a truth tree for the following argument: \(\neg (P\rightarrow \neg Q), P\vee Q \models S\vee T\). To receive full credit, you must (i) construct the entire truth table or tree, (ii) label whether it is a valid or invalid (that is, entailment of non-entailment), and (iii) if the argument is invalid, identify write out the interpretation (e.g. \(\mathscr {I}(P)=T, \mathscr {I}(Q)=F\)) demonstrating its invalidity.
--- Answer: The argument is invalid or a case of non-entailment. If creating a table, then a table of at least 16 rows is required and the table must provide a completed row where the premises are true and the conclusion is false. In the case of a tree, the following is a possible answer:
Since it is invalid, an interpretation must be provided. Here is the only interpretation: \(\mathscr {I}(Q)=T, \mathscr {I}(P)=T, \mathscr {I}(T)=F, \mathscr {I}(S)=F\)
0.5 Extra Credit Questions
Bonus Question: If \(\phi \rightarrow \psi \) is a contradiction, is it the case that \(\phi \not \models \psi \)? Provide a proof of your answer. --- Answer: Yes. If \(\phi \rightarrow \psi \) is a contradiction, then \(\phi \not \models \psi \). If \(\phi \rightarrow \psi \) is a contradiction, then for every interpretation, \(v(\phi )=T\) and \(v(\psi )=F\). If for every interpretation \(v(\phi )=T\) and \(v(\psi )=F\), then there is at least one interpretation where \(v(\phi )=T\) and \(v(\psi )=F\). Therefore \(\phi \not \models \psi \).
Bonus Question: Instead of T and F, use 1 and 0. Create a valuation function for the conjunction, conditional, and negation. In doing this, express it using 1, 0, possibly basic arithmetic, and \(\max \), \(\min \), or \(abs\) function. For example, the valuation function for disjunction can be expressed as follows: \(v(\phi \vee \psi )=\max (\phi , \psi )\). This takes the maximum value between \(\phi \) and \(\psi \). --- Answer: Need to get at least two of the following correct: \(v(\phi \wedge \psi )=\min (\phi , \psi )\), \(v(\phi \rightarrow \psi )=\max (\phi -1, \psi )\), \(v(\neg (\phi )) = |{(1-\phi )}|\)
0.6 Table and Tree Rules
