Page 37 - Discrete Mathematics and Its Applications

16 1 / The Foundations: Logic and Proofs

40. Explain, without using a truth table, why (p ∨¬q) ∧ because Fred is happy most of the time, and the truth value
(q ∨¬r) ∧ (r ∨¬p) is true when p, q, and r have the 0.4 can be assigned to the statement “John is happy,” because
same truth value and it is false otherwise. John is happy slightly less than half the time. Use these truth
values to solve Exercises 45–47.
41. Explain, without using a truth table, why (p ∨ q ∨ r) ∧
(¬p ∨¬q ∨¬r) is true when at least one of p, q, and r 45. The truth value of the negation of a proposition in fuzzy
is true and at least one is false, but is false when all three logic is 1 minus the truth value of the proposition. What
variables have the same truth value. are the truth values of the statements “Fred is not happy”
42. What is the value of x after each of these statements is and “John is not happy?”
encountered in a computer program, if x = 1 before the 46. The truth value of the conjunction of two propositions in
statement is reached? fuzzy logic is the minimum of the truth values of the two
a) if x + 2 = 3 then x := x + 1 propositions. What are the truth values of the statements
b) if (x + 1 = 3) OR (2x + 2 = 3) then x := x + 1 “Fred and John are happy” and “Neither Fred nor John is
c) if (2x + 3 = 5) AND (3x + 4 = 7) then x := x + 1 happy?”
d) if (x + 1 = 2) XOR (x + 2 = 3) then x := x + 1 47. The truth value of the disjunction of two propositions in
e) if x< 2 then x := x + 1 fuzzy logic is the maximum of the truth values of the two
43. Find the bitwise OR, bitwise AND, and bitwise XOR of propositions. What are the truth values of the statements
each of these pairs of bit strings. “Fred is happy, or John is happy” and “Fred is not happy,
a) 101 1110, 010 0001 or John is not happy?”
b) 1111 0000, 1010 1010 ∗ 48. Is the assertion “This statement is false” a proposition?
c) 00 0111 0001, 10 0100 1000 ∗ 49. The nth statement in a list of 100 statements is “Exactly
d) 11 1111 1111, 00 0000 0000 n of the statements in this list are false.”
44. Evaluate each of these expressions. a) What conclusions can you draw from these state-
a) 1 1000 ∧ (0 1011 ∨ 1 1011) ments?
b) (0 1111 ∧ 1 0101) ∨ 0 1000 b) Answer part (a) if the nth statement is “At least n of
c) (0 1010 ⊕ 1 1011) ⊕ 0 1000 the statements in this list are false.”
d) (1 1011 ∨ 0 1010) ∧ (1 0001 ∨ 1 1011) c) Answer part (b) assuming that the list contains 99
Fuzzy logic is used in artificial intelligence. In fuzzy logic, a statements.
proposition has a truth value that is a number between 0 and 1, 50. An ancient Sicilian legend says that the barber in a remote
inclusive.A proposition with a truth value of 0 is false and one town who can be reached only by traveling a dangerous
with a truth value of 1 is true. Truth values that are between 0 mountain road shaves those people, and only those peo-
and 1 indicate varying degrees of truth. For instance, the truth ple, who do not shave themselves. Can there be such a
value 0.8 can be assigned to the statement “Fred is happy,” barber?

1.2 Applications of Propositional Logic

Introduction

Logic has many important applications to mathematics, computer science, and numerous other
disciplines. Statements in mathematics and the sciences and in natural language often are im-
precise or ambiguous. To make such statements precise, they can be translated into the language
of logic. For example, logic is used in the specification of software and hardware, because these
specifications need to be precise before development begins. Furthermore, propositional logic
and its rules can be used to design computer circuits, to construct computer programs, to verify
the correctness of programs, and to build expert systems. Logic can be used to analyze and
solve many familiar puzzles. Software systems based on the rules of logic have been developed
for constructing some, but not all, types of proofs automatically. We will discuss some of these
applications of propositional logic in this section and in later chapters.

Translating English Sentences

There are many reasons to translate English sentences into expressions involving propositional
variables and logical connectives. In particular, English (and every other human language) is