Page 57 - Discrete Mathematics and Its Applications

36 1 / The Foundations: Logic and Proofs

∗ 44. Show that ¬ and ∧ form a functionally complete col- stand because it involves two conditional statements. Find
lection of logical operators. [Hint: First use a De Mor- an equivalent, easier-to-understand specification that in-
gan law to show that p ∨ q is logically equivalent to volves disjunctions and negations but not conditional
¬(¬p ∧¬q).] statements.
∗ 45. Show that ¬ and ∨ form a functionally complete collec- 58. How many of the disjunctions p ∨¬q, ¬p ∨ q, q ∨ r,
tion of logical operators. q ∨¬r, and ¬q ∨¬r can be made simultaneously true
The following exercises involve the logical operators NAND by an assignment of truth values to p, q, and r?
and NOR. The proposition p NAND q is true when either p
59. How many of the disjunctions p ∨¬q ∨ s, ¬p ∨
or q, or both, are false; and it is false when both p and q are ¬r ∨ s, ¬p ∨¬r ∨¬s, ¬p ∨ q ∨¬s, q ∨ r ∨¬s,
true. The proposition p NOR q is true when both p and q are q ∨¬r ∨¬s, ¬p ∨¬q ∨¬s, p ∨ r ∨ s, and p ∨ r ∨¬s
false, and it is false otherwise. The propositions p NAND q can be made simultaneously true by an assignment of
and p NOR q are denoted by p | q and p ↓ q, respectively. truth values to p, q, r, and s?
(The operators | and ↓ are called the Sheffer stroke and the 60. Show that the negation of an unsatisfiable compound
Peirce arrow after H. M. Sheffer and C. S. Peirce, respec- proposition is a tautology and the negation of a compound
tively.)
proposition that is a tautology is unsatisfiable.
46. Construct a truth table for the logical operator NAND.
61. Determine whether each of these compound propositions
47. Show that p | q is logically equivalent to ¬(p ∧ q).
is satisfiable.
48. Construct a truth table for the logical operator NOR.
49. Show that p ↓ q is logically equivalent to ¬(p ∨ q). a) (p ∨¬q) ∧ (¬p ∨ q) ∧ (¬p ∨¬q)
50. In this exercise we will show that {↓} is a functionally b) (p → q) ∧ (p →¬q) ∧ (¬p → q) ∧ (¬p →¬q)
complete collection of logical operators. c) (p ↔ q) ∧ (¬p ↔ q)
a) Show that p ↓ p is logically equivalent to ¬p. 62. Determine whether each of these compound propositions
b) Show that (p ↓ q) ↓ (p ↓ q) is logically equivalent is satisfiable.
to p ∨ q. a) (p ∨ q ∨¬r) ∧ (p ∨¬q ∨¬s) ∧ (p ∨¬r ∨¬s) ∧
c) Conclude from parts (a) and (b), and Exercise 49, that (¬p ∨¬q ∨¬s) ∧ (p ∨ q ∨¬s)
{↓} is a functionally complete collection of logical
b) (¬p ∨¬q ∨ r) ∧ (¬p ∨ q ∨¬s) ∧ (p ∨¬q ∨
operators.
¬s) ∧ (¬p ∨¬r ∨¬s) ∧ (p ∨ q ∨¬r) ∧ (p ∨
∗ 51. Find a compound proposition logically equivalent to ¬r ∨¬s)
p → q using only the logical operator ↓.
c) (p ∨ q ∨ r) ∧ (p ∨¬q ∨¬s) ∧ (q ∨¬r ∨ s) ∧
52. Show that {|} is a functionally complete collection of log-
(¬p ∨ r ∨ s) ∧ (¬p ∨ q ∨¬s) ∧ (p ∨¬q ∨¬r) ∧
ical operators. (¬p ∨¬q ∨ s) ∧ (¬p ∨¬r ∨¬s)
53. Show that p | q and q | p are equivalent.
63. Show how the solution of a given 4 × 4 Sudoku puzzle
54. Show that p | (q | r) and (p | q) | r are not equivalent, can be found by solving a satisfiability problem.
so that the logical operator | is not associative.
∗ 55. How many different truth tables of compound proposi- 64. Construct a compound proposition that asserts that ev-
tions are there that involve the propositional variables p ery cell of a 9 × 9 Sudoku puzzle contains at least one
and q? number.
56. Show that if p, q, and r are compound propositions such 65. Explain the steps in the construction of the compound
that p and q are logically equivalent and q and r are log- proposition given in the text that asserts that every col-
ically equivalent, then p and r are logically equivalent. umn of a 9 × 9 Sudoku puzzle contains every number.
57. The following sentence is taken from the specification of ∗ 66. Explain the steps in the construction of the compound
a telephone system: “If the directory database is opened, proposition given in the text that asserts that each of the
then the monitor is put in a closed state, if the system is nine 3 × 3 blocks of a 9 × 9 Sudoku puzzle contains ev-
not in its initial state.” This specification is hard to under- ery number.

1.4 Predicates and Quantifiers

Introduction

Propositional logic, studied in Sections 1.1–1.3, cannot adequately express the meaning of all
statements in mathematics and in natural language. For example, suppose that we know that

“Every computer connected to the university network is functioning properly.”