离散数学实验报告命题逻辑—构造命题公式的真值表

一实验目的 (1)二实验内容 (1)三实验环境 (1)四实验原理和实现过程（算法描述） (1)五实验数据及结果分析； (3)六源程序清单； (5)七其他收获和体会。

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

二实验内容1.从键盘输入两个命题变元P和Q的真值，求它们的合取、析取、条件和双条件的真值。

(A)2.求任意一个命题公式的真值表(B,并根据真值表求主范式(C))三实验环境C或C++语言编程环境实现。

四实验原理和实现过程(算法描述)A：首先提示用户输入真值指派，然后判断用户输入的是否是0或者1,如果不是则利用while语句提示错误，然后提示重新输入直至输入正确，再根据用户输入的真值给代表合取，析取，蕴含，双条件的变量赋值，再以两行表格形式输出所得结果。

最后提示按#键退出, 否则继续循环求真值。

B：主要思路：首先提示用户输入表达式，然后编写并调用一个函数将表达式转换为逆波兰式，在转换的同时，插入部分语句将表达式中的变量名存储到数组bianl[N]中，然后输出存好的各变量名及用户输入的表达式(建立表头)，将每次的真值指派存在数组zhi[]中，编写函数zzhi ()每次调用zzhi ()时都使数组zhi □中的真值加1, (利用递推实现加一时可能的进位，)然后编写并调用一函数qiuzhi ()计算每次真值指派下的逆波兰表达式的值，再输出各真值指派和求出的表达式的真值，然后调用函数zzhiO将真值指派的数组加1, 最后外围利用while 语句循环输出每个不同的真值指派和该指派下表达式的值。

将表达式转换成逆波兰式并将变量提取的算法：首先需要分配2 个栈，一个作为临时存储运算符的栈fu[], —个作为输入逆波兰式的栈nibol：],从中缀式的左端开始取字符，逐序进行如下步骤：（1）若取出的字符是字母，则该字母直接送入nibol[]栈。

同时为了找出所有变量，将该变量名与数组bianl[]中已有的元素比较, 如果bianl □中还没有该字母，则该字母是新出现的变量，将其录入数组bianl []中。

离散数学上机实验指导徐凤生如果你需要索取源程序，请发邮件至xfs@。

实验11实验内容（1）求任意一个命题公式的真值表。

（2）利用真值表求任意一个命题公式的主范式。

（3）利用真值表进行逻辑推理。

注：（2）和（3）可在（1）的基础上完成。

2实验目的真值表是命题逻辑中的一个十分重要的概念，利用它几乎可以解决命题逻辑中的所有问题。

例如，利用命题公式的真值表，可以判断命题公式的类型、求命题公式的主范式、判断两命题公式是否等价，还可以进行推理等。

本实验通过编写一个程序，让计算机给出命题公式的真值表，并在此基础上进行命题公式类型的判定、求命题公式的主范式等。

目的是让学生更加深刻地理解真值表的概念，并掌握真值表的求解方法及其在解决命题逻辑中其他问题中的应用。

3算法的主要思想利用计算机求命题公式真值表的关键是：①给出命题变元的每一组赋值；②计算命题公式在每一组赋值下的真值。

真值表中命题变元的取值具有如下规律：每列中0和1是交替出现的，且0和1连续出现的个数相同。

n个命题变元的每组赋值的生成算法可基于这种思想。

含有n个命题变元的命题公式的真值的计算采用的方法为“算符优先法”。

为了程序实现的方便，约定命题变元只用一个字母表示，非、合取、析取、条件和双条件联结词分别用！、&、|、－、＋来表示。

算符之间的优先关系如表1-32所示：为实现算符优先算法，另一个称作OPND，用以寄存操作数或运算结果。

算法的基本思想是：（1）首先设置操作数栈为空栈，符号“@”为运算符的栈底元素；（2）调用函数Divi（exp，myopnd）得到命题公式包含的命题变元序列myopnd（按字典序排列，同一个命题变元只出现一次）；（3）依次读入命题公式中的每个字符，若是命题变元则其对应的赋值进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较后作相应操作，直至整个命题公式求值完毕。

实验21实验内容（1）求任意两个集合的交集、并集、差集。

（2）求任意一个集合的幂集。

《离散数学》双语教学第一章真值表，逻辑和证明《离散数学》双语教学第一章真值表，逻辑和证明CHAPTER 1TRUTH TABLES, LOGIC, AND PROOFSGlossarystatement, proposition:命题 logical connective:命题联结词compound statement:复合命题 propositional variable:命题变元negation:否定(式)truth table:真值表conjunction:合取 disjunction:析取 propositional function:命题公式fallacy: 谬误syllogism:三段论universal quantification:全称量词化 existential quantification:存在量词化 hypothesis(premise): 假设～前提～前件 conditional statement, implication:条件式～蕴涵式 consequent, conclusion:结论～后件 converse:逆命题contrapositive:逆否命题biconditional, equivalence:双条件式～等价(逻辑)等价的 logically equivalent:contingency:可满足式tautology:永真式(重言式)contradiction, absurdity:永假(矛盾)式 logically follow:是…的逻辑结论 argument:论证axioms:公理第 1 页共 47 页 2010-12-27《离散数学》双语教学第一章真值表，逻辑和证明 postulate:公设rules of reference:推理规则modus ponens:肯定律 modus tollens:否定律reductio ad absurdum:归谬律proof by contradiction:反证法counterexample:反例 minterm:极小项disjunctive normal form:主析取范式maxterm:极大项conjunctive normal form:主合取范式第 2 页共 47 页 2010-12-27《离散数学》双语教学第一章真值表，逻辑和证明本章内容及教学要点:1.1 Statements and Connectives教学内容:statements(propositions)～compound statement～connectives:negation～conjunction～disjunction～truth tables 1.2 Conditional Statements教学内容:implications(conditional statements)～biconditional～equivalent～and quantifications1.3 Equivalent Statements教学内容:logical equivalence～converse～inverse～contrapositive～tautology～contradiction(absurdity)～contingency～properties of logical connectives1.4 Axiomatic Systems: Arguments and Proofs教学内容:rules of reference～augument～valid argument～hypotheses～premises～law of detachment(modus ponens)～syllogism～modus tollens～addition～proof by contradiction 1.5 Normal Forms教学内容:minterm～disjunctive normal form～maxterm～conjunctive normal form定理证明及例题解答第 3 页共 47 页 2010-12-27《离散数学》双语教学第一章真值表，逻辑和证明Logic, developed by Aristotle, has been used through the centuries in the development of many areas of learning including theology, philosophy, and mathematics. It is the foundation on which the whole structure of mathematics is built. Basically it is the science of reasoning, which may allow us to determine statements about mathematics whether are true or false based on a set of basic assumptions called axioms. Logic is also used in computer science to construct computer programs and to show that programs do what they are designed to do.逻辑学是研究人的思维形式的科学. 而数理逻辑是逻辑学的一个重要分支～是用数学形式化的方法研究思维规律的一门学科. 由于它使用了一套符号来简洁地表达出各种推理的逻辑关系～故它又称符号逻辑.数理逻辑用数学方法研究推理、利用符号体系研究推理过程中前提和结论之间的关系. 数理逻辑的主要内容:逻辑演算(L和L)、公理化集合论、模型论、S p构造主义与证明论. 数理逻辑在电子线路、机器证明、自动化系统、编译理论、算法设计方法方面有广泛的应用.The rules of logic specify the meaning of mathematicalstatements. Logic is the basis of all mathematical reasoning, and it has practical applications to the design of computing machines, to system specifications, to artificial intelligence(AI), to computer programming, to programming languages, and to other areas of computer science, as well as to many other fields of study.第 4 页共 47 页 2010-12-27《离散数学》双语教学第一章真值表，逻辑和证明1.1 Statements and Connectivess(命题和联结词)命题逻辑研究的对象是命题及命题之间的逻辑关系.Propositions are the basic building blocks of logic. Many mathematical statements are constructed by combining one or more propositions.定义1.1.1 A proposition is a statement or declarative sentence that is either true or false, but not both,命题是一个非真即假的陈述句,.因此不能判断真假的陈述句、疑问句、祈使句和感叹句都不是命题.,1, The true or false value assigned to a statement is called its truth value; (一个命题的真或假称为命题的真值. 真用T或1表示～假用F或0表示),2, 一个陈述句有真值与是否知道它的真假是两回事.例1.1.1 判断下列语句是不是命题,若是～给出命题的真值: (1) 陕西师大不是一座工厂.(2) 你喜欢唱歌吗,(3) 给我一块钱吧:(4) 我不是陕西师大的学生.(5) 我正在说谎.Logical connectives(命题联结词)数理逻辑的特点是并不关心具体某个命题的真假～而是将逻辑推理变成类似数学演算的形式化过程, 关心的是命题之间的关联性. 因此需要进行命题符号化.命题联结词的作用是为了将简单命题组合成复合命题.We will now introduce the logical connectives that are used to form new propositions from existing propositions. And once truth values have been assigned to simple propositions, we can progress to more complicated compound statements.A statement that contains no connectives is called a simple第 5 页共 47 页 2010-12-27《离散数学》双语教学第一章真值表，逻辑和证明statement. We will use p,q,r…to represent simple statements(简单命题就是简单陈述句～用字母p,q,r…(或带下标)表示),Sometimes, the letters p,q,r,s,…are used to denote propositional variables that can be replacedby statements(命题变元:可以用命题代替的变元).A statement that contains logical connectives(命题联结词) is called compound statements(复合命题). In general, a compound statement may have many component parts, each of which is itself a statement, represented by some propositional variable. The truth of a compound proposition is determined by the truth or falsity of the component parts.propositional constant(命题常元):T(1)或F(0)～或者表示一个确定的命题,propositional variable(命题变元):可用一个特定的命题取代。

“离散数学”实验报告目录一、实验目的 (3)二、实验内容 (3)三、实验环境 (3)四、实验原理和实现过程（算法描述） (3)1、实验原理........................................................................................................2、实验过程.......................................................................................................五、实验数据及结果分析 (13)六、源程序清单 (24)源代码 (24)七、其他收获及体会 (45)一、实验目的实验一：熟悉掌握命题逻辑中的联接词、真值表、主范式等，进一步能用它们来解决实际问题。

实验二：掌握关系的概念与性质，基本的关系运算，关系的各种闭包的求法。

理解等价类的概念，掌握等价类的求解方法。

实验三：理解图论的基本概念，图的矩阵表示，图的连通性，图的遍历，以及求图的连通支方法。

二、实验内容实验一：1. 从键盘输入两个命题变元P和Q的真值，求它们的合取、析取、条件和双条件的真值。

（A）2. 求任意一个命题公式的真值表（B，并根据真值表求主范式（C））实验二：1.求有限集上给定关系的自反、对称和传递闭包。

（有两种求解方法，只做一种为A，两种都做为B）2. 求有限集上等价关系的数目。

（有两种求解方法，只做一种为A，两种都做为B）3. 求解商集，输入集合和等价关系，求相应的商集。

（C）实验三：以偶对的形式输入一个无向简单图的边，建立该图的邻接矩阵，判断图是否连通（A）。

并计算任意两个结点间的距离（B）。

对不连通的图输出其各个连通支（C）。

三、实验环境C或C＋＋语言编程环境实现。

四、实验原理和实现过程（算法描述）实验一：1.实验原理（1）合取：二元命题联结词。

离散数学实验报告真值四川⼤学计算机学院实验报告实验名称：求合适公式的真值指导教师：姓名：学号：班级：⽇期：⼀．实验⽬的设计⼀个程序，来达到输⼊⼀个正确的合式公式，求它的真值表。

通过实验，更好地掌握离散数学中的概念、性质和运算。

⼆．功能设计任意输⼊的合适公式计算其真值表并输出三．界⾯设计四．实现步骤算法逻辑如下：（1）任意设计⼀个真值判断表达式，并使其赋值计算（2）计算模拟器中所对应的⼀组真值指派下合式公式的真值（3）输出真值表中对应于模拟器所给出的⼀组真值指派及这组真值指派所对应的⼀⾏真值。

五．运⾏结果六．源代码#include#include#includeusing namespace std;string calcValue(string value1);string calcValueNop(string value1);string caclAnd(string x,string y);string caclOr(string x,string y);string caclNot(string x);int main(){string in,varList="";//="!a+b^c"cout<<"*****************************************\n"<cout<<"** 欢迎进⼊逻辑运算软件**\n"<cout<<"** (可运算真值表，⽀持括号) **\n"<cout<<"** ⽤!表⽰否定**\n"<cout<<"** ⽤^表⽰合取**\n"<cout<<"** ⽤+表⽰析取**\n"<cout<<"*****************************************\n\n"<cout<<"请输⼊命题公式：注意: !,^,+,(,),字母为合法,不要有数字、空格，括号也要匹配！"< cout<<"⽰例：!a+b^c"<cin>>in;cout<<"输⼊命题公式"<int length=in.length();int i=0,j=0;for(i=0;ichar code=in[i];if( ((code>=97)&&(code<123)||((code>=65))&&(code<81))&&varList.find(code, 0)==-1 ) varList+=code;}int n=varList.length();for(i=0;icout<int flag;char *trow=new char[n];for(i=0;ifor(i=0;ifor(j=0;jcout<string value1=in;for(j=0;jchar x=varList[j];for(int k=0;kif(value1[k]==x)value1[k]=trow[j];}cout<flag=1;for(j=n-1;j>-1;j--) {int temp;temp=int(trow[j])-48;flag=flag+temp;if(flag==2) {trow[j]='0';flag=1;}else{trow[j]='1';flag=0;break;}}}delete trow;system("pause");return 0;}string calcValue(string value1){int nlp=value1.find('(',0);int nrp=value1.length();string x="",v="";int i=nlp+1;while(nlp>=0) {x=value1.substr(i,1);if(x=="("){nlp=i;i++;}else{if(x==")"){nrp=i;v=calcValueNop(value1.substr(nlp+1,nrp-nlp-1));value1=(nlp>0?value1.substr(0,nlp):"")+v+((nrp+1)<=value1.length()?value1.substr(n rp+1):"");nlp=value1.find('(',0);i=nlp+1;}else{i=i+1;}}if(i>=value1.length()){nlp=value1.find('(',0);i=nlp+1;}}return calcValueNop(value1);}string calcValueNop(string value1){int nnot=value1.find('!',0);while(nnot>=0) {value1=(nnot>0?value1.substr(0,nnot):"")+caclNot(value1.substr(nnot+1,1))+((nnot+ 2)<=value1.length()?value1.substr(nnot+2):"");nnot=value1.find('!',0);}int nand=value1.find('^',0);while (nand>0){value1=((nand-1)>0?value1.substr(0,nand-1):"")+caclAnd(value1.substr(nand-1,1),va lue1.substr(nand+1,1))+((nand+2) <=value1.length()?value1.substr(nand+2):"");nand=value1.find('^',0);}int nOr=value1.find('+',0);while (nOr>0){value1=((nOr-1)>0?value1.substr(0,nOr-1):"")+caclOr(value1.substr(nOr-1,1),value1. substr(nOr+1,1))+((nOr+2)<=value1.length()?value1.substr(nOr+2):"");nOr=value1.find('+',0);}return value1;}string caclAnd(string x,string y){if ((x=="1") && (y=="1")){return "1";}else {return "0";}}string caclOr(string x,string y){if ((x=="0") && (y=="0")){return "0";}else {return "1";}}string caclNot(string x){if (x=="1") {return "0";}else {return "1";}}七．⼼得体会离散数学课程在各学科领域，特别在计算机科学与技术领域有着⼴泛的应⽤，同时离散数学也是计算机专业的许多专业课程，如程序设计语⾔编译技术、⼈⼯智能、算法设计与分析等必不可少的先⾏课程。

离散数学实验报告专业班级：姓名：学号：实验成绩：1．【实验题目】命题逻辑（2）2．【实验目的】熟悉掌握命题逻辑中真值表，进一步能用它们来解决实际问题。

3．【实验内容】求任意一个命题公式的真值表4. 【实验要求】通过以下界面提示实现相应逻辑运算，列出其真值表****************************************************************请选择（1—6）要进行的真值表运算：1.逻辑非（┌ P）2.合取（P∧Q）3.析取（P∨Q）4.条件（P→Q）5.双条件（P←→Q）6.继续/退出（y/n）****************************************************************5. 【算法描述】1.实验原理真值表:列出命题公式真假值的表，通常以1表示真，0 表示假。

命题公式的取值由组成命题公式的命题变元的取值和命题联结词决定，命题联结词的真值表给出了真假值的算法。

2.实验过程对于给定的命题公式，生成相应真值表，然后用函数运算，输出结果：如生成逻辑非、合取、析取、条件、双条件表达式的真值表，例如：输入 !a输出真值表如下：a !a0 110输入a&&b输出真值表如下：a b a∧b0 0 00 1 01 0 01 1 1输入a||b输出真值表如下：a b a∨b0 0 00 1 11 0 11 1 1输入a->b输出真值表如下：a b a→b0 0 10 1 11 0 01 1 1输入a<>b (其中<>表示双条件) 输出真值表如下：a b a←→b0 0 10 1 01 0 01 1 16. 【源程序（带注释）】#include <stdio.h>#include <stdlib.h>#include <string.h>static int a[2];//定义全局数组a[2]void main(){int luojifei();//声明逻辑非函数int hequ();// 声明合取函数int xiqu();//声明析取函数int tiaojian();//声明条件函数int shuangtiaojian();//声明双条件函数void print();//声明打印星号函数char n[10];char c;print();//打印星号loop: //loop循环开始标记do{fflush(stdin);//清空输入缓存区，以免对后面的数据输入造成干扰printf("请选择（1-6）要进行的真值表运算：\n\n");printf("\t1.逻辑非（┌P）\n\t2.合取（P∧Q）\n\t3.析取（P∨Q）\n\t4.条件（P→Q）\n\t5.双条件（P←→Q）\n\t6.继续/退出（y/n）\n");print();printf("\t提示：若想查看真值表，按提示输入：\n\t!a 查看逻辑非真值表\n\ta&&b 查看合取真值表\n\ta||b 查看析取真值表\n\ta->b 查看条件真值表\n\ta<>b 查看双条件真值表\n");print();scanf("%s",n);//接收用户输入的功能序号if (strcmp("1",n)==0) //若输入为1，进行逻辑非运算{print();printf("\n逻辑非结果┌P=%d\n",luojifei());//逻辑非运算结果来自luojifei子函数的返回值print();fflush(stdin);system("pause");}if (strcmp("2",n)==0) //若输入为2，进行合取运算{print();printf("\n合取结果（P∧Q）=%d\n",hequ());//合取运算结果来自hequ子函数的返回值print();fflush(stdin);system("pause");}if (strcmp("3",n)==0) //若输入为3，进行析取运算{print();printf("\n析取结果（P∨Q）=%d\n",xiqu());//析取运算结果来自xiqu子函数的返回值print();fflush(stdin);system("pause");}if (strcmp("4",n)==0) //若输入为4，进行条件运算{print();printf("\n条件运算结果（P→Q）=%d\n",tiaojian());//条件运算结果来自tiaojian子函数的返回值print();fflush(stdin);system("pause");}if (strcmp("5",n)==0) //若输入为5，进行双条件运算{print();printf("\n双条件运算结果（P→Q）=%d\n",shuangtiaojian());//双条件运算结果来自shuangtiaojian子函数的返回值print();fflush(stdin);system("pause");}if (strcmp("6",n)==0) break;//若输入为6，跳出while循环if (strcmp("!a",n)==0) {printf("逻辑非真值表为：\n\ta !a\n\t0 1\n\t1 0\n") ; print();fflush(stdin);system("pause");}if (strcmp("a&&b",n)==0) {printf("合取真值表为：\n\ta b a∧b\n\t0 0 0\n\t0 1 0\n\t1 0 0\n\t1 1 1\n"); print();fflush(stdin);system("pause");}if (strcmp("a||b",n)==0) {printf("析取真值表为：\n\ta b a∨b\n\t0 0 0\n\t0 1 1\n\t1 0 1\n\t1 1 1\n"); print();fflush(stdin);system("pause");}if (strcmp("a->b",n)==0) {printf("条件真值表为：\n\ta b a→b\n\t0 0 1\n\t0 1 1\n\t1 0 0\n\t1 1 1\n"); print();fflush(stdin);system("pause");}if (strcmp("a<>b",n)==0) {printf("双条件真值表为：\n\ta b a←→b\n\t0 0 1\n\t0 1 0\n\t1 0 0\n\t1 1 1\n"); print();fflush(stdin);system("pause");}}while((c==getchar())!=EOF);//一直执行while循环，直到无更多的数据可读取档案结束fflush(stdin);//清空输入缓存区，以免对后面的数据输入造成干扰printf("\n确认退出（y/n）?");scanf("%c",&c);//接收用户输入的字符if(c=='y') exit(1);//字符为y，则退出程序else{print();fflush(stdin);goto loop;//返回loop循环起始标签}}void print()//定义print函数{printf("****************************************************************\n");}int panduanp(int p)//定义判断p的值是否有效的panduanp函数{while(p!=0 && p!=1)//当p不为0，且p不为1的时候进入while循环{printf("\n输入有误，请重新输入P的值（0或1）：\nP=");//提示用户输错数据fflush(stdin);scanf("%d",&p);//重新接收p的值，再进行while循环判断}return p;}void panduanpq(int p,int q)//定义判断p和q的值是否有效的panduanpq函数{while((p!=0 && p!=1) || (q!=0 && q!=1))//当p不为0也不为1，q不为0也不为1的时候进入循环{fflush(stdin);printf("输入错误，请重新输入：\nP=");scanf("%d",&p);printf("\nQ=");scanf("%d",&q);//重新接收p和q的值，再进行while循环判断}a[0]=p;a[1]=q;//将正确的p和q的值分别存储到全局数组变量a[0],a[1]中}int luojifei()//定义逻辑非函数{int panduanp(int p);//子函数里声明panduanp函数int p;printf("\n您要进行逻辑非运算，请输入P的值：\nP=");scanf("%d",&p);if(panduanp(p)==1) return 0;//调用判断p函数来确保输入的数据有效，并传送回p的值，再对p的值进行逻辑非判断else return 1;}int hequ()//定义合取函数{void panduanpq(int p,int q);//子函数里声明panduanpq函数int p,q;printf("\n您要进行合取运算，请输入P与Q的值（0或1）：\nP=");scanf("%d",&p);printf("Q=");scanf("%d",&q);panduanpq(p,q);//调用判断pq函数来确保输入的p,q数据有效，有效数据在判断pq函数中已经储存到了全局变量a[0],a[1]中if(a[0]==1 && a[1]==1) return 1;//合取时，只有在p,q均为1的时候，才返回1的值else return 0;}int xiqu()//定义析取函数{void panduanpq(int p,int q);//子函数里声明panduanpq函数int p,q;printf("\n您要进行析取运算，请输入P与Q的值（0或1）：\nP=");scanf("%d",&p);printf("Q=");scanf("%d",&q);panduanpq(p,q);//调用判断pq函数来确保输入的p,q数据有效，有效数据在判断pq函数中已经储存到了全局变量a[0],a[1]中if(a[0]==1 || a[1]==1) return 1;//析取时，只要有一个为1，即返回1的值else return 0;}int tiaojian()//定义条件运算函数{void panduanpq(int p,int q);//子函数里声明panduanpq函数int p,q;printf("\n您要进行条件运算，请输入P与Q的值（0或1）：\nP=");scanf("%d",&p);printf("Q=");scanf("%d",&q);panduanpq(p,q);//调用判断pq函数来确保输入的p,q数据有效，有效数据在判断pq函数中已经储存到了全局变量a[0],a[1]中if(a[0]==1 && a[1]==0 ) return 0;//蕴含时，只有在p为1,q为0的情况下返回0的值else return 1;}int shuangtiaojian()//定义双条件函数{void panduanpq(int p,int q);//子函数里声明panduanpq函数int p,q;printf("\n您要进行双条件运算，请输入P与Q的值（0或1）：\nP=");scanf("%d",&p);printf("Q=");scanf("%d",&q);panduanpq(p,q);//调用判断pq函数来确保输入的p,q数据有效，有效数据在判断pq函数中已经储存到了全局变量a[0],a[1]中if(a[0]==a[1] ) return 1;//等价时，只有在p=q的情况下，返回1的值else return 0;}7．【实验结果与分析总结（含运行结果截图）】测试输出真值表：测试逻辑非运算：测试合取运算：测试析取运算：测试条件运算：测试双条件运算：测试继续功能：分析总结实验二大体来说是在实验一的基础上进行修改而成，由于首先需要让用户选择6个功能中的其中一个功能，在执行功能运算的时候，需要多次对P和Q的值进行有效判断。