• Logic “the science or study of how to evaluate arguments or reason”

• Logical reasoning used in Mathematics to prove theorems

 Logic
• Crucial for mathematical reasoning
• Used for designing electronic circuitry

• Logic is a system based on propositions.

• A proposition is a statement that is either true or
false (not both).
• We say that the truth value of a proposition is either
true (T) or false (F).

• Corresponds to 1 and 0 in digital circuits

3
• Proposition or statement is a Logical connectives:
declarative sentence that is • and
either true or false but not both
• or
• Propositional variable used to
represent a proposition, p, q, r • if then
• Logical connectives are used to • not
combine simple propositions to • if and only if
form compound propositions • exclusive-or
Propositional Logic:
Propositions and Operators
• What are “Simple Propositions”?
• Statements which cannot be broken down without a loss in meaning.
• E.g. “John and Leah is a couple” cannot be broken down without a change in
meaning of the statement. Note what happens if we break it down to “John is
a couple” and “Leah is a couple”
Propositional Logic
• But “Juanita and Juanito are diligent students” is not a simple sentence
because it can be broken down without a change in meaning. “Juanita is a
diligent student.” “Juanito is a diligent student.”
• This is an example of a “Compound Proposition.”
• How do we represent (simple) propositions in propositional logic?
• Conventionally, capital letters (usually towards the beginning of the alphabet)
may be used as abbreviations for propositions.
The Operators
Connective Symbol Formal Name
Not ~ Negation
And ^ Conjunction

Or v Disjunction

→ Conditional /
If… then…
Implication

… if and
only if… ↔ Biconditional
• Truth Table displays the relationship between all possible truth values
of the component propositions
Truth Table of Conjunction •
Given any two statements, p and q

p q p^q
T T T

T F F

F T F

F F F

A conjunction is true if and only if both conjuncts are true

Truth Table for Negation
Where p is any statement, its negation is ~p

p ~p

T F

F T
Disjunction Truth Table
p q pvq
T T T
T F T
F T T
F F F

A (weak) disjunction is false only in the case that both its disjuncts are false
If…then Truth Table
p q pq
T T T
T F F
F T T
F F T

A (weak) disjunction is false only in the case that both its disjuncts are false
If and only if.. Truth Table
p q p  q
T T T
T F F
F T F
F F T

A (weak) disjunction is false only in the case that both its disjuncts are false
• A Contradiction is a compound
proposition that is false for all
possible truth values of its • A Tautology is a compound
component propositions proposition that is true for all
possible truth values of its
P ~P p˄ ~ p component propositions.
T F F
F T F
(~P V Q)  (P  Q)

P Q ~P ~ P v Q P→Q (~P V Q)↔ (P→ Q)

T T F T T T
T F F F F T
F T T T T T
F F T T T T
 Rules of Inference
•Rules of inference provide the justification of the steps
used in a proof.

•One important rule is called modus ponens or the law of

detachment. It is based on the tautology
(p(pq))  q. We write it in the following way:

•p
•p  q The two hypotheses p and p  q are
•____
• q written in a column, and the conclusion
below a bar, where  means “therefore”.

Fall 2002 CMSC 203 - Discrete Structures 15

 Rules of Inference

•The general form of a rule of inference is:

• p1
• p2 The rule states that if p1 and p2 and …
• . and pn are all true, then q is true as well.
• .
• .
• pn These rules of inference can be used in
•____
• q any mathematical argument and do not
require any proof.

Fall 2002 CMSC 203 - Discrete Structures 16

Rules of Inference

Modus
Addition
tollens

Simplification Hypothetical
syllogism

Conjunction Disjunctive
syllogism
 Arguments

•Just like a rule of inference, an argument consists of one

or more hypotheses and a conclusion.

•We say that an argument is valid, if whenever all its

hypotheses are true, its conclusion is also true.

•However, if any hypothesis is false, even a valid argument

can lead to an incorrect conclusion.
 Arguments
•Example:
•“If 101 is divisible by 3, then 1012 is divisible by 9. 101 is
divisible by 3. Consequently, 1012 is divisible by 9.”

•Although the argument is valid, its conclusion is

incorrect, because one of the hypotheses is false (“101 is
divisible by 3.”).

•If in the above argument we replace 101 with 102, we

could correctly conclude that 1022 is divisible by 9.

Fall 2002 CMSC 203 - Discrete Structures 19

 Arguments
•Which rule of inference was used in the last argument?

•p: “101 is divisible by 3.”

•q: “1012 is divisible by 9.”

Modus
ponens

Unfortunately, one of the hypotheses (p) is false.

Therefore, the conclusion q is incorrect.

Fall 2002 CMSC 203 - Discrete Structures 20

 Arguments

•Another example:
•“If it rains today, then we will not have a barbeque today.
If we do not have a barbeque today, then we will have a
barbeque tomorrow.
Therefore, if it rains today, then we will have a barbeque
tomorrow.”

•This is a valid argument: If its hypotheses are true, then

its conclusion is also true.

Fall 2002 CMSC 203 - Discrete Structures 21

 Arguments
•Let us formalize the previous argument:
•p: “It is raining today.”
•q: “We will not have a barbecue today.”
•r: “We will have a barbecue tomorrow.”
•So the argument is of the following form:

Hypothetical
syllogism

Fall 2002 CMSC 203 - Discrete Structures 22