Propositional Logic

Assylbek Issakhov,
Ph.D., professor
 Propositional Logic: 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.
 Propositions: Example
▪ 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.
 Propositions: Example
▪ Consider the following sentences.
1. What time is it? 2. Read this carefully.
3. 𝑥 + 1 = 2. 4. 𝑥 + 𝑦 = 𝑧.
▪ 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.
 Propositions
▪ We use letters to denote propositional
variables (or statement variables), that is,
variables that represent propositions, just as
letters are used to denote numerical variables.
The conventional letters used for propositional
variables are 𝑝, 𝑞, 𝑟, 𝑠, . . . . The truth value of a
proposition is true, denoted by 𝑇, if it is a true
proposition, and the truth value of a
proposition is false, denoted by 𝐹, if it is a false
proposition.
 Propositions

▪ The area of logic that deals with propositions is

called the propositional calculus or
propositional logic. It was first developed
systematically by the Greek philosopher
Aristotle more than 2300 years ago.
 Propositions
▪ 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.
 Propositions

▪ DEFINITION 1. Let p be a proposition. The

negation of p, denoted by ¬𝑝 (also denoted by
𝑝), is the statement
“It is not the case that 𝑝.”
▪ The proposition ¬𝑝 is read “not 𝑝.” The truth
value of the negation of 𝑝, ¬𝑝, is the opposite
of the truth value of 𝑝.
 Propositions: Example
▪ Find the negation of the proposition
“Asan’s PC runs Linux”
and express this in simple English.
▪ Solution: The negation is
“It is not the case that Asan’s PC runs Linux.”
This negation can be more simply expressed as
“Asan’s PC does not run Linux.”
 Propositions
▪ Table below displays the truth table for the
negation of a proposition 𝑝. This table has a row
for each of the two possible truth values of a
proposition 𝑝. Each row shows the truth value
of ¬𝑝 corresponding to the truth value of 𝑝 for
this row.
 Propositions
▪ 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.
 Propositions
▪ DEFINITION 2. Let 𝑝 and 𝑞 be propositions. The
conjunction of 𝑝 and 𝑞, denoted by 𝑝 ∧ 𝑞, is the
proposition “𝑝 and 𝑞.” The conjunction 𝑝 ∧ 𝑞 is
true when both 𝑝 and 𝑞 are true and is false
otherwise.
 Propositions
▪ DEFINITION 2. Let 𝑝 and 𝑞 be propositions. The
conjunction of 𝑝 and 𝑞, denoted by 𝑝 ∧ 𝑞, is the
proposition “𝑝 and 𝑞.” The conjunction 𝑝 ∧ 𝑞 is
true when both 𝑝 and 𝑞 are true and is false
otherwise.
▪ 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.”
 Propositions: Example

▪ Find the conjunction of the propositions 𝑝 and 𝑞

where 𝑝 is the proposition “Aizhan’s PC has
more than 16 GB free hard disk space” and 𝑞 is
the proposition “The processor in Aizhan’s PC
runs faster than 1 GHz.”
 Propositions: Example
▪ Solution: The conjunction of these propositions,
𝑝 ∧ 𝑞, is the proposition “Aizhan’s PC has more
than 16 GB free hard disk space, and the
processor in Aizhan’s PC runs faster than 1 GHz.”
This conjunction can be expressed more simply
as “Aizhan’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.
 Propositions
▪ DEFINITION 3. Let 𝑝 and 𝑞 be propositions. The
disjunction of 𝑝 and 𝑞, denoted by 𝑝 ∨ 𝑞, is the
proposition “𝑝 or 𝑞.” The disjunction 𝑝 ∨ 𝑞 is
false when both 𝑝 and 𝑞 are false and is true
otherwise.
 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.”
 Propositions
▪ 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.”
 Propositions
▪ 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.
 Propositions
▪ DEFINITION 4. Let 𝑝 and 𝑞 be propositions.
The exclusive or of 𝑝 and 𝑞, denoted by 𝑝 ⊕ 𝑞,
is the proposition that is true when exactly
one of 𝑝 and 𝑞 is true and is false otherwise.
 Propositions

▪ DEFINITION 5. Let 𝑝 and 𝑞 be propositions.

The conditional statement 𝑝 → 𝑞 is the
proposition “if 𝑝, then 𝑞.” The conditional
statement 𝑝 → 𝑞 is false when 𝑝 is true and 𝑞
is false, and true otherwise. In the conditional
statement 𝑝 → 𝑞, 𝑝 is called the hypothesis (or
antecedent or premise) and 𝑞 is called the
conclusion (or consequence).
 Propositions
▪ The statement 𝑝 → 𝑞 is called a conditional
statement because 𝑝 → 𝑞 asserts that 𝑞 is true
on the condition that 𝑝 holds. A conditional
statement is also called an implication.
 Propositions
▪ Because conditional statements play such an
essential role in mathematical reasoning, a
variety of terminology is used to express 𝑝 → 𝑞.
You will encounter most if not all of the
following ways to express this conditional
statement:
“if 𝑝, then 𝑞”; “𝑝 implies 𝑞”; “if 𝑝, 𝑞”; “𝑝 only if
𝑞”; “𝑝 is sufficient for 𝑞”; “a sufficient condition
for 𝑞 is 𝑝”; “𝑞 if 𝑝”; “𝑞 whenever 𝑝”; “𝑞 when 𝑝”;
“q is necessary for 𝑝”; “a necessary condition for
𝑝 is 𝑞”; “𝑞 follows from 𝑝”; “𝑞 unless ¬𝑝”.
 Propositions: Example

▪ A useful way to understand the truth value of a

conditional statement is to think of an obligation
or a contract. For example, the pledge many
politicians make when running for office is
“If I am elected, then I will lower taxes.”
 Propositions: Example
▪ If the politician is elected, voters would expect
this politician to lower taxes. Furthermore, if the
politician is not elected, then voters will not have
any expectation that this person will lower taxes,
although the person may have sufficient influence
to cause those in power to lower taxes. It is only
when the politician is elected but does not lower
taxes that voters can say that the politician has
broken the campaign pledge. This last scenario
corresponds to the case when 𝑝 is true but 𝑞 is
false in 𝑝 → 𝑞.
 Propositions
▪ The if-then construction used in many
programming languages is different from that
used in logic. Most programming languages
contain statements such as if 𝑝 then 𝑆, where 𝑝
is a proposition and 𝑆 is a program segment (one
or more statements to be executed).When
execution of a program encounters such a
statement, 𝑆 is executed if 𝑝 is true, but 𝑆 is not
executed if 𝑝 is false.
 Propositions
▪ We can form some new conditional statements
starting with a conditional statement 𝑝 → 𝑞. In
particular, there are three related conditional
statements that occur so often that they have
special names. The proposition 𝑞 → 𝑝 is called
the converse of 𝑝 → 𝑞. The contrapositive of
𝑝 → 𝑞 is the proposition ¬𝑞 → ¬𝑝. The
proposition ¬𝑝 → ¬𝑞 is called the inverse of
𝑝 → 𝑞. We will see that of these three conditional
statements formed from 𝑝 → 𝑞, only the
contrapositive always has the same truth value as
𝑝 → 𝑞.
 Propositions: Example

▪ What are the contrapositive, the converse, and

the inverse of the conditional statement
“The home team wins whenever it is raining?”
▪ Solution: Because “𝑞 whenever 𝑝” is one of the
ways to express the conditional statement
𝑝 → 𝑞, the original statement can be rewritten
as
“If it is raining, then the home team wins.”
 Propositions: Example
▪ Solution (cont.): Consequently, the
contrapositive of this conditional statement is
“If the home team does not win, then it is not
raining.” The converse is “If the home team
wins, then it is raining.” The inverse is “If it is
not raining, then the home team does not win.”
▪ Only the contrapositive is equivalent to the
original statement.
 Propositions: BICONDITIONALS

▪ DEFINITION 6. Let 𝑝 and 𝑞 be propositions.

The biconditional statement 𝑝 ↔ 𝑞 is the
proposition “𝑝 if and only if 𝑞.” The
biconditional statement 𝑝 ↔ 𝑞 is true when 𝑝
and 𝑞 have the same truth values, and is false
otherwise. Biconditional statements are also
called bi-implications.
 Propositions: BICONDITIONALS
▪ Note that the statement 𝑝 ↔ 𝑞 is true when
both the conditional statements 𝑝 → 𝑞 and
𝑞 → 𝑝 are true and is false otherwise. That is
why we use the words “if and only if” to express
this logical connective and why it is symbolically
written by combining the symbols → and ←.
There are some other common ways to express
𝑝 ↔ 𝑞:
▪ “𝑝 is necessary and sufficient for 𝑞”; “if 𝑝 then 𝑞,
and conversely”; “𝑝 iff 𝑞.”
 Propositions: BICONDITIONALS
▪ Note that 𝑝 ↔ 𝑞 has exactly the same truth
value as (𝑝 → 𝑞) ∧ (𝑞 → 𝑝).
 Truth Tables of Compound
Propositions: Example
▪ Construct the truth table of the compound
proposition: (𝑝 ∨ ¬𝑞) → (𝑝 ∧ 𝑞).
▪ Solution: Because this truth table involves two
propositional variables p and q, there are four
rows in this truth table, one for each of the pairs
of truth values 𝑇𝑇, 𝑇𝐹, 𝐹𝑇, and 𝐹𝐹. The first two
columns are used for the truth values of 𝑝 and 𝑞,
respectively. In the third column we find the truth
value of ¬𝑞, needed to find the truth value of
𝑝 ∨ ¬𝑞, found in the fourth column.
 Truth Tables of Compound
Propositions: Example
▪ Solution (cont.): The fifth column gives the truth
value of 𝑝 ∧ 𝑞. Finally, the truth value of
(𝑝 ∨ ¬𝑞) → (𝑝 ∧ 𝑞) is found in the last column.
Precedence of Logical Operators
 Logic and Bit Operations
▪ Computers represent information using bits. A
bit is a symbol with two possible values,
namely, 0 (zero) and 1 (one). This meaning of
the word bit comes from binary digit, because
zeros and ones are the digits used in binary
representations of numbers. The well-known
statistician John Tukey introduced this
terminology in 1946. A bit can be used to
represent a truth value, because there are two
truth values, namely, true and false.
 Logic and Bit Operations

▪ As is customarily done, we will use a 1 bit to

represent true and a 0 bit to represent false.
That is, 1 represents T (true), 0 represents F
(false). A variable is called a Boolean variable
if its value is either true or false.
Consequently, a Boolean variable can be
represented using a bit.
 Logic and Bit Operations
▪ Computer bit operations correspond to the
logical connectives. By replacing true by a one
and false by a zero in the truth tables for the
operators ∧, ∨, and ⊕, the tables shown in
Table 9 for the corresponding bit operations are
obtained. We will also use the notation OR,
AND, and XOR for the operators ∨,∧, and ⊕, as
is done in various programming languages.
Logic and Bit Operations
HOMEWORK: Exercises 2, 4, 8, 12, 16,
22, 28, 30, 32, 38 on pp. 12-15