Disjunctive Normal Form - ia Tech：析取范式-佐治亚理工学院.ppt

Logical Operators ? - Disjunction ? - Conjunction ?- Negation ?- Implication p?q ??p ? q ?- Exclusive or (p ?? q) ?(?p ? q) ?- Biconditional p ? q ? (p ? q) ?(q? p) ? ( ?p ? q) ?(?q ? p) Do we need all these? plete ? A set of logical operators is called plete if pound proposition is logically equivalent to a compound proposition involving only this set of logical operators. ??, ?, and ? form a plete set of operators. Are ?(p?(?p? q)) and ( ?p ?? q) equivalent? ?(p?(?p? q)) ??p ??(?p?q) an ??p ?( ?? p ?? q) an ??p ? (p ?? q) Double Negation ?(?p?p)?(?p ?? q) Distribution ?(p ?? p)?(?p ?? q) Commutative ? F ?(?p ?? q) And Contradiction ?(?p ?? q) ? F Commutative ?(?p ?? q) Identity Are ?(p?(?p? q)) and ( ?p ?? q) equivalent? ? Even though both are expressed with only ?, ?, and ?, it is still hard to tell without doing a proof. ? What we need is a unique representation of pound proposition that uses ?, ?, and ?.? This unique representation is called the Disjunctive Normal Form. Disjunctive Normal Form ? A disjunction of conjunctions where every variable or its negation is represented once in each conjunction ( a minterm ) – each minterm appears only once Example: DNF of p ? q is (p??q)?(?p? q). pqp?q (p ?? q) ?(?p?q) TTFFTFTTFTTTFFFF Truth Table Method to construct DNF ? Construct a truth table for the proposition. ? Use the rows of the truth table where the proposition is True to construct minterms – If the variable is true, use the propositional variable in the minterm – If a variable is false, use the negation of the variable in the minterm ? Connect the minterms with ?’ s. How to find the DNF of ( p ??q)??r pq r (p ??q)?r (p ??q)??r TTTTFF TTFTTT TFTTFF TFFTTT FTTTFF FTFTTT FFTFFT FFFFTT There are five sets of input that make the statement true. Therefore there are five minterms. pq r (p ??q)?r (p ??q)??r TTTTFF TTFTTT TFTTFF TFFTTT FTTTFF FTFTTT FFTFFT FFFFTT From the truth