1.2 Propositional Equivalences

DEFINITION:

A compound proposition that is always true, no matters what the truth values of the propositional variable that occur in it, is called TAUTOLOGY. A compound proposition that is always false is CONTRADICTION neither is called CONTINGENCY.

LOGICAL EQUIVALENCES

Compound propositions that have the same truth values in all possible cases are called logically equivalences .

                                                     @

The compound propositions p and q are called logically equivalence if p↔q is a tautology. The notation p≡q denotes that p and q are logically equivalent.

REMARK : The sym ≡is not a logical connective and p ≡ q is not a compound proposition but rather is the statement that p↔q is a tautology. The symbol ó is used instead of ≡ to denote logical equivalent.

Example: Proof that p→q and ¬ p v q is logically equivalent.

p	q	¬p	p →q	¬p v q
T	T	F	T	T
T	F	F	F	F
F	T	T	T	T
F	F	T	T	T

LOGICAL EQUIVALENCES TABLES

LOGICAL EQUIVALENCES TABLES INVOLVING CONDITIONAL STATEMENTS

Example: Show that ¬ ( p v ( ¬ p ^q ) ) is logically equivalent to ¬ p ^ ¬q

                using the propositional theorems and identities.

¬ ( p v ( ¬ p ^q ) )        ≡   ¬ p ^ ¬( ¬ p ^q ) 

                               ≡   ¬ p ^ [¬( ¬ p) ^q ]

                                      ≡ ¬ p ^ [p ^q ]

                                      ≡   ( ¬ p ^ p) v ( ¬ p ^ ¬q ) 

                                      ≡  F v ( ¬ p ^ ¬q )

                                      ≡   ¬ p ^ ¬q

 

PROPOSTIONAL SATISFIABILITY

• A compound proposition is satisfiable if there is an assignment of truth values that makes it true .
• A compound proposition is unsatisfiable if and only if its negation is true for all assignments of truth values to the variable, that if and only if the negation is a tautology.

p/s: You can get the notes from this link ----〉1.2 Propositional Equivalences