Chapter 12 对偶性 1. 模式对偶性的定义 如果一个模式的真值分析(或真值表),在将其中的T和F进行调换后,成了另一个模式的真值分析(或真值表),那么这两个模式便是对偶模式。 2. 关于对偶的五个定律 (1) 如果一个模式中没有“→”和“↔”,那么将其中的合取和析取互换,就得到这个模式的对偶式。 (2)如果把一个模式中的每个单字换成其否定式,并对结果进行否定,得到的将是其对偶式。 (3)一个模式是有效的,当且仅当该模式的对偶式是不一致的。 (4)模式P蕴含模式Q,当且仅当Q的对偶式蕴含P的对偶式。 (5)两个模式是等价的,当且仅当这两个模式的对偶式是等价的。 3. 标准合取模式和发达标准合取模式 指单字的析取的合取。这可视为标准析取模式的对偶定义。发达标准合取模式则是指符合下列条件的标准合取模式:(1)如果某个字母在模式中出现,它要出现在所有合取肢中。(2)没有有效的合取肢。(3)合取肢里没有相同的单字。(4)合取肢里各个单字按字母顺序排列。(5)没有相同的合取肢。这同样可视为发达标准析取模式的对偶定义。每个合取标准模式都可以转化为发达合取标准模式,在转化过程中,一般会涉及到将“p”置换以与之等价的“p∨q·p∨q1”这类的步骤。这个步骤仍可视为将析取标准模式转化为发达析取标准模式的有关步骤的对偶步骤。 标准析取模式的不一致性是一目了然的,它只剩下了“pp1”之类的式子。而标准合取模式的有效性则是一目了然的,它只剩下了“p∨p1”之类的式子。 Exercises
1. p↔q, p↔q1, p1↔q, —(p↔q) are dual to which? Justify. 【答案】 “p↔q”的对偶式是“—(p1↔q1)”,它只在“p”和“q”真值不同时为真,所以是与后面3个模式等价的。结论:“p↔q” 和后面的三个模式互为对偶式。【双条件句的对偶式是其否定式。】
2. p→q, q→p, —(p→q), —(q→p) 【答案】 “p→q”的对偶式是“—(p1→q1)”,与“—(q→p)”等价。同样地,“q→p”的对偶式是“—(p→q)”。因此,“p→q”和“—(q→p)”互为对偶式;“q→p”和“—(p→q)”互为对偶式。 3. We saw in Chapter 11 a test of redundancy for a clause or a literal of an alternational schema. What, by considerations of duality, should be the tests of redundancy for a clause or a literal of a conjunctional normal schema? 【答案】设标准合取模式S的一个合取肢为P,其他部分为Q。P可删除,即S和Q等价,当且仅当P为Q所蕴含。 设标准合取模式S的一个合取肢为P,其他部分为Q,P的一个单字为R,其他部分为T。R可删除,即S等价于T和Q的合取,当且仅当T为S所蕴含。 4. By successive transformations, transform each of the schemata of Exercise 1 of Chapter 10 into a conjunctional normal schema. Simplify where you can. 【答案】 —(p∨—{q∨—[r∨—(q∨p)]}) p1— —{q∨—[r∨—(q∨p)]} p1·q∨—[r∨—(q∨p)] p1·q∨r1——(q∨p) p1:q∨·r1·q∨p p1·q∨r1·q∨q∨p p1·q∨r1·q∨p…简化,删除合取肢中相同的单字。 p1·q∨p…简化,“q∨r1”为“p1·q∨p”所蕴含。 p1q…简化,“q”为“p1·q∨p”所蕴含,“q∨p”中的“p”可删除 p→q·q→r·→·p→r —(p→q·q→r)∨·p→r —(p→q) ∨—(q→r)∨·p→r pq1∨qr1∨p1∨r p∨qr1∨p1∨r·q1∨qr1∨p1∨r p∨q∨p1∨r·p∨r1∨p1∨r·q1∨q∨p1∨r ·q1∨r1∨p1∨r p∨p1 p→q·→p:↔p1 p→q·→p:p1:∨—(p→q·→p)p —(p→q) ∨p·p1·∨·p→q·p1p —(p→q) ∨p·p1 pq1∨p·p1 p∨p· q1∨p· p1 p· q1∨p· p1 pp1 p↔q·↔r —(p↔q·r1)—(—(p↔q)r) —(p↔q)∨r·(p↔q)∨r1 pq1∨p1q∨r·pq∨p1q1∨r1 p∨p1q∨r·q1∨p1q∨r·p∨p1q1∨r1·q∨p1q1∨r1 p∨p1∨r·p∨q∨r·q1∨p1∨r·q1∨q∨r·p∨p1∨r1·p∨q1∨r1·q∨p1∨r1·q∨q1∨r1 p∨q∨r·q1∨p1∨r·p∨q1∨r1·q∨p1∨r1 p↔q·q↔r pq∨p1q1·qr∨q1r1 p∨p1·p∨q1·q∨p1·q∨q1·q∨q1·q∨r1·r∨q1·r∨r1 p∨q1·q∨p1·q∨r1·r∨q1 p∨q1·q∨r1·r∨p1 (或者:p1∨q·q1∨r ·r1∨p) pq↔r —(pqr1)—(—(pq)r) p1∨q1∨r·pq∨r1 p1∨q1∨r·p∨r1·q∨r1 6. Expand the results of Exercise 4 into developed conjunctional normal form. p1q p1∨q·p1∨q1·q∨p·q∨p1 p1∨q∨r·p1∨q∨r1·p1∨q1∨r·p1∨q1∨r1·p∨q∨r·p∨q∨r1·p1∨q∨r·p1∨q∨r1 p1∨q∨r·p1∨q∨r1·p1∨q1∨r·p1∨q1∨r1·p∨q∨r·p∨q∨r1 p∨p1 (化为乌有) pp1 p∨q·p∨q1·p1∨q·p1∨q1 p∨q∨r·q1∨p1∨r·p∨q1∨r1·q∨p1∨r1 p∨q∨r·p1∨q1∨r·p∨q1∨r1·p1∨q∨r1 p∨q1·q∨p1·q∨r1·r∨q1 p∨q1∨r·p∨q1∨r1·p1∨q∨r·p1∨q∨r1·p∨q∨r1·p1∨q1∨r p1∨q1∨r·p∨r1·q∨r1 p1∨q1∨r·p∨q ∨r1·p∨q1 ∨r1·p∨q∨r1·p1∨q∨r1 p1∨q1∨r·p∨q ∨r1·p∨q1 ∨r1·p1∨q∨r1 6. Test the four schemata of Exercise 1 of Chapter 6 for validity by putting them into conjunctional normal form. p→q·∨·q→p, p↔q·∨·p↔q1, p→q·∨·q→p p1∨q∨q1∨p…有效 p∨qr∨·p1·q1∨r1 p∨qr∨p1 ·p∨qr∨q1∨r1 p∨qr∨q1∨r1 p∨q∨q1∨r1·p∨r∨q1∨r1…有效 p↔q·∨·p↔q1 pq∨p1q1∨pq1∨p1q p∨p1q1∨pq1∨p1q ·q∨p1q1∨pq1∨p1q p∨p1q1∨p1q ·q∨p1q1∨pq1 p∨p1∨p1q ·p∨q1∨p1q ·q∨p1∨pq1·q∨q1∨pq1 p∨q1∨p1q ·q∨p1∨pq1 p∨q1∨p1 ·p∨q1∨q ·q∨p1∨p·q∨p1∨q1…有效 p↔q·∨·q↔r·∨·p↔r pq∨p1q1∨qr∨q1r1∨pr∨p1r1 p∨p1q1∨qr∨q1r1∨pr∨p1r1· q∨p1q1∨qr∨q1r1∨pr∨p1r1 p∨p1q1∨qr∨q1r1∨p1r1· q∨p1q1∨q1r1∨pr∨p1r1 p∨p1∨qr∨q1r1∨p1r1·p∨q1∨qr∨q1r1∨p1r1·q∨p1∨q1r1∨pr∨p1r1·q∨q1∨q1r1∨pr∨p1r1 p∨q1∨q∨q1r1∨p1r1·p∨q1∨r∨q1r1∨p1r1·q∨p1∨q1∨pr∨p1r1·q∨p1∨r1∨pr∨p1r1 p∨q1∨r∨q1r1∨p1r1·q∨p1∨r1∨pr∨p1r1 p∨q1∨r∨p1r1·q∨p1∨r1∨pr p∨q1∨r∨p1·p∨q1∨r∨r1·q∨p1∨r1∨p·q∨p1∨r1∨r…有效 |
|