利用真值表法求主析取范式及主合取范式的实现

主析取范式
求解主析取范式、主合取范式方法
1、真值表法
①在表中列出变元值的全部可能
②查表判断命题
命题结果真，变元值对应主析取范式
命题结果假，变元值对应主合取范式
2、等值演算法
①命题化简
蕴涵等值式：A→B↔¬A∨B（作用：去→）
矛盾律：A↔∧¬A（作用：补齐变元）
分配律：(A∧B)∨C↔(A∨C)∧(B∨C)、(A∨B)∧C↔(A∧C)∨(B∧C)
②判断命题
命题结果真，变元值对应主析取范式
命题结果假，变元值对应主合取范式。

例题
求公式(p→q)∧(q→r)的主析取范式和主合取范式、成真赋值。

解：
1、真值表法
查表可得
成真赋值：000、001、011、111
主析取范式：∑(0,1,3,7)
成假赋值：010、100、101、110
主合取范式：∏(2,4,5,6)
2、等值演算法
(p→q)∧(q→r)
=(¬p∨q)∧(¬q∨r)-----------------------------（蕴涵等值式：
化简→）
=((¬p∨q)∨(¬r∧r)))∧((¬q∨r)∨(¬p∧p))----（矛盾律：补齐变元）
=(¬p∨q∨¬r)∧(¬p∨q∨r)∧(¬p∨¬q∨r)∧(p∨¬q∨r)—（分配律：化简）
↔M5M4M6M2。

#include "stdio.h"#include "stdlib.h"#include "string.h"#include "math.h"#define N 50void pd(int b[N],int f);int H1 (char T1[N], char T2[N], int T3[N], int y);int H2 (char T1[N], char T2[N], int T3[N], int y);int main(){int i1,i2,d=1,T3[N],kh=0,jg,j=0,y;int w=0,hequ[N],h=0,x=0,xiqu[N];char T1[N],T2[N],T10[N],s;hequ[0]=-1;xiqu[0]=-1;printf("#########################################\n"); printf("## 用!表示否定 ##\n");printf("## 用&表示合取 ##\n");printf("## 用|表示析取 ##\n");printf("## 用^表示条件 ##\n");printf("## 用~表示双条件 ##\n");printf("#########################################\n\n"); printf("请输入一个合法的命题公式:\n");gets(T1);strcpy(T10,T1);for(i1=0;i1<strlen(T1);i1++){if(T1[i1]==')' || T1[i1]=='(')kh++;if(T1[i1]>='a' && T1[i1]<='z' || T1[i1]>='A' && T1[i1]<='Z') {for(i2=0;i2<j;i2++)if(T2[i2]==T1[i1])d=0;if(d==1){T2[j]=T1[i1];j++;}d=1;}}1printf("\n输出真值表如下:\n \n");for(i1=0;i1<y;i1++)printf(" %c ",T2[i1]);printf(" ");puts(T1);printf("\n");for(i1=0;i1<j;i1++)T3[i1]=0;for(i2=0;i2<j;i2++)printf(" %d ",T3[i2]);jg=H1(T1,T2,T3,y);if(jg==0)hequ[h++]=w;elsexiqu[x++]=w;printf(" %d\n",jg);strcpy(T1,T10);for(i1=0;i1<(int)pow(2,j)-1;i1++) {++w;pd(T3,j-1);jg=H1(T1,T2,T3,y);if(jg==0)hequ[h++]=w;elsexiqu[x++]=w;strcpy(T1,T10);for(i2=0;i2<j;i2++)printf(" %d ",T3[i2]);printf(" %d\n",jg);}if(hequ[0]==-1)printf("\n该命题公式不存在主合取范式。

简答题1．用真值表法判断下列公式的类型.（1）⌝（P∧Q）↔（⌝P∧⌝Q）（2）（P∧⌝Q）→R（3）（P→（P∨Q））∨R（4）⌝（P→Q）∧Q解：（1）⌝（P∧Q）↔（⌝P∧⌝Q）的真值表为：（2）（P∧⌝Q）→R的真值表为：（3）（P→（P∨Q））∨R的真值表为：（4）⌝（P →Q ）∧Q 的真值表为：2．用真值表的方法求（P ∨Q ）→（Q ↔R ）的主析取范式和主合取范式。

解：（P ∨Q ）→（Q ↔R ）的真值表（P ∨Q ）→（Q ↔R ）⇔ 0147m m m m ∨∨∨ 主合取范式为：（P ∨Q ）→（Q ↔R ）⇔2356M M M M ∧∧∧3．用等值演算法求（（P ∨Q ）→R ）→P 的主析取范式和主合取范式。

解：（（P ∨Q ）→R ）→P ⇔⌝（⌝（P ∨Q ）∨R ）∨P ⇔（（P ∨Q ）∧⌝R ）∨P⇔（P ∧⌝R ）∨（Q ∧⌝R ）∨P （析取范式） ⇔P ∨（Q ∧⌝R ）（析取范式）⇔（P ∧（Q ∨⌝Q ）∧（R ∨⌝R ））∨（（Q ∧⌝R ）∧（ P ∨⌝P ）） ⇔（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 ）∨（P ∧⌝Q ∧⌝R ）∨（⌝P ∧Q ∧⌝R ） ⇔24567m m m m m ∨∨∨∨ （主析取范式） 由主合取范式与主析取范式的关系得：（（P ∨Q ）→R ）→P ⇔013M M M ∧∧ （主合取范式） 4．求下列公式的主析取和合取范式。

（1）(┐P → Q)∧(P → R) （2）(P → Q)∨(P∧R) （3） P ∧Q ∨R解：（1）(┐P → Q)∧(P → R)⇔(P∨Q)∧(┐P∨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) (主合取范式) ⇔0146M M M M ∧∧∧由主合取范式与主析取范式的关系得：(┐P → Q)∧(P → R)⇔2567m m m m ∨∨∨(主析取范式) （2）(P → Q)∨(P∧R)⇔（┐P∨Q）∨(P∧R ) ⇔(P∨┐P∨Q )∧(┐P∨Q ∨R) (合取范式)⇔(1∨Q )∧(┐P∨R∨Q )⇔┐P ∨Q∨R (主合取范式) ⇔4M由主合取范式与主析取范式的关系得： (P →Q)∨(P∧R)⇔0123567m m m m m m m ∨∨∨∨∨∨ （3） P ∧Q ∨R ⇔(P ∨R)∧(Q∨R)⇔(P ∨(Q ∧┐Q)∨R)∧((P∧┐P)∨Q∨R )⇔(P ∨Q ∨R)∧(P∨┐Q ∨R)∧(P∨Q ∨R)∧(┐P ∨Q ∨R) ⇔(P ∨Q ∨R)∧(P∨┐Q ∨R)∧(┐P ∨Q ∨R) ⇔024M M M ∧∧ (合取范式) 由主合取范式与主析取范式的关系得：P ∧Q ∨R ⇔13567m m m m m ∨∨∨∨ (主析取范式)5.给定解释I如下：(1)D={2,3}；I(2)D中的特定元素a=2；I(3)D上的函数f(x)为f(2)=3,f(3)=2;I(4)D上的谓词F(x)为F(2)=0,F(3)=1;.IG(x,y)为G(2,2)= G(2,3)= G(3,2)=1, G(3,3)=0;L(x,y)为L(2,2)=L(3,3)=1,L(2,3)= L(3,2)= 0;在这个解释下，求下列各式的值：(1)∀x(F(x)∧G(x,a));(2) ∃x(F(f(x))∧G(x,f(x))) ；(3) ∀x∃yL(x,y);(4)∃y∀xL(x,y);(5)∀x∀y( L(x,y) →L(f(x),f(y)))解：(1) ∀x(F(x)∧G(x,a))⇔(F(2)∧G(2,2))∧(F(3)∧G(3,2))⇔(0∧1)∧(1∧1)⇔ 0(2)∃x(F(f(x))∧G(x,f(x)))⇔(F(f(2))∧G(2,f(2))) ∨ (F(f(3))∧G(3,f(3)))⇔ (F(3)∧G(2,3)) ∨ (F(3)∧G(3,3))⇔(1∧1) ∨(0∧1)⇔1(3)∀x∃yL(x,y)⇔∃yL(2,y)∧∃yL(3,y)⇔(L(2,2)∨L(2,3))∧(L(3,2)∨L(3,3))⇔1∧1⇔1(4)∃y∀xL(x,y)⇔∃y(L(2,y)∧L(3,y))⇔(L(2,2)∧L(3,2))∨ (L(2,3)∧L(3,3))⇔0 ∨ 0⇔0(5)∀x∀y( L(x,y) →L(f(x),f(y)))⇔∀y(L(2,y)→L(f(2),f(y)))∧∀y(L(3,y)→L(f(3),f(y)))⇔(L(2,2)→L(f(2),f(2)))∧(L(2,3)→L(f(2),f(3)))∧(L(3,2)→L(f(3),f(2)))∧(L(3,3)→L(f(3),f(3)))⇔(1→L(3,3))∧(0→L(3,2))∧(0→L(2,3))∧(1→L(2,2))⇔(1→1)∧(0→0)∧(0→0)(1→1)⇔06.给定解释I如下：D为实数集合R；(a)个体域I(b)D中的特定元素a=0；ID上的特定函数f(x,y)=x-y;(c)ID上的特定谓词F(x,y):x=y,G(x,y):x<y(d)I说明下列公式在I下的含义，并指出其真值。

求主析取范式的方法求主析取范式是一种用于逻辑推理和逻辑问题求解的方法。

在计算机科学和数学领域，求主析取范式被广泛应用于逻辑电路设计、自动推理、人工智能等领域。

本文将介绍求主析取范式的基本概念、求解方法以及应用。

一、求主析取范式的基本概念求主析取范式是一种用于描述逻辑表达式的标准化形式。

它由主合取范式和主析取范式组成，其中主合取范式是逻辑表达式的合取范式中最简单的形式，主析取范式是逻辑表达式的析取范式中最简单的形式。

主合取范式是由若干个子句通过逻辑与运算符连接而成的合取范式，其中每个子句由若干个文字通过逻辑或运算符连接而成。

主合取范式的形式如下：C1 ∧ C2 ∧ ... ∧ Cn其中Ci表示第i个子句，每个子句由若干个文字通过逻辑或运算符连接而成。

主析取范式是由若干个子句通过逻辑或运算符连接而成的析取范式，其中每个子句由若干个文字通过逻辑与运算符连接而成。

主析取范式的形式如下：C1 ∨ C2 ∨ ... ∨ Cn其中Ci表示第i个子句，每个子句由若干个文字通过逻辑与运算符连接而成。

二、求主析取范式的求解方法求主析取范式的方法主要有两种：真值表法和奎宁-麦克劳斯基算法。

真值表法是一种基于逻辑运算的方法。

它通过构造逻辑表达式的真值表，逐行比较真值表中的值，将真值为真的行转换为主合取范式或主析取范式。

真值表法的优点是简单直观，但当逻辑表达式的字母变量较多时，真值表的大小会呈指数级增长，计算量较大。

奎宁-麦克劳斯基算法是一种基于逻辑运算和逻辑等价转换的方法。

它通过逻辑等价转换将逻辑表达式逐步转化为主合取范式或主析取范式。

奎宁-麦克劳斯基算法的优点是计算量相对较小，但需要一定的逻辑推理能力。

三、求主析取范式的应用求主析取范式在逻辑电路设计中具有重要的应用。

逻辑电路可以通过主析取范式表示为若干个子电路的并联，每个子电路由若干个逻辑门组成。

通过将逻辑门的输出连接到主析取范式的输入端，可以实现逻辑电路的功能。

求主析取范式在自动推理中也有广泛的应用。

求给定命题公式的真值表并根据真值表求公式的主范式(求给定命题公式的真值表并根据真值表求公式的主范式)专业网络工程班级 1202班学号 12407442姓名张敏慧2013.12.14目录一.实验目的 .......................................................3二.实验内容 (3)求任意一个命题公式的真值表 ..................................................................... ..... 3 三.实验环境 (3)四. 实验原理和实现过程(算法描述) (3)1.实验原理 ..................................................................... ...................................... 3 2.实验流程图 ..................................................................... .................................. 5 五.实验代码 (6)六. 实验结果 (14)七. 实验总结 (19)- 1 -一.实验目的本实验课程是网络工程专业学生的一门专业基础课程，通过实验，帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算;通过实验提高学生编写实验报告、总结实验结果的能力;使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。

熟悉掌握命题逻辑中的真值表、主范式等，进一步能用它们来解决实际问题。

二.实验内容求任意一个命题公式的真值表，并根据真值表求主范式详细说明:求任意一个命题公式的真值表本实验要求大家利用C/C，，语言，实现任意输入公式的真值表计算。

一般我们将公式中的命题变元放在真值表的左边，将公式的结果放在真值表的右边。

习题一1。

下列句子中,哪些是命题？在是命题的句子中，哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？（1）中国有四大发明。

答：此命题是简单命题,其真值为1。

（2答：此命题是简单命题，其真值为1。

（3）3是素数或4是素数.答：是命题，但不是简单命题，其真值为1.x+<（4）235答：不是命题.（5）你去图书馆吗？答:不是命题。

（6）2与3是偶数.答：是命题,但不是简单命题，其真值为0.（7）刘红与魏新是同学.答:此命题是简单命题，其真值还不知道。

(8)这朵玫瑰花多美丽呀！答：不是命题。

（9）吸烟请到吸烟室去!答:不是命题。

（10）圆的面积等于半径的平方乘以π.答：此命题是简单命题，其真值为1。

（11)只有6是偶数，3才能是2的倍数.答：是命题，但不是简单命题,其真值为0。

（12)8是偶数的充分必要条件是8能被3整除.答:是命题，但不是简单命题,其真值为0。

（13）2008年元旦下大雪.答:此命题是简单命题，其真值还不知道。

2。

将上题中是简单命题的命题符号化。

解：(1）p:中国有四大发明.(2）p：是无理数.(7）p:刘红与魏新是同学。

（10）p：圆的面积等于半径的平方乘以π.（13）p:2008年元旦下大雪。

3。

写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值.（15.答：否定式5. p5q5.其否定式q的真值为1。

25不是无理数.答:25p25不是无理数。

q25是有理数. 其否定式q的真值为1.(3）2.5是自然数。

答:否定式：2.5不是自然数。

p：2。

5是自然数。

q:2.5不是自然数. 其否定式q的真值为1.（4）ln1是整数。

答：否定式：ln1不是整数. p：ln1是整数。

q:ln1不是整数. 其否定式q的真值为1。

4。

将下列命题符号化，并指出真值.（1）2与5都是素数答：p：2是素数，q：5是素数，符号化为p q∧,其真值为1。

（2)不但π是无理数，而且自然对数的底e也是无理数.答:p：π是无理数，q：自然对数的底e是无理数，符号化为p q∧，其真值为1。

利用真值表求主合取范式在逻辑学中，主合取范式是一个命题逻辑式的合式范式，它由多个合取式组成，每个合取式中包含了命题变量或它们的否定形式。

利用真值表求一个命题逻辑式的主合取范式可以通过以下步骤完成：1. 构造命题变量在真值表中的全部可能取值组合。

2. 对于每一组取值，计算命题逻辑式的真值。

3. 将所有真值为真的组合找出来，把它们表示成合取式的形式。

4. 把所有的合取式用“或”连接起来，就得到了主合取范式。

例如，假设要求命题逻辑式P∨(Q∧R)的主合取范式，可以按照以下步骤进行：1. 构造真值表，列出P、Q、R的所有可能取值组合：| P | Q | R | P∨(Q∧R) ||---|---|---|---------|| T | T | T | T || T | T | F | T || T | F | T | T || T | F | F | T || F | T | T | T || F | T | F | F || F | F | T | F || F | F | F | F |2. 对于每一组取值，计算命题逻辑式的真值：| P | Q | R | P∨(Q∧R) ||---|---|---|---------|| T | T | T | T || T | T | F | T || T | F | T | T || T | F | F | T || F | T | T | T || F | T | F | F || F | F | T | F || F | F | F | F |3. 找出所有真值为真的组合：P∨(Q∧R) =(T∧T∧T)∨(T∧F∧F)∨(T∧F∧T)∨(T∧F∧F)∨(F∧T∧T) =T∨F∨T∨F∨F4. 把所有的合取式用“或”连接起来，就得到了主合取范式：P∨(Q∧R)的主合取范式为(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)。

等值演算是一种逻辑代数的方法，可用于简化布尔代数的表达式。

在逻辑电路设计和计算机科学领域，利用等值演算可以帮助我们求解复杂的布尔函数的主析取范式和主合取范式。

在布尔代数中，一个布尔函数可以表示为一系列输入变量和输出变量的逻辑关系式。

通过布尔代数的运算规则，我们可以对这些逻辑关系式进行等值变换，将其简化为更加简洁的形式。

其中，最重要的简化形式包括主析取范式和主合取范式。

主析取范式是指一个布尔函数的各项按照与或关系相连的形式，其中每一项都是不可简化的极小项。

主析取范式的求解可以帮助我们理解布尔函数的逻辑结构，并为电路的设计提供参考。

主合取范式则是指一个布尔函数的各项按照或与关系相连的形式，其中每一项都是不可简化的极大项。

主合取范式的求解同样可以帮助我们理解布尔函数的逻辑结构，并为电路的设计提供参考。

接下来，我们将通过等值演算的方法，来求解一个布尔函数的主析取范式和主合取范式。

1. 我们需要将布尔函数转换为真值表的形式。

真值表可以清晰地展现出布尔函数在各个输入变量组合下的输出取值情况。

通过真值表的分析，我们可以对布尔函数进行等值变换和化简。

2. 我们利用等值演算的定理和法则，对布尔函数进行等值变换。

其中，包括重要的等值演算定理，如恒等律、吸收律、对偶律等。

通过运用这些定理和法则，我们可以将布尔函数逐步化简为主析取范式和主合取范式的形式。

3. 我们将化简后的布尔函数表示为主析取范式和主合取范式的形式。

主析取范式和主合取范式的求解过程中，需要格外注意每一步等值变换的正确性和合理性，以确保最终得到的主析取范式和主合取范式是布尔函数的最简形式。

通过以上等值演算的步骤和方法，我们可以成功地求解出一个复杂布尔函数的主析取范式和主合取范式。

这些简化后的形式将极大地方便我们对布尔函数的理解和分析，为逻辑电路的设计和优化提供重要的参考依据。

等值演算作为一种重要的逻辑代数方法，在计算机科学和信息技术领域也有着广泛的应用和意义。

用真值表求主合取范式在逻辑学和计算机科学中，主合取范式(MDNF)和主析取范式(MKNF)是重要概念。

其中MDNF是布尔函数的一种标准形式。

本文将讨论如何用真值表来求主合取范式。

先回忆一下布尔函数：布尔函数指的是仅由0和1两个值组成的函数，比如AND、OR和NOT函数。

布尔函数通常用真值表来表示。

真值表列出了所有可能的输入以及对应的输出。

举个例子，假设我们想要求解一个布尔函数f(x, y)，其中x和y为输入变量，f(x,y)的输出值为1当且仅当x和y均为1。

我们可以通过真值表来表示这个布尔函数：|x|y|f(x,y)| |-|-|------| |0|0| 0 | |0|1| 0 | |1|0| 0 | |1|1| 1 |这个真值表说明了当x和y都为1时，f(x,y)取值为1；而在其他情况下，f(x,y)都取值为0。

要求布尔函数的主合取范式，我们需要先将真值表中所有输出为1的行合并起来，然后将它们组合在一起。

这样就组成了主合取范式。

再看上面的例子，我们可以发现当f(x,y)=1时有一行符合要求，即x=1且y=1。

这样我们就可以得到主合取范式为(x AND y)。

另一个例子是考虑一个三元函数的真值表：|x|y|z|f(x,y,z)| |-|-|-|--------| |0|0|0| 1| |0|0|1| 0| |0|1|0| 1| |0|1|1| 1| |1|0|0| 0| |1|0|1| 1| |1|1|0| 0| |1|1|1| 0|从这张真值表中我们可以看出f(x,y,z)的主合取范式为(x AND NOT y AND z) OR (NOT x AND y AND z) OR (x AND y AND NOT z)。

对于比较复杂的布尔函数，用真值表来求主合取范式可能不是最有效的方法。

但对于简单的函数，采用这种方法很方便。

此外，这种方法也提供了一种验证主合取范式是否正确的方法。

同时，需要注意的是MDNF不一定是唯一的。

第四节 主析取范式与主合取范式n 个命题变项虽然可以构成无穷多个形式各异的命题公式，但就其真值而言，只有22n种。

对应每种真值情况虽然又有无穷多个等值的公式，但这些公式却有相同的标准形式。

本节将给出规范公式的概念，这种规范的公式能表达真值表所能给出的一切信息。

定义4.1 命题变项及其否定统称为文字。

如p ，q ，¬p ，¬q ，L 都是文字，即每个命题变项产生两个文字。

（1）仅由有限个文字构成的合取式称为简单合取式。

（2）仅由有限个文字构成的析取式称为简单析取式。

例如，p ∧q ，p ∧¬q ∧r ，L 都是简单合取式。

p ∨q ， ¬p ∨q ∨r ，L 都是简单析取式。

单个文字既是简单析取式，又是简单合取式。

定义4.2 （1）仅由有限个简单合取式构成的析取式称为析取范式； （2）仅由有限个简单析取式构成的合取式称为合取式。

例如，p ，¬q ，p ∧q ，（p ∧¬q ）∨（p ∧q ），L 都是析取范式。

p ，¬r ，p ∨q ，（p ∨q ）∧（q ∨¬r ），L 都是合取范式。

注意，两个文字构成的简单合取式与析取式都既是析取范式又是合取范式。

例如，p ∨q 是析取范式，它是由两个简单的合取式p 与q 析取而成。

同时它也是合取范式，看成是一个简单析取式构成的合取范式。

定义 4.3 （1）n 个命题变项1p ，2p ，L ，n p （1n ≥）构成的简单合取式中，若每个i p （1,2,,i n =L ）都以文字的形式出现一次且仅出现一次，而且出现在左起的第i 位上，则称它为极小项。

（2）n 个命题变项1p ，2p ，L ，n p （1n ≥）构成的简单析取式中，若每个ip （1,2,,i n =L ）以文字的形式出现一次且仅出现一次，而且出现在左起的第i 位上，则称它为极大项。

两个命题变项p ，q 共可形成4个极小项：¬p ∧¬q ，¬p ∧q ，p ∧¬q ，p ∧q 。

离散数学求命题公式的主析取范式和主合取范式Description输⼊命题公式的合式公式，求出公式的真值表，并输出该公式的主合取范式和主析取范式。

Input命题公式的合式公式Output公式的主析取范式和主合取范式，输出形式为：“ mi ∨ mj ; Mi ∧ Mj” ，极⼩项和∨符号之间有⼀个空格，极⼤项和∧符号之间有⼀个空格；主析取范式和主合取范式之间⽤“ ; ”隔开，“ ; ”前后各有⼀个空格。

永真式的主合取范式为 1 ，永假式的主析取范式为 0 。

输⼊公式的符号说明：! ⾮，相当于书⾯符号中的 “ ¬ ”& 与，相当于书⾯符号中的 “ ∧ ”| 或，相当于书⾯符号中的 “ ∨ ”蕴含联结词，相当于书⾯符号中的 “ → ”等价联结词，相当于书⾯符号中的 “ ↔ ”( 前括号) 后括号Code#include <cstdio>#include <cstring>#include <cmath>#define N 1000#define MAX 10000000char s[N];bool table[30];int explain[30];int value[MAX];int sum = 0;int priority(char c){switch (c){case '#': return -1;case '!': return 5;case '&': return 4;case '|': return 3;case '-': return 2;case '+': return 1;case '(': return 0;default: return 0;}}void postfix(){char post[N] = { '\0' };int pp = -1;char stack[N] = { '#' };int ps = 0;int len = strlen(s);for (int i = 0; i < len; i++){if (s[i] >= 'a' && s[i] <= 'z'){post[++pp] = s[i];continue;}if (s[i] == '!' || s[i] == '&' || s[i] == '|' || s[i] == '-' || s[i] == '+'){while (priority(s[i]) <= priority(stack[ps]))post[++pp] = stack[ps--];stack[++ps] = s[i];continue;}if (s[i] == '('){stack[++ps] = s[i];continue;}if (s[i] == ')'){while (stack[ps] != '(') post[++pp] = stack[ps--];ps--;continue;}}while (ps) post[++pp] = stack[ps--];strcpy(s, post);int l = strlen(s);}void settable(){memset(table, 0, sizeof(table));int len = strlen(s);for (int i = 0; i < len; i++){if (s[i] >= 'a' && s[i] < 'z')table[s[i] - 'a'] = true;}for (int i = 0; i < 26; i++)if (table[i]) sum++;sum = pow(2, sum);}int btoi(){int sum = 0, weight = 1;for (int i = 25; i >= 0; i--)if (table[i]){if (explain[i]) sum += weight;weight *= 2;}return sum;}int calc(int a, int b, char c){switch (c){case '&': return a * b;case '|': if (a + b) return 1; else return 0;case '-': if (a == 1 && b == 0) return 0; else return 1; case '+': return !((a + b) & 1);}}int work(){int stack[N], ps = -1;int len = strlen(s);for (int i = 0; i < len; i++){if (s[i] >= 'a' && s[i] <= 'z'){stack[++ps] = explain[s[i] - 'a'];continue;}if (s[i] == '!'){stack[ps] = (stack[ps] + 1) & 1;continue;}int ans = calc(stack[ps - 1], stack[ps], s[i]);stack[--ps] = ans;}return stack[0];}void assign(){int x = btoi();int ans = work();value[x] = ans;}void generate(char c){while (c <= 'z' && table[c - 'a'] == false) c++;if (c > 'z'){assign();return;}explain[c - 'a'] = 0;generate(c + 1);explain[c - 'a'] = 1;generate(c + 1);}void output1(){int i = 0;while (i < sum && !value[i]) i++;if (i >= sum){printf("0 ; ");return;}printf("m%d", i);for (i++; i < sum; i++)if (value[i]) printf(" ∨ m%d", i);printf(" ; ");}void output2(){int i = 0;while (i < sum && value[i]) i++;if (i >= sum){printf("1\n");return;}printf("M%d", i);for (i++; i < sum; i++)if (!value[i]) printf(" ∧ M%d", i);printf("\n");}int main(){scanf("%s", s);postfix();settable();memset(value, 0, sizeof(value));memset(explain, 0, sizeof(explain)); generate('a');output1();output2();return 0;}。

离散数学习题答案（耿素云屈婉玲）离散数学习题答案习题⼆及答案：（P38）5、求下列公式的主析取范式，并求成真赋值：（2）()()p q q r ?→∧∧解：原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧()()p q r p q r ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式，所以成真赋值为011，111。

6、求下列公式的主合取范式，并求成假赋值：（2）()()p q p r ∧∨?∨解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式，所以成假赋值为100。

7、求下列公式的主析取范式，再⽤主析取范式求主合取范式：（1）()p q r ∧∨解：原式()(()())p q r r p p q 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 p q r p q r p q r∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧13567m m m m m ?∨∨∨∨，此即主析取范式。

主析取范式中没出现的极⼩项为0m ，2m ，4m ，所以主合取范式中含有三个极⼤项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。

9、⽤真值表法求下⾯公式的主析取范式：（1）()()p q p r ∨∨?∧解：公式的真值表如下：由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极⼩项的析取即为主析取范式，故主析取范式1234567m m m m m m m ?∨∨∨∨∨∨习题三及答案：（P52-54）11、填充下⾯推理证明中没有写出的推理规则。

前提：,,,p q q r r s p ?∨?∨→结论：s 证明：① p 前提引⼊② p q ?∨前提引⼊③ q ①②析取三段论④ q r ?∨前提引⼊⑤ r ③④析取三段论⑥ r s →前提引⼊⑦ s ⑤⑥假⾔推理15、在⾃然推理系统P 中⽤附加前提法证明下⾯推理：（2）前提：()(),()p q r s s t u ∨→∧∨→结论：p u →证明：⽤附加前提证明法。

离散数学主析取范式主合取范式主析取范式和主合取范式是离散数学中逻辑表达式的两种常见形式。

它们在逻辑推理、计算机科学和人工智能等领域具有重要的应用价值。

本文将介绍主析取范式和主合取范式的概念、特性以及如何通过布尔运算将任意逻辑表达式转化为主析取范式或主合取范式。

一、主析取范式（DNF）主析取范式是一个逻辑表达式的标准形式，它由多个子句的析取组成。

每个子句由多个文字的合取构成。

主析取范式的最简形式是由至少一个子句组成的合取。

例如，逻辑表达式(A ∧ B) ∨ (C ∧ D ∧ E)就是一个主析取范式。

其中，(A ∧ B) 和 (C ∧ D ∧ E) 是两个子句，分别由 A、B 和 C、D、E 构成。

主析取范式的特性：1. 每个子句中的文字可以是变量或其否定形式。

2. 主析取范式中的每个文字都是变量的析取或否定析取。

3. 主析取范式可以使用布尔运算来简化和优化。

如何得到主析取范式？可以通过真值表法或布尔代数的演算法来将任意逻辑表达式转化为主析取范式。

方法如下：2. 找到真值表中使得逻辑表达式为真的行。

3. 对每一行，在真值为真的列上取出对应的文字，并将它们合取起来构成一个子句。

4. 将所有子句析取起来得到主析取范式。

二、主合取范式（CNF）主合取范式是一个逻辑表达式的标准形式，它由多个子句的合取组成。

每个子句由多个文字的析取构成。

主合取范式的最简形式是由至少一个子句组成的析取。

例如，逻辑表达式(A ∨ B) ∧ (C ∨ D ∨ E)就是一个主合取范式。

其中，(A ∨ B) 和 (C ∨ D ∨ E) 是两个子句，分别由 A、B 和 C、D、E 构成。

主合取范式的特性：1. 每个子句中的文字可以是变量或其否定形式。

2. 主合取范式中的每个文字都是变量的合取或否定合取。

3. 主合取范式可以使用布尔运算来简化和优化。

如何得到主合取范式？可以通过真值表法或布尔代数的演算法来将任意逻辑表达式转化为主合取范式。