Binalonan, Pangasinan

College of Information Technology

1st Semester A.Y 2025 - 2026

MODULE 2
PREDICATE LOGIC
Course Title: Discrete Mathematics
Course Code: MS 101
No of Units: 3
I. Module Objectives
At the end of the course, the student should be able to:
 Translate natural language statements into propositional and predicate logic
 Identify and correctly use universal and existential quantifiers and their negations.
 Apply rules of inference to form valid arguments.

II. Lecture and Discussions

1. Introduction
Predicate logic, also known as first-order logic, is an extension of propositional logic that allows us to
express statements involving variables and predicates. It enables us to make more detailed and precise
statements about objects, their properties, and their relationships.
Whereas propositional logic treats entire statements as indivisible, predicate logic analyzes statements
into subjects and predicates with quantifiers.
2. Predicates

A predicate is a property or condition that a subject (variable) can satisfy. A predicate is a function that
returns a truth value when applied to an object.

 Denoted as P(x), Q(x, y), etc., where x, y are variables.

 A predicate becomes a proposition when its variables are assigned specific values.

Example 1:

Let P(x): “x is an IT student.”

P(Maria) → True if Maria is an IT student.
P(Juan) → False if Juan is not an IT student.
Example 2:
Let P(x): “x is an even number.”
If x = 4, P(4) is true.
If x = 5, P(5) is false.
Example 3:
Let C(x): “x is a computer in the laboratory.”
Let N(x): “x is connected to the network.”
C(PC1) is true if PC1 is indeed a computer in the lab.

2. Quantifiers

Universal Quantifier (∀)

Prepared by:
PRINCESS JOANNA M. LABARO
Instructor
 Binalonan, Pangasinan
 Symbol: ∀
 Meaning: “for all” or “for every”
 Used to state that a predicate holds for all elements in the domain.
 Example: ∀x (x > 0 → x² > 0)
“For every x greater than 0, x squared is greater than 0.”
 “For every x, if x is a computer in the lab, then x is connected to the network.”

Existential Quantifier (∃)

 Symbol: ∃
 Meaning: “there exists” or “for some”
 Used to state that a predicate holds for at least one element in the domain.
 Example: ∃x (x² = 4)
“There exists an x such that x squared equals 4.
 “There exists at least one student who is also a database administrator.”

3. Negating Quantifiers

Negations switch the quantifier type:

 ¬(∀x P(x)) ≡ ∃x ¬P(x)

“Not all x satisfy P(x)”→ There exists at least one x that does not satisfy P(x).
 ¬(∃x P(x)) ≡ ∀x ¬P(x)
“There is no x that satisfies P(x)” → All x do not satisfy P(x).

Example 1:
Statement: “All students in this class own a laptop.”
Negation: “There exists at least one student in this class who does not own a laptop.”

Example 2:
Statement: “All employees in this company have an ID card.”
Negation: “There exists at least one employee in this company who does not have an ID card.”
Explanation:
Original: ∀x P(x) → “Every employee has an ID card.”
Negation: ∃x ¬P(x) → “At least one employee does not have an ID card.”

Example 3:
Statement: “There is at least one cat in the neighborhood that is black.”
Negation: “All cats in the neighborhood are not black.”
Explanation:
Original: ∃x P(x) → “Some cat is black.”
Negation: ∀x ¬P(x) → “No cat is black.”

4. Translating Natural Language to Predicate Logic

Example 1:
“All IT students know programming.”
Let P(x): “x is an IT student”
Let Q(x): “x knows programming”
Translation: ∀x (P(x) → Q(x))

Example 2:
“Some programmers work remotely.”
Let R(x): “x is a programmer”
Let W(x): “x works remotely”
Prepared by:
PRINCESS JOANNA M. LABARO
Instructor
 Binalonan, Pangasinan
Translation: ∃x (R(x) ∧ W(x))
Why if–then?
Because the meaning is: If a person is an IT student, then that person knows programming.
The condition is being an IT student (P(x)).
The consequence is knowing programming (Q(x)).

Example 3:
“No viruses are beneficial.”
Let V(x): “x is a virus”
Let B(x): “x is beneficial”
Translation: ∀x (V(x) → ¬B(x))

Why and?
Because we are describing the same person with two properties:
That person is a programmer (R(x)).
That person works remotely (W(x)).
Both must be true together for that person. That’s why we use ∧ (and) instead of →.
If we wrote ∃x(R(x)→W(x)), it would be wrong, because implication would also be true for people who are not
programmers (since R(x) would be false, the implication holds automatically). But we specifically want a
programmer who also works remotely, so we use ∧.

5. Rules of Inference

Rules of inference are logical patterns that allow us to draw valid conclusions from premises.

Common Rules:

1. Modus Ponens (Law of Detachment)

 p → q, p is true ⟹ q is true.
 Example: If a computer has malware, it will slow down. The computer has malware ⟹
It will slow down.

Example (IT context):

If a computer has malware, then it will slow down. (p→q)

The computer has malware. (p)

Therefore, the computer will slow down. (q) ✅

Why? Because when the condition p is satisfied, the consequence q must also follow.

2. Modus Tollens

 p → q, ¬q is true ⟹ ¬p is true.
 Example: If the network is down, emails cannot be sent. Emails were sent ⟹ The
network was not down.

Example (IT context):

If the network is down, then emails cannot be sent. (p→q)

Prepared by:
PRINCESS JOANNA M. LABARO
Instructor
 Binalonan, Pangasinan
Emails were sent. (¬q)

Therefore, the network was not down. (¬p) ✅

Why? Because if the consequence doesn’t happen (¬q), then the condition (p) could not have
been true in the first place.

3. Hypothetical Syllogism

 p → q, q → r ⟹ p → r.

Example:

If a student studies hard, then they pass the exam. (p→q)

If a student passes the exam, then they graduate. (q→r)

Therefore, if a student studies hard, then they graduate. (p→r)

4. Disjunctive Syllogism

 p ∨ q, ¬p ⟹ q.

Example:

Either the printer is out of ink or the printer is jammed. (p∨q)

The printer is not out of ink. (¬p)

Therefore, the printer is jammed. (q)

6. Applications in IT

 Database Query Languages: SQL WHERE clauses often represent predicate logic.
 Artificial Intelligence: Knowledge bases and reasoning engines use predicate logic to make
decisions.
 Software Testing: Formal verification uses predicate logic to confirm program correctness.

III. Application / Activity

Activity 1: IT Scenario Translation

Instructions: Translate the following into predicate logic. Use proper predicates and quantifiers.

1. Every database has at least one table.

D(x): “x is a database”
T(y): “y is a table”
Translation: ∀x (D(x) → ∃y T(y))

2. Some programmers use Linux.

Let P(x): “x is a programmer”

Prepared by:
PRINCESS JOANNA M. LABARO
Instructor
 Binalonan, Pangasinan
Let L(x): “x uses Linux”
Translation: ∃x (P(x) ∧ L(x))

3. There is a server that is offline.

Let S(x): “x is a server”

Let O(x): “x is offline”
Translation: ∃x (S(x) ∧ O(x))

4. All IP addresses in this network are unique.

5. There exists a student who does not like coding.

Let S(x): “x is a student”

Let C(x): “x likes coding”
Translation: ∃x (S(x) ∧ ¬C(x))

Activity 2: Negations
Instructions: For each statement below, write its predicate logic form, then write its negation in correct logical
form.

6. All printers are wireless.

Let P(x): “x is a printer”

Let W(x): “x is wireless”
Form: ∀x (P(x) → W(x))
Negation: ∃x (P(x) ∧ ¬W(x))

7. Some routers are faulty.

Let R(x): “x is a router”

Let F(x): “x is faulty”
Form: ∃x (R(x) ∧ F(x))
Negation: ∀x (R(x) → ¬F(x))

8. Every file in the system is backed up.

Let F(x): “x is a file”

Let S(x): “x is in the system”
Let B(x): “x is backed up”
Form: ∀x ((F(x) ∧ S(x)) → B(x))
Negation: ∃x ((F(x) ∧ S(x)) ∧ ¬B(x))
Activity 3: Rules of Inference
Instruction: Identify which rule of inference is used in given arguments.
Given:

9. If a device is connected to the internet, it can be hacked.

Let C(x): “x is connected to the internet”

Let H(x): “x can be hacked”
Form: ∀x (C(x) → H(x))

10. Device A is connected to the internet.

Question: Can we conclude Device A can be hacked? Which rule of inference applies?
Prepared by:
PRINCESS JOANNA M. LABARO
Instructor
 Binalonan, Pangasinan
Conclusion: H(A) — Device A can be hacked.
Rule of Inference Used: Modus Ponens (from p→q and p, infer q).

IV. Other References

 Epp, S. S. (2022). Discrete Mathematics with Applications (6th ed.). Cengage Learning.
 Rosen, K. H. (2023). Discrete Mathematics and Its Applications (9th ed.). McGraw-Hill Education.

V. Conclusion / Summary

Predicate logic extends propositional logic by introducing variables, predicates, and quantifiers, allowing
more detailed representation of knowledge. It is essential in computing for structuring database queries,
reasoning in AI, and ensuring software correctness. Mastering these concepts strengthens analytical thinking
and problem-solving skills for IT professionals.

Prepared By:
PRINCESS JOANNA M. LABARO, LPT
Faculty, College of Information Technology

Noted By:
FREDERICK J. SORIANO, MIT
Dean, College of Information Technology

Approved By:
GLORIA CATUNGAL-NEMEDEZ, PHD
Vice-President for Academic Affairs and Internalization

Prepared by:
PRINCESS JOANNA M. LABARO
Instructor