Boolean Logic

Boolean logic is a fundamental concept in computer science, used extensively in digital circuits and programming. It deals with logical operations on binary values (True/False or 1/0). This section covers how to translate problem statements, logic circuits, and truth tables into Boolean logic expressions.

Basic Boolean Operators

The main Boolean operators are:

• AND ($ \land $): The result is True only if both inputs are True.
• OR ($ \lor $): The result is True if at least one input is True.
• NOT ($ \neg$): Inverts the input. If the input is True, the output is False, and vice versa.

Translating Problem Statements into Boolean Expressions

Here's how to translate common phrases into Boolean expressions:

• "A and B" translates to $A \land B$
• "A or B" translates to $A \lor B$
• "Not A" translates to $ \neg A $
• "A if and only if B" translates to $A \iff B$ (exclusive or)

Example: If a student passes the exam (A) and scores above 50% (B), then they get a certificate. The Boolean expression is: $A \land B$

Translating Logic Circuits into Boolean Expressions

Logic circuits visually represent Boolean logic. To translate a circuit, trace the signal flow and identify the Boolean expressions corresponding to each gate.

Example: Consider a circuit with an AND gate connected to inputs A and B. The output of the AND gate is $A \land B$

Translating Truth Tables into Boolean Expressions

Truth tables show the output of a Boolean expression for all possible input combinations. You can construct a Boolean expression from a truth table using the following steps:

1. Identify the rows where the output is True.
2. For each row, determine the Boolean expression that results in True.
3. Combine these expressions using the appropriate logical operators (AND, OR, NOT).

Example: Consider the following truth table:

A	B	Output
0	0	0
0	1	1
1	0	1
1	1	1

The output is 1 when (A=0 and B=1) or (A=1 and B=0) or (A=1 and B=1). This can be represented as: $(\neg A \land B) \lor (A \land \neg B) \lor (A \land B)$

Practice

Problem: Write a Boolean expression for the statement: "The light is on if the switch is flipped and the power is on."

Solution: Let A represent the switch being flipped and P represent the power being on. The Boolean expression is: $A \land P$

Problem: Consider a logic circuit with two inputs, X and Y, connected to an OR gate, and the output of the OR gate connected to a NOT gate. Write a Boolean expression for the output.

Solution: The output of the OR gate is $X \lor Y$. The NOT gate inverts this, so the output is $ \neg (X \lor Y) $

Problem: Here's a truth table. Write a Boolean expression for it.

A	B	Output
0	0	0
0	1	1
1	0	0
1	1	0

Solution: The output is 1 when B=1 and A=0. This can be expressed as: $ \neg A \land B $