Discrete Structures: Propositional Logic

Propositional Logic

• Propositional logic, also known as Boolean logic, deals with statements that can be true or false.
• Examples of propositions: "A football is spherical in shape", "3 + 9 = 24", "Miva is an open university".

Logical Operators

• Negation: NOT (¬)
• Conjunction: AND (∧)
• Disjunction: OR (∨)
• Implication: IF-THEN (→)
• Biconditional: IF-AND-ONLY-IF (⇔)

Truth Tables

• A truth table indicates the true/false value of a proposition for each possible set of truth values for the variables.
• Example: constructing a truth table for a compound proposition involving logical operators.

Java Logical Expressions

• Java logical expressions are used to control program flow and make decisions based on conditions.
• Java provides several operators for creating and evaluating logical expressions:
  • Logical AND (&&)
  • Logical OR (||)
  • Logical NOT (!)
  • Logical XOR (^)
• Short-circuit evaluation: Java evaluates the second operand only if necessary.

Truth Assignments

• A truth assignment assigns a true (T) or false (F) value to each propositional variable.
• Example: evaluating the truth value of a propositional formula in a given environment.

Equivalence

• Two propositional formulas are equivalent if and only if they yield the same truth value across all possible environments.
• Examples of equivalent formulas:
  • Double Negation: P ≡ ¬¬P
  • De Morgan's Laws: ¬(P∧Q) ≡ ¬P∨¬Q, ¬(P∨Q) ≡ ¬P∧¬Q
  • Contrapositive: p → q ≡ ¬q → ¬p
  • Idempotent Laws: P∨P ≡ P, P∧P ≡ P
  • Material Implication: p → q ≡ ¬p ∨ q
  • Absorption Laws: p ∨ (p ∧ q) ≡ p, p ∧ (p ∨ q) ≡ p
  • Distributive Laws: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r), p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

Example Problems

• Example 2: Show that ¬(p ∨ q) and ¬p ∧ ¬q are logically equivalent.
• Example 3: Show that p → q and ¬p ∨ q are logically equivalent.
• Example 4: Show that ¬(p ∨ (¬p ∧ q)) and ¬p ∧ ¬q are logically equivalent by developing a series of logical equivalences.

Propositional Satisfiability

• A compound proposition is satisfiable if there exists an assignment of truth values to its variables that renders it true.
• A compound proposition is unsatisfiable if it is false for all assignments of truth values to its variables.
• Example 5: Determine whether each of the compound propositions is satisfiable.

Summary

• Propositional logic deals with statements that can be true or false.
• Logical operators are used to construct compound propositions.
• Truth tables are used to determine the truth values of propositions for all possible combinations of truth values for the variables.
• Java logical expressions are used to control program flow and make decisions based on conditions.
• Equivalent formulas yield the same truth value across all possible environments.
• Satisfiable formulas have at least one assignment of truth values that render them true.