Logical Statements & Propositional Logic Expressions (Discrete Structures) PDF

Discrete Structures Logical Statements & Propositional Logic Expressions  Discrete Structures LEARNING OBJECTIVES At the end of this lesson, you should be able to: Identify and dierentiate between the logical operators in propositional logic, including negation, conjunction, disjunct...

Discrete Structures Logical Statements & Propositional Logic Expressions  Discrete Structures LEARNING OBJECTIVES At the end of this lesson, you should be able to: Identify and dierentiate between the logical operators in propositional logic, including negation, conjunction, disjunction, implication, and biconditional. Construct truth tables for compound propositions involving logical operators, such as OR and AND, to determine their truth values for all possible combinations of truth values for the variables. Apply Java logical operators (&&, ||, !) to create and evaluate logical expressions, understanding their behavior with boolean values. Explain the concepts of satisfiability and unsatisfiability in propositional logic, including how to determine if a compound proposition is satisfiable or unsatisfiable.  Discrete Structures Propositional (Boolean) Logic Propositional logic, also known as Boolean logic, is a fundamental branch of formal logic that deals with propositions, or statements, that can be either true or false. Examples: A football is spherical in shape. 3 + 9 = 24 Miva is an open university.  Discrete Structures Operators in Propositional Logic  Discrete Structures Truth Table A truth table indicates the true/false value of a proposition for each possible set of truth values for the variables. For example:  Discrete Structures Truth Table (Contd.)  Discrete Structures Java Logical Expressions In Java programming, logical expressions are essential for controlling the flow of execution within programs and making decisions based on conditions. These expressions typically involve boolean values, which can be either true or false. Java provides several operators for creating and evaluating logical expressions:  Discrete Structures Java Logical Expressions (Contd.) Logical AND (&&): The logical AND operator returns true if both operands are true; otherwise, it returns false. For example:  Discrete Structures Java Logical Expressions (Contd.) Logical OR (||): The logical OR operator returns true if at least one of the operands is true; otherwise, it returns false. For example:  Discrete Structures Java Logical Expressions (Contd.) Logical NOT (!): The logical NOT operator negates the value of its operand. If the operand is true, the result is false, and vice versa. For example:  Discrete Structures Java Logical Expressions (Contd.) Short-Circuit Evaluation: Java also supports short-circuit evaluation for logical AND (&&) and logical OR (||) operators. Short-circuit evaluation means that the second operand is evaluated only if necessary. For example:  Discrete Structures Java Logical Expressions (Contd.) Logical XOR (^): The logical XOR (exclusive OR) operator returns true if one operand is true and the other is false; otherwise, it returns false. For example: Logical expressions are commonly used in conditional statements (if-else), loop control (while, do-while, for),  Discrete Structures Java Logical Expressions (Contd.) And boolean expressions in Java programs to control program flow and make decisions based on conditions.  Discrete Structures Truth Assignments In logic, a truth assignment assigns either a true (T) or false (F) value to each propositional variable. Within computer science, this assignment of values to variables is termed an "environment." With knowledge of the environment, we can determine the value of a propositional formula.  Discrete Structures Evaluation in an Environment Example: Suppose environment, v, assigns v(P) = T, v(Q)= T, v(R) = F. What is the Truth value of (NOT(P AND Q) ) OR (R XOR NOT(Q))? v(P) v(Q) v(R) T T F F T F F F  Discrete Structures Equivalence Two propositional formulas are considered equivalent if and only if they yield the same truth value across all possible environments. Some examples of equivalent formulas include: 1. Double Negation: P is equivalent to ¬¬P 2. De Morgan’s Laws: ¬(P∧Q) is equivalent to ¬P∨¬Q ¬(P∨Q) is equivalent to ¬P∧¬Q  Discrete Structures Equivalence 3. Contrapositive: p → q is equivalent to ¬q → ¬p 4. Idempotent Laws: P∨P is equivalent to P P∧P is equivalent to P 5. Material Implication: p → q) is equivalent to ¬p ∨ q  Equivalent Formulas (Contd.) Discrete Structures Equivalent Formulas (Contd.) 6. Absorption Laws: p ∨ (p ∧ q)is equivalent to p p ∧ (p ∨ q) is equivalent to p 7. Distributive Laws: p ∧ (q ∨ r) is equivalent to (p ∧ q) ∨ (p ∧ r) p ∨ (q ∧ r) is equivalent to (p ∨ q) ∧ (p ∨ r)  Discrete Structures Example 2 Show that ¬(p ∨ q) and ¬p ∧ ¬q are logically equivalent.  Discrete Structures Solution p q p∨q ¬(p ∨ q) ¬p ¬q ¬p ∧ ¬q T T T F F F F T F T F F T F F T T F T F F F F F T T T T  Discrete Structures Example 3 Show that p → q and ¬p ∨ q are logically equivalent.  Discrete Structures Solution p q ¬p ¬p∨q T T F T T T F F F F F T T T T F F T T T  Discrete Structures Example 4 Show that ¬(p ∨ (¬p ∧ q)) and ¬p ∧ ¬q are logically equivalent by developing a series of logical equivalences.  Discrete Structures Solution ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬(¬p ∧ q) by the second De Morgan law ≡ ¬p ∧ [¬(¬p) ∨ ¬q] by the first De Morgan law ≡ ¬p ∧ (p ∨ ¬q) by the double negation law ≡ (¬p ∧ p) ∨ (¬p ∧ ¬q) by the second distributive law ≡ F ∨ (¬p ∧ ¬q) because ¬p ∧ p ≡ F ≡ (¬p ∧ ¬q) ∨ F by the commutative law for disjunction ≡ ¬p ∧ ¬q by the identity law for F Consequently ¬(p ∨ (¬p ∧ q)) and ¬p ∧ ¬q are logically equivalent.  Discrete Structures Propositional Satisfiability A compound proposition is satisfiable when there exists an assignment of truth values to its variables that renders it true. Conversely, a compound proposition is unsatisfiable when it is false for all assignments of truth values to its variables. A compound proposition is unsatisfiable if and only if its negation is true for all assignments of truth values to the variables, meaning its negation is a tautology. When we discover a specific assignment of truth values that results in a compound proposition being true, we have demonstrated its satisfiability. Such an assignment is referred to as a solution to this particular satisfiability problem.  Discrete Structures Example 5 Determine whether each of the compound propositions a) (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p), b) (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r), and c) (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) ∧ (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r) is satisfiable.  Discrete Structures Solution a) (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p): Satisfiable b) (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r): Satisfiable c) (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) ∧ (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r): Unsatisfiable  Discrete Structures Summary In this lecture, we cover the following concepts: Propositional logic, or Boolean logic, deals with statements that can be true or false. Logical operators like negation, conjunction, disjunction, implication, and biconditional 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. In Java programming, logical expressions are crucial for controlling program flow based on conditions, using operators like &&, ||, and !. Equivalent formulas yield the same truth value across all possible environments, while satisfiable formulas have at least one assignment of truth values that render them true.  Discrete Structures REFERENCES & FURTHER READING Kenneth H. Rosen (2012). Discrete Mathematics and Its Applications. United States: McGraw-Hill. Handbook of Discrete Mathematics and Its Applications by Rosen. United States: McGraw-Hill. hp://www-history.mcs.st-and.ac.uk/ Discrete Structures Thank You