22
Formal Logic
41. Use algorithm TautologyTest to prove that the following expressions are tautologies.
a. [B′ ` (A S B)] S A′
b. [(A S B) ` A] S B
c. (A ~ B) ` A′ S B
42. Use algorithm TautologyTest to prove that the following expressions are tautologies.
a. (A ` B) ` B′ S A
b. (A ` B′) S (A S B)′
c. (A ` B)′ ~ B′ S A′ ~ B′
43. A memory chip from a digital camera has 2
5
bistable (ON-OFF) memory elements. What is the total number of ON-OFF configurations?
44. In each case, construct compound wffs P and Q so that the given statement is a tautology.
a. P ` Q
b. P S P′
c. P ` (Q S P′)
45. From the truth table for A ~ B, the value of A ~ B is true if A is true, if B is true, or if both are true. This
use of the word “or,” where the result is true if both components are true, is called the inclusive or. It is
the inclusive or that is understood in the sentence, “We may have rain or drizzle tomorrow,” which might
also be expressed as, “We may have rain or drizzle or both tomorrow.” Another use of the word “or” in
the English language is the exclusive or, sometimes written XOr, in which the result is false when both
components are true. The exclusive or is understood in the sentence, “At the intersection, you should turn
north or south,” (but obviously not both). Exclusive or is symbolized by A ! B. Write the truth table for
the exclusive or.
46. Prove that A ! B 4 (A 4 B)′ is a tautology. Explain why this makes sense.
Exercises 47–50 show that defining four basic logical connectives (conjunction, disjunction, implication, and
negation) is a convenience rather than a necessity because certain pairs of connectives are enough to express
any wff. Exercises 51–52 show that a single connective, properly defined, is sufficient.
47. Every compound statement is equivalent to a statement using only the connectives of conjunction and negation. To see this, we need to find equivalent wffs for A ~ B and for A S B that use only ` and ′. These
new statements can replace, respectively, any occurrences of A ~ B and A S B. (The connective 4 was
defined in terms of other connectives, so we already know that it can be replaced by a statement using
these other connectives.)
a. Show that A ~ B is equivalent to (A′ ` B′)′
b. Show that A S B is equivalent to (A ` B′)′
48. Show that every compound wff is equivalent to a wff using only the connectives of ~ and ′. (Hint: See
Exercise 47.)
49. Show that every compound wff is equivalent to a wff using only the connectives of S and ′. (Hint: See
Exercise 47.)
50. Prove that there are compound statements that are not equivalent to any statement using only the
connectives S and ~ .
51. The binary connective 0 is called the Sheffer stroke, named for the American logic professor Henry Sheffer, who proved in 1913 that this single connective is the only one needed. The truth table for 0 is given
here. Sheffer also coined the term “Boolean algebra,” the topic of Chapter 8, where we will see that this
truth table represents the NAND gate.
Formal Logic
41. Use algorithm TautologyTest to prove that the following expressions are tautologies.
a. [B′ ` (A S B)] S A′
b. [(A S B) ` A] S B
c. (A ~ B) ` A′ S B
42. Use algorithm TautologyTest to prove that the following expressions are tautologies.
a. (A ` B) ` B′ S A
b. (A ` B′) S (A S B)′
c. (A ` B)′ ~ B′ S A′ ~ B′
43. A memory chip from a digital camera has 2
5
bistable (ON-OFF) memory elements. What is the total number of ON-OFF configurations?
44. In each case, construct compound wffs P and Q so that the given statement is a tautology.
a. P ` Q
b. P S P′
c. P ` (Q S P′)
45. From the truth table for A ~ B, the value of A ~ B is true if A is true, if B is true, or if both are true. This
use of the word “or,” where the result is true if both components are true, is called the inclusive or. It is
the inclusive or that is understood in the sentence, “We may have rain or drizzle tomorrow,” which might
also be expressed as, “We may have rain or drizzle or both tomorrow.” Another use of the word “or” in
the English language is the exclusive or, sometimes written XOr, in which the result is false when both
components are true. The exclusive or is understood in the sentence, “At the intersection, you should turn
north or south,” (but obviously not both). Exclusive or is symbolized by A ! B. Write the truth table for
the exclusive or.
46. Prove that A ! B 4 (A 4 B)′ is a tautology. Explain why this makes sense.
Exercises 47–50 show that defining four basic logical connectives (conjunction, disjunction, implication, and
negation) is a convenience rather than a necessity because certain pairs of connectives are enough to express
any wff. Exercises 51–52 show that a single connective, properly defined, is sufficient.
47. Every compound statement is equivalent to a statement using only the connectives of conjunction and negation. To see this, we need to find equivalent wffs for A ~ B and for A S B that use only ` and ′. These
new statements can replace, respectively, any occurrences of A ~ B and A S B. (The connective 4 was
defined in terms of other connectives, so we already know that it can be replaced by a statement using
these other connectives.)
a. Show that A ~ B is equivalent to (A′ ` B′)′
b. Show that A S B is equivalent to (A ` B′)′
48. Show that every compound wff is equivalent to a wff using only the connectives of ~ and ′. (Hint: See
Exercise 47.)
49. Show that every compound wff is equivalent to a wff using only the connectives of S and ′. (Hint: See
Exercise 47.)
50. Prove that there are compound statements that are not equivalent to any statement using only the
connectives S and ~ .
51. The binary connective 0 is called the Sheffer stroke, named for the American logic professor Henry Sheffer, who proved in 1913 that this single connective is the only one needed. The truth table for 0 is given
here. Sheffer also coined the term “Boolean algebra,” the topic of Chapter 8, where we will see that this
truth table represents the NAND gate.