🟰Algebraic Logic Unit 2 – Propositional Logic and Boolean Algebra

Key Concepts and Definitions

• Propositional logic deals with propositions, which are declarative sentences that can be either true or false
• Boolean algebra is a mathematical system that uses binary variables and logical operators to represent and manipulate logical expressions
• Logical operators include AND (conjunction), OR (disjunction), NOT (negation), implication, and equivalence
• Truth tables are used to evaluate the truth values of logical expressions for all possible combinations of input values
• Tautology is a logical expression that is always true regardless of the truth values of its variables
• Contradiction is a logical expression that is always false regardless of the truth values of its variables
• Contingency is a logical expression that can be either true or false depending on the truth values of its variables
  • Satisfiability refers to the existence of at least one set of truth values that makes a logical expression true
  • Validity refers to a logical expression being true for all possible truth value assignments

Propositional Logic Basics

• Propositions are represented by lowercase letters (p, q, r) and can be combined using logical operators to form compound propositions
• The truth value of a proposition is either true (T) or false (F)
• Compound propositions are formed by connecting simple propositions using logical operators
• The order of precedence for logical operators from highest to lowest is: NOT, AND, OR, implication, equivalence
• Parentheses can be used to override the default order of precedence and specify the desired order of evaluation
• The truth value of a compound proposition depends on the truth values of its constituent propositions and the logical operators used
  • De Morgan's laws describe the relationship between negation, conjunction, and disjunction: $\neg(p \wedge q) \equiv \neg p \vee \neg q$ and $\neg(p \vee q) \equiv \neg p \wedge \neg q$
• The principle of bivalence states that every proposition is either true or false, with no other possible truth values

Boolean Algebra Fundamentals

• Boolean algebra is a mathematical system based on the values true (1) and false (0) and the operations AND, OR, and NOT
• Boolean expressions can be represented using algebraic notation, with variables and operators
• The AND operation is represented by multiplication or the symbol $\wedge$, the OR operation by addition or the symbol $\vee$, and the NOT operation by a bar or the symbol $\neg$
• Boolean algebra satisfies the commutative, associative, and distributive laws
  • Commutative laws: $p \wedge q \equiv q \wedge p$ and $p \vee q \equiv q \vee p$
  • Associative laws: $(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$ and $(p \vee q) \vee r \equiv p \vee (q \vee r)$
  • Distributive laws: $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$ and $p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$
• Identity elements for AND and OR operations are 1 and 0, respectively: $p \wedge 1 \equiv p$ and $p \vee 0 \equiv p$
• Complement laws: $p \wedge \neg p \equiv 0$ and $p \vee \neg p \equiv 1$
• Idempotent laws: $p \wedge p \equiv p$ and $p \vee p \equiv p$

Logical Operators and Truth Tables

• The AND operator ($\wedge$) returns true if both operands are true, otherwise false
• The OR operator ($\vee$) returns true if at least one operand is true, otherwise false
• The NOT operator ($\neg$) negates the truth value of its operand
• The implication operator ($\rightarrow$) represents a conditional statement, where if the antecedent is true, the consequent must also be true for the implication to be true
• The equivalence operator ($\leftrightarrow$) represents a biconditional statement, where both propositions must have the same truth value for the equivalence to be true
• Truth tables list all possible combinations of truth values for the variables and the corresponding truth value of the logical expression
  • The number of rows in a truth table is $2^n$, where $n$ is the number of variables
• Constructing truth tables helps determine the properties of logical expressions, such as tautology, contradiction, and contingency

Simplification and Equivalence

• Logical expressions can be simplified using Boolean algebra laws and rules to obtain equivalent expressions
• Two logical expressions are equivalent if they have the same truth table or can be transformed into each other using Boolean algebra laws
• Simplification involves applying Boolean algebra laws to reduce the complexity of logical expressions
  • Examples of simplification rules: $p \wedge 1 \equiv p$, $p \vee 0 \equiv p$, $p \wedge \neg p \equiv 0$, $p \vee \neg p \equiv 1$
• The duality principle states that for any Boolean algebra law, replacing AND with OR, OR with AND, 1 with 0, and 0 with 1 results in another valid law
• Karnaugh maps (K-maps) are graphical tools used to simplify logical expressions by grouping together adjacent cells with the same output value
• Consensus theorem: $(p \wedge q) \vee (\neg p \wedge r) \vee (q \wedge r) \equiv (p \wedge q) \vee (\neg p \wedge r)$
• Absorption laws: $p \vee (p \wedge q) \equiv p$ and $p \wedge (p \vee q) \equiv p$

Proof Techniques and Methods

• Direct proof involves assuming the premises are true and using logical reasoning to derive the conclusion
• Proof by contradiction (reductio ad absurdum) assumes the negation of the conclusion and shows that it leads to a contradiction with the premises or known facts
• Proof by cases considers all possible cases for the variables and proves the statement holds for each case
• Proof by induction proves a statement for a base case and then shows that if it holds for a specific case, it also holds for the next case
  • Mathematical induction has two steps: the base case and the inductive step
• Proof by equivalence demonstrates that two logical expressions are equivalent by transforming one into the other using Boolean algebra laws
• Proof by counterexample disproves a statement by finding a specific instance where the statement does not hold
• Proof by exhaustion verifies a statement by checking all possible cases (suitable for small, finite sets of cases)
• Proof by construction provides an explicit example or procedure that satisfies the statement

Applications in Computer Science

• Propositional logic and Boolean algebra form the foundation for digital circuit design and computer architecture
• Logical gates (AND, OR, NOT) are the building blocks of digital circuits and implement Boolean functions
• Simplification of Boolean expressions is crucial for optimizing digital circuits and minimizing hardware complexity
  • Karnaugh maps and Boolean algebra are used to minimize the number of gates and interconnections in digital circuits
• In programming languages, logical operators (&&, ||, !) are used to evaluate conditions and control the flow of execution
• Propositional logic is used in artificial intelligence and knowledge representation to model and reason about facts and rules
• Search algorithms and optimization techniques often rely on propositional logic to represent constraints and objectives
• Formal verification techniques, such as model checking and theorem proving, use propositional logic to verify the correctness of hardware and software systems
• In databases, propositional logic is used to express queries and conditions for retrieving and manipulating data

Practice Problems and Examples

1. Simplify the following Boolean expression: $(p \wedge q) \vee (\neg p \wedge q) \vee (p \wedge \neg q)$
2. Construct a truth table for the logical expression: $(p \rightarrow q) \wedge (\neg q \rightarrow \neg p)$
3. Prove or disprove the following statement using a truth table: $(p \rightarrow q) \rightarrow (\neg q \rightarrow \neg p)$ is a tautology
4. Simplify the Boolean expression using Boolean algebra laws: $(\neg p \vee q) \wedge (p \vee \neg q)$
5. Given the Boolean function $F(x, y, z) = (x \wedge y) \vee (\neg x \wedge z)$, construct a digital circuit using logical gates
6. Prove the equivalence of the following logical expressions using Boolean algebra: $p \rightarrow q$ and $\neg p \vee q$
7. Simplify the Boolean expression using a Karnaugh map: $F(w, x, y, z) = \sum(1, 3, 5, 7, 8, 9, 11, 12, 13, 15)$
8. Express the following statement in propositional logic: "If it is raining, then I will take an umbrella, and if it is not raining, then I will wear sunglasses."