INTRODUCTION TO

LOGIC
MS101-DISCRETE MATHEMATICS
 LOGIC
• The term “logic” is often used, but not always in its technical sense.
• It is technically defined as the science or study of how to evaluate
arguments and reasoning.
• It helps us to differentiate correct reasoning from poor reasoning.
• It also defined as discipline that deals with the method of reasoning.
LOGICAL REASONING
• Logical reasoning is used in Mathematics to prove theorems and
to verify the correctness of programs.
MATHEMATICAL LOGIC
• A branch of mathematics with close connections to computer
science.
• It includes both the mathematical study of logic and the
applications of formal logic to other areas of mathematics.
STATEMENT
• A statement or proposition is a declarative sentence that is either
true or false, but not both.
• The truth value of the statements is the truth and falsity of the
statements.
EXAMPLE
• WHICH OF THE FOLLOWING ARE STATEMENTS?
1. Manila is the capital of the Philippines.
2. What day is it?
3. Help me, please.
4. Maria speaks accurately.
EXERCISE
DETERMINE WHICH OF THE FOLLOWING ARE
STATEMENTS.
1. 2 + 4 = 8.
2. The world is flat.
3. 3𝑥 + 4𝑦 = 1.
4. It will rain tomorrow.
LOGICAL CONNECTIVES
• A propositional variable is a variable which used to represent a
statement.
• A formal propositional written using propositional logic
notation, 𝑝, 𝑞, and 𝑟 are used to represent statements.
• Logical connectives are used to combine simple statements
which are referred as compound statements
LOGICAL CONNECTIVES
• A compound statement is a statement composed of two or more
simple statements connected by logical connectives “and”, “or”,
“if then”, “not”, “if and only if”, and “exclusive-or”.
• Six main logical connectives are the following: conjunction,
disjunction, negation, conditional, biconditional, and eexclusive-
or.
CONJUNCTION
• The conjunction of the statement 𝑝 and 𝑞 is the compound
statement "𝑝 𝑎𝑛𝑑 𝑞".
• Symbolically, 𝑝 ∧ 𝑞, where ∧ is the symbol for "𝑎𝑛𝑑".
• PROPERTY 1: If 𝑝 is true and 𝑞 is true, then 𝑝 ∧ 𝑞 is true;
otherwise 𝑝 ∧ 𝑞 is false. Meaning, the conjunction of the
statements is true only if each statement is true.
TRUTH TABLE OF CONJUNCTION
𝒑 𝒒 𝒑∧𝒒
T T T
T F F
F T F
F F F
EXAMPLE: Determine the truth value of each of the
following conjunction.
1. 2 + 6 = 9 and 2 × 6 = 12.
2. Manny Pacquiao is a boxing champion and Gloria Macapagal
Arroyo is the first female President of the Philippines.
3. Today is January 23, 2024 and it’s Tuesday.
DISJUNCTION
• The disjunction of the statement 𝑝,and 𝑞 is the compound
statement "𝑝 𝑜𝑟 𝑞“. Symbolically, 𝑝 ∨ 𝑞, where ∨ is the symbol for
"𝑜𝑟“.
• PROPERTY 2: If 𝑝 is true or 𝑞 is true or if both 𝑝 and 𝑞 are true,
then 𝑝 ∨ 𝑞 is true; otherwise 𝑝 ∨ 𝑞 is false. Meaning the
disjunction of the two statements is false only if each statement
is false.
TRUTH TABLE OF DISJUNCTION
𝒑 𝒒 𝒑∨𝒒
T T T
T F T
F T T
F F F
EXAMPLE: Determine the truth value of each of the
following disjunction.
1. 2 + 6 = 9 or 1 − 5 = −4.
2. 5 is a prime number or 4 is divisible by 3.
3. 10 is a composite number or 6 is a multiple of 3.
NEGATION
• The negation of the statement 𝑝 is denoted by ∼ 𝑝, where ∼ is
the symbol for "𝑛𝑜𝑡“.
• PROPERTY 3: If 𝑝 is true, ∼ 𝑝 is false. Meaning, the truth value
of the negation of the statement is always the reverse of the truth
value of the original statement.
TRUTH TABLE OF NEGATION
𝒑 ∼𝒑

T F

F T
EXAMPLE: Find the corresponding negation of the
following statements.
1. 2 + 3 = 8
2. Math is difficult
3. Sofia is a girl.
CONDITIONAL
• The conditional (or implication) of the statements 𝑝 and 𝑞 is the
comp "𝑖𝑓 𝑝 𝑡ℎ𝑒𝑛 𝑞". Symbolically, 𝑝 → 𝑞, where → is the symbol
for "𝑖𝑓 𝑡ℎ𝑒𝑛". 𝑝 is called the hypothesis ( or antecedent , or
premise) and 𝑞 is called conclusion (or consequent, or
consequence).
• PROPERTY 4: The conditional statement 𝑝 → 𝑞 is false only
when 𝑝 is true and 𝑞 is false; otherwise 𝑝 → 𝑞 is true.
TRUTH TABLE OF CONDITIONAL
𝒑 𝒒 𝒑→𝒒
T T T
T F F
F T T
F F T
EXAMPLE: Obtain the truth value of each of the
following conditional statements.
1. If vinegar is sweet, then sugar is sour.
2. 2+5 =7 is a sufficient condition for 5+6=1.
3. If 14-8=4 then 6÷ 3=2.
BICONDITIONAL
• The biconditional of the statement 𝑝 and 𝑞 is the compound
statement "𝑝 if and only if 𝑞“. Symbolically, 𝑝 ↔ 𝑞, where ↔ is
the symbol for “if and only if“.
• PROPERTY 5: If 𝑝 and 𝑞 are true or both false, then 𝑝 ↔ 𝑞 is true
𝑝 and 𝑞 have opposite truth values, then 𝑝 ↔ 𝑞 is false.
EXAMPLE: Determine the truth values of each of
the following biconditional statements.
1. 2 + 8 = 10 if and only if 6 − 3 = 3.
2. 8 − 2 = 5 is necessary and sufficient for 4 + 2 = 7.
3. Manila is the capital of the Philippines is equivalent to Seoul is
the capital of Japan.
TRUTH TABLE OF BICONDITIONAL
𝒑 𝒒 𝒑↔𝒒
T T T
T F F
F T F
F F T
EXCLUSIVE-OR
• The exclusive-or of the statement 𝑝 and 𝑞 is the compound
statement "𝑝 exclusive-or 𝑞“. Symbolically, 𝑝 ⊕ 𝑞, where ⊕ is the
symbol for “exclusive-or”.
• PROPERTY 6: If 𝑝 and 𝑞 are true or both false, the 𝑝 ⊕ 𝑞 is false;
if 𝑝 and 𝑞 have opposite values, then 𝑝 ⊕ 𝑞 is true.
• It can be noted that the truth values of 𝑝 ⊕ 𝑞 is the negation of
the truth values 𝑝 ↔ 𝑞.
EXAMPLE: Determine the exclusive-or statement
of the following simple statements.
• 𝑝 − Sofia will take her lunch in Batangas
• 𝑞 − Sofia will have her lunch in Singapore.
TRUTH TABLE OF BICONDITIONAL
𝒑 𝒒 𝒑⊕𝒒
T T F
T F T
F T T
F F F
EVALUATING STATEMENT FORMULA
WITHOUT PARENTHESIS
• ∼(top priority)
• ∧ (second priority)
• ∨ (third priority)
• → (fourth priority)
• ↔ (fifth priority)
ACTIVITY: Construct the truth tables of the
following statements.
1. ∼ 𝑝 ∨∼ 𝑞
2. 𝑝 → (𝑝 ↔ 𝑞)
3. 𝑝 → 𝑞 ⊕ (𝑞 ∧∼ 𝑟)
THREE IMPORTANT COMPOUND STATEMENTS
• Tautology
• Contradiction
• Contingency
TAUTOLOGY
• It is a compound statement that is true for all possible
combinations of the truth values of the propositional variables
also called logically true.
CONTRADICTION
• It is a compound statement that is false for all possible
combinations of the truth values of its propositional variables.
• Also called logically false or absurdity.
CONTINGENCY
• It is a compound statement that can be either true or false,
depending on the truth values of the propositional variables that
are neither tautology nor contradiction.
EXAMPLE:
Write the truth table for each of the following compound
statements and determine whether the compound statement is
tautology, contradiction, or contingency.
a. ∼𝑝∧𝑞 →𝑞
b. 𝑝 → 𝑞 ∧ (𝑝 →∼ 𝑞)
c. ∼ 𝑝 ∨ 𝑞 ⊕ (𝑝 → 𝑞)
LOGICALLY EQUIVALENT
• Two statements are said to be logically equivalent (or
equivalent) if they have the same truth value for every row of
the truth table, that is, if 𝑥 → 𝑦 is a tautology.
• Symbollically, 𝑥 ≡ 𝑦.
EXAMPLE:
Show that the following are equivalent.
1. 𝑝 ∧ (𝑞 ∨ 𝑟) and 𝑝 ∧ 𝑞 ∨ (𝑝 ∧ 𝑟)
2. 𝑝 → 𝑞 and ∼ 𝑞 →∼ 𝑝
3. 𝑝 ↔ 𝑞 and 𝑝 → 𝑞 ∧ (𝑞 → 𝑝)
LAWS OF LOGICAL EQUIVALENCE
• Let 𝑝, 𝑞, and 𝑟 stands for any statements. Let 𝑇 indicates
tautology and 𝐹 indicates contradiction.
LAWS LOGICAL EQUIVALENCE
Commutative 𝑝 ∨ 𝑞 ≡ 𝑞 ∨ 𝑝𝑝 ∧ 𝑞 ≡ 𝑞 ∧ 𝑝

Associative 𝑝∧ 𝑞∧𝑟 ≡ 𝑝∧𝑞 ∧𝑟

𝑝∨ 𝑞∨𝑟 ≡ 𝑝∨𝑞 ∨𝑟
Distributive 𝑝 ∨ 𝑞 ∧ 𝑟 ≡ 𝑝 ∨ 𝑞 ∧ (𝑝 ∨ 𝑟)𝑝 ∧ 𝑞 ∨ 𝑟
≡ 𝑝 ∧ 𝑞 ∨ (𝑝 ∧ 𝑟)

Identity 𝑝∧𝑇 ≡𝑝
𝑝∨𝐹 ≡𝑝
LAWS OF LOGICAL EQUIVALENCES
LAWS LOGICAL EQUIVALENCE
Inverse 𝑝 ∧∼ 𝑝 ≡ 𝐹
𝑝 ∨∼ 𝑝 ≡ 𝑇
Double Negation ∼ ∼𝑝 ≡𝑝
Idempotent 𝑝∧𝑝≡𝑝
𝑝∨𝑝≡𝑝
De Morgan’s ∼ 𝑝 ∧ 𝑞 ≡∼ 𝑝 ∨∼ 𝑞
∼ 𝑝 ∨ 𝑞 ≡∼ 𝑝 ∧∼ 𝑞
Universal Bound 𝑝∧𝐹 ≡𝐹
𝑝∨𝑇 ≡𝑇
Absorption 𝑝∧ 𝑝∨𝑞 ≡𝑝
𝑝∨ 𝑝∧𝑞 ≡𝑝
ADDITIONAL LOGICAL EQUIVALENCES
LAWS LOGICAL EQUIVALENCE
Exportation Law 𝑝 ∧ 𝑞 → 𝑟 ≡ 𝑝 → (𝑞 → 𝑟)
Contrapositive 𝑝 → 𝑞 ≡∼ 𝑞 →∼ 𝑝
Reductio Ad Absurdum 𝑝 → 𝑞 ≡ 𝑝 ∧∼ 𝑞 → 𝐹
Equivalence 𝑝 ↔ 𝑞 ≡ 𝑝 → 𝑞 ∧ (𝑞 → 𝑝)
𝑝 ↔ 𝑞 ≡ ∼ 𝑝 ∨ 𝑞 ∧ (𝑝 ∨∼ 𝑞)
Implication 𝑝 → 𝑞 ≡∼ 𝑝 ∨ 𝑞
EXAMPLE: Show that the following compound
statements are true using the laws of equivalences
1. 𝑝∨ ∼𝑝∧𝑞 ∨ 𝑝 ∨∼ 𝑞 ≡ 𝑇
2. 𝑞 ∨ ∼ 𝑝 ∧ 𝑞 ∨ 𝑝 ∨∼ 𝑞 ∧∼ 𝑞 ≡∼ 𝑞
VARIATIONS OF CONDITIONAL STATEMENT
NAME STATEMENT

CONDITIONAL 𝑝→𝑞

CONVERSE 𝑞→𝑝

INVERS ∼ 𝑝 →∼ 𝑞

CONTRAPOSITIVE ∼ 𝑞 →∼ 𝑝
EXAMPLE:
• Given the conditional statement,“If 8|32 then 4|16. Determine the
converse, inverse, and contrapositive.
SWITCHING NETWORK
• It is a collection of wires and switches connecting two terminals,
𝑋 and 𝑌. A switch may be either open, 𝑂 or closed, 𝐶.
• An open switch will not permit the current to flow .
• A closed switch will permit current to flow
SINGLE WIRE, OPEN SWITCH, AND CLOSED
SWITCH

𝑋 𝑌
SINGLE WIRE
OPEN SWITCH 𝑝
𝑋 𝑝 𝑌

CLOSED SWITCH 𝑝
𝑋 𝑝 𝑌
SERIES SWITCH AND PARALLEL SWITCH

𝑝 𝑞 𝑌
SERIES SWITCH: 𝑝 ∧ 𝑞
𝑋

𝑝
𝑋 𝑌 PARALLEL SWITCH: 𝑝 ∨ 𝑞
𝑞
TRUTH TABLES OF SWITCHING NETWORK
𝒑 𝒒 𝒑∧𝒒 𝒑∨𝒒 𝒑 𝒒 Series Parallel
Circuit Circuit
T T T T C C C C
or
T F F T C O O C
F T F T O C O C
F F F F O O O O
SWITCHING NETWORK
• Two switches are complementary if one switch is open and the
other is closed, and vice versa.
• Two switches are said to be equivalent if they have the same
electrical properties concerning the flow and non-flow of current
EXAMPLE: Construct the switching network of
each of the following compound statements.
1. 𝑝∧𝑟 ∨ 𝑞∧𝑟 ∨∼ 𝑞
2. ∼ 𝑝 → 𝑞 ∨ (𝑝 ↔ 𝑞)