ITEC 122 2008fall ibarland

home—info—lectures—exams—archive

hw01
Propositional Logic, Boolean Algebra

Although you are welcome to typeset your work nicely (using Microsoft Word or LaTeX or whatever to get nice logic symbols), it's probably much easier to write formulas by hand.

1. p.16 #10: Let p, q, and r be the propositions
   • p: You get an A on the final exam
   • q: You do every exercise in this book
   • r: you get an A in this class
   Write theses propositions using p, q, and r and logical connectives.
   1. You get an A in this class, but you do not do every exercise in this book
   2. You get an A on the final, you do every exercise in this book, and you get an A in this class
   3. To get an A in this class it is necessary for you to get an A on the final.
   4. You get an A on the final, but you don’t do every exercise in this book; nevertheless, you get an A in this class.
   5. Getting an A on the final and doing every exercise in this book is sufficient for getting an A in this class.
   6. You will get an A in this class if and only if you either do every exercise in this book or you get an A on the final.

2. We explore how propositional logic might be a way to talk about web-pages.

   It just so happens that all the web pages in Logiconia which contain the word “Poppins” also contain the word “Mary”. Write a formula (a query) expressing this. Use the proposition Poppins to represent the concept “the web page contains 'Poppins'” (and similarly for Mary).

   Sample solution: (Poppins→Mary).
   (Any page which doesn't satisfy this formula is definitely non-Logiconian.)

   It further happens to be the case that:

   1. Whenever a Logicanian page contains the word “weasel”, then it also contains either “words” or “eyed”; and whenever a Logiconian page contains the word “mongoose”, it does not also contain the word “weasel”; and finally, all Logiconian pages contain the word “Logiconia”, rather patriotically. Write a formula expressing all this. (Your formula will involve six propositions -- weasel, etc.. Try to find a formula which mirrors the English wording above.)

   2. If a web page in Logiconia does not contain “weasel”, does it necessarily contain “mongoose”?

   3. Let's go meta for a moment: What can you conclude about this web page? (Yes, this one you're looking at now -- the one with the homework problems.) Why?

3. Rosen p.18, #24d,e,f: Construct a truth table for of these compound propositions.
   4. (p ∧ q) → (p ∨ q)
   5. (q → p) ↔ (p ↔ q)
   6. (p ↔q) ⊕ (p ↔ q)
      (where “⊕” stands for exclusive-or (“xor”) — one or the other but not both)
   Which of these — if any — are tautologies?
4. p.28 #18 (5ed: p.26 #12): Show that (p → q) and (¬q → ¬p) are logically equivalent.
5. TeachLogic exercises I: #20 (equivalences via truth-tables)
   Let φ = ( (a∨c) ∧ (b→c) ∧ (c→a) ),
   ψ = ( (b→c) ∧ a ), and
   ω = ( (a∨c) ∧ (b→c) ).
   Show that φ≡ψ, but they aren't equivalent to ω.
6. Optional: TeachLogic exercises I: #4 (hidden premises in a real-world argument)

If you see a few other problems in Rosen which catch your eye, and you'd like to do them for extra credit, you are welcome to (though you can ask me for how much; extra-credit is harder to earn point-per-point than regular credit).

home—info—lectures—exams—archive

©2008, Ian Barland, Radford University Last modified 2008.Sep.10 (Wed)

Please mail any suggestions (incl. typos, broken links) to iba�rlandrad�ford.edu