北京邮电大学 计算机学院 离散数学 1.3- Propositional equivalences.ppt

* * * * * * College of Computer Science Technology, BUPT 等值演算（举例） 例：(p∧q)→r??p∨?q∨r 解： (p∧q)→r ? ?(p∧q)∨r （蕴涵等值式） ? (?p∨?q)∨r （德●摩根律） ? ?p∨?q∨r （结合律） * * College of Computer Science Technology, BUPT Proof: A?(B?C) ?(A ? B) ? C * * College of Computer Science Technology, BUPT Proof: (~A ?(~B ? C)) ?(B ? C) ?(A ? C) ? C * * College of Computer Science Technology, BUPT Proof: (p ? ?q) ? (p ? r) ? ?p ? q ? ?r. * * College of Computer Science Technology, BUPT Using De Morgan’s Laws Example 5 Use De Morgan’s laws to Express the negations of “Miguel has a cellphone and he has a laptop computer” and “Heather will go to the concert or Steve will go to the concert.” * * College of Computer Science Technology, BUPT Example 8 Show that is a tautology. (p ? q) ? (p ? q) Propositional Satisfiability A compound proposition is satisfiable if there is an assignment of truth values to its variables that makes it true. When no such assignments exists, that is, when the compound proposition is false for all assignments of truth values to its variables, the compound proposition is unsatisfiable. * * College of Computer Science Technology, BUPT EXAMPLE 9 Determine whether each of the compound propositions (p ∨￢q) ∧ (q ∨￢r) ∧(r ∨￢p), (p ∨ q ∨ r) ∧ (￢p ∨￢q ∨￢r), and (p ∨￢q) ∧ (q ∨￢r) ∧ (r ∨￢p) ∧(p ∨ q ∨ r) ∧ (￢p ∨￢q ∨￢r) is satisfiable. * * College of Computer Science Technology, BUPT Applications of Satisfiability * * College of Computer Science Technology, BUPT * * College of Computer Science Technology, BUPT 简单析取式和简单合取式 仅有有限个命题变元或其否定的析取构成的析取式称为简单析取式，或基本和。 例如：~P?Q?R，~P?~Q?P是简单析取式 而仅有有限个命题变元或其否定的合取构成的合取式称为简单合取式，或基本积。 例如：~P?R，Q?R?~Q是简单合取式。 P，~Q一个变项本身可以看作简单析取式也可以看作简单合取式。 而~P?（Q ? R），（P?Q）?~R不是简单析取式。 * * College of Computer Science Technology, BUPT 析取范式(disjunctive normal form) 析取范式：由有限个简单合取式（基本积）的析取构成的析取式称为析取范式。 例 P?（P?Q）?（~P?~Q?~R）是析取范式 P?Q?R是析取范式，是三个简单合取范式的析取 * * College of Computer Science