Unit 1
Notes
Applications of Propositional Logic
1. Translating English Sentences
How can this English sentence be translated into a logical expression?
EXAMPLE : “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 ).
2. 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 : 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.”
Consequently, our specification can be represented by the conditional statement q →￢p.
3. 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 : Web Page Searching MostWeb search engines support Boolean searching
techniques, which usually can help find Web 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.)
4. Logic Puzzles
Puzzles that can be solved using logical reasoning are known as logic puzzles. Solving logic
puzzles is an excellent way to practice working with the rules of logic. Also, computer programs
designed to carry out logical reasoning often use well-known logic puzzles to illustrate their
capabilities. Many people enjoy solving logic puzzles, published in periodicals, books, and on
the Web, as a recreational activity.
5. Cryptography
One of the earliest known uses of cryptography was by Julius Caesar. He made messages secret
by shifting each letter three letters forward in the alphabet (sending the last three letters of the
alphabet to the first three). For instance, using this scheme the letter B is sent to E and the letter
X is sent to A. This is an example of encryption, that is, the process of making a message secret.
To express Caesar’s encryption process mathematically, first replace each letter by an element of
Z26, that is, an integer from 0 to 25 equal to one less than its position in the alphabet.
For example, replace A by 0, K by 10, and Z by 25. Caesar’s encryption method can be
represented by the function f that assigns to the nonnegative integer p, p ≤ 25, the integer f (p) in
the set {0, 1, 2, .. .., 25} with f (p) = (p + 3) mod 26.
In the encrypted version of the message, the letter represented by p is replaced with the letter
represented by (p + 3) mod 26.
