Fundamentals of Computing: Propositional Logic: Syntax, Semantics and Truth Tables

Lesson overview

Evaluate compound logical statements.

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

Distinguish propositions from non-propositions.
Use and, or, not and implication accurately.
Construct a truth table for a compound statement.

Learning outcomes

By the end of this lesson, you can distinguish propositions from non-propositions.
By the end of this lesson, you can use and, or, not and implication accurately.
By the end of this lesson, you can construct a truth table for a compound statement.

Key vocabulary

What this lesson is about

Propositional logic studies statements that are either true or false and combines them using connectives such as not, and, or and implies. Syntax is the written form; semantics is the meaning.

Truth tables give the semantics by checking every possible truth-value assignment. They are exhaustive, so they are useful for proving equivalence, implication and condition behaviour.

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.

PropositionLogic term. A statement with a definite truth value: true or false.

Truth tableNamed method. An exhaustive table of all truth-value assignments for a logical formula.

ConnectiveLogic term. A logical operator such as not, and, or, or implies.

SemanticsPhrase. The meaning of a formal expression. In propositional logic, truth tables define the semantics of connectives.

Formal notation and definitions

\negP, P \land Q, P \lor Q and P \Rightarrow Q are compound propositions. P \Rightarrow Q is false only when P is true and Q is false. Truth tables define semantics by cases.

How to read the symbols

$\neg P$ Not P.

$P\land Q$ P and Q are both true.

$P\lor Q$ At least one of P or Q is true.

$P\Rightarrow Q$ False only when P is true and Q is false.

Use truth-table notation to evaluate every possible truth-value assignment, not just the case that feels most likely.

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

A login rule such as admin OR verified can be analysed as a proposition before it is implemented as a condition.

Objects: propositions P and Q, their truth values, the connective, and the final truth-table column.

Model cue: Use a truth table with one row per valuation. For two propositions P and Q there are four rows.

2. Mathematical working

A\lor V\quad\text{means Admin is true, Verified is true, or both are true}

\begin{array}{c c|c}A & V & A\lor V\\\hline T&T&T\\ T&F&T\\ F&T&T\\ F&F&F\end{array}

Plain text version

Admin Verified | Admin ∨ Verified
T     T        | T
T     F        | T
F     T        | T
F     F        | F

3. How to read the working

Read A and V as propositions with truth values, not as variables holding arbitrary data.
For A ∨ V, the final column is true when at least one of A or V is true.
Check all four rows because two propositions have 2² possible truth-value assignments.
Translate the final column into condition behaviour: the access rule fails only when both inputs are false.

4. Computing meaning and check

The truth table is exhaustive evidence. It shows exactly when a program condition grants access and when it denies it.

Now check: Build the truth table for P ⇒ Q and identify the single row where it is false.

Worked example

From scenario to formal reasoning

Scenario: A login rule such as admin OR verified can be analysed as a proposition before it is implemented as a condition.

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

Reveal model answer

For a login rule Admin ∨ Verified, the result is true when Admin is true, Verified is true, or both are true. It is false only when both are false.

Worked solution structure

How a strong answer should be written

Define: State the domain and the objects under discussion. For this lesson, begin from ¬P, P ∧ Q, P ∨ Q and P ⇒ Q are compound propositions.
Apply: Use the relevant definition from propositional 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 reading implication as everyday causation. In logic, implication has a precise truth-table meaning.

Guided practice

Build the truth table for P ⇒ Q and identify the only false row.
Translate an access rule Admin ∨ Verified into a truth table.
Explain why logical implication is not the same as everyday causation.
Give one program condition that is unreachable according to a truth table.

Quick checks

1. P ⇒ Q is false only when:

P is false and Q is trueP and Q are both falseP is true and Q is false

2. A truth table is useful because it:

replaces the need for definitionschecks every truth-value assignmentchecks only likely cases

Digital exam practice

Example exam task

Construct the truth table for P ⇒ Q and use it to explain a program guard where P means 'precondition holds' and Q means 'result is valid'. Identify the one false row and explain implication without everyday causation language.

Notation toolkit

P,Q

Means: propositions with truth values

How to use: Use them as simple true-or-false variables.

P\Rightarrow Q

Means: implication: false only when P is true and Q is false

How to use: Use it for promise-style conditions.

2^n

Means: the number of truth-table rows for n propositions

How to use: Use it to check that the table is complete.

What a good answer is expected to show

A strong answer for this lesson defines propositions P and Q, their truth values, the connective, and the final truth-table column, applies the propositional logic method with visible working, and finishes by interpreting the result in the computing scenario.

How to solve it

Read A and V as propositions with truth values, not as variables holding arbitrary data.
For A ∨ V, the final column is true when at least one of A or V is true.
Check all four rows because two propositions have 2² possible truth-value assignments.
Translate the final column into condition behaviour: the access rule fails only when both inputs are false.

Model answer

Reveal model answer

P\Rightarrow Q\equiv\neg(P\land\neg Q)

\begin{array}{c c|c}P&Q&P\Rightarrow Q\\\hline T&T&T\\T&F&F\\F&T&T\\F&F&T\end{array}

For P ⇒ Q, the truth table is true except when P is true and Q is false. As a program guard, this means the requirement is violated only when the precondition holds but the promised result does not. Logical implication is a truth-table connective, not a claim that P causes Q.

Practise next

Build the truth table for P ⇒ Q and identify the only false row.
Translate an access rule Admin ∨ Verified into a truth table.

Self-marking criteria

Lists all four valuations.
Marks only P true and Q false as false.
Uses syntax/semantics language accurately.
Connects the table to guard behaviour.
Avoids causal wording for implication.

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: Logical Equivalence, Implication and Normal Forms.