MAT 1348 Study Guide - Final Guide: Disjunctive Normal Form

• School: University of Ottawa
• Department: Mathematics
• Course: MAT 1348
• Professor: Guy Beaulieu

Document Summary

Recall: a proposition is said to be in disjunctive normal form (dnf) if it is a disjunction of conjunctive clauses, or is itself a con- junctive clause. In lecture 4 we found a dnf for a given compound proposition in two ways: using truth tables, using truth trees. When forming the truth tree we use the branching algorithm. The branching rules follow form the corresponding logical equivalences. Q p q p q p q (p q) ( p q) (p q) ( p q) p q p q p q p. (p q) (p q) ( p q) Examples: for each of the compound propositions construct a complete truth tree and use it to nd a dnf: ((p q) ( p r)) (q r) 3: ((p q) r) ( p q) Longer answer: using truth trees we can answer all these questions below. (remember we already used truth trees to nd a dnf for a given compound proposition. )