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

Degree Level Programmes · Formal Computing Foundations · Lesson 27

Logical Equivalence, Implication and Normal Forms

Rewrite logical statements without changing their truth conditions.

Back to coursePreviousNext lesson

Lesson overview

Rewrite logical statements without changing their truth conditions.

CourseFundamentals of Computing
Topic strandPropositional 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

  • Test logical equivalence using truth tables.
  • Apply common equivalence laws.
  • Recognise the purpose of normal forms.

Learning outcomes

  • By the end of this lesson, you can test logical equivalence using truth tables.
  • By the end of this lesson, you can apply common equivalence laws.
  • By the end of this lesson, you can recognise the purpose of normal forms.

Key vocabulary

equivalenceimplicationDe Morgan's lawsnormal form

What this lesson is about

Logical equivalence means two expressions always have the same truth value. Implication means one statement being true guarantees another under the truth-table definition.

Normal forms rewrite logic into standard shapes. Conjunctive normal form (CNF) is an AND of OR-clauses; disjunctive normal form (DNF) is an OR of AND-clauses.

For example, P ⇒ (Q ∧ R) first becomes ¬P ∨ (Q ∧ R), then distributes into CNF as (¬P ∨ Q) ∧ (¬P ∨ R). Normal forms matter because standard shapes are easier to compare, simplify and implement.

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.

Logical equivalenceLogic term. Two formulae are logically equivalent when they have the same truth value under every valuation.
De Morgan's lawsNamed laws. Rules for pushing negation through and/or: not(P or Q) becomes not P and not Q; not(P and Q) becomes not P or not Q.
CNF (Conjunctive normal form)Acronym. A standard shape written as an AND of OR-clauses, useful for some automated reasoning and satisfiability methods.
DNF (Disjunctive normal form)Acronym. A standard shape written as an OR of AND-clauses, useful for expressing cases where a formula is true.
Normal formPhrase. A standard shape for a logical expression, useful for comparison, simplification or automated processing.
ValuationLogic term. An assignment of truth values to the propositions in a formula.

Formal notation and definitions

P ≡ Q means P and Q have the same truth value under every valuation.¬(P ∨ Q) ≡ ¬P ∧ ¬Q.¬(P ∧ Q) ≡ ¬P ∨ ¬Q.CNF is an AND of OR-clauses; DNF is an OR of AND-clauses.P ⇒ (Q ∧ R) ≡ (¬P ∨ Q) ∧ (¬P ∨ R).

How to read the symbols

P≡QP\equiv QP and Q have the same truth value under every valuation.
¬(P∨Q)\neg(P\lor Q)Not either P or Q.
CNFConjunctive normal form: an AND of OR-clauses.
DNFDisjunctive normal form: an OR of AND-clauses.
normal formA standardised shape for a logical expression.

Use equivalence notation only when two formulae match under every valuation. One matching example is not enough.

Degree-level reasoning

Propositional logic gives exact semantics to conditions. It is especially useful for simplifying guards, checking requirements and finding unreachable branches.

Truth tables are not busywork: they are exhaustive case analysis over all valuations.

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

NOT (A OR B) is equivalent to NOT A AND NOT B, which is useful when simplifying conditions.

Objects: the original formula, the rewritten formula, each valuation, the final truth columns, and the CNF or DNF target shape.

Model cue: Use paired truth tables. If the final columns match in every row, the statements are logically equivalent.

2. Mathematical working

¬(P∨Q)≡¬P∧¬Q\neg(P\lor Q)\equiv \neg P\land\neg QPQ¬(P∨Q)¬P∧¬QTTFFTFFFFTFFFFTT\begin{array}{c c|c|c}P&Q&\neg(P\lor Q)&\neg P\land\neg Q\\\hline T&T&F&F\\T&F&F&F\\F&T&F&F\\F&F&T&T\end{array}P⇒(Q∧R)≡¬P∨(Q∧R)≡(¬P∨Q)∧(¬P∨R)P\Rightarrow(Q\land R)\equiv \neg P\lor(Q\land R)\equiv(\neg P\lor Q)\land(\neg P\lor R)CNF is an AND of OR-clauses; DNF is an OR of AND-clauses\text{CNF is an AND of OR-clauses; DNF is an OR of AND-clauses}
Plain text version
P ⇒ (Q ∧ R)
≡ ¬P ∨ (Q ∧ R)
≡ (¬P ∨ Q) ∧ (¬P ∨ R), which is CNF

3. How to read the working

  1. Read the equivalence symbol ≡ as 'has the same truth value in every row', not merely 'looks similar'.
  2. Compare the final columns of the two truth-table expressions row by row.
  3. For De Morgan's law, moving negation inside changes ∨ to ∧, or ∧ to ∨.
  4. For implication, first rewrite P ⇒ Q as ¬P ∨ Q before trying to reach a normal form.
  5. For CNF, aim for an AND of OR-clauses; for DNF, aim for an OR of AND-clauses.
  6. Translate equivalence into program behaviour: either form can replace the other without changing the condition's result.

4. Computing meaning and check

Equivalence allows a condition to be rewritten without changing behaviour. That matters when simplifying code or requirements.

Now check: Use a truth table to verify ¬(P ∧ Q) ≡ ¬P ∨ ¬Q. Then convert P ⇒ (Q ∧ R) into CNF.

Worked example

From scenario to formal reasoning

Scenario: NOT (A OR B) is equivalent to NOT A AND NOT B, which is useful when simplifying conditions.

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

Reveal model answer

De Morgan's law says ¬(P ∨ Q) is equivalent to ¬P ∧ ¬Q. Normal forms use standard shapes: CNF is an AND of OR-clauses and DNF is an OR of AND-clauses. For example, P ⇒ (Q ∧ R) is equivalent to ¬P ∨ (Q ∧ R), which distributes to the CNF (¬P ∨ Q) ∧ (¬P ∨ R).

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 P ≡ Q means P and Q have the same truth value under every valuation.
  2. Apply: Use the relevant definition from propositional 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 moving a negation inside a statement without changing the connective correctly.

Guided practice

  1. Use a truth table to verify ¬(P ∧ Q) ≡ ¬P ∨ ¬Q.
  2. Rewrite P ⇒ (Q ∧ R) by first eliminating implication.
  3. Distribute to produce CNF: (¬P ∨ Q) ∧ (¬P ∨ R).
  4. Explain why a normal form is useful for comparing or implementing conditions.

Quick checks

1. Which is a CNF form?

2. Why use normal forms?

Digital exam practice

Example exam task

Verify a De Morgan equivalence with a truth table, then convert P ⇒ (Q ∧ R) into CNF. Explain why CNF or DNF can help automated comparison.

Notation toolkit

P≡QP\equiv Q

Means: P and Q have the same truth value in every case

How to use: Use it when comparing formulae.

¬(P∨Q)\neg(P\lor Q)

Means: a negated compound statement

How to use: Use it when applying De Morgan's laws.

⋀⋁L\bigwedge\bigvee L

Means: an AND of OR-clauses, the shape of CNF

How to use: Use it when converting statements to normal form.

What a good answer is expected to show

A strong answer for this lesson defines the original formula, the rewritten formula, each valuation, the final truth columns, and the CNF or DNF target shape, applies the propositional logic method with visible working, and finishes by interpreting the result in the computing scenario.

How to solve it

  1. Read the equivalence symbol ≡ as 'has the same truth value in every row', not merely 'looks similar'.
  2. Compare the final columns of the two truth-table expressions row by row.
  3. For De Morgan's law, moving negation inside changes ∨ to ∧, or ∧ to ∨.
  4. For implication, first rewrite P ⇒ Q as ¬P ∨ Q before trying to reach a normal form.
  5. For CNF, aim for an AND of OR-clauses; for DNF, aim for an OR of AND-clauses.
  6. Translate equivalence into program behaviour: either form can replace the other without changing the condition's result.

Model answer

Reveal model answer
¬(P∨Q)≡¬P∧¬Q\neg(P\lor Q)\equiv\neg P\land\neg QP⇒(Q∧R)≡¬P∨(Q∧R)≡(¬P∨Q)∧(¬P∨R)P\Rightarrow(Q\land R)\equiv\neg P\lor(Q\land R)\equiv(\neg P\lor Q)\land(\neg P\lor R)CNF=⋀i⋁jLij,DNF=⋁i⋀jLij\text{CNF}=\bigwedge_i\bigvee_j L_{ij},\quad \text{DNF}=\bigvee_i\bigwedge_j L_{ij}

De Morgan's law can be verified by matching the final columns for ¬(P ∨ Q) and ¬P ∧ ¬Q. For P ⇒ (Q ∧ R), eliminate implication to get ¬P ∨ (Q ∧ R), then distribute to CNF: (¬P ∨ Q) ∧ (¬P ∨ R). CNF and DNF help automated comparison because they put formulae into standard shapes.

Practise next

  1. Use a truth table to verify ¬(P ∧ Q) ≡ ¬P ∨ ¬Q.
  2. Rewrite P ⇒ (Q ∧ R) by first eliminating implication.

Self-marking criteria

  • Uses a complete truth table for equivalence.
  • Eliminates implication to ¬P ∨ (Q ∧ R).
  • Distributes to (¬P ∨ Q) ∧ (¬P ∨ R).
  • Names CNF and DNF correctly.
  • Explains the computing purpose of normal forms.

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: Predicate Logic: Quantifiers, Domains and Translation.