1） p?q 2） p 3） q 4）?p?r 5）r 6）?q?s 7) s 8)r?s
Qn?nM.其中每个若每个Q为?和?，M为不含
前束范式（一个谓词公式A，若具有形式Q1?1Q2?2L量词的谓词公式，则称谓词公式A为前束范式）
求解步骤
1）将公式化为只含3个联结词?,?,?的形式
2）利用?(?p)?p、德摩根律及两次转换律等将公式中的所有?以到原子公式前面。（可以将约束变元换名）
3）利用量词辖域收缩及扩张律、量词分配律等，将所有量词提到公式最前面。
第一步：否定深入 。即利用量词转化公式 ，把否定联结
词深入到命题变元和 谓词填式的 前面 。
第二步：改名 。即利用换名规则 、代入规则更换一些变元的
名称 ， 以便消除混乱 。
第三步：量词前移 。即利用量词辖域的收缩与扩张把移到
前面 。
这样便可求出与公式 等价的前束范式。
例：求??xP?x???yQ(x,y) 的前束范式
??xP?x???yQ(x,y)??xP?x???yQ(x,y)??x?yP?x??Q(x,y) ?x的辖域是P?x???yQ(x,y) 约束变元为x，y
?y 的辖域是Q(x,y) 约束变元为y，自由变元为x
谓词演算的推理规则
1、全称量词消去规则（UI规则）
?xA(x)?A(y)或?xA(x)?A(c)
成立条件：
① x是A(x)中自由出现的个体变元；
② y是任意的不在 A(x)中约束出现的个体变元； ③ y可以去个体 域中的任意c
2、存在量词消去规则（EI规则）
?xA(x)?A(c)
成立的条件：
① c是个体域中使 A成立的特定个体常元； 成立的特定个体常元； ② c不曾在 A(x)中出现过；
③ A(x)中除 x外还有其他自由出现的个体变元时，不能用此规则。 外还有其他自由出现的个体变元时，不能用此规则。 外还有其他自由出现的个体变元时，不能用此规则。 外还有其他自由出现的个体变元时，不能用此规则。 外还有其他自由出现的个体变元时，不能用此规则。
3、全称量词引入规则（UG规则）
A(y)??xA(x)
成立的条件
① y是A(y)中自由出现的个体变元， y取个体域中的任何值， A都为真；
② 取代 y的x不能在 A(x)中 4、存在量词引入规则（EG规则）
A(c)??cA(c)
成立条件
① y是A(y)中自由出现的个体变元， y取个体域中的任何值， A都为真；
② 取代 y的x不能在 A(x)中
例：所有的自然数都是整数，某些自然数是偶数。所以某些整数是偶数。
A(x)：x是整数
B(x)：x是自然数 C(x)：x是偶数
前提：?x(B(x)?A(x)),?x(B(x)?C(x))
结论：?x(A(x)?C(x)
1) ?x(B(x)?C(x) 2) B(c)?C(c) 3) B(c) 4) C(c)
EI 化简 化简 UI
3），6）假言推论 4），7）附加 EU
5) ?x(B(x)?A(x)) 6) B(c)?A(c) 7) A(c)
8) A(c)?C(c)
9) ?x(A(x)?C(x)
证明集合恒等的方法 集合恒等定义
命题演算 集合恒等式 名称 恒等律 支配律 幂等律 双重否定律 交换律 结合律 分配律 德摩根律 吸收律 补律 等式 A???A,A?E?A A?E?E,A???? A?A?A,A?A?A :?:A??A A?B?B?A,A?B?B?A A??B?C???A?B??C,A??B?C???A?B??C A??B?C???A?B???A?C?,A??B?C???A?B???A?C? :?A?B??:A?:B,:?A?B??:A?:B A??A?B??A,A??A?B??A A??:A???,A??:A??E 例
证明?A?B???A?:B??A 方法一：命题演算 对任意x,x??A?B???A?:B? ?x??A?B??x??A?:B? ??x?A?x?B???x?A?x?B? ???x?A?x?B??x?A????x?A?x?B??x?B??x?A 方法二：集合恒等式 ?A?B???A?:B? ???A?B??A????A?B??:B?. ??A?A???B?A???A?:B???B?:B??A.
关系的五条性质
1、 自反关系
设R是集合 A上的一个关系，如果对 A中的 每一个元素 x，均有
?x,x??R则称 R是自反关系 ，即 Ｒ是自反的??x(x?A??x,x??R)
2、 反自反关系
设R是集合 A上的一个关系，如果对 A中的每一个元素 x，均有
?x,x??R则称 R是反自关系，即 R是反自的??x(x?A??x,x??R)
3、 对称关系
设R是A上的一个关系，如果对 A中的 任意 元素 x和 y，如有
?x,y??R，必有?y,x??R，则称 R是对称关系 ，即 R是对称的??x?y(x,y?A??x,y??R??y,x??R)
4、 反对称关系
设R是A上的一个关系，如果对 A中的 任意 元素 x和y， 若
?x,y??R和?y,x??R，就必有 x=y，则称 R是反对称关系 ，即
R是反对称的??x?y(x?A?y?A??x,y??R??y,x??R?x?y) 若关系 R是反对称的，当 x≠y时，?x,y??R，则?y,x??R
5、 传递关系
设R是A上的一个关系， x、y、z是A中的元素，若?x,y??R，?y,z??R，必有?x,z??R，则称 R是传递关系 ， 即
R是传递的 ??x?y?z(x?A?y?A?z?A??x,y??R??y,z??R??x,z??R)
例 设R1，R2是集合X上的任意二元关系，证明或反驳命题。 1) 如果R1，R2是自反的，则R1oR2也是自反的。、 1) R1oR2={(x,z)|x?X?z?X??y(y?X?(x,y)?R2?(y,z)?R1} ?x(x?R1??x,x??R1) ?z(z?R2??z,z??R2) 当x=z 时、 当x≠z时 R1oR2=?，则 R1oR2是自反的
闭包
设R是非空集合A上的二元关系，如果A上的关系R'满足
(1)R'是自反的(对称的或传递的)；（具备所需性质） (2)R'?R；（包含R）
(3)对A上的任何自反(对称或传递)关系R″，都有R''?R'。 （最小性） 自反闭包 r（R）
r?R??RUIA?RUR0 对称闭包 s（R） 例
s?R??RUR?1
i t?R??RUR2UR3L?UnRi传递闭包 t（R）
设集合A?{a,b,c,d},R1,R2都是A上的二元关系，R1={（a,b),(b,c),(c,a)}，、
R2??,试求的自反闭包，对称闭包，传递自包。
r(R)?（{a,b),(b,c),(c,a),(a,a),(b,b),(c,c),(d,d)}
1s(R1)?（{a,b),(b,c),(c,a),(b,a),(c,b),(a,c)}
离散数学期中课程报告
