01命题逻辑基本概念.ppt

定义1.8 赋值或解释 设p1,p2,…,pn是出现在公式A中的全部命题变项，给p1,p2,…,pn各指定一个真值，称为对A的一个赋值或解释。若指定的一组值使A的真值为1，则称这组值为A的成真赋值；若使A的真值为0，则称这组值为A的成假赋值。 对含n个命题变项的公式A的赋值情况做如下规定：(1)若A中出现的命题符号为p1,p2,…,pn，给定A的赋值α1,α2,…,αn 是指p1＝α1，p2＝α2,…，pn＝αn。 (2)若A中出现的命题符号为p，q，r...,给定A的赋值α1,α2,…,αn是指p＝α1，q＝α2,…，最后一个字母赋值αn。 上述αi取值为0或1，i＝1,2,…,n。 赋值举例 在公式(┐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个不同的赋值。 定义1.9 真值表 将命题公式A在所有赋值下取值情况列成表，称作A的真值表。 构造真值表的具体步骤如下： (1)找出公式中所含的全体命题变项p1,p2,…,pn (若无下角标就按字典顺序排列)，列出2n个赋值。本书规定，赋值从00…0开始，然后按二进制加法依次写出各赋值，直到11…1为止。 (2)按从低到高的顺序写出公式的各个层次。 (3)对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。 公式A与B具有相同的或不同的真值表，是指真值表的最后一列是否相同，而不考虑构造真值表的中间过程。 说明 例1.8 求下列公式的真值表，并求成真赋值和成假赋值。 (1)(┐p∧q)→┐r (2)(p∧┐p)?(q∧┐q) (3)┐(p→q)∧q∧r 定义1.10 重言式、永真式、可满足式 设A为任一命题公式 (1)若A在它的各种赋值下取值均为真,则称A是重言式(tautology)或永真式。 (2)若A在它的各种赋值下取值均为假,则称A是矛盾式(contradiction)或永假式。 (3)若A不是矛盾式,则称A是可满足式（satisfactable formula）。 定义1.10的进一步说明 A是可满足式的等价定义是：A至少存在一个成真赋值。 重言式一定是可满足式，但反之不真。因而，若公式A是可满足式，且它至少存在一个成假赋值，则称A为非重言式的可满足式。 真值表可用来判断公式的类型: 若真值表最后一列全为1，则公式为重言式。 若真值表最后一列全为0，则公式为矛盾式。 若真值表最后一列中至少有一个1，则公式为可满足式。 说明 n个命题变项共产生2n个不同赋值 含n个命题变项的公式的真值表只有 种不同情况 例题 例题1.9 下列各公式均含两个命题变项p与q，它们中哪些具有相同的真值表? (1) p→q (4) (p→q)∧(q→p)(2) p?q (5) ┐q∨p(3) ┐(p∧┐q) 哑元 设公式A,B中共含有命题变项p1,p2,…,pn，，而A或B不全含有这些命题变项，比如A中不含pi,pi+1,…,pn ,称这些命题变项为A的哑元，A的取值与哑元的变化无关，因而在讨论A与B是否有相等的真值表时，将A,B都看成p1,p2,…,pn的命题公式。 例题 例1.10 下列公式中,哪些具有相同的真值表?(1)p→q (2)┐q∨r (3)(┐p∨q)∧((p∧r)→p) (4)(q→r)∧(p→p) 本章主要内容 命题与真值（或真假值）。 简单命题与复合命题。 联结词：┐，∧，∨，→，?。 命题公式（简称公式）。 命题公式的层次和公式的赋值。 真值表。 公式的类型：重言式（永真式），矛盾式（永假式），可满足式。 本章学习要求 在5种联结词中，要特别注意蕴涵联结的应用，要弄清三个问题： p→q 的逻辑关系 p→q 的真值 p→q 的灵活的叙述方法 写真值表要特别仔细认真，否则会出错误。 深刻理解各联结词的逻辑含义。 熟练地将复合命题符号化。 会用真值表求公式的成真赋值和成假赋值。 本章典型习题 命题符号化 求复合命题的真值与命题公式的赋值 判断公式的类型 例题：命题符号化 (1)我和他既是兄弟又是同学 p：我和他是兄弟，q：我和他是同学。 故命题可符号化为： p∧q。 (2)张三或李四都可以做这件事。 p：张三可以做这件事。 q：李四可以做这件事。 故命题可符号化为：p∧q。