DM LECTURE (1)

Propositional Logic

Definition(1) : A proposition is a declarative sentence (that is, a

sentence that declares a fact) that is either true or false, but not both.

Example (l )
All the following declarative sentences are propositions.
1. Damascus is the capital of Syria.
2 . Cairo is the capital of Jordan
3.1+1=2.
4. 2 + 2 = 3.
Propositions 1 and 3 are true, whereas 2 and 4 are false.

Example (2)

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.

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 p, q , r, s, . .
The truth value of a proposition is true, denoted by T, if it is a true
proposition and false, denoted by F, if it is a false proposition.
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 2 300 years ago.
We now turn our attention to methods for producing new propositions
from those that we already have.

Definition (2) : 1 Let p be a proposition. The negation of p, denoted by

¬p (also denoted by 𝒑), is the statement "It is not the case that p."
The proposition is ¬p 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 "Today is Friday."
and express this in simple English.
Solution: The negation is :
"It is not the case that today is Friday."
This negation can be more simply expressed by
"Today is not Friday,"
or
"It is not Friday today."

Example (4) : Find the negation of the proposition

"At least 20 cm of rain fell today in Damascus."
and express this in simple English.
Solution: The negation is:
"It is not the case that at least 20 cm of rain fell today in Damascus."
This negation can be more simply expressed by
"Less than 20 cm of rain fell today in Damascus."
Remark: Strictly speaking, sentences involving variable times such as
those in Examples 3 and4 are not propositions unless a fixed time is
assumed. The same holds for variable places unless a fixed place is
assumed and for pronouns unless a particular person is assumed.
We will always assume fixed times, fixed places, and particular people in
such sentences unless otherwise noted.

Table ( 1):Truth Table for the Negation of a Proposition :

p ¬p
T F
F T

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 (3) : 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.)

Table (2) :Truth table for the conjunction :

p q 𝑝∧𝑞
T T T
T F F
F T F
F F F
𝑝 ∧ 𝑞 (p and q) is true when both p and q are true and is false
otherwise .

Definition (4) : Let p and q be propositions. The disjunction of p and q,

denoted by 𝒑 ∨ 𝒒 , is the proposition "p or q ." The disjunction 𝒑 ∨ 𝒒 is
false when both p and q are false and is true otherwise.
Table (3 ) displays the truth table for 𝒑 ∨ 𝒒.
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. 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 entree," 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.

Table (3):Truth table for the disjunction :

p q 𝑝∨𝑞
T T T
T F T
F T T
F F F
𝑝 ∨ 𝑞 ( p or q ) is false when both p and q are false and is true
otherwise
Example (5) : Find the conjunction of the propositions p and q where p
is the proposition "Today is Friday" and q is the proposition "It is raining
today."
Solution: The conjunction of these propositions, p /\ q, is the proposition
"Today is Friday and it is raining today."
This proposition is true on rainy Fridays and is false on any day that is
not a Friday and on Fridays when it does not rain.

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 v q, is the proposition

"Today is Friday or it is raining today."
This proposition is true on any day that is either a Friday or a rainy day
(including rainy Fridays).
It is only false on days that are not Fridays when it also does not rain.
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.
Definition (5) : Let p and q be propositions. The exclusive or of p and q,
denoted by 𝒑 ⊕ 𝒒 , 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.

Table (4) :Truth table for the Exclusive Or :

p q 𝑝⨁𝑞
T T F
T F T
F T T
F F F
𝒑⨁𝒒 ( XOR) is true when exactly one of p and q is true and is
false otherwise

Conditional Statements
We will discuss several other important ways in which propositions can
be combined.

Definition ( 6 ) : Let p and q be propositions. The conditional statement

𝑝 → 𝑞 is the proposition "if p, then q ."
The conditional statement 𝑝 → 𝑞 is false when p is true and q is false,
and true otherwise.
In the conditional statement 𝑝 → 𝑞, p is called the hypothesis (or
antecedent or premise) and q is called the conclusion (or consequence).
 p q 𝑝⟶𝑞
T T T
T F F
F T T
F F T

𝒑 ⟶ 𝒒 ( p implies q ) is false when p is true and q is false , and true

otherwise .

The statement 𝑝 → 𝑞 is called a conditional statement because 𝑝 → 𝑞

asserts that q is true on the condition that p holds.
A conditional statement is also called an implication.
The truth table for the conditional statement 𝑝 → 𝑞 is shown in Table 5.

Note that the statement 𝑝 → 𝑞 is true when both p and q are true and
when p is false (no matter what truth value q has).

Example (7 ) : Let p be the statement "Maria learns discrete

mathematics" and q the statement "Maria will find a good job."
Express the statement 𝑝 → 𝑞 as a statement in English.

Solution: From the definition of conditional statements, we see that when

p is the statement "Maria learns discrete mathematics"
and q is the statement "Maria will find a good job," 𝑝 → 𝑞 represents the
statement :
"If Maria learns discrete mathematics, then she will find a good job."
BICONDITIONALS
We now introduce another way to combine propositions that expresses
that two propositions have the same truth value.

Definition (7 ) : Let p and q be propositions. The biconditional statement

𝑝 ↔ 𝑞 is the proposition "p if and only if q ."
The biconditional statement 𝑝 ↔ 𝑞 is true when p and q have the same
truth values, and is false otherwise.
Biconditional statements are also called bi-implications.

The truth table for 𝑝 ↔ 𝑞 is shown in Table 6. Note that the statement
𝑝 ↔ 𝑞 is true when both the conditional statements 𝑝 → 𝑞 and 𝑞 → 𝑝
are true and is false otherwise.
Table(6) : Truth table for the biconditional statement

𝒑 𝒒 𝒑↔𝒒
T T T
T F F
F T F
F F T
The biconditional statement 𝒑 ↔ 𝒒 ( p if and only q) is true when p
and q have the same truth values, 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 𝑝 ↔ 𝑞 :
"p is necessary and sufficient for q "
"if p then q , and conversely"
"p iff q ."
The last way of expressing the biconditional statement 𝑝 ↔ 𝑞 uses the
abbreviation "iff" for"if and only if."
Note that 𝑝 ↔ 𝑞 has exactly the same truth value as 𝑝 → 𝑞 ∧ (𝑞 → 𝑝)

Example ( 8) :
Let p be the statement "You can take the flight" and let q be the
statement "You buy a ticket."
Then 𝑝 ↔ 𝑞 is the statement :
"You can take the flight if and only if you buy a ticket."
This statement is true if p and q are either both true or both false, that is,
if you buy a ticket and can take the flight or if you do not buy a ticket and
you cannot take the flight. It is false when p and q have opposite truth
values, that is, when you do not buy a ticket, but you can take the flight
(such as when you get a free trip) and when you buy a ticket and cannot
take the flight(such as when the airline bumps you).

Truth Tables o f Compound Propositions

Example (9) : 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, corresponding to the
combinations of truth values TT, TF, FT, and FE
Table 7.
p q ¬𝑞 𝒑 ∨ ¬𝒒 (𝒑 ∧ 𝒒) 𝒑 ∨ ¬𝒒 → (𝒑 ∧ 𝒒)

T T F T T T
T F T T F F
F T F F F T
F F T T F F
 Exercises
1. Which of these sentences are propositions ? What are the truth values
of those that are propositions ?

a) Cairo is the capital of Syria.

b) Amman is the capital of Jordan.

c) 2+3 = 5 .

d) 5+7 =10.

e) x+2 = 11.

f) Answer this question.

g) x + y = -3

2. Which of these sentences are propositions ? What are the truth values
of those that are propositions ?

a) Do not pass go.

b) What time is it?

c) There are no trees on the moon.

d) x-1 =4.

e) The moon is made of green cheese.

f) 2n > 55.

3. Determine whether these biconditionals are true or false .

a) 2+2=4 if and only if 1+1=2

b) 1+1=2 if and only if 2+3=4

c) 1+1= 3 if and only if monkeys can fly.

d) 0>1 if and only if 2>1.

4. Determine whether each of these conditional statements is true or

false .

a) If 1+1=2 , then 2+2 =5.

b) If 1+1=3 , then 2+2 =4.

c) If 1+1=3 , then 2+2 =5.

d) If monkeys can fly , then 1+1=3.

5. Construct a truth table for each of these compound propositions.

a) 𝑝 ∧ ¬𝑝 b) 𝑝 ∨ ¬𝑝 c) (𝑝 ∨ ¬𝑞) ⟶ 𝑞

d) 𝑝∨𝑞 ⟶ 𝑝∧𝑞 e) 𝑝 ⟶ 𝑞 ⟷ (¬𝑞 ⟶ ¬𝑝 )

f) 𝑝 ⟷ 𝑞 ⊕ (𝑝 ⟷ ¬𝑞) g ) 𝑝 ⟶ ¬𝑞 ∨ 𝑟

h) 𝑝 ⟶ 𝑞 ∨ ¬𝑝 ⟶ 𝑟 i) 𝑝 ⟶ 𝑞 ∧ ¬𝑝 ⟶ 𝑟