Fcs fundamental computer science questions

 Note remember page numbers

Propositional Logic

Introduction

The rules of logic give precise meaning to mathematical statements. These rules are used to

distinguish between valid and invalid mathematical arguments. Because a major goal of this book

is to teach the reader how to understand and how to construct correct mathematical arguments,

we begin our study of discrete mathematics with an introduction to logic.

Besides the importance of logic in understanding mathematical reasoning, logic has numer￾ous applications to computer science. These rules are used in the design of computer circuits,

the construction of computer programs, the verification of the correctness of programs, and in

many other ways. Furthermore, software systems have been developed for constructing some,

but not all, types of proofs automatically. We will discuss these applications of logic in this and

later chapters.

Propositions

Our discussion begins with an introduction to the basic building blocks of logic—propositions.

A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true

or false, but not both.

EXAMPLE 1 All the following declarative sentences are propositions.

1. Washington, D.C., is the capital of the United States of America.

2. Toronto is the capital of Canada.

3. 1 + 1 = 2.

4. 2 + 2 = 3.

Propositions 1 and 3 are true, whereas 2 and 4 are false. ▲

Some sentences that are not propositions are given in Example 2.

EXAMPLE 2 Consider the following sentences.

1. What time is it?

2. Read this carefully.

3. x + 1 = 2.

4. x + y = z.

Sentences 1 and 2 are not propositions because they are not declarative sentences. Sentences 3

and 4 are not propositions because they are neither true nor false. Note that each of sentences 3

and 4 can be turned into a proposition if we assign values to the variables. We will also discuss

other ways to turn sentences such as these into propositions in Section 1.4. ▲

We use letters to denote propositional variables (or statement variables), that is, vari￾ables that represent propositions, just as letters are used to denote numerical variables. The

ARISTOTLE (384 b.c.e.–322 b.c.e.) Aristotle was born in Stagirus (Stagira) in northern Greece. His father was

the personal physician of the King of Macedonia. Because his father died when Aristotle was young, Aristotle

could not follow the custom of following his father’s profession. Aristotle became an orphan at a young age

when his mother also died. His guardian who raised him taught him poetry, rhetoric, and Greek. At the age of

17, his guardian sent him to Athens to further his education. Aristotle joined Plato’s Academy, where for 20

years he attended Plato’s lectures, later presenting his own lectures on rhetoric. When Plato died in 347 B.C.E.,

Aristotle was not chosen to succeed him because his views differed too much from those of Plato. Instead,

Aristotle joined the court of King Hermeas where he remained for three years, and married the niece of the

King. When the Persians defeated Hermeas, Aristotle moved to Mytilene and, at the invitation of King Philip

of Macedonia, he tutored Alexander, Philip’s son, who later became Alexander the Great. Aristotle tutored Alexander for five years

and after the death of King Philip, he returned to Athens and set up his own school, called the Lyceum.

Aristotle’s followers were called the peripatetics, which means “to walk about,” because Aristotle often walked around as he

discussed philosophical questions. Aristotle taught at the Lyceum for 13 years where he lectured to his advanced students in the

morning and gave popular lectures to a broad audience in the evening. When Alexander the Great died in 323 B.C.E., a backlash against

anything related to Alexander led to trumped-up charges of impiety against Aristotle. Aristotle fled to Chalcis to avoid prosecution.

He only lived one year in Chalcis, dying of a stomach ailment in 322 B.C.E.

Aristotle wrote three types of works: those written for a popular audience, compilations of scientific facts, and systematic

treatises. The systematic treatises included works on logic, philosophy, psychology, physics, and natural history. Aristotle’s writings

were preserved by a student and were hidden in a vault where a wealthy book collector discovered them about 200 years later. They

were taken to Rome, where they were studied by scholars and issued in new editions, preserving them for posterity

conventional letters used for propositional variables are p, q, r, s, . . . . The truth value of a

proposition is true, denoted by T, if it is a true proposition, and the truth value of a proposition

is false, denoted by F, if it is a false proposition.

The area of logic that deals with propositions is called the propositional calculus or propo￾sitional logic. It was first developed systematically by the Greek philosopher Aristotle more

than 2300 years ago.

We now turn our attention to methods for producing new propositions from those that

we already have. These methods were discussed by the English mathematician George Boole

in 1854 in his book The Laws of Thought. Many mathematical statements are constructed by

combining one or more propositions. New propositions, called compound propositions, are

formed from existing propositions using logical operators.

DEFINITION 1 Let p be a proposition. The negation of p, denoted by ¬p (also denoted by p), is the statement

“It is not the case that p.”

The proposition ¬p is read “not p.” The truth value of the negation of p, ¬p, is the opposite

of the truth value of p.

EXAMPLE 3 Find the negation of the proposition

“Michael’s PC runs Linux”

and express this in simple English.

Solution: The negation is

“It is not the case that Michael’s PC runs Linux.”

This negation can be more simply expressed as

“Michael’s PC does not run Linux.”

▲

EXAMPLE 4 Find the negation of the proposition

“Vandana’s smartphone has at least 32GB of memory”

and express this in simple English.

Solution: The negation is

“It is not the case that Vandana’s smartphone has at least 32GB of memory.”

This negation can also be expressed as

“Vandana’s smartphone does not have at least 32GB of memory”

or even more simply as

“Vandana’s smartphone has less than 32GB of memory

Table 1 displays the truth table for the negation of a proposition p. This table has a row

for each of the two possible truth values of a proposition p. Each row shows the truth value of

¬p corresponding to the truth value of p for this row.

The negation of a proposition can also be considered the result of the operation of the

negation operator on a proposition. The negation operator constructs a new proposition from

a single existing proposition. We will now introduce the logical operators that are used to form

new propositions from two or more existing propositions. These logical operators are also called

connectives.

DEFINITION 2 Let p and q be propositions. The conjunction of p and q, denoted by p ∧ q, is the proposition

“p and q.” The conjunction p ∧ q is true when both p and q are true and is false otherwise.

Table 2 displays the truth table of p ∧ q. This table has a row for each of the four possible

combinations of truth values of p and q. The four rows correspond to the pairs of truth values

TT, TF, FT, and FF, where the first truth value in the pair is the truth value of p and the second

truth value is the truth value of q.

Note that in logic the word “but” sometimes is used instead of “and” in a conjunction. For

example, the statement “The sun is shining, but it is raining” is another way of saying “The sun

is shining and it is raining.” (In natural language, there is a subtle difference in meaning between

“and” and “but”; we will not be concerned with this nuance here.)

EXAMPLE 5 Find the conjunction of the propositions p and q where p is the proposition “Rebecca’s PC has

more than 16 GB free hard disk space” and q is the proposition “The processor in Rebecca’s

PC runs faster than 1 GHz.”

Solution: The conjunction of these propositions, p ∧ q, is the proposition “Rebecca’s PC has

more than 16 GB free hard disk space, and the processor in Rebecca’s PC runs faster than 1

GHz.” This conjunction can be expressed more simply as “Rebecca’s PC has more than 16 GB

free hard disk space, and its processor runs faster than 1 GHz.” For this conjunction to be true,

both conditions given must be true. It is false, when one or both of these conditions are false. ▲

DEFINITION 3 Let p and q be propositions. The disjunction of p and q, denoted by p ∨ q, is the proposition

“p or q.” The disjunction p ∨ q is false when both p and q are false and is true otherwise.

Table 3 displays the truth table for p ∨ q.

TABLE 2 The Truth Table for

the Conjunction of Two

Propositions.

p q p ∧ q

T T T

T F F

F T F

F F F

TABLE 3 The Truth Table for

the Disjunction of Two

Propositions.

The use of the connective or in a disjunction corresponds to one of the two ways the word

or is used in English, namely, as an inclusive or. A disjunction is true when at least one of the

two propositions is true. For instance, the inclusive or is being used in the statement

“Students who have taken calculus or computer science can take this class.”

Here, we mean that students who have taken both calculus and computer science can take the

class, as well as the students who have taken only one of the two subjects. On the other hand,

we are using the exclusive or when we say

“Students who have taken calculus or computer science, but not both, can enroll in this

class.”

Here, we mean that students who have taken both calculus and a computer science course cannot

take the class. Only those who have taken exactly one of the two courses can take the class.

Similarly, when a menu at a restaurant states, “Soup or salad comes with an entrée,” the

restaurant almost always means that customers can have either soup or salad, but not both.

Hence, this is an exclusive, rather than an inclusive, or.

EXAMPLE 6 What is the disjunction of the propositions p and q where p and q are the same propositions as

in Example 5?

Solution: The disjunction of p and q, p ∨ q, is the proposition

“Rebecca’s PC has at least 16 GB free hard disk space, or the processor in Rebecca’s PC

runs faster than 1 GHz.”

This proposition is true when Rebecca’s PC has at least 16 GB free hard disk space, when the

PC’s processor runs faster than 1 GHz, and when both conditions are true. It is false when both

of these conditions are false, that is, when Rebecca’s PC has less than 16 GB free hard disk

space and the processor in her PC runs at 1 GHz or slower. ▲

As was previously remarked, the use of the connective or in a disjunction corresponds

to one of the two ways the word or is used in English, namely, in an inclusive way. Thus, a

disjunction is true when at least one of the two propositions in it is true. Sometimes, we use or

in an exclusive sense. When the exclusive or is used to connect the propositions p and q, the

proposition “p or q (but not both)” is obtained. This proposition is true when p is true and q is

false, and when p is false and q is true. It is false when both p and q are false and when both

are true.

GEORGE BOOLE (1815–1864) George Boole, the son of a cobbler, was born in Lincoln, England, in

November 1815. Because of his family’s difficult financial situation, Boole struggled to educate himself while

supporting his family. Nevertheless, he became one of the most important mathematicians of the 1800s.Although

he considered a career as a clergyman, he decided instead to go into teaching, and soon afterward opened a

school of his own. In his preparation for teaching mathematics, Boole—unsatisfied with textbooks of his day—

decided to read the works of the great mathematicians. While reading papers of the great French mathematician

Lagrange, Boole made discoveries in the calculus of variations, the branch of analysis dealing with finding

curves and surfaces by optimizing certain parameters.

In 1848 Boole publishedThe Mathematical Analysis of Logic, the first of his contributions to symbolic logic.

In 1849 he was appointed professor of mathematics at Queen’s College in Cork, Ireland. In 1854 he published The Laws of Thought,

his most famous work. In this book, Boole introduced what is now called Boolean algebra in his honor. Boole wrote textbooks

on differential equations and on difference equations that were used in Great Britain until the end of the nineteenth century. Boole

married in 1855; his wife was the niece of the professor of Greek at Queen’s College. In 1864 Boole died from pneumonia, which

he contracted as a result of keeping a lecture engagement even though he was soaking wet from a rainstorm.

p q p ∨ q

T T T

T F T

F T T

F F F