Page 39 - Discrete Mathematics and Its Applications

18 1 / The Foundations: Logic and Proofs

reply can be sent,” which can also be expressed as “The automated reply cannot be sent.”
Consequently, our specification can be represented by the conditional statement q →¬p. ▲

System specifications should be consistent, that is, they should not contain conflicting
requirements that could be used to derive a contradiction.When specifications are not consistent,
there would be no way to develop a system that satisfies all specifications.

EXAMPLE 4 Determine whether these system specifications are consistent:
“The diagnostic message is stored in the buffer or it is retransmitted.”
“The diagnostic message is not stored in the buffer.”
“If the diagnostic message is stored in the buffer, then it is retransmitted.”

Solution: To determine whether these specifications are consistent, we first express them using
logical expressions. Let p denote “The diagnostic message is stored in the buffer” and let q
denote “The diagnostic message is retransmitted.” The specifications can then be written as
p ∨ q, ¬p, and p → q. An assignment of truth values that makes all three specifications true
must have p false to make ¬p true. Because we want p ∨ q to be true but p must be false,
q must be true. Because p → q is true when p is false and q is true, we conclude that these
specifications are consistent, because they are all true when p is false and q is true. We could
come to the same conclusion by use of a truth table to examine the four possible assignments
of truth values to p and q. ▲

EXAMPLE 5 Do the system specifications in Example 4 remain consistent if the specification “The diagnostic
message is not retransmitted” is added?

Solution: By the reasoning in Example 4, the three specifications from that example are true
only in the case when p is false and q is true. However, this new specification is ¬q, which is
false when q is true. Consequently, these four specifications are inconsistent. ▲

Boolean Searches

Logical connectives are used extensively in searches of large collections of information, such
as indexes of Web pages. Because these searches employ techniques from propositional logic,
they are called Boolean searches.
In Boolean searches, the connective AND is used to match records that contain both of
two search terms, the connective OR is used to match one or both of two search terms, and the
connective NOT (sometimes written as AND NOT ) is used to exclude a particular search term.
Careful planning of how logical connectives are used is often required when Boolean searches
are used to locate information of potential interest. Example 6 illustrates how Boolean searches
are carried out.
EXAMPLE 6 Web Page Searching Most Web search engines support Boolean searching techniques, which
usually can help findWeb pages about particular subjects. For instance, using Boolean searching
to find Web pages about universities in New Mexico, we can look for pages matching NEW
AND MEXICO AND UNIVERSITIES. The results of this search will include those pages that
contain the three words NEW, MEXICO, and UNIVERSITIES. This will include all of the
pages of interest, together with others such as a page about new universities in Mexico. (Note
that in Google, and many other search engines, the word “AND” is not needed, although it is
understood, because all search terms are included by default. These search engines also support
the use of quotation marks to search for specific phrases. So, it may be more effective to search
for pages matching “New Mexico” AND UNIVERSITIES.)