Chapter One
PROPOSITIONAL
LOGIC
CHAPTER OBJECTIVES
▪ Interpret compound propositions using logical connective;
▪ Translate English statements into mathematical logic;
▪ Describe truth values of compound propositions;
▪ Construct truth tables of propositions;
▪ Define and differentiate tautology from contradiction;
▪ Specify the different logical equivalences;
▪ Relate some of the logical equivalences to practical
situation;
2
TOPICS
▪ Propositions, Logical Connectives and Truth Tables
▪ Negation, Conjunction and Disjunction
▪ Conditional and Biconditional Propositions
▪ Tautologies and Contradictions
▪ Logical Equivalence
▪ Arguments
▪ Applications of Logic in Circuits
3
PART 1
Introduction and
Preliminaries
IT 107 [Session 1]
LOGIC
▪ It is the discipline that deals with the methods of
reasoning. It is specifically concerned with whether
the reasoning is correct.
▪ It allows us to determine the validity of an argument
that depends on its logical form, not one the
particular meaning of the terms contains.
5
LOGIC
▪ Logical methods are used in mathematics to prove
theorems in computer science to verify the
correctness of programs, in the natural and physical
sciences to draw conclusions from experiments, in
the social sciences and in out everyday lives to solve
a multitude of problems.
6
PROPOSITION
▪ (otherwise known as statement) is a declarative
sentence.
▫ Declarative sentences are simply statements that relay
information. It states the facts and lets the reader know
something specific. It always ends with a period.
▪ It assigns one and only one of the two possible truth
values (or Boolean values): true (1) or false (0).
7
PROPOSITION: Examples
▪ The only positive integers that divide 5 are 1 and 5
itself.
▪ The sun will come out tomorrow.
▪ a + b = b + c if a = c
▪ 5<1
▪ 10 - 1 = 9
8
PROPOSITION: Wrong Examples
▪ 5-a = b
▪ What time is it?
▪ Help!
▪ Malolos is the best city in the province of
Bulacan.
▪ This sentence is false.
▪ Please pick up the pieces of papers.
9
More on Propositions
▪ In logic, statements are usually represented
symbolically by the lowercase letters to represent
propositional variables, i.e., variables that can be
replaced by statements.
▫ Atomic proposition – a statement that is not
decomposable into simple statement
▫ Compound proposition – a statement formed over
the composition of different statements through
logical connectives.
10
Logical Connectives
▪ These are the devices used to link or join pairs of
statement.
▫ Negation [“not”]
▫ Conjunction [“and”]
▫ Disjunction [“or”]
▫ Inclusive Disjunction
▫ Exclusive Disjunction
11
Truth Values vs. Truth Table
▪ Truth Value
▫ It is the assigned value to a given proposition.
▪ Truth Table
▫ It is the table which summarizes the truth values of
propositions. It displays all the possible combinations
of the given proposition, may be atomic or compound
propositions.
▫ [Remark] There are 2n possible combinations of
truth values to be considered in the truth table.
12
How to Construct a Truth Table?
▪ [Step 1] Prepare all possible combinations of truth
values for propositional variables. [This gives the
total number of rows in the truth table.]
▫ The number of variables will give the initial
number of columns.
▪ [Step 2] Obtain the truth values of each connective
and put these truth values in a new column.
13
14
15
Negation
▪ Let 𝑝 be a proposition. The statement “It’s not the
case that 𝑝” is called negation of 𝑝. It is denoted as
¬𝑝 𝑜𝑟 ~𝑝 read as “not 𝑝”.
▫ Inserting in statement the word “not”.
▫ It is false that p.
▫ It is not the case that p
Remark: The symbol “~“ is called curl or tilde and is used to
symbolize negation (or denial or contradictory). Other symbols
like “-” and “>” can also be used as negation.
16
Negation: Examples
▪ 𝑝: “Today is Friday.”
▫ ~ 𝑝: “Today is not Friday.”
▫ ~ 𝑝: “It is not the case that today is Friday.”
▫ ~ 𝑝: “It is false that today is Friday.”
▪ 𝑝: “The sun is not shining.”
Correct Case:
▫ ~ 𝑝: “The sun is shining.”
▫ ~ 𝑝: “ It is not the case that the sun is not shining.”
Wrong Case/s: [It introduces ‘double negation’.]
▫ ~ 𝑝: “It is not the case that the sun is shining.”
▫ ~ 𝑝: “It is false that the sun is shining.”
▪ 𝑝: “Five is an even number.”
▪ 𝑝: “I like Math.”
17
Negation: Truth Table
p ~p
1 0
0 1
18
[Sort of Review]
▪ Compound Propositions
▫ It is a combination of propositions formed from
existing propositions using logical connectives.
▫ Propositional Connectives
▫ It is an operation that combines two propositions
to yield a new one whose truth value depends
only on the truth values of the two original
propositions.
19
Conjunction
▪ Let 𝑝 and 𝑞 be propositions. The propositions “𝑝 and
𝑞” is denoted by 𝑝 ∧ 𝑞. This is also read as “the
conjunction of 𝑝 and 𝑞”. The conjunction “𝑝 ^ 𝑞” is
true if both 𝑝 and 𝑞 are true.
NOTE:
▪ “but” has the same logical meaning as “and”
▪ Other words used to conjoin two propositions
▫ moreover, furthermore, yet, still, however, also,
nevertheless, although, and so forth, comma (,) and colon (:)
are also used to conjoin two propositions
20
Conjunction: Truth Table
p q p^q
1 1 1
1 0 0
0 1 0
0 0 0
21
Conjunction: Examples
▫ 𝑝: “Today is Friday”
𝑞: “It is raining today”
𝑝 ∧ 𝑞: “Today is Friday and it is raining today”
▫ 𝑝: “I am sick”
𝑞: “I cannot take the exam”
𝑝 ∧ 𝑞: “I am sick and I cannot take the exam”
22
Disjunction
▪ Let 𝑝 and 𝑞 be propositions. The “disjunction of 𝑝 and 𝑞” is
denoted by 𝑝 ∨ 𝑞. This is also read as “𝑝 or 𝑞”.
▫ INCLUSIVE OR: If 𝑝 and 𝑞 are propositions then 𝑝 OR
𝑞 is true if either 𝑝 is true or 𝑞 is true or if both 𝑝 and
𝑞 are true.
▫ EXCLUSIVE OR: If 𝑝 and 𝑞 are propositions, the
“exclusive or” of 𝑝 and 𝑞 is denoted as 𝑝 ⊕ 𝑞. This
means that strictly one of the propositions must true
in order for the exclusive disjunction to be true.
▫ Note: “unless” may also be used in expressing the
23
disjunction of two propositions.
Disjunction: Truth Tables
Inclusive Disjunction Exclusive Disjunction
p q pvq p q p⊕q
1 1 1 1 1 0
1 0 1 1 0 1
0 1 1 0 1 1
0 0 0 0 0 0
24
Inclusive Disjunction
Inclusive Disjunction: Examples p q pvq
▪ 𝑝: “Plaridel is the capital of Bulacan” 1 1 1
▪ 𝑞: “Malolos is one of the cities found in Region III”
1 0 1
▪ 𝑝 ∨ 𝑞: “Plaridel is the capital of Bulacan or
Malolos is one of the cities found in Region III” 0 1 1
0 0 0
▪ 𝑝: “3 is an even number”
▪ 𝑞: “A century is 100 years”
▪ 𝑝 ∨ 𝑞: “3 is an even number or a century is 100
years.”
25
Exclusive Disjunction
Exclusive Disjunction: Examples p q p⊕q
▪ 𝑝: “I am looking at my seatmate” 1 1 0
▪ 𝑞: “I am looking at my teacher”
1 0 1
▪ 𝑝 ⊕ 𝑞: “I am looking at my seatmate or I am
looking at my teacher”
0 1 1
▪ 𝑝: “I can take a plane going to Romblon” 0 0 0
▪ 𝑞: “I can take a ferry going to Romblon”
▪ 𝑝 ⊕ 𝑞: “I can take a plane or a ferry going to
Romblon”
26
Note on Compound Propositions
• To connote groupings:
• “both” goes with “and”
• “either” goes with “or”
• “neither 𝑝 nor 𝑞” is the same as “not either 𝑝 or 𝑞”
27
Exercises [Part 1]
▪ Use the symbols ~, ^ and v, and write the following
statements.
▫ both p or q and r
▫ p or both q and r
▫ either p and q or r
▫ p and either q or r
▫ neither p nor q
28
Exercises [Part 2]
Use the symbols ~, ∧ and ∨ to write the following statements.
[Note: Use grouping symbols.]
▫ 𝑝: “-6 is a positive number”
▫ 𝑞: “3 is a positive number”
▫ 𝑟: “ 5 is an irrational number”
1. -6 and 3 are both not positive numbers
2. -6 and 3 are not both positive numbers
3. either -6 is a positive number or 3 is a positive number and 5
is irrational
4. 5 is irrational but -6 is not a positive number
5. either -6 is a positive number or 3 is a positive number but
they are not both positive numbers
29
Conditional Propositions
▪ If p and q are propositions, the compound statement
“if p, then q” is called an implication or conditional
statement and is denoted by p → q:
▫ p is called the hypothesis (or antecedent)
▫ q is called the conclusion (or consequent)
NOTE:
▪ 𝑝→𝑞 is equivalent to the following expressions:
▫ 𝑝 implies 𝑞, If 𝑝 then 𝑞, 𝑞 if 𝑝, 𝑞 whenever 𝑝, 𝑝 is sufficient
for 𝑞, 𝑝 is necessary for 𝑞
30
Conditional Propositions: Example
▪ 𝑝: “I am late”
▪ 𝑞: “I cannot take the seatwork”
▪ 𝑝 → 𝑞: “If I am late then I cannot take the seatwork.”
▪ 𝑝: “Today is Monday.”
▪ 𝑞: “I have a test today”
▪ 𝑝 → 𝑞: “If today is Monday then I have a test today”
31
Conditional Propositions: Example
Let 𝑝, 𝑞, 𝑎𝑛𝑑 𝑟 be propositions:
▫ 𝑝: It is a long weekend.
▫ 𝑞: I will stay at home.
▫ 𝑟: Lucky is not going to watch Riverdale.
▪ If it is not a long weekend, then Lucky is not going to watch
Riverdale.
▪ If it is a long weekend, then I will stay at home.
▪ I will stay at home if it is a long weekend.
▪ I will stay at home whenever it is a long weekend.
32
Note on Conditional Proposition
▪ 𝑝 → 𝑞 is false when 𝑝 is true and 𝑞 is false [a true
statement cannot imply a false one]
EXAMPLE
▪ 𝑝: “1 > 2”
▪ 𝑞: “4 < 8”
▪ 𝑝→𝑞: “If 1 > 2 then 4 < 8”
▪ 𝑞→𝑝: “If 4 < 8 then 1 > 2 “
33
Note on Conditional Proposition
p q p→q
▪ As observed, the truth values for the
conjunction - “p ∧ q” and “q ∧ p” are 1 1 1
always the same. Also, the truth tables
for the disjunction “p ∨ q” and “q ∨ p” are 1 0 0
identical.
0 1 1
▪ However, it is false that the truth values 0 0 1
for p → q and q → p are the same as seen
in the previous example.
34
Conditional Proposition: Truth Table
p q p→q
1 1 1
1 0 0
0 1 1
0 0 1
35
Conditional Proposition: Truth Table p q p→q
Give examples of or tell why no such example exists: 1 1 1
1. A false implication with a false conclusion 1 0 0
2. A true implication with a true conclusion. 0 1 1
0 0 1
3. A true implication with a false conclusion
4. A false implication with a false hypothesis
5. A false implication with a true hypothesis
6. A true implication with a false hypothesis
36
Note on Conditional Proposition
▪ Given the conditional proposition p → q, then
▫ the converse of p → q is the implication q → p,
▫ the contrapositive of p→ q is the implication ~q→ ~p,
▫ the inverse of p → q is the implication of ~p→~q
37
Note on Conditional Proposition
EXAMPLE: Let p: it is hot; and q: I will go to the mall
▪ Implication
▫ p → q: If it is hot, then I will go to the mall.
▪ Converse
▫ q → p: If I will go to the mall, then it is hot.
▪ Contrapositive
▫ ~q → ~p: If I will not go to the mall, then it is not hot.
▪ Inverse
▫ ~p → ~q: If it is not hot, then I will not go the mall.
38
Conditional Proposition: Truth Table
p q ~p ~q p→q q→p ~p → ~q ~q → ~p
1 1 0 0 1 1 1 1
1 0 0 1 0 1 1 0
0 1 1 0 1 0 0 1
0 0 1 1 1 1 1 1
39
Biconditional Propositions
▪ If p and q are propositions, the compound proposition “p if
and only if q” is called a biconditional proposition and is
written p q.
▪ The connective “p if and only if q” is the conjunction of
p → q and its converse q → p, the truth value of
proposition p q is defined by the truth table below.
NOTE:
▪ 𝑝 𝑞 is equivalent to the following expressions:
▫ 𝑝 is equivalent to 𝑞, 𝑝 if and only if 𝑞, 𝑝 is necessary and
40 sufficient for 𝑞, if 𝑝 then 𝑞 and conversely
Biconditional Propositions: Examples
▪ 𝑝: “David is the son of Ricky.”
▪ 𝑞: “Ricky is the father of David.”
▪ 𝑝 𝑞: “David is the son of Ricky if and only if Ricky is the
father of David.”
▪ 𝑝: “12 is divisible by 2.”
▪ 𝑞: “12 is even.”
▪ 𝑝 𝑞: “12 is divisible by 2 if and only if 12 is even”
41
Note on Biconditional Proposition
▪ 𝑝 𝑞 is true when both 𝑝 𝑎𝑛𝑑 𝑞 has the same logical
truth value
EXAMPLE
▪ 𝑝: “7 > 12”
▪ 𝑞: “7 is even”
▪ 𝑝 𝑞: “7 > 12 if and only if 7 is even.”
▪ 𝑝: “A square is a quadrilateral.”
▪ 𝑞: “A triangle has four vertices.”
▪ 𝑝 𝑞: “A square is a quadrilateral if and only if a triangle
has four vertices.”
42
Biconditional Proposition: Truth Table
p q p q
1 1 1
1 0 0
0 1 0
0 0 1
43