From the Text

Complete the following questions from the text:

• Section 1.2: 6, 12(a,c), 18. [In these questions “show that” means do a formal proof, not a truth table, unless it specifically says “with a truth table”. A formal proof is with one logical step on each line, and the reason given.]
• Section 1.3: 12, 22.
• Section 1.4: 4 (a,c,e), 8, 32 (a,b,d; no need for an equivalence proof: just state the negation as specified).
• Section 1.5: 4, 14(a,b,d).
• Section 1.6: 6.

Questions

1. Show that \((p\wedge\neg q) \vee \neg(p\rightarrow \neg q)\) is equivalent to \(p\) (with a formal proof, not a truth table).
2. Using predicates \(P(x)\) for “\(x\) is from Portugal”, \(Q(x)\) for “\(x\) is from Qatar”, and \(K(x,y)\) for “\(x\) knows \(y\)”, translate these sentences into logical expressions:
   1. “John is from Portugal.”
   2. “Someone is from Portugal.”
   3. “If a person is from Portugal, they are not from Qatar.”
   4. “There is a person from both Portugal and Qatar.”
   5. “There are people from both Portugal and Qatar (but not necessarily the same people).”
   6. “Everyone from Qatar knows someone from Portugal.”
   7. “A Qatari (person from Qatar) knows every Portuguese person.”
   8. “Some Qatari and Portuguese people know each other.”
   9. “No Qatari person knows a Portuguese person.”
3. For each step in the proof below, give the rule of inference that justifies it. (That is, fill in the “modus ponens” or whatever goes beside that line.) If any of the steps are invalid, state why.

   We are given as hypotheses these statements: \[\forall x (Q(x)\rightarrow (P(x)\wedge R(x))\\ \forall x (Q(x)\wedge S(x))\,.\]

   Proof:

   1. \(\forall x (Q(x)\rightarrow (P(x)\wedge R(x))\)
   2. \(Q(a)\rightarrow (P(a)\wedge R(a))\)
   3. \(\forall x (Q(x)\wedge S(x))\)
   4. \(Q(a)\wedge S(a)\)
   5. \(S(a)\)
   6. \(Q(a)\)
   7. \(P(a)\wedge R(a)\)
   8. \(R(a)\)
   9. \(R(a)\wedge S(a)\)
   10. \(\forall x (R(x)\wedge S(x))\)