Applications Of Propositional Logic
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 imprecise 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.
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 often ambiguous. Translating sentences into compound statements (and other types of logical expressions, which we will introduce later in this chapter) removes the ambiguity. Note that this may involve making a set of reasonable assumptions based on the intended meaning of the sentence. Moreover, once we have translated sentences from English into logical expressions we can analyze these logical expressions to determine their truth values, we can manipulate them, and we can use rules of inference (which are discussed in Section 1.6) to reason about them.
To illustrate the process of translating an English sentence into a logical expression, consider Examples 1 and 2.
EXAMPLE 1 How can this English sentence be translated into a logical expression? “You can access the Internet from campus only if you are a computer science major or you are not a freshman.”
Solution: There are many ways to translate this sentence into a logical expression. Although it is possible to represent the sentence by a single propositional variable, such as p, this would not be useful when analyzing its meaning or reasoning with it. Instead, we will use propositional variables to represent each sentence part and determine the appropriate logical connectives between them. In particular, we let a, c, and f represent “You can access the Internet from campus,” “You are a computer science major,” and “You are a freshman,” respectively. Noting that “only if” is one way a conditional statement can be expressed, this sentence can be represented as
a → (c ∨¬f ).
EXAMPLE 2 How can this English sentence be translated into a logical expression? “You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old.”
Solution: Let q, r, and s represent “You can ride the roller coaster,” “You are under 4 feet tall,” and “You are older than 16 years old,” respectively. Then the sentence can be translated to (r ∧¬s)→¬q. Of course, there are other ways to represent the original sentence as a logical expression, but the one we have used should meet our needs.
System Specifications: Translating sentences in natural language (such as English) into logical expressions is an essential part of specifying both hardware and software systems. System and software engineers take requirements in natural language and produce precise and unambiguous specifications that can be used as the basis for system development. Example 3 shows how compound propositions can be used in this process.
EXAMPLE 3 Express the specification “The automated reply cannot be sent when the file system is full” using logical connectives.
Solution: One way to translate this is to let p denote “The automated reply can be sent” and q denote “The file system is full.” Then ¬p represents “It is not the case that the automated reply can be sent,” which can also be expressed as “The automated reply cannot be sent.”
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 MostWeb 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.)
Next, to find pages that deal with universities in New Mexico or Arizona, we can search for pages matching (NEW AND MEXICO OR ARIZONA) AND UNIVERSITIES. (Note: Here the AND operator takes precedence over the OR operator. Also, in Google, the terms used for this search would be NEW MEXICO OR ARIZONA.) The results of this search will include all pages that contain the word UNIVERSITIES and either both the words NEW and MEXICO or the word ARIZONA. Again, pages besides those of interest will be listed. Finally, to find Web pages that deal with universities in Mexico (and not New Mexico), we might first look for pages matching MEXICO AND UNIVERSITIES, but because the results of this search will include pages about universities in New Mexico, as well as universities in Mexico, it might be better to search for pages matching (MEXICO AND UNIVERSITIES) NOT NEW. The results of this search include pages that contain both the words MEXICO and UNIVERSITIES but do not contain the word NEW. (In Google, and many other search engines, the word “NOT” is replaced by the symbol “-”. In Google, the terms used for this last search would be MEXICO UNIVERSITIES -NEW.)