离散数学

实验一  联结词的运算

一．实验目的

通过上机实验操作，将命题连接词运算融入到C语言的程序编写中，一方面加强对命题连接词运算的理解，另一方面通过编程实现命题连接词运算，帮助学生复习和锻炼C语言知识，将理论知识与实际操作结合，让学生更加容易理解和记忆命题连接词运算。

二．实验原理

(1) 非运算, 符号:ù ,当P=T时 ，ùP为F, 当P=F时 ，ùP为T 。

(2) 合取, 符号: ∧ , 当且仅当P和Q的真值同为真，命题P∧Q的真值才为真；否则，P∧Q的真值为假。

(3) 析取, 符号: ∨ , 当且仅当P和Q的真值同为假，命题P∨Q的真值才为假；否则，P∨Q的真值为真。

(4) 异或, 符号: ▽ , 当且仅当P和Q的真值不同时，命题P▽Q的真值才为真；否则，P▽Q的真值为真。

(5) 蕴涵, 符号: → , 当且仅当P为T,Q为F时，命题P→Q的真值才为假；否则，P→Q的真值为真。

(6) 等价, 符号: ? , 当且仅当P,Q的真值不同时，命题P?Q的真值才为假；否则，P→Q的真值为真。

三．实验内容

编写一个程序实现非运算、合取运算、析取运算、异或运算、蕴涵运算、等价运算。

四．算法程序

内容格式：新罗马，小五号，行间距固定值18磅

#include

using namespace std;

int main()

    bool P=true,Q=false;

       cout<<"请选择运算方式"<

       cout<<"0-----------------或取"<

       cout<<"1-----------------异或"<

       cout<<"2-----------------合取"<

       cout<<"3-------------------非"<

       cout<<"4-----------------蕴含"<

       cout<<"5-----------------等价"<

       int m;

       cin>>m;

       while( m>=0 && m<=4 )

       {

              cout<<"请输入P Q的值"<

              cin>>P>>Q;

        int count = 0;

              switch(m)

              {

              case 0:while( (count >= 0)&&(count < 4 ) )

                        {

                               if(Q==0 && P==0)   

                                      cout<<"P 或取 Q = "<<'0'<

                               else

                                      cout<<"P 或取 Q = "<<'1'<

                               count++;

                               if(count==4)  break;

                               cout<<"请输入P Q的值"<

                               cin>>P>>Q;

                        }

                        break;

              case 1:while((count >= 0) && (count < 4))

                            {

                                   if(Q==P)

                                          cout<<"P 异或 Q = "<<'0'<

                                   else

                                          cout<<"P 异或 Q = "<<'1'<

                                   count++;

                                   if(count == 4)  break;

                                   cout<<"请输入P Q的值"<

                                   cin>>P>>Q;

                            }

           case 2:while( (count >= 0)&&(count < 4 ) )

                        {

                               if(Q==1 && P==1)

                                      cout<<"P 合取 Q = "<<'1'<

                               else

                                      cout<<"P 合取 Q = "<<'0'<

                               count++;

                               if(count==4)  break;

                      cout<<"请输入P Q的值"<

                               cin>>P>>Q;

                       }

                       break;

              case 3:while( (count >= 0)&&(count < 4 ) )

                        {

                               if(Q==0)   cout<<"非Q = "<<'1'<<"  "<

                               else       cout<<"非Q = "<<'0'<

                               if(P==0)   cout<<"非P = "<<'1'<<"  "<

                               else       cout<<"非P = "<<'0'<

                               count++;

                            if(count==4)  break;

                               cout<<"请输入P Q的值"<

                               cin>>P>>Q;

                        }

                        break;

              case 4:while( (count >= 0)&&(count < 4 ) )

                        {

                               if( Q==1 || (Q==0 && P==0)) 

                                      cout<<"P 蕴含 Q = "<<'1'<

                               else if(P==1 && Q==0)

                                   cout<<"P 蕴含 Q = "<<'0'<

                               count++;

                            if(count==4)  break;

                               cout<<"请输入P Q的值"<

                               cin>>P>>Q;

                        }

                        break;

              case 5:while( (count >= 0)&&(count < 4 ) )

                        {

                            if(P==Q)

                                cout<<"P 等价 Q = "<<'1'<

                         else

                                cout<<"P 等价 Q = "<<'0'<

                            count++;

                if(count==4)  break;

                            cout<<"请输入P Q的值"<

                            cin>>P>>Q;

                        }

                        break;

              }

              cout<<"请重新选择运算方式"<

              cin>>m;

       }

    system("pause");

       return 0;

五．实验结果

实验结果截图大小为：宽（10cm）×高（8cm）

六．心得体会

内容格式：宋体，五号，行间距固定值18磅

通过设计算法可以使得数学中逻辑算法用程序来实现，这样只要借助计算机的程序就可以很方便的将一些复杂的逻辑运算轻松地解决。

主函数中设计的代码虽然代码过长，但是结构明显，但是可以拆分为一个菜单函数，和一个指令输入函数，这样整体的机构更加简洁，方便代码的维护。

实验二  根据矩阵的乘法求复合关系

一．实验目的

复合运算是一种重要的二元关系运算，可用于二元关系的合成，二元关系的性质判断，二元关系传递闭包的运算等方面，通过编程实现二元关系的复合运算，帮助同学们理解复合运算的过程，复合形成新的二元关系中的序偶是如何产生的。

二．实验原理

复合运算能由两个二元关系生成一个新的二元关系。

设X→Y(R关系)，Y→Z(S关系)，则称X→Z(R?S关系)为R和S的复合关系，并规定为：R?S={|x∈X∧z∈Z∧?y(y∈Y∧∈R∧∈S)}

关系可用矩阵表示，故复合运算也可用矩阵表示。设有三个集合：X={x₁,x₂…x_m},Y={y₁,y₂…y_n},Z={z₁,z₂…z_p}, ，|X|=m, |Y|=n, |Z|=p,M_R=[a_ik]_{m×n ，}M_S=[a_kj]_n×p则复合关系R?S的关系矩阵为：

M_R?_S= M_R?M_S=[c_ij] _m×p   

∨代表逻辑加，满足0∨0=0，0∨1=1,1∨0=1，1∨1=1

∧代表逻辑乘，满足0∧0=0，0∧1=0,1∧0=0，1∧1=1

三．实验内容

将二元关系用关系矩阵表示，通过两个关系矩阵对应行列元素先进行逻辑乘，后进行逻辑加生成新的关系矩阵中的每一个元素。新的关系矩阵所对应的二元关系就是两个二元关系复合形成的，编程实现这一复合过程。

四．算法程序

#include

using namespace std;

#define N 100

int main()

               int n,m,p;

               cout<<"请输入n,m,p的值：";

               cin>>n>>m>>p;

               int i,j,k;

               int R[N][N],S[N][N];

               cout<<"输入R的序偶:"<

               for(i=0;i

                            for(j=0;j

                            {

                                   cin>>R[i][j];

                                   if(R[i][j]!=0 && R[i][j]!=1)//兼容性，如果键盘输入不是1或0则默认该值为0

                                          R[i][j] = 0;

                            }

               cout<<"输入S的序偶:"<

               for(i=0;i

                            for(k=0;k

                            {

                                   cin>>S[i][k];

                                   if(S[i][k]!=0 && S[i][k]!=1)//兼容性，如果键盘输入不是1或0则默认该值为0

                                          S[i][k] = 0;

                            }

               

               int RS[N][N];

               for(i=0;i

                      for(k=0;k

                      {

                             int sum = 0;

                             for(j=0;j

                             {

                                    sum += R[i][j] * S[j][k];

                                    if(sum != 0)

                                           RS[i][k] = 1;

                                    else

                                           RS[i][k] = 0;

                             }  

                      }

           cout<<"R矩阵:"<

              for(i=0;i

              {

                     for(j=0;j

                            cout<

                         cout<<"\n";

              }

              cout<<"S矩阵:"<

              for(i=0;i

              {

                     for(k=0;k

                            cout<

                         cout<<"\n";

              }

             cout<<"R复合S:"<

              for(i=0;i

              {

                     for(k=0;k

                            cout<

                         cout<<"\n";

              }

              return 0;

五．实验结果

实验结果截图大小为：宽（10cm）×高（8cm）

六．心得体会

内容格式：宋体，五号，行间距固定值18磅

利用算法的兼容性将算法优化，避免键盘输入而产生的其他数值，影响代码以及结果的正确性，通过程序可以很简单的计算多维矩阵的复合运算。

实验三  利用warshall算法求关系的传递闭包

一．实验目的

对于一个二元关系R,它的传递闭包(t(R))就是包含R,并且具有传递性质的最小二元关系。传递闭包在图论、数据库、编译原理、计算机形式语言中都有重要的应用。warshall算法是计算传递闭包的一种有效算法，通过编程实现warshall算法，帮助同学们更好地理解传递闭包的生成过程。

二．实验原理

设X是含有n个元素的集合，R是X上的二元关系，则：

以上计算传递闭包时需要按照复合关系定义求，这是比较麻烦的，特别当有限集合元素比较多时计算量很大。1962年Warshall提出了一个求t(R)的有效计算方法：设R是n个元素集合上的二元关系，是R的关系矩阵：

第一步：置新矩阵M，；

第二步：置i，；

第三步：对，若M的第j行i列处为1，则对作如下计算：

将M的第j行第k列元素与第i行第k列元素进行逻辑加，然后将结果送到第j行k列处，即  ；

第四步：；

第五步：若，转到第三步，否则停止。

三．实验内容

将二元关系用关系矩阵表示，编程实现Warshall算法，获得二元关系传递闭包的关系矩阵。

四．算法程序

内容格式：新罗马，小五号，行间距固定值18磅

#include

using namespace std;

#define N 10

int logical_add(int x,int y)

    int a=1;

    if(x==0&&y==0)

        a=0;

    return a;

int main()

    int MR[N][N] ;

    int M[N][N];

    int i,j,k,n;

    cout << "请输入关系矩阵的阶数:";

    cin >> n;

    cout << "请输入关系矩阵MR "<< n <<" * " << n << " : " << endl;

    for(i=0;i

        for(j=0;j

        {

            cin >> MR[i][j];

            if( MR[i][j]!=0 && MR[i][j]!=1 )

                MR[i][j] = 0;

            M[i][j] = MR[i][j];

        }

    i = 0;

    while(i

    {

        for(j=0;j

            if(M[j][i]==1)

                for(k=0;k

                   M[j][k] = logical_add(M[j][k],M[i][k]);

        i++;   

    }

    cout << "关系矩阵为:" << endl;

    for(i=0;i

    {

        for(j=0;j

            cout << MR[i][j] << " ";

        cout << "\n";

    }

    cout << "结果为:" << endl;

    for(i=0;i

    {

        for(j=0;j

            cout<

        cout << "\n";

    }

    return 0;

五．实验结果

实验结果截图大小为：宽（10cm）×高（8cm）

六．心得体会

内容格式：新罗马，小五号，行间距固定值18磅