当前位置：文档之家 › 利用真值表法求主析取范式及主合取范式的实现

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

  • 格式：doc
  • 大小：302.50 KB
  • 文档页数：21

下载文档原格式

  / 21

合集下载

离散数学14.主合取范式

离散数学14.主合取范式
M0∧M1式(R∧R)形式 补R.用分配律等公式加以整理.
例2 求((PQ)R)P的主合取范式. 解: 原式 ((P∨Q)∨R)∨P (P∨Q)∧(R∨P ) (合取范式) ((P∨Q)∨(R∧R ))∧((R∨P )∨(Q∧Q)) (P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧ (P∨Q∨R) (P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) (主合取范式)
⑶用“∧”联结上述大项，即可.
例1 求 PQ和PQ的主合取范式
P Q PQ PQ
FF T
T
FT T
F
TF F
F
TT T
T
PQ M2 P∨Q PQ M1∧M2
(P∨Q )∧(P∨Q)
方法2：用公式的等价变换 ⑴先写出给定公式的合取范式
A1∧A2∧...∧An . ⑵除去合取范式中的所有为永真的合取项. ⑶合并相同的析取项和相同的变元. (4)为使每个Ai变成大项，对缺少变元的析取式Ai补全变
主合取范式
主合取范式
1.定义：给定的命题公式，如果有一个等价公式， 它仅由大项的合取所组成，则该等价式称作原式的主 合取范式.
2.主合取范式的求法 方法1：列真值表 ⑴列出给定公式的真值表. ⑵找出真值表中每个“F”对应的大项.
如何根据一组指派写对应的为“F”的大项：如果变 元P被指派为F，P在大项中以P形式出现；如变元P被指 派为T，P在大项中以P形式出现(确保该大项为F).

离散数学总结

离散数学总结
反例 设个体域为实数集合，A(x, y): x-y=1. 则 (x)(y)A(x, y)为真， 而(y)(x)A(x, y)为假， 所以(6)式反过来不成立.
总结下就是任意可以改成存在，存在不能变成 任意所以先做存在。 任意（推出ห้องสมุดไป่ตู้则先用德摩根律把推出给换了， 在把量词放进去！ 有限集合中元素的个数称为集合的基数 (cardinality). 集合A的基数表示为|A|(或card(A)=n). n card(P(A)=2 )幂集 设A, B为两个集合，A=B当且仅当AB且B A. 即A=B(AB) (B A)
个人. 则命题符号化为：
(x)(y)(F(x) F(y) H(x, y) L(x, y))
(8) 每个自然数都有后继数.
解： 引入特性谓词 F(x) ： x是自然数.并设 H(x, y)：y是x的后继数. 则命题符号化为： (x)(F(x) (y) (F(y) H(x, y))
证： 任取x，则
xA∩ (B∪C) xA xB∪C xA (xB x C) (xA xB) (xA xC) x A∩B x A∩C
x (A∩B)∪(A∩C)
推广
三、集合中元素的计数
|A∪B∪C |A||B|| |A∩B ||A∩C||B∩C| |A∩B∩C | C| |
(x)A(x) (x)B(x)
量词转化律
E20
三、谓词演算的等价式与蕴含式
(三) 谓词演算中常见的蕴含式： (1)(x)A(x)(x)B(x) (x)(A(x)B(x)) (2)(x)(A(x)B(x)) (x)A(x)(x)B(x) (1), (2)两式反过来均不成立. 反例 设个体域为自然数集合， A(x): x为奇数. B(x): x为偶数.则 (1)(x)(A(x)B(x))为真， 而(x)A(x)为假， (x)B(x)为假， 故(x)A(x)(x)B(x)为假， 所以(1)式反过来不成立； (2)(x)A(x)为真，(x)B(x)为真， 故(x)A(x)(x)B(x)为真, 但(x)(A(x)B(x))为假， 所以(2)式反过来也不成立.

主析取范式

主析取范式

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

离散数学第2次作业参考答案

离散数学第2次作业参考答案
1
1
0
0
1
1
1
0
0
1
1
1
1
1
1
0
1
0
1
(3-2)主析取范式：
(4)由真值表和主析取范式分别可以验证该推理正确。
6、(每题12分，共24分)
(1)如果今天是星期六，我们就要到颐和园或圆明园去玩。如果颐和园游人太多，我们就不去颐和园。今天是星期六。颐和园游人太多。所以我们去圆明园玩。
解：
(1)令p:今天是星期六; q:我们要到颐和园玩; r:我们要到圆明园玩; s:颐和园游人太多.
5、(20分)用2种方法(真值表法、主析取范式法)判断下面推理是否正确。
若 是奇数，则 不能被2整除。若 是偶数，则 能被2整除。因此，如果 是偶数，则 不是奇数。
解：(1)简单命题符号化：
p: 是奇数，q: 能被2整除，r: 是偶数。
(2)前提和结论分别符号化为：
若 是奇数，则 不能被2整除: p→ q。
2018级离散数学第二次作业参考答案
学号：姓名：班级：总分：
1、(每空5分，共30分)
(1)已知公式A含有3个命题变项p,q,r,并且它的成真赋值为000，011，110，那么命题公式A的成假赋值为001,010,100,101,111,主析取范式为 ,主合取范式为M1∧M2∧M4∧M5∧M7。
(2)已知公式A含有3个命题变项，并且公式A的主合取范式为 ，那么公式A的成真赋值为000, 010,101,110,111，成假赋值为001, 011, 100，公式A的主析取范式为 。
解：
令p:小王是理科生, q:小王是文科生, r:小王的数学成绩很好.
前提: p→r, ¬q→p, ¬r

主析取范式和主合取范式

主析取范式和主合取范式

应用主析取范式分析和解决实际 问题
例2.12 某科研所要从3名科研骨干A,B,C中挑 选1～2名出国进修。由于工作原因，选派时 要满足以下条件： (1)若A去，则C同去。 (2)若B去，则C不能去。 (3)若C不去，则A或B可以去。 问应如何选派他们去？
分析： (1)将简单命题符号化
说明
• n个命题变项共可产生2n个不同的极小项。其 中每个极小项都有且仅有一个成真赋值。若 成真赋值所对应的二进制数转换为十进制数i ，就将所对应极小项记作mi 。 • 类似地，n个命题变项共可产生2n个极大项， 每个极大项只有一个成假赋值，将其对应的 十进制数i做极大项的角标，记作Mi。
表2.3 p,q形成的极小项与极大项
定理2.5 任何命题公式都存在着与之等值的主析取 范式和主合取范式，并且是唯一的。
定理2.4.5的证明
(只证主析取范式的存在和唯一性) (1)证明存在性。 设A是任一含n个命题变项的公式。 由定理2.3可知，存在与A等值的析取范式A′， 即AA′，若A′的某个简单合取式Ai中既不含 命题变项pj，也不含它的否定式┐pj，则将Ai展 成如下形式： Ai Ai∧1 Ai∧(pj∨┐pj) (Ai∧pj)∨(Aj∧┐pj)
析取范式和合取范式的性质
定理2.2 (1)一个析取范式是矛盾式当且仅当它的每个 简单合取式都是矛盾式。 (2)一个合取范式是重言式当且仅当它的每个 简单析取式都是重言式。
范式存在的讨论
• 在范式中不会出现联结词→与，否则可使 用等值式消除 A→B ┐A∨B AB (┐A∨B)∧(A∨┐B) • 在范式中不会出现形如 ┐┐A,┐(A∧B),┐(A∨B)的公式： ┐┐A A ┐(A∧B) ┐A∨┐B • ┐(A∨B)┐A∧┐B

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

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

#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该命题公式不存在主合取范式。

求给定命题公式的真值表并根据真值表求公式的主范式

求给定命题公式的真值表并根据真值表求公式的主范式(求给定命题公式的真值表并根据真值表求公式的主范式)专业网络工程班级 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)。

离散数学(第3讲)


2018/11/12
计算机学院
27
（6）若析取范式的某一个短语中缺少该命题公式中所 规定的命题变元P ，则可用公式： （～Ｐ∨Ｐ）∧Q=Q 将命题变元 P 补进去，并利用分配律展开，然后合并 相同的短语，此时得到的短语将是标准的极小项； （7）若合取范式的某一个子句中缺少该命题公式中所 规定的命题变元P ，则可用公式： （～Ｐ∧Ｐ）∨Q=Q 将命题变元 P 补进去，并利用分配律展开，然后合并 相同的子句，此时得到的子句将是标准的极大项。 （8）利用幂等律将相同的极小项和极大项合并，同时 利用交换律进行顺序调整，由此可转换成标准的主析 取范式和主合取范式。
2018/11/12 计算机学院 8
求一个命题公式的与之等价的析取范式和合取 范式，其步骤如下： （1）利用等价公式中的等价式和蕴涵式将公式 中的→、用联结词～ 、∧、∨来取代； （ 2 ）利用德 摩根定律将否定号┐移到各个命 题变元的前端； （3）利用结合律、分配律、吸收律、幂等律、 交换律等将公式化成其等价的析取范式和合取范 式。
demorgan定律可知对公式的否定可以直接作用到原子本身并且把公式中的变成把变成即得201521计算机学院结合律分配律该式正好是b左端的对偶式由a及对偶原理得证该式正好是右端的对偶式201521计算机学院一个命题公式可有无穷多个和它等价的命题公式用真值表或等价变换证明它们是否等价往往比较困难甚至连计算机也不能解决
2018/11/12
计算机学院
14
主（特异、正则）合取范式
定义1-4.4 在n个变元的基本和（子句）中，若每一个变 元与其否定并不同时存在，且二者之一必出现且仅出现一 次，则这种基本和称为极大项。 由有限个极大项组成的合取式称为 主合取范式。 以下是由两个原子构成的极大项的真值表 P 1 1 0 0 Q 1 0 1 0 P∨Q 1 1 1 0 P∨～Q 1 1 0 1

主析取范式与主合取范式

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

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
}
void If() //条件,b->a
{
result = (b == 1 && a == 0) ? 0 : 1;
stack.Push(result);
}
void Doubleif() //双条件
{
result = (b == a) ? 1 : 0;
stack.Push(result);
}
bool CanIn(char out)//优先级的判断
stack.Push(result);
}
void Or() //析取
{
result = a + b;
result = result > 1 ? 1 : result;
stack.Push(result);
}
void And() //合取
{
result = a * b;
stack.Push(result);
}
int p, q, r, s, t, u;
int a, b, result;
int v =0;
int number;//用number表示变元的个数
SeqStack stack(200);
void Not() //否定
{
a = stack.Top();
stack.Pop();
result = a == 1 ? 0 : 1;
case '|':o = 6; break;
case '&':o = 8; break;
case '!':o = 10; break;
case ')':o = 1; break;
}
if(i < o)
return true;
else
return false;
}
void InfixToPostfix()//中缀表达式转后缀表达式
二、实验环境(实验设备)
硬件:PC机。
软件:Code::Blocks（C++）
三、实验原理及内容
内容：编程实现用真值表法求任意含三个以内变量的合式公式的主析取范式和主合取范式。
原理：首先读入变元个数，然后读入合式公式，用堆栈的知识将中缀表达式转化为后缀表达式，调用否定、析取、合取、条件、双条件的函数计算P、Q、R取不同真值时合式公式的真值，然后输出真值表，调用计算主析取范式和主合取范式的函数并输出。
};
SeqStack::SeqStack(int mSize)
{
maxtop = mSize - 1;
top = -1;
st = new char[mSize];
}
SeqStack::~SeqStack()
{
delete[]st;
}
char SeqStack::Top()
{
return st[top];
{
char in = stack.Top();
int i, o;
switch(in)
{
case '#':i = 0; break;
case '(':i = 1; break;
case '-':i = 3; break;
case '>':i = 5; break;
case '|':i = 7; break;
}
bool SeqStack::Push(char x)
{
if(top == maxtop)
return false;
st[++top] = x;
return true;
}
bool SeqStack::Pop()
{
if(top == -1)
return false;
top--;
return true;
程序：
#include<iostream>
#include<string>
#include<conio.h>
#include<windows.h>
using namespace std;
string OriginalForm; //原式
string Hequ; //主合取范式
string Xiqu; //主析取范式
实验报告
（/学年第一学期）
课程名称
离散数学
实验名称
利用真值表法求主析取范式及主合取范式的实现
实验时间
年
月
日
指导单位
指导教师
学生姓名
班级学号学院(系)专业 Nhomakorabea实验报告
实验名称
利用真值表法求主析取范式及主合取范式的实现
指导教师
实验类型
上机
实验学时
4
实验时间
一、实验目的和要求
能够列出合式公式的真值表并给出相应主析取范式和主合取范式。
{
tmp=tmp+OriginalForm[i];
continue;
}
if(CanIn(OriginalForm[i]))
stack.Push(OriginalForm[i]);
else if(OriginalForm[i] == ')')
{
while(stack.Top() != '(')
{
tmp = tmp + stack.Top();
{
string tmp = "";
stack.Push('#');
for(int i = 0; (unsigned)i <OriginalForm.length(); i++)
{
if(OriginalForm[i] == 'P' || OriginalForm[i] == 'Q' ||OriginalForm[i] == 'R' || OriginalForm[i] == 'S' || OriginalForm[i] == 'T' || OriginalForm[i] == 'U')
stack.Pop();
}
stack.Pop();
}
else
{
do
{
tmp = tmp + stack.Top();
stack.Pop();
} while(!CanIn(OriginalForm[i]));
stack.Push(OriginalForm[i]);
}
case '&':i = 9; break;
case '!':i = 11; break;
case ')':i = 12; break;
}
switch(out)
{
case '#':o = 0; break;
case '(':o = 12; break;
case '-':o = 2; break;
case '>':o = 4; break;
class SeqStack//建立一个堆栈，利用将中缀表达式转为后缀表达式
{
public:
SeqStack(int mSize);
~SeqStack();
char Top();
bool Push(char x);
bool Pop();
private:
char *st;
int top;
int maxtop;