精华内容
下载资源
问答
  • 【问题描述】 请根据给定的命题公式,计算其真值为T的小项,列出主析取范式,并输出结果。 【输入形式】 输入一个字符串(字符串长度)形式的命题公式,以回车表示输入结束。其中的命题公式为仅包含原子命题、联结词...

    【问题描述】

    请根据给定的命题公式,计算其真值为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
    本方法涉及栈的应用,经过本人测试正确
    代码如下:

    #include <stdio.h>
    #
    展开全文
  • 主析取范式和主合取范式的c++求解程序

    千次阅读 多人点赞 2019-10-27 19:40:14
    主要思想是:先求真值表,再根据真值表输出主析取范式和主合取范式。 用!来表示非,用小写v表示析取,用^来表示合取,用~来表示双条件,用-来表示条件,用大写字母来表示命题变元。 真值表的求...

    这是我们老师刚刚布置的作业,自己百度了一下,发现没有比较简单完善的程序代码,于是自己写成功后,与大家分享一下。有些地方描述的不好,可能比较难理解,请见谅。如果有啥不懂的,可以在下面评论,我会尽力解答
    一、算法思想
    主要思想是:先求真值表,再根据真值表输出主析取范式和主合取范式。

    用!来表示非,用小写v表示析取,用^来表示合取,用~来表示双条件,用-来表示条件,用大写字母来表示命题变元。

    真值表的求解
    ① 根据命题的个数n,得出所有命题变元赋值的情况个数sum,例如n=4个命题变元,则有sum=2^4种情况,并将所有情况存入二维数组a[i][j]中,a[i]代表第i种情况。
    ② 创建两个栈,一个用来存放操作符Operator,先自己在栈里面存放字符‘#’(输入命题公式时要最后应该加一个字符‘#’);一个存放操作数Operand。
    ③ 根据表达式求值的思想,读取表达式,若是操作符,则与之前的操作符相比优先级,若大于前者,则读取下一个;若相等,则说明两者为()则弹出前者,读取下一个;若小于前者,则可以进行运算;
    ④ 若读取的是操作数,则在数组a中读取操作数所对应的数,存入栈中;
    ⑤ 将最后的运算结果存入数组result中,再次循环步骤③,循环sum次即可
    ⑥ 根据result的结果,当输出主析取范式时,当result[i]==1时,则输出相应的命题变元(当命题变元为1则输出P,为0则输出!P),把result都遍历一遍,将结果为1的都连在一起即可;求取主合取范式就将result=0的输出连在一起即可;
    二、源代码

    第一个头文件const.h//预定义常量头文件
    #pragma once

    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 1
    #define INFEASIBLE -1
    #define OVERFLOW -2

    typedef int Status;

    第二个头文件prefunction.h//变量类型的定义与函数的声明
    #pragma once

    #include"const.h"

    #define STACK_INIT_SIZE 100
    #define STACKINCREMENT 10

    typedef char SElemType;

    typedef int SElemType_1;

    typedef struct {
    SElemType *base;
    SElemType *top;
    int stacksize;
    }SqStack;//操作符栈

    typedef struct {
    SElemType_1 *INTbase;
    SElemType_1 *INTtop;
    int INTstacksize;
    }INTStack;//操作数栈
    Status InitStack(SqStack &S);//初始化
    Status GetTop(SqStack S, SElemType &e);//读栈顶
    Status Push(SqStack &S, SElemType e);//入栈
    Status Pop(SqStack &S, SElemType &e);//出栈
    Status initStack(INTStack &S);// 初始化
    Status pop(INTStack &S, SElemType_1 &e);// 出栈
    Status push(INTStack &S, SElemType_1 e);// 入栈
    char precede(SElemType e1, SElemType e2);//判断操作数的优先级
    Status bothway(int &a, SElemType b, int c);//双向运算符操作
    Status TruthTable(int a[65][6], int count,char ch[6]);//真值表
    Status Proposition(char a[50], char ch[6]);//求命题的个数

    第二个头文件function.h
    #pragma once
    #include
    #include
    #include

    #include"prefunction.h"

    Status InitStack(SqStack &s) {
    //构造一个空的栈
    s.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if (!s.base)
    exit(OVERFLOW);
    s.top = s.base;
    s.stacksize = STACK_INIT_SIZE;
    return OK;
    }
    Status GetTop(SqStack s, SElemType &e) {
    //获得栈顶元素
    if (s.top == s.base)
    return ERROR;
    e = (s.top - 1);
    return OK;
    }
    Status Push(SqStack &s, SElemType e) {
    //插入元素e为新的栈顶
    if (s.top - s.base >= s.stacksize) {
    s.base = (SElemType
    )realloc(s.base, (s.stacksize + STACKINCREMENT) * sizeof(SElemType));
    if (!s.base)
    exit(OVERFLOW);
    s.top = s.base + s.stacksize;
    s.stacksize += STACKINCREMENT;
    }
    *s.top++ = e;
    return OK;
    }
    Status Pop(SqStack &s, SElemType &e) {
    //弹出栈顶元素
    if (s.top == s.base)
    return ERROR;
    e = –s.top;
    return OK;
    }
    Status initStack(INTStack &s)
    {
    //构造一个空的栈
    s.INTbase = (SElemType_1
    )malloc(STACK_INIT_SIZE * sizeof(SElemType_1));
    if (!s.INTbase)
    exit(OVERFLOW);
    s.INTtop = s.INTbase;
    s.INTstacksize = STACK_INIT_SIZE;
    return OK;
    }
    Status pop(INTStack &s, SElemType_1 &e)
    {//弹出栈顶元素
    if (s.INTtop == s.INTbase)
    return ERROR;
    e = –s.INTtop;
    return OK;
    }
    Status push(INTStack &s, SElemType_1 e)
    {
    //插入元素e为新的栈顶
    if (s.INTtop - s.INTbase >= s.INTstacksize) {
    s.INTbase = (SElemType_1
    )realloc(s.INTbase, (s.INTstacksize + STACKINCREMENT) * sizeof(SElemType_1));
    if (!s.INTbase)
    exit(OVERFLOW);
    s.INTtop = s.INTbase + s.INTstacksize;
    s.INTstacksize += STACKINCREMENT;
    }
    *s.INTtop++ = e;
    return OK;
    }
    char precede(SElemType e1, SElemType e2)//判断操作数的优先级
    {
    if (e1 == ‘v’&&e2 == ‘v’)
    return ‘>’ ;
    if (e1 == ‘v’&&e2 == ‘^’)
    return ‘>’;
    if (e1 == ‘v’&&e2 == ‘~’)
    return ‘>’;
    if (e1 == ‘v’&&e2 == ‘-’)
    return ‘>’;
    if (e1 == ‘v’&&e2 == ‘)’)
    return ‘>’;
    if (e1 == ‘v’&&e2 == ‘(’)
    return ‘<’;
    if (e1 == ‘v’&&e2 == ‘#’)
    return ‘>’;

    if (e1 == '^'&&e2 == 'v')
    	return '>';
    if (e1 == '^'&&e2 == '^')
    	return '>';
    if (e1 == '^'&&e2 == '~')
    	return '>';
    if (e1 == '^'&&e2 == '-')
    	return '>';
    if (e1 == '^'&&e2 == ')')
    	return '>';
    if (e1 == '^'&&e2 == '(')
    	return '<';
    if (e1 == '^'&&e2 == '#')
    	return '>';
    
    if (e1 == '-'&&e2 == 'v')
    	return '>';
    if (e1 == '-'&&e2 == '^')
    	return '>';
    if (e1 == '-'&&e2 == '~')
    	return '>';
    if (e1 == '-'&&e2 == '-')
    	return '>';
    if (e1 == '-'&&e2 == ')')
    	return '>';
    if (e1 == '-'&&e2 == '(')
    	return '<';
    if (e1 == '-'&&e2 == '#')
    	return '>';
    
    if (e1 == '~'&&e2 == 'v')
    	return '>';
    if (e1 == '~'&&e2 == '^')
    	return '>';
    if (e1 == '~'&&e2 == '~')
    	return '>';
    if (e1 == '~'&&e2 == '-')
    	return '>';
    if (e1 == '~'&&e2 == ')')
    	return '>';
    if (e1 == '~'&&e2 == '(')
    	return '<';
    if (e1 == '~'&&e2 == '#')
    	return '>';
    
    if (e1 == '('&&e2 == 'v')
    	return '<';
    if (e1 == '('&&e2 == '^')
    	return '<';
    if (e1 == '('&&e2 == '~')
    	return '<';
    if (e1 == '('&&e2 == '-')
    	return '<';
    
    
    
    if (e1 == '#'&&e2 == 'v')
    	return '<';
    if (e1 == '#'&&e2 == '^')
    	return '<';
    if (e1 == '#'&&e2 == '~')
    	return '<';
    if (e1 == '#'&&e2 == '-')
    	return '<';
    if (e1 == '#'&&e2 == '(')
    	return '<';
    
    if (e1 == '!'&&e2 == 'v')
    	return '>';
    if (e1 == '!'&&e2 == '^')
    	return '>';
    if (e1 == '!'&&e2 == '~')
    	return '>';
    if (e1 == '!'&&e2 == '-')
    	return '>';
    if (e1 == '!'&&e2 == ')')
    	return '>';
    if (e1 == '!'&&e2 == '(')
    	return '<';
    if (e1 == '!'&&e2 == '#')
    	return '>';
    
    
    
    if (e1 == 'v'&&e2 == '!')
    	return '<';
    if (e1 == '^'&&e2 == '!')
    	return '<';
    if (e1 == '~'&&e2 == '!')
    	return '<';
    if (e1 == '-'&&e2 == '!')
    	return '<';
    if (e1 == '#'&&e2 == '!')
    	return '<';
    
    
    
    
    
    if (e1 == '('&&e2 == '(')
    	return '<';
    if (e1 == '('&&e2 == ')')
    	return '=';
    return 'p';
    

    }
    //用小写的v来表示析取;用^来表示合取;用-来表示条件;用~来表示双条件;
    Status bothway(int &a, SElemType b, int c)
    {
    if ( b ==‘v’) {
    if (a == 0 && c == 0)
    a = 0;
    else
    a = 1;
    }
    if (b ‘^’) {
    if (a == 1 && c == 1)
    a = 1;
    else
    a = 0;
    }
    if (b == ‘-’) {
    if (a == 1 && c == 0)
    a = 0;
    else
    a = 1;
    }
    if (b == ‘~’) {
    if (a == c)
    a = 1;
    else
    a = 0;
    }
    return OK;
    }
    Status TruthTable(int a[65][6], int count,char ch[6])//真值表
    {
    int i,sum=1,s,k,j;
    for (i = 0; i < count; i++)
    sum = sum * 2;
    i = 1;
    s = sum;
    while (i <= count) {
    s = s / 2;
    k = 0;
    j = 1;
    while (j <= sum) {
    if((j/s)%2
    0)
    for (k = 0; k < s; k++) {
    a[j-1][i-1] = 0; j++;
    }
    else
    for (k = 0; k < s; k++) {
    a[j-1][i-1] = 1; j++;
    }
    }
    i++;
    }

    return OK;
    

    }
    Status Proposition(char a[50], char ch[6])//求命题的个数
    {
    int i=0,j=0,k=0;
    int flag = 0;
    while (a[i]) {
    if (a[i] >= 65 && a[i] <= 90) {
    while (ch[j]) {
    if (a[i] == ch[j])
    flag = 1;
    j++;
    }
    if (flag == 0) {
    ch[k] = a[i];
    k++;
    }
    flag = 0;
    j = 0;
    }
    i++;
    }
    return OK;
    }
    第四个文件是cpp文件:xiquhequ.cpp
    #include"function.h"

    using namespace std;

    int main() {

    int n,a[65][6],sum=1,s;
    char exqu[50], ch[6] = {0};
    printf_s("请输入命题的个数:");
    scanf("%d", &n);
    printf_s("请输入命题表达式:");
    scanf("%s", exqu);
    for (s = 0; s < n; s++) {
    	sum = sum * 2;
    }//求所有的情况个数sum
    
    
    Proposition(exqu,ch);//将n个变量变元提取出来存入字符数组ch
    
    TruthTable(a, n, ch);//将所有情况存入数组a中
    
    
    SqStack Operator;//操作符栈
    INTStack Operand;//操作数栈
    InitStack(Operator);//初始化
    initStack(Operand);//初始化
    
    
    SElemType e;
    int k = 0,result[65];
    int i = 0,j=0;
    SElemType_1 p, q;
    SElemType	E;
    
    while (k < sum)
    {
    	*Operator.top = '#';
    	Operator.top++;
    	GetTop(Operator, e);
    	i = 0;
    	while (exqu[i] != '#' || e != '#') 
    	{
    
    
    		if (exqu[i] <= 90 && exqu[i] >= 65) {
    			while (exqu[i] != ch[j]) {
    				j++;
    			}
    			push(Operand, a[k][j]);
    			//print(Operand);
    			//*Operand.INTtop = a[k][j];// printf_s("%d", a[k][j]);
    			//Operand.INTtop++;
    			j = 0;
    			i++;
    		}
    		else {
    			GetTop(Operator, e);
    			switch (precede(e, exqu[i])) {
    			case '<':Push(Operator, exqu[i]); i++;
    				break;
    			case '=':Pop(Operator, e); i++;
    				break;
    			case '>':Pop(Operator, E); 
    				if (E == '!')
    				{
    					pop(Operand, p);
    					if (p == 0)
    						p = 1;
    					else
    						p = 0;	
    					push(Operand, p);
    
    					//print(Operand);
    					//printf("%d", p);
    				}
    				else
    				{
    					pop(Operand, p); pop(Operand, q);  bothway(q, E, p); push(Operand, q);//print(Operand);
    				}
    				break;
    			default:printf_s("precede函数返回值错误\n");
    			}
    		}
    		GetTop(Operator, e);
    	}
    
    	pop(Operand, q);
    	//printf("%d\n", q);
    	result[k] = q;
    	k++;
    	Pop(Operator, e);
    	//Pop(Operator, e);
    
    
    }
    
    
    for (i = 0; i < n; i++) {
    	printf_s("%c    ", ch[i]);
    }
    i = 0;
    while (exqu[i]!='#') {
    	printf_s("%c", exqu[i]);
    	i++;
    }
    printf_s("\n");
    for (k = 0; k < sum; k++) {
    
    	for (i = 0; i < n; i++) {
    		printf_s("%d    ", a[k][i]);
    	}
    	printf_s("%d", result[k]);
    	printf_s("\n");
    }
    
    //输出主析取范式
    printf_s("主析取范式\n");
    for (k = 0; k < sum; k++)
    {
    	if (result[k] == 1)
    	{
    		printf_s("(");
    		for (i = 0; i < n; i++)
    		{
    			if (a[k][i] == 1)
    				printf_s("%c^", ch[i]);
    			else
    				printf_s("!%c^", ch[i]);
    		}
    		printf_s("\b)v");
    	}		
    }
    printf_s("\b \n");
    
    //输出主合取范式
    printf_s("主合取范式\n");
    for (k = 0; k < sum; k++)
    {
    	if (result[k] == 0)
    	{
    		printf_s("(");
    		for (i = 0; i < n; i++)
    		{
    			if (a[k][i] == 1)
    				printf_s("%c^", ch[i]);
    			else
    				printf_s("!%c^", ch[i]);
    		}
    		printf_s("\b)v");
    	}
    }
    printf_s("\b ");
    getchar();
    getchar();
    return 0;
    

    }
    三,输入输出结果

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • C语言求解合式公式的主合取范式和主析取范式

    千次阅读 多人点赞 2021-04-30 17:34:28
    //主合取十进制下标 } } puts("\n主析取范式为:"); for(i=0;i;i++){ printf("m%d%s",result_disjunction[i],i^disjunction_top?"&":""); } puts("\n主合取范式为:"); for(i=0;i;i++){ printf("M%d%s",result_...

    我最爱的冯老师在离散课上出了一个附加题。
    为了能够加更多的学分也是出于自己的好奇,我决定尝试一下。
    思路:二进制枚举+逆波兰表达式

    #include<stdio.h>
    #include<string.h>
    #define T 1
    #define F 0
    
    struct Stack{
        int top;
        char arr[80];
    }number={-1},symbol={-1};
    //number储存后缀表达式结果
    //symbol 操作符栈,用来保存操作符 
    
    int book[26];//记录变元元素和个数 
    //a对应下标为0
    //b对应下标为1
    //c对应下标为2
    //以此类推 
    int num=0;//记录变元的个数 
    int alphabet_true_false[26];
    /*
    上面的book数组每个元素存放的是
    该下标对应的字母是否存在
    
    类似的这个alphabet_true_false存放的是
    该下标对应的字母变元的真值(true or false) 
    当然,只有book[i]不为零的情况下该数组才会奏效 
    */ 
    int enum_result[80];
    /*
    如果二进制值为110110010
    那么该数组从前往后数每个元素分别为:
    1 1 0 1 1 0 0 1 0
    说白了就是把十进制转为二进制01值并存到enum_result里罢了 
    */
    
    
    
    char str_copy[80];//输入的字符串的副本 
    
    void count_num(char str[]){//记录变元的个数,用全局变量num储存 
    	int i,len=strlen(str);
    	for(i=0;i<len;i++){
            if(str[i]>='a'&&str[i]<='z'){
                if(book[str[i]-'a']==0){ 
    				book[str[i]-'a']=1;    
    				++num; 
    			} 
        	}      
        }
    }
     
    void scan_string(char str[]){
    	//输入小写字符
    	//例如!(p|q)>(q&!r|(r>p)) 
    	int i;
        gets(str);
        strcpy(str_copy,str);
        
        count_num(str);//记录变元的个数,用全局变量num储存 
        int len=strlen(str);
        for(i=0;i<len;i++){
        	//对操作符进行优先级处理
    		//把字符数组的操作符改为计算机可判断优先级的特别字符 
            switch(str[i]){
                case '!':str[i]=')'+5;break;
                case '&':str[i]=')'+4;break;
                case '|':str[i]=')'+3;break;
                case '>':str[i]=')'+2;break;
                case '=':str[i]=')'+1;break;
            }        
        }
    }
    
    void reverse_polish(char s[]){
    	//把命题公式改为后缀表达式
    	//并把后缀处理的结果保存在number结构体里
    	//number结构体里原本存放的是变元,就是那些字母。
    	//symbol里存放的是操作符, 经过后缀处理完后symbol里应该为空。 
    	//经过后缀处理完后就会把symbol里的操作符也转移到了number里 
        int i,len=strlen(s);
        for(i=0;i<len;i++){
            if(s[i]>='a'&&s[i]<='z'){//如果是命题变元就直接入number栈 
                number.arr[++number.top]=s[i];          
            }else if(s[i]>')'&&s[i]<=5+')'){
                if(symbol.top==-1||symbol.arr[symbol.top]==')'){
                    ++symbol.top;
                    symbol.arr[symbol.top]=s[i];
                }else if(s[i]>=symbol.arr[symbol.top]){
                    ++symbol.top;
                    symbol.arr[symbol.top]=s[i];
                }else{
                    while(symbol.top!=-1&&s[i]<symbol.arr[symbol.top]){
                        ++number.top;
                        number.arr[number.top]=symbol.arr[symbol.top];
                        --symbol.top;
                    }
                    --i;
                }
            }
    		else if(s[i]=='('||s[i]==')'){
    		    if(s[i]=='('){
                    ++symbol.top;
                    symbol.arr[symbol.top]=s[i];
                }else{
                    while(symbol.arr[symbol.top]!='('){
                        ++number.top;
                        number.arr[number.top]=symbol.arr[symbol.top];
                        --symbol.top;              
                    }
                    if(symbol.top!=-1)--symbol.top;
                }
            }       
        }
        while(symbol.top!=-1){
            ++number.top;
            number.arr[number.top]=symbol.arr[symbol.top];
            --symbol.top;                                
        }
    }
    
    int check(int num){//判断enum_result[]的二进制情况组成的是极小值(return 1)还是极大值(return 0)
    	struct Stack ans={-1};
    	int i,k=0,len=0,temp;
    	for(i=0;i<26;i++){
    		if(book[i]){
    			++len;
    			alphabet_true_false[i]=enum_result[k++];//enum_result里只有真或假(1,0) 
    			//这一步类似于变元p被赋值为false(0)
    			//或者t被赋值为true(1)
    		}
    	}
    	for(i=0;i<=number.top;i++){
    		if(number.arr[i]>='a'&&number.arr[i]<='z'){
    			++ans.top;
    			ans.arr[ans.top]=alphabet_true_false[number.arr[i]-'a'];
    		}else{
    			switch(number.arr[i]){
    				case '.':
    					ans.arr[ans.top]=!ans.arr[ans.top];
    					break;
    				case '-':
    					ans.arr[ans.top-1]=ans.arr[ans.top-1]&ans.arr[ans.top];
    					--ans.top;
    					break;
    				case ',':
    					ans.arr[ans.top-1]=ans.arr[ans.top-1]|ans.arr[ans.top];
    					--ans.top;
    					break;
    				case '+':
    					ans.arr[ans.top-1]=!ans.arr[ans.top-1]|ans.arr[ans.top];
    					--ans.top;
    					break;
    				case '*':
    					ans.arr[ans.top-1]=
    									 (!ans.arr[ans.top-1]|ans.arr[ans.top])
    									&(!ans.arr[ans.top]|ans.arr[ans.top-1]);
    					--ans.top;
    					break;
    			}
    		}
    	}
    	printf("%4d\n",ans.arr[0]); 
    	return ans.arr[0];
    }
    
    void binary_enumeration(int num){
    	//二进制枚举 2^num次 遍历所有情况 
    	//
    	int i,j;
    	int conjunction_top=-1,disjunction_top=-1;/*也把下面的两个数组看作栈,
    	使用这两个top变量指向的就是栈顶元素的下标 */ 
    	int result_conjunction[80]={0};//储存的是主合取结果 
    	int result_disjunction[80]={0};//储存的是主析取结果 
    	
    	
    	for(i=0;i<26;i++)
            if(book[i])printf("%4c|",i+'a');
    	putchar(' '),puts(str_copy);
    	
    	//二进制枚举用的是两层循环
    	//最外面的一层循环如果num是4
    	//则1<<num的二进制就为(1111),十进制就是15
    	//说白了就是循环15次,让变量i自增15次 
    	//而里面的循环则是:
    	//读取变量i的二进制中的第j位比特值
    	//假如变量i位5,则i的二进制就是101
    	// 
    	for(i=0;i<(1<<num);i++){// 
    		memset(enum_result,0,num);
    		for(j=0;j<num;j++){//这一层的循环说白了就是把变量j的值转换为对应的二进制,并把二进制值储存到enum_result数组里 
    			if(i&(1<<(num-j-1))){
    				enum_result[j]=T;
    			}else{
    				enum_result[j]=F;
    			}
    			printf("%4d|",enum_result[j]);
    		}
    		//里层循环完之后现在的enum_result每一位里存放的就是j的二进制对应的值 
    		if(check(num)){
    			result_disjunction[++disjunction_top]=i;//主析取十进制下标 
    		}else{
    			result_conjunction[++conjunction_top]=i;//主合取十进制下标 
    		}
    	}
    	puts("\n主析取范式为:");
    	for(i=0;i<=disjunction_top;i++){
    		printf("m%d%s",result_disjunction[i],i^disjunction_top?"&":"");
    	}
    	puts("\n主合取范式为:");
    	for(i=0;i<=conjunction_top;i++){
    		printf("M%d%s",result_conjunction[i],i^conjunction_top?"|":"");
    	}
    }
    
    void show(char str[]){
    	int i; 
    	puts("\n后缀表达式为:");
        for(i=0;i<=number.top;i++){
        	switch(number.arr[i]){
                case ')'+5:number.arr[i]='!';break;
                case ')'+4:number.arr[i]='&';break;
                case ')'+3:number.arr[i]='|';break;
                case ')'+2:number.arr[i]='>';break;
                case ')'+1:number.arr[i]='=';break;
            } 
            printf("%c",number.arr[i]);
        }
        
        puts("\n使用的命题变项:");
        for(i=0;i<26;i++)
            if(book[i])printf("%c ",i+'a');
    }
    
    /*
               优先级
    非  :!      5
    合取:&       4
    析取:|       3
    蕴涵:>       2
    等价:=       1
    */
    
    int main()
    {
        int i=0;
        char str[80];
        scan_string(str);//输入小写字符
    	reverse_polish(str);//逆波兰表达式 去括号 
        binary_enumeration(num);//把变元个数num传入函数
    	//有num个变元就有2^num个情况,对每一个二进制情况经进行heck(), 
    	show(str);
        return 0;
    }
    

    大一,寒假时为了蓝桥杯学了不少算法和数据结构的知识。
    写了将近4个小时。又复习了一遍后缀表达式。
    算法方面没有什么不理解的地方,大部分时间都是细节上的错误,
    比如

    for(i=0;i<=number.top;i++){
    	switch(number.arr[i]){
    	...
    	}
    }
    

    写成

    for(i=0;i<=number.top;i++){
    	switch(number.arr[number.top]){//循环的是i,我却循环成了栈顶元素。这个地方卡了差不多一个小时。可能是因为太晚了脑子有点糊涂
    	...
    	}
    }
    

    程序跑通了调的没bug了之后拿给老师看,老师理所当然的给出了肯定的评价;
    就是不知道她什么时候能把我这个分给加上。

    以下是运行结果:

    为了配的上我心中的那个执念
    lonely but only study
    lonely but only suppress

    展开全文
  • C语言实现主析取范式 第一次写,不喜勿喷 (先来水一波) 先保证输入的式子是合法的 (不合法我也不会,太弱了) 难点主要是计算真值表,可以用堆栈实现,建立两个堆栈,一个储存操作符,另一个储存数值 (手写堆栈) ...

    C语言实现主析取范式

    第一次写,不喜勿喷
    (先来水一波)
    先保证输入的式子是合法的 (不合法我也不会,太弱了)
    难点主要是计算真值表,可以用堆栈实现,建立两个堆栈,一个储存操作符,另一个储存数值 (手写堆栈)

    int OPNUM[300], OPOP[300], inum = 0, inop = 0;//储存数字和操作符的堆
    

    储存的是int类型,在这之前有将操作符转化成对应的优先级

    int charge_operator(char ch){//判断优先级
        if (ch == '!') return 1;
        else if (ch == '&') return 2;
        else if (ch == '|') return 3;
        else if (ch == '$') return 4;//单条件
        else if (ch == '@') return 5;//双条件
        else if (ch == '(') return 6;
        else if (ch == ')') return 7;
        return 10;
    }
    

    如果上一个操作符和这个操作符的优先级相同或者上一个操作符的优先级大于这个操作的优先级,则可以计算,也就是取上一个操作的操作符,和数值栈的前两个元素计算,然后再压入栈。否则操作符直接入栈,操作符堆其实是维持一个单调递增的序列。

    if(cha>=OPOP[inop] && inop){//保证有操作符
    	   int op = OPOP[inop];
    	   int a, b, c;
    	   a = OPNUM[inum-1], b = OPNUM[inum], inum--;//取数值栈的前两个
    	   c = operator_A(op, a, b);//计算数值
    	   OPNUM[inum]=c;//数值入栈
    	   OPOP[inop] = cha;//操作符入栈
    }
    else OPOP[++inop]=cha;
    

    这里主要判断一下条件非,和左括号:
    条件非的判断:只需要在每个数值入栈之前看一下操作符是不是条件非

    //f数组用来储存表达式
    if (f[i]=='0' || f[i] == '1'){
                if (OPOP[inop] == 1) {OPNUM[++inum] = (f[i] == '1'? 0:1); inop--;} //判断!的情况
                else OPNUM[++inum] = f[i] - '0';
            }
    

    在条件非入栈的时候,看一下上一个操作符是不是条件非,如果是两个条件非就相互抵消了,例如!!0, 两个非就直接抵消。

    如果是左括号直接入栈,如果是右括号,直接往前计算到左括号。
    最后别忘记堆栈中剩余的元素

     while(inop!=0){
            int op = OPOP[inop];
            inop--;
            int a, b, c;
            a = OPNUM[inum-1], b = OPNUM[inum], inum--;
            c = operator_A(op, a, b);
            OPNUM[inum]=c;
        }
    

    直接上代码

    #include<stdio.h>
    #include<bits/stdc++.h>
    #define extraction '|' //析取
    #define conjunction '&' //合取
    #define non '!'//非
    /*
    双条件@
    单条件$
    */
    char forluma[1100]; //表示表达式和表达式的列数,数组从1开始
    int n, col, row,num;//用来储存真值表中的行数和列数,num表示变量的个数
    int Map[300][300],mp[300],nowval[30];//用mp维护数组,map存放真值表,nowval存当前表达式每个字母的取值
    void init(){
        memset(forluma,0, sizeof(forluma));
        memset(Map, 0, sizeof(Map));
        memset(mp, 0, sizeof(mp));
        col=0,row=0;
    }
    void read(){
        char ch;
        int cnt = 0;
        while(scanf("%c", &ch) != EOF){
            if ((ch >='A' && ch <= 'Z') || ch == '(' || ch == ')' || ch ==extraction || ch == conjunction || ch == non
            || ch == '@' || ch == '$'){//去掉输入的空格空格
                forluma[++cnt] = ch;
            }
            if (ch >='A'&&ch<='Z'&&!mp[ch]){//用mp维护字母
                mp[ch]=++num;
            }
        }
        n = cnt, cnt = 0;
        for (int i = 1; i <= 100; i++){//离散化变量
            if (mp[i])mp[i]=++cnt;
        }
    }
    int operator_A(int ch, int x, int y){//计算式子的值
        if (ch == 2) return x & y;
        else if (ch == 3) return x | y;
        else if (ch == 4){
            if (x == 1 && y == 0) return 0;
            else return 1;
        } 
        else if(ch == 5){
            if (x == y) return 1;
            else return 0;
        }
        return 0;
    }
    int charge_operator(char ch){//判断优先级
        if (ch == '!') return 1;
        else if (ch == '&') return 2;
        else if (ch == '|') return 3;
        else if (ch == '$') return 4;
        else if (ch == '@') return 5;
        else if (ch == '(') return 6;
        else if (ch == ')') return 7;
        return 10;
    }
    
    char f[1200];//赋值的式子
    int calculate(){
        for (int i = 1; i <= n; i++){//把每个字母的值赋值给式子
            if (forluma[i] >='A' && forluma[i] <= 'Z') f[i]=nowval[mp[forluma[i]]] + '0';
            else f[i] = forluma[i];
        }
        int OPNUM[300], OPOP[300], inum = 0, inop = 0;//储存数字和操作符的堆
        for (int i = 1; i <= n; i++){
            if (f[i]=='0' || f[i] == '1'){
                if (OPOP[inop] == 1) {OPNUM[++inum] = (f[i] == '1'? 0:1); inop--;} //判断!的情况
                else OPNUM[++inum] = f[i] - '0';
            }
            else {
                int cha = charge_operator(f[i]);
                if(cha == 7){//右括号的情况
                    int op = OPOP[inop]; inop--;//取运算符
                    while(op != 6){//一直算到左括号
                        int a, b, c;
                        a = OPNUM[inum-1], b = OPNUM[inum], inum--;
                        c = operator_A(op, a, b);
                        OPNUM[inum]=c;
                        op=OPOP[inop--];
                    }
                    op=OPOP[inop];
                    if(op==1) {OPNUM[inum] = !OPNUM[inum];inop--;}//判断'('前面是不是条件非
                }
                else if(cha == 6) OPOP[++inop] = cha;
                else if (cha == 1){//条件非的判断
                    if(OPOP[inop] == 1) inop--;//!!0 = 0,两个非相互抵消
                    else OPOP[++inop] = cha;
                }
                else{
                    if(cha>=OPOP[inop] && inop){//保证有操作符,上一个操作符的优先级大于等于这个操作的优先级
                        int op = OPOP[inop];
                        int a, b, c;
                        a = OPNUM[inum-1], b = OPNUM[inum], inum--;
                        c = operator_A(op, a, b);
                        OPNUM[inum]=c;
                        OPOP[inop] = cha;
                    }
                    else OPOP[++inop]=cha;
                }
            }
        }
        while(inop!=0){//最后清空操作符栈
            int op = OPOP[inop];
            inop--;
            int a, b, c;
            a = OPNUM[inum-1], b = OPNUM[inum], inum--;
            c = operator_A(op, a, b);
            OPNUM[inum]=c;
        }
        return OPNUM[1];
    }
    void dfs(int now_x){//枚举每一种情况
        if (now_x  == num){
            row++;
            for (int i = 1; i <= now_x; i++) Map[row][i] = nowval[i];
            Map[row][now_x+1] = calculate();
            return ;
        }
        nowval[now_x + 1] = 0;
        dfs(now_x + 1);
        nowval[now_x + 1] = 1;
        dfs(now_x + 1);
    }
    
    void work(){
        dfs(0);
        printf("真值表:\n\t\t");
        char abc[30];
        int cnt = 0;
        for (int i = 1; i <= 100; i++){
            if (mp[i]) {printf("%c ", i);abc[++cnt]=i;}
        }
        printf("\n\t\t");
        for(int i = 1; i<=row; i++){
            for (int j = 1; j <= num + 1; j++){
                printf("%d ",Map[i][j]);
            }
            printf("\n\t\t");
        }
        char xi[2000], he[2000];
        int x=0, h=0;
        for (int i = 1; i <= row; i++){
            if (Map[i][num+1]==1){
                if (x) xi[++x] = '|';
                xi[++x] = '(';
                for (int j = 1; j <= num; j++){
                    if(j!=1)xi[++x]='&';
                    if (Map[i][j] == 0)xi[++x]='!';
                    xi[++x]=abc[j];
                }
                xi[++x]=')';
            }
            else {
                if (h)he[++h]='&';
                he[++h]='(';
                for (int j = 1; j <= num; j++){
                    if (j!=1)he[++h]='|';
                    if (Map[i][j]==1)he[++h]='!';
                    he[++h]=abc[j];
                }
                he[++h]=')';
            }
        }
        printf("\n主析取范式:");
        for (int i = 1; i <= x; i++) {
            if (xi[i]=='|') printf("∨");
            else if (xi[i]=='&') printf("∧");
            else if (xi[i]=='!') printf("ㄱ");
            else printf("%c",xi[i]);
        }
        printf("\n主合取范式:");
        for (int i = 1; i <= h; i++){
            if (he[i]=='|') printf("∨");
            else if (he[i]=='&') printf("∧");
            else if (he[i]=='!') printf("ㄱ");
            else printf("%c",he[i]);
        }
    }
    
    int main(){
        printf("请输入逻辑表达式:\n");
        printf("与逻辑:&  或逻辑:|  非逻辑:! 单条件:$  双条件:@\n");
        printf("请注意:表达式错误程序可能无法运行或者结果错误\n");
        init();
        read();
        work();
    }
    

    输入:

    (P$R)&(Q$!R)&(!R$(P|Q))
    

    输出:

    请输入逻辑表达式:
    与逻辑:&  或逻辑:|  非逻辑:! 单条件:$  双条件:@
    请注意:表达式错误程序可能无法运行或者结果错误
    真值表:
    		P Q R 
    		0 0 0 0 
    		0 0 1 1 
    		0 1 0 1 
    		0 1 1 0 
    		1 0 0 0 
    		1 0 1 1 
    		1 1 0 0 
    		1 1 1 0 
    		
    主析取范式:(P∧ㄱQR)(PQ∧ㄱR)(P∧ㄱQR)
    主合取范式:(PQR)(P∨ㄱQ∨ㄱR)(PQR)(P∨ㄱQR)(P∨ㄱQ∨ㄱR)
    

    如有错误欢迎指正

    展开全文
  • 利用真值表法求主合取范式及主析取范式的实现

    万次阅读 多人点赞 2016-09-29 18:23:45
    利用真值表法求主析取范式主析取范式的实现(C++) 功能:用户可输入合式公式(包含!&|以及圆括号),程序即可输出变元真值表及主合取范式及主析取范式 《离散数学》南京邮电大学学习期间,离散数学实验一 2016.9...
  • C++实现求主析取范式、主合取范式

    千次阅读 2016-11-01 22:42:04
    离散数学第一次上机实验,突击学完什么是主析取范式和主合取范式之后粗略地想了下实现的思路。 第一步自然是把输入的式子转换成后缀表达式。结合数据结构书上对基本四则运算的代码和前人的思路勉强写出来一个,但...
  • 使用C++求命题公式的主析取范式与主合取范式

    千次阅读 多人点赞 2018-09-22 17:21:29
    最近的离散数学的一个上机作业,要求任意输入一个命题公式,求它的真值表与主析取范式和主合取范式。其中的命题连接词都是用特殊符号来表示(怕麻烦……),并最终选择使用C++来编写程序。 先贴代码: // 五种...
  • 根据命题公式真值表求主析取范式。 输入格式: 第一行为命题中符号的个数(最大不超过8); 第二行开始到最后为命题公式的真值表最后一列。 输出格式: 输出主析取范式。 注意: 1.逻辑连接词非为!,与为^,或为+; 2....
  • 编程析取范式求主析取范式。。

    千次阅读 2014-11-03 10:43:47
     ...离散数学中析取范式如何通过计算机求主析取范式。其中一种办法就是用二维数组存储析取范式的真值表,然后代入命题公式,真值为T,就是它的最小项。其中会用到栈这种数据结构判断优先级。。
  • 主析取范式与主合取范式,并求公式的成真赋值和成假赋值。 a1 = [0,0,0,0,1,1,1,1]; a2 = [0,0,1,1,0,0,1,1]; a3 = [0,1,0,1,0,1,0,1]; a4 = [1,1,0,0,1,1,0,0]; fprintf('在本题中用!代表非,&代表合取,-&...
  • 求公式的主合取范式和主析取范式

    热门讨论 2009-12-13 08:44:49
    求公式的主合取范式和主析取范式 c++写的类
  • } //主析取范式中的一个值 void xiqu(Val* val,int num) { int j = 0; printf("("); for (int i = 0; i ; i++) { if (val->vaule[i]== 1+'0') { //e[j++] = val->ch[i]; if(i!=num-1) printf("%c&", val->ch[i]); ...
  • 求公式(p∨q)→r的主析取范式。 [输入] 本题无输入。 [输出] 在单独的一行中输出公式的主析取范式,所有极小项按照对应的解释的字典顺序输出,即┐p∧┐q∧┐r是字典序的第一个极小项,p∧q∧r是字典序的最后...
  • 公式的主析取范式和主合取范式,输出形式为:“ mi ∨ mj ; Mi ∧ Mj” ,极小项和 ∨ 符号之间有一个空格,极大项和 ∧ 符号之间有一个空格;主析取范式和主合取范式之间用“ ; ”隔开,“ ; ”前后各有一个空格。 ...
  • 离散数学上机实验,给定一个命题公式,求其主析取范式,主合取范式,能力有限,参考了我学长的一篇博客,并进行了许多优化。 本次离散数学实验,我学到了许多东西,也看了自己的不足之处 1).我深刻地体会到在比较...
  • //输出主合取范式 } } if (xq[0] == -1) printf("\n该命题公式不存在主析取范式。\n"); else { printf("\n\n该命题公式的主析取范式:\n\t"); for (i1 = 0; i1 ; i1++) { if (i1 > 0) printf...
  • 标题:真值表求主析取范式、主合取范式的计算机语言实现 背景 语言、环境选择 C++ Visual Studio 2010 知识涉及(关键词) 线性栈的使用 中缀表达式,后缀表达式 映射 二进制枚举 实验思路 将中缀表达式转化...
  • 本程序可以实现任意输入表达式,变元数最多可为3个,即可输出主析取式和主合取式。 规定符号: ! 否定 | 析取 & 合取 -> 条件 双条件 #include #include usingnamespace std;... //主析取范式
  • -------YYC #include #include #include #include using namespace std; /* *说明: ...* 用| 表示 析取 * 用- 表示 条件 * 用~ 表示 双条件 */ list> inlist_value_map ;//用于记录所有
  • 求真值表及主范式求真值表及主范式求真值表及主范式
  • 这是我门上机作业,有个同学做的很好,拿来和大家分享,希望对大家有益^
  • 求一个命题公式的主析取(合取)范式 这是大二学离散数学的时候写的, 在这里留个档吧, 算是回忆... 代码各种乱, 不改了. 1 /* header.h 2 *author : jackiesteed 3 *内容: 给定一个命题公式, 可以...
  • 主析取范式主合取范式求解不太理解的可以看看下面这个例子 求下列公式的主析取范式,再用主析取范式求主合取范式. (1) (p∧q)∨r (2) (p→q)∧(q→r) (1) 这里是解答 ⇔(p∧q∧(¬r∨r))∨((¬p∨p)∧(¬q∨q)∧...
  • 对于任意命题公式,都存在与其等价的析取范式和合取范式 另一种表述: 每一真值函数,都可用范式(析取范式或合取范式)表示; 每一个复合命题形式,都至少存在一个与其等值的范式(析取范式或合取范式) 英文表述 ...
  • // 部 分 if(key(a,b)==1) { if(c[2]=='#') {x[z++]='|';x[z++]='(';x[z++]=c[0];x[z++]='&';x[z++]='!';x[z++]=c[1];x[z++]=')';} if(c[2]!='#') {x[z++]='|';x[z++]='(';x...
  • 离散上级作业 C语言

    2018-03-17 10:21:16
    用C写的离散上级作业,/笛卡尔积序偶简单矩阵输出输出/给定一个命题公式, 可以求出该公式的吸取范式和主合取范式
  • 离散数学第二节

    2021-05-13 16:04:36
    主析取范式与主合取范式的意义: 任何逻辑表达式都可以化为析取范式,这意味着任何逻辑表达式都可以化为主析取范式(通过缺什么补什么的方法)。 假设某一电路中现在有100个输入信号,1个输出信号,各个电路之间的...
  • 《数据库系统概论》复习

    千次阅读 多人点赞 2019-05-27 12:13:27
    相对应(R与S可以是同一关系),则对于R中每个元组在F上的值必须空值或S中某个元组的码值。 外码:设F是基本关系R的属性/属性集,但不是关系R的码,K s 是基本关系S的码,如果F与K s 相对应,则称F是R的外码...
  • 从键盘输入两个命题变元P和Q的真值,求它们的合取、析取、蕴涵和等价四种运算的真值。要求对输入内容进行分析,如果不符合0、1条件需要重新输入,程序有良好的输入输出界面。 此题代码: while 1 n = input('请...

空空如也

空空如也

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

c语言主析取范式

c语言 订阅