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 numerous
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.
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.
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.
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.”
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.
p q p ? q
T T T
T F T
F T T
F F F
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.
TABLE 4 The Truth Table for
the Exclusive Or of Two
Propositions.
p q p ? q
T T F
T F T
F T T
F F F
TABLE 5 The Truth Table for
the Conditional Statement
p ? q.
p q p ? q
T T T
T F F
F T T
F F T
DEFINITION 4 Let p and q be propositions. The exclusive or of p and q, denoted by p ? q, is the proposition
that is true when exactly one of p and q is true and is false otherwise.
The truth table for the exclusive or of two propositions is displayed in Table 4.
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .
الرجوع الى لوحة التحكم
|