The University of Hong Kong · FACULTY OF COMPUTER SCIENCE

COMP2121 Chap.1 Propositional Logic, Predicates and Quantifiers

- one subject, every graph, every model, every mark
6 Chapters5-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 1 of 11 · COMP2121

Propositional Logic, Predicates and Quantifiers

Statements, operators and truth

The chapter starts with propositions, statements that are true or false but not both, and the six operators that combine them. Implication is the operator to master: it is false only when a true hypothesis meets a false conclusion.

Logical equivalence is proved either with a complete truth table or by rewriting with named laws such as De Morgan and the implication law.

From predicates to quantified claims

Predicates become propositions once their variables are assigned or quantified over a stated domain.

The universal quantifier pairs with an implication and the existential with a conjunction, and negation moves through a quantifier by switching its kind.

Where marks go in logic questions

The course solutions establish an equivalence in one of two accepted ways: a complete truth table with every column shown, or a chain of rewrites in which each line names the law it uses.

Both earn full credit when complete; a table with a missing row or a chain that skips a law does not. Translations are judged on the declared domain and on the connective under each quantifier, so state the domain in words before writing any symbols.

Nested quantifiers and order

Swapping the order of two different quantifiers usually changes the meaning.

For every x there exists y with x plus y equal to zero is true over the integers, because y can depend on x, while there exists y such that for every x the sum is zero is false, because a single y would have to work for all x at once.

Reading each nested statement as a game, in which the existential player answers the universal player's choice, makes the difference concrete and gives a quick way to test a claimed truth value.

In this chapter

What this chapter covers

  • 01

    Propositions and truth tables

  • 02

    Implication and the biconditional

  • 03

    Equivalence laws

  • 04

    Predicates and domains

  • 05

    Quantifier negation

  • 06

    Translating English into logic

Worked example · free

Read an implication cell by cell

Q [6 marks]. This practice weighting was set for revision and is not an official University marking scheme. Give the truth table of (p and not q) implies r, and state the only assignments that make it false.
The implication p → q is false in exactly one cell.The implication p → q is false in exactly one cell. Rows give the truth value of the hypothesis p and columns give the conclusion q; only a true hypothesis paired with a false conclusion breaks the promise, so both cells with p false are true.q trueq falsep truep falseTFTTonly false row
The implication p → q is false in exactly one cell. Rows give the truth value of the hypothesis p and columns give the conclusion q; only a true hypothesis paired with a false conclusion breaks the promise, so both cells with p false are true.
  • 2List all eight assignments of p, q and r.
  • 2Evaluate the hypothesis p and not q in each row.
  • 2Mark the rows where the hypothesis is true and r is false.
The hypothesis holds only in rows with p true and q false, and there are two such rows. The implication fails in exactly one of them, where r is also false, so the single falsifying assignment is p true, q false, r false. Every other row is true, six of them because the hypothesis is false and one because the conclusion holds.
Sia tip — An implication with a false hypothesis is true; do not mark those rows false.
Glossary

Key terms

Proposition
A statement that is either true or false, but not both.
Logical equivalence
A relation between two formulas whose biconditional is true under every assignment.
Universe of discourse
The domain of values a quantified variable may take.
FAQ

Propositional Logic, Predicates and Quantifiers FAQ

When is an implication true?

It is false in one case only: the hypothesis holds and the conclusion fails. With a false hypothesis the implication counts as true, which is called vacuous truth, and this is a common source of lost marks.

How do I negate a quantified statement?

Switch the quantifier from universal to existential or the reverse, then negate the body. A negated implication becomes the hypothesis together with the negated conclusion, and strict inequalities become non-strict ones.

Why does a universal use an implication?

A restricted universal claim says that anything meeting the condition has the property. Writing a conjunction instead would claim that everything in the domain meets the condition, which is a different and usually false statement.

Does the order of quantifiers matter?

Swapping two quantifiers of one kind never changes the meaning, but a universal and an existential cannot. When the existential comes second, its witness may depend on the earlier variable; when it comes first, one witness must serve every value, which is a much stronger claim.

What does a tautology look like in a truth table?

Its final column is true in every row, whatever the truth values of the variables. A contradiction is false in every row, and a contingency is neither. Two formulas are logically equivalent exactly when their biconditional is a tautology, which links the table method to the definition directly.

Study strategy

Exam move

Write each equivalence law with a one-line use beside it, then practise reducing both sides of a claimed equivalence to one common form. For translations, state the domain first, choose the hidden connective under each quantifier, and test your formula on one small scenario where the English sentence is false. Keep a list of tricky words such as unless, whenever and but not both.

Finish each session by negating two nested statements fully, pushing the negation all the way to the predicates, and checking the result on a small domain. Before the quizzes, time yourself translating five sentences, and check each translation by constructing a case where the English is false.

Working through Propositional Logic, Predicates and Quantifiers in COMP2121? Sia is AskSia’s AI Computer Science tutor — ask any COMP2121 Propositional Logic, Predicates and Quantifiers question and get a clear, step-by-step explanation grounded in how COMP2121 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.

A+Everything unlocked
Unlocks this Bible + all 52 of your subjects at The University of Hong Kong, plus 1,000+ more Bibles across the AskSia library.
Sia - your COMP2121 tutor, unlimited, worked the way the exam marks it
The full 5-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works