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

利用真值表求主合取范式
1、把变量的各种可能取值与想对应的函数值，用表格的形式一一列举出来，这种表格就叫做真值表。

2、设一个变量均有0、1两种可能取值，n个变量共有2n种可能，将它们按顺序（一般按二进制数递增规律）排列起来，同时在相应位置上写上逻辑函数的值，便可得到该逻辑函数的真值表。

3、例如：逻辑函数的Y=AB+BC+CA的真值表如下：真值表以表格的形式表示逻辑函数，其优点是直观明了。

4、输入变量取值一旦确定，即可以从表中查出相应的函数值。

5、所以，在许多数字集成电路手册中，常常以不同形式的真值表，给出器件的逻辑功能。

6、另外，在把一个实际逻辑问题，抽象成为数学表达形式时，使用真值表是最方便的。

7、所以，在数字电路逻辑设计过程中，第一步就是要列出真值表；在分析数字电路逻辑功能时，最后也要列出真值表。

8、但是，真值表也有一些缺点：首先，难以对其使用逻辑代数的公式和定理进行运算和变换；其次，当变量比较多时，列真值表会十分繁琐。

#include <iostream>#include <cmath>#include <cassert>#include <cctype>using namespace std;char str[100]; //输入的命题公式int tv[20] = {0}; //真值指派的数组int length; //命题公式长度char expression[100]; //将命题公式中的命题变元变为真值后的数组int icp(const char c) //联结词的栈外优先级{int result = -1;switch(c){case '#': result = 0; break;case '(': result = 10; break;case '!': result = 9; break;case '&': result = 6; break;case '|': result = 4; break;case '>': result = 2; break;case ')': result = 1;}return result;}int isp(const char c) //联结词的栈内优先级{int result = -1;switch(c){case '#': result = 0; break;case '(': result = 1; break;case '!': result = 8; break;case '&': result = 7; break;case '|': result = 5; break;case '>': result = 3; break;case ')': result = 10;}return result;}void Plus(int a[],int q) //二进制加法指派真值{a[q]=a[q]+1;for (int i = q; a[i] == 2; i--){a[i]=0;a[i-1]=a[i-1]+1;}}template<class T>class Stack{public:virtual bool IsEmpty() const = 0;virtual bool IsFull() const = 0;virtual bool Top(T& x) const = 0;virtual bool Push(T x) = 0;virtual bool Pop() = 0;virtual void Clear() = 0;};template<class T>class SeqStack: public Stack<T> //顺序栈类{public:SeqStack(int mSize = 30);~SeqStack() { delete []s; }bool IsEmpty() const { return top == -1; }bool IsFull() const { return top == maxTop; } bool Top(T& x) const;bool Push(T x);bool Pop();void Clear() { top = -1; }private:int top;int maxTop;T* s;};template<class T>SeqStack<T>::SeqStack(int mSize){maxTop = mSize - 1;s = new T[mSize];top = -1;}template<class T>bool SeqStack<T>::Top(T& x) const{if (IsEmpty()){cout << "Empty" << endl;return false;}x = s[top];return true;}template<class T>bool SeqStack<T>::Push(T x){if (IsFull()){cout << "Overflow" << endl;return false;}s[++top]=x;return true;}template<class T>bool SeqStack<T>::Pop(){if(IsEmpty()){cout << "Underflow" << endl;}top--;return true;}class Calculator{public:Calculator(int maxSize):s(maxSize){}void Change();int Run();void Solve();void Clear() { s.Clear(); }private:SeqStack<bool> s; //运算栈void PushOperand(bool);bool GetOperands(bool &, bool &);void DoOperator(char);};void Calculator::PushOperand(bool op){s.Push(op);}bool Calculator::GetOperands(bool & op1, bool & op2) //获取栈顶两个元素{if (!s.Top(op1)){cerr << "Missing operand!" << endl;return false;}s.Pop();if (!s.Top(op2)){cerr << "Missing operand!" << endl;return false;}s.Pop();return true;}void Calculator::DoOperator(char oper) //联结词运算{bool left, right;bool result = GetOperands(left, right);if (result)switch(oper){case '!': s.Push(!left && right); break; //not运算case '&': s.Push(left && right); break; //and运算case '|': s.Push(left || right); break; //or运算case '>': s.Push(!right || left); break; //条件运算}elseClear();}void Calculator::Change() //将输入的字符串转化为可计算的表达式{int k = 0, t = 0;int flag = 1; //标记，防止相同的命题变元赋入不同的值int count = 0;for (int i = 0; i < pow(2,count); i++){k=1;for (int m = 0; m < length; m++){if (isalpha(str[m])) //将原来的命题变元修改为真值{if (flag == 1){if(tv[k] == 0)expression[m] = '0';elseexpression[m] = '1';k++;}elseexpression[m] = '0';flag = 1;for (t = m; t >= 0; t--)if ((str[m+1] == str[t]) && isalpha(str[m+1]) && isalpha(str[t]))flag = 0;}else{expression[m] = str[m]; //逻辑联结词不变for (t = m; t >= 0; t--)if ((str[m+1] == str[t]) && isalpha(str[m+1]) && isalpha(str[t]))flag = 0;}}for (int t = 0; t < length; t++)for (int j = t; j < length; j++)if (str[t] == str[j])expression[j] = expression[t]; //相同的命题变元复制赋值}}int Calculator::Run(){SeqStack<char> s1; //联结词栈char ch, y;char p[100];int i = 0;s1.Push('#');for (int temp=0; temp < length ; temp++){ch = expression[temp];if (isdigit(ch)){p[i++] = ch;}else if(ch == ')')for(s1.Top(y), s1.Pop(); y != '('; s1.Top(y), s1.Pop())p[i++] = y;else{if(ch == '!') p[i++] = '1'; //非运算，在!前加1，将!视作双目操作符for(s1.Top(y), s1.Pop(); icp(ch) <= isp(y); s1.Top(y), s1.Pop())p[i++] = y;s1.Push(y);s1.Push(ch);}}while(!s1.IsEmpty()){s1.Top(y);s1.Pop();if(y != '#')p[i++] = y;}p[i++] = '#';/* ------↑中缀表达式转化为后缀表达式-----------↓计算后缀表达式结果------------- */bool newop;for (i = 0; p[i] !='#'; i++){switch(p[i]){case '!':case '&':case '|':case '>': DoOperator(p[i]); break;default:cin.putback(p[i]);cin >> newop;PushOperand(newop);break;}}if (s.Top(newop)){cout << (int)newop << endl;return (int)newop; //输出并返回最终结果}}void Calculator::Solve(){cout << "***************************************" << endl;//标语cout << "** 欢迎进入逻辑运算软件**" << endl;cout << "** (可运算真值表，主范式，支持括号) **" << endl;cout << "** **" << endl;cout << "** 用!表示not 用&表示and **" << endl;cout << "** 用|表示or 用>表示蕴含**" << endl;cout << "** **" << endl;cout << "***************************************" << endl;cout << "请输入合法的命题公式(以#结尾): ";int flag = 1; //标记，防止重复添加命题变元int count = 0; //命题变元的数目cin >> str; //输入命题公式length = strlen(str) - 1;char index[10]; //命题变元数组for (int i = 0; i < length; i++) //逐次添加命题变元{if (isalpha(str[i]) && (flag == 1))index[count++] = str[i];flag=1;for (int k = 0; k < count; k++)if (index[k] == str[i+1])flag=0;}if (!count){cout << "无命题变元,重新输入!" << endl;system("pause");system("cls");Solve();}cout << "真值表:" << endl;for (int w = 0; w < count; w++)cout << index[w] << ' ';for (w = 0; w < length; w++)cout << str[w];cout << endl;int *truth = new int[pow(2,count)];int xx = 0, dx = 0; //小项，大项for (int r = 0; r < pow(2,count); r++) //输出真值表{for (int j = 1; j <= count; j++)cout << tv[j] << ' ';Change();truth[r] = Run();if (truth[r]) //记录小项和大项的个数xx++;elsedx++;Plus(tv,count);}if(xx > 1) //输出主析取范式{int flag_xx = 0;cout << "主析取范式为";for(r = 0; r < pow(2,count); r++){if (truth[r]){if (flag_xx) cout << " \\/ ";cout << "m" << r;flag_xx = 1;}}cout << endl;}elsecout << "没有主析取范式!" << endl;if(dx > 1) //输出主合取范式{int flag_dx = 0;cout << "主合取范式为";for(r = 0; r < pow(2,count); r++){if (!truth[r]){if (flag_dx) cout << " /\\ ";cout << "M" << r;flag_dx = 1;}}cout << endl;}elsecout << "没有主合取范式!" << endl;cout << "是否继续运算?(Y/N)" << endl;char goon;cin >> goon;if (goon=='y' || goon=='Y'){system("cls");Solve(); //递归调用Solve，重新计算}elseexit(0);}int main(){Calculator Cal(100);Cal.Solve();return 0;}。

主析取范式
求解主析取范式、主合取范式方法
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。

主析取范式的求法及其应用杨菲〔天津市河西区职工大学，天津市300203〕摘要：本文综述了求主析取范式的三种主要方法，即推演法、真值表法、构造树法，并从经典例题入手分析了三种方法的应用技巧。

关键词：主析取范式 推演法 真值表法 构造树法命题公式的主析取范式在数理逻辑学中具有非常重要的意义，其求解的主要目的在于使命题公式标准化，从而有利于判断两个命题公式是否等值，并且还可以判断一个公式是重言式〔永真式〕还是矛盾式〔永假式〕。

鉴于主析取范式求解的重要意义，本文综述了求主析取范式的方法及各种方法的应用技巧。

1 相关概念 1.1 极小项为了说明主析取范式的概念，首先介绍一下极小项的相关理论内容。

定义：n 个命题变元组成的合取式，该式中要包含所有这n 个变元或它的否认，那么称这个合取式为关于这n 个命题变元的极小项。

性质：〔1〕对于n 个原子n P P P ,......,,21而言，其所有的极小项共有n 2个。

(2) 每个小项当其真值指派与编码一样时，其真值为T ，在其余12-n种指派情况下均为F 。

主析取范式定义：对于一个给定的命题公式，假设有一个由小项的析取组成的命题公式与其等价，那么称该等价式为给定命题公式的主析取范式。

定理1. 对于任何一个命题公式，其主析取范式存在且唯一。

〔证明略〕 2 主析取范式的求法解析 2.1 推演法对于给定命题公式的主析取范式可由推演法求出，其主要步骤归纳为： (1) 首先将公式化为析取范式。

(2) 除去析取范式中永假的析取项，并将析取式中重复出现的合取项和一样变元合并。

(3) 对于不是小项的合取式，补入没有出现的命题变元，即通过合取添加)(P P ⌝∨式，然后应用分配律展开公式。

例1. 求)()(R Q Q P ∧∨∧的主析取范式解 111110011011111110111)()()()())()(())()(()()(m m m m m m m P R Q P R Q R Q P R Q P P P R Q R R Q P R Q Q P ∨∨⇔∨∨∨⇔⌝∧∧∨∧∧∨⌝∧∧∨∧∧⇔⌝∨∧∧∨⌝∨∧∧⇔∧∨∧特点：初步将命题公式化为一般析取范式后，各合式公式中缺少一到两个命题变元即该形式已经接近主析取范式时，可以用该法较快得解。

1#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]; charT1[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; } }2printf(\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. 给定一个布尔函数，列出其真值表，其中包括所有可能的输入和相应的输出值。

2. 找出真值表中所有输出为1的每个组合，并将它们称为最小项。

例如，如果布尔函数有4个输入变量，则真值表将包含16个可能的组合。

如果输出为1的组合有3个，则有3个最小项。

3. 将这些最小项组合成一个包含所有最小项的主范式。

这可以通过使用布尔代数规则来完成，例如使用与操作符和或操作符。

4. 如果存在多个主范式，则可以使用其中任何一个来简化布尔函数。

但是，一般情况下，我们会选择包含最少项的主范式，因为这意味着最简单的逻辑表达式。

5. 如果需要，可以使用主范式来创建逻辑电路或编写计算机程序，以实现相应的布尔函数。

通过这些步骤，我们可以快速、准确地确定布尔函数的主范式，从而简化其逻辑表达式并实现相应的功能。

- 1 -。

简答题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下的含义，并指出其真值。

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

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

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

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

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

利用真值表求一个命题逻辑式的主合取范式可以通过以下步骤完成：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. 在真值表的右侧列出命题逻辑公式的值，其中1表示真，0表示假。

3. 将真值表中所有结果为真的行对应的命题变量取合取式，即为主合取范式。

下面以一个简单的例题进行说明。

例题：求命题逻辑公式p∧(p∨q)的主合取范式。

首先列出真值表如下：p q p∨q p∧(p∨q)0 0 0 00 1 1 01 0 1 11 1 1 1由此可得主合取范式为p∧(p∨q) = p。

（二）代数化简法代数化简法是一种基于逻辑代数的求主合取范式的方法，它的步骤如下：1. 将命题逻辑公式转化为逻辑代数表达式。

2. 进行逻辑代数的运算，如与、或、非、异或等。

3. 将逻辑代数表达式转化为命题逻辑公式。

下面以一个简单的例题进行说明。

例题：求命题逻辑公式(p∨q)∧(p∨r)的主合取范式。

首先将命题逻辑公式转化为逻辑代数表达式如下：(p+q)(p+r)然后进行逻辑代数的运算如下：(p+q)(p+r) = pp+pr+qp+qr= pr+qp最后将逻辑代数表达式转化为命题逻辑公式，即为主合取范式：pr∧qp。

二、例题解析下面给出一个例题，通过真值表法和代数化简法求出其主合取范式。

例题：求命题逻辑公式(p∨q)∧(p∨r∨q)的主合取范式。

（一）真值表法首先列出真值表如下：p q r (p∨r∨q) (p∨q)∧(p∨r∨q)0 0 0 1 00 0 1 1 00 1 0 1 10 1 1 1 11 0 0 0 01 0 1 1 11 1 0 1 11 1 1 1 1由此可得主合取范式为(p∨q)∧(p∨r∨q) = q∧(p∨r)。

第四节 主析取范式与主合取范式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 。

用真值表求主合取范式在逻辑学和计算机科学中，主合取范式(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不一定是唯一的。