精华内容
下载资源
问答
  • 离散数学主析取范式及主合取范式

    万次阅读 多人点赞 2018-03-28 19:28:21
    今天总结了一下关于离散数学化简主析取范式以及主合取范式的一些方法。首先一般可能会用到 分配律: A∨(B∧C)<=>(A∨B)∧(A∨C), A∧(B∨C)<=>(A∧B)∨(A∧C);其次若化简式里有蕴涵...

    今天总结了一下关于离散数学化简主析取范式以及主合取范式的一些方法。

    首先一般可能会用到 分配律: A∨(BC)<=>(AB)(AC),

                                                A(BC)<=>(AB)(AC)

    其次若化简式里有蕴涵符号,则可以用 蕴涵等值式 AB<=>¬AB 进行化简;

    若求主析取范式,化简式中有 pq,需给其配上r,可配(pq)∧(r¬r),  这里用了零律及同一律,这里就不详说了;

    若求主合取范式,化简式中有pq,需给其配上r,可配(pq)(r¬r),所用同上。
    当然,也可利用成真赋值,成假赋值互相求出;

    例如:

         (p∨(q∧r))→(p∧q∧r) 

    <=>(p∨(q∧r))∨(p∧q∧r) (﹁p∧﹁(q∧r))∨(p∧q∧r) 

    <=>(﹁p∧(﹁q∨﹁r))∨(p∧q∧r) (﹁p∧﹁q)∨(﹁p∧﹁r)∨(p∧q∧r)

    <=>((﹁p∧﹁q)∧(r∨﹁r))∨((﹁p∧﹁r)∧(q∨﹁q))∨(p∧q∧r)

    <=>(﹁p∧﹁q∧r)∨(﹁p∧﹁q∧﹁r)∨(﹁p∧q∧﹁r)∨(p∧q∧r)

    <=>(﹁p∧﹁q∧﹁r)(﹁p∧﹁q∧r)(﹁p∧q∧﹁r)∨(p∧q∧r)、

    <=>m0m1m2m7

    则可得出其主合取范式为M3M4M5M6,这里默认顺序为p q r

    另外,还需常记得公式有

    等价等值式:
                          A↔B⇔(A→B)∧(B→A)
    假言易位:
                          A→B⇔ ¬B→ ¬A
    等价否定等值式:
                           A↔B⇔ ¬A↔ ¬B
    归谬论:
                     (A→B)∧(A→ ¬B)⇔ ¬A
    未经本人同意,不得转载。
    展开全文
  • //输出主合取范式 } } if (xq[0] == -1) printf("\n该命题公式不存在主析取范式。\n"); else { printf("\n\n该命题公式的主析取范式:\n\t"); for (i1 = 0; i1 ; i1++) { if (i1 > 0) printf...
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <conio.h>
    #include <math.h>
    #define N 50
    
    void panduan(int b[N], int f);//赋值函数
    int tkh(char sz[N], char ccu[N], int icu[N], int h0);//分级运算函数
    int fkh(char sz[N], char ccu[N], int icu[N], int h0);//主运算函数
    
    int main()
    {
    	int i1, i2, d = 1, icu[N], kh = 0, jg, j = 0, h0;//icu[N]用于存放变量值,kh括号计数,jg存放结果
    	int bj = 0, hq[N], h = 0, x = 0, xq[N];//hq[N]存放合取结果xq[N]存放析取结果
    	char sz[N], ccu[N], sz0[N], s;//sz[N]存放式子,ccu[N]存放变量,sz0[N]也是用于存放式子
    	hq[0] = -1;
    	xq[0] = -1;
    	printf("*****************************************\n");
    	printf("\n");
    	printf("               用!表示否定\n");
    	printf("               用&表示且\n");
    	printf("               用|表示或\n");
    	printf("               用^表示条件\n");
    	printf("               用~表示双条件\n");
    	printf("\n");
    	printf("*****************************************\n\n");
    	printf("         请输入一个合法的命题公式:\n");
    	gets_s(sz);//读取式子
    	strcpy(sz0, sz);
    	for (i1 = 0; i1 < strlen(sz); i1++)
    	{
    		if (sz[i1] == ')' || sz[i1] == '(')//存储括号数量
    			kh++;
    		if (sz[i1] >= 'a' && sz[i1] <= 'z' || sz[i1] >= 'A' && sz[i1] <= 'Z')
    		{
    			for (i2 = 0; i2 < j; i2++)        //判断并储存变量。
    			{
    				if (ccu[i2] == sz[i1])    //去除重复变量
    					d = 0;
    			}
    			if (d == 1)
    			{
    				ccu[j] = sz[i1];
    				j++;
    			}
    			d = 1;
    		}
    	}
    	printf("\n该式子中的变量个数为:%d\n", j);//输出变量个数
    	h0 = j;
    	printf("\n输出真值表如下:\n \n"); //输出真值表表头
    
    	for (i1 = 0; i1 < h0; i1++)
    		printf(" %c ", ccu[i1]);
    	printf(" ");
    	puts(sz);
    	printf("\n");
    
    	for (i1 = 0; i1 < j; i1++)     //先将所有的变量赋值为1。
    		icu[i1] = 1;
    	for (i2 = 0; i2 < j; i2++)     //输出真值表前项
    		printf(" %d ", icu[i2]);
    	jg = tkh(sz, ccu, icu, h0);  //用函数求结果
    
    	if (jg == 0)               //结果为0,合取加1
    		hq[h++] = bj;
    	else                    //否则,析取加1
    		xq[x++] = bj;
    	printf("    %d\n", jg);  //输出运算结果
    	strcpy(sz, sz0);
    
    	for (i1 = 0; i1 < pow(2, j) - 1; i1++)
    	{
    		++bj;
    		panduan(icu, j - 1);     //赋值变量
    		jg = tkh(sz, ccu, icu, h0);
    		if (jg == 0)             //结果为0,合取加1
    			hq[h++] = bj;
    		else                  //否则,析取加1
    			xq[x++] = bj;
    
    		strcpy(sz, sz0);       //恢复被修改的数组。
    
    		for (i2 = 0; i2 < j; i2++)
    			printf(" %d ", icu[i2]);//输出真值表前项
    		printf("    %d\n", jg);//输出运算结果
    	}
    
    	if (hq[0] == -1)           //不存在合取范式时
    		printf("\n该命题公式不存在主合取范式。\n");
    	else
    	{
    		printf("\n该命题公式的主合取范式:\n\t");
    		for (i1 = 0; i1 < h; i1++)
    		{
    			if (i1 > 0)
    				printf("/\\");
    			printf("M(%d)", hq[i1]); //输出主合取范式
    		}
    	}
    
    	if (xq[0] == -1)
    		printf("\n该命题公式不存在主析取范式。\n");
    	else
    	{
    		printf("\n\n该命题公式的主析取范式:\n\t");
    		for (i1 = 0; i1 < x; i1++)
    		{
    			if (i1 > 0)
    				printf("\\/");
    			printf("m(%d)", xq[i1]);//输出主析取范式
    		}
    	}                           //结束
    	getch();
    }
    
    void panduan(int b[N], int f)  // 二进制赋值。
    {
    	int i;
    	i = f;
    	if (b[f] == 1)                 //减1
    		b[f] = 0;
    	else                        //进位
    	{
    		b[f] = 1;
    		panduan(b, --i);
    	}
    }
    
    int tkh(char sz[N], char ccu[N], int icu[N], int h0)//分级运算函数
    {
    	int i, j, h, s, kh = 0, wz[N], a;
    	char xs1[N], ckh[N];         //xs1用来保存括号内的字符 ckh用来保存括号。
    	s = strlen(sz);
    	for (i = 0; i < s; i++)
    
    		if (sz[i] == '(' || sz[i] == ')')  //判断括号
    		{
    			wz[kh] = i;                  //存储括号位置
    			ckh[kh] = sz[i];             //存储括号类型
    			kh++;
    		}
    
    	if (kh == 0)
    		return fkh(sz, ccu, icu, h0);//如果无括号,直接运行
    	else
    	{
    		for (i = 0; i < kh; i++)
    			if (ckh[i] == ')')           //找到第一个
    				break;
    
    		for (j = wz[i - 1] + 1, h = 0; j < wz[i]; j++, h++) //存储最内级括号中的内容
    			xs1[h] = sz[j];
    		xs1[h] = '\0';
    		a = fkh(xs1, ccu, icu, h0);    //运行最内层括号的式子,得到结果
    		if (a == 1)                  //判断并存储结果
    			sz[wz[i - 1]] = 1;
    		else
    			sz[wz[i - 1]] = -2;
    
    		for (j = wz[i - 1] + 1; j < s + wz[i - 1] - wz[i]; j++)//将括号后内容前移
    			sz[j] = sz[j + wz[i] - wz[i - 1]];
    		sz[j] = '\0';
    		return tkh(sz, ccu, icu, h0);//循环执行
    	}
    }
    
    int fkh(char sz[N], char ccu[N], int icu[N], int h0)//主运算函数
    {
    	int i, h = 0, j = 0, j1 = 0, j2 = 0, j3 = 0, j4 = 0, j5 = 0, i1, i2, p1 = -1, p2 = -1, s;
    	char dt[N];
    	s = strlen(sz);
    
    	if (s == 1)
    	{
    		for (i1 = 0; i1 < h0; i1++)
    			if (sz[0] == ccu[i1])
    				p1 = icu[i1];
    		if (sz[0] == -2 || p1 == 0)     //判断是否是最后一项
    			return 0;
    		else
    			return 1;
    	}          //1 就是sz[0]的值
    	else
    	{
    
    
    		for (i = 0; i < s - j; i++)         //先处理非
    			if (sz[i] == '!')
    			{
    				for (i1 = 0; i1 < h0; i1++)
    					if (sz[i + 1] == ccu[i1])
    					{                    //将变量赋值并给P1
    						p1 = icu[i1];
    					}
    				if (sz[i + 1] == -2)          //如果是前运算结果的0,则P1等于0
    					p1 = 0;
    				if (p1 == -1)               //如果是数字,直接给P1
    					p1 = sz[i + 1];
    				sz[i] = !p1;
    				j++;
    				p1 = -1;
    				for (i1 = i + 1; i1 < s - j; i1++)
    					sz[i1] = sz[i1 + 1];       //将后续式子前移一项
    			}
    		p1 = -1;
    		j1 = j;
    
    
    
    		for (i = 0; i < s - j1 - 2 * j2; i++)   // 处理与
    			if (sz[i] == '&')
    			{
    				for (i1 = 0; i1 < h0; i1++)
    				{
    					if (sz[i - 1] == ccu[i1])   //将变量赋值并给P1
    						p1 = icu[i1];
    					if (sz[i + 1] == ccu[i1])   //将变量赋值并给P2
    						p2 = icu[i1];
    				}
    				if (sz[i - 1] == -2)          //如果是前运算结果的0,则P1等于0
    					p1 = 0;
    				if (sz[i + 1] == -2)
    					p2 = 0;
    				if (p1 == -1)              //如果是数字,直接给P1
    					p1 = sz[i - 1];
    				if (p2 == -1)
    					p2 = sz[i + 1];
    
    				sz[i - 1] = p1 && p2;
    				j2++;
    				p1 = -1;
    				p2 = -1;
    				for (i1 = i; i1 < s - j1 - 2 * j2; i1++)//将后续式子前移两项
    					sz[i1] = sz[i1 + 2];
    				i = i - 1;
    			}
    
    
    		for (i = 0; i < s - j1 - 2 * j2 - 2 * j3; i++) // 处理或。
    			if (sz[i] == '|')
    			{
    				for (i1 = 0; i1 < h0; i1++)
    				{
    					if (sz[i - 1] == ccu[i1])   //将变量赋值并给P1
    						p1 = icu[i1];
    					if (sz[i + 1] == ccu[i1])
    						p2 = icu[i1];
    				}
    
    				if (sz[i - 1] == -2)          //如果是前运算结果的0,则P1等于0
    					p1 = 0;
    				if (sz[i + 1] == -2)
    					p2 = 0;
    				if (p1 == -1)               //如果是数字,直接给P1
    					p1 = sz[i - 1];
    				if (p2 == -1)
    					p2 = sz[i + 1];
    
    				sz[i - 1] = p1 || p2;
    				j3++;
    				p1 = -1;
    				p2 = -1;
    				for (i1 = i; i1 < s - j1 - 2 * j2 - 2 * j3; i1++)//将后续式子前移两项
    					sz[i1] = sz[i1 + 2];
    				i--;
    			}
    
    
    		for (i = 0; i < s - j1 - 2 * j2 - 2 * j3 - 2 * j4; i++) // 处理条件
    			if (sz[i] == '^')
    			{
    				for (i1 = 0; i1 < h0; i1++)
    				{
    					if (sz[i - 1] == ccu[i1])//将变量赋值并给P1
    						p1 = icu[i1];
    					if (sz[i + 1] == ccu[i1])
    						p2 = icu[i1];
    				}
    
    				if (sz[i - 1] == -2)       //如果是前运算结果的0,则P1等于0
    					p1 = 0;
    				if (sz[i + 1] == -2)
    					p2 = 0;
    				if (p1 == -1)            //如果是数字,直接给P1
    					p1 = sz[i - 1];
    				if (p2 == -1)
    					p2 = sz[i + 1];
    
    				sz[i - 1] = !p1 || p2;
    				j4++;
    				p1 = -1;
    				p2 = -1;
    				for (i1 = i; i1 < s - j1 - 2 * j2 - 2 * j3 - 2 * j4; i1++)//将后续式子前移两项
    					sz[i1] = sz[i1 + 2];
    				i--;
    			}
    
    
    		for (i = 0; i < s - j1 - 2 * j2 - 2 * j3 - 2 * j4 - 2 * j5; i++) // 处理双条件
    			if (sz[i] == '~')
    			{
    				for (i1 = 0; i1 < h0; i1++)
    				{
    					if (sz[i - 1] == ccu[i1])//将变量赋值并给P1
    						p1 = icu[i1];
    					if (sz[i + 1] == ccu[i1])
    						p2 = icu[i1];
    				}
    				if (sz[i - 1] == -2)       //如果是前运算结果的0,则P1等于0
    					p1 = 0;
    				if (sz[i + 1] == -2)
    					p2 = 0;
    				if (p1 == -1)            //如果是数字,直接给P1
    					p1 = sz[i - 1];
    				if (p2 == -1)
    					p2 = sz[i + 1];
    
    				sz[i - 1] = (!p1 || p2) && (!p2 || p1);
    				j5++;
    				p1 = -1;
    				p2 = -1;
    				for (i1 = i; i1 < s - j1 - 2 * j2 - 2 * j3 - 2 * j4 - 2 * j5; i1++)//将后续式子前移两项
    					sz[i1] = sz[i1 + 2];
    				i--;
    			}
    
    		return sz[0];
    	}
    }
    
    
    展开全文
  • 离散数学主析取及主合取范式

    千次阅读 2019-12-06 23:11:56
    离散数学主析取及主合取范式 ...文章目录离散数学主析取及主合取范式**概念**一:析取范式与合取范式析取范式与合取范式求范式的步骤二:主析取及主合取范式**解法**等价公式真值表注: 概念 一:析取...

    本文为本人结合书本,网络资源的学习笔记,没有任何商业用途,如有任何错误,问题请广大网友指正和提出!

    概念

    一:析取范式与合取范式

    百度百科

     	命题变项及其否定统称作文字。
     	仅由有限个文字构成的析取式称为简单析取式。
     	仅由有限个文字构成的合取式称为简单合取式。
    

    例如,文字:p,┐q,r,q.

    简单析取式: p,q,p∨q,p∨┐p∨r,┐p∨q∨┐r.

    简单合取式: p,┐r,┐p∧r,┐p∧q∧r,p∧q∧┐r**.**

    析取范式与合取范式

    (1)由有限个简单合取式构成的析取式称为析取范式

    (2)由有限个简单析取式构成的合取式称为合取范式

    (3)析取范式与合取范式统称为范式。

    例如,析取范式:**(**p┐∧q)∨r, ┐p∨q∨r, p∨┐q∨r.

    合取范式:(p∨q∨r)∧(┐q∨r), ┐p∧q∧r, p∧┐q∧r.

    求范式的步骤

    1.消去联结词→、←、↔;

    2.利用德·摩根律将否定符号┐直接移到各个命题变元之前;

    3.利用分配律。

    命题公式的析取范式与合取范式都不是唯一的。

    二:主析取及主合取范式
    1. 主析取范式:

      设命题公式A中含n个命题变项,如果A得析取范式中的简单合取式全是极小项,则称该析取范式为A的主析取范式。
      

      若干个极小项的析取(并集)。

    2. 主合取范式:

      设命题公式A中含n个命题变项,如果A得析取范式中的简单合析式全是极大项,则称该析取范式为A的主析取范式。
      

      若干个极大项的合取(交集)。

    3. 极大项,极小项

    极大项

    包含全部数目的命题变元的析取表达式。

    极小项

    包含全部数目的命题变元的合取表达式。

    所有极小项的析取为永真公式,所有极大项的合取为永假公式。

    解法

    等价公式

    常用基本等价公式:

    (G↔H)=(G→H)∧(H→G)=(¬G∨H)∧(¬H∨G);
    (G→H)=(¬G∨H);(蕴含式)
    G∨G=G,G∧G=G;(幂等律)
    G∨H=H∨G,G∧H=H∧G;(交换律)
    G∨(H∨S)=(G∨H)∨S,G∧(H∧S)=(G∧H)∧S;(结合律)
    G∨(G∧H)=G,G∧(G∨H)=G;(吸收律)
    G∨(H∧S)=(G∨H)∧(G∨S),G∧(H∨S)=(G∧H)∨(G∧S);(分配律)
    G∨0=G;G∧1=G;(同一律)
    G∧0=0,G∨1=1;(零律)
    ¬(G∨H)=¬G∧¬H,¬(G∧H)=¬G∨¬H(德摩根律)
    

    例:(p∨(q∧r))→(p∧q∧r)

    0.﹁(p∨(q∧r))∨(p∧q∧r)

    1.(﹁p∧﹁(q∧r))∨(p∧q∧r)

    2.(﹁p∧(﹁q∨﹁r))∨(p∧q∧r)

    3.(﹁p∧﹁q)∨(﹁p∧﹁r)∨(p∧q∧r)

    4.((﹁p∧﹁q)∧(r∨﹁r))∨((﹁p∧﹁r)∧(q∨﹁q))∨(p∧q∧r)
    5.(﹁p∧﹁q∧r)∨(﹁p∧﹁q∧﹁r)∨(﹁p∧q∧﹁r)∨(p∧q∧r)

    6.(﹁p∧﹁q∧﹁r)∨(﹁p∧﹁q∧r)∨(﹁p∧q∧﹁r)∨(p∧q∧r)

    主析取范式m0∨m1∨m2∨m7

    则可得出其主合取范式为M3∧M4∧M5∧M6

    1.这里也用过主析取范式与主合取范式转换的相关知识,以及极大极小项的表示,本例m0–m7的表示,具体知识不详述。

    2.使用公式转换法求主范式时,需要增加某一个命题变元,此时要注意正确加入该变
    水真公式和永假公式,同时注意正确化简公式(如上述例子的3,4步的过渡)。

    真值表

    [直接给例子吧]
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    注:

    = ”不是一个联结词,而是一种关系。而且具有以下三种性质:

    1.自反性:即G=G
    2.对称性:即若G=H,则H=G
    3.传递性:即若G=H,H=S,则G=S
    
    展开全文
  • 南京邮电大学实验一真值表法求主析取范式和主合取范式代码 离散数学 实 验 一利用真值表法求取主析取范式以及主合取范式的实现 实验名称:利用真值表法求取主析取范式以及主合取范式的实现 实验目的:通过编程实现...
  • 请根据给定的命题公式,计算其真值为T的小项,列出主析取范式,并输出结果。 【输入形式】 输入一个字符串(字符串长度<=50)形式的命题公式,以回车表示输入结束。其中的命题公式为仅包含原子命题、联结词和括号...

    【问题描述】
    请根据给定的命题公式,计算其真值为T的小项,列出主析取范式,并输出结果。
    【输入形式】
    输入一个字符串(字符串长度<=50)形式的命题公式,以回车表示输入结束。其中的命题公式为仅包含原子命题、联结词和括号的合式公式。联结词仅包含下述5中联结词:
    1、否定,表示为“!”
    2、合取,表示为“*”
    3、析取,表示为“|”
    4、条件,表示为“-”
    5、双条件,表示为“=”
    例如:
    (P-Q)-R
    注意:输入符号均采用英文输入。
    【输出形式】
    输出一个以单个空格分隔的字符串,字符串中各项分别对应主析取范式中小项的序号。
    如(P-Q)- R对应的小项为
    则输出1 3 4 5 7
    注意:其中的原子命题按字母表排序。

    【样例输入】

    (P-Q)-R
    

    【样例输出】

    1 3 4 5 7
    

    算法分析
    显然将给出的公式中提取出它的n个不同命题变元,显然每个变元的赋值非真即假,而他们的组合情况恰有2^n种情况,故而可用二进制的形式来模拟,对n个变元进行赋值。在二进制赋值中我们采用模拟二进制过程的算法,从0000开始,从最后一位开始加1,直至最后结果为1111;显然这就包含了2 n种情况。
    具体实现代码如下

    void truth(int times)
    {
        int i = argument.size() - 1;
        while (times)
        {
            a[i] = (times & 1);
            times >>= 1;
            --i;
        }
        int len = argument.size();
        for (i = 0; i < len; ++i)
            mp[argument[i]] = a[i];
        // display
        for (int i = 0; i < len; ++i)
            cout << a[i] << '\t';
        cout << endl;
    }
    

    再者,显然该命题公式就是一个中缀表达式的式子,故而在有了对命题变元的赋值后,我们可以采用处理计算中缀表达式的值的算法来做。首先最一般的算法就是写一个模拟过程,采用栈存储,利用运算符的优先级大小关系进行运算。但值得注意的是,中缀表达式可以处理成二叉表达树的形式,如下图
    在这里插入图片描述
    显然,运算符都将会是分支结点,而命题变元将会是叶子结点,因此在构建出二叉表达树后,我们采用后序遍历进行运算直至根节点,便可得出一组赋值的情况,而二叉树的建立也是采用栈的存储,利用优先级关系进行建树。
    具体解释将在代码中给出。

    /*
     * @Author: csc
     * @Date: 2020-12-08 14:12:16
     * @LastEditTime: 2020-12-11 00:02:42
     * @LastEditors: Please set LastEditors
     * @Description: In User Settings Edit
     * @FilePath: \code\data structure\ls_tree.cpp
     */
    #include <iostream>
    #include <algorithm>
    #include <string>
    #include <string.h>
    #include <cmath>
    #include <map>
    #include <vector>
    #include <stack>
    using namespace std;
    // 联结词优先 ! * | - =  高到低
    unsigned char prior[7][7] = { //比较大小关系
        '>', '<', '<', '<', '<', '<', '>', 
        '>', '>', '<', '<', '<', '<', '>', 
        '>', '>', '>', '<', '<', '<', '>', 
        '>', '>', '>', '>', '<', '<', '>', 
        '>', '>', '>', '>', '<', '>', '>', 
        '<', '<', '<', '<', '<', '<', '=', 
        '>', '>', '>', '>', '>', ' ', '>', };
    char opset[7] = {'=', '-', '/', '*', '!', '(', ')'};
    /**
     * @description: 假设有两个变量x,y;不妨设x为先出现的变量,则它对应的
     * 应为行数,y则对应列数,此时便可列优先级方阵,其中‘<'代表x的优先级小于y
     */
    int returnOpOrd(char op, char *TestOp) // 返回运算符对应的下标
    {
        int i;
        for (i = 0; i < 7; i++)
        {
            if (op == TestOp[i])
                return i;
        }
        return 0;
    }
    char precede(char Aop, char Bop)//返回优先级大小关系
    {
        return prior[returnOpOrd(Aop, opset)][returnOpOrd(Bop, opset)];
    }
    bool isdigit(char ch) //判断数据
    {
        if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))
            return true;
        return false;
    }
    bool isop(char ch) //判断运算符
    {
        if (ch == '=' || ch == '-' || ch == '|' || ch == '*' || ch == '!')
            return true;
        return false;
    }
    stack<char> oper;      //运算符栈
    map<char, int> mp;     //每次赋值
    vector<char> argument; //命题变元
    vector<int> ans; // 答案向量
    int a[55];      //赋值
    string formula; //公式
    int handle_argument()
    /**
     * @description: 处理命题公式,提取其中的命题变元,
     * 注意这里可能出现两个或两个以上的相同的变元,但存储的
     * 时候只需存储一次
     */
    {
        int len = formula.length();// formula存储命题公式
        int ii = 0;
        for (int i = 0; i < len; ++i)
        {
            if (isop(formula[i]) || formula[i] == '(' || formula[i] == ')')
                continue;
            else
            {
                if (ii == 0)
                {
                    argument.push_back(formula[i]);
                    ++ii;
                }
                else
                {
                    bool flag = true;
                    for (int j = 0; j < ii; ++j)
                        if (argument[j] == formula[i])
                        {
                            flag = false;
                            break;
                        }
                    if (flag)
                    {
                        argument.push_back(formula[i]);
                        ++ii;
                    }
                }
            }
        }
        // display
        for (auto x : argument)//采用迭代器输出提取好的命题变元
            cout << x << '\t';
        cout << endl;
        return argument.size();
    }
    void truth(int times)
    /**
     * @description: 二进制赋值法
     * 根据传入参数times的值采用数组进行
     * 模拟二进制存储
     */
    {
        int i = argument.size() - 1;
        while (times)
        {
            a[i] = (times & 1);
            times >>= 1;
            --i;
        }
        int len = argument.size();
        for (i = 0; i < len; ++i)
            mp[argument[i]] = a[i];
        // display
        for (int i = 0; i < len; ++i)
            cout << a[i] << '\t';
        cout << endl;
    }
    typedef struct node
    {
        char oper;//运算符
        char num;//变元
        struct node *l;
        struct node *r;
    } * bitnode;//结点定义
    stack<bitnode> tree;//结点栈
    bitnode root, lc, rc;
    void creat_num(bitnode &root, bitnode L, bitnode R, char ch)
    {
        bitnode T = new node;
        T->num = ch;
        T->l = L;
        T->r = R;
        root = T;
    }
    void creat_op(bitnode &root, bitnode L, bitnode R, char ch)
    {
        bitnode T = new node;
        T->oper = ch;
        T->l = L;
        T->r = R;
        root = T;
    }
    void judge_cal()
    /**
     * @description: 辅助函数
     * 判断运算符,并根据运算符不同进行建树
     */
    {
        char cc;
        cc = oper.top();
        oper.pop();
        if (cc == '!')
        /**
         * 显然!只管一个命题变元,故而只需将根节点设为!,
         * 左孩子连接一个变元,右孩子置空即可
         */
        {
            lc = tree.top();
            tree.pop();
            creat_op(root, lc, NULL, cc);
            tree.push(root);
        }
        else
        /**
         * 对于其他运算符则管得到两个变元,故而左右孩子应各接一个变元
         */
        {
            rc = tree.top();
            tree.pop();
            lc = tree.top();
            tree.pop();
            creat_op(root, lc, rc, cc);
            tree.push(root);
        }
    }
    void build()
    /**
     * @description: 建树过程
     */
    {
        int len = formula.length();
        root = lc = rc = NULL;
        for (int i = 0; i < len; ++i)
        {
            if (isdigit(formula[i]))//若为变元,则建议一个树,根节点为变元,左右孩子置空
            {
                creat_num(root, NULL, NULL, formula[i]);
                tree.push(root);
            }
            else if (isop(formula[i]))//是运算符(联结词)
            {
                while (1)
                {
                    if (oper.empty() || oper.top() == '(')//联结词栈空或为(直接压栈
                    {
                        oper.push(formula[i]);
                        break;
                    }
                    else if (precede(oper.top(), formula[i]) == '<')//后进的优先级较大,则入栈
                    {
                        oper.push(formula[i]);
                        break;
                    }
                    else//否则进行运算
                        judge_cal();
                }
            }
            else//读取的是 ( 或 )
            {
                if (formula[i] == '(')// 直接压栈
                    oper.push(formula[i]);
                else
                {
                    while (oper.top() != '(')// 对一个()内的内容运算完,建成一棵树
                        judge_cal();
                    oper.pop();
                }
            }
        }
        while (!oper.empty())//若联结词栈还有元素,则应拿出来建树
            judge_cal();
    }
    int get_value(char c, int L, int R)
    /**
     * @description: 辅助函数
     * 对每一个结点进行运算,判断输入的运算符
     * 然后根据不同的联结词对应的值进行运算,看结果为0或1;并将运算结果返回
     */
    {
        int res = 0;
        if (c == '!')
        {
            L ^= 1;
            res = L;
        }
        else
        {
            if (c == '*')
                res = (L & R);
            else if (c == '|')
                res = (L | R);
            else if (c == '-')
            {
                if (L == 1 && R == 0)
                    res = 0;
                else
                    res = 1;
            }
            else if (c == '=')
            {
                if ((L && R) || (L == 0 && R == 0))
                    res = 1;
                else
                    res = 0;
            }
        }
        return res;
    }
    int calculate(bitnode T)
    /**
     * @description: 后序遍历二叉表达树进行运算
     */
    {
        int l = 0, r = 0;
        if (T->l == NULL && T->r == NULL)
            return mp[T->num];//我对处理好的变元及每一次赋值采用map进行存储,方便找值
        else
        {
            l = calculate(T->l);
            if (T->r)
                r = calculate(T->r);
            return get_value(T->oper, l, r);
        }
    }
    string s[100];//存储主析取范式
    void in(int id)//根据最后的结果进行输出对应的主析取范式
    {
        s[id] = "";
        s[id] += '(';
        int len = argument.size();
        for (int i = 0; i < len; ++i)
        {
            if (a[i] == 0)
            {
                s[id] += '!';
                s[id] += argument[i];
            }
            else
            {
    
                s[id] += argument[i];
            }
            if (i != len - 1)
                s[id] += '*';
        }
        s[id] += ')';
    }
    void init()//若进行若此运算,则应将对应的容器都进行清空,否则容易访问出错
    {
        while (!tree.empty())
            tree.pop();
        while (!oper.empty())
            oper.pop();
        ans.clear();
        argument.clear();
    }
    
    int main()
    {
        //cout << "请输入公式:" << endl;
        while (cin >> formula)
        {
            init();
            cout << "提取的命题变元及其赋值情况" << endl;
            int n = handle_argument();
            build();
            int times = 0, ma = pow(2, n);//2^n种赋值情况
            while (times < ma)
            {
                memset(a, 0, sizeof(a));
                truth(times);
                if (calculate(root))
                {
                    in(ans.size());
                    ans.push_back(times);
                }
                times++;
            }
            cout << "得到的结果:" << endl;
            if (ans.empty())
            {
                cout << "主析取范式不存在" << endl
                     << endl;
                continue;
            }
            for (auto v : ans)
                cout << v << " ";
            cout << endl;
            cout << "对应的主析取范式:" << endl;
            int cnt = ans.size();
            for (int i = 0; i < cnt - 1; cout << "|", ++i)
                cout << s[i];
            cout << s[cnt - 1] << endl
                 << endl;
        }
    
        return 0;
    }
    
    展开全文
  • 主析取范式 对任意一个命题公式来说,主析取范式与主合取范式都是唯一的。 命题变元指原子化的,P,Q命题。 极小项的定义:包含全部N个命题变元的合取式,称其为极小项,且N个命题变元中,每个变元与它的否定不能...
  • 请根据给定的命题公式,计算其真值为T的小项,列出主析取范式,并输出结果。 【输入形式】 输入一个字符串(字符串长度<=50)形式的命题公式,以回车表示输入结束。其中的命题公式为仅包含原子命题、联结词和...
  • 求公式(p∨q)→r的主析取范式。 [输入] 本题无输入。 [输出] 在单独的一行中输出公式的主析取范式,所有极小项按照对应的解释的字典顺序输出,即┐p∧┐q∧┐r是字典序的第一个极小项,p∧q∧r是字典序的最后...
  • 计算主析取范式 【问题描述】 请根据给定的命题公式,计算其真值为T的小项,列出主析取范式,并输出结果。 【输入形式】 输入一个字符串(字符串长度<=50)形式的命题公式,以回车表示输入结束。其中的命题公式为...
  • 编程实现求解逻辑表达式的真值表、主析取范式、主合取范式对于一个含n个命题变元的表达式(n为相异的命题变元总个数),其真值表可看作由从0到2ⁿ-1的二进制数的变化表。因此,可以通过按行列举0到2ⁿ-1的二进制数来...
  • 离散数学上机实验,给定一个命题公式,求其主析取范式,主合取范式,能力有限,参考了我学长的一篇博客,并进行了许多优化。 本次离散数学实验,我学到了许多东西,也看了自己的不足之处 1).我深刻地体会到在比较...
  • 离散数学实验报告
  • 主析取范式和主合取范式

    千次阅读 2021-04-06 15:31:04
    主析取范式 小项 是n个命题变元的合取式,其中每个变元必出现且仅出现一次(以本身或否定形式),称这个合取式为小项 例:含有两个变元的小项 P ^ Q , P ^ !Q , !P ^ Q , !P ^ !Q 若有n个变元,则有2的n次方个小项 ...
  • 范式包含析取范式和合取范式,而主析取范式和主合取范式的求解也是命题逻辑的重要内容,小项和大项也是必须掌握的内容。
  • 实验原理 使用的数据结构和存储结构: 栈(中缀转后缀并计算) 数组(存放真值表) map(存放命题变元以及对应的真假值) #include #include #include #include ... cout 主析取范式为:" ; cout 主合取范式为:" ; }
  • 题目:根据给定的式子,先输出其真值表,再利用真值表法求取主析取范式以及主合取范式,输出答案。 举例:以 (P^Q) V (非P^R) 为例。 程序代码 //(P^Q) V (非P^R) //主合取范式: (非PVQV非R) ^ (非PVQVR) ^ (PV非...
  • 本文属于「离散数学」系列文章之一。这一系列着重于离散数学的学习和应用。由于内容随时可能发生更新变动,欢迎关注和收藏离散数学系列文章汇总目录一文以作备忘。此外,在本系列学习文章中,为了透彻理解数学知识,...
  • 法一:相信大家都会的方法是——真值表法, 把真值表写出来后,把真值为1的项合取的结果就是主析取范式, 把真值为0的项析取的结果就是主合取范式。 法二(重点):这里讲得是配凑法。配凑法能直接配出来主析取范式...
  • 根据命题公式真值表求主析取范式。 输入格式: 第一行为命题中符号的个数(最大不超过8); 第二行开始到最后为命题公式的真值表最后一列。 输出格式: 输出主析取范式。 注意: 1.逻辑连接词非为!,与为^,或为+; 2....
  • 编程实现用真值表法求取任意数量变量的合式公式的主析取范式和主合取范式。 要求: 能够列出任意合式公式的真值表并给出相应主析取和主合取范式。 内容: 编程实现用真值表法求取任意数量变量的合式公式的主析取...
  • 南京邮电大学离散数学主析取范式和主合取范式实验代码。 因为CSDN上没有好的代码,于是博主自己写了一篇。 ```cpp #include <iostream> #include <cstdlib> #include <vector> #include <...
  • 离散数学中求合取范式&析取范式

    千次阅读 2018-03-22 17:36:00
    //获取主析取范式 string getND(); //获取主合取范式 void printSource() { cout ; } void printDNormal() //打印合取串 { cout ; } void printCNormal() //打印析取串 { cout ; } void ...
  • 主析取范式和主合取范式的c++求解程序

    千次阅读 多人点赞 2019-10-27 19:40:14
    主要思想是:先求真值表,再根据真值表输出主析取范式和主合取范式。 用!来表示非,用小写v表示析取,用^来表示合取,用~来表示双条件,用-来表示条件,用大写字母来表示命题变元。 真值表的求...
  • 实 验 一利用真值表法求取主析取范式以及主合取范式的实现 实验名称:利用真值表法求取主析取范式以及主合取范式的实现 实验目的:通过编程实现主析取范式以及主合取范式的真值表求法以巩固相关理论的掌握 实验...
  • 构造主析取范式离散数学

    千次阅读 2019-06-11 09:12:58
    构造主析取范式 先上图。。。 主界面: 真值表: 主析取范式
  • 给定公式中的命题变元,以及所有极小项(或极大项)的解释,可以计算出对应主范式。 在LaTeX中,公式按照这种格式:把符号串放入一对$中。 于是$P\vee \neg Q\wedge R$会显示为P∨¬Q∧R。 Word的公式编辑器也是用...
  • 关于离散数学中主合取与主析取范式的实现,主要通过c++实现
  • if (s1.length()==0){ System.out.println("主析取范式:\n空"); }else { System.out.println("主析取范式:\n" + s1); } if (s2.length()==0){ System.out.println("主合取范式:\n空"); } else { System.out....
  • 公式的主析取范式和主合取范式,输出形式为:“ mi ∨ mj ; Mi ∧ Mj” ,极小项和 ∨ 符号之间有一个空格,极大项和 ∧ 符号之间有一个空格;主析取范式和主合取范式之间用“ ; ”隔开,“ ; ”前后各有一个空格。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 426
精华内容 170
关键字:

离散数学主析取范式