Chapter 1: PROPOSITIONAL LOGIC

IT 107 – Discrete Structures for IT

conclusions from experiments, in the

CHAPTER OBJECTIVES social sciences and in out everyday
lives to solve a multitude of problems.

★ Interpret compound propositions using PROPOSITION

logical connective;
★ Translate English statements into ★ (Otherwise known as statement) is a
mathematical logic; declarative sentence.
★ Describe truth values of compound ○ Declarative sentences are
propositions; simply statements that relay
★ Construct truth tables of propositions; information. It states the facts
★ Define and differentiate tautology and lets the reader know
from contradiction; something specific. It always
★ Specify the different logical ends with a period.
equivalences; ★ It assigns one and only one of the two
★ Relate some of the logical possible truth values (or Boolean
equivalences to practical situation; values): true (1) or false (0).
TOPICS Proposition Examples:
★ The only positive integers that divide
5 are 1 and 5 itself.
★ Propositions, Logical Connectives and ★ The sun will come out tomorrow.
Truth Tables ★ a + b = b + c if a = c
★ Negation, Conjunction and ★ 5<1
Disjunction ★ 10 - 1 = 9
★ Conditional and Biconditional Proposition Wrong Examples:
Propositions ★ 5-a = b
★ Tautologies and Contradictions ★ What time is it?
★ Help!
★ Logical Equivalence
★ Malolos is the best city in the province
★ Arguments of Bulacan.
★ Applications of Logic in Circuits ★ This sentence is false.
PART 1 ★ Please pick up the pieces of papers.
More on Propositions
★ In logic, statements are usually
Introduction and Preliminaries LOGIC represented symbolically by the
★ It is the discipline that deals with the lowercase letters to represent
methods of reasoning. It is specifically propositional variables, i.e., variables
that can be replaced by statements.
concerned with whether the reasoning
○ Atomic proposition – a
is correct. statement that is not
★ It allows us to determine the validity decomposable into simple
of an argument that depends on its statement
logical form, not one the particular ○ Compound proposition – a
meaning of the terms contains. statement formed over the
★ Logical methods are used in composition of different
statements through logical
mathematics to prove theorems in
connectives.
computer science to verify the
correctness of programs, in the natural Logical Connectives
and physical sciences to draw

1
Chapter 1: PROPOSITIONAL LOGIC
IT 107 – Discrete Structures for IT

★ These are the devices used to link or ○ It is false that p.

join pairs of statement. ○ It is not the case that p
★ Negation [“not”] Remark: The symbol “~“ is called curl or
★ Conjunction [“and”] tilde and is used to symbolize negation (or
★ Disjunction [“or”] denial or contradictory). Other symbols like
○ Inclusive Disjunction “-” and “>” can also be used as negation.
○ Exclusive Disjunction Negation: Examples

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 ★ 𝑝: “Today is Friday.”
propositions.
■ [Remark] There are
2n possible
combinations of truth
values to be
considered in the truth
table.
How to Construct a Truth Table?
★ [Step 1] Prepare all possible
combinations of truth values for
propositional variables. [This gives ○ ~ 𝑝: “Today is not Friday.”
the total number of rows in the truth ○ ~ 𝑝: “It is not the case that
table.] today is Friday.”
○ The number of variables will ○ ~ 𝑝: “It is false that today is
give the initial number of Friday.”
columns. ★ 𝑝: “The sun is not shining.”
★ [Step 2] Obtain the truth values of
each connective and put these truth Correct Case:
values in a new column. ★ ~ 𝑝: “The sun is shining.”
★ ~ 𝑝: “ It is not the case that the sun is
NEGATION not shining.”
Wrong Case/s: [It introduces ‘double
★ Let 𝑝 be a proposition. The statement negation’.]
“It’s not the case that 𝑝” is called
negation of 𝑝. It is denoted as ¬ ~𝑝 ○ ~ 𝑝: “It is not the case that the
read as “not 𝑝”. sun is not shining.”
○ Inserting in statement the ○ ~ 𝑝: “It is false that the sun is
word “not”. not shining.”

2
Chapter 1: PROPOSITIONAL LOGIC
IT 107 – Discrete Structures for IT

○ 𝑝: “Five is an even number.” forth, comma (,) and colon (:)

○ 𝑝: “I like Math.” are also used to conjoin two
propositions
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”

Negation: Truth Table DISJUNCTION

[Sort of Review]
★ Let 𝑝 and 𝑞 be propositions. The
★ Compound Propositions “disjunction of 𝑝 and 𝑞” is denoted by
○ It is a combination of 𝑝 ∨ 𝑞. This is also read as “𝑝 or 𝑞”.
propositions formed from ○ INCLUSIVE OR: If 𝑝 and 𝑞
existing propositions using are propositions then 𝑝 OR 𝑞
logical connectives. is true if either 𝑝 is true or 𝑞 is
○ Propositional Connectives true or if both 𝑝 and 𝑞 are
■ It is an operation that true.
combines two ○ EXCLUSIVE OR: If 𝑝 and 𝑞
propositions to yield a are propositions, the
new one whose truth “exclusive or” of 𝑝 and 𝑞 is
value depends only on denoted as 𝑝 ⊕ 𝑞. This means
the truth values of the that strictly one of the
two original propositions must true in
propositions. order for the exclusive
disjunction to be true.
CONJUNCTION ■ Note: “unless” may
also be used in
expressing the
★ Let 𝑝 and 𝑞 be propositions. The disjunction of two
propositions “𝑝 and 𝑞” is denoted by 𝑝 propositions.
∧ 𝑞. This is also read as “the
Disjunction: Truth Tables
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

3
Chapter 1: PROPOSITIONAL LOGIC
IT 107 – Discrete Structures for IT

Note on Compound Propositions

• To connote groupings:
• “both” goes with “and”
• “either” goes with “or”
• “neither pnor q ” is the same as “not
either p or q ”

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
Exercises [Part 2]
Use the symbols ~, ∧ and ∨ to write the
following statements. [Note: Use grouping
symbols.]
▫ p :“-6 is a positive number”
▫ q : “3 is a positive number”
▫ r : “√ 5 is an irrational
number”
Inclusive Disjunction: Examples 1. -6 and 3 are both not
▪ 𝑝: “Plaridel is the capital of Bulacan” positive numbers
2. -6 and 3 are not both
▪ 𝑞: “Malolos is one of the cities found positive numbers
in Region III” 3. Either -6 is a positive
▪ 𝑝 ∨ 𝑞: “Plaridel is the capital of number or 3 is a positive number and
Bulacan or Malolos is one of the cities
found in Region III”
√ 5 is irrational
▪ 𝑝: “3 is an even number” 4. √ 5 is irrational but -6 is not
▪ 𝑞: “A century is 100 years” a positive number
▪ 𝑝 ∨ 𝑞: “3 is an even number or a 5. Either -6 is a positive
century is 100 years.” number or 3 is a positive
number but they are not both
Exclusive Disjunction: Examples positive numbers
▪ p :“I am looking at my seatmate” Conditional Propositions
▪ q : “I am looking at my teacher” ▪ If p and q are propositions, the
▪ p ⊕q : “I am looking at my seatmate compound statement “if p, then q” is
or I am looking at my teacher” called an implication or conditional
▪ p :“I can take a plane going to statement and is denoted by p  q:
Romblon” ▫ p is called the hypothesis (or
▪ q : “I can take a ferry going to antecedent)
Romblon” ▫ q is called the conclusion (or
▪ p ⊕q : “I can take a plane or a ferry consequent)
going to Romblon”

4
Chapter 1: PROPOSITIONAL LOGIC
IT 107 – Discrete Structures for IT

▪ 𝑞: “4 < 8”
NOTE: T
▪ 𝑝→𝑞 is equivalent to the following ▪ 𝑝→𝑞: “If 1 > 2 then 4 < 8”
expressions: T
▫ 𝑝 implies 𝑞, If 𝑝 then 𝑞, 𝑞 if ▪ 𝑞→𝑝: “If 4 < 8 then 1 > 2 “
𝑝, 𝑞 whenever 𝑝, 𝑝 is F
sufficient for 𝑞, 𝑝 is necessary Note on Conditional Proposition
for 𝑞  As observed, the truth values for the
conjunction - “p ∧ q” and “q ∧ p” are
Conditional Propositions: Example always the same. Also, the truth tables
for the disjunction “p ∨ q” and “q ∨
p” are identical.

▪ However, it is false that the truth

values for p  q and q  p are the
same as seen in the previous example.

Conditional Proposition: Truth Table

▪ 𝑝: “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”
Conditional Propositions: Example
Let 𝑝, 𝑞, 𝑎𝑛𝑑 𝑟 be propositions:
▫ 𝑝: It is a long weekend.
▫ 𝑞: I will stay at home.
▫ 𝑟: Lucky is not going to watch
Riverdale. Give examples of or tell why no such
▪ If it is not a long weekend, then Lucky
example exists:
is not going to watch Riverdale.
1. A false implication with a false
▪ If it is a long weekend, then I will stay
conclusion
at home.
2. A true implication with a true
▪ I will stay at home if it is a long
conclusion.
weekend.
3. A true implication with a false
▪ I will stay at home whenever it is a
conclusion
long weekend.
4. A false implication with a false
Note on Conditional Proposition
hypothesis
▪ 𝑝 → 𝑞 is false when 𝑝 is true and 𝑞 is
5. A false implication with a true
false [a true statement cannot imply a
hypothesis
false one]
6. A true implication with a false
EXAMPLE
hypothesis
▪ 𝑝: “1 > 2”
F Note on Conditional Proposition

5
Chapter 1: PROPOSITIONAL LOGIC
IT 107 – Discrete Structures for IT

▪ Given the conditional proposition p  ▪ 𝑝↔𝑞: “David is the son of Ricky if

q, then and only if Ricky is the father of
▫ the converse of p  q is the David.”
implication q  p, ▪ 𝑝: “12 is divisible by 2.”
▫ the contrapositive of p q is ▪ 𝑞: “12 is even.”
the implication ~q ~p, ▪ 𝑝↔𝑞: “12 is divisible by 2 if and only
▫ the inverse of p  q is the if 12 is even”
implication of ~p~q
Note on Biconditional Proposition
Note on Conditional Proposition ▪ 𝑝↔𝑞 is true when both 𝑝 𝑎𝑛𝑑 𝑞 has
EXAMPLE: Let p: it is hot; and q: I will go to the same logical truth value
the mall
▪ Implication EXAMPLE
▫ p  q: If it is hot, then I will  p :“7 > 12”
go to the mall. F
▪ Converse  q : “7 is even”
▫ q  p: If I will go to the mall, F
then it is hot.  p ↔q : “7 > 12 if and only if
7 is even.” T
▪ Contrapositive  p :“A square is a
▫ ~q  ~p: If I will not go to quadrilateral.” T
the mall, then it is not hot.  q : “A triangle has four
▪ Inverse vertices.” F
▫ ~p  ~q: If it is not hot, then  p ↔q : “A square is a
I will not go the mall. quadrilateral if and only if a
triangle has four vertices.”
F
Conditional Proposition: Truth Table
Biconditional Propositions Biconditional Proposition: Truth Table
▪ 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
sufficient for 𝑞, if 𝑝 then 𝑞
and conversely
Biconditional Propositions: Examples
▪ 𝑝: “David is the son of Ricky.”
▪ 𝑞: “Ricky is the father of David.”