Chapter Review 151- Form a truth table for the proposition p V -,(p A q).
- Use the substitution rule with p --* q for p, and prove that the result is a tautology for
-q --* (q -- p)- Prove the following identities for a boolean algebra:
(a) (-'pVq)A(pV-q)=pAqV(-pA--q)
(b) -ppv(qAr) v(pVq)A(-'pVr)-=--pVr
(c) -(-(pvq)A--(qvr))V(qAr)=pvq
- Draw combinatorial circuits that realize the following formulas:
(a) (pAq)V(qAr)V(pA-r)
(b) -((p A q) V p) V (p A q)
2.9.4 Using Discrete Mathematics in Computer Science
- We built formulas with the logical operators A, V, -, --, and and the constants
T and F. In designing circuits, we described gates for only three connectives: A, V,
and -. Computer hardware designers might want to make as few kinds of gates as
possible. Do they really need a --- gate? (The answer turns out to be "no," but how
do you know that?) Could they get along with fewer than three types of gates? A set
of logical operators is called complete if every well-formed formula of propositional
logic is equivalent to a well-formed formula using connectives from the set.
(a) Find a formula equivalent to a -+ (b A C A d) using only the connectives - and
A (and not the constants T and F). Find the shortest such formula; does it have
more or fewer symbols than the formula a -+ (b A c A d)?
(b) Show that the set {-, A} of operators is complete.
(c) Find a formula equivalent to a --+ (b A c A d) using only the connectives - and
-- (and not the constants TRUE and FALSE). Find the shortest such formula;
does it have more or fewer symbols than the formula a -+ (b A C A d)?
(d) Show that the set {-, -+ } of operators is complete.
(e) Find a formula equivalent to a -+ (b A c A d) using only the connective --* and
the constant FALSE. Find the shortest such formula; does it have more or fewer
symbols than the formula a -- (b A C A d)?
(f) Show that the set (FALSE, --+I is complete. - See the definition of "complete set of operators" in Exercise 1. This problem shows
that the engineers need build only one type of gate.
(a) NAND has the truth table
p q NAND(p, q)
T T F
T F T
F T T
F F TShow that the set {NAND} is a complete set of operators.