Fundamentals of Computing: Reasoning with Predicates, Negation and Nested Quantifiers

Lesson overview

Handle more complex quantified statements.

CourseFundamentals of Computing

Topic strandPredicate logic

Assessment styleDigital exam practice

EvidenceWorked answer plus justification

Starter: make the model explicit

Before reading the worked example, write down the objects involved, the claim being made and the notation you expect to use. This prevents the common error of calculating before modelling.

Learning objectives

Negate quantified statements correctly.
Interpret nested quantifiers in order.
Find counterexamples for quantified claims.

Learning outcomes

By the end of this lesson, you can negate quantified statements correctly.
By the end of this lesson, you can interpret nested quantifiers in order.
By the end of this lesson, you can find counterexamples for quantified claims.

Key vocabulary

What this lesson is about

Nested quantifiers place quantifiers inside one another, so order matters. 'For every user there exists a file' is different from 'there exists a file for every user'.

Negating quantified claims also changes the quantifier. The negation of every is some not; the negation of exists is none.

Terms, acronyms and named methods

These are the phrases and named techniques used in this lesson. Read this section before the worked example so the notation and examples have a clear meaning.

Nested quantifiersLogic phrase. Two or more quantifiers used together. Their order matters because later choices can depend on earlier variables.

ScopeLogic term. The part of a formula controlled by a quantifier or negation.

Negating quantifiersNamed technique. Changing 'for all' to 'there exists not', or 'there exists' to 'for all not', while moving negation through a quantified statement.

CounterexampleProof term. An object or case that makes a universal quantified claim false.

Formal notation and definitions

\neg\forallx P(x) \equiv \existsx \negP(x). \neg\existsx P(x) \equiv \forallx \negP(x). \forallx\existsy R(x,y) is not equivalent to \existsy\forallx R(x,y).

How to read the symbols

$\forall x\exists y$ For each x, there may be a different y.

$\exists y\forall x$ There is one y that works for every x.

$\neg\forall x P(x)\equiv\exists x\neg P(x)$ To negate 'all', find at least one counterexample.

Use quantifier order carefully. For every x there exists a y does not mean there is one y that works for every x.

Degree-level reasoning

Predicate logic is where formal computing starts to express requirements with variables. The order of quantifiers changes the claim, sometimes drastically.

Good answers translate both ways: from English to symbols and from symbols back to precise English.

Do not stop at a correct-looking answer. State why the method is valid, whether the result depends on a hidden assumption, and what would count as a counterexample.

Worked formal model

This section shows the model, notation, calculation and interpretation as one worked answer. The notation is part of the reasoning, not decoration.

1. Context and objects

Negating 'every user has a role' gives 'there exists a user with no role', not 'every user has no role'.

Objects: the user variable u, role variable r, the Assigned relation, and the witness or counterexample required.

Model cue: Use two stacked quantifier diagrams. In ∀x∃y, each x may have its own y. In ∃y∀x, one y must work for all x.

2. Mathematical working

\neg\forall u\in Users,\ \exists r\in Roles\ Assigned(u,r)

\exists u\in Users\ \text{such that}\ \forall r\in Roles,\ \neg Assigned(u,r)

Plain text version

¬∀x P(x) ≡ ∃x ¬P(x).
¬∃x P(x) ≡ ∀x ¬P(x).
∀x∃y R(x,y) is not equivalent to ∃y∀x R(x,y).

Worked use: Negating 'every user has a role' gives 'there exists a user with no role'. It does not mean 'every user has no role'. The quantifier changes from universal to existential.

3. How to read the working

Read the outer negation as applying to the whole quantified claim, not just to the Assigned predicate.
Push the negation through ∀ by changing it to ∃, then through ∃ by changing it to ∀.
The result says there is a particular user u with no assigned role r at all.
Translate the witness carefully: one unassigned user disproves 'every user has some role'.

4. Computing meaning and check

The order and negation of quantifiers decide what evidence is needed. One missing role is enough to disprove 'every user has a role'.

Now check: Negate ∀u ∈ Users, ∃r ∈ Roles Assigned(u, r), and explain the result in plain English.

Worked example

From scenario to formal reasoning

Scenario: Negating 'every user has a role' gives 'there exists a user with no role', not 'every user has no role'.

Method: Use the definitions and notation introduced above, then state what the result means in this computing scenario.

Reveal model answer

Negating 'every user has a role' gives 'there exists a user with no role'. It does not mean 'every user has no role'. The quantifier changes from universal to existential.

Worked solution structure

How a strong answer should be written

Define: State the domain and the objects under discussion. For this lesson, begin from ¬∀x P(x) ≡ ∃x ¬P(x).
Apply: Use the relevant definition from predicate logic; do not rely on the diagram, wording or intuition alone.
Check: Test a boundary case, counterexample candidate or representation limit.
Conclude: Write one sentence that connects the formal result back to the computing scenario.

Common misconception

A common mistake is swapping quantifiers casually. 'Every user has some file' and 'some file belongs to every user' are very different.

Guided practice

Negate ∀u ∈ Users, ∃r ∈ Roles Assigned(u, r).
Translate the negated statement into plain English.
Compare ∀u∃r Assigned(u,r) with ∃r∀u Assigned(u,r).
Give a small user-role example where the first statement is true and the second is false.

Quick checks

1. The negation of ∀u ∃r Assigned(u,r) is:

∃u ∀r ¬Assigned(u,r)∃r ∀u Assigned(u,r)∀u ∀r Assigned(u,r)

2. What is the difference between ∀u∃r and ∃r∀u?

The second has no variables.They are always equivalent.The first may choose a different r for each u; the second requires one r for all u.

Digital exam practice

Example exam task

Negate ∀u ∈ Users, ∃r ∈ Roles Assigned(u,r), translate it into English, and compare ∀u∃r with ∃r∀u using a small example.

Notation toolkit

\forall u\ \exists r

Means: for each user, at least one role may depend on that user

How to use: Use it when the witness can vary with the outer variable.

\exists u\ \forall r

Means: one user works for every role in the statement

How to use: Use it when a single witness must cover all cases.

\neg\forall x\ P(x)\equiv\exists x\ \neg P(x)

Means: negating a universal claim gives an existential counterexample

How to use: Use it when disproving an all-objects statement.

What a good answer is expected to show

A strong answer for this lesson defines the user variable u, role variable r, the Assigned relation, and the witness or counterexample required, applies the predicate logic method with visible working, and finishes by interpreting the result in the computing scenario.

How to solve it

Read the outer negation as applying to the whole quantified claim, not just to the Assigned predicate.
Push the negation through ∀ by changing it to ∃, then through ∃ by changing it to ∀.
The result says there is a particular user u with no assigned role r at all.
Translate the witness carefully: one unassigned user disproves 'every user has some role'.

Model answer

Reveal model answer

\neg\forall u\in Users\ \exists r\in Roles\ \operatorname{Assigned}(u,r)

\equiv\exists u\in Users\ \forall r\in Roles\ \neg\operatorname{Assigned}(u,r)

\forall u\exists r\ \operatorname{Assigned}(u,r)\not\equiv\exists r\forall u\ \operatorname{Assigned}(u,r)

Negating ∀u ∈ Users, ∃r ∈ Roles Assigned(u,r) gives ∃u ∈ Users such that ∀r ∈ Roles, ¬Assigned(u,r). In plain English, at least one user has no assigned role at all. The order matters: every user having some role does not mean one role is assigned to every user.

Practise next

Negate ∀u ∈ Users, ∃r ∈ Roles Assigned(u, r).
Translate the negated statement into plain English.

Self-marking criteria

Changes ∀ to ∃ and ∃ to ∀ under negation.
Places the negation on Assigned(u,r).
Translates the result as one user with no role.
Explains why quantifier order matters.
Provides a small example or counterexample.

Extension

Change one assumption in the worked scenario and decide whether the same method still applies. If it does not, name the exact point where the reasoning breaks.

Study route

Save one clean worked answer from this lesson. Include the problem statement, notation, working, final answer and a short note explaining the computing meaning of the result.

Next lesson: Whole-Course Consolidation and Final Digital Exam Practice.