离散数学定义(必须背)
温柔似野鬼°
661次浏览
2021年02月02日 15:44
最佳经验
本文由作者推荐
成全机构-沔州中学
命题逻辑
(
论域
)
定义：论域是一 个数学系统，记为
D
。它由三部分组成：
•
(1)
一个非空对象集合
S
，每个对象也称为个体；
•
(2)
一个关于
D
的函数集合
F
；
•
(3)
一个关于
D
的关系集合
R
。
（逻辑连接词）定义
•
设
n>0 ,
称为
{0,1}
n
到
{0,1}
的函数为
n元函数，真值函数也称为联结词。
•
若
n =0
，则称为
0
元函数。
（命题合式公式）定义：
•
(1).
常元
0
和
1
是合式公式；
•
(2).
命题变元是合式公式；
•
(3).
若
Q,R
是合式公式，
则
(
Q)、
(Q
R)
、
(Q
R)
、
(Q
R)
、
(Q
R)
、
(Q
R)
是合式公式；
•
(4).
只有有限次应用
(1)
—
(3)
构成的公式是合式公式。
（生成公式）定义
1.5
设
S
是联结词的集合。由
S
生成的公式定义如下：
•
⑴若
c
是
S
中的
0
元联结词 ，则
c
是由
S
生成的公式。
•
⑵原子公式是由
S
生成的公式。
•
⑶若
n
≥
1
，
F
是
S
中的
n
元联结 词，
A
1
,
…
,A
n
是由
S
生成 的公式，则
FA
1
…
A
n
是由
S
生成的公 式。
（复杂度）公式
A
的复杂度表示为
FC(A)
•
常元复杂度为
0
。
•
命题变元复杂度为
0
，如果
P
是命题变元，则
FC (P)=0
。
•
如果公式
A=
B
，则
FC (A)=FC(B)+1
。
•
如果公式
A=B
1
B
2
，或
A=B
1
B
2
，或
A=B
1
B
2
，或
A=B
1
B
2
，或
A=B
1
B
2
，或
则
FC (A)=max{FC(B
1
), FC(B
2
)}+1
。
命题合式公式语义
•
论域：研究对象的集合。
•
解释：用论域的对象对应变元。
•
结构：论域和解释称为结构。
•
语义：符号指称的对象。公式所指称对象。合式公式的语义是其对应的逻辑
真值。
（合式公式语义）设
S
是联结词的集合是
{
，
，
，
，
，
}
。由
S
生成的合式
公式
Q
在真值赋值
v
下的真值指派
v(Q)
定义如下：
•
⑴
v(0)=0, v(1)=1
。
•
⑵若
Q
是命题变元
p
，则
v(A)= pv
。
•
⑶若
Q1,Q2
是合式公式
若
Q=
Q
1
，则
v(Q)=
v(Q
1
)
若
Q=Q
1
Q
2
，则
v(Q)=v( Q
1
)
v(Q
2
)
若
Q=Q
1
∨
Q
2
，则
v(Q)=v(Q
1
)
∨
v(Q
2
)
若
Q=Q
1
Q
2
，则
v(Q)=v(Q
1
)
v(Q
2
)
若
Q=Q
1
Q
2
，则
v(Q)=v( Q
1
)
v(Q
2
)
< br>若
Q=Q
1
Q
2
，则
v(Q)=v(Q< br>1
)
v(Q
2
)
（真值赋值）由
S
生成的公式
Q
在真值赋值
v
下的真值
v(Q)
定义如下：
•
⑴若
Q
是
S
中的
0
元联结词
c
，则
v(Q)=c
。
•
⑵若
Q
是命题变元
p
，则
v(Q)= pv
。
•
⑶若
Q
是
FQ1
…
,Qn
，其中
n
≥
1
，
F
是
S< br>中的
n
元联结词，
Qi
是公式，则
v(Q)=v( FQ1
…
Qn)=Fv(Q1)
…
v(Qn)
。
（可满足与有效）定义
1.7
设
Q
是公式。
•
⑴如果真值赋值
v
使得
v(Q)=1
，则称< br>v
满足
Q
。
•
⑵如果每个真值赋值都满 足
Q
，则称
Q
为有效式，或称为永真式，也称为重
言式。
•
⑶如果每个真值赋值都不满足
Q
，则称
Q
为永 假式，也称为矛盾式，不可满
足式。
•
⑷如果至少有一个真值赋值满足
Q
，则称
Q
为可满足式。
定理
1.5
（对偶定理）
•
设
A,B
是由
{0,1,
,
∨
,
∧
}
生 成的公式，
A*
与
A
互为对偶式，
B*
与
B
互为对偶
式。如果
A
B
，则
A*
B*
。
（完全集）定义：
•
定义
1.12
设
F
是
n
元联结词，
p1,p2 ,
…
,pn
是不同的命题变元。
如果公式
A
中
不出 现除
p1,p2,
…
,pn
之外的命题变元，
并且
A
Fp1,p2,
…
,pn
，
则称
A
定义
F
。
•
设
S
是联结词集合。如果每个
n(n>0)
元的联结词都可由
S
定义，则称
S
为完
全集 。
•
如果完全集
S1
中的每个联结词都可由联结词集合
S2
定义，
则
S2
也是完全集。
•
< br>如果从完全集
S
中去掉任何一个联结词就成为不完全的了，就称
S
为极 小完
全集。
(
范式
)
定义：
•
原子公式和原子公式的否定统称为文字。如果一个文字恰为另一个文字的否
定，则称它们为相反文字。
•
设
n
是正整数，
A1,
……
,An
都是文字，称
A1
∨
…
∨An
为简单析取式，称
A1
∧
…
∧
An
为简单合取式。
•
定义⒈１６设
n
是正整数。若
B1,
……
,Bn
都是简单合取式，则称
B1
∨
…
∨
Bn
为析取范式。若
B1,
……
,Bn< br>都是简单析取式，则称
B1
∧
…
∧
Bn
为合取范式。
（逻辑推论）定义：
•
若真值赋值
v
满足公式 集合
Γ
中的每个公式，则称
v
满足
Γ
。若有真值赋值
满足
Γ
，则称
Γ
是可满足的，否则称
Γ
是不可满足的。< br>
•
设
Γ
是公式的集合，
A
是公式。如果每个满足
Γ
的真值赋值都满足
A
，
则称
A
是
Γ
的逻辑推论，记为
Γ
|=A
。若
Γ
|=A不成立，记为
Γ
|
≠
A
。
谓词逻辑
（论域）定义：论域是一个数学系统，记为
D
。它由三部分组成：
•
(1)
一个非空对象集合
D
；
•
(2)
一个关于
D
的函数集合
,
也称运算；
•
(3)
一个关于
D
的关系集合。
（一阶谓词逻辑语言）简称一阶逻辑语言
•
逻辑符号：包括变元、联接词、量词；
•
非逻辑符号：包括常元、函词、谓词；
•
仅有个体变元；
•
按形成规则构成的合式公式集合
•
（字符集）定义：
逻辑符号，
包括变元、
联接词、
量词、
逗号以及括号等，
表示如下：
变元：
x1, x2,
…
< br>联接词：
,
,
,
,
,
；
量词：
,
；
逗号：
,
括号：
(, )
非逻辑符号，包括常元、函词、谓词等，表示如下：
常元：
c1, c2 ,
…
函词：
f11, f21,......
；
f12, f22,......
；
谓词：
P11,P 21,......
；
P 12, P 22,....
。
（项）定义：
•
(1).
个体常元是项；
•
(2).
个体变元是项；
•
(3).
若是
t1,
…
,tn
项，
f in
是
n
元函词，则是
f i (t1,
…
,tn)
项。
（合式公式）定义：合式公式是按如下规则构成的有穷长符号串。
•
(1).
若是
t
1
,
…
,t
n
项，< br>Q
i
n
是
n
元谓词，则
Q
i
n(t
1
,
…
,t
n
)
是合式公式。
•
(2).
若
Q
是合式公式，则
(
< br>Q)
是合式公式；
•
(3).
若
Q和
R
是合式公式，
则
(Q
R)
、
( Q
R)
、
(Q
R)
、
(Q
R)
及
(Q
R)
是合式
公式；
•
(4).
若
Q
是合式公式，
x
是变元 ，则
(
xQ)
及
(
xQ)
是合式公式 。
•
(5).
只有有限次应用
(1)
—
(4)
构成的公式是合式公式。
（约束变元）定义：
•
若
(
xQ) (
或
xQ)
是公式，则称变元
x
在公式
(
xQ)
(
或
xQ)
中为约束出现，称
x< br>是约束变元，并称
x
出现的辖域为
Q
。
（自由变元）定义：
•
如果变元
x
在公式
Q
中的出现不是约束出现，
则称
x
在
Q< br>中为自由出现。
在
公式
Q
中有自由出现的变元称为
Q
的自由变元，将
Q
中自由变元的集合记
为
Var(Q)
。
定义：不出现变元的项称为基项。
定义：没有自由变元的公式称为语句。
解释（定义）
：设
D
是论域，一个解释
I
由以下四部分组成：
•
(1)
对于每个常元
c
，指派
D
中一个元素
c
。
•
(2)
对于每个
n
元函词
f
，指派一个
D
上的一个
n
元运算
f
。
•
(3)
对于每个
n
元谓词
Q
，指派一个
D
上的一个
n
元关系
Q
。
（结构）定义：
•
给定一阶语言
L
以及论域< br>D
和解释
I
，
偶对
称为
L
的结构，
记为
S=
。
（赋值）定义：
•
从变元到论域
D
的函数称为
I
中的赋值，记为
σ
:V
D
。
（模型）定义：
•
给定一阶语言
L
以及它的结构
S
和赋值
σ
，偶对
>
称为
L
的模型，记为
M=
>
。
（项的语义）定义：设
L
是一阶语言，
U
是论域，
I
是解释，语言
L的项
t
的语义是
D
中一个对象，记为
σ
I
(t )
，简记为
σ
(t)
。
•
(1)
若
t
是常元
a
，则
σ
(t) =aI
。
•
(2)
若
t
是变元
x
，则
σ
(t) =
σ
(x)
。
•
(3)
若
t
是
f (t1, t2,
…
, tn)
，则
σ
(t) = f I(
σ
(t1),
σ
(t2),
…
,
σ
(tn))
。
（谓词合式公式意义）定义给定一阶语言
L
，结构
S=
和赋值函数
σ
:V
D
，
t
1
,
t
2
,
…
, t
n
是项。在模型
M=
>
下，公式
P,Q,R
的语义是确定的逻辑真值。
•
(1)
若
P
是
Q(t1, t2,
…
, tn)
，则
σ
(P) = QI(
σ
(t1),
σ
(t2),
…
,
σ
(tn))
。
•
(2)
若
P
是
Q
，则
σ
(
Q) =
σ
(Q)
。
•
(3)
若
P
是
Q
R
，则
σ
(Q
R) =
σ
(Q)
σ
(R)
。
•
(4)
若
P
是
Q
R，则
σ
(Q
R) =
σ
(Q)
σ
(R)
。
•
(5)
若
P
是
Q
R
，则
σ
(Q
R) =
σ
(Q)
σ
(R)
。
•
(6)
若
P
是
Q
R，则
σ
(Q
R) =
σ
(Q)
σ
(R)
。
•
(7)
若
P
是
Q
R
，则
σ
(Q
R) =
σ
(Q)
σ
(R)
。
•
(8)
若
P
是
xQ(x)
，则
•
(9)
若
P
是
xQ(x)
，则
（可满足性）定义：
•
定义：
给 定一阶语言
L
和它的公式
Q
，
如果存在模型
M=
>
，
使得
σ
(Q)=1
成立，则称公式
Q
关于模型
>
是可满足的，简称
Q
可满足，也称模型
>
满足
Q
，记为╞
M Q
。
•
定义：给定一阶语言
L
和它的公式
Q
，如果不 存在模型
M=
>
，使得
σ
(Q)=1
成 立，则称公式
Q
关于模型
>
是不可满足的，也称模型
>
不
满足
Q
，记为
|
M Q
。
•
定义：给定一阶语言
L
和它的公式集合
Γ
= {Q1,...,Qn}
，如果存在模型
M=
>
，使得对 于每个公式
Qk
，
Qk
Γ
，有
σ
(Qk )=1
成立，则称公式集合
Γ
关
于模型
>
是可满足的，
简称
Γ
可满足，
也称模型
>
满足
Γ
，
记为╞
M
Γ
，也记为
σ
(
Γ
)=1
。
（有效性）定义
•
定义：若合式公式
Q
对于一阶语言
L
的任意模型
M=
>
均可满足，即对
任意结构
S
和任意赋值
σ成立，则称公式集合
Q
是永真的或有效的，记为╞
Q
。