离散数学总结 1.ppt

离散数学总结 1.ppt解:
由真值表
主合取范式:
( PQ R) ( PQR) (P QR) (PQR)
=M101 M100  M010  M000
主析取范式与主合取范式的简记式中的下标是“互补”的.
Why?
利用真值表求(P  Q) ( P R)的主析取范式与主合取范式.
P
T
T
T
T
F
F
F
F
Q
T
T
F
F
T
T
F
F
R
T
F
T
F
T
F
T
F
 P R
F
F
F
F
T
F
T
F
(P  Q) ( P R)
T
T
F
F
T
F
T
F
P  Q
T
T
F
F
F
F
F
F
五、对偶与范式
(7) 一切人都不一样高.
(x)(y)(F(x)  F(y)  H(x, y)  L(x, y))
解:
引入特性谓词 F(x) :
L(x, y) : x与y一样高. H(x, y):x与y不是同一个人. 则命题符号化为:
(8) 每个自然数都有后继数.
解:
引入特性谓词 F(x) :
H(x, y):y是x的后继数. 则命题符号化为:
(x)(F(x) (y) (F(y)  H(x, y))
一、谓词逻辑命题符号化的有关概念与方法
(9) 有的自然数无先驱数.
解:
引入特性谓词 F(x) :
H(x, y)::
(x)(F(x) (y)(F(y)  H(x,y))
(10) 有的有理数是整数. (个体域为实数集)
解:
引入特性谓词 F(x) :
G(x)::
(x)(F(x)  G(x))
HW: 2-1, 2-2习题
(1)a,c,e,f,h
(2)a,b,c,d,f
一、谓词逻辑命题符号化的有关概念与方法
解:
(2) (x)(P Q(x))
又R(a)为F,所以
 F
(2) (x)(P Q(x))R(a),其中P:2>1. Q(x): x  3; R(x): x > 5; a: 5;论域{-2,3, 6}.
(P Q(-2)) (P Q(3)) (P Q(6))
(T  T)(T  T)(T  F)
 T  T  F
F  F
(x)(P Q(x)) R(a)
F.
二、谓词公式
HW:2-3习题
(5);(7)
2-4习题
(2)c,d;(4)
2-5习题
(2) a,d
(Ⅲ) 量词作用域的扩张与收缩等价式
(x)(A(x)B)
(x)(BA(x))
(x)A(x)B
B(x)A(x)
(7)
(8)
由上述几个式子,可推得下列等价式也成立:
(x)(BA(x))
(x)(A(x)B)
(x)A(x)B
 B(x) A(x)
(5)
(6)
三、谓词演算的等价式与蕴含式
:(x)(A(x)  B(x))
(x)(A(x)  B(x))
(x)( A(x)B(x))
解:
(x)( A(x))(x)B(x)
(x)A(x)(x)B(x)
E20
量词的分配
E20
(x)A(x)( x)B(x).
(x)A(x) (x)B(x)
量词转化律
三、谓词演算的等价式与蕴含式
公式