离散数学实验指导书及其答案
余年寄山水
642次浏览
2021年01月30日 00:39
最佳经验
本文由作者推荐
成绩单评语-我不后悔
实验一
命题逻辑公式化简
【实验目的】加深对五个基本联结词 （否定、合取、析取、条件、双条件）的理解、掌
握利用基本等价公式化简公式的方法。
【实验内容】用化简命题逻辑公式的方法设计一个表决开关电路。
实验用例：
用化简命题逻辑公式的方法设计一个
5
人表决开关电路，
要求
3
人 以上
（含
3
人）同意则表决通过（表决开关亮）
。
【实验原理和方法】
（
1
）
写出
5
人表 决开关电路真值表，
从真值表得出
5
人表决开关电路的主合取公式
（或
主析取公式）
，将公式化简成尽可能含五个基本联结词最少的等价公式。
（
2
）上面公式中的每一个联结词是一个开关元件，将它们定义成
C
语言中的函数。< br>
（
3
）输入
5
人表决值（
0
或
1
）
，调用上面定义的函数，将
5
人表决开关电路真值表的
等价公式写 成一个函数表达式。
（
4
）输出函数表达式的结果，如果是
1，则表明表决通过，否则表决不通过。
参考代码：
#include
int vote(int a,int b,int c,int d,int e)
{
/
/
五人中任取三人的不同的取法有
10
种。
i
f( a&&b&&c || a&&b&&d || a&&b&&e || a&&c&&d || a&&c&&e || a&&d&&e || b&&c&&d
|| b&&c&&e || b&&d&&e || c&&d&&e)
}
void main()
{
i
nt a,b,c,d,e;
p
rintf(
请输入第五个人的表决值（
0
或
1
，空格分开）
：
s
canf(
i
f(vote(a,b,c,d,e))
}
//
注：联结词不定义成函数，否则太繁
e
lse
printf(
遗憾，表决没有通过！
n
printf(
很好，表决通过！
n
return 1;
return 0;
e
lse
实验二
命题逻辑推理
【实验目的】加深对命题逻辑推理方法的理解。
【实验内容】用命题逻辑推理的方法解决逻辑推理问题。
实验用例：根据下面的命题，试用逻辑推理方法确定谁是作案者，写出推理过程。
（
1
）营业员
A
或
B
偷了手表；
（
2
）若
A
作案，则作案不在营业时间；
（
3
）若
B
提供的证据正确，则货柜末上锁；
（
4
）若
B
提供的证据不正确，则作案发生在营业时间；
（
5
）货柜上了锁。
【实验原理和方法】
（
1
）符号化上面的命题，将它们作为条件，营业员
A
偷了手表作为结论，得一 个复合
命题。
（
2
）将复合命题中要用到的联结词定义成
C
语言中的函数，用变量表示相应的命题变
元。将复合命题写成一个函数表达式。
< br>（
3
）函数表达式中的变量赋初值
1
。如果函数表达式的值为
1
，则结论有效，
A
偷了
手表，否则是
B
偷了手表。
用命题题变元表示：
A:
营业员
A
偷了手表
B:
营业员
B
偷了手表
C:
作案不在营业时间
D:B
提供的证据正确
E:
货柜末上锁
则上面的命题符号化为
(A||B) && (!A||C) && (!D||E) && (D||!C) && !E
要求找到满足上面式子的变元
A
，
B
的指派便是结果。
C
语言算法：
i
nt A,B,C,D,E;
f
or(A=0;A<=1;A++)
}
/*
实验结果是：
A=0
，
B= 1
，即
B
偷了手表
*/
for(B=0;B<=1;B++)
for(C=0;C<=1;C++)
for(D=0;D<=1;D++)
for(E=0;E<=1;E++)
if((A||B) && (!A||C) && (!D||E) && (D||!C) && !E)
printf(
实验三
集合运算
【实验目的】掌握用计算机求集合的交、并、差和补运算的方法。
【实验内容】编程实现集合的交、并、差和补运算。
【实验原理和方法】
（
1
）用数组
A
，
B
，
C
，E
表示集合。输入数组
A
，
B
，
E
（全集）< br>，输入数据时要求检查
数据是否重复（集合中的数据要求不重复）
，要求集合
A
，
B
是集合
E
的子集。
以下每一个运算都要求先将集合
C
置成空集。
（
2
）二个集合的交运算：把数组
A
中元素逐一与数组
B
中的元素进行比较，将 相同的
元素放在数组
C
中，数组
C
便是集合
A
和集 合
B
的交。
C
语言算法：
f
or(i=0;i
for(j=0;j
if(a[i]==b[j]) c[k++]=a[i];
（
3
）二个集合的并运算：把数组
A
中 各个元素先保存在数组
C
中。将数组
B
中的元素
逐一与数组
B
中的元素进行比较，
把不相同的元素添加到数组
C
中，
数组
C
便是集合
A
和集
合
B
的并。
{
}
（
4
）二个集合的差运算：把数组
A
中各个元素先保存在数组
C
中。将数组
B
中的元素
逐一与数组
B
中的元素进行比较 ，
把相同的元素从数组
C
中删除，
数组
C
便是集合
A
和集合
B
的差
A-B
。
C
语言算法：
f
or(i=0;i
c[i]=a[i];
for(j=0;j
if(b[i]==c[j])
{
for(k=j;k
c[k]=c[k+1];/*
移位
*/
m--;
f
or(i=0;i
if(b[i]==c[j]) break;
if(j==m){ c[m+k]=b[i];k++;}
C
语言算法：
for(i=0;i
f
or(i=0;i
}
break;
（
5
）集合的补运算：将数组
E
中的元素逐一与数组
A
中的元素进行比较，把不相同的
元素保存到数组
C< br>中，数组
C
便是集合
A
关于集合
E
的补集。
求补集是一种种特殊的集合差运算。
实验四
二元关系及其性质
【实验目的】掌握二元关系在计算机上的表示方法，并掌握如果判定关系的性质。
【实验内容】
编程判断一个二元关系是否为等价关系，如果是，求其商集。
等价关系：
集合
A
上的二元关系
R
同时具有自反性、
对称性和传递性，
则称
R
是
A
上的
等价关系。
【实验原理和方法】
（
1
）
A
上的二元关系用一 个
n
×
n
关系矩阵
R=
(
r
ij
)
n
n
表示，
定义一个
n
×
n
数组
r[n][n]
表示
n
×
n
矩阵关系。
（
2
）若
R
对角线上的元素都是
1
，则
R具有自反性。
C
语言算法：
int i,flag=1;
for(i=0;i
if(r[i][i]!=1) flag=0;
如果
flag=1
，
则
R
是自反关系
（
3
）若
R
是对称矩阵，则
R
具有对称性。对称矩 阵的判断方法是：
r
ij
R
,
有< br>
r
ji
R
。
C
语言算法：
int i,j,flag=1;
for(i=0;i
for(j=i+1;j
if(r[i][j] &&r[j][i]!=1) flag=0;
如果
flag=1
，
则
R
是对称关系
（
4
）关系的传递性判断方法：对任意
i
，
j
，< br>k
，若
r
ij
1
且
r
jk
1
有
r
ik
1
。
C
语言算法：
int i,j,k,flag=1;
for(j=0;j
for(k=0;k
if(r[i][j] &&r[j][k] && r[i][k]!=1) flag=0;
for(i=0;i
flag=1
，
则
R
是传递关系
（
5
）求商集的方法：商集是由 等价类组成的集合。已知
R
是等价关系，下面的算法是
把等价类分行打印出来。
C
语言算法：
int i,j,flag=1;
int a[N];
for(i=0;i
{
if(a[i])
a[i]=i+1;/*i
代表第
i
个元素
*/
for(i=0;i
{
}
}
printf(
for(j=0;j
if(r[i][j] && a[j]!=0)
{
printf(
打印和第
i
个元素有关系的所有元素
*/
a[j]=0;
}
printf(
实验五
关系闭包运算
【实验目的】掌握求关系闭包的方法。
【实验内容】编程求一个关系的闭包，要求传 递闭包用
warshall
方法。
【实验原理和方法】
设
N
元关元系用
r[N][N]
表示，
c[N][N]
表示 各个闭包，函数
initc(r)
表示将
c[N][N]
初始化为
r [N][N]
。
（
1
）自反闭包：
r
(
R
)
R
I
A
。
C
语言算法：
将关系矩阵的对角线上所有元素设为
1
。
initc(r);
/*
将关系矩阵的对角线上所有元素设为
1*/
for(i=0;i
c[i][i]=1;
（
2
）对称闭包：
s
(
R
)
R
R
C
语言算法：
在关系矩阵的基础上，若
r< br>ij
1
,
令
r
ji
1
。
initc(r);
for(i=0;i
for(j=0;j
if(c[i][j])
c[j][i]=1;/*
将关系矩阵的对角线上所有元素设为
1*/
（< br>3
）传递闭包：
t
(
R
)
R
< br>R
2
R
n
，或用
warsh all
方法。
方法
1
：
t
(
R
)
R
R
2
R
n
，下面求得的关系矩阵
T=
(
b
ij
)
n
n
就是
t
(
R
)
。
int b[N][N];
initc(r);/*
用
c
装好
r*/
for(m=1;m
r
的
m
次方
,
用
c
装好
*/
{
for(i=0;i
for(j=0;j
}
b[i][j]=0;
for(k=0;k
b[i][j]+=c[i][k]*r[k][j];
if(b[i][j]) b[i][j]=1;
initc(b);/*
把
r
的
m
次方
b
赋给
c
保存
*/