Lecture-1

Introduction to Propositional Logic and Truth Tables

Proposition
What is a Proposition
Definition
A proposition is a declarative sentence (i.e. a sentence that declares a fact) that is either true or false,
but not both.

Examples
 Pakistan’s GDP is growing exponentially.
 Mr. Jinnah was the most well-dressed gentleman of his time.
 Green shirts will win the upcoming T-20 world cup.
 Lahore is the capital of Punjab.
 GE-24 are won by N-League.
 5÷2=2
 There does not exist an even prime.

Non-Propositional Statements
 Commands and Imperatives
o Close the door.
o Study for your exam.
o Please pass the salt.
 Questions
o What time is it?
o Have you fulfilled your dream?
o What is your favorite time of the day?
 Exclamation or Expressions
o Wow, that’s amazing!
o Ah, that hurts!
o Oh, I forgot my keys!
 Statements that Lacks a Clear Truth Value
o Drive safely!
o Have a nice day!
o Stay alert!
o 𝑥+1=3
o 𝑥+𝑦 =𝑧

SHEIKH MUHAMMAD SALEEM SHAHZAD 1

The propositional variables are usually denoted by p, q, r, s etc. Also, the truth value of a proposition is
true, denoted by T, when the proposition is true, and the truth value of a proposition is false, denoted by F,
when the proposition is false. Also, the area of logic that deals with propositions is called Propositional
Logic or Propositional Calculus.

Logical Connectives
Now, we shift our focus to the process of constructing new propositions from one or more existing
propositions. These newly formed propositions are known as Compound Propositions. In this section, we
explore how logical connectives allow us to combine propositions to create compound statements with
distinct truth values and meanings.

Negation
Definition
The negation of a proposition 𝒑, denoted as ~𝑝 or 𝑝̅ , is the statement:
“It is not the case that 𝒑”
The proposition ~𝑝 is read “not 𝑝”. The truth value of negation 𝑝, ~𝑝, is the opposite of the truth value
of 𝑝.

The following table shows the truth value of ~𝑝 for every possible truth value of 𝑝.

The Truth Table for the Negation of a Proposition

𝒑 ~𝒑
T F
F T

Examples
 The negation of the proposition “Wasim Akram is a former captain of Pakistan’s Cricket team” Is:
“It is not the case that Wasim Akram is a former captain of Pakistan’s Cricket team.”
This negation can be more simply expressed as:
“Wasim Akram is NOT a former captain of Pakistan’s Cricket team.”

Try yourself
Find negation of the following statements:

 All politicians are honest.

 Every student loves mathematics.
 If it's sunny, then I'll go for a run.
 The sum of all angles of a triangle is 180° .
 Every prime number greater than 2 is odd.

SHEIKH MUHAMMAD SALEEM SHAHZAD 2

Negation operator produces a proposition out of single proposition. Next, we will explore those operators
which combine two or more proposition to produce a compound proposition.

Conjunction
Definition
The conjunction of two proposition 𝒑 and 𝒒, denoted as 𝒑 ˄ 𝒒, is the proposition “𝑝 and 𝑞”. The
conjunction is true only if both 𝑝 and 𝑞 are true, otherwise false.

The following table shows the truth value of 𝑝 ˄ 𝑞 for every possible truth value of 𝑝 and 𝑞.

The Truth Table for the Conjunction of Two Proposition Namely 𝒑 and 𝒒
𝒑 𝒒 𝒑˄𝒒
T T T
T F F
F T F
F F F

Examples
The conjunction of the two propositions 𝑝 and 𝑞 where 𝑝 is the proposition “The flight is on time” and 𝑞 is
the proposition “I have my passport” is given as:
“The flight is on time, and I have my passport.”
This compound proposition is true when both of the original propositions 𝑝 and 𝑞 are true, otherwise false.

Try yourself
Find conjunction of following pairs of propositions.

𝒑 𝒒
The student attended all classes today. The student completed all homework assignments.
He did a 30-minute cardio workout. He followed a balanced diet.
The suitcase is packed. The tickets are printed.
The venue is booked. The invitations are sent.
She had a dental checkup. She had a vision test.

Disjunction
Definition
The disjunction of two proposition 𝒑 and 𝒒, denoted as 𝒑 ˅ 𝒒, is the proposition “𝑝 or 𝑞”. The
disjunction is true when at least one of the propositions is true, otherwise false.

Depending upon the context, the word ‘or’ is said to have two possible meanings as follows:

SHEIKH MUHAMMAD SALEEM SHAHZAD 3

  Inclusive or: The compound proposition in this case is true only when
o Both 𝑝 and 𝑞 are true
o Either of 𝑝 and 𝑞 is true.
Example: The ‘inclusive or’ is used in the statement “Students who have taken Computer Science
or Calculus can take this class.” This means that students who have taken either Computer Science,
Calculus, or both courses are eligible to take the class. Following is the truth table in this case:

The Truth Table for the Disjunction (inclusive or) of Two Proposition Namely 𝒑 and 𝒒
𝒑 𝒒 𝒑˅𝒒
T T T
T F T
F T T
F F F

 Exclusive or: The compound proposition in this case is true only when either of 𝑝 and 𝑞 is true
BUT NOT BOTH. This is symbolically written as 𝑝 ⊕ 𝑞.
Example: The ‘exclusive or’ is used in the statement “Students who have taken Computer Science
or Calculus, but not both, can take this class.” This means that students who have taken either
Computer Science, Calculus, but not both are eligible to take the class. Following is the truth table
in this case:

The Truth Table for the Disjunction (exclusive or) of Two Proposition Namely 𝒑 and 𝒒
𝒑 𝒒 𝒑 ⊕ 𝒒
T T F
T F T
F T T
F F F

Conditional Statements
Definition
Let 𝑝 and 𝑞 be two proposition. The conditional statement 𝑝 → 𝑞 is the proposition “If 𝒑, then 𝒒”. The
conditional statement is false only when 𝑝 is true and 𝑞 is false, otherwise true. In this conditional
statement, 𝑝 is known as antecedent/hypothesis/premise and 𝑞 is called conclusion/consequence. A
conditional statement is sometimes referred to as an Implication as well.

The conditional statements are so important in Mathematical reasoning that a variety of terminologies are
used to express 𝑝 → 𝑞. For example:

 If 𝑝, then 𝑞
 𝑝 implies 𝑞
 If 𝑝, 𝑞
 𝑝 only if 𝑞
SHEIKH MUHAMMAD SALEEM SHAHZAD 4
  𝑝 is sufficient for 𝑞
 A sufficient condition for 𝑞 is 𝑝
 𝑞 if 𝑝
 𝑞 whenever 𝑝
 𝑞 when 𝑝
 𝑞 is necessary for 𝑝
 A necessary condition for 𝑞 is 𝑝
 𝑞 follows from 𝑝
 𝑞 unless ~𝑝
The following table shows the truth value of 𝑝 → 𝑞 for every possible truth value of 𝑝 and 𝑞.

The Truth Table for the conditional statement 𝒑 → 𝒒 of Two Proposition Namely 𝒑 and 𝒒
𝒑 𝒒 𝒑→𝒒
T T T
T F F
F T T
F F T

Example
One can think of a conditional statement as a pledge. Consider a politician who pledges to lower taxes if he
gets elected. Specifically, he makes the following commitment:
“If I get elected, I will lower taxes.”
The nation can only accuse him of breaking his vow if he gets elected and then fails to lower taxes. In the
other scenarios—either he is elected and fulfills his promise, or he is not elected at all—he cannot be
accused of not fulfilling his promise.

Try Yourself
 If it rains, then the roads will be slippery.
 If you exercise regularly, then you will improve your cardiovascular health.
 If you save money consistently, then you will have financial security in the future.
 If children eat a balanced diet, then they will have better growth and development.
 If you water the plants regularly, then they will thrive.

Converse, Inverse and Contrapositive

One can form new conditional statements based on 𝑝 → 𝑞 as follows:
 Converse (𝑞 → 𝑝)
 Inverse (~𝑝 → ~𝑞)
 Contrapositive (~𝑞 → ~𝑝)

SHEIKH MUHAMMAD SALEEM SHAHZAD 5

Out of these, only contrapositive have the same truth value as that of 𝑝 → 𝑞. Also, when two compound
propositions have same truth values, they are regarded as “Equivalent”. Consequently, we can say that a
conditional statement and its contrapositive are always equivalent.

SHEIKH MUHAMMAD SALEEM SHAHZAD 6