Free degree-level computing lessons for careful independent study.
Aplailasain by Static Carnival

Degree Level Programmes · Formal Computing Foundations · Lesson 28

Predicate Logic: Quantifiers, Domains and Translation

Use predicates and quantifiers to express claims about objects.

Back to coursePreviousNext lesson

Lesson overview

Use predicates and quantifiers to express claims about objects.

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

  • Define a domain of discourse.
  • Translate all and exists statements.
  • Explain how predicates extend propositional logic.

Learning outcomes

  • By the end of this lesson, you can define a domain of discourse.
  • By the end of this lesson, you can translate all and exists statements.
  • By the end of this lesson, you can explain how predicates extend propositional logic.

Key vocabulary

predicatedomainfor allthere exists

What this lesson is about

Predicate logic extends propositional logic by talking about objects. A predicate is a statement with variables, and a quantifier says whether it applies to all objects or at least one object.

The domain is essential. The same quantified sentence can become true or false when the domain changes.

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.

PredicateLogic term. A statement with variables whose truth depends on the objects substituted for those variables.
QuantifierLogic term. A symbol that states how many objects the claim concerns, such as 'for all' or 'there exists'.
Domain of discoursePhrase. The collection of objects over which the variables range.
WitnessProof term. A specific object that proves an existential claim.

Formal notation and definitions

∀x ∈ D, P(x) means P holds for every object in D.∃x ∈ D such that P(x) means at least one object in D satisfies P.Always state D before interpreting the quantifier.

How to read the symbols

∀x∈D\forall x\in DFor every object x in domain D.
∃x∈D\exists x\in DThere exists at least one object x in domain D.
P(x)P(x)A predicate: a statement whose truth depends on x.

Use the domain of discourse before reading the quantifier. Changing the domain changes what the sentence claims.

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

The claim 'every submitted file has an owner' needs a domain of files and a predicate that links each file to ownership.

Objects: the domain of files, the domain of users, file variable f, user variable u, and predicate Owns(u, f).

Model cue: Use a domain box containing objects. Universal quantification checks every object; existential quantification looks for at least one witness.

2. Mathematical working

∀f∈Files, ∃u∈Users Owns(u,f)\forall f\in Files,\ \exists u\in Users\ \mathrm{Owns}(u,f)∃f∈Files such that ∀u∈Users, ¬Owns(u,f)\exists f\in Files\ \text{such that}\ \forall u\in Users,\ \neg\mathrm{Owns}(u,f)
Plain text version
∀f ∈ Files, ∃u ∈ Users Owns(u, f)
For each submitted file f, find at least one user u who owns it.
A single unowned file is a counterexample.

3. How to read the working

  1. Read the domain restrictions first: f ranges over Files and u ranges over Users.
  2. Read ∀f as 'for each file'. For each chosen file, the statement must find at least one owning user.
  3. Read ∃u as a witness requirement: a particular owner must exist for the file under discussion.
  4. To disprove the claim, find one file for which no user satisfies Owns(u, f).

4. Computing meaning and check

The quantified model separates the objects being checked from the relationship being claimed. Changing the domain changes the truth of the statement.

Now check: Translate 'some user owns every file' and compare it with 'every file has some owner'.

Worked example

From scenario to formal reasoning

Scenario: The claim 'every submitted file has an owner' needs a domain of files and a predicate that links each file to ownership.

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

Reveal model answer

The claim 'every submitted file has an owner' becomes ∀f ∈ Files, ∃u ∈ Users such that Owns(u, f). The domain Files must contain only submitted files, otherwise the claim changes.

Worked solution structure

How a strong answer should be written

  1. Define: State the domain and the objects under discussion. For this lesson, begin from ∀x ∈ D, P(x) means P holds for every object in D.
  2. Apply: Use the relevant definition from predicate logic; do not rely on the diagram, wording or intuition alone.
  3. Check: Test a boundary case, counterexample candidate or representation limit.
  4. Conclude: Write one sentence that connects the formal result back to the computing scenario.

Common misconception

A common mistake is leaving the domain implicit. Quantified claims are unsafe unless we know what objects they range over.

Guided practice

  1. Translate 'every submitted file has an owner' using Files, Users and Owns(u, f).
  2. Translate 'some user owns every file' and compare it with 'every file has some owner'.
  3. State the domain of each variable before interpreting the formula.
  4. Give a single unowned file as a counterexample to the universal ownership claim.

Quick checks

1. 'Every file has some owner' is best written as:

2. Why must the domain be stated?

Digital exam practice

Example exam task

Using domains Files and Users and predicate Owns(u,f), translate 'every submitted file has an owner' and 'some user owns every file'. Compare the claims and state a counterexample for the first.

Notation toolkit

∀x∈D\forall x\in D

Means: for every object x in domain D

How to use: Use it for all-objects claims.

∃x∈D\exists x\in D

Means: there exists at least one object x in D

How to use: Use it when a witness must be found.

Owns⁡(u,f)\operatorname{Owns}(u,f)

Means: a predicate relating user u to file f

How to use: Use it to express a property involving named variables.

What a good answer is expected to show

A strong answer for this lesson defines the domain of files, the domain of users, file variable f, user variable u, and predicate Owns(u, f), applies the predicate logic method with visible working, and finishes by interpreting the result in the computing scenario.

How to solve it

  1. Read the domain restrictions first: f ranges over Files and u ranges over Users.
  2. Read ∀f as 'for each file'. For each chosen file, the statement must find at least one owning user.
  3. Read ∃u as a witness requirement: a particular owner must exist for the file under discussion.
  4. To disprove the claim, find one file for which no user satisfies Owns(u, f).

Model answer

Reveal model answer
∀f∈Files, ∃u∈Users Owns⁡(u,f)\forall f\in Files,\ \exists u\in Users\ \operatorname{Owns}(u,f)∃u∈Users, ∀f∈Files Owns⁡(u,f)\exists u\in Users,\ \forall f\in Files\ \operatorname{Owns}(u,f)∃f0∈Files such that ∀u∈Users, ¬Owns⁡(u,f0)\exists f_0\in Files\ \text{such that}\ \forall u\in Users,\ \neg\operatorname{Owns}(u,f_0)

'Every submitted file has an owner' is ∀f ∈ Files, ∃u ∈ Users Owns(u,f). 'Some user owns every file' is ∃u ∈ Users, ∀f ∈ Files Owns(u,f). The second claim is stronger because the same user must own all files. A single file f0 with no owning user disproves the first claim.

Practise next

  1. Translate 'every submitted file has an owner' using Files, Users and Owns(u, f).
  2. Translate 'some user owns every file' and compare it with 'every file has some owner'.

Self-marking criteria

  • States both domains.
  • Uses ∀f∃u Owns(u,f) for every file has some owner.
  • Uses ∃u∀f Owns(u,f) for one user owns every file.
  • Explains the order difference.
  • Gives an unowned file as a 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: Reasoning with Predicates, Negation and Nested Quantifiers.