《命题逻辑教学》PPT课件.ppt

第 一 章 命题逻辑,1-1 命题及其表示法,1-2 联结词,1-3 命题公式与翻译,1-4 真值表与等价公式,第一章 命题逻辑,1-5 重言式与蕴涵式,1-6 其他联结词,1-7 对偶与范式,1-8 推理理论,第一章 命题逻辑,1-1 命题及其表示法,把对确定的对象作出判断的陈述句 称作命题,当判断正确或符合客观实际时， 称该命题真（True），用“T”或“1”表示； 否则称该命题假（False），用“F”或“0”表示。 要点：确定的对象 作出判断 陈述句 （见P-2的句子）,通常把不含有逻辑联结词的命题 称为原子命题或原子（atoms） （自然语言中的单句,P-2的(1)、(2)、(4)）,把由原子命题和逻辑联结词共同组成的 命题称为复合命题（compositive propositions or compound statements） （自然语言中的复句， P-2的(9)、(10)）。,命题的符号化（标示符）： 可以用以下两种形式将命题符号化： .用（带下标的）大写字母； 例如：P：今天下雨。 .用数字。 例如：12：今天下雨。 上例中的“P”和“12”称为命题标示符。,命题常元（proposition constants） 我们把表示具体命题及表示常命题的p，q，r，s等与f，t统称为命题常元。,命题变元（proposition variable） 是以“真、假”或“1，0”为取值范围的变元，它未指出符号所表示的具体命题，可以代表任意命题 。,指派 当命题变元用一个特定命题取代时，该命题变元才能有确定的真值，从而成为一个命题。称对命题变元进行指派,对任意给定的命题变元p1,pn的一种取值 状况，称为指派或赋值（assignments） ， 用字母，等表示,当A对取值状况 为真时，称指派弄真A或是A的成真赋值，记为(A) = 1； 反之称指派弄假A或是A的成假赋值，记为 (A) = 0。,1-2 联结词,否定词“并非”,合取词“并且”,析取词“或”,条件词“如果，那么”,双条件词“当且仅当”,(1)否定（negation ） 定义1-2.1 设P为一命题，P的否定是一个新命题，记作“P”。若P为T， P为F；若P为F， P为T。联结词“ ”表示自然语言中的“并非”（not ）。,表1-2.1 否定词“”的意义,“见假为真，见真为假” p读作“并非p”或“非p”。,（2）合取（ conjunction ） 定义1-2.2 两个命题P和Q的合取是一个复合命题，记作PQ。当且仅当P、Q同时为T时， PQ 为T，其他情况下， PQ的真值都是F。合取联结词 “”表示自然语言中的 “并且”（and ）。,1-2.2 合取词“”的意义,pq读作“p并且q”或“p且q”,见假为假，全真为真。,（3）析取词（disjunction） 定义1-2.3 两个命题P和Q的析取是一个复合命题，记作P Q。当且仅当P、Q同时为F时， P Q 为F，其他情况下， P Q的真值都是T。析取联结词 “ ”表示自然语言中的 “ 或”（or ）。,表 1-2.3 析取词“”的意义,见真为真，全假为假。,pq读作“p或者q”、“p或q”。,（4）条件词（implication) 定义1-2.4 给定两个命题P和Q，其条件命题是一个复合命题，记作P Q。当且仅当P的真值为T，Q的真值为F时， P Q 的真值为F，其他情况下， P Q的真值都是T。条件联结词 “ ”表示自然语言中的 “如果，那么” （ifthen）。,表1-2.4 条件词“ ”的意义,pq中的p称为条件前件，q称为条件后件,前真后假为假，其他为真。,（5）双条件(two-way-implication) 定义1-2.5 给定两个命题P和Q，其复合命题P Q称作双条件命题。当P和Q的真值相同时， P Q 的真值为T，否则， P Q的真值都是F。双条件联结词 “ ”表示自然语言中的“当且仅当”（if and only if）。,1-2.5 双向条件词“ ”的意义,pq读作“p与q互为条件”，“p当且仅当q”。,相同为真，相异为假。,定义1-3.1 以下四条款规定了命题公式（proposition formula） 的意义：,（1）单个命题常元或命题变元是命题公式，也称为原子公式或原子。 （2）如果A是命题公式，那么A也是命题公式。 （3）如果A，B是命题公式，那么（AB），（AB），（AB），（AB）也是命题公式。 （4）只有有限步引用条款（1）、（2）、（3）所组成的符号串是命题公式。 命题公式又称为合式公式Wff（Well formed formula ） Wff的正例和反例见P-10页。,1-3 命题公式与翻译,联结词的优先级 命题公式外层的括号可以省略； 联结词的优先级：、。 利用加括号的方法可以提高优先级。 范例：如下的Wff ： PQR 等价于Wff ： （PQ）R ） 等价于Wff ： （PQ）R 不等价于Wff ： P（QR）,自然语言的语句用Wff 形式化 主要是以下几个方面：, 要准确确定原子命题，并将其形式化。, 要选用恰当的联结词，尤其要善于识别自然语言中的联结词（有时它们被省略），否定词的位置要放准确。, 必要时可以进行改述，即改变原来的叙述方式， 但要保证表达意思一致。, 需要的括号不能省略，而可以省略的括号， 在需要提高公式可读性时亦可不省略。, 要注意语句的形式化未必是唯一的。 自然语言的语句用Wff 形式化的例子见P-10页。,1-4 真值表与等价公式,定义1-4.1（真值表） 在命题公式Wff中， 对于公式中分量一切可能的指派组合,公式A的取值可能用下表来描述，这个表称为真指表（truth table） 。 真值表的例子见P-13页表1-4.1 、表1-4.2 、表1-4.3和P-14页表1-4.4、表1-4.5 、表1-4.6 。,定义1-4.2 （ 等价公式） 给定两个命题公式A和B，设P1，P2， ， Pn为所有出现于A和B中的原子变元，若给P1，P2， ， Pn任一组真值指派，A和B的真值都相同，则称A和B是等价的或逻辑相等。记作AB 等价证明方法1：可以用真值表验证两个Wff是否等价，见P-13的例题5 “真值表法”。,常用的等价等值式 E1 AA 双重否定律 E2 AAA 幂等律 E3 AAA 幂等律 E4 ABBA 交换律 E5 ABBA 交换律 E6 (AB)CA(BC) 结合律 E7 (AB)CA(BC) 结合律 E8 A(BC) (AB)(AC) 分配律 E9 A(BC) (AB)(AC) 分配律 E10 (AB) AB 德摩根律 E11 (AB) AB 德摩根律 E12 A(AB) A 吸收律 E13 A(AB) A 吸收律,E14 ABAB E15 A B (AB)(BA) E16 Att E17 AtA E18 AfA E19 Aff E20 AAt 排中律 E21 AAf 矛盾律 E22 tf, ft 否定律 E23 ABCA(BC) E24 AB BA 逆否律 E25 (AB)(AB) A P-16 例题6 验证吸收率,1律,0律,定义1-4.3 如果X是Wff A的一部分，且X本身也是一个Wff，则称X为公式A的子公式。 定理1-4.1 （替换原理Rule of Replacement ，简记为RR）如果X是Wff A的子公式，若X Y，如果将A中的X用Y来置换，所得到的新公式B与公式A等价，即A B。 等价证明方法2：证明思路： “讨论指派法” 等价证明方法3：见P-16的例题7“等价代换法”。,定义1-5.1 对命题公式A，如果对A中命题变元的一切指派均弄真A，则A称为重言式（tautology）， 又称永真式.,如果至少有一个指派弄真A，则A称为可满足式 （satisfactable formula or contingency）。,定义1-5.2如果对A中命题变元的一切指派均弄假A，则称A为不可满足式或矛盾式（contradiction or absurdity）或永假式 。,1-5 重言式与蕴涵式,定理1-5.1 任何两个重言式的合取或析取，仍然是一个重言式。 证明思路：“讨论指派法”A为T，B为T， A与B析取（或合取）仍为T， 定理1-5.2 一个重言式，对同一分量都用任何Wff置换，其结果仍为一重言式。 证明思路：“讨论指派法” 真值与分量的指派无关，置换后与仍为T。 见P-20的例题1 定理1-5.3 设A、B是两个Wff，一个重言式， AB当且仅当A B为一重言式。 关于“当且仅当”的证明思路：双向证明法，从“AB”出发推出“A B为一重言式”；再从“A B为一重言式”出发推出“AB” 。,定义1-4.2 （ 等价公式的另一种定义）当命题公式AB为重言式时，称A逻辑等价于B，记为 A B，它又称为逻辑等价式 （logically equivalent or equivalent）。,定义1-5.3 当命题公式AB为重言式时，称A逻辑蕴涵B，记为A B，它又称为逻辑蕴涵式 (logically implication)。 常用的逻辑蕴涵式见p-21页表1-5.2,定理1-5.4 设P、Q为任意两个命题公式，PQ的充分必要条件是PQ且QP 。 证明思路： 本定理的结论是“PQ” 本定理的条件是“PQ且QP ” 如果能从条件“PQ且QP ”推出结论“PQ”，说明条件是充分的； 如果能从结论“PQ”推出条件“PQ且QP ” ， 说明条件是必要的。 先证必要性：XXXXXX 再证充分性：XXXXXX ,关于等价式和蕴涵式的性质： （1）AB当且仅当 AB （2）AB当且仅当 AB （3）若AB，则BA 等价对称性 （4）若AB，BC，则AC 等价传递性 （5）若AB，则BA 蕴涵逆否性 （6）若AB，BC，则AC 蕴涵传递性 （7）若AB，AA，BB，则AB 蕴涵等价代换 （8）若AB，CB，则ACB （9）若AB，AC，则ABC,设A为永真式，p为A中命题变元，A(B/p) 表示将A中p的所有出现全部代换为公式B后所得的命题公式（称为A的一个代入实例），那么 A(B/p)亦为永真式。,代入原理（Rule of Substitution），简记为RS,1-6 其它联结词,1-6.1 异或词“”的意义,p q读作“p异或q”,相同为假，相异为真。,（1）不可兼析取（异或） 定义1-6.1 两个命题公式P和Q的不可兼析取是一个新命题公式，记作P Q。当且仅当P、Q真值不同时， P Q 为T，其他情况下的真值都是F。,异或联结词的性质： （1） PQPQ 交换律 （2）（PQ）R P（QR） 结合律 （3）P（QR）（PQ）（PR）分配律 （4）（ PQ ）（P Q）（ PQ） （5）（ PQ ） （PQ） （6）（ PP ）F，FP P，T P P 定理1-6.1 设P、Q和R为命题公式，如果 PQR，则PRQ ，QRP， 且PQR 为一矛盾式。 证明思路利用性质（6）。,表1-6.2 异或词“”的意义,p q读作“p和q的条件否定”,前真后假为真 其余为假。,（2）条件否定 定义1-6.2 设P和Q是两个命题公式， P和Q的条件否定是一个新命题公式，记作P Q。当且仅当P的真值为T，Q的真值为F时， P Q 为T，其他情况下的真值都是F。 根据此定义，可知 P Q （P Q）,（3）与非 定义1-6.3 设P和Q是两个命题公式， P和Q的与非是一个新命题公式，记作P Q。当且仅当P和Q的真值都为 T时， P