逻导复习资料.doc

第一章命题逻辑 1. 命题表示判断的有确定真值的陈述句为命题。陈述句可能是命题,但是要有确定的真值。北京是大城市, 为命题, 并且是真命题。雪是黑色的, 是命题, 为假命题。您上网了吗? 不是命题。向右看齐!不是命题。火星上有生命,虽然暂时确定不了真值,但它是命题。 35??x ,不是命题,因为真值不确定。 2. 联结词熟悉九个联结词的定义和联结词的优先顺序, n 个命题变项可能的真值指派为 n2 种, 不要以为 n 是几都只有 4 种真值指派, 会作各种命题公式的真值表, 作真值表要熟悉联结词的定义; ⑴否定┐性质: ┐┐ P? P (2) 合取∧性质:P∧P? PP∧Q? Q∧P (P∧ Q)∧R? P∧(Q∧ R) P∧T? PP∧F? FP ∧┐ P? F⑶析取∨性质:P∨P? PP∨Q? Q∨P(P∨Q)∨R? P∨(Q∨R) P∨F? PP∨T? TP ∨┐ P? TP∨(Q∧ R)?(P∨ Q)∧(P∨ R) P∧(Q∨ R)?(P∧ Q)∨(P∧ R) P∨(P∧ Q)? PP∧(P∨ Q)? P┐(P∨ Q)?┐P ∧┐ Q┐(P∧ Q)?┐P ∨┐ Q (4) 条件→性质:P→Q?┐Q →┐ PP→Q?┐P∨Q┐(P→ Q)? P ∧┐ QP→P? TP→F?┐P P→T? TP →┐ P?┐P┐P→P? PF→P? TT→P? P (5) 双条件?性质:P? Q? Q? P (P? Q)? R? P?(Q? R) P? P? TP? F?┐PP? T? PP?┐P? FP? Q?(P→ Q)∧(Q→ P)?(P∧ Q)∨(┐P ∧┐ Q) ┐(P? Q)? P?┐Q (6) 不可兼析取( 异或)V 性质:PV Q? QV P (PV Q)V R? PV (QV R) P∧(QV R)?(P∧Q)V (P∧ R) PV Q?(P ∧┐ Q)∨(┐P∧ Q)?┐(P? Q) PV P? FPV F? PPV T?┐P若PV Q? R,则PV R? Q,QV R? P,且PV QV R? F (7) 条件否定??? c 性质:P??? c P? FP??? c F? PP??? c T? F P??? c ┐P? P┐P??? c P?┐PT??? c P?┐PF??? c P? FP??? c Q?┐(P→ Q) (8) 与非↑性质:P↑Q?┐(P∧ Q) P↑P?┐(P∧ P)?┐P (P↑ Q)↑(P↑ Q)?┐(P↑ Q)? P∧Q (P↑ P)↑(Q↑ Q)?┐P ↑┐ Q?┐(┐P ∧┐ Q)? P∨Q P↑F? TP↑T?┐P (9) 或非↓性质:P↓P?┐(P∨ P)?┐P (P↓ Q)↓(P↓ Q)?┐(P↓ Q)? P∨Q (P↓ P)↓(Q↓ Q)?┐P ↓┐ Q?┐(┐P ∨┐ Q)? P∧Q P↓Q?┐(P∨ Q) 3 .联结词的优先顺序最外层括号可以省略, 联结词运算的优先次序为?,∧,∨,→,?。一个联结词集合, 若任何一个命题公式都可以用该联结词组中的联结词的合式公式所确定, 就称它为全功能联结词组( 联结词功能完备集). 如果在此集合中任意去掉一个联结词就不再具有这种特性, 就称此集合为最小全功能联结词组( 最小功能完备集或最小联结词组). {┐,∨,∧} 是全功能联结词组.{┐,∨},{ ┐,∧} 为最小全功能联结词组.{↑},{ ↓} 也是最小全功能联结词组。 4 .命题公式与符号化给定一个命题公式 A,若A 在各种赋值下取值均为真,, 则称 不是矛盾式, 则称 A为可满足式. 由定义可以看出, 重言式是可满足式, 但是其逆命题不真, 可满足式不见得是重言式. 用真值表可以判断一个公式是否为重言式, 矛盾式和可满足式。判别命题公式的类型,即重言式(永真式) 、矛盾式(永假式)和可满足式; 给出成真指派或成假指派, 不要把小项误认为成真指派或不要把大项误认为成假指派; 判断两个命题公式是否等价; 判断 A,B 是否等价, 就是要判断 A? B 为重言式. 也就是在各种赋值下,A与B 是否有相同的真值. 在给定的命题公式A中,将∨换成∧,将∧换成∨, 若有特殊元T和F 亦互相取代, 所得公式?A 称为 A的对偶式. 显然 A 也是?A 的对偶式. 求主析取范式和主合取范式,主析取范式为成真指派所对应小项的析取,主合取范式为成假指派所对应大项的合取。一般容易把小项写成成真指派,把大项写成成假指派。 5 .等价演算法求主析取范式和主合取范式清楚小项( 极小项) 、大项( 极大项) 、主析取范式和主合取范式的定义,特别要注意小项下标是成真指派,大项下标是成假指派。主析取范式是给定命题公式小项析取的等价式, 主