离散数学 课件全套 第1-7章 命题逻辑、谓词逻辑-图

离散数学离散数学与其他专业课的关系数理逻辑:人工智能、形式语义学集合:形式语言、编译技术、计算复杂性关系:关系数据库函数:算法设计与分析、软件形式化方法图:数据结构、网络技术、人工智能代数系统:数字电路设计、软件形式化方法第1节 引言 第1章命题逻辑第2节 命题及命题逻辑联结词第3节 命题变元和合式的公式第4节 重言式（或永真式）和永真蕴涵式第5节 对偶原理（略）

第6节 范式和判定问题第7节 命题演算的推论理论一、地位作用:二、研究对象:三、主要内容:第1节、引言离散数学数学分支，计算机核心课程离散量结构及相互关系数理逻辑、集合论、代数系统、图论等1、命题的定义第1章命题逻辑第1节 基本概念第2节、命题及命题逻辑联结词5、原子命题2、命题的真值3、真值的表示4、命题标识符6、原子变元7、分子命题（复合命题）8、逻辑联结词1、命题的定义 一个具有确定的真假意义的陈述句称为命题；一般用英文大写字母表示。疑问句,祈使句,感叹句等均不是命题命题要么正确,要么错误2、命题的真值 一个命题的取值或真或假，这两种可能的取值称为命题的真值。正确错误3、真值的表示真值是真真值是假1T0FTrueFalse(1)上海是一个小山村。(2)抽烟的人均要得肺癌。(3)十是整数。(4)上课去！(5)你吃饭了吗？

(6)今天天气多好啊！(7)蚊子是鸟类动物。(8)我正在说谎。(F)(F)(F)(T)(×)(×)(×)(×)例、判断下列命题的真假关于悖论“我正在说谎。”

如果真值为“真”，则隐含着我正在说谎；真值不确定悖论如果真值为“假”，则隐含着我没有说谎。4、命题标识符 用英文大写字母表示命题命题标识符命题常量:命题变元:表示确定的命题表示任意的命题真值∈｛0，1｝或∈｛T，F｝5、原子命题 不能再分解成更简单的命题本原命题6、原子变元 若命题变元表示原子命题时，该变元称原子变元。例：命题变元是命题吗？第1章命题逻辑第1节 基本概念解： 命题变元不是命题，因为命题变元的真值不确定。 当命题变元P用特定的命题取代时，P才能确定真值对P进行真值指派7、分子命题 由原子命题通过逻辑联结词构成的新命题复合命题逻辑联结词1、真值表的概念2、否定（

）3、合取（∧，与）4、析取（∨，或）5、单条件（→）6、双条件（↔）7、命题符号化1、真值表的概念 在复合命题中，对命题变元的所有种可能的真值指派，复合命题都有一个确定的真值与其相对应，形成一个表，称为真值表。n个命题变元，2n种真值指派:两个命题变元,22＝4种真值指派00011011(0～3)0～2n-12、否定（

） 一元运算符，当且仅当P为真时，

P为假。真值表如表1.1所示。表1.1 逻辑联结词“

”的真值表P

P1001例、给出下列命题的否定命题（1）大连的每条街道都临海。（2）天津是一个城市。并非大连的每条街道都临海。大连的每条街道不都临海。大连的每条街道都不临海。√√×天津不是一个城市。注意：否定是对命题的部分否定。3、合取（∧，与） 二元运算符，当且仅当P、Q的真值均为真时，P∧Q的真值才为真。真值表如表1.2所示。表1.2 逻辑联结词“∧”的真值表PQP∧Q000110110001注意：

在数理逻辑中，只要P和Q的真值确定，P∧Q的真值即可确定，就可以成为新的命题，不管这个新命题在自然语言中是否有意义。将下列命题符号化(1)我虽然生病，但我仍去学校。(2)我虽然有钱，但我不去看电影。(3)张华与李明在吃饭。解：命题符号化过程及结果(1)我虽然生病，但我仍去学校。P：我生病；Q：我去学校；

(2)我虽然有钱，但我不去看电影。P：我有钱;Q：我去看电影;

(3)P:张华在吃饭;Q:李明在吃饭;注意：

用命题变元表示肯定的命题。P∧QP∧

QP∧Q第1章命题逻辑

第2节 逻辑联结词4、析取（∨，或、可兼或）

二元运算符，当且仅当P、Q的真值均为假时，P∨Q的真值才为假。真值表如表1.3所示。表1.3 逻辑联结词“∨”的真值表PQP∨Q000110110111第1章命题逻辑第2节 逻辑联结词例:将下列命题符号化：（1）张三或李四可以做这件事。（2）我们不能既划船又跑步。解：命题符号化过程及结果(1)张三或李四可以做这件事。P：张三可以做这件事；Q：李四可以做这件事；(2)我们不能既划船又跑步。P：我们划船;Q：我们跑步;

P∨Q

P∨

Q

(P∧Q)第1章命题逻辑

第2节 逻辑联结词5、单条件（→，善意的推定） 二元运算符，当且仅当P为真，Q为假时，P→Q的真值才为假，否则，均为真。真值表如表1.5所示。善意的推定：当条件为假时，无论后件为真为假，结论均为真。第1章命题逻辑

第2节 逻辑联结词PQP→

Q00011011表1.5 逻辑联结词“→”的真值表0111第1章命题逻辑第2节 逻辑联结词例:将下列命题符号化：（1）如果我生病，那么我不去学校。（2）如果我有钱，那么我就去看电影。解：命题符号化过程及结果(1)如果我生病，那么我不去学校。P：我生病；Q：我去学校；

(2)如果我有钱，那么我就去看电影。P：我有钱;Q：我去看电影;

P→

QP→Q第1章命题逻辑

第2节 逻辑联结词6、双条件（↔

） 二元运算符，当且仅当P、Q的真值相同时，P↔Q的真值才为真，否则，均为假。真值表如表1.6所示。第1章命题逻辑

第2节 逻辑联结词PQP↔

Q00011011表1.6 逻辑联结词“↔”的真值表1100第1章命题逻辑第2节 逻辑联结词例:将下列命题符号化：（1）只有在我生病的时候，我才不去学校。（2）当且仅当我有钱时，我才去看电影。解：命题符号化过程及结果(1)只有在我生病的时候，我才不去学校。P：我生病；Q：我去学校；

(2)当且仅当我有钱时，我才去看电影。P：我有钱;Q：我去看电影;

P↔

QP↔Q第1章命题逻辑逻辑联结词的优先级∧

∨

→

↔高低注意：

“∧”的优先级比“∨”高，而不是相同。第1章命题逻辑7、命题符号化的原则：（1）“∧”：（并列、递进、转折）同时、不但…而且、即…又、和（2）“∨”：（相容、选择）或许、大概、可能（3）“→”：（条件）如果…则…、如果…那么…第1章命题逻辑命题符号化的原则（续）：（4）“↔”：（等价）充分必要、当且仅当、只有…才能（5）“

”：（否定）非、不

第1章命题逻辑命题符号化的步骤：（1）找出原子命题；（2）用符号（大写英文字母）定义原子命题；（3）使用正确的逻辑联结词，将自然语言变成与之等价的符号化语言。第1章命题逻辑例：将下列命题符号化：（1）如果明天上午7点不是雨加雪，则我去学校。（2）只有明天上午7点不下雨而且不下雪，我才去学校。解：命题符号化过程及结果(1)P:明天上午7点下雨；Q:明天上午7点下雪；R:我去学校；如果明天上午7点不是雨加雪，则我去学校。

(P∧Q)→R第1章命题逻辑(P 只有明天上午7点不下雨而且不下雪，我才去学校。R∧

Q)↔第1章命题逻辑例：P：我生病；Q：我去学校；（1）我虽然生病，但我仍去学校。（2）只有在我生病的时候，我才不去学校。（3）如果我生病，那么我不去学校。P∧QP↔

QP→

Q第1章命题逻辑命题公式（合式的公式）的递归定义

合式的公式（Wff）是由命题变元、逻辑联结词、圆括号组成的：(1)单个的命题变元是合式的公式；(2)如果A是Wff，则

A是Wff(3)如果A和B是Wff，则(A∧B)、(A∨B)、(A→B)、(A↔B)都是Wff(4)当且仅当有限次地使用(1)、(2)、(3)所得到的包含命题变元、逻辑联结词、圆括号的符号串是Wff(递归基础）；（递归方法）；（递归方法）。（递归界限）第3节 命题变元和合式的公式第1章命题逻辑去括号原则(1)最外层括号可省；(2)、∧、∨、→、↔的优先级由高到低，有的括号可省；第1章命题逻辑例、根据定义判断下列公式是否是合式公式(1)、((A∧B)→A) (2)、A→(∧B) (3)、(P∧Q) (4)、ך(A→B) (5)、(P→(P∨ךQ)) (6)、(((P→Q)∧(Q→R))↔(S↔T))(7)、(P→Q)→(∧Q) (8)、(P→Q (9)、(P∧Q)→Q) （√）（×）(∧

是二元运算符

）（×)(括号不匹配）（×）括号不匹配（×)(∧

是二元运算符）（√）（√）（√）（√）第1章命题逻辑1、永真式（重言式）

对于命题变元的所有种可能的真值指派，命题公式的真值均为真，称该合式公式为永真式。第4节 重言式（或永真式）和永真蕴涵式第1章命题逻辑例、构造下列命题公式的真值表(1)、(P∧(P→Q))→Q(2)、P∨ךP(3)((P∨Q)∧R)∨ך((P∨Q)∧R)(4)P→Q、ךP∨Q、ך(P∧ך

Q)表1.8(P∧(P→Q))→Q的真值表PQ00011011P→

QP∧(P→Q)(P∧(P→Q))→Q011110001111(P∧(P→Q))→Q是永真式第1章命题逻辑表1.9P∨ךP的真值表P01ך

PP∨ךP1011P∨ךP是永真式第1章命题逻辑表1.10((P∨Q)∧R)∨ך((P∨Q)∧R)的真值表PQR000001010011100101110111P∨Q(P∨Q)∧Rך((P∨Q)∧R)((P∨Q)∧R)∨ך((P∨Q)∧R)00111111111000001110101011111111((P∨Q)∧R)∨ך((P∨Q)∧R)是永真式第1章命题逻辑表1.10P→Q、ךP∨Q、ך(P∧ך

Q)的真值表PQ

00011011注意：以上三个命题公式的真值表完全相同，称这三个命题公式等价。P→Q0111ך

Pך

P∨Q11001101ך

QP∧ך

Qך(P∧ך

Q)101000101101第1章命题逻辑第1章命题逻辑2、永假式（矛盾式） 给定一命题公式，若对任何的真值指派,其对应的真值永为F，则称该命题公式为矛盾式或永假式。第1章命题逻辑例、构造下列命题公式的真值表(1)、P∧ךP(2)、(P∧Q)∧ךP表1.11P∧ךP的真值表P01ך

PP∧

ךP1000P∧

ךP是永假式第1章命题逻辑表1.12(P∧Q)∧

P的真值表PQ00011011第1章命题逻辑P∧Q

P(P∧Q)∧

P100011000000(P∧Q)∧ךP是永假式第1章命题逻辑3、可满足式

至少有一组真值指派使得命题公式取值为真，则称该命题公式为可满足式。注意：永真式是可满足式的一种特例。第1章命题逻辑例、构造下列命题公式的真值表1.P→(Q∨R)2.(P∨Q)↔(Q∨P)表1.14

P→(Q∨R)的真值表PQR000001010011100101110111第1章命题逻辑Q∨RP→(Q∨R)0111011101111111P→(Q∨R)是可满足式表1.15

(P∨Q)↔(Q∨P)的真值表

PQ00011011第1章命题逻辑P∨QQ∨P(P∨Q)↔(Q∨P)011101111111(P∨Q)↔(Q∨P)是永真式第1章命题逻辑4、永真式的特点（1）永真式的否定为矛盾式，反之亦然；（2）永真式的“∧”、”∨”、”→”、”↔”仍为永真式；（3）由永真式可以产生许多恒等式。等价式第1章命题逻辑5、 等价式的定义 给定两个命题公式A和B,P1，P2，…，Pn为所有出现于A和B中的原子变元，若给n个命题变元P1，P2，…，Pn指派2n个可能的真值，命题公式A和B的真值都相同，则称公式A等价公式B，或：如果A↔BT，则A

B记作A

B。第1章命题逻辑例、利用真值表证明下列等价式1.

(P↔Q)

(P∨Q)∧

(P∧Q)2.P→(Q∨R)

(P∧

Q)→R3.P∧(P∨Q)

P表1.17

(P↔Q)、(P∨Q)∧

(P∧Q)的真值表

PQ00011011所以：(P↔Q)

(P∨Q)∧

(P∧Q)第1章命题逻辑P↔Q

(P↔Q)11000110P∨Q0111P∧Q0001

(P∧Q)1110(P∨Q)∧

(P∧Q)0110表1.18P→(Q∨R)、(P∧

Q)→R

的真值表PQR000001010011100101110111所以：P→(Q∨R)

(P∧

Q)→R第1章命题逻辑Q∨R01110111P→(Q∨R)11110111

Q11001100P∧

Q00001100(P∧

Q)→R11110111表1.19P∧(P∨Q)的真值表PQ00011011所以：P∧(P∨Q)

P第1章命题逻辑P∨Q0111P∧(P∨Q)0011第1章命题逻辑常见的等价式（1）交换律；（2）结合律；（3）分配律；（4）否定深入；（5）变元等同；（6）常值与变元的联结；（7）联结词的化归；（8）吸收律；第1章命题逻辑（1）交换律（∧、∨、↔）①P∧Q

Q∧P

Q∨P

Q↔P③P↔Q②P∨Q第1章命题逻辑（2）结合律（∧、∨、↔）①(P∧Q)∧RP↔(Q↔R)

P∧(Q∧R)②(P∨Q)∨RP∨(Q∨R)③(P↔Q)↔R第1章命题逻辑（3）分配律（∧对∨、∨对∧、→对→

）①P∧(Q∨R)(P→Q)→(P→R)(P∧Q)∨(P∧R)②P∨(Q∧R)(P∨Q)∧(P∨R)③P→(Q→R)证明：P∧(Q∨R)(P∧Q)∨(P∧R)PQR000001010011100101110111所以：P∧(Q∨R)(P∧Q)∨(P∧R)Q∨R01110111P∧(Q∨R)00000111P∧Q00000011P∧R00000101(P∧Q)∨(P∧R)00000111第1章命题逻辑第1章命题逻辑（4）否定深入①双重否定定律：PQ

P

P②德摩根定律：

(P∧Q)

P∨

Q

(P∨Q)

P∧

Q③(P↔Q)

P↔Q

P↔Q证明：

(P∧Q)

P∨

Q

PQ00011011所以：

(P∧Q)

P∨

Q

P∧Q0001

(P∧Q)1110P1100

Q1010

P∨

Q1110第1章命题逻辑第1章命题逻辑（5）变元等同①等幂律：P∧P

PP∨P

P②P∧

P

FP∨

P

T③P→P

TP→P

PP→P

P④P↔PTP↔PP↔PF第1章命题逻辑（6）常值与变元的联结①同一律：P∨F

PP∧T

P②零律：P∨T

TP∧F

F③T→P

PF→PTP→TTP→F

P④P↔TPP↔FP第1章命题逻辑（7）联结词的化归①P∧Q

P↔Q(P∨Q)②P∨Q

(P∧Q)③P→Q

P∨Q④P↔Q(P→Q)∧(Q→P)(P∨Q)∧(

Q∨P)(P∧Q)∨(P∧Q)证明：P↔Q(P∧Q)∨(P∧Q)PQ00011011所以：P↔Q(P∧Q)∨(P∧Q)P∧Q0001P1100

Q1010P∧

Q1000(P∧Q)∨(P∧

Q)1001P↔Q1001第1章命题逻辑第1章命题逻辑（8）吸收律①P∧(P∨Q)

②P∨(P∧Q)

PP第1章命题逻辑说明：(1)Q→P称为P→Q的逆换式；(2)ךP→ךQ称为P→Q的反换式；(3)ךQ→ךP称为P→Q的逆反式。注意：P→Q

Q→

P第1章命题逻辑6、 永真蕴涵式A称为B的逻辑前提,B称为A的逻辑结果；由A能推出B，B是由A推出的。若A→B

TA永真蕴涵B永真蕴涵式AB第1章命题逻辑证明永真蕴涵式的方法（1）真值表法:则AB；若A→BT，则AB；（2）假设前件A为真，若能证明后件B必为真，则AB；（3）假设后件B为假，若能证明前件A必为假，第1章命题逻辑例、试用不同的方法证明下列蕴涵式P∧(P→Q)

Q证明P∧(P→Q)

Q方法1真值表法：PQ00011011即：P∧(P→Q)

QP→Q11010001P∧(P→Q)(P∧(P→Q))→Q1111第1章命题逻辑证明P∧(P→Q)

Q方法2假设前件为真，证明后件必为真假设前件P∧(P→Q)为真即：P∧(P→Q)

Q真真真第1章命题逻辑证明P∧(P→Q)

Q方法3假设后件为假，证明前件必为假假设后件Q为假则对前件P∧(P→Q)中的P进行如下讨论：即：P∧(P→Q)

Q（1）P为真时：P∧(P→Q)（2）P为假时：P∧(P→Q)真假假假真假第1章命题逻辑第1章命题逻辑常见的永真蕴涵式（1）化简式：P∧Q

P，P∧Q

Q（2）附加式：P

P∨Q，QP∨Q（3）析取三段论：

P，P∨Q

Q（4）假言推论：P，P→Q

Q（5）拒取式：Q，P→Q

P（6）假言三段论：P→Q，Q→R

P→R（7）二难推论：P∨Q，P→R，Q→RR

注意：，即∧证明：析取三段论：

P，P∨Q

Q

假设前件

P，P∨Q为真，证明后件Q为真即

P，P∨Q

Q

P为真P∨Q为真P必为假真第1章命题逻辑证明：假言三段论：P→Q，Q→R

P→R假设后件P→R为假,证明前件P→Q,Q→R必为假：即P→Q，Q→R

P→RP→R为假P必为真R必为假对Q进行以下讨论：(1)Q为真时:(2)Q为假时:P→Q为真Q→R为假(P→Q)∧(Q→R)必为假P→Q为假Q→R为真(P→Q)∧(Q→R)必为假第1章命题逻辑第1章命题逻辑7、 代入规则和替换规则（1）代入实例；（2）代入规则；（3）替换规则（置换定理）；（4）等价式的证明方法；（5）代入规则和替换规则的不同点。第1章命题逻辑（1）、 代入实例WffB(P1，P2，…，Pi,…，Pn)命题变元WffAi代换所有出现WffAWffB的代入实例。注意：（1）只能代换命题变元；（2）代换该命题变元的所有出现；代入实例举例已知：命题公式(P∧Q)→(P∧R) 试用命题公式（A↔B）代换P的所有出现，得到以下的命题公式：

第1章命题逻辑(∧Q)→(∧R)(A↔B)(A↔B)第1章命题逻辑（2）、 代入规则 永真式的任何代入实例仍为永真式。第1章命题逻辑第4节 等价式（恒等式）和永真蕴涵式 代入规则举例P∨

P为永真式； 以命题公式：Q∧R代换命题变元P的所有出现；得到的命题公式：(Q∧R)∨

(Q∧R)永真式第1章命题逻辑（3）、 替换规则（置换定理）WffAWffA′子公式WffA′

WffB′替换WffB

注意：（1）实现的是等价变换；（2）不需要代换所有出现；第1章命题逻辑（4）证明等价式的方法（1）真值表法；（2）利用置换定理产生等价序列；证明

(

P∨

Q)∨

(

P∨Q)P方法一真值表法：PQ00011011第1章命题逻辑第4节 等价式（恒等式）和永真蕴涵式P1100

Q1010P∨

Q1110(P∨

Q)0001P∨Q1101(P∨Q)0010(P∨

Q)∨(P∨Q)0011

(

P∨

Q)∨

(

P∨Q)P证明

(

P∨

Q)∨

(

P∨Q)P方法二置换定理：

(

P∨

Q)∨

(

P∨Q)第1章命题逻辑(P∧Q)∨(P∧Q) (德摩根定律）P（分配率）P∧(Q∨Q) P∧T第1章命题逻辑（5）代入规则和替换规则的不同点（1）代入规则：被替换的是命题变元； 替换规则：被替换的可以是命题常量、命题 变元、合式公式；（2）替换规则：要求替换和被替换的合式公式必 须是等价的； 代入规则：不必；（3）代入规则：若对命题变元P使用代入规则， 则合式公式中所有P的出现均要 使用代入规则； 替换规则：不必。第1章命题逻辑例、证明下列等价式1.(A→D)∧(B→D)

(A∨B)→D2.((A∧B)→C)∧(B→(D∨C))

(B∧(D→A))→C3.P→(Q→R)

Q→(P→R)

ךR→(Q→ךP)证明：(A→D)∧(B→D)

(A∨B)→D左式

(A→D)∧(B→D)第1章命题逻辑(

A∨D)∧(

B∨D)

(A∨B)→D（分配率）(

A∧

B)∨D(德摩根定律）

(A∨B)∨D

右式证明：((A∧B)→C)∧(B→(D∨C))

(B∧(D→A))→C

左式

(

(A∧B)∨C)∧(

B∨(D∨C))

第1章命题逻辑

(B∧(D→A))→C(德摩根定律）

(

A∨

B∨C)∧(

B∨D∨C)（分配率）((

A∨

B)∧(

B∨D))∨C（分配率）(

B∨(

A∧D))∨C(德摩根定律）

(

B∨(A∨

D))∨C(德摩根定律)

(B∧(A∨

D))∨C

(B∧(D→A))∨C

右式证明：P→(Q→R)

Q→(P→R)

R→(Q→ךP)

左式

P∨(

Q∨R)第1章命题逻辑

R→(Q→ךP)

（交换率,结合律）

Q∨(

P∨R)

Q∨(P→R)

Q→(P→R)

Q∨

P∨R（交换率,结合律）

R∨(

Q∨

P)

R∨(Q→ךP)第1章命题逻辑功能完备集 设有一个联结词集合A，如果：（1）用A中的联结词能够表达任何命题公式；（2）删除A中的任何联结词得到一个联结词集合A′，至少有一个公式不可能用仅含于A′中的逻辑联结词的等价式表达出来，则集合A称为功能完备集。{ך,∧},{ך,∨}是功能完备集P→Q

P∨QP↔Q(P∧Q)∨(P∧Q)P∧Q(P∨Q)P∨Q(P∧Q)第1章命题逻辑第1章命题逻辑例、写出与下式等价并仅含{ך，∧}的最简式

P→(Q→R)

P∨(

Q∨R)(P∧Q∧

R)第1章命题逻辑第6节 范式和判定问题1、析取范式和合取范式2、主析取范式和主合取范式第1章命题逻辑1、析取范式和合取范式（1）基本积和基本和（2）析取范式（3）合取范式（4）求合取范式或析取范式的步骤第1章命题逻辑（1）基本积和基本和 合式公式中的一些变元和一些变元的否定的合取，称为基本积； 合式公式中的一些变元和一些变元的否定的析取，称为基本和；如：P∧

Q如：

P∨R∨

Q第1章命题逻辑（2）析取范式注意：一个命题公式的析取范式不唯一

WffA由基本积的和组成的公式

A的析取范式A

A1∨A2∨…∨Ann≥1记作：基本积第1章命题逻辑（3）合取范式注意：一个命题公式的合取范式不唯一

WffA由基本和的积组成的公式

A的合取范式A

A1∧

A2∧

…∧

Ann≥1记作：基本和(4)求合取范式或析取范式的步骤将公式中的联结词化归成∧、∨、

；利用德•摩根定律将否定符号

直接移到各个命题变元之前；利用分配律、结合律将公式化为合取范式或析取范式。第1章命题逻辑析取范式和合取范式举例求(P∧(Q→R))→S的合取范式求

(P∨Q)

↔(P∧Q)的析取范式第1章命题逻辑求(P∧(Q→R))→S的合取范式基本和基本和第1章命题逻辑(P∧(Q→R))→S

(P∧(

Q∨R))∨S（德摩根定律）(P∨

(

Q∨R))∨S（德摩根定律）(P∨(Q∧

R))∨S（分配律）((P∨Q)∧(P∨

R))∨S（分配律）(P∨Q∨S)∧(P∨

R∨S)（合取范式）求

(P∨Q)↔(P∧Q)的析取范式

(P∨Q)↔(P∧Q)(P∧

Q)↔(P∧Q)（德摩根定律）(()∧())∨(()∧

())

P∧

QP∧Q

P∧

QP∧Q(

P∧

Q∧P∧Q)∨((P∨Q)∧(

P∨

Q))F∨((P∨Q)∧(

P∨

Q))(P∨Q)∧(

P∨

Q)（合取范式）((P∨Q)∧

P)∨((P∨Q)∧

Q)（分配律）

(P∧

P)∨(Q∧

P)∨(P∧

Q)∨(Q∧

Q)（分配律）

(

P∧Q)∨(P∧

Q)（析取范式）第1章命题逻辑2、主析取范式和主合取范式（1）极小项（2）主析取范式（3）极大项（4）主合取范式（5）主析取范式和主合取范式的求法（6）主析取范式和主合取范式的关系（7）极大项和极小项的关系（8）主析取范式和主合取范式的作用第1章命题逻辑（1）极小项编码原则：极小项中命题变元的否定对应着“0”；命题变元本身对应着“1”。

WffA中含有n个命题变元每个变元与其否定必出现且仅出现一次极小项基本积第1章命题逻辑例、写出两个命题变元的极小项及其真值表 两个命题变元的极小项及真值表PQ极小项编码mi00011011P∧Qm0P∧Qm1P∧Qm2P∧Qm3第1章命题逻辑例、写出三个命题变元的极小项及其真值表 三个命题变元的极小项及真值表PQR极小项编码mi000001010011100101110111P∧Q∧Rm0P∧Q∧Rm1P∧Q∧Rm2P∧Q∧Rm3P∧Q∧Rm4P∧Q∧Rm5P∧Q∧Rm6P∧Q∧Rm7第1章命题逻辑关于极小项的几点说明：

①n个命题变元共有2n个可能极小项。②没有两个极小项是等价的。③每个极小项都只对应一组真值指派，使 得该极小项的真值为T。例:P∧Q∧R100T第1章命题逻辑（2）主析取范式注意：除永假式外，任一Wff的主析取范式必存在 且唯一。WffWWffH由极小项的析取组成

WffW主析取范式第1章命题逻辑（3）极大项注意：极大项中命题变元的否定对应着“1”；命题变元本身对应着“0”。

WffA中含有n个命题变元每个变元与其否定必出现且仅出现一次极大项基本和第1章命题逻辑例、写出两个命题变元的极大项及其真值表 两个命题变元的极大项及真值表PQ极大项编码Mi00011011P∨QM0P∨

QM1P∨QM2P∨QM3第1章命题逻辑例、写出三个命题变元的极大项及其真值表 三个命题变元的极大项及真值表PQR极大项编码Mi000001010011100101110111P∨Q∨RM0P∨Q∨RM1P∨Q∨RM2P∨Q∨RM3P∨Q∨RM4P∨Q∨RM5P∨Q∨RM6P∨Q∨RM7第1章命题逻辑关于极大项的几点说明：

①n个命题变元共有2n个可能的极大项。②没有两个极大项是等价的。③每个极大项都只对应一组真值指派，使 得该极大项的真值为F。例:P∨Q∨R011F第1章命题逻辑（4）主合取范式注意：除永真式外，任一Wff的主合取范式必存在 且唯一。WffWWffH由极大项的合取组成

WffW的主合取范式第1章命题逻辑（5）主析取范式和主合取范式的求法①真值表法；②推导法；第1章命题逻辑①真值表法 主析取范式：一个Wff的真值表中真值为“1”的各种真值指派对应的极小项的析取，为该Wff的主析取范式； 主合取范式：一个Wff的真值表中真值为“0”的各种真值指派对应的极大项的合取，为该Wff的主合取范式；第1章命题逻辑例、用真值表法求下式的

主析取范式和主合取范式P→(Q∧R)P→(Q∧R)的真值表PQR极大(小)项编码Mi(

mi)000001010011100101110111Q∧R00010001P→(Q∧R)11110001P∧Q∧Rm0P∧Q∧Rm1P∧Q∧Rm2P∧Q∧Rm3P∧Q∧Rm7P∨Q∨RM4P∨Q∨RM5P∨Q∨RM6第1章命题逻辑P→(Q∧R)的

主析取范式和主合取范式P→(Q∧R)

(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)

m0∨m1∨m2∨m3∨m7∑(m0,m1,m2,m3,m7)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)

M4

∧M5∧M6∏(M4,M5,M6)第1章命题逻辑②推导法a、消去逻辑联结词→和↔；b、化为析取范式或合取范式；c、添加缺少的命题变元；第1章命题逻辑(1)主析取范式合取一个缺少变元的永真式(如：

P∨P)，然后应用分配律展开公式。添加缺少的命题变元Q∧R基本积WffA中含有P,Q,R三个命题变元缺少变元P

(Q∧R)∧(P∨P)

(P∧Q∧R)∨(P∧Q∧R)缺少变元P的永真式极小项第1章命题逻辑添加缺少的命题变元(2)主合取范式析取一个缺少变元的永假式(如：

P∧P)，然后应用分配律展开公式Q∨R基本和WffA中含有P,Q,R三个命题变元缺少变元P

(Q∨R)∨(P∧P)

(P∨Q∨R)∧(P∨Q∨R)缺少变元P的永假式极大项第1章命题逻辑第6节 主析取范式和主合取范式例、用推导法求下式的

主析取范式和主合取范式P→(Q∧R)P∨(Q∧R)(P∨Q)∧(P∨R)((P∨Q)∨(R∧R))∧((P∨R)∨(Q∧Q))(P∨Q∨R)∧(P∨Q∨

R)∧(P∨R∨Q)∧(P∨RQ)(P∨Q∨R)∧(P∨Q∨

R)∧(P∨Q∨R)∧(P∨Q∨R)(P∨Q∨R)∧(P∨Q∨

R)∧(P∨Q∨R)

M4

∧M5∧M6∏(M4,M5,M6)(主合取范式)第1章命题逻辑（6）主析取范式和主合取范式的关系 二者是互补的关系，即如果某个mi在主析取范式中出现，则Mi一定不在主合取范式中出现。注意：只要求出主析取范式或主合取范式中的任何一种，另外一种范式根据互补关系就可以相应写出。第1章命题逻辑（7）极小项和极大项的关系mi

MiMi

mi例：m3：P∧Q∧R

m3(P∧Q∧R)P∨Q∨R

M3011第1章命题逻辑第6节 主析取范式和主合取范式（8）主析取范式和主合取范式的作用①判断两个公式是否等价：②判断wff是否是永真式：③判断wff是否是永假式：wffG的主合(析)取范式wffH的主合(析)取范式

G

H主析取范式中所有的极小项均出现不存在主合取范式主合取范式中所有的极大项均出现不存在主析取范式第1章命题逻辑例、求下式的主析取范式和主合取范式(1)(P∧Q)∨(

P∧R)(2)(P→Q∧R))∧(

P→(

Q∧

R))(3)(Q→P)∧(

P∧Q)(1)(P∧Q)∨(

P∧R)推导法第1章命题逻辑(P∧Q)∨(

P∧R)∧(

R∨R)∧(

Q∨Q)析取范式缺少变元R缺少变元Q

(P∧Q∧

R)∨(P∧Q∧R)∨(

P∧R∧

Q)∨(

P∧R∧Q)

(P∧Q∧

R)∨(P∧Q∧R)∨(

P∧

Q∧R)∨(

P∧Q∧R)

m6∨m7∨m1∨m3110111001011∑(m1,m3,m6,m7)

M0∧M2∧M4∧M5∏(M0,M2,M4,M5)(P∨Q∨R)∧(P∨

Q∨R)∧(P∨Q∨R)∧(P∨Q∨

R)000010100101(1)(P∧Q)∨(

P∧R)真值表法PQR000001010011100101110111第1章命题逻辑P∧Q00000011

P11110000

P∧R01010000(P∧Q)∨(

P∧R)01010011编码M0M2M4M5m1m3m6m7第1章命题逻辑(2)(P→Q∧R))∧(

P→(

Q∧

R))推导法原式

(

P∨(Q∧R))∧(P∨(

Q∧

R))

(

P∨Q)∧(

P∨R)∧(P∨

Q)∧(P∨

R)

(

P∨Q)∧(

P∨R)∧(P∨

Q)∧(P∨

R)∨(

R∧R)∨(

Q∧Q)∨(

R∧R)∨(

Q∧Q)分配率析取范式析取缺少变元的永假式

(

P∨Q∨

R)∧(

P∨Q∨R)∧(

P∨R∨

Q)∧(

P∨R∨Q)∧(P∨

Q∨

R)∧(P∨

Q∨R)∧(P∨

R∨

Q)∧(P∨

R∨Q)分配率

M5∧M4∧M6∧M3∧M2∧M1∏(M1,M2,M3,M4,M5,M6)

m0∨m7∑(m0,m7)

(

P∧

Q∧

R)∨(P∧Q∧R)(2)(P→Q∧R))∧(

P→(

Q∧

R))真值表法

PQR000001010011100101110111第1章命题逻辑Q∧R00010001P→(Q∧R)11110001

P11110000

Q11001100

R10101010

Q∧

R10001000

P→(

Q∧

R)10001111原式10000001编码m0m7M1M2M3M4M5M6(3)(Q→P)∧(

P∧Q)推导法

第1章命题逻辑原式

(

Q∨P)∧(

P∧Q)分配率

(

P∧Q∧

Q)∨(

P∧Q∧P)FF

F

M0∧M1∧M2∧M3

∏(M0,M1,M2,M3)

(P∨Q)∧(P∨

Q)∧(

P∨Q)∧(

P∨

Q)

(3)(Q→P)∧(

P∧Q)真值表法PQ00011011第1章命题逻辑Q→P1011

P1100

P∧Q01000000编码(Q→P)∧(

P∧Q)M0M1M2M3第1章命题逻辑第7节 命题演算的推论理论第7节 命题演算的推论理论1、有效结论2、形式证明3、推论规则第1章命题逻辑第7节 命题演算的推论理论1、 有效结论H1，H2，…，Hn，C命题公式当且仅当H1∧H2∧…∧Hn

C时则C是{H1，H2，…，Hn}的有效结论。前提集合第1章命题逻辑第7节 命题演算的推论理论2、 形式证明

构造命题序列来描述推理过程，命题序列中的命题或者是前提，或者是前提推出的中间结果，其中最后一个命题就是结论。(1)WffG1(2)WffG2(3)WffG3

……(n)WffC(前提Hi)(中间结果)（结论）第1章命题逻辑第7节 命题演算的推论理论3、 推论规则(1)P规则（前提引用规则）(2)T规则（结论引用规则）(3)CP规则（条件证明规则）(4)F规则（间接证明法）第1章命题逻辑第7节 命题演算的推论理论（1）、 P规则（前提引用规则） 在推理过程中从前提集合中任取且仅取一个前提称使用一次P规则。第1章命题逻辑第7节 命题演算的推论理论（2）、 T规则（结论引用规则） 在推理过程中，使用前面推论过程中所得到的中间结果，称使用一次T规则。注意：直接证明方法实质上就是：假设前件为真 证明后件必为真的方法。注意：命题序列中均为真命题。第1章命题逻辑第7节 命题演算的推论理论例、使用推论规则证明结论的有效性

(P∧Q)，Q∨R，R

P

(P∧Q)，Q∨R，R

P第1章命题逻辑第7节 命题演算的推论理论(1)R

(P规则)(2)Q∨R(P规则)(3)Q(T规则,(1)(2))(4)

(P∧Q)

(P规则)(5)

P(T规则,(3)(4))FF第1章命题逻辑第7节 命题演算的推论理论例、符号化并证明结论的有效性（1）如果我学习，那么我不放松数学；（2）如果我不打篮球，那么我就学习；（3）我放松了数学；结论：我打篮球了。确定原子命题P:我学习；Q:我放松数学;R:我打篮球第1章命题逻辑第7节 命题演算的推论理论符号化（1）如果我学习，那么我不放松数学；（2）如果我不打篮球，那么我就学习；（3）我放松了数学；结论：我打篮球了。第1章命题逻辑第7节 命题演算的推论理论P→QR→PQR使用推论规则证明结论的有效性第1章命题逻辑第7节 命题演算的推论理论(1)QP→Q,R→P,Q

R(P规则)(2)P→Q(P规则)(3)P (T规则,(1)(2))(4)R→P(P规则)(5)R(T规则,(3)(4))FFFF第1章命题逻辑第7节 命题演算的推论理论（3）、 CP规则（条件证明规则）

设H1，H2，…，Hn，P，Q是命题公式，若:H1∧H2∧…∧Hn∧P注意：CP规则用在结论为单条件的情况下

Q则:H1∧H2∧…∧Hn

P→Q第1章命题逻辑第7节 命题演算的推论理论

CP规则的使用方法使用条件:结论为单条件P→Q使用方法:前提集合Q前提集合P→Q第1章命题逻辑第7节 命题演算的推论理论例、符号化并证明结论的有效性(a)或者是天晴，或者是下雨；(b)如果是天晴,则开运动会；(c)如果开运动会，则停课；结论:如果不停课，则天在下雨。确定原子命题P：天晴；Q：天下雨；R：开运动会；S：停课；第1章命题逻辑符号化(a)或者是天晴，或者是下雨；

(b)如果是天晴,则开运动会；

(c)如果开运动会，则停课；结论:如果不停课，则天在下雨。第1章命题逻辑P∨QP→RR→S

S→Q使用CP规则证明结论的有效性第1章命题逻辑P∨Q,P→R,R→S

S→Q(1)

S(P规则，附加前提)(2)R→S(P规则)F(3)R(T规则,(1)(2))(4)P→R(P规则)F(5)P(T规则,(3)(4))(6)P∨Q(P规则)T(7)Q(T规则,(5)(6))(8)

S→Q(CP规则，(1)(7))第1章命题逻辑第7节 命题演算的推论理论一致性和非一致性H1，H2，…，Hn命题公式当且仅当:真值指派使得H1∧H2∧…∧Hn的真值为T时，则称:H1，H2，…，Hn是一致的；如果对于每一组真值指派均使得H1∧H2∧…∧Hn的真值为F则称:H1,H2,…,Hn是非一致的。第1章命题逻辑第7节 命题演算的推论理论（4）、 F规则（间接证明法）注意：F规则用在由前提集合不能直接推出结论的情况命题公式集合{H1，H2，…，Hn}一致性的C命题公式若:集合{H1，H2，…，Hn，C}非一致的则C是前提集合{H1，H2，…，Hn}的有效结论若:H1∧H2∧…∧Hn∧C

F则:H1∧H2∧…∧Hn

C第1章命题逻辑第7节 命题演算的推论理论F规则的使用方法F规则的使用条件:前提很少由前提集合不能直接推出结论F规则的使用方法:结论

∧前提集合

FP∧P有效结论假设前提第1章命题逻辑第7节 命题演算的推论理论例、使用F规则证明结论的有效性(1)A→B，

(B∨C)

A(2)P∨Q，P→R，Q→S

S∨R(3)A→(B→C)，

D∨A，B

D→C(1)A→B，

(B∨C)

A第1章命题逻辑(1)

(B∨C)(P规则)(2)

B∧

C(T规则，(1))(3)

B (T规则，(2))(4)A→B(P规则)FF(5)

A (T规则，(3)(4))第1章命题逻辑(1)A→B，

(B∨C)

A(1)

A

(P规则，）假设前提(2)A(T规则，(1))(3)A→B(P规则)(4)B(T规则，(2)(3))(5)

(B∨C)(P规则)(6)

B∧

C(T规则，(5))(7)

B(T规则，(6))(8)B∧

B (T规则，(4)(7),)矛盾式(9)

A (F规则，(1)(8))(2)P∨Q，P→R，Q→S

S∨R第1章命题逻辑(1)(S∨R)

(P规则，）假设前提(2)

S∧

R(T规则，(1))(3)

S(T规则，(2))(4)

R(T规则，(2))(5)P→R(P规则）(6)

PF(T规则，(4)(5))(7)Q→S(P规则）(8)

QF(T规则，(3)(7))(9)P∨Q(P规则）(10)PF(T规则，(8)(9))(11)

P∧P(T规则，(6)(10),)矛盾式(12)S∨R(，(1)(11))F规则第1章命题逻辑(1)(D→C)

(P规则，）假设前提(2)(D∨C)(T规则，(1))(3)D∧

C(T规则，(2))(4)D(T规则，(3))(5)

C(T规则，(3))(6)

D∨A(P规则）(7)AF(T规则，(4)(6))(8)A→(B→C)(P规则）(9)B→C (T规则，(7)(8))(10)B(P规则）(11)C(T规则，(9)(10))(12)

C∧C(T规则，(5)(11),)矛盾式(13)D→C(，(1)(12))F规则第2章谓词逻辑第2章谓词逻辑第1节谓词逻辑的基本概念第2节谓词逻辑的合式公式（谓词公式）第3节谓词逻辑的等价式和永真蕴涵式第4节谓词逻辑中的推论理论第2章谓词逻辑命题逻辑的弱点1、表达能力差2、推理能力差第2章谓词逻辑1、表达能力差P：王强是大学生Q：张丽是大学生第2章谓词逻辑2、推理能力差例：苏格拉底三段论：凡人必死，苏格拉底是人，故苏格拉底必死。PQRPQR?第2章谓词逻辑第1节 谓词逻辑的基本概念第1节谓词逻辑的基本概念1、个体2、谓词3、命题函数4、个体域5、个体变元6、命题函数应注意的三点7、将命题函数变成命题的方法8、全称量词9、存在量词10、辖域11、量词的含义第1节 谓词逻辑的基本概念1、个体注意：个体间的次序不能随意颠倒。独立存在的事物抽象的具体的用小写的英文字母表示第2章谓词逻辑第1节 谓词逻辑的基本概念个体举例（1）李红是大学生。（2）李红和李兰是姐妹。（3）上海位于南京和杭州之间。第2章谓词逻辑第1节 谓词逻辑的基本概念2、谓词注意：单独的谓词不是完整的命题，只有加入个体才能成为命题。第2章谓词逻辑用来刻划个体的性质或个体之间关系的词。用大写的英文字母表示一元谓词：和一个个体相联，刻划个体的性质；多元谓词：和多个个体相联，刻划个体间的关系第1节 谓词逻辑的基本概念谓词逻辑的表示方法第2章谓词逻辑(1)一元谓词:“b是A”A(b)(2)二元谓词:“a是小于b的”B(a,b)(3)n元谓词:联结n个个体A(a1,a2,…,an)第1节 谓词逻辑的基本概念谓词逻辑的举例第2章谓词逻辑谓词:H：能够到达山顶个体:l:李四；t:老虎；c:汽车；H(l):H(t):H(c):李四能够到达山顶。老虎能够到达山顶。汽车能够到达山顶。第1节 谓词逻辑的基本概念谓词逻辑的举例(续)第2章谓词逻辑H(l)、H(t)、H(c):表示三个不同的命题共同的形式H(x)H(x):个体变元x能够到达山顶。S(x,y):x和y是姐妹。T(x,y,z):x在y和z之间。第1节 谓词逻辑的基本概念3、命题函数第2章谓词逻辑一个n元谓词An个个体变元a1,a2,…,anA(a1,a2,…,an)命题函数第1节 谓词逻辑的基本概念4、个体域、全总个体域个体的变化范围称为个体域。所有个体域的总和称为全总个体域。第2章谓词逻辑第1节 谓词逻辑的基本概念5、个体变元以某个个体域为变域的变元称为个体变元。第2章谓词逻辑第1节 谓词逻辑的基本概念谓词逻辑的举例主谓结构：我高兴。主谓宾结构：我有辆自行车。主谓宾宾结构：我给他一本书。第2章谓词逻辑S(x):x高兴。H(x,y):x有y。G(x,y,z):x给y一个z。第1节 谓词逻辑的基本概念谓词逻辑的优点（1）把内涵表示出来了；（2）把同一类的命题用命题函数表示出来。第2章谓词逻辑第1节 谓词逻辑的基本概念6、命题函数应注意的三点（1）命题函数不是命题，只有把特定的个体代入时才是命题；（2）个体变元的取值有一个范围（个体域）；（3）个体变元的顺序不能颠倒。第2章谓词逻辑第1节 谓词逻辑的基本概念个体变元的取值范围举例S(x):x是大学生。(1)若x的范围是信息学院2017级学生(2)若x的范围是大连海事大学的所有师生

(3)若x的范围是大连海事大学的附校学生第2章谓词逻辑S(x)是永真式S(x)是可满足式S(x)是永假式第1节 谓词逻辑的基本概念7、将命题函数变成命题的方法（1）用个体域中的特定的个体去替换所有的个体变元；（2）在个体域上将命题函数量化。量词：全称量词、存在量词第2章谓词逻辑第1节 谓词逻辑的基本概念引进量词的举例（1）所有的大学生都要参加军训；（2）有些大学生是三好优秀生；第2章谓词逻辑第1节 谓词逻辑的基本概念符号化（1）所有的大学生都要参加军训；谓词：…参加军训；个体：大学生；第2章谓词逻辑MxM(x)：大学生要参加军训；没有表示出来第1节 谓词逻辑的基本概念符号化（2）有些大学生是三好优秀生；谓词：…是三好优秀生；个体：大学生；第2章谓词逻辑大学生是三好优秀生；HxH(x)：没有表示出来第1节 谓词逻辑的基本概念8、全称量词第2章谓词逻辑(

x)(

x)P(x)谓词个体变元对于个体域中的所有个体x，谓词P(x)均为真(

x)“所有的”“每一个”“任何一个”第1节 谓词逻辑的基本概念9、存在量词第2章谓词逻辑(

x)(

x)P(x)在个体域中存在某个个体x，使得谓词P(x)为真(

x)“存在一个”“某一个”“有些”“某些”第1节 谓词逻辑的基本概念10、辖域第2章谓词逻辑(

x)P(x)(

x)的辖域作用范围(

x)P(x)(

x)的辖域第1节 谓词逻辑的基本概念特性谓词

第2章谓词逻辑限制个体变元取值范围的谓词特性谓词的作用:全总个体域实际的个体域第1节 谓词逻辑的基本概念特性谓词与逻辑联结词的对应关系第2章谓词逻辑(

x)“→”(

x)(→)特性谓词(

x)“∧”(

x)(∧)特性谓词第1节 谓词逻辑的基本概念例、将下列命题符号化（1）所有的大学生都要参加军训；（2）有些大学生是三好优秀生；（3）没有不犯错误的人；（4）发光的不都是金子；（5）每一个有理数都是实数；（6）某些实数是有理数；第2章谓词逻辑第1节 谓词逻辑的基本概念（1）所有的大学生都要参加军训；特性谓词第2章谓词逻辑S(x)：x是大学生；M(x):x要参加军训；符号化结果：(

x)(→)S(x)M(x)个体域第1节 谓词逻辑的基本概念（2）有些大学生是三好优秀生；第2章谓词逻辑特性谓词:S(x)：x是大学生；G(x):x是三好优秀生；符号化结果：(

x)(∧)S(x)G(x)个体域第1节 谓词逻辑的基本概念（3）没有不犯错误的人；第2章谓词逻辑特性谓词:P(x)：M(x):x是要犯错误的；符号化结果：

(

x)(∧)P(x)

M(x)(

x)(→)P(x)M(x)x是人；个体域第1节 谓词逻辑的基本概念（4）发光的不都是金子；特性谓词第2章谓词逻辑个体域L(x)：x是发光的G(x)：x是金子；符号化结果：(

x)(∧)L(x)

G(x)第1节 谓词逻辑的基本概念（5）每一个有理数都是实数；第2章谓词逻辑特性谓词Q(x)：x是有理数R(x)：x是实数；符号化结果：(

x)(→)Q(x)R(x)个体域第1节 谓词逻辑的基本概念（6）某些实数是有理数；第2章谓词逻辑特性谓词个体域R(x)：x是实数；Q(x)：x是有理数符号化结果：(

x)(∧)R(x)Q(x)第1节 谓词逻辑的基本概念例、判断下列命题的真假值R(x):x是实数；P(x):x2-1=(x+1)(x-1)Q(x):x+3=2（1）(

x)(R(x)→P(x))（2）(

x)(R(x)∧Q(x))（3）(

x)(R(x)∧P(x))（4）(

x)(R(x)→Q(x))第2章谓词逻辑第1节 谓词逻辑的基本概念（1）(

x)(R(x)→P(x))(

x)(R(x)→P(x))表示： 对于任意的x，如果x是实数，则必有

x2-1=(x+1)(x-1)该命题是真命题。第2章谓词逻辑第1节 谓词逻辑的基本概念（2）(

x)(R(x)∧Q(x))(

x)(R(x)∧Q(x))表示： 存在x，x是实数，并且x+3=2该命题是真命题。第2章谓词逻辑第1节 谓词逻辑的基本概念（3）(

x)(R(x)∧P(x))(

x)(R(x)∧P(x))表示：

存在x，x是实数，并且x2-1=(x+1)(x-1)该命题是真命题。第2章谓词逻辑第1节 谓词逻辑的基本概念（4）(

x)(R(x)→Q(x))(

x)(R(x)→Q(x))表示： 对于任意的x，如果x是实数，则必有x+3=2该命题是假命题。第2章谓词逻辑第1节 谓词逻辑的基本概念11、量词的含义设个体域x={a1,a2,…,an}则：第2章谓词逻辑(

x)P(x)＝P(a1)P(a2)……P(an)∧∧∧(

x)P(x)＝P(a1)P(a2)……P(an)∨∨∨第1节 谓词逻辑的基本概念量词是不可交换的(

y)(

x)P(x，y)第2章谓词逻辑(

x)(

y)P(x，y)第1节 谓词逻辑的基本概念例、量词不可交换性举例个体域：人P(x,y):y是x的母亲；(

y)(

x)P(x，y)：(

x)(

y)P(x，y)：第2章谓词逻辑有一个人是所有人的母亲任何人都有自己的母亲。假真第2章谓词逻辑第2节 谓词逻辑的合式公式第2节谓词逻辑的合式公式1、谓词公式的递归定义2、约束变元3、自由变元4、约束变元的改名规则5、自由变元的代入规则第2章谓词逻辑第2节 谓词逻辑的合式公式1、谓词公式的递归定义(1)原子谓词公式是Wff;

(2)如果A是Wff，则

A是Wff；(3)如果A和B是Wff，则(A∧B)、(A∨B)、(A→B)、(A↔B)都是Wff；(4)如果A是Wff，x是A中出现的