3.7. References 69
(b)Demonstrate that this set of specifications is satisfiable by describing a single
truth assignment for the variablesL;Q;B;Nand verifying that under this assign-
ment, all the specifications are true.
(c)Argue that the assignment determined in part (b) is the only one that does the
job.
Problems for Section 3.4
Practice Problems
Problem 3.13.
A half dozen different operators may appear in propositional formulas, but just
AND,OR, andNOTare enough to do the job. That is because each of the operators
is equivalent to a simple formula using only these three operators. For example,
AIMPLIESBis equivalent toNOT.A/ORB. So all occurences ofIMPLIESin a
formula can be replaced using justNOTandOR.
(a)Write formulas using onlyAND,OR,NOTthat are equivalent to each ofAIFFB
andAXORB. Conclude that every propositional formula is equivalent to anAND-
OR-NOTformula.
(b)Explain why you don’t even needAND.(c)Explain how to get by with the single operatorNANDwhereANANDBis
equivalent by definition toNOT.AANDB/.
Class Problems
Problem 3.14.
The propositional connectiveNORis defined by the rule
PNORQWWD.NOT.P/AND NOT.Q//:Explain why every propositional formula—possibly involving any of the usual op-
erators such asIMPLIES,XOR,... —is equivalent to one whose only connective is
NOR.
Problem 3.15.
Explain how to find a conjunctive form for a propositional formula directly from a
disjunctive form for its complement.