离散数学命题逻辑.ppt

* * 3. 张三说李四在说谎，李四说王五在说谎，王五说张三、 李四都在说谎。问张三、李四、王五三人，到底谁说真话，谁说假话？ 由题意知推理的前提为： P→? Q，?P→Q，Q→?R，? Q→R， R→（?P∧? Q），? R→（P∨Q）。 下面根据已知前提进行形式推理。 解 先将简单命题符号化。 令P：张三说真话；Q：李四说真话；R：王五说真话， * * 因此，由上述推理知张三说假话，王五说假话，只有李四说真话。 编 号 公 式 依 据 （1） P → ? Q 前 提 （2） ? Q→R 前 提 （3） P→R （1），（2）；I13 （4） R→（?P∧?Q） 前 提 （5） P→（?P∧? Q） （3），（4）；I13 （6） ?P∨（?P∧? Q） （5）；E11 （7） ?P （6）；E9 （8） ?P→Q 前 提 （9） Q （7），（8）；I11 （10） Q→?R 前 提 （11） ?R （9），（10）；I11 （12） ?P∧Q∧?R （7），（9），（11）；I9 P→? Q，?P→Q，Q→?R，? Q→R， R→（?P∧? Q），? R→（P∨Q）。 * * 例 题 1. 将下列命题符号化 （1）小李虽然聪明，但不用功。 （3）人不犯我，我不犯人；人若犯我，我必犯人。 （2）当他心情好的时候，他一定会唱歌；当他在唱歌时，就说明他心情一定很好。 令P：小李聪明；Q：小李用功。 则命题可表示为P∧ ? Q。 令P：他心情好；Q：他在唱歌。 则命题可表示为（P→Q）∧（Q → P）或P ? Q。 令P：人犯我；Q：我犯人。 则该命题可表示为（ ? P → ? Q）∧（P → Q）即 P ? Q * * 2.判断下列命题公式的类型 (1) (P → Q) ? (? Q → ? P) (2) ( ? Q → P) → (P → Q) 解 (1) F1= (P → Q) ? (? Q → ? P)的真值表如下表所示，由表知F1所标记的那一列全为1，故F1重言式 。 (2)F2=(? Q→P) → (P → Q)的真值表如下表所示,由表知F2所标记的那一列不全为1,但当(P，Q)=(0，0)时,F2取“1”,所以F2是可满足式。 P Q P?Q ?Q??P ?Q?P F1 F2 0 0 1 1 0 1 1 0 1 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 1 1 * * 3. 证明下列命题公式的等值关系 （1） ? （P ? Q） ? （P∨Q）∧ ? （P∧Q） （2）（P → （Q → R）） ? （P → ? Q）∨（P → R） 解 (1) ∵ ? （P ? Q） ? ? （（P∧Q）∨（ ? P∧ ? Q）） E12 ? ? （P∧Q）∧（P∨Q） E10，E6 ∴ ? （P ? Q） ? （P∨Q）∧ ? （P∧Q） 解 (2) ∵（P → ? Q）∨（P → R） ?（ ? P∨ ? Q）∨（ ? P∨R） E11 ? （ ? P∨ ? P）∨（ ? Q∨R） E1，E2 ? ? P∨（ ? Q∨R） E7 ? P → （Q → R） ∴（P → （Q → R）） ? （P → ? Q）∨（P → R） （2）（P → （Q → R）） ? （P → ? Q）∨（P → R） * * 4.用形式证明方法证明 （1）P → S是前提? P∨Q， ? Q∨R，R → S的结论。 (1) 证明 编 号 公 式 依 据 （1） （2） （3） （4） （5） （6） （7） （8） P ? P∨Q Q ? Q∨R R R → S S P → S 附加前提 前提 （1）,（2）；I10 前提 （3）,（4）；I10 前提 （5）,（6）；I11 （1）,（7）；CP规则 ∴ ? P∨Q， ? Q∨R，R → S ? P → S * * （2）S → ? Q，S∨R， ? R， ? P → Q ? P (2) 证明 因此，S → ? Q，S∨R， ? R， ? P → Q ? P。 （1） （2）