COMP2121 Chap.1 Propositional Logic, Predicates and Quantifiers
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.
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
- 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.
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.
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.
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.