16.1 等值式
本章目录 · 1 节
本章导读
【16.1 等值式】两个公式A、B在共同变量集的每个赋值下真值相同,称逻辑等值。本章保留原书元语言记号A⇔B;公式内部的↔是二元联结词,A⇔B等价于“A↔B为重言式”。不能将单次赋值下的同真,或单向A→B,直接当成逻辑等值。
【定义16.1.1】A⇔B由全部赋值决定;不等值记A⇎B。比较时将缺少的变量补作哑元。等值具有自反、对称、传递性。
【例16.1.1】¬(p∨q)与¬p∧¬q等值。表中A=¬(p∨q),B=¬p∧¬q,最后A↔B恒为1。
【例16.1.2】F₁=p→(q→r),F₂=(p∧q)→r,F₃=(p→q)→r。
F₁⇔F₂,都化为¬p∨¬q∨r;F₃化为(p∧¬q)∨r,在000或010时为0而前两者为1,因此F₃不与它们等值。(例完)
【统一代入】重言式中每个变项的所有出现同时用同一个任意公式代替,仍为重言式。因为新公式在任意赋值下先算出替入公式的值,再代回原重言式,结果仍为1。相同变项不能有时替成A、有时替成B;代入公式也须适当加括号。
【16组基本等值式模式】以下A、B、C均代表任意公式。
(16.1.1)双重否定:A⇔¬¬A。
(16.1.2)幂等:A∨A⇔A,A∧A⇔A。
(16.1.3)交换:A∨B⇔B∨A,A∧B⇔B∧A。
(16.1.4)结合:(A∨B)∨C⇔A∨(B∨C),(A∧B)∧C⇔A∧(B∧C)。
(16.1.5)分配:A∨(B∧C)⇔(A∨B)∧(A∨C),A∧(B∨C)⇔(A∧B)∨(A∧C)。
(16.1.6)德摩根:¬(A∨B)⇔¬A∧¬B,¬(A∧B)⇔¬A∨¬B。
(16.1.7)吸收:A∨(A∧B)⇔A,A∧(A∨B)⇔A。
(16.1.8)零律:A∨1⇔1,A∧0⇔0。
(16.1.9)同一律:A∨0⇔A,A∧1⇔A。
(16.1.10)排中:A∨¬A⇔1。
(16.1.11)矛盾:A∧¬A⇔0。
(16.1.12)蕴涵:A→B⇔¬A∨B。
(16.1.13)等价:A↔B⇔(A→B)∧(B→A)。
(16.1.14)假言易位:A→B⇔¬B→¬A。
(16.1.15)等价否定:(A↔B)⇔(¬A↔¬B)。
(16.1.16)归谬形式:(A→B)∧(A→¬B)⇔¬A。
以上共24个具体等值式;⇔用于断言等值,不参与对象公式的运算优先级。尤其不要把第(16.1.15)右边错录成只有一个否定。
【置换规则】若A⇔B,在任一公式语境Φ中,将选定的A子公式出现替成B,可得等值公式。可以替全部出现,也可以只替选定的一次;须替换完整子公式而非任意字符串片段。此规则与统一替换变项的“代入”不同。
例如(p→q)→r⇔(¬p∨q)→r⇔¬(¬p∨q)∨r⇔(p∧¬q)∨r⇔(p∨r)∧(¬q∨r)。各步依次用蕴涵式、蕴涵式、德摩根、分配,置换规则在每步隐含使用。
【例16.1.3】证明(p∨q)→r⇔(p→r)∧(q→r)。右边⇔(¬p∨r)∧(¬q∨r)⇔(¬p∧¬q)∨r⇔¬(p∨q)∨r⇔左边。这里公共后件r不代表蕴涵一般满足结合律。(例完)
【例16.1.4】(p→q)→r与p→(q→r)不等值,用000或010即可反驳。可先分别化简再找反例,也可直接列真值表。单纯演算到两个外观不同的式子不能证明不等值,因为它们仍可能是另一个等值式。(例完)
【例16.1.5】(1)((p→q)∧p)→q⇔¬((¬p∨q)∧p)∨q⇔¬(p∧q)∨q⇔¬p∨¬q∨q⇔1,重言式。
(2)¬(p→(p∨q))∧r⇔¬(¬p∨p∨q)∧r⇔0,矛盾式。
(3)p∧(((p∨q)∧¬p)→q)中,内层前件⇔q∧¬p,故其蕴涵⇔¬q∨p∨q⇔1,整式⇔p。它是偶然式,按pq赋值00、01为假,10、11为真;化简后仍按共同变量保留q这个哑元。(例完)
【例16.1.6 口音判断】设p:王教授是苏州人,q:是上海人,r:是杭州人。甲断言¬p及q;乙断言p及¬q;丙断言¬q及¬r。每人两句话,教授说三人中一人全对、一人对一半、一人全错。
分别记甲全对B₁=¬p∧q,半对B₂=(¬p∧¬q)∨(p∧q),全错B₃=p∧¬q;乙全对C₁=p∧¬q,半对C₂=(p∧q)∨(¬p∧¬q),全错C₃=¬p∧q;丙全对D₁=¬q∧¬r,半对D₂=(¬q∧r)∨(q∧¬r),全错D₃=q∧r。
将“全对、半对、全错”分配给三人的六种排列作析取:E=(B₁∧C₂∧D₃)∨(B₁∧C₃∧D₂)∨(B₂∧C₁∧D₃)∨(B₂∧C₃∧D₁)∨(B₃∧C₁∧D₂)∨(B₃∧C₂∧D₁)。展开后仅两项不为0,得E⇔(¬p∧q∧¬r)∨(p∧¬q∧r)。
在题目将籍贯理解为单一城市的背景下,不允许p、r同时真,排除第二项,故p=0,q=1,r=0:教授为上海人,甲全对、乙全错、丙半对。互斥是题设语义约束,不是三个任意命题变项自动具有的性质;若不加该约束,第二个形式赋值101也满足E,不能略去。(例完)
