🌟 Level 2 - Topic 13: Boolean Algebra (Part 1) 🧮💡

1) Introduction to Boolean Algebra 🧮

Welcome to the fascinating world of Boolean Algebra! In this topic, we're stepping away from numbers for a bit and diving into the realm of logic. Boolean Algebra is a branch of algebra where variables can only have one of two values: TRUE or FALSE. It might sound simple, but it's the fundamental mathematics behind digital logic and computer science. Everything from the circuits in your smartphone to complex software algorithms relies on the principles of Boolean Algebra. In Part 1, we will introduce the basic concepts, values, and operations of Boolean Algebra.

Boolean Algebra is a system of algebra dealing with logical values and operations. It operates on variables that can be either TRUE or FALSE (or equivalently, 1 or 0).

Boolean Algebra provides a way to represent and simplify logical expressions, making it invaluable in fields like computer science, digital electronics, and formal logic.

1.1 Boolean Values and Variables

In Boolean Algebra, we work with Boolean values and Boolean variables.

  • Boolean Values: There are just two Boolean values:
    • TRUE (represented as 1)
    • FALSE (represented as 0)
  • Boolean Variables: These are symbols (usually letters like \(x\), \(y\), \(A\), \(B\), etc.) that can hold either a TRUE or FALSE value.

Unlike variables in regular algebra that can represent a range of numbers, Boolean variables are binary – they can only be one of two states.

Example 1: Boolean Values in Context

Consider these statements:

  • "The sun rises in the East." - This is TRUE (Boolean value: 1).
  • "2 + 2 = 5." - This is FALSE (Boolean value: 0).
  • Let \(x\) be a Boolean variable representing "It is raining". \(x\) can be TRUE if it is raining, or FALSE if it is not.


2) Basic Boolean Operations 💡

Boolean Algebra defines several operations. We'll start with the three fundamental ones: AND, OR, and NOT. These operations manipulate Boolean values to produce new Boolean values.

2.1 AND Operation (Logical Conjunction)

The AND operation, often denoted as \( \wedge \), \( \cdot \), or simply by juxtaposition (like in multiplication), is true if and only if both of its operands are TRUE. Otherwise, it is FALSE.

Think of "AND" as requiring all conditions to be met. If we have two Boolean variables \(A\) and \(B\), \(A \text{ AND } B\) is TRUE only when \(A\) is TRUE and \(B\) is TRUE.

Truth Table for AND

A truth table systematically lists all possible input combinations and their corresponding output for a Boolean operation.

Input AInput BA AND B
FALSE (0)FALSE (0)FALSE (0)
FALSE (0)TRUE (1)FALSE (0)
TRUE (1)FALSE (0)FALSE (0)
TRUE (1)TRUE (1)TRUE (1)

Example 2: AND Operation

Let \(P\) be "It is sunny" and \(Q\) be "It is warm". Consider "P AND Q":

  • If it is sunny (TRUE) AND it is warm (TRUE), then "P AND Q" is TRUE.
  • If it is sunny (TRUE) AND it is NOT warm (FALSE), then "P AND Q" is FALSE.
  • If it is NOT sunny (FALSE) AND it is warm (TRUE), then "P AND Q" is FALSE.
  • If it is NOT sunny (FALSE) AND it is NOT warm (FALSE), then "P AND Q" is FALSE.

2.2 OR Operation (Logical Disjunction)

The OR operation, often denoted as \( \vee \) or \( + \), is true if at least one of its operands is TRUE. It is FALSE only if both operands are FALSE.

Think of "OR" as needing at least one condition to be met. If we have two Boolean variables \(A\) and \(B\), \(A \text{ OR } B\) is TRUE when \(A\) is TRUE or \(B\) is TRUE, or both are TRUE.

Truth Table for OR

Input AInput BA OR B
FALSE (0)FALSE (0)FALSE (0)
FALSE (0)TRUE (1)TRUE (1)
TRUE (1)FALSE (0)TRUE (1)
TRUE (1)TRUE (1)TRUE (1)

Example 3: OR Operation

Let \(R\) be "I will go swimming" and \(S\) be "I will read a book". Consider "R OR S":

  • If I go swimming (TRUE) OR I read a book (TRUE), then "R OR S" is TRUE.
  • If I go swimming (TRUE) OR I do NOT read a book (FALSE), then "R OR S" is TRUE.
  • If I do NOT go swimming (FALSE) OR I read a book (TRUE), then "R OR S" is TRUE.
  • If I do NOT go swimming (FALSE) OR I do NOT read a book (FALSE), then "R OR S" is FALSE. (Only when I do neither is "R OR S" false).

2.3 NOT Operation (Logical Negation)

The NOT operation, often denoted as \( \neg \), \( \sim \), or an overline (like \( \overline{A} \)), is a unary operation that reverses the Boolean value of its operand. If the operand is TRUE, NOT makes it FALSE, and vice versa.

"NOT" is used to negate a condition. If \(A\) is a Boolean variable, \( \text{NOT } A \) (or \( \overline{A} \)) is TRUE when \(A\) is FALSE, and FALSE when \(A\) is TRUE.

Truth Table for NOT

Input ANOT A
FALSE (0)TRUE (1)
TRUE (1)FALSE (0)

Example 4: NOT Operation

Let \(T\) be "The door is open". Consider "NOT T":

  • If "The door is open" is TRUE, then "NOT T" (i.e., "The door is NOT open") is FALSE.
  • If "The door is open" is FALSE, then "NOT T" (i.e., "The door is NOT open") is TRUE.


3) Boolean Expressions and Evaluation 📝

We can combine Boolean variables and operations to form Boolean expressions. These expressions represent complex logical conditions. To evaluate a Boolean expression, we need to determine its overall Boolean value (TRUE or FALSE) based on the values of its variables and the operations involved.

3.1 Constructing Boolean Expressions

Boolean expressions are constructed using:

  • Boolean variables (e.g., \(x, y, A, B\)).
  • Boolean operators: AND, OR, NOT.
  • Parentheses to group operations and control precedence, just like in regular algebra.

Example 5: Boolean Expressions

Here are some examples of Boolean expressions:

  • \( A \wedge B \) (A AND B)
  • \( X \vee Y \) (X OR Y)
  • \( \neg P \) (NOT P)
  • \( (A \wedge B) \vee \neg C \) ((A AND B) OR (NOT C))
  • \( \neg (X \vee Y) \wedge Z \) (NOT (X OR Y) AND Z)

3.2 Evaluating Boolean Expressions

To evaluate a Boolean expression, you need to substitute the Boolean values (TRUE or FALSE, or 1 or 0) for the variables and then perform the operations according to the rules of Boolean Algebra and operator precedence (typically, NOT is performed first, then AND, then OR, and parentheses are used to override precedence).

Example 6: Evaluating a Boolean Expression

Evaluate the Boolean expression \( (A \wedge B) \vee \neg C \) when \(A = \text{TRUE}\), \(B = \text{FALSE}\), and \(C = \text{TRUE}\).

Step 1: Substitute values.

\( (\text{TRUE} \wedge \text{FALSE}) \vee \neg \text{TRUE} \)

Step 2: Evaluate within parentheses first.

\( (\text{TRUE} \wedge \text{FALSE}) = \text{FALSE} \) (because for AND, both must be TRUE)

\( \neg \text{TRUE} = \text{FALSE} \) (NOT of TRUE is FALSE)

So, the expression becomes: \( \text{FALSE} \vee \text{FALSE} \)

Step 3: Evaluate the OR operation.

\( \text{FALSE} \vee \text{FALSE} = \text{FALSE} \) (because for OR, at least one needs to be TRUE, which is not the case here)

Therefore, the Boolean expression \( (A \wedge B) \vee \neg C \) evaluates to FALSE when \(A = \text{TRUE}\), \(B = \text{FALSE}\), and \(C = \text{TRUE}\).


4) Practice Questions 🎯

5.1 Fundamental – Build Skills

1. What are the two Boolean values? Represent them using both words and numbers.

2. Complete the truth table for the AND operation:

Input AInput BA AND B
FALSEFALSE?
FALSETRUE?
TRUEFALSE?
TRUETRUE?

3. Complete the truth table for the OR operation:

Input AInput BA OR B
FALSEFALSE?
FALSETRUE?
TRUEFALSE?
TRUETRUE?

4. Complete the truth table for the NOT operation:

Input ANOT A
FALSE?
TRUE?

5. Evaluate the Boolean expression \( A \wedge B \) when \(A = \text{TRUE}\) and \(B = \text{TRUE}\).

6. Evaluate the Boolean expression \( A \vee B \) when \(A = \text{FALSE}\) and \(B = \text{TRUE}\).

7. Evaluate the Boolean expression \( \neg A \) when \(A = \text{TRUE}\).

8. Evaluate \( (A \wedge B) \vee C \) when \(A = \text{TRUE}\), \(B = \text{FALSE}\), and \(C = \text{TRUE}\).

9. Evaluate \( \neg (A \vee B) \) when \(A = \text{FALSE}\) and \(B = \text{FALSE}\).

10. If \(X\) is TRUE, what is the value of \( \neg (\neg X) \)? Explain.

5.2 Challenging – Push Limits 💪🚀

1. Create a truth table for the Boolean expression \( (A \wedge B) \vee \neg A \).

2. Evaluate the Boolean expression \( \neg A \vee (B \wedge \neg C) \) when \(A = \text{FALSE}\), \(B = \text{TRUE}\), and \(C = \text{FALSE}\).

3. Write a Boolean expression that is TRUE only when \(A\) is TRUE and \(B\) is FALSE.

4. (Conceptual) Explain in your own words why the AND operation is sometimes compared to multiplication and the OR operation to addition in Boolean Algebra. Are these comparisons perfectly accurate?

5. (Application) In digital circuits, AND and OR gates are fundamental. Consider a scenario where a light should turn ON if either switch 1 AND switch 2 are both ON, OR if switch 3 is ON. Let \(S_1\), \(S_2\), \(S_3\) be Boolean variables representing the state of switch 1, 2, 3 (TRUE=ON, FALSE=OFF) and \(L\) be a variable for the light (TRUE=ON, FALSE=OFF). Write a Boolean expression for \(L\) in terms of \(S_1\), \(S_2\), and \(S_3\).


6) Summary 🎉

  • Boolean Algebra deals with logical values: TRUE (1) and FALSE (0).
  • Boolean Variables can hold either TRUE or FALSE.
  • Basic Boolean Operations:
    • AND (\( \wedge \) or \( \cdot \)): TRUE only if both inputs are TRUE.
    • OR (\( \vee \) or \( + \)): TRUE if at least one input is TRUE.
    • NOT (\( \neg \) or \( \overline{} \)): Reverses the input value.
  • Truth Tables systematically define Boolean operations.
  • Boolean Expressions are formed using variables and operators, and can be evaluated to TRUE or FALSE.

Excellent start! You've now been introduced to the basics of Boolean Algebra, understanding its values, variables, and fundamental operations. In Part 2, we will delve deeper into Boolean Algebra, exploring Boolean Laws, simplification techniques, and more complex expressions. Keep practicing with truth tables and expression evaluation, and you'll build a strong foundation in this essential area of logic and computer science! 🌟

← Back to Previous Topic (Part 2 - Basic Matrices) Continue to Topic 14 (Boolean Algebra Part 2) → View Level 2 Topics Overview →