This chapter presents logical equivalences, De Morgan’s laws, tautologies and contradictions, laws of logic, conditional propositions. In this lecture, the following topics will be covered: Mathematical review; asymptotic and algorithm analysis; relationships and data structures; requential storage: Lists, queues, stacks, deques; hash tables; trees; priority queues and heaps; sort algorithms; graphs and graph algorithms; algorithm design techniques; complexity classes and NP completeness. | (CSC 102) Lecture 2 Discrete Structures Previous Lecture Summery Introduction to the Course Propositions Logical Connectives Truth Tables Compound propositions Translating English to logic and logic to English. Today’s Lecture Logical Equivalences. De Morgan’s laws. Tautologies and Contradictions. Laws of Logic. Conditional propositions. Logical Equivalence Definition Two proposition form are called logically equivalent if and only if they have identical truth values for each possible substitution of propositions for their proposition variable. The logical equivalence of proposition forms P and Q is written P ≡ Q Construct the truth table for P. Construct the truth table for Q using the same proposition variables for identical component propositions. Check each combination of truth values of the proposition variables to see whether the truth value of P is the same as the truth value of Q. Equivalence of Two Compound Propositions P and Q If in each row the truth value of P is the same as the truth value of Q, then P and Q are logically equivalent. If in some row P has a different truth value from Q, then P and Q are not logically equivalent. Equivalence Check Example Prove that ¬ (¬p)≡ p Solution As you can see the corresponding truth values of p and ¬ (¬p) are same, hence equivalence is justified. p ¬p ¬ (¬p) T F T F T F Example Show that the proposition forms ¬(p q) and ¬p ¬q are NOT logically equivalent. Here the corresponding truth values differ and hence equivalence does not hold p q ¬p ¬q (p q) ¬(p q) ¬p ¬q T T F F T F F T F F T F T F F T T F F T F F F T T F T T De Morgan’s laws De Morgan’s laws state that: The negation of an and proposition is logically equivalent to the or proposition in which each component is negated. The negation of an or proposition is logically equivalent to the and proposition in which each component is negated. Symbolically (De Morgan’s Laws) ¬(p q) ≡ ¬p ¬q ¬(p q) ≡ ¬p ¬q Applying De-Morgan’s Law Question: Negate the following . | (CSC 102) Lecture 2 Discrete Structures Previous Lecture Summery Introduction to the Course Propositions Logical Connectives Truth Tables Compound propositions Translating English to logic and logic to English. Today’s Lecture Logical Equivalences. De Morgan’s laws. Tautologies and Contradictions. Laws of Logic. Conditional propositions. Logical Equivalence Definition Two proposition form are called logically equivalent if and only if they have identical truth values for each possible substitution of propositions for their proposition variable. The logical equivalence of proposition forms P and Q is written P ≡ Q Construct the truth table for P. Construct the truth table for Q using the same proposition variables for identical component propositions. Check each combination of truth values of the proposition variables to see whether the truth value of P is the same as the truth value of Q. Equivalence of Two Compound Propositions P and Q If in each row the truth value of P is the same
