Discrete Structures
HW #2
§1.2: Propositional Equivalences
Last Update: 10 September 2010, 7:52
P.M.
Note:
or
material is highlighted

All exercises come from the Rosen text.
Each HW problem's solution should consist of:
All solutions must be handwritten.
PUT YOUR NAME, DATE, & RECITATION SECTION AT TOP RIGHT OF
EACH PAGE;
STAPLE MULTIPLE PAGES 
 (3 points for truth table; 3 points for explanation; 6 points
total)
p. 28: 4a
 Use truth tables to show that 2 propositions are logically
equivalent.
 You must not only show the complete truth table,
including all intermediate columns,
but you must also say why or how the truth table shows that the two
propositions are equivalent.
 (12 points)
p. 28: 8b
 Compute the negation of an English sentence.
 Do this problem in 4 steps (3 points each;
you do not have to construct a truth table, however!):
 (3 points)
Identify the atomic propositions and choose
letters to represent them.
 (3 points)
Represent the compound proposition that is given in the
problem (i.e., translate it from English to the language
of propositional logic).
 (3 points)
Use DeMorgan's Laws (and any other logical equivalences
from Table 6 in the text) to construct its negation.
 (3 points)
Translate back into English.
 (24 points)
to correct
page:
p. 29: 44
 Show that negation (¬) and conjunction (∧) are "functionally complete",
i.e.,
that only the two connectives ¬ and ∧
are needed in order to represent any molecular proposition.
(I.e., show that you don't need to use ∨, ⊕, →,
or ↔.)
 Be sure to read the paragraph on p. 29 between
problems 42 and 43 that defines "functionally complete"
 To show that these two connectives are functionally
complete, you need to do two things:
 (3 points each; total = 12 points)
For any proposition containing ∨, →, ↔,
or ⊕,
find a logically equivalent
proposition that only contains ¬ and ∧.
 (3 points each; total = 12 points)
Construct truth tables that show the following:
 Any proposition of the form
"(p ∨ q)" can be written as a logically equivalent
proposition using only ¬ and ∧ (using the hint in the text).
 Any proposition of the form
"(p → q)" can be written as a logically equivalent
proposition using only ¬ and ∧.
 Hint: Either directly show
that "(p → q)"
can be written as a logically equivalent
proposition using only ¬ and ∧,
or else show that it can be
written as a logically equivalent
proposition using only ¬ and ∨,
and then use the equivalence in part (i)
 Any proposition of the form
"(p ↔ q)" can be written as a logically equivalent
proposition using only ¬ and ∧.
 Hint: Show
that "(p ↔ q)"
can be written as a logically equivalent
proposition using only ∧ and →.
Then, using previous equivalences,
show how it can be rewritten using
only ¬ and ∧.
 Any proposition of the form
"(p ⊕ q)" can be written as a logically equivalent
proposition using only ¬ and ∧.
 Hint: Show
that "(p ⊕ q)"
can be written as a logically equivalent
proposition using ¬, ∨, and ∧.
Then use previous equivalences to
show that you can rewrite it using
only ¬ and ∧.
 (3 points each; total = 6 points)
p. 29: 48, 50b
Total points = 48
Tentative grading scheme:
A 4648
A 4345
B+ 4142
B 3840
B 3537
C+ 3334
C 2732
C 2226
D+ 1721
D 916
F 0 8
DUE: AT THE BEGINNING OF LECTURE, FRI., SEP. 17 
*
UB philosophy Prof. Randall R. Dipert is the "Charles Sanders Peirce
Professor of American Philosophy".
Text copyright © 2010 by William J. Rapaport
(rapaport@buffalo.edu)
Cartoon links and screencaptures appear here for your enjoyment.
They are not meant to infringe on any copyrights held by the creators.
For more information on any cartoon, click on it, or contact me.
http://www.cse.buffalo.edu/~rapaport/191/F10/hw02.html20100910