离散数学L1命题.ppt

判断符号串是否wff 根据公式的合式定义,层层归约,直到原子命题即可判断. 例子 ?(P?Q) (??P?(P?Q)) (((P?Q)?(Q?R))?(P?R)) ?(?P) 这个公式是wff ? ((P?Q)?(?Q)) (P?Q * 简写约定 为了减少括号的数量,可以引入优先级的约定. 例如按?,?,?,?,?的次序安排优先级. 相同联结词按从左到右的优先次序. 例: (P?(Q?R))可写成P?(Q?R),进而写成P?Q?R. (P?(P?R))可写成P?(P?R),但不能写成P?P?R. * 无括号表示法 前面的wff定义采用联结词中缀表示法,需要用括号区分运算次序. 波兰表示法(前缀): A ? B 表示为 ?AB 逆波兰表示法(后缀): A ? B 表示为 AB? (逆)波兰式无需括号,便于计算机处理. 例: (P?(Q?R)) 波兰式: ?P?QR 逆波兰式: PQR?? * 命题公式的真值(语义) 命题公式的真值由其成员命题的真值决定.常用真值表方法计算. 设公式?由成分命题P1, …, Pn联结而成. 对P1, …, Pn的真值指派(assignment)决定了? 的真值,称为? 的解释(interpretation),可表示为真值表的一行: P1 … Pn ? T … F T ?总共有2n个解释,构成?的真值表(2n行). * 重言式 若公式?在任一解释I 下值都为T,就称?为重言式(或永真式,tautology). 例如: P??P是重言式. 重言式由?,?,?,?联结所得公式仍是重言式. 重言式反映了逻辑规律. 若公式?在某个解释I0下值为T,则称?是可满足的(satisfiable). 例如:P?Q在I0 = (T, F)下值为T,所以是可满足的. 若公式?在任一解释I 下值都为F,就称?为矛盾式(永假式或不可满足式,contradiction). 例如:P? ?P * 三类公式间关系 定理: 1.? 永真 iff ??永假. 2.? 可满足 iff ??非永真. 3.? 非永假 iff ?可满足. * 代入保持重言式 代入规则:将公式? 中的命题变元P的所有出现都替换成公式?. 记为? [P/? ]. 针对命题变项代入. 处处代入. 定理:若?是重言式,则? [P/? ]也是重言式. * 例:代入 代入时被替换的是命题变元(原子命题),而不能是复合命题. 例如:可用(R?S)来替换(P??P)中的P,结果仍是重言式;但若用Q替换(P??P),则不能保持重言式. 代入时必须对同一命题变项处处替换以同一公式. 例如:上例中用Q只替换一处P得到的Q??P不是重言式. * 利用代入规则证明重言式 例1: 证明(R?S)??(R?S)为重言式。 因P??P是重言式, 以(R?S)代入P,得(R?S)??(R?S).必是重言式. 例2:证明((R?S)?((R?S)?(P?Q)))?(P?Q)为重言式. 易验证:(A?(A?B))?B是重言式(此公式表达的正是modus ponens推理规则), A以R?S代入,B以P?Q代入即可证明. * 自然语句的形式化表示 为了进行逻辑演算,需要首先对自然语句用形式化的逻辑语言进行表示. 方法: 1.根据自然语句的含义,确定若干简单命题,并用命题符号P、Q…表示之; 2.根据自然语句的含义,确定简单命题之间的关系,并用命题联结词将它们联结起来. 可能需要仔细考察自然语句的含义,才能抽取出隐含的简单命题和联结词. * 例子 (1)张三不是学生. 令P:张三是学生.则(1): ?P. 令P:张三不是学生. 如何? (2)张三既聪明又用功. 令P:张三聪明. Q:张三用功.则(2):P?Q. 令P:张三既聪明又用功. 如何? 思考:张三虽然聪明但不用功. (3)张三一感冒就发烧. 令P:张三感冒. Q:张三发烧.则(3):P?Q. * 例子(续) (4)张三和李四是学生. 令P:张三是学生. Q:李四是学生.则(4):P?Q. 思考:张三和李四是表兄弟.也用?? (5)张三或李四当班长. 令P:张三当班长. Q:李四当班长.则(5):P?Q? 不可兼或!(5)应表示为:(P??Q)?(?P?Q). 思考:张三和李四至少一人是学生.P?Q合适. 思考:张三或李四都可当班长.也用?? * 逻辑趣题 某岛上只有骑士(knight)和无赖(knave)两种居民.骑士总说真话,无赖总说假话. 假如你去该岛后遇到甲乙两人, 甲说:“乙是骑士.” 乙说:“我们两人是不同类型的人.” 问甲和乙分别是什么人? * End Lu Chaojun, SJTU Lu Chaojun, SJTU 命