Use logic statements to define parts of an algorithm solution

9.2 Algorithms – Using Logic Statements to Define Parts of an Algorithm

Learning Objective

By the end of this lesson you will be able to use logical statements (AND, OR, NOT, IF‑THEN, etc.) to clearly define the input, processing, and output sections of an algorithm solution.

Why Logic Matters in Algorithms

• Logic provides a precise language for describing decisions and repetitions.
• It allows algorithms to be unambiguous, which is essential for implementation and testing.
• Logical expressions can be directly translated into programming constructs such as if, while, and for loops.

Basic Logical Operators

Defining the Parts of an Algorithm with Logic

1. Input Section

   Identify the data required and any pre‑conditions using logical statements.

   Example: “The algorithm requires a positive integer \$n\$ such that \$n > 0\$.”

2. Processing Section

   Use logical expressions to control the flow of operations.

   Typical structures:

   • Conditional execution – IF \$condition\$ THEN … ELSE …
   • Repetition – WHILE \$condition\$ DO …
   • Combined conditions – IF \$(A \cdot B) + C\$ THEN …

3. Output Section

   State the post‑conditions that must hold when the algorithm terminates.

   Example: “The algorithm outputs the factorial \$f\$ such that \$f = n!\$ and \$f > 0\$.”

Worked Example – Computing the Greatest Common Divisor (GCD)

We will define the algorithm using logical statements for each part.

Problem Statement

Given two positive integers \$a\$ and \$b\$, find their greatest common divisor \$g\$.

Algorithm (Pseudocode)

1. INPUT a, b
2. PRE‑CONDITION: \$a > 0 \cdot b > 0\$
3. WHILE \$b \neq 0\$ DO
4.     \$temp \leftarrow b\$
5.     \$b \leftarrow a \bmod b\$
6.     \$a \leftarrow temp\$
7. END WHILE
8. OUTPUT \$a\$   // \$a\$ now holds the GCD
9. POST‑CONDITION: \$a = \gcd(original\a, original\b)\$

Explanation of Logical Statements

• Line 2 uses the AND operator to ensure both inputs are positive.
• Line 3 uses the NOT‑EQUAL (\$\neq\$) condition to control the loop.
• The loop invariant (a logical condition that remains true) can be expressed as:

  \$\forall k \ge 0,\; \gcd(ak, bk) = \gcd(original\a, original\b)\$

  where \$ak\$ and \$bk\$ are the values of \$a\$ and \$b\$ after \$k\$ iterations.

Practice Exercise

Write an algorithm to determine whether a given year \$y\$ is a leap year. Use logical statements to define the input, processing, and output sections.

Guidelines

1. Input: \$y\$ (an integer).
2. Pre‑condition: \$y > 0\$.
3. Processing: Use the rule

   \$\text{Leap} \leftrightarrow (y \bmod 4 = 0) \cdot \bigl((y \bmod 100 \neq 0) + (y \bmod 400 = 0)\bigr)\$

4. Output: “Leap year” if the condition is true, otherwise “Common year”.

Summary Checklist

• Identify all required inputs and express any pre‑conditions with logical operators.
• Translate decision points into IF‑THEN statements using \$ \cdot, +, \lnot \$ as needed.
• Use WHILE or REPEAT loops with clear logical termination conditions.
• State post‑conditions that describe the expected output in logical form.