Unit 2: Computational Thinking and Algorithms — Long Questions

Computational thinking is a way of thinking to solve problems clearly and logically. It means thinking like a problem solver: we understand a problem step by step, break a big problem into smaller parts, look for patterns in problems and solutions, remove unnecessary details and focus on important points, and then create clear steps to solve the problem. These steps can be followed by either humans or computers, which is why computational thinking is not limited to computer science students — it is used by scientists, engineers, and even chefs when planning complex tasks.

Importance 1. It helps us think logically and clearly instead of guessing.
2. Breaking a problem into smaller parts (decomposition) makes a difficult problem easier to manage.
3. Creating steps in the correct order prevents errors during problem solving.
4. Clear steps can be understood and used easily by anyone, and computers can follow the same step-by-step instructions.
5. Good planning through computational thinking leads to correct and efficient results.

Example To make tea, the problem can be solved with the algorithm: Start → Boil Water → Steep Tea → Add Milk or Lemon → Serve Tea → End. This shows how a familiar task is converted into a clear, step-by-step logical solution, which is the essence of computational thinking.

Logic is the science of true reasoning and is an important concept in computer science. As a knowledge representation framework, it helps computers store, understand, and use information correctly, and it allows complex information to be represented in a simple way using rules and true/false conditions. Logical statements are used in programs and algorithms to help control the flow of programs, making logic the basis of many computer operations.

Role in reasoning and decision making: Logic helps both computers and humans draw correct conclusions. Decisions are made based on facts and rules rather than guesswork, which removes confusion. Logical reasoning allows problems to be solved step by step, and it helps computers choose the correct action in a given situation, ensuring that decisions are consistent and accurate. This is why logic is used in expert systems and artificial intelligence, where a system must reason over facts to reach a decision — for example, an "if-then" rule such as "If it rains, then we will stay indoors" shows how logic connects a condition to a decision.

Propositional logic is a basic form of logic used in computer science. It deals with statements, called propositions, that can be true or false but not both at the same time. Questions and commands are not propositions because they do not have a clear true/false value. A proposition is usually represented by a capital letter such as P, Q, or R — for example, if P represents "The sky is blue," we write P = "The sky is blue." Other examples are "2 + 3 = 5" (True), "1 > 3" (False), and "Today is Sunday" (True or False depending on the day).

Simple propositions A simple proposition contains only one statement and cannot be broken into smaller parts, e.g., "It is raining."

Compound propositions A compound proposition is formed by combining two or more simple propositions using logical connectives such as AND, OR, and NOT, e.g., "It is raining and it is cold" (a combination of "It is raining" AND "It is cold"). AND is true only when both statements are true, OR is true when at least one statement is true, and NOT reverses the truth value of a statement. Compound propositions let us express more complex ideas than simple propositions and are common in logical reasoning and computer programs.

Truth tables are used in logic to show the truth values of statements. A truth table lists all possible combinations of truth values of the propositions involved and shows the final result of the logical expression for each combination. They are widely used in propositional logic, computer science, and mathematics to check the correctness of logical expressions and make logical thinking clear and simple.

Creating a truth table First, identify the propositions involved (e.g., A and B). Each proposition is given a truth value of True or False, and all possible combinations are listed — since each proposition can take 2 values, n propositions require 2ⁿ rows. The logical connectives (AND, OR, NOT) are then applied step by step to these combinations, and the final result is written for each row in a neat, organized table.

Example truth table for A AND B, A OR B, and NOT A:
| A | B | A AND B | A OR B | NOT A |
|---|---|---------|--------|-------|
| True | True | True | True | False |
| True | False | False | True | False |
| False | True | False | True | True |
| False | False | False | False | True |

Using such a table, we can immediately see the truth value of a compound expression for any combination of inputs, which helps in checking complex expressions, comparing statements, and supporting decision-making.

Propositional equivalence explains when two logical expressions have the same meaning. Even if two expressions look different, they may give the same result for every combination of truth values. Propositional equivalence is checked using truth tables: if two expressions have the same truth values in all cases, they are said to be equivalent, shown using the symbol "≡" (or "⟺").

Identifying equivalence Each expression is tested for all possible truth values of its propositions using a truth table. If the results match in every row, the expressions are equivalent; logical laws can also be used to identify equivalence and simplify expressions.

Example The expressions (A AND NOT B) OR (B AND NOT A) and (A OR B) AND (NOT A OR NOT B) are logically equivalent, because both are true in exactly the same cases (both represent XOR):
| A | B | (A AND NOT B) OR (B AND NOT A) | (A OR B) AND (NOT A OR NOT B) |
|---|---|---|---|
| F | F | F | F |
| F | T | T | T |
| T | F | T | T |
| T | T | F | F |
Therefore: (A AND NOT B) OR (B AND NOT A) ⟺ (A OR B) AND (NOT A OR NOT B).

Importance Equivalence helps simplify complex logic problems by allowing complex expressions to be replaced with simpler equivalent ones, saving time and effort. In programming, this improves code efficiency, helps avoid logical errors, and ensures correct and consistent reasoning and decision-making.

Propositional satisfiability is a concept in logic that checks whether a statement can be true — that is, whether a logical expression has at least one situation in which it is true. It is widely used in computer science, especially in problem solving, programming, algorithm design, and verifying programs.

A proposition is satisfiable if there is at least one combination of truth values that makes it true. If all possible combinations make it false, the proposition is unsatisfiable. Whether an expression is satisfiable depends on its structure and the logical connectives (AND, OR, NOT) used; checking all possible cases with a truth table is one way to test satisfiability.

Examples of satisfiable expressions "P OR Q" is satisfiable because it is true if either P or Q is true. "P AND Q" is satisfiable because it is true when both P and Q are true. Similarly, "Bring pizza OR (burger AND do NOT bring soda)" is satisfiable — bringing pizza with no soda makes it true, so a solution exists.

Example of an unsatisfiable expression: "P AND NOT P" is never true because P cannot be both true and false at the same time, so it is unsatisfiable. Likewise, "You must bring pizza AND you must NOT bring pizza" has no solution and is unsatisfiable.

Predicate logic is an extension of propositional logic that allows us to express more detailed statements about objects, their properties, and the relationships between them. A predicate is a statement that can be true or false depending on the values of variables — for example, "x is greater than 5" or isEven(x), which is true only when x is an even number. Variables represent objects or values in the domain of discourse. Unlike propositional logic, which treats a statement such as "Ali is Tall" (A) as a single unit that cannot be examined further, predicate logic can write this as Tall(Ali), separating the subject (Ali) from the property (Tall), making it much more expressive — it can represent general statements like "All students are hardworking" or "Some books are interesting."

Quantifiers describe how many objects satisfy a condition:

• The Universal Quantifier "∀" (for all) means a statement is true for every object in a set, e.g., "∀x, x > 0" means "For all x, x is greater than 0."
• The Existential Quantifier "∃" (there exists) means a statement is true for at least one object in a set, e.g., "∃x, x is even" means "There exists at least one x that is even." Quantifiers can be combined with predicates, e.g., "∀x ∃y, x < y" means "for every x there exists a y greater than x."

Application to real-world problems Predicate logic can model real situations by representing relationships using predicates — for example, Borrows(x, y) meaning "student x borrows book y," and Teaches(t, s) meaning "teacher t teaches student s," used to model a library system. Quantifiers let us write general rules, such as ∀x, Student(x) → Borrows(x, Book) ("every student borrows a book") and ∃y, Book(y) ∧ Available(y) ("there exists at least one book that is available"). Using such facts and rules, we can reason and draw conclusions — for example, if "∀x, Student(x) → HasLibraryCard(x)" and "Ali is a student," we can conclude "Ali has a library card," helping systems make correct and consistent decisions such as checking whether a student can borrow a book.