主讲教师 欧阳丹彤 ouyd@jlu.edu.cn 吉林大学计算机科学与技术学院 第三章 古典数理逻辑 第四讲 完备集 主讲教师 欧阳丹彤 ouyd@jlu.edu.cn 吉林大学计算机科学与技术学院
2 完备集 定义3.1.12 完备集 设Q是逻辑运算符号集合，若所有逻辑运算都能由Q中元素表示出来，而Q的任意真子集无此性质，则称Q是一个完备集。 {，}，{，}都是完备集。
证明 {，} 是完备集 证明： PQ = (P Q) PQ = PQ= (PQ) PQ = (PQ) (QP) = (P Q) (Q P) = ((P Q)) ((QP))
定义3.1.13 与非式 设P，Q是两个命题，命题 “P与Q的 否定”称为P与Q的与非式，记作PQ。 “”称作与非联结词。 真值规定:PQ为真 iff P,Q不同时为真。
定义3.1.14 或非式 设P，Q是两个命题，命题 “P或Q的 否定”称为P与Q的或非式，记作 PQ， 称作或非联结词。 定义3.1.14 或非式 设P，Q是两个命题，命题 “P或Q的 否定”称为P与Q的或非式，记作 PQ， 称作或非联结词。 PQ=(PQ) 真值规定：PQ为真 iff P，Q同时为假。
证明：{}是完备集 P = (P P) =PP PQ = (P Q) = (P) (Q) =(PP)(QQ) PQ= (PQ)= (PQ) =((PQ) (PQ))=(PQ)(PQ) 练习：证明{}是完备集。