Study Notes on Logical and Algorithmic Thinking

LOGICAL AND ALGORITHMIC THINKING NOTES

OBJECTIVES

• Learn the importance of logic to computational thinking.

• Appreciate the difference between deductive and inductive reasoning.

• Understand Boolean logic and its importance to computation.

• See the importance of using logical and mathematical notation instead of natural language.

• Learn the properties of algorithms: sequence, iteration, selection.

• Understand the importance of state in algorithms.

• See common mistakes made in logical and algorithmic thinking and learn how to avoid them.

APPROACH

• Logic and algorithms are fundamental to computational thinking (CT).

• They support the subject and appear frequently in various applications.

• Humans have an intuitive grasp of logic and algorithms; however, they are mathematical in nature with strict rules.

• Understanding precise concepts is essential to avoid mistakes.

• Focus will be on core areas where new learners typically encounter difficulties, ultimately developing a habit of logical and algorithmic thought.

• Aim: Learn to apply logic and algorithms to problem-solving with practice making the processes automatic.

LOGICAL THINKING

• Logic is crucial in computational thinking and involves creating sound logical expressions from intuitive ideas.

Definition of Logic

• Logic: A system to differentiate between valid and invalid arguments.

  • An argument is defined as a chain of reasoning leading to a conclusion.

  • Basic format of a logical argument:

  1. Premise 1: Socrates is a man.

  2. Premise 2: All men are mortal.

  3. Conclusion: Therefore, Socrates is mortal.

• Logical reasoning helps develop and test hypotheses, relying on premises which have a truth value (true or false).

Premises

• Premises: Statements that can be evaluated as true or false, forming the basis of logical arguments.

• Forms that cannot serve as premises: Questions or commands (e.g. ‘What time is it?’).

INDUCTIVE VS DEDUCTIVE REASONING

• Arguments can vary in strength, categorized primarily as inductive and deductive.

Deductive Arguments

• Deductive reasoning is the strongest form where the conclusion necessarily follows from true premises.

  • Example:

  1. Missie is a dog.

  2. All dogs are brown.

  3. Conclusion: Therefore, Missie is brown.

  • The argument fails if a premise is false (e.g., not all dogs are brown).

• Deductive reasoning requires strict construction and true premises. A false premise or poor construction leads to invalidity.

Inductive Arguments

• Inductive reasoning deals with scenarios with less certainty than deductive inference.

• Example:

  1. A bag contains 99 red balls and one black ball.

  2. 100 people draw one ball each.

  3. Sarah is one of those people, so she probably drew a red ball.

• This type of reasoning supports defining probabilities rather than certainties.

BOOLEAN LOGIC

• Boolean logic reflects the binary nature of computers, using only true/false values.

Propositions

• Propositions: Statements in Boolean logic evaluated as true or false.

  • Key properties include:

  1. A proposition can only have one value (either true or false).

  2. Propositions must have clear meanings to avoid ambiguity.

  3. Complex statements can combine propositions using logical operators.

Logical Operators

1. AND (Conjunction): Both propositions must be true for the conclusion to be true.
   Example: A ∧ B is true only if both A and B are true.

2. OR (Disjunction): At least one proposition must be true for the conclusion to be true.
   Example: A ∨ B is true if either A or B (or both) are true.

3. NOT (Negation): Flips the truth value of a single proposition.
   Example: If A is true, ¬A (NOT A) is false.

4. IMPLIES (Implication): States that if the first proposition is true, then the second must be true.
   Example: A → B is true except when A is true and B is false.

5. IF AND ONLY IF (Biconditional): Both propositions are either true or false together.
   Example: A ↔ B is true if both A and B are true or both are false.

Symbolic Logic

• Symbolic logic uses symbols instead of natural language to maintain precision and avoid ambiguity.

• Example mappings:

  • AND: Λ

  • OR: V

  • NOT: ¬

  • IMPLIES: →

  • IF AND ONLY IF: ↔

• Truth tables are used to define the combinations of proposition values and their logical validity.

Truth Table Examples

• 
  

• AND Truth Table:

  P	Q	P AND Q
  True	True	True
  True	False	False
  False	True	False
  False	False	False

• 
  

• OR Truth Table:

  P	Q	P OR Q
  True	True	True
  True	False	True
  False	True	True
  False	False	False

• 
  

• NOT Truth Table:
  

  P	NOT P
  True	False
  False	True
  ALGORITHMIC THINKING

  • Algorithmic thinking focuses on processes that build upon logic to produce outputs based on decision-making rules.

  Definition of Algorithms

  • Algorithm: A clearly defined sequence of steps describing a process based on unambiguous instructions with specific start and endpoints.

  • Algorithms translate logical rules into systematic procedures to achieve tasks effectively.

  Key Properties of Algorithms

  1. Collection of Individual Steps: Each step must be explicit and defined.

  2. Definiteness: Every step must have a definite and unambiguous meaning.

  3. Sequential: Steps must be carried out in a specific order.

  Importance of State in Algorithms

  • State: The configuration of all information tracked by a program at a certain time.

  • Algorithms change state as they progress; maintaining sequence ensures the state evolves predictably.

  Control Mechanisms in Algorithms

  1. Iteration / Looping: Reversing a series of steps multiple times.

     • Example: Using variable X to represent iterations.

  2. Selection (Conditional Statements): Allowing decision-making based on the current state value.

     • Example using an ‘if-then-else’ construct.

  Example of an Algorithm in Pseudocode

  • A simple framework for a game:

  1. start the game.

  2. loop:

  3. prompt the player.

  4. if chosen square is valid, place symbol.

  5. check for winner or draw.

  6. switch players if not won/drawn.

  7. end loop if game concludes.

  8. display game over message.

  COMMON MISTAKES (GOTCHAS)

  • Clarity and Precision: Algorithms and logic must be outlined in precise detail to avoid ambiguity.

  • Misuse of Logical Operators: Understanding logical connectors (AND, OR, NOT) is crucial; often misapplied from natural language.

  • Undescribed Eventualities: Missing 'else' procedures in conditional algorithms, for example in grading algorithms.

  • Complex Conditionals: Ensure proper definition and interpretation, especially with the NOT operator when forming conditions.

  These topics illustrate how critical understanding logic and algorithms are in computational thinking, directly influencing how computers solve problems and execute tasks effectively. Achieving clarity, precision, and proper logical application forms the foundation of good computational practices and algorithmic development.