命题逻辑的基本概念.pptVIP

Lu Chaojun, SJTU * 命题公式 在由命题变项通过联结词构成复杂命题时,如何才是有意义的命题? 例如: ?P?Q?R.(意义明确吗?) 定义(命题公式): (1)命题变元(原子命题)是命题公式. (2)如果?、?是公式,那么(??), (? ?? ), (? ?? ), (??? )和(??? )是命题公式. (3)命题公式仅限于此. 上面这种定义方式是形式系统常用的合式定义,所定义的公式称为合式公式(well-formed formula,简记为wff). * 1+2;2+4/5; 3*3+1 1+2-; 1-/3 Lu Chaojun, SJTU * 判断符号串是否wff 根据公式的合式定义,层层归约,直到原子命题即可判断. 例子 ?(P?Q) (??P?(P?Q)) (((P?Q)?(Q?R))?(P?R)) ?(?P) 这个公式是wff ? ((P?Q)?(?Q)) (P?Q * Lu Chaojun, SJTU * 简写约定 为了减少括号的数量,可以引入优先级的约定. 例如按?,?,?,?,?的次序安排优先级. 相同联结词按从左到右的优先次序. 例: (P?(Q?R))可写成P?(Q?R),进而写成P?Q?R. (P?(P?R))可写成P?(P?R),但不能写成P?P?R. * Lu Chaojun, SJTU * 无括号表示法 前面的wff定义采用联结词中缀表示法,需要用括号区分运算次序. 波兰表示法(前缀): A ? B 表示为 ?AB 逆波兰表示法(后缀): A ? B 表示为 AB? (逆)波兰式无需括号,便于计算机处理. 例: (P?(Q?R)) 波兰式: ?P?QR 逆波兰式: PQR?? * Lu Chaojun, SJTU * 命题公式的真值(语义) 命题公式的真值由其成员命题的真值决定.常用真值表方法计算. 设公式?由成分命题P1, …, Pn联结而成. 对P1, …, Pn的真值指派(assignment)决定了? 的真值,称为? 的解释(interpretation),可表示为真值表的一行: P1 … Pn ? T … F T ?总共有2n个解释,构成?的真值表(2n行). * Lu Chaojun, SJTU * 重言式 若公式?在任一解释I 下值都为T,就称?为重言式(或永真式,tautology). 例如: P??P是重言式. 重言式由?,?,?,?联结所得公式仍是重言式. 重言式反映了逻辑规律. 若公式?在某个解释I0下值为T,则称?是可满足的(satisfiable). 例如:P?Q在I0 = (T, F)下值为T,所以是可满足的. 若公式?在任一解释I 下值都为F,就称?为矛盾式(永假式或不可满足式,contradiction). 例如:P? ?P * Lu Chaojun, SJTU * 三类公式间关系 定理: (练习) 1.? 永真 iff ??永假. 2.? 可满足 iff ??非永真. 3.? 非永假 iff ?可满足. * Lu Chaojun, SJTU * 代入保持重言式 代入规则:将公式? 中的命题变元P的所有出现都替换成公式?. 记为? [P/? ]. 针对命题变项代入. 处处代入. 定理:若?是重言式,则? [P/? ]也是重言式. * Lu Chaojun, SJTU * 例:代入 代入时被替换的是命题变元(原子命题),而不能是复合命题. 例如:可用(R?S)来替换(P??P)中的P,结果仍是重言式;但若用Q替换(P??P),则不能保持重言式. 代入时必须对同一命题变项处处替换以同一公式. 例如:上例中用Q只替换一处P得到的Q??P不是重言式. * 为什么? Lu Chaojun, SJTU * 利用代入规则证明重言式 例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代入即可证明. * Lu Chaojun, SJTU * 自然语句的形式化表示 为了进行逻辑演算,需要首先对自然语句用形式化的逻辑语言进行表示. 方法: 1.根据自然语句的含义,确定若干简单命题,并用命题符号P、Q…表示之; 2.根据自然语句的含义,确定简单命题之间的关系,并用命题联结词将它们联结起来. 可能需要仔细考察自然