基本信息
文件名称:离散学命题逻辑.ppt
文件大小:3.22 MB
总页数:46 页
更新时间:2025-07-09
总字数:约8.39千字
文档摘要

赋值举例在公式(┐p1∧┐p2∧┐p3)∨(p1∧p2)中,

000(p1=0,p2=0,p3=0),

110(p1=1,p2=1,p3=0)都是成真赋值,

001(p1=0,p2=0,p3=1),

011(p1=0,p2=1,p3=1)都是成假赋值。在(p∧┐q)→r中,

011(p1=0,p2=1,p3=1)为成真赋值,

100(p1=1,p2=0,p3=0)为成假赋值。重要结论:

含n(n≥1)个命题变项的公式共有2n个不同的赋值。第31页,共46页,星期日,2025年,2月5日定义1.9真值表将命题公式A在所有赋值下取值情况列成表,称作A的真值表。构造真值表的具体步骤如下:(1)找出公式中所含的全体命题变项p1,p2,…,pn(若无下角标就按字典顺序排列),列出2n个赋值。本书规定,赋值从00…0开始,然后按二进制加法依次写出各赋值,直到11…1为止。(2)按从低到高的顺序写出公式的各个层次。(3)对应各个赋值计算出各层次的真值,直到最后计算出公式的真值。公式A与B具有相同的或不同的真值表,是指真值表的最后一列是否相同,而不考虑构造真值表的中间过程。说明第32页,共46页,星期日,2025年,2月5日例1.8求下列公式的真值表,并求成真赋值和成假赋值。(1)(┐p∧q)→┐r(2)(p∧┐p)?(q∧┐q)(3)┐(p→q)∧q∧r第33页,共46页,星期日,2025年,2月5日定义1.10重言式、永真式、可满足式设A为任一命题公式(1)若A在它的各种赋值下取值均为真,则称A是重言式(tautology)或永真式。(2)若A在它的各种赋值下取值均为假,则称A是矛盾式(contradiction)或永假式。(3)若A不是矛盾式,则称A是可满足式(satisfactableformula)。第34页,共46页,星期日,2025年,2月5日定义1.10的进一步说明A是可满足式的等价定义是:A至少存在一个成真赋值。重言式一定是可满足式,但反之不真。因而,若公式A是可满足式,且它至少存在一个成假赋值,则称A为非重言式的可满足式。真值表可用来判断公式的类型:若真值表最后一列全为1,则公式为重言式。若真值表最后一列全为0,则公式为矛盾式。若真值表最后一列中至少有一个1,则公式为可满足式。说明n个命题变项共产生2n个不同赋值含n个命题变项的公式的真值表只有种不同情况第35页,共46页,星期日,2025年,2月5日*离散学命题逻辑第1页,共46页,星期日,2025年,2月5日说明主要内容命题、联结词、复合命题命题公式、赋值、命题公式的分类与后续知识的关系是后续的准备或前提第2页,共46页,星期日,2025年,2月5日1命题与联结词数理逻辑研究的中心问题是推理。推理的前提和结论都是表达判断的陈述句。表达判断的陈述句构成了推理的基本单位。第3页,共46页,星期日,2025年,2月5日1.1命题与联结词称能判断真假而不是可真可假的陈述句为命题

(proposition)。作为命题的陈述句所表达得的判断结果称为命题的真值。真值只取两个:真与假。真值为真的命题称为真命题。真值为假的命题称为假命题。感叹句、疑问句、祈使句都不能称为命题。判断结果不唯一确定的陈述句不是命题。陈述句中的悖论不是命题。说明第4页,共46页,星期日,2025年,2月5日4是素数。x大于y。充分大的偶数等于两个素数之和。今天是星期二。请不要吸烟!这朵花真美丽啊!我正在说假话。例1.1判断下列句子是否为命题。是,假命题是,真命题不是,无确定的真值是,真值客观存在是,真值根据具体情况而定。不是,疑问句不是,祈使句不是,感叹句不是,悖论第5页,共46页,星期日,2025年,2月5日命题和真值的符号化用小写英文字母p,q,r…,pi,qi,ri…表示命题用“1”表示真,用“0”表示假r:充分大的偶数等于两个素数之和。s:今天是星期二。p:4是素数。q:不能被分解成更简单的陈述句,称这样的命题为简单命题或原子命题。由简单陈述句通过联结词而成的陈述句,称这样的命题为复合命题。第6页,共46页,星期日,2025年,2月5日例1.2将下面这段陈述中所出现的原子命题符号化,并指出它们的真值,然后再写出这段陈述。是有理数是不对的;2是偶素数;2或4是素数;如果2是素数,则3也是素数;2是素数当且仅当3也是素数。p:是有理数q:2是素数;r:2是偶数s:3是素数;t:4