第一章命题逻辑(1.3-1.4)

1、1.3 命题公式与翻译1、命题公式：由命题变元、联结词和圆括号按一定规则组成的合式公式。 定义定义 合式公式合式公式定义如下： （1）单个命题变元是一个合式公式； （2）如果A是合式公式，则 A也是合式公式； （3）如果A和B是合式公式，则A B，A B，AB，AB均是合式公式； （4）当且仅当能有限次地利用（1）（3）形成的符号串才是合式公式。1.3 命题公式与翻译 例如， (P(P Q)Q)，P(PP(P Q)Q)等都是命题公式，而(P)(P)，(P)(P) ， RPRP等不是命题公式。2 2、命题符号化（翻译） 命题逻辑里讨论的对象是命题公式，而日常生活中的推理问题是用自然语言描述的，因

2、此要进行推理演算必须先把自然语言符号化（或形式化）成逻辑语言，即命题公式。然后再根据逻辑演算规律进行推理演算。1.3 命题公式与翻译例 将下列命题符号化（1）李明是计算机系的学生，他住在312室。（2）张三和李四是朋友。（3）虽然交通堵塞，但是老王还是准时到达了车站。（4）只有一个角是直角的三角形才是直角三角形。（5）老王或小李中有一个去上海出差。1.3 命题公式与翻译解：（1）首先用字母表示简单命题。 P：李明是计算机系的学生。 Q：李明住在312室。 该命题符号化为：P Q（2）张三和李四是朋友。是一个简单句 该命题符号化为：P1.3 命题公式与翻译（3）首先用字母表示简单命题。 P：交通

3、堵塞。 Q：老王准时到达了车站。 该命题符号化为：P Q（4）首先用字母表示简单命题。 P：三角形的一个角是直角。 Q：三角形是直角三角形。 该命题符号化为： P Q（ Q P ）1.3 命题公式与翻译（5）首先用字母表示简单命题。 P：老王去上海出差。 Q：小李去上海出差。 该命题符号化为：P Q（ 不可兼或） 也可符号化为：（PQ） （ P Q）或者 （P Q） （P Q）1.3 命题公式与翻译 从以上例子中可以看出，所谓命题符号化是指把一个用自然语言叙述的命题相应地写成由命题变元、联结词和圆括号表示的命题公式。符号化应该注意注意下列事项：u确定给定句子是否为命题。u句子中连词是否为命题联

4、结词。u要正确地表示原子命题和适当选择命题联 结词。1.3 命题公式与翻译 例：假如上午不下雨，我去看电影，否则就在家里读书或看报。 解：设解：设P P：上午下雨；：上午下雨； Q Q：我去看电影；：我去看电影； R R：我在家里读书；：我在家里读书； S S：我在家里看报。：我在家里看报。 本例可表示为：本例可表示为： （ P PQ Q） （P P（RSRS） 1.4 真值表与等价公式1 1、命题公式的真值表、命题公式的真值表 定义定义1.4.1 1.4.1 在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题的各种真值情况，把它汇列称表，就是命题公式的真值表命题公式的真值表。1.

5、4 真值表与等价公式2 2、构造真值表的步骤 1)1)找出给定命题公式中所有的命题变元，列出所有可能的真值。 2)2)按照从低到高顺序写出命题公式的各层次。 3)3)对应每个真值，计算命题公式各层次的值，直到最后计算出整个命题公式的值。1.4 真值表与等价公式例构造命题公式 的真值表1.4 真值表与等价公式例2 2构造命题公式(P Q） 的真值表1.4 真值表与等价公式例3 3构造命题公式 (P Q） （ P Q）的真值表1.4 真值表与等价公式 由上例可见: :个命题变元有组真值指派；个命题变元有2 23 3 组真值指派，个则有个2 2n n个真值指派。1.4 真值表与等价公式、命题公式的永

6、真式、永假式和可满足式、命题公式的永真式、永假式和可满足式 定义定义 设公式中有设公式中有n个不同的命题变元个不同的命题变元 p1,pn,(n为正整数为正整数)。该变元组的任意一组。该变元组的任意一组确定的值（确定的值（ u1,un）称为关于）称为关于p1,pn的一个的一个完全指派完全指派，其中，其中ui或为，或为。如果对于或为，或为。如果对于中部分变元赋以确定值，其余变元没有赋以中部分变元赋以确定值，其余变元没有赋以确定的值，则这样的一组值称为公式的关于确定的值，则这样的一组值称为公式的关于该变元组的该变元组的部分指派部分指派。1.4 真值表与等价公式、命题公式的永真式、永假式和可满足式、命

7、题公式的永真式、永假式和可满足式 例例 设设A=(P (QR) S， 其变元组为其变元组为(P,Q,R,S)。 (P,Q,R,S)=(1,0,1,1)为为A的完全指派，的完全指派， (P,Q,R,S)=(0,0,1,S)为为A的部分指派。的部分指派。1.4 真值表与等价公式、命题公式的永真式、永假式和可满足式、命题公式的永真式、永假式和可满足式 定义定义 对于任一公式对于任一公式A A，凡使得，凡使得A A为真的指派，为真的指派，不管是完全指派还是部分指派，都称为不管是完全指派还是部分指派，都称为A A的的成真成真指派指派，凡使得凡使得A A为假的指派，也不管是完全指派为假的指派，也不管是完全

8、指派还是部分指派，都称为还是部分指派，都称为A A的的成假指派成假指派。 1.4 真值表与等价公式、命题公式的永真式、永假式和可满足式、命题公式的永真式、永假式和可满足式例例 设设A A=(P(Q=(P(Q R)R) ( ( R R S)S)，则，则完全指派完全指派(P,Q,R,S)=(0,1,0,1)(P,Q,R,S)=(0,1,0,1)和和部分指派部分指派(P,Q,R,S)=(0,1,0,S)(P,Q,R,S)=(0,1,0,S)都是都是A A的成真指派，的成真指派，而指派而指派(P,Q,R,S)=(1,0,1,0)(P,Q,R,S)=(1,0,1,0)为为A A的成假指派。的成假指派。1

9、.4 真值表与等价公式 定义定义 如果一个命题公式的所有完全指派均为成真如果一个命题公式的所有完全指派均为成真指派，则该公式称为指派，则该公式称为永真式永真式。 如果一个命题公式的所有完全指派均为成假如果一个命题公式的所有完全指派均为成假指派，则该公式称为指派，则该公式称为永假式永假式。 既不是永真式，又不是永假式，则称此命题既不是永真式，又不是永假式，则称此命题公式是公式是可满足式可满足式。1.4 真值表与等价公式4 4、等价公式、等价公式 定义定义 给定两个命题公式和，设给定两个命题公式和，设p1,pn为为所有出现于所有出现于A和和B中的原子变元，若给中的原子变元，若给p1,pn任任一组真

10、值指派，一组真值指派，A和和B的真值均相同，则称的真值均相同，则称，是逻辑等价的是逻辑等价的，亦说（）等价于，亦说（）等价于（）（）,并记作：并记作：1.4 真值表与等价公式4 4、等价公式、等价公式例：利用真值表证明TTT TTTT FTTF TTTF F Q QPPP Q 1.4 真值表与等价公式4 4、等价公式、等价公式例：例：AB （A B） （B A） 1.4 真值表与等价公式4 4、等价公式、等价公式练习：判断公式A：(PQ) (P Q)与 B：(PR) (P R)是否等价。1.4 真值表与等价公式解：列该公式的真值表：FFFTTFTTFFFFFTFFFTTTFFFFFTTTFFF

11、TFFFTFFTFFTTFTTTTTTTTFFTTTTTFTTTTFTTTTTTTTFFTTTTTTFTTFTTTBAPRPRRPQPQQRQP1.4 真值表与等价公式下面列出组等价公式（1）双重否定律 （2）同等律 ； （3）交换律 ； ； 1.4 真值表与等价公式（4）结合律 （）（）； （）（）； （） （）（5）分配律 （）（）（）； （）（）（） 1.4 真值表与等价公式（6）摩根律 （）； （） （7）吸收律 （） ； （） 1.4 真值表与等价公式（8）蕴含律 （9）等价律 （）（）（10）零律； 1.4 真值表与等价公式（11）同一律； （12）互补律； （13）输出律 （）

12、1.4 真值表与等价公式（14）归缪律 （）（）（15）逆反律 说明：（）证明上述组等价公式的方法可用真值表法，把改为所得的命题公式为永真式，则成立。 1.4 真值表与等价公式（2） 、 均满足结合律， 则在单一用、 联结词组成的命题公式中，括号可以省去。（3）每个等价模式实际给出了无穷多个同类型的具体的命题公式。例如： (P Q) ( P Q)， (P Q) (R S) ( (P Q) (R S)， (PQ) R) ( (P Q) R) 1.4 真值表与等价公式5 5、置换规则、置换规则 定义定义 给定一命题公式，其中P1、P2Pn 是中的原子命题变元，若（1）用某些命题公式代换中的一些原子

13、命题变元Pi （2）用命题公式i代换Pi，则必须用i代换中的所有Pi 由此而得到的新的命题公式称为命题公式的代换实例代换实例1.4 真值表与等价公式讨论定义：（1 1）要用命题公式同时代换同一个原子命题变元例设：（Q） 若用（）代换中的，得 ：（）（Q（）是的代换实例， 而：（）（Q）不是B的代换实例。1.4 真值表与等价公式讨论定义：（2 2）永真式的代换实例仍为永真式；反之代换实例为永真式时，则不能断定原公式也一定是永真式。例2：为一永真式，若用任何命题公式代换，则仍为永真式 为一个可满足的命题公式，若用代换，则得（）为永真式，但（）并不是永真式。1.4 真值表与等价公式讨论定义：（3 3）一个命题公式的代换实例有许多个，但不一定都等价于原来的命题公式 例3的代换实例有：（），（），（）等所以，一个命题公式的代换实例有无限个。1.4 真值表与等价公式下面讨论取代过程（置换规则）： 定义定义 给定一命题公式，是的任何部分，若也是一命题公式，则称是的子命是