CSC305 Discrete Structures

Discrete Structures
Other conditional statement:

In discrete mathematics, a conditional statement has a few closely related forms.

If the original conditional is:

1. Converse

q→p

• Switch the hypothesis and conclusion.

• Not logically equivalent to the original.

Example:
If it is raining, then the ground is wet.
Converse: If the ground is wet, then it is raining. ❌ (not always true)

2. Inverse

¬p → ¬q

• Negate both parts.

• Not logically equivalent to the original.

Example:
If it is raining, then the ground is wet.
Inverse: If it is not raining, then the ground is not wet. ❌

3. Contrapositive

¬q → ¬p

• Negate both parts and switch them.

• Logically equivalent to the original (very important in proofs).

Example:
If it is raining, then the ground is wet.
Contrapositive: If the ground is not wet, then it is not raining. ✔

Key equivalence facts

• Conditional ⇔ Contrapositive

• Converse ⇔ Inverse

BSCS 3A and 3B 2026

CSC305 Discrete Structures

So they pair up like this:

Statement Equivalent to
p→q ¬q → ¬p
q→p ¬p → ¬q

Bonus: Biconditional

Sometimes you’ll also see:

p ↔ q (“p if and only if q”)

Which means:

• p → q AND q → p

Truth Table for Conditional Statements

Let the original statement be p → q.

p q p → q q → p (Converse) ¬p → ¬q (Inverse) ¬q → ¬p (Contrapositive)

TTT T T T
TFF T T F
F TT F F T
FFT T T T

Key observations

• p → q and ¬q → ¬p have identical truth values → ✔ logically equivalent

• q → p and ¬p → ¬q match each other → ✔ logically equivalent
• Converse & inverse are not equivalent to the original

Practice Time
Setup of propositions

• 𝑝 = “It is raining.”
• 𝑞 = “You carry an umbrella.”
• 𝑟 = “You get wet.”
BSCS 3A and 3B 2026
CSC305 Discrete Structures

Logical expressions and English translations

a) 𝑝 → 𝑞

b) ¬𝑞 ↔ 𝑟

c) 𝑞 → ¬𝑟

d) 𝑝 ∨ 𝑞 ∨ 𝑟

e) (𝑝 → ¬𝑟) ∨ (𝑞 → ¬𝑟)

f) (𝑝 ∧ 𝑞) ∨ (¬𝑞 ∧ 𝑟)

Part 2: Another example

New propositions

• 𝑝: You submit the project.

• 𝑞: You attend all lectures.
• 𝑟: You pass the course.

New questions (same style)

a) You pass the course, but you do not attend all lectures.

b) You submit the project, attend all lectures, and pass the course.

c) To pass the course, it is necessary to submit the project.

d) You submit the project, but you do not attend all lectures; nevertheless, you pass the
course.

e) Submitting the project and attending all lectures is sufficient for passing the course.

f) You pass the course if and only if you attend all lectures or submit the project.

BSCS 3A and 3B 2026

CSC305 Discrete Structures

Review:
1⃣ Predicate Logic Example

∀𝑥 (𝑆(𝑥) → ¬𝑆𝑜(𝑥))

• Domain: all fruits

• Predicates:
o 𝑆(𝑥) = “x is sweet”
o 𝑆𝑜(𝑥) = “x is sour”
• Meaning in English:

“For every fruit, if it is sweet, then it is not sour.”

• Why it’s predicate logic:

o Uses variables (𝑥) and quantifiers (∀)
o Applies to each individual element in the domain

Exam Question:

Express the following statement in propositional logic using a single proposition:

“If you study hard, then you will pass the exam.”

Solution:

• Let 𝑝 = “You study hard”

• Let 𝑞 = “You will pass the exam”
• Propositional logic expression:

𝑝→𝑞

Explanation:

• This is a conditional statement (compound proposition).

• We treat the whole sentence as one statement made of smaller propositions.

2⃣ Propositional Logic Example

(𝑝 → ¬𝑟) ∨ (𝑞 → ¬𝑟)

• Propositions:
BSCS 3A and 3B 2026
CSC305 Discrete Structures

o 𝑝 = “You have the flu”

o 𝑞 = “You miss the final exam”
o 𝑟 = “You pass the course”
• English reading:

“Either if you have the flu, you will not pass the course, or if you miss the final exam, you
will not pass the course.”

Exam Question:

Express the following statement in predicate logic using quantifiers:

“All students who study hard will pass the exam.”

Solution:

• Domain: all students

• Predicate:
o 𝑆(𝑥) = “x studies hard”
o 𝑃(𝑥) = “x passes the exam”
• Predicate logic expression:

∀𝑥 (𝑆(𝑥) → 𝑃(𝑥))

Explanation:

• This is more precise than propositional logic.

• It explicitly applies the conditional to every student individually.
• ∀𝑥 = “for every student x”

Example:

Logic type Expression What it emphasizes

Propositional 𝑝→𝑞 Treats the statement as one unit (true/false)
Predicate ∀𝑥 (𝑆(𝑥) → 𝑃(𝑥)) Applies the statement to each individual in the domain

• Why it’s propositional logic:

o Works with whole propositions (𝑝, 𝑞, 𝑟)
o Does not mention individual elements or variables
o Uses logical connectives (→, ∨, ¬) between propositions

✅ Key Difference

BSCS 3A and 3B 2026

CSC305 Discrete Structures

Feature Predicate Logic Propositional Logic

Symbols ∀, ∃, variables, predicates p, q, r (propositions)
Applies to elements
Scope Applies to entire propositions as a unit
individually
Example ∀x (S(x) → ¬So(x)) (p → ¬r) ∨ (q → ¬r)
“For every fruit, if it is sweet, “Either if you have the flu you don’t pass, or if
Reading
then it is not sour.” you miss the exam you don’t pass.”

Propositional Equivalences,
Law of Logic
1. Tautology (Always True)
Definition (intuition):
True no matter what happens.

Real-life example:

“Either it is raining, or it is not raining.”

Logical form:
p ∨¬p
Why it’s a tautology:
There is no possible situation where this statement is false. One of the two must be true.

2. Contradiction (Always False)

Definition (intuition):
Can never be true in any situation.

Real-life example:

“It is raining and it is not raining at the same time and place.”

Logical form:
p ∧¬p

BSCS 3A and 3B 2026

CSC305 Discrete Structures

Why it’s a contradiction:

A statement and its negation cannot both be true simultaneously.

3. Contingency (Sometimes True, Sometimes False)

Definition (intuition):
Truth depends on circumstances.

Real-life example:

“If I study, then I will pass the exam.”

Logical form:
P→Q

Why it’s a contingency:

• True in some cases (you study and pass)

• False in others (you study and fail)

It’s not guaranteed and not impossible—it depends on what actually happens.

Super-quick memory trick

• Tautology → “It must be true”
• Contradiction → “It can’t be true”
• Contingency → “It might be true”

Compound Proposition
Definition

A compound proposition is a statement formed by combining two or more simple

(atomic) propositions using logical connectives.

Simple vs Compound (quick contrast)

• Simple (atomic) proposition:

BSCS 3A and 3B 2026

CSC305 Discrete Structures

“It is raining.”
(Cannot be broken down further)

• Compound proposition:

“It is raining and it is cold.”

The Core Rule:

A proposition is compound if and only if it contains at least one logical

connective (¬, ∧, ∨, →, ↔).

Side-by-Side Comparison (this is the key)

Statement Type Why
“I study.” Simple No connective
“I do not study.” Compound Contains negation (¬)
“I study and I pass.” Compound Two propositions + ∧
“If I study, then I pass.” Compound Uses →

Two compound propositions p and q are equivalent if and only if the columns in a truth
table giving their truth values agree.

This truth table show ¬p ∨ q is equivalent to p → q.

Truth Tables For Compound Propositions

BSCS 3A and 3B 2026

CSC305 Discrete Structures

Exercise:
Construct a truth table for

• (p ∨ ¬q) →( p ^q)
• (p ∨ q) → ¬ r

BSCS 3A and 3B 2026