4.1 Logical Equivalence and Laws of Propositional Logic

Logical equivalence is a key concept in propositional logic. It helps us understand when two statements have the same truth value, no matter what values their components have. This idea is crucial for simplifying complex logical expressions.

The laws of propositional logic give us tools to manipulate and simplify logical statements. These laws, like De Morgan's laws and the distributive law, allow us to transform expressions while keeping their meaning intact. They're essential for solving logical puzzles and proofs.

Logical Equivalence

Properties of logical equivalence

Top images from around the web for Properties of logical equivalence

• 

  Truth Tables – Critical Thinking View original

  Is this image relevant?

• 

  Propositional Logic Proof using I.P. or C.P or rules of inference - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Truth Tables – Critical Thinking View original

  Is this image relevant?

• 

  Propositional Logic Proof using I.P. or C.P or rules of inference - Mathematics Stack Exchange View original

  Is this image relevant?

1 of 2

Top images from around the web for Properties of logical equivalence

• 

  Truth Tables – Critical Thinking View original

  Is this image relevant?

• 

  Propositional Logic Proof using I.P. or C.P or rules of inference - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Truth Tables – Critical Thinking View original

  Is this image relevant?

• 

  Propositional Logic Proof using I.P. or C.P or rules of inference - Mathematics Stack Exchange View original

  Is this image relevant?

1 of 2

• Logical equivalence is a relationship between two propositions or propositional statements where they have the same truth value for all possible truth value assignments of their component variables
• Reflexive property states that every proposition is logically equivalent to itself ($p \equiv p$)
• Symmetric property asserts that if $p$ is logically equivalent to $q$, then $q$ is also logically equivalent to $p$ ($p \equiv q \implies q \equiv p$)
• Transitive property indicates that if $p$ is logically equivalent to $q$, and $q$ is logically equivalent to $r$, then $p$ is logically equivalent to $r$ ($p \equiv q$ and $q \equiv r \implies p \equiv r$)

Equivalence of propositional statements

• Determine if two propositional statements are logically equivalent by creating a truth table that includes all possible truth value assignments for the component variables
• If the truth values of the two statements are the same for all rows in the truth table, the statements are logically equivalent
• Use the laws of propositional logic to transform one statement into the other and if the transformation is successful, the statements are logically equivalent

Laws of Propositional Logic

Application of De Morgan's laws

• De Morgan's laws negate compound propositions involving the conjunction ($\land$) and disjunction ($\lor$) connectives
• First law states that the negation of a conjunction is equivalent to the disjunction of the negations ($\neg (p \land q) \equiv \neg p \lor \neg q$)
• Second law asserts that the negation of a disjunction is equivalent to the conjunction of the negations ($\neg (p \lor q) \equiv \neg p \land \neg q$)
• Apply De Morgan's laws by negating the entire compound proposition, changing the main connective ($\land$ becomes $\lor$, $\lor$ becomes $\land$), and negating each individual proposition within the compound proposition

Simplification of propositional statements

• Identity laws simplify statements involving true ($T$) and the proposition ($p$) itself ($p \land T \equiv p$) or false ($F$) and the proposition ($p$) itself ($p \lor F \equiv p$)
• Domination laws simplify statements involving true ($T$) and any proposition ($p$) ($p \lor T \equiv T$) or false ($F$) and any proposition ($p$) ($p \land F \equiv F$)
• Idempotent laws simplify statements where a proposition is combined with itself using conjunction ($p \land p \equiv p$) or disjunction ($p \lor p \equiv p$)
• Double negation law removes double negations ($\neg (\neg p) \equiv p$)
• Commutative laws allow swapping the order of propositions in a conjunction ($p \land q \equiv q \land p$) or disjunction ($p \lor q \equiv q \lor p$)
• Associative laws allow regrouping of propositions in a conjunction ($(p \land q) \land r \equiv p \land (q \land r)$) or disjunction ($(p \lor q) \lor r \equiv p \lor (q \lor r)$)
• Distributive laws expand a proposition over a conjunction ($p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$) or disjunction ($p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$)
• Absorption laws simplify statements where a proposition is combined with a conjunction ($p \land (p \lor q) \equiv p$) or disjunction ($p \lor (p \land q) \equiv p$) involving itself and another proposition
• Simplify a propositional statement by applying the appropriate laws until the statement cannot be further simplified