Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Translating English into logic

How to convert ordinary English sentences into precise propositional and predicate-logic formulas, with rules, common patterns, worked translations and how to negate quantified statements.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Translating English into logic gives precise, unambiguous statements that a program, proof or specification can use. Engineers use this when writing formal requirements, specifying program pre/post-conditions, designing digital circuits (via Boolean logic) and proving correctness of algorithms.

Key ideas

  • Domain (universe): the set of objects the variables range over. Always state it when translating (e.g. "domain: natural numbers", "domain: students").
  • Atomic formula: a predicate applied to terms (e.g., P(a), Likes(Alice, x)).
  • Well-formed formula (wff): an atomic formula or a formula built from atomic formulas using logical connectives and quantifiers according to grammar rules.

Connectives (define before use):

  • Negation (¬): unary connective meaning "not". If P is a proposition, ¬P is true exactly when P is false.
  • Conjunction (∧): binary, means "and". P ∧ Q true when both P and Q true.
  • Disjunction (∨): binary, means "or" (inclusive). P ∨ Q true when at least one of P or Q true.
  • Exclusive or (⊕): binary, means exactly one of P or Q true. Often expressed as (P ∨ Q) ∧ ¬(P ∧ Q).
  • Implication (→): binary, P → Q reads "if P then Q" and is equivalent to ¬P ∨ Q. Be careful: P → Q is true when P is false, even if Q false.
  • Biconditional (↔): binary, P ↔ Q means both directions P → Q and Q → P hold; true when P and Q have same truth value. Assume standard precedence: ¬ > ∧ > ∨ > → > ↔; use parentheses to avoid ambiguity.

Quantifiers (define before use):

  • Universal quantifier (∀x): "for every x in the domain". Formula ∀x P(x) means P(x) is true for all x.
  • Existential quantifier (∃x): "there exists an x in the domain". ∃x P(x) means some x makes P(x) true.
  • Uniqueness quantifier (∃!x): "there exists exactly one x". Defined by: ∃!x P(x) ⇔ ∃x (P(x) ∧ ∀y (P(y) → y = x)).

Rules and important equivalences (state exactly like an answer):

  • De Morgan's laws for propositional logic:
    • ¬(P ∧ Q) ≡ (¬P) ∨ (¬Q)
    • ¬(P ∨ Q) ≡ (¬P) ∧ (¬Q) Assumption: P and Q are propositions.
  • Implication equivalence:
    • P → Q ≡ ¬P ∨ Q Derivation method commonly asked: truth table with four rows for P,Q; show columns for P → Q and ¬P ∨ Q identical.
  • Contraposition:
    • (P → Q) ≡ (¬Q → ¬P) Assumption: classical logic (law of excluded middle holds).
  • Negating quantifiers (quantifier duality):
    • ¬(∀x P(x)) ≡ ∃x ¬P(x)
    • ¬(∃x P(x)) ≡ ∀x ¬P(x) Assumption: domain non-empty is not required for these equivalences; they are semantic.

Translation patterns (common English → logic):

  • "If A then B" → A → B.
  • "A only if B" → A → B (note: "only if" places B as necessary condition for A). Also, "A if B" → B → A.
  • "If and only if" / "iff" → A ↔ B.
  • "Unless A, B" → A ∨ B (equivalently ¬A → B). Typical exam translation: "Unless it rains, we will go" → Rain ∨ Go or ¬Rain → Go (choose the form that makes subsequent proof easiest).
  • "Either A or B" (exclusive) → (A ∨ B) ∧ ¬(A ∧ B). If inclusive use A ∨ B.
  • "All/Every" → ∀x (condition → predicate) or ∀x (predicate) depending on phrasing; always state domain.
  • "Some/There exists" → ∃x (predicate).
  • "No" → ∀x ¬P(x) or equivalently ¬∃x P(x).
  • "Exactly one" → ∃!x P(x) using the definition above.

Ambiguity and scope: always specify quantifier order and scope. Example difference:

  • ∀x ∃y R(x,y) means "for each x there exists y" (y may depend on x).
  • ∃y ∀x R(x,y) means "there exists a single y that works for every x". Draw two boxes and arrows when explaining: label box 1 as "choose x first" then arrow to box 2 "choose y possibly depending on x"; reverse for the other order.

What to draw in an exam where asked to justify an equivalence: draw a truth table with columns for each subformula and show the final columns match. For quantifier negation: draw a small finite domain {a,b} and show the truth values to illustrate how ¬∀x P(x) becomes ∃x ¬P(x).

Formulas

¬(P ∧ Q) ≡ (¬P) ∨ (¬Q) — ¬ means negation, ∧ is and, ∨ is or. Truth values only; no SI unit. Applicable in propositional logic.

¬(P ∨ Q) ≡ (¬P) ∧ (¬Q) — symbols as above. Use when pushing negation inward.

P → Q ≡ ¬P ∨ Q — → means implication. Use to eliminate implication in proofs.

P ↔ Q ≡ (P → Q) ∧ (Q → P) — ↔ means logical equivalence.

¬(∀x P(x)) ≡ ∃x ¬P(x) — ∀ is universal quantifier, ∃ is existential; domain assumed stated.

¬(∃x P(x)) ≡ ∀x ¬P(x) — use when negating existential claims.

∃!x P(x) ≡ ∃x (P(x) ∧ ∀y (P(y) → y = x)) — uniqueness definition. = means equality in domain.

(A unless B) ≡ (¬B → A) ≡ (A ∨ B) — use with caution; choose form that fits the proof.

Note: these are logical equivalences about truth values; no physical units.

Worked examples

  1. Translate "Only students who register can attend the exam." (clear step-by-step)

    • Step 1: state domain: all people in the college.
    • Step 2: choose predicates: S(x): "x is a student"; R(x): "x registers"; A(x): "x can attend the exam".
    • Step 3: natural-language reading: "If someone can attend then they are a student and they registered" because "only students who register can attend" makes both being a student and registration necessary for attendance.
    • Step 4: formula: ∀x (A(x) → (S(x) ∧ R(x))).
    • Comment: Do NOT translate it as ∀x (R(x) → A(x)) — that would mean registration guarantees attendance.
  2. Translate "There is exactly one student who got full marks." (model exam answer)

    • Domain: students. Predicate: F(x): "x got full marks".
    • Use uniqueness definition:
      • Formula: ∃x (F(x) ∧ ∀y (F(y) → y = x)).
    • Alternative equivalent compact form often accepted: ∃x ∀y (F(y) ↔ y = x). Both specify one and only one.
    • Show a short justification: first part ∃x F(x) ensures at least one; second part ∀y (F(y) → y = x) ensures no other distinct y satisfies F.
  3. Translate and negate: "Every computer-engineering student knows C and either Java or Python."

    • Domain: all students. Predicates: CE(x): "x is a CE student"; K(x, lang): "x knows lang" where lang ∈ {C, Java, Python}.
    • Translation: ∀x (CE(x) → (K(x, C) ∧ (K(x, Java) ∨ K(x, Python)))).
    • Negation step-by-step (push negation inside using quantifier duality and De Morgan):
      • ¬∀x (CE(x) → (K(x, C) ∧ (K(x, Java) ∨ K(x, Python))))
      • ≡ ∃x ¬(CE(x) → (K(x, C) ∧ (K(x, Java) ∨ K(x, Python))))
      • ≡ ∃x (CE(x) ∧ ¬(K(x, C) ∧ (K(x, Java) ∨ K(x, Python))))
      • ≡ ∃x (CE(x) ∧ (¬K(x, C) ∨ ¬(K(x, Java) ∨ K(x, Python))))
      • ≡ ∃x (CE(x) ∧ (¬K(x, C) ∨ (¬K(x, Java) ∧ ¬K(x, Python))))
    • Final English: "There exists a CE student who either does not know C, or knows neither Java nor Python."

Common mistakes

  • Using → when sentence means ↔ ("iff") and vice versa.
  • Wrong quantifier order: ∀x ∃y vs ∃y ∀x are not equivalent; always justify order.
  • Forgetting to convert "exactly one" into ∃ and ∀ part; writing ∃x P(x) and claiming uniqueness without the second clause.
  • Mixing inclusive vs exclusive "or"; examiners often expect clarification which one.
  • Incorrect negation of quantifiers: writing ¬∀x P(x) as ∀x ¬P(x) (wrong).

For your exam

Kinds of questions: short definitions (define predicate, quantifier, etc.), translation tasks (English → formal), negation and simplification of formulas, showing equivalences (truth tables or algebraic steps), small proofs using contraposition or quantifier manipulation, and short error-spotting where you correct incorrect translations.

What a full-marks answer includes:

  • Domain stated, predicates defined with clear English meaning and types shown (unary, binary).
  • The precise formula(s) with correct quantifier order and parentheses.
  • If asked to negate or simplify, show each step (use quantifier duality and De Morgan) and a final English sentence explaining the negation.
  • For equivalences: either a truth table (for propositional formulas) drawn with exactly four rows for two variables or stepwise equivalence using known laws (cite De Morgan, implication elimination, etc.).

Quick check

  1. Translate: "Every cat likes some food." Domain: things (animals and foods); C(x): x is a cat; L(x,y): x likes y; Food(y): y is food.
  2. Translate: "Unless it rains, we will go to the picnic." Use R = "it rains", G = "we go".
  3. Write the negation of ∀x (P(x) → Q(x)).

Answers: 1) ∀x (C(x) → ∃y (Food(y) ∧ L(x,y))). 2) R ∨ G (or equivalently ¬R → G). 3) ∃x (P(x) ∧ ¬Q(x)).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?