第五章函数Function
函数在数学、应用数学等许多领域，
尤其计算机科学领域有着极其重要的
作用。函数的思想、概念和应用无处
不在，无时不在。
它主要是研究变量之间的关系和规
律。函数的划分有很多种。有线性与
非线性之分、连续与离散之分。例如，
x12345…
y357911…
5.1 函数
假定A，B是两个非空集合，f : A→B，称f为A到B上的函数，对每个
a∈A, 有唯一的f(a)∈B, 记做b = f(a)。
函数也叫映射mappings或变换transformations（错误）
a叫做函数f的自变量argument，b被称为因变量，b=f(a)叫做函数的值
value，也叫a的像。
例1. A＝{1,2,3,4}, B={a,b,c,d},
，则 f是一个函数。
也可以简单记为，
f={(1,a), (2,a), (3,d), (4,c)}
另外,
g={(1,a), (1,b), (2,a), (4,c)}
因为对于1来说，1∈A, 不是唯一的f(1)∈B与之相对应, f(1)=a,
并且f(1)=b, 因此g就不是一个函数。
例2．
f：Z→Z，
f(a)=
f是函数。
例3． 恒等函数1A(a)=a是函数。
正如，我们在第四章里表述的，函数 f : A→B，b=f(a), 是一个特殊的
二元关系，我们知道，由函数f可以确定一个关系，简单地，可以表示
为(a,b)∈，或 ab。关系的特征函数为
或者简记为
因此，这样一来，我们以前所讨论的有关集合或关系的运算和性质对
于函数来说，就可以完全适用。
例如，f：A→B, g：A→B,
函数的复合
设f：A→B，g：B→C，是函数，则g◦f：A→C，是函数。
g◦f（a）＝g(f(a))例4． 函数的复合
设f，g都是整数函数，
f(a)=a+1, g(b)=2b.
则 g◦f (a)=2(a +1) 是整数集到偶数集的函数。
f◦g(a)=2a＋1也是整数集到奇数集的函数。
特殊函数Special Type of Functions
5.1 一阶逻辑等值式与置换规则
定义5.1 设A，B是一阶逻辑中任意两个公式，若AB是永真式，则称A与B是等值的。记做AB，称AB是等值式。
谓词逻辑中关于联结词的等值式与命题逻辑中相关等值式类似。下面主要讨论关于量词的等值式。
一、基本等值式
第一组 代换实例
由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式，因而第二章的16组等值式给出的代换实例都是一阶逻辑的等值式的模式。例如：
xF(x)┐┐xF(x)
xy(F(x,y)→G(x,y))┐┐xy(F(x,y)→G(x,y))
等都是(2.1)式的代换实例。又如：
F(x)→G(y)┐F(x)∨G(y)
x(F(x)→G(y))→zH(z)┐x(F(x)→G(y))∨zH(z))
等都是(2.1)式的代换实例。
第二组 消去量词等值式
设个体域为有限域D={a1,a2,…,an}，则有
(1)xA(x)A(a1)∧A(a2)∧…∧A(an)
(2)xA(x)A(a1)∨A(a2)∨…∨A(an) (5.1) 第三组 量词否定等值式
设A(x)是任意的含有自由出现个体变项x的公式，则
(1)┐xA(x)x┐A(x)
(2)┐xA(x)x┐A(x) (5.2)
(5.2)式的直观解释是容易的。对于(1)式，“并不是所有的x都有性质A”与“存在x没有性质A”是一回事。对于(2)式，“不存在有性质A的x”与“所有x都没有性质A”是一回事。
第四组 量词辖域收缩与扩张等值式
设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则
(1)x(A(x)∨B)xA(x)∨B x(A(x)∧B)xA(x)∧B
离散数学答案 屈婉玲版
第二版 高等教育出版社课后答案
第一章部分课后习题参考答案
16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。
（1）p∨(q∧r) 0∨(0∧1) 0
（2）（p?r）∧(﹁q∨s) （0?1）∧(1∨1) 0∧10.
（3）（p∧q∧r）?(p∧q∧﹁r) （1∧1∧1） ? (0∧0∧0)0
(4)（r∧s）→(p∧q) （0∧1）→(1∧0) 0→01
17．判断下面一段论述是否为真：“是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。”
答：p: 是无理数 1
q: 3是无理数 0
r: 2是无理数 1
s: 6能被2整除 1
t: 6能被4整除 0
命题符号化为： p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。
19．用真值表判断下列公式的类型：
（4）(p→q) →(q→p)
（5）(p∧r) (p∧q)
（6）((p→q) ∧(q→r)) →(p→r)
答： （4）
p q p→q q p q→p (p→q)→(q→p)
0 0 1 1 1 1 1
0 1 1 0 1 1 1
1 0 0 1 0 0 1
1 1 1 0 0 1 1
第一章 第二节 P18
19、用真值表判断下列公式的类型：
（2）、（p→p）→q
解：
p q p q p→p （p→p）→q
0 0 1 1 1 1
0 1 1 0 1 0
1 0 0 1 0
1
1 1 0 0 0 1
该公式为可满足式。
20、求下列公式的成真赋值。
（3）、（p∧q）→p
解：该公式的真值表为：
p q p p∧q （p∧q）→p
0 0 1 0 1
0 1 1 0 1
1 0 0 0 1
1 1 0 1 0
所以其成真赋值为00、01、10、11.
21、求下列各公式的成假赋值
（1）、rqp)(
解：因为所求公式要为假命题，则r与qp同假。而r为假时，r的真值为1。
而由真值表：
p q p qp )(qp
0 0 1 0 1
0 1 1 1 0
1 0 0 0 1
1 1 0 0 1
可知)(qp为假时，其成假赋值为01。
所以所求公式的成假赋值为011。
