PHIL012 – Symbolic
Exam 2 – 3/23/2001 NAME______
Problems 1-17 are 4 points each.
1. Which of the following statements are logically equivalent to one another?
I. (ØHome(Max) Ù ØHome(Claire)) Ú Happy(Carl)
II. Ø((Home(Max) Ù Home(Claire)) Ù ØHappy(Carl))
III. (Happy(Carl) Ú ØHome(Max)) Ù (ØHome(Claire) Ú Happy(Carl))
IV (ØHome(Max) Ù ØHome(Claire)) Ú (Happy(Carl) Ú Happy(Carl))
a. I and II only.
b. II and III only.
c. I, II, and III
d. I, III, and IV only
e. I, II, III, and IV
The answer is d. While II is very similar to I, it is an incorrect application of DeMorgan’s Theorem because the connective within the parenthesis was not changed.)
2. Which of the following are logically equivalent to the following statement?
(ØØP Ú Q) Ù Ø(S Ú T)
I. (ØS Ù ØT) Ù (P Ú Q)
II. ((ØØP Ú Q) Ù (ØS Ú T)) Ú R
III. (R Ù M) Ú ((P Ú Q) Ù Ø(S Ú T))
a. I only
b. I and II only
c. I and III only
d. I, II, and III
e None of the above.
The answer is a. You get I by applying DeMorgan’s Theorem to Ø(S Ú T), double negation to ØØP, and applying commuativity to the whole thing. II is a valid logical step but is not logically equivalent. This is because if (ØØP Ú Q) Ù Ø(S Ú T) happens to be false, the truth value of II will depend on the truth value of R, and is not therefore always identical. The same reasoning prevents III from being logically equivalent.
3. Which of the following is a negation normal form of the following sentence?
Ø(A Ù B) Ú C
I. Ø(A Ù B) Ú C
II. (ØA Ù ØB) Ú C
III. Ø((A Ù B) Ú ØC)
IV. ØA Ú Ø B Ú ØC
a. I and II only
b. II and III only
c. I, II, and III only
d. I, II, III, and IV
e. None of the above.
The answer is e, none of the above. I is not negation normal form because there is a Ø outside of parentheses. II is not logically equivalent, being a misapplication of DeMorgan’s Theorem. III is not NNF because of the Ø outside of the parentheses, even though it is a correct application of DeMorgan. IV is not logically equivalent, therefore not a NNF of the first statement.
4. Which of the following is a disjunctive normal form of the following sentence?
(P Ú Q) Ù R
I. (R Ú P) Ù (Q Ú R)
II. (R Ù P) Ú (Q Ù R)
III. (P Ù Q) Ú R
a. I only
b. II only
c. III only
d. I and II only
e. I and III only
The answer is b, II only. I and III are incorrect attempts at distribution.
5. Which of the following is a conjunctive normal form of the following sentence?
Ø(A Ú B) Ù C
I. Ø(A Ú B) Ù C
II. ØA Ù ØB Ù C
III. (C Ú Ø A) Ù (C Ú ØB)
a. I only
b. II only
c. III only
d. I and II only
e. I and III only
The answer is b. By definition, anything in CNF is in NNF (because any NF must be a sequence of literals or negations of literals), so I isn’t in CNF. III is just wrong, having been an attempt to apply DeMorgan’s theorem to Ø(A Ú B), but not realizing that this leads to a statement with all Ù’s, thus making the further attempt at distribution wrong.
Choose the best translation of the following sentences into FOL.
6. Either Claire is home or Mat is unhappy.
a. Home(Claire) Ú Happy(Mat)
b. Home(Claire) Ù ØHappy(Mat)
c. Home(Claire) Ú ØHappy(Mat)
d. Ø(ØHome(Claire) Ù Happy(Mat)
e. ØHappy(Mat) Ú Home(Claire)
The answer is c. Answer a says that Mat is happy. Answer b has different truth conditions, requiring Claire to be at home and Mat to be unhappy. Answers d and e are logically equivalent, but bad translations since they modify the word order or express the converse of the original statement. Thus, it is important to remember my insistence that a good translation is as literal as possible and preserves word order as much as possible.
7. c is a cube and is large, but a is either a tetrahedron or a dodecahedron.
a. Large(Cube(c)) Ù (Tet(a) Ú Dodec(a))
b. (Cube(c) Ù Large(c)) Ú (Tet(a) Ú Dodec(a))
c. (Cube(c) Ù Large(c)) Ù (Tet(a) Ú Dodec(a))
d. All of the above translate the sentence equally well.
e. None of the above is an accurate translation.
The answer is c. For this one it is important to remember that but is best expressed by Ù, not Ú, thus b is out. Answer a does not have good syntax.
8. Either Max is happy and Claire is unhappy or Carl is home and is either fishing or skating.
a. (Happy(Max) Ù ØHappy(Claire)) Ú (Home(Carl) Ù (Fishing (Carl) Ú Skating(Carl)))
b. (Happy(Max) Ù ØHappy(Claire)) Ú ((Home(Carl) Ù Fishing(Carl)) Ú (Home(Carl) Ù Skating(Carl)))
c. ((Happy(Max) Ú Happy(Claire)) Ú ((Home(Carl) Ù (Fishing(Carl) Ú Skating(Carl)))
d. All of the above translate the sentence equally well.
e. None of the above are accurate translations.
The answer is a. Although b is logically equivalent by distribution, it is not the most literal translation. Answer c says that Claire is happy and she is unhappy.
9. Which of the following express valid inference steps?
I. From P Ú Q and ØP infer Q.
II. From P Ú Q and Q infer ØP.
III. From Ø(P Ú Q) infer ØP.
a. I only
b. I and II only
c. I and III only
d. I, II, and III
e. None of the above are valid inference steps.
The answer is c. I follows from the definition of Ú. You can see that III follows by applying DeMorgan’s Theorem to Ø(P Ú Q) to get ØP Ù ØQ and seeing that ØP follows from this. II does not follow because knowing that Q is true doesn’t tell us anything about the truth value of P. We only know the truth value of the other disjunct if we know that one of them is false because of the definition of Ú.
10. Which of the following express valid inference steps?
I. From Ø(P Ù Q) and P infer ØQ.
II. From Ø(P Ù Q) infer ØP.
III. From P Ù Q and ØP infer Q.
a. I only
b. I and II only
c. I and III only
d. I, II, and III
e. None of the above are valid inference steps.
The answer is c. By applying DeMorgan’s Theorm to Ø(P Ù Q) we get ØP Ú ØQ. Knowing that P is true implies that ØP is false. But if ØP is false, ØQ must be true. II does not follow for the same reason that II in #9 is invalid, which can be seen once we apply DeMorgan’s Theorem. III is a valid inference for two reasons. First, if we know P Ù Q, we automatically know Q, based on the truth table for Ù. Second, P Ù Q and ØP imply a contradiction, namely P Ù ØP, from which we can infer anything, including Q.
Choose the best statements to describe the following sentences:
Assume that all sentences like A, B, and C are atomic sentences, are logically independent, and each can be either true or false. All sentences such as Cube(a) follow the rules of Tarski's world
The best way to do these problems is to do truth tables for them and then to notice any logical dependencies between the terms, such as a cannot be a Cube and a Tetrahedron at the same time, thus ruling out spurious rows.
11. (Cube(a) Ù Tet(a)) Ú Cube(b)
a. The sentence is unsatisfiable.
b. The sentence is a tautology.
c. The sentence is logically true.
d. The sentence is tautological and logically true.
e. The sentence is neither unsatisfiable, tautological, nor logically true.
( Cube(a) / Ù / Tet(a) ) / Ú / Cube(b)T / T / T / T / T
T / T / T / T / F
T / F / F / T / T
T / F / F / F / F
F / F / T / T / T
F / F / T / T / F
F / F / F / T / T
F / F / F / F / F
Here we note that the highlighted rows are spurious because a can’t be both a tetrahedron and a cube at the same time. However, the fact that these rows are spurious doesn’t make any difference to the type of claim that the whole sentence is making. This is because before we rule out our spurious rows the column below the major connective contains both T’s & F’s, meaning that the statement is neither unsatisfiable nor a tautology. After we rule out the spurious rows, the column below the major connective still contains both T’s & F’s, meaning that the statement isn’t unsatisfiable, a tautology, or logically true. So, the answer is e.
12. (A Ú ØA) Ú B
a. The sentence is unsatisfiable.
b. The sentence is a tautology.
c. The sentence is logically true.
d. The sentence is tautological and logically true.
e. The sentence is neither unsatisfiable, tautological, nor logically true.
( A / Ú / Ø / A ) / Ú / BT / T / F / T / T / T
T / T / F / T / T / F
F / T / T / F / T / T
F / T / T / F / T / F
To make this truth table, we count the number of atomic sentence (2, A & B) and raise 2 to that power (2), yielding 4 rows. Having assigned the truth tables, we inspect the column containing the major connective and notice that it is all T’s. This means that the statement is a tautology. Since being a tautology is a more stringent condition, every tautology is also logically true. The best answer (which is what the directions said to choose) is therefore d.
13. Ø(Cube(a) Ù Tet(a)) Ú Cube(b)
a. The sentence is unsatisfiable.
b. The sentence is a tautology.
c. The sentence is logically true.
d. The sentence is tautological and logically true.
e. The sentence is neither unsatisfiable, tautological, nor logically true.
Ø / ( Cube(a) / Ù / Tet(a) ) / Ú / Cube(b)F / T / T / T / T / T
F / T / T / T / F / F
T / T / F / F / T / T
T / T / F / F / T / F
T / F / F / T / T / T
T / F / F / T / T / F
T / F / F / F / T / T
T / F / F / F / T / F
The answer is c. Rows 1 and 2 turn out to be spurious because it is not possible for a to be a cube and a tetrahedron at the same time. Before we ruled out these rows, the statement appeared to be merely satisfiable, but not a tautology, since the column with the major connective contained both T’s & F’s. However, by ruling out the first two rows, we see that due to the logical dependences of the terms, we are left with all T’s, thus making the statement logically true.
For the following questions, use these rules:
Conjunction Elimination (Ù Elim) Disjunction Elimination (Ú Elim)
Conjunction Introduction (Ù Intro) Disjunction Introduction (Ú Intro)
Negation Elimination (Ø Elim) Negation Introduction (Ø Intro)
Distribution of Ù over Ú Distribution of Ú over Ù
DeMorgan's Theorems (DeM) Reiteration (Reit)
Consider the following proof:
1. Ø(P Ù Q)
2. P Ú R
3. Q Ú R / \R
4. ØP Ú ØQ
5. ØP
6. P
7. ØR
8. P Ù ØP
9. R
10. R
11. R
12. R
13. ØQ
14. Q
15. ØR
16. ?
17. R
18. R
19. R
20. R
21. R
14. Lines 5 and 13 are
a. Invalid
b. the assumptions for Ú Elim
c. the assumptions for Ú Intro
d. the assumptions for two Ø Intro's
e. None of the above.
The answer is b. The Ú we are eliminating is on line 4 and steps 5-12 and 13-20 independently prove R by assuming one side of the disjunction, thus proving that R follows from the disjunction itself.
15. Lines 6, 10, 14 and 18 are
a. Invalid
b. the assumptions for Ú Elim
c. the assumptions for Ú Intro
d. the assumptions for two Ø Intro's
e. None of the above.
The answer is b. Lines 6 and 10 eliminate the Ú on line 2. Lines 14 and 18 eliminate the Ú on line 3.
16. The rule for line 4 is
a. Invalid
b. Ø Elim, 2
c. DeM, 1
d. Ú Elim, 7
e. None of the above.
The answer is c.
17. The missing step (line 16) should be:
a. P Ú ØP Tautology
b. P Ù ØP Ù Intro, 5, 6
c. ØR ØIntro
d. ØR Ú Q Ú Intro, 15