逻辑命题公式计算
题号：第一题
题目：电梯模拟
1，需求分析：
计算命题演算公式的真值
所谓命题演算公式是指由逻辑变量（其值为TRUE或FALSE）和逻辑运算符∧（AND）、∨（OR）和┐（NOT）按一定规则所组成的公式（蕴含之类的运算可以用∧、∨和┐来表示）。公式运算的先后顺序为┐、∧、∨，而括号（）可以改变优先次序。已知一个命题演算公式及各变量的值，要求设计一个程序来计算公式的真值。
要求：
（1）利用二叉树来计算公式的真值。首先利用堆栈将中缀形式的公式变为后缀形式；然后根据后缀形式，从叶结点开始构造相应的二叉树；最后按后序遍历该树，求各子树之值，即每到达一个结点，其子树之值已经计算出来，当到达根结点时，求得的值就是公式之真值。
（2）逻辑变元的标识符不限于单字母，而可以是任意长的字母数字串。
（3）根据用户的要求显示表达式的真值表。
2，设计：
2.1 设计思想：
<1>，数据结构设计：
(1) 线性堆栈1的数据结构定义
typedef struct
{
DataType stack [MaxStackSize];
int top; /* 当前栈的表长*/
} SeqStack;
用线性堆栈主要是用来存储输入的字符，它的作用就是将中缀表达式变成后缀表达式。
(2) 线性堆栈2的数据结构定义
typedef struct
{
BiTreeNode *stack [MaxStackSize];
int top; /* 当前栈的表长*/
} TreeStack;
这个堆栈和上面的堆栈的唯一不同就是它们存储的数据的类型不同，此堆栈存储的是树节点，它的作用是将后缀表达式构成一棵二叉树。
(3)树节点数据结构定义
typedef struct Node
{
DataType data;
struct Node *leftChild;
struct Node *rightChild;
}BiTreeNode;
<2>算法设计详细思路如下：
首先实现将中缀表达式变成后缀表达式：
在将中缀表达式变成后缀表达式的时候会用到堆栈，因此首先需要初始化一个堆栈。又由于逻辑变元可能是字符也可能是字符串，所以它又不同于将单字符的逻辑变元的中缀表达式变成后缀表达式。我的设计是这样的，我将中缀表达式变成后缀表达式的过程分成了两部：化简（将一维的复杂的中缀表达式变成一维的简单的中缀表达式，并将字符串逻辑变元存放在二维数组中），转化（将化简后的中缀表达式变成后缀表达式）。
（1）化简：先用一个字符数组存放输入的中缀表达式（表达式以‘#’号结束），然后将一维的中缀表达式中的字符串逻辑变元用一个字符进行标识，这样我们就可以将原来复杂的中缀表达式变成熟悉而又简单的中缀表达式，同时用二维数组存放那些字符串逻辑变元。实现的过程就是首先扫描一维中缀表达式，如果遇到逻辑符号，那么记住这个逻辑符号在数组中的相对位置用一个变量存放，然后继续扫描中缀表达式直到再次遇到逻辑符号，再一次记住它在中缀表达式中的相对位置，这两个逻辑符号之间的部分就是一个完整的逻辑变元，将这个字符串逻辑变元用一个字符代替并将这个字符串逻辑变元保存在二维数组中。这个过程的实现我把它放在change()函数中。
（2）转化：在实现该功能时，首先需要定义各符号的优先级，即：'(' 和')' 的优先级最高；'!'（逻辑非号）的优先级次之；'&'（逻辑与号）的优先级又低一级，'|'（逻辑或号）的优先级跟低；'#' （他不是逻辑符号，只是为了方便使用堆栈而设置）的优先级最低，接着将'#'压入堆栈。在这之后就是正式的转化了，其过程为：当读到的是逻辑变元时直接输出，并保存到保存后缀表达式的数组中，当读到的单词为运算符时，令x1为当前栈顶运算符的变量，x2为当前扫描到的简单中缀表达式的运算符的变量，把当前读入的单词赋予变量x2，然后比较x1和x2的优先级。若x1的优先级高于x2的优先级，将x1退栈作为后缀表达式的一个单词输出，然后接着比较新的栈顶运算符x1的优先级与x2的优先级；若x1的优先级低于x2的优先级，将x2的值进栈，然后接着读下一个单词；若x1的优先级等于x2的优先级且x1为“（”，x2为“）”，将x1退栈，然后接着读下一个单词；若x1的优先级等于x2的优先级且x1为“#”，x2为“#”，算法结束。这个过程我把它放在InToPost()函数中。
然后用后缀表达式构造出二叉树：
在这个过程中，我用到了之前所定义的存放树的堆栈。具体实现为：扫描后缀表达式，如果遇到逻辑变元然后将这个变元变成一个树节点，它的实现就是将该逻辑变元赋给树的data域，然后将它的左右子树赋为NULL，然后将这个树节点压入相应的堆栈；接着继续扫描，如果遇到的是单目运算符（非号“！”）也将它构造成一个树节点然后从堆栈里面弹出一个树形节点，将弹出的元素的作为它的左子树，右子树设置为NULL，然后将这个树节点压入相应的堆栈；如果扫描到的是双目运算符（与号“&”或者或号“|”）将它也构造成一棵树，然后将这个树节点压入相应的堆栈，然后从栈中弹出两个元素，一个作为它的左子树，一个作为它的右子树，如此重复n（n为后缀表达式的长度）次。这个过程我把它放在Maketree()
函数中。
最后打印真值表：
打印真值表也用到了前面的简单的后缀表达式，其实现的基本思想为和构造二叉树差不多，它实现了每到一个根节点就计算一个运算的值。在打印之前需要统计字符的个数，有m 个字符则要打印2^m 行，因为他有这么多情况。具体实现为：用一个字符型的数组来存放每个元素的一次取值，然后扫描后缀表达式，如果遇到逻辑变元就通过这个标识将相应的取值赋给它，然后它压入堆栈；接着继续扫描，如果遇到的是单目运算符（非号“！”）则从堆栈里面弹出一个元素，并对它进行非运算，然后又将这个运算后的值压入堆栈；如果扫描到的是双目运算符（与号“&”或者或号“|”）则从栈中弹出两个元素，并对这两个元素进行相应的运算，然后将这个运算后的值压入堆栈，如此重复n （n 为后缀表达式的长度）次。这个过程我把它放在Print()函数中。
其中第一，二过程的流程图描述分别为：
Y es
Y es
No No
No Y es Y es
No
开始
扫描后缀表达式
扫描到x2是逻辑变元？
输出
取栈顶元素x1
栈顶元素的优先级高？
出栈
进栈
小于
x1为'(',x2we 为')' x1,x2都为'#'
结束
扫描后缀表达式
扫描到的是逻辑变元？
构造成树节点并进栈
单目运算符
双目运算符
构造成树节点从栈中弹出一个元素作为其左子树
构造成树节点从栈中弹出两个元素作为其左右子树
进栈
进栈
2.2 设计表示：
<1>, 函数调用关系及函数说明：
change()函数原型为：
void change(char prefixStr1[],char prefixStr[],int length[],char store[][10],int* row,int* k ) 该函数含有有六个参数，其中 prefixStr1[]为用户输入的中缀表达式，prefixStr[]为即将转化成为的简单中缀表达式，length[]为二维数组中存放的各个字符串的的长度store[][10]用来存放中缀表达式中的逻辑变元，row 就是逻辑变元的个数，k 简化后的中缀表达式的长度。该函数的功能就是将复杂的中缀表达式变成简单的中缀表达式。
InT oPost()函数原型为：
void InToPost(char prefixStr[],char postfixStr[],SeqStack* myStack,int* n,int k)
该函数函数有五个参数 prefixStr[]为中缀表达式，postfixStr[]为简化后的后缀表达式，myStack 为在转化过程中用到的堆栈，n 为后缀表达式的字符长度，k 为中缀表达式的字符长度。该函数的功能就是将简单的中缀表达式变成简单的后缀表达式。
Maketree()函数原型为：
void Maketree(BiTreeNode *root,TreeStack* myTree,char postfixStr[],int n)
该函数共有四个参数，其中root 为所建立的树的根节点，myTree 是在构造树时所用到的堆栈，另外两个参数和前面的同名参数具有相同意义。这个函数的功能就是将简单的中缀表达式变成简单的后缀表达式。
Precede()函数原型为：
DataType Precede(DataType x1,DataType x2)
该函数有两个参数，返回值类型为DataType 型，其中x1和x2就是要进行优先级比较的两个两个字符。x1为栈顶元素，x2为扫描到的元素。该函数的功能就是比较x1和x2的优先级并将比较结果返回给调用函数。
main()
change() InToPost()
Print()
Maketree() Precede()
StackTop() StackPop() StackPush()
StackPush1() StackPop1
StackPop() StackPush()
Print()函数原型为：
void Print(char postfixStr[],char store[][10],int length[],int row,int n,SeqStack* myStack) 该函数有六个参数，其中myStack是在输出真值表过程中要用到的堆栈，其余的参数和前面介绍的函数中的同名参数具有相同的意义。该函数的功能就是打印真值表。
<2> 函数接口说明：
函数的调用关系在上面的图中已经显示出来了，整个程序就是由一些子函数的集合，他们之间按所要实现的功能不同而调用不同的函数。在这些函数中除主函数外，其它函数的级别相同。
2.3详细设计：
（1），定义所需要的结构体，前面已经介绍了；
（2），我将中缀表达式变成后缀表达式的过程分成了两部：化简（将一维的复杂的中缀表达式变成一维的简单的中缀表达式，并将字符串逻辑变元存放在二维数组中），转化（将化简后的中缀表达式变成后缀表达式）。其中化简部分将要用伪代码描述为
while(prefixStr1[m]!='#')
{
扫描中缀表达式
while(prefixStr1[m]不为运算'符)
{
继续扫描，直到扫描到运算符;
}
扫描到运算符后
{
构造简化的中缀表达式;
得到这个字符串的长度;
将这个字符串存放在store[][10]中;
}
}
转化部分用伪代码描述为：
循环扫描中缀表达式
{
if(扫描到逻辑变元)
保存到后缀表达式中；
else{
StackTop(myStack,&x);
res=Precede(x,扫描到的运算符);
if(res=='>') x退栈；
if(res=='<') 扫描到的运算符进栈；
if(res=='=' && x=='(') 退栈
if(res=='=' && x=='#') 结束；
}
}
（3），构造二叉树，其思想就是将逻辑变元作为叶子节点，运算符作为根节点，用堆栈实现，用伪代码简单描述为：
循环扫描后缀表达式{
if(扫描到逻辑变元')
讲逻辑变元进栈；
else
{
if('扫描到双目运算符){
StackPop1(myTree,&x1);
StackPop1(myTree,&x2);
将x1，x2作为它的左右子树；
StackPush1(myTree,p);}
else
{
StackPop1(myTree,&x1);
将x1作为它的左子树，又子树为空；
StackPush1(myTree,p);
}
}
StackPop1(myTree,&x1);
root->leftChild=x1;}
（4），打印二叉树，其基本思想就是每到一个根节点就计算一个值，如此重复，直到总根节点，用伪代码简单描述为：
循环赋值{
if(扫描到逻辑变元')
{
赋值进栈；
}
else
{
if(扫描到双目运算符)
{
从栈中弹出两数
对两数进行相应的运算;
将运算结构进栈；;
}
else
{
从栈中弹出两数;
对两数进行非运算;
将运算结构进栈;
}
每循环一次输出一个结构;
}
3，调试分析：
<1>，调试过程中遇到的问题与解决方案：
这个题我个人觉的是这几个中最麻烦的一个，因为它有几个难点去分析与实现：
首先就是中缀表达式中的逻辑变元不是单个字符而是一些字符串，这样在将中缀表达式转化成后缀表达式的时候就会比较麻烦，起初我也不太清楚该怎么处理他，后来经过一番分析与调试后，我觉得用二维数组存放比较好，那样实现起来就会比较简单，当然虽然这么说，其实实现起来也还是有一定的困难的，比如怎样去找到一个完整的字符串逻辑变元，找到之后又怎样存放等等。
然后再就是构造树，在构造树时要用到堆栈，但是前面用到的堆栈的数据类型和此时用到的又有很大的差别，在此时又要想到再换一个类型的堆栈，同时在构造树的时候有要找到合适的算法……
最后就是真值表的打印，对这一模块的实现最容易想到的就是有几个逻辑变元就进行几次循环，每一重循环对应着一个变量的取值。但是经过分析这显然是行不通的，因为在事先我们并不知道会有多少个变元。最后我用到的方法就是那种最原始的方法，用一重循环去实现，每重循环都会有一个值，将这个值反复进行对2取余和对2进行整除，将取余后的值赋给相应的变元。这样总共循环2的变元素的n次方次即可。
当然在完成这个程序时还遇到其它的很多的问题，这里就不多进行列出了，最后我在声明一下这个程序的一个缺陷，他在进行逻辑变元数统计的时候没有对两个相同的变元进行识别。
<2>，算法的时空复杂度分析：
本次程序的完成除书上的那些头文件外，其它的算法都是自己提供，对于我自己写的那些函数，比如change()函数，InToPost()函数，Print()函数，Maketree()函数他们的时间复杂度均为o(n),而对于change()函数其空间复杂度为o(1),其它的三个函数，由于他们都用到了堆栈这个数据结构他们的空间复杂度都是o(n).
4，用户手册：
本程序经过编译，连接后，运行时只需要用户输入一个中缀表达式，也即用户想要进行的逻辑运算的表达式。这里有三点需要要提醒用户：
1，在输入表达式时“&”表示逻辑与；“|”号表示逻辑或，“！”表示逻辑非。在输入中缀表达式后程序将自动执行并输出结构，用户不需进行干预；
2，在本程序的书写中我定义了一个最多的逻辑变元的数量为十个，用户在输入表达式时应该注意输入，不要超过这个界限。
3，用户在输入完所要进行运算的表达式后要记得以“#”号结尾，“#”号是判断输入结束的标识，如果用户没有以“#”号结束，那么程序的运行结果将会出错，这时用户必须重新对程序进行编译连接，然后按照要求输入表达式。
5，测试数据及测试结果：
由于用户的不同输入将对应着不同的结果，这里我仅随便输入一个逻辑表达式以供用户参考：
请输入表达式(以#号结束)：!aaa&(bb|cd1)&wq|d#
将中缀表达式变成后缀表达式为：
aaa ! bb cd1 | & wq & d |
打印构造的二叉树为：
---d
---|
---wq
---&
---!
---aaa
---&
---cd1
---|
---bb
二叉树的后序遍历为：
bb cd1 | aaa ! & wq & d |
打印真值表为：
aaa bb cd1 wq d 运算结果
0 0 0 0 0 0
1 0 0 0 0 0
0 1 0 0 0 0
1 1 0 0 0 0
0 0 1 0 0 0
1 0 1 0 0 0
0 1 1 0 0 0
1 1 1 0 0 0
0 0 0 1 0 0
1 0 0 1 0 0
0 1 0 1 0 1
1 1 0 1 0 0
0 0 1 1 0 1
1 0 1 1 0 0
0 1 1 1 0 1
1 1 1 1 0 0
0 0 0 0 1 1
1 0 0 0 1 1
0 1 0 0 1 1
1 1 0 0 1 1
0 0 1 0 1 1
1 0 1 0 1 1
0 1 1 0 1 1
1 1 1 0 1 1
0 0 0 1 1 1
1 0 0 1 1 1
0 1 0 1 1 1
1 1 0 1 1 1
0 0 1 1 1 1
1 0 1 1 1 1
0 1 1 1 1 1
1 1 1 1 1 1
6，源程序清单：
caculate.cpp //程序源文件
BiTree.h //树的相关操作的头文件
BiTreeTraverse.h //树的遍历的头文件
caozuo.h //自己提供的为实现所要求的功能而添加的头文件Compare.h //比较运算符优先级的头文件
SeqStack.h //线性堆栈的有关操作的头文件
TreeStack.h //为构造树而用到的头文件
//caculate.cpp 程序源文件
#include
#include
#include
#define MaxStackSize 50
#include "SeqStack.h"
#include "BiTree.h"
#include "TreeStack.h"
#include "Compare.h"
#include "BiTreeTraverse.h"
#include "caozuo.h"
///////////////////////////////////////////////////////////////////////////////////////////////
void main()
{
int i,j,n=0,k=0,row=0;
SeqStack myStack;
char prefixStr[100],prefixStr1[100];
char postfixStr[100];
char store[10][10];
int length[10],index=0;
BiTreeNode *root;
TreeStack myTree;
StackInitiate(&myStack);
StackPush(&myStack,'#');
printf("请输入表达式(以#号结束)：");
scanf("%s",prefixStr1);
change(prefixStr1,prefixStr,length,store,&row,&k); //k是中缀表达式的字符长度InToPost(prefixStr,postfixStr,&myStack,&n,k);
////////////////////////////////////////////////////////////////////
printf("将中缀表达式变成后缀表达式为：\n");
for(i=0;i if(postfixStr[i]>='A' && postfixStr[i]<='Z') { for(j=0;j { printf("%c",store[index][j]); } index++; printf(" "); } else { printf("%c ",postfixStr[i]); } } printf("\n"); ///////////////////////////////////////////////////////////////////////构造二叉树 printf("\n打印构造的二叉树为：\n"); StackInitiate1(&myTree); TreeInitiate(&root); Maketree(root,&myTree,postfixStr,n); PrintBiTree(root,0,store,length); //凹入打印二叉树 printf("二叉树的后序遍历为：\n"); PostOrder(root->leftChild,store,length); printf("\n"); /////////////////////////////////////////////////////打印真值表 printf("\n打印真值表为：\n"); Print(postfixStr,store,length,row,n,&myStack); } //caozuo.h 头文件 void change(char prefixStr1[],char prefixStr[],int length[],char store[][10],int* row,int* k ) { int j,t,m=0; char ch='A'; while(prefixStr1[m]!='#') { j=m; while(prefixStr1[m]!='&' && prefixStr1[m]!='|' && prefixStr1[m]!='!' && prefixStr1[m]!='(' && prefixStr1[m]!=')' && prefixStr1[m]!='#') { m++; } if(m!=j) { prefixStr[(*k)++]=ch; ch+=1; for(t=j;t { length[*row]=m-j; store[*row][t-j]=prefixStr1[t]; } (*row)++; } prefixStr[(*k)++]=prefixStr1[m]; m++; if(prefixStr1[m]=='&' || prefixStr1[m]=='|' || prefixStr1[m]=='!' || prefixStr1[m]=='(' || prefixStr1[m]==')' || prefixStr1[m]=='#') { prefixStr[(*k)++]=prefixStr1[m]; } else m--; if(prefixStr1[m]!='#') { m++; } else { break; } } } //////////////////////////////////////////////////////////////////////// void InToPost(char prefixStr[],char postfixStr[],SeqStack* myStack,int* n,int k) { int i; DataType res,x; for(i=0;i { if(prefixStr[i]>='A' && prefixStr[i]<='Z') { postfixStr[(*n)++]=prefixStr[i]; } else { StackTop(myStack,&x); res=Precede(x,prefixStr[i]); if(res=='>') { while(res=='>') { StackPop(myStack,&x); postfixStr[(*n)++]=x; StackTop(myStack,&x); res=Precede(x,prefixStr[i]); } } if(res=='<') { StackPush(myStack,prefixStr[i]); } if(res=='=' && x=='(') { StackPop(myStack,&x); } if(res=='=' && x=='#') { break; } } } } /////////////////////////////////////// void Print(char postfixStr[],char store[][10],int length[],int row,int n,SeqStack* myStack) { char *ptr; DataType x,v1,v2; int i,j,t,total=1; int value,value1,value2,value3; for(i=0;i { for(j=0;j { printf("%c",store[i][j]); } printf(" "); } printf("运算结果"); printf("\n"); for(i=0;i { total*=2; } ptr=(char* )malloc(sizeof(char)*row); for(i=0;i { t=i; for(j=0;j { ptr[j]=t%2+48; printf("%c ",ptr[j]); t=t/2; } for(j=0;j { if(postfixStr[j]>='A' && postfixStr[j]<='Z') { value=postfixStr[j]-'A'; StackPush(myStack,ptr[value]); } else { if(postfixStr[j]!='!') { StackPop(myStack,&v1); value1=v1-48; StackPop(myStack,&v2); value2=v2-48; switch(postfixStr[j]) { case '&': value3=value1&&value2; break; case '|': value3=value1||value2; break; } x=value3+48; StackPush(myStack,x); } else { StackPop(myStack,&v1); value1=v1-48; value3=!value1; x=value3+48; StackPush(myStack,x); } } } StackPop(myStack,&x); printf(" %c",x); printf("\n"); } } //////////////////////////////////////////// void Maketree(BiTreeNode *root,TreeStack* myTree,char postfixStr[],int n) { int i; BiTreeNode *p,*x1,*x2; for(i=0;i { if(postfixStr[i]>='A' && postfixStr[i]<='Z') { p=(BiTreeNode *)malloc(sizeof(BiTreeNode)); p->data=postfixStr[i]; p->leftChild=NULL; p->rightChild=NULL; StackPush1(myTree,p); } else { p=(BiTreeNode *)malloc(sizeof(BiTreeNode)); x1=(BiTreeNode *)malloc(sizeof(BiTreeNode)); x2=(BiTreeNode *)malloc(sizeof(BiTreeNode)); if(postfixStr[i]!='!') { StackPop1(myTree,&x1); StackPop1(myTree,&x2); p->data=postfixStr[i]; if(x1->data>='A' && x1->data<='Z') { p->leftChild=x2; p->rightChild=x1; } else { p->leftChild=x1; p->rightChild=x2; } StackPush1(myTree,p); } else { StackPop1(myTree,&x1); p->data=postfixStr[i]; p->leftChild=x1; p->rightChild=NULL; StackPush1(myTree,p); } } } StackPop1(myTree,&x1); root->leftChild=x1; } //Compare.h 头文件 DataType Precede(DataType x1,DataType x2) { DataType result; switch(x2) { case '|': { if(x1=='('||x1=='#') result='<'; else result='>'; break; } case '&': { if(x1=='&' ||x1==')' ||x1=='!') result='>'; else result='<'; break; } case '!': { if(x1==')' ||x1=='!') result='>'; else result='<'; break; } case '(': { if(x1==')') { printf("ERROR1\n"); exit(0); } else result='<'; break; } case ')': { switch(x1) { case '(': { result='='; break; } case '#': { printf("ERROR2\n"); exit(0) ; } default: result='>'; } break; } case '#': { switch(x1) { case '#':{result='='; break;} case '(':{printf("ERROR3\n"); exit(0);} default: result='>'; } } } return result; } //TreeStack.h 头文件 typedef struct { BiTreeNode *stack [MaxStackSize]; int top; /* 当前栈的表长*/ } TreeStack; void StackInitiate1 (TreeStack *S) { S->top=0; } int StackPush1 (TreeStack * S, BiTreeNode *x) { if (S->top>=MaxStackSize) return 0;//判栈满否，栈满异常退出else { S->stack[S->top]=x; S->top++; return 1; } } int StackPop1 (TreeStack * S, BiTreeNode **x) { if (S->top<=0)//判栈非空否，栈空异常退出return 0; else { S->top--; *x=S->stack[S->top]; return 1; } } 题号：第一题 题目：电梯模拟 1，需求分析： 计算命题演算公式的真值 所谓命题演算公式是指由逻辑变量（其值为TRUE或FALSE）和逻辑运算符∧（AND）、∨（OR）和┐（NOT）按一定规则所组成的公式（蕴含之类的运算可以用∧、∨和┐来表示）。公式运算的先后顺序为┐、∧、∨，而括号（）可以改变优先次序。已知一个命题演算公式及各变量的值，要求设计一个程序来计算公式的真值。 要求： （1）利用二叉树来计算公式的真值。首先利用堆栈将中缀形式的公式变为后缀形式；然后根据后缀形式，从叶结点开始构造相应的二叉树；最后按后序遍历该树，求各子树之值，即每到达一个结点，其子树之值已经计算出来，当到达根结点时，求得的值就是公式之真值。 （2）逻辑变元的标识符不限于单字母，而可以是任意长的字母数字串。 （3）根据用户的要求显示表达式的真值表。 2，设计： 2.1 设计思想： <1>，数据结构设计： (1) 线性堆栈1的数据结构定义 typedef struct { DataType stack [MaxStackSize]; int top; /* 当前栈的表长*/ } SeqStack; 用线性堆栈主要是用来存储输入的字符，它的作用就是将中缀表达式变成后缀表达式。 (2) 线性堆栈2的数据结构定义 typedef struct { BiTreeNode *stack [MaxStackSize]; int top; /* 当前栈的表长*/ } TreeStack; 这个堆栈和上面的堆栈的唯一不同就是它们存储的数据的类型不同，此堆栈存储的是树节点，它的作用是将后缀表达式构成一棵二叉树。 (3)树节点数据结构定义 typedef struct Node { DataType data; struct Node *leftChild; struct Node *rightChild; }BiTreeNode; <2>算法设计详细思路如下： 首先实现将中缀表达式变成后缀表达式： 在将中缀表达式变成后缀表达式的时候会用到堆栈，因此首先需要初始化一个堆栈。又由于逻辑变元可能是字符也可能是字符串，所以它又不同于将单字符的逻辑变元的中缀表达式变成后缀表达式。我的设计是这样的，我将中缀表达式变成后缀表达式的过程分成了两部：化简（将一维的复杂的中缀表达式变成一维的简单的中缀表达式，并将字符串逻辑变元存放在二维数组中），转化（将化简后的中缀表达式变成后缀表达式）。 （1）化简：先用一个字符数组存放输入的中缀表达式（表达式以‘#’号结束），然后将一维的中缀表达式中的字符串逻辑变元用一个字符进行标识，这样我们就可以将原来复杂的中缀表达式变成熟悉而又简单的中缀表达式，同时用二维数组存放那些字符串逻辑变元。实现的过程就是首先扫描一维中缀表达式，如果遇到逻辑符号，那么记住这个逻辑符号在数组中的相对位置用一个变量存放，然后继续扫描中缀表达式直到再次遇到逻辑符号，再一次记住它在中缀表达式中的相对位置，这两个逻辑符号之间的部分就是一个完整的逻辑变元，将这个字符串逻辑变元用一个字符代替并将这个字符串逻辑变元保存在二维数组中。这个过程的实现我把它放在change()函数中。 （2）转化：在实现该功能时，首先需要定义各符号的优先级，即：'(' 和')' 的优先级最高；'!'（逻辑非号）的优先级次之；'&'（逻辑与号）的优先级又低一级，'|'（逻辑或号）的优先级跟低；'#' （他不是逻辑符号，只是为了方便使用堆栈而设置）的优先级最低，接着将'#'压入堆栈。在这之后就是正式的转化了，其过程为：当读到的是逻辑变元时直接输出，并保存到保存后缀表达式的数组中，当读到的单词为运算符时，令x1为当前栈顶运算符的变量，x2为当前扫描到的简单中缀表达式的运算符的变量，把当前读入的单词赋予变量x2，然后比较x1和x2的优先级。若x1的优先级高于x2的优先级，将x1退栈作为后缀表达式的一个单词输出，然后接着比较新的栈顶运算符x1的优先级与x2的优先级；若x1的优先级低于x2的优先级，将x2的值进栈，然后接着读下一个单词；若x1的优先级等于x2的优先级且x1为“（”，x2为“）”，将x1退栈，然后接着读下一个单词；若x1的优先级等于x2的优先级且x1为“#”，x2为“#”，算法结束。这个过程我把它放在InToPost()函数中。 然后用后缀表达式构造出二叉树： 在这个过程中，我用到了之前所定义的存放树的堆栈。具体实现为：扫描后缀表达式，如果遇到逻辑变元然后将这个变元变成一个树节点，它的实现就是将该逻辑变元赋给树的data域，然后将它的左右子树赋为NULL，然后将这个树节点压入相应的堆栈；接着继续扫描，如果遇到的是单目运算符（非号“！”）也将它构造成一个树节点然后从堆栈里面弹出一个树形节点，将弹出的元素的作为它的左子树，右子树设置为NULL，然后将这个树节点压入相应的堆栈；如果扫描到的是双目运算符（与号“&”或者或号“|”）将它也构造成一棵树，然后将这个树节点压入相应的堆栈，然后从栈中弹出两个元素，一个作为它的左子树，一个作为它的右子树，如此重复n（n为后缀表达式的长度）次。这个过程我把它放在Maketree()函数中。 第一章逻辑推理 在数学竞赛中，有一类问题似乎不像数学题，这类问题没有或很少给出数量或数量关系，也不出现任何图形。解答这类问题没有什么现成的公式可用，甚至不需要什么复杂计算。也有的问题，似乎像算术或几何问题，但解决它却很少用到算术和集合的知识，而是用逻辑推理的知识来解答。这类问题称为逻辑推理问题。逻辑推理是运用已知若干判断去获得一个新判断的思维方法。在推理过程中，常常需要否定一些错误的可能性，去获得正确的结论。 解决这类问题常用的方法有：直接法；假设法；排除法；图解法；列表法和枚举法等。 逻辑推理问题的解决，需要我们深入地理解条件和结论，分析关键所在，找到突破口，进行合情合理的推理，最后做出正确的判断。 推理的过程，必须要有充足的理由和充分的依据。论证的才能不是天生的，而是在不断的实践活动中逐渐锻炼、培养出来的。 一、直接法 例 1 张、王、李三个工人，在甲、乙、丙三个工厂里分别当车工、钳工和电工，已知：（1）张不在甲厂；（2）王不在乙厂；（3）在甲厂的不是钳工；（4）在乙厂的是车工；（5）王不是电工，这三个人分别在哪个厂？干什么工作？ 【分析与解】此题可用直接法解答，即直接从特殊条件出发，再结合其他条件往下推，直到推出结论为止。 由条件（5）可知，王不是电工，那么王必是车工或钳工；由条件（2）可知，王不在乙厂，那么王必在甲厂或丙厂；又由条件（4）可知，在乙厂的是车工，所以王只能是钳工；又因为甲厂的不是钳工，则王必是丙厂的钳工；张不在甲厂，必在乙厂或丙厂，而王在丙厂，则张必在乙厂，是乙厂的车工，剩下的李是甲厂的电工。 所以，张是乙厂的车工，王是丙厂的钳工，李是甲厂的电工。 例2 A、B、C、D、E五人参加乒乓球比赛，每两人都要赛一场，并且只赛一场，规定胜者得2分，负者得0分。现在知道比赛结果是：A和B并列第一名；C 是第三名，D和E并列第四名，求C得多少分？ 【分析与解】我们从A和B并列第一名，D和E并列第四名的已知条件直接 名 称 逻 辑 表 达 式 逻 辑 符 号 真 值 表 逻辑运算规则 与 门 AB F = A 0 0 1 1 0 1 0 1 有0得0 全1得1 B F 0 0 0 1 或 门 B A F += A 0 0 1 1 0 1 0 1 有1得1 全0得0 B F 0 1 1 1 非 门 A F = A 0 1 有0得1 有1得0 F 1 0 与 非 门 AB F = A 0 0 1 1 0 1 0 1 有0得1 全1得0 B F 1 1 1 0 或 非 门 B A F += A 0 0 1 1 0 1 0 1 有1得0 全0得1 B F 1 0 0 0 与 或 非 门 CD AB F += A 0 0 (1) 0 0 (1) 0 0 … 1 0 1 (1) AB 或CD 有一组或两组全是 1结果得0 其余输出全得1 B C D F 1 1 0 异 或 门 B A F ⊕= B A B A += A 0 0 1 1 0 1 0 1 不同得1 相同得0 B F 0 1 1 0 同或门A F=⊙B AB B A+ =A0 0 1 1 0 1 0 1 不同得0 相同得1 B F 1 0 0 1 色环电阻的表示 颜 色 黑棕红橙黄绿蓝紫灰白金银无 有 效 数 字 0123456789-1-2-3 乘 数 10010110210310410510610710810910-110-2 精确度±1 ﹪ ±2 ﹪ ±﹪± ﹪ ± ﹪ ±5 ﹪ ± 10 ﹪ ± 20 ﹪ 注：四色环电阻：1、2环表示是有效数照写，3环表示是乘数（就是要乘与这个乘数），4环表示是精确度。五色环电阻：1、2、3环表示是有效数照写，4环表示是乘数（就是要乘与这个乘数），5环表示是精确度。 逻辑命题与推理 必然性推理（演绎推理）：对当关系推理、三段论、复合命题推理、关系推理和模态推理 可能性推理：归纳推理（枚举归纳、科学归纳）、类比推理 命题 直言命题的种类：（AEIOae） ⑴全称肯定命题：所有S是P（SAP） ⑵全称否定命题：所有S不是P（SEP） ⑶特称肯定命题：有的S是P（SIP） ⑷特称否定命题：有的S不是P（SOP） ⑸单称肯定命题：某个S是P（SaP） ⑹单称否定命题：某个S不是P（SeP） 直言命题间的真假对当关系： 矛盾关系、（上）反对关系、（下）反对关系、从属关系 矛盾关系：具有矛盾关系的两个命题之间不能同真同假。主要有三组： SAP与SOP之间。“所有同学考试都几个了”与“有些同学考试不及格” SEP与SIP之间。“所有同学考试不及格”与“有些同学考试及格” SaP与SeP之间。“张三考试及格”与“张三考试不及格” 上反对关系：具有上反对关系的两个命题不能同真（必有一假），但是可以同假。即要么一个是假的，要么都是假的。存在于SAP与SEP、SAP与SeP、SEP与SaP之间。 下反对关系：具有下反对关系的两个命题不能同假（必有一真），但是可以同真。即要么一个是真的，要么两个都是真的。存在于SIP与SOP、SeP与SIP、SaP与SOP之间。 从属关系（可推出关系）：存在于SAP与SIP、SEP与SOP、SAP与SaP、SEP与SeP、SaP与SIP、SeP与SOP 六种直言命题之间存在的对当关系可以用一个六角图形来表示，“逻辑方阵图” SAP SEP SaP SeP SIP SOP 直言命题的真假包含关系 全同关系、真包含于关系、真包含关系、交叉关系、全异关系 复合命题：负命题、联言命题、选言命题、假言命题 负命题的一般公式：并非P 联言命题公式：p并且q “并且、…和…、既…又…、不但…而且、虽然…但是…” 选言命题：相容的选言命题、不相容的选言命题 相容的选言命题公式：p或者q“或、或者…或者…、也许…也许…、可能…可能…” 【一个相容的选言命题是真的，只有一个选言支是真的即可。只有当全部选言支都假时，相容的选言命题才是假的】不相容选言命题公式：要么p要么q “要么…要么…、不是…就是…、或者…或者…二者必居其一、或者…或者…二者不可兼得” 【一个不相容的选言命题是真的，有且只有一个选言支是真的。当选言支全真或全假时，此命题为假】 假言命题：充分条件假言命题、必要条件假言命题、充要条件假言命题 充分条件假言命题公式：如果p，那么q“如果…就…、有…就有…、倘若…就…、哪里有…哪里有…、一旦…就…、假若…、只要…就…” 【有前件必然有后件。如果有前件却没有后件，这个充分条件假言命题就是假的。因此，对于一个充分条件的假言命题来说，只有当其前件真而后件假时，命题才假。】 必要条件假言命题公式：只有p，才q “没有…就没有…、不…不…、除非…不…、除非…才…” 【没有前件必然没有后件。如果没有前件也有后件，这个必要假言命题为假。对于一个必要条件的假言命题来说，只有当其前件假而后件真时，命题才假。】 充要条件假言命题公式：当且仅当p，才q 【有前件必然有后件，没有前件必然没有后件。充要条件假言命题在前件与后件等值即前件真并且后件真，或者前件假并且后件假时，命题为真，在前件与后件不等值即前真后假，或前假后真时，命题为假】 充分条件与必要条件之间可以相互转化： 判断推理常用公式 一、逻辑判断 并非(A或B)=非A且非B ?真假判断题型解题技巧 六种关系 矛盾关系(主体相同的两句话,必一真一假) ①某个S就是P,某个S不就是P; ②所有S都就是P,有的S不就是P;③所有的S都不就是P,有的S就是P; ④P且Q,非P或非Q。 ⑤P或Q,非P且非Q⑥如果P→Q,P→非Q(如果天下雨,路就滑) 反对关系 ⑤有的S就是P,有的S不就是P(至少有一真);⑥所有S都就是P,所有S都不就是P(至少有一假)。 包容关系 例: 所有A→B 所有老师都会英语A 校长会英语B ①一直前假如果题目问只有一个就是真的 分析,如果A真,B截然为真。与问题说的只有一真矛盾,哪么A一定为假 ②一假后真如果题目问只有一个就是假的 分析,如果B假,A截然为假。与问题说的只有一假矛盾,哪么B一定为真 二、翻译推理 1、单句判断 ①所有(凡就是)S都就是P 翻译S →P ②所有(凡就是)S都不就是P 翻译S →—P ③没有S就是P (所有S不就是P) 翻译P →—S 见没有改所有 ④没有S不就是P (所有S就是P) 翻译S →P ⑤不就是S都就是P 翻译—S →P ⑥不就是S都不就是P 翻译—S →—P 2、否定关系 1、并非所有A都就是B 等价于有的A不就是B (并非所有换成有的,就是换不就是) 2、并非有的A就是B 等价于所有A都不就是B (并非有的换成所有,就是换成不就是) 3、等价关系 1、所有的A都不就是B 等价于所有的B都不就是A 2、有的A就是B 等价于有的B就是啊 五个解题步骤 ①符号化;②找关系(六种关系);③推知其余项真假;④根据其余项真假,得出真实情况;⑤带回“矛盾或反对”项,判断其真假。 排列组合题型 1、选项信息充分,运用排除法, 2、选项不处分,找推理起点:信息最大优先,特殊信息优先 ■削弱题型方法: １、否因削弱 已知因果推理主线:因→果 否因削弱:强调原因不成立或起不到作用。 2、她因 已知推理主线:因→果 她因削弱:强调存在别的原因会导致该结果,或者导致不了该结果。 3、反例 已知推理主线:因→果 反例削弱:举出一个反例,即满足了“因”却没有得到所说的“果”。 4、因果倒置 已知推理主线:A、B两个现象同时出现→A导致了B 因果倒置:很有可能就是B导致了A。 ■假设、支持题型方法: 1、排她因 已知推理主线:因→果 排她因:排除其她因素的干扰,或排除其她可能性,使推理更可信。 2、否因否果 已知推理主线:因→果 否因否果:非因→非果,会支持“因→果” 3、建立联系 已知推理主线:因→果 建立联系:因果之间有跳跃,唯有建立联系才可行。 4、推论可行 已知推理主线:因→果 推论可行:因果之间有漏洞,需加前提才可行。 ■解释题型关键: 解题技巧:抓住需要解释的关键信息。 ■归纳题型技巧: 1、四项原则:从弱原则,整体原则,就近原则、协调原则 1.7 推 理 理 论 从假设前提利用推理规则得到其他命题，即形成结论的过程就是推理，这是研究逻辑的主要目标。 1.7.1 蕴含与论证 1．推理的含义与形式 [定义1-22] 当且仅当p →q 为永真式时，称为p 蕴含q （logical implication ），记作p q ?，或p q 。此时，称p 为前提，q 为p 的有效结论或逻辑结论，也称为q 可由p 逻辑推出。得出此逻辑关系的过程称为论证。 [辨析] 由于仅在p 为1而q 为0时公式p q →为0，可见，p q →永真意味着不可能存在前件p 为1而后件q 为0的情况，或者说，若p q ?，则只要前件p 为1，后件q 也一定为1。因此，p q ?也称为“永真蕴含” ，即p 永真蕴含q 。 [延伸] 通常，定理（theorem ）被解释为“经过受逻辑限制的证明为真的陈述”，就是指对“在一定条件成立的情况下必然产生某个（些）结论”的陈述。因此，定理证明也就是对蕴含关系的论证。当然，通常只有重要或有趣的陈述才被视为定理。 所有逻辑推理的实质就是证明p q ?，也就是证明p q →为永真式。例如，以下是一个简单的初等数学证明题目： 已知a 、b 、c 为实数，且22a b bc -=，0c ≠，则有2/(/1)a c b b c =+。 如果记 p ：22a b bc -=，q ：0c ≠，r ：2/(/1)a c b b c =+ 则上述论证要求可描述为： p q r ∧? 证明的目的就是说明：若前提p q ∧正确，则结论r 也正确，即证明p q r ∧→为永真式。 通常的逻辑推理问题都会由一组前提来推断一个逻辑结论，此时的多个前提可写成合取式12n H H H ∧∧∧ ，或写成用逗号分隔的命题序列H 1, H 2, ..., H n ，即论证要求可写作： 12n H H H C ∧∧∧? ，或12,...,n H H H C ?，，或 12n H H H C ∧∧∧ ，或12,...,,n H H H C 可见，论证A C 、A C ?或A C →是永真式都是同义的，且前提也可以用集合表示，如： 12{,..,},.n H H H C 在数学上，总是要求前提为真，从而推导出有效的结论，并不需要研究从假的前提能得到什么结论，且推理形式与前提的排列次序无关。尽管由前提A 到结论C 的推理一般记作A C ，如 四计算命题演算公式的真值 一．实验题目 所谓命题演算公式是指由逻辑变量（其值为TRUE或FALSE）和逻辑运算符∧（AND）、∨（OR）和┐（NOT）按一定规则所组成的公式（蕴含之类的运算可以用∧、∨和┐来表示）。公式运算的先后顺序为┐、∧、∨，而括号（）可以改变优先次序。已知一个命题演算公式及各变量的值，要求设计一个程序来计算公式的真值。 要求： （1）利用二叉树来计算公式的真值。首先利用堆栈将中缀形式的公式变为后缀形式；然后根据后缀形式，从叶结点开始构造相应的二叉树；最后按后序遍历该树，求各子树之值，即每到达一个结点，其子树之值已经计算出来，当到达根结点时，求得的值就是公式之真值。 （2）逻辑变元的标识符不限于单字母，而可以是任意长的字母数字串。 （3）根据用户的要求显示表达式的真值表。 二．实验设计 1. 设计思想 （1）数据结构设计 a 建立一个链式堆栈，实现括号的匹配问题。 b建立一个顺序堆栈，来实现中缀转后缀并实现二叉树的打印。 （2）算法设计 a.括号匹配 b中缀转后缀 c打印二叉树和真值表 2. 设计表示 自定义和调用的函数如下所示： #include"" #include"" #include<> #include<> #include<> #include<> #include<> 函数说明如下 SeqStack1; /*定义一个堆栈SeqStack1*/ void StackInitiate1(SeqStack1 *S) /*初始化堆栈1，栈底为‘#’*/ void StackPush1(SeqStack1 *S,DataType x) /*将元素压入堆栈1*/ void StackPop1(SeqStack1 *S,DataType *x) /*弹出堆栈1的栈顶元素*/ int StackTop1(SeqStack1 S,DataType *d) /*取堆栈1的栈顶元素*/ SeqStack2; /*定义一个顺序堆栈SeqStack2*/ void StackInitiate2(SeqStack2 *S) /*初始化堆栈2*/ BiTreeNode * StackPop2(SeqStack2 *S) /*从堆栈2中弹出栈顶元素*/ BiTreeNode; /*定义二叉树的结点*/ void Initiate(BiTreeNode **root) /*初始化树的根结点*/ void print(BiTreeNode *bt,int n) /*逆时针打印二叉树*/ void StackPush2(SeqStack2 *S,BiTreeNode *x) /*将二叉树结点压入堆栈2*/ int Convert(char a[500],char b[500][100],SeqStack1 *S,int n) /*将待求表达式转换为后缀形式*/ BiTreeNode * BuildTree(char b[500][100],int n)/*根据表达式的后缀形式，构造相应的二叉树*/ LSNode; /*定义了链式堆栈用于下面检测表达式的括号匹配*/ void StackInitiate(LSNode** head) /*初始化堆栈*/ int StackNotEmpty(LSNode* head) /*检测堆栈是否为空的函数*/ int StackPush(LSNode* head,DataType x) /*将元素入栈*/ 逻辑判断推理中常用的 逻辑公式 Document serial number【UU89WT-UU98YT-UU8CB-UUUT-UUT108】 逻辑命题与推理 必然性推理（演绎推理）：对当关系推理、三段论、复合命题推理、关系推理和模态推理 可能性推理：归纳推理（枚举归纳、科学归纳）、类比推理 命题 直言命题的种类：（AEIOae） ⑴全称肯定命题：所有S是P（SAP） ⑵全称否定命题：所有S不是P（SEP） ⑶特称肯定命题：有的S是P（SIP） ⑷特称否定命题：有的S不是P（SOP） ⑸单称肯定命题：某个S是P（SaP） ⑹单称否定命题：某个S不是P（SeP） 直言命题间的真假对当关系： 矛盾关系、（上）反对关系、（下）反对关系、从属关系 矛盾关系：具有矛盾关系的两个命题之间不能同真同假。主要有三组： SAP与SOP之间。“所有同学考试都及格了”与“有些同学考试不及格” SEP与SIP之间。“所有同学考试不及格”与“有些同学考试及格” SaP与SeP之间。“张三考试及格”与“张三考试不及格” 上反对关系：具有上反对关系的两个命题不能同真（必有一假），但是可以同假。即要么一个是假的，要么都是假的。存在于SAP与SEP、SAP与SeP、SEP与SaP之间。 下反对关系：具有下反对关系的两个命题不能同假（必有一真），但是可以同真。即要么一个是真的，要么两个都是真的。存在于SIP与SOP、SeP与SIP、SaP与SOP之间。 从属关系（可推出关系）：存在于SAP与SIP、SEP与SOP、SAP与SaP、SEP与SeP、SaP与SIP、SeP与SOP 六种直言命题之间存在的对当关系可以用一个六角图形来表示，“逻辑方阵图” SAP SEP SaP SeP SIP SOP 直言命题的真假包含关系 全同关系、真包含于关系、真包含关系、交叉关系、全异关系 复合命题：负命题、联言命题、选言命题、假言命题 负命题的一般公式：并非P 联言命题公式：p并且q “并且、…和…、既…又…、不但…而且、虽然…但是…” 选言命题：相容的选言命题、不相容的选言命题 相容的选言命题公式：p或者q“或、或者…或者…、也许…也许…、可能…可能…” 【一个相容的选言命题是真的，只有一个选言支是真的即可。只有当全部选言支都假时，相容的选言命题才是假的】 不相容选言命题公式：要么p要么q . 命题逻辑 一、选择题（每题3分） 1、下列句子中哪个是命题？(C) A、你的离散数学考试通过了 吗？ B 、请系好安全带！ C、是有理数 D 、本命题是假的 2、下列句子中哪个不是命 题？(C) A、你通过了离散数学考试 B 、我俩五百年前是一家 C、我说的是真话 D 、淮海工学院是一座工厂 3、下列联接词运算不可交换的 是(C) A、B、 C 、 D 、 4、命题公 式P Q不能表述为(B) A、P或Q B 、非P每当QC、非P仅当Q D、除非P，否则Q 5、永真式的否定是(B) A、永真式 B 、永假 式 C 、可满足式 D 、以上答案均有可能 6、下列哪组赋值使命题公 式P(P Q)的真值为假(D) A、P假Q真 B、P假Q假C 、P真Q真D、P真Q假 7、下列为命题公式P (Q R)成假指派的是(B) A、100 B 、101 C 、110 D 、111 8、下列公式中为永真式的是(C) A、P(PQ) B、P (PQ) C、(PQ) Q D、(PQ)Q 9、下列公式中为非永真式的是(B) A、(P P) Q B、(P P) Q C、P(P Q) D、P(PQ) 10、下列表达式错误的是(D) A、P(PQ) P B 、P(PQ) P C、P(PQ)PQ D 、P(PQ)PQ 11、下列表达式正确的是(D) A、PPQ B、PQP C、Q (P Q) D、(PQ)Q 12、下列四个命题中真值为真的命题为(B) （1）2 2 4当且仅当3是奇数（2）2 2 4 当且仅当3不是奇数； （3）2 2 4当且仅 当3是奇数（4）2 24当且仅当3不是奇数 A、（1）与（2） B 、（1）与（4）C、（2）与（4） D 、（3）与（4） 13、设P：龙凤呈祥是成语，Q：雪是黑的，R：太阳从东方升起，则下列假命题为(A) A、P Q R B 、Q P S C、P Q R D 、Q P S 14、设P：我累，Q：我去打球，则命题：“除非我累，否则我去打球”的符号化为（ B ） A、PQ B 、P Q C、PQ D、P Q 15、设P：我听课，Q：我睡觉，则命题“我不能一边听课，一边睡觉”的符号化 为(B) A、PQ B 、P QC、PQ D、P Q 提示：(P Q) P Q 16、设P：停机；Q：语法错误；R：程序错误， 则命题“停机的原因在于语法错误或程序错误”的符号化为（ D） A、PQR B、P QR C、QRP D、QRP 17、设P：你来了；Q：他唱歌；R：你伴奏 则命题“如果你来了，那末他唱不唱歌将看你是否伴奏而的符号化为（D ） 逻辑常识（逻辑学习总体把握） 一、逻辑推理 是指由一个或几个已知的判断推导出另外一个新的判断的思维形式。一切推理都必须由前提和结论两部分组成。一般来说，作为推理依据的已知判断称为前提，所推导出的新的判断则称为结论。推理大体分为直接推理和间接推理。 （一）直接推理 只有一个前提的推理叫直接推理。 例如：有的高三学生是共产党员，所以有的共产党员是高三学生。 （二）间接推理 一般有两个或两个以上前提的推理就是间接推理。 例如：贪赃枉法的人必会受到惩罚，你们一贯贪赃枉法，所以今天你们终于受到法律的制裁和人民的惩罚。 一般说，间接推理又可以分为演绎推理、归纳推理和类比推理等三种形式。 （1）演绎推理 所谓演绎推理，是指从一般性的前提得出了特殊性的结论的推理。 例如：贪赃枉法的人是必定会受到惩罚的，你们一贯贪赃枉法，所以，你们今天是必定要受到法律的制裁、人民的惩罚的。 这里，“贪赃枉法的人是必定会受到惩罚的”是一般性前提，“你们一贯贪赃枉法”是特殊 性前提。根据这两个前提推出”你们今天是必定要受到法律的制裁和人民的惩罚的”这个 特殊性的结论。 演绎推理可分为三段论、假言推理和选言推理。 a三段论 b假言推理 c选言推理 （2）归纳推理 归纳推理是从个别到一般，即从特殊性的前提推出普遍的一般的结论的一种推理。 一般情况下，归纳推理可分为完全归纳推理、简单枚举归纳推理。 a完全归纳推理 也叫完全归纳法，是指根据某一类事物中的每一个别事物都具有某种性质，推出该类事物普遍具有这种性质的结论。 正确运用完全归纳推理，要求所列举的前提必须完全，不然推导出的结论会产生错误。 例如：在奴隶社会里文学艺术有阶级性；在封建社会里文学艺术有阶级性；在资本主义社会里文学艺术有阶级性；在社会主义社会里文学艺术有阶级性；所以，在阶级社会里，文学艺术是有阶级性的。（注：奴隶社会、封建社会、资本主义社会、社会主义社会这四种社会形态构成了整个阶级社会。） b简单枚举归纳推理 是根据同一类事物中部分事物都具有某种性质，从而推出该类事物普遍具有这种性质的结论。这是一种不完全归纳推理。但是，这种推理通常仅考察了某类事物中部分对象的性质就得出了结论，所以结论可 ljlj 逻 辑 学 论 文 数学科学学院 09级3班 吴洁琼 学号2009040288 命题逻辑中几种常见的推理证明方法 吴洁琼 哈尔滨师范大学 （黑龙江·哈尔滨 150025） 【摘 要】：命题逻辑的推理证明是《离散数学》课程的重点难点内容，其主要原因有两个： 一是内容比较抽象且方法较独特，其灵活性很大, 故很难掌握；二是题型以证明题居多, 大多数题的知识面涉及较广, 故习题较难。而命题逻辑又是数理逻辑的基础, 熟练而灵活地掌握好命题逻辑中推理证明的方法既是学习命题逻辑的重点, 又会为进一步学习谓词逻辑打下良好的基础。本文结合适当的例题讲解，总结了命题逻辑中几种常见的推理证明方法，并进行了分析和探讨,以加深学生的理解，以及知识的灵活使用。 以期在帮助学生掌握命题逻辑的推理证明方法的同时, 又能对学生进行逻辑思维能力的训练,培养学生分析问题和解决问题的能力。 【关键词】：命题逻辑；推理；证明方法 数理逻辑是《离散数学》课程的主要内容之一，它主要包括命题逻辑和谓词逻辑两大部分, 而命题逻辑又是谓词逻辑的基础,其中的内容也比较抽象，所以学好命题逻辑又是学好数理逻辑的关键。学好数理逻辑既能加强学生的逻辑思维能力，又同时能够帮助同学学习数字电路和人工智能等其它课程。数理逻辑中关于命题逻辑证明题比较多，学好数理逻辑的关键是能不能很好的掌握这些证明题。 一、命题逻辑中推理的相关概念 定义1：一个命题公式序列1α，2α， ，n α；β，即βααα→ΛΛΛ)(21n 称为推理形式，其中序列最后一项β称为推理的结论，1α，2α， ，n α称为推理的条件。 定义2：对于命题公式序列1α，2α， ，n α；β的命题变元组);,,,(21p p p p n 的任意指派);,,,(21t t t t n 存在使n αααΛΛΛ 21为真，而β为假，则称此推理为无效推理，否则是有效推理。 证明命题公式β为有效结论的过程就是命题逻辑推理证明的过程。而证明推理形式1α， 2α， ，n α；β是有效的充要条件是βααα→ΛΛΛ)(21n 为重言式。 二、常见证明方法 命题逻辑的推理证明有六种常用证明方法，分别是直接证明法，真值表法,范式法，间接证明法。其中间接证明法里面常见的是CP 规则证明法和反证法，本文就这几种方法进行论述。 直言命题 所有的都是上反对 必有一假 所有的都不是包 容矛盾 包 容 有的是必有一真 下反对有的不是 所有的A是B 上反对 必有一假 所有的A都不是B 包 容矛盾 包 容 有的A是B 必有一真 下反对有A的不是B 三段论 A→B B→C A→B 有的B是C A→C 有的C是B —B →—A 逆否（A→B的矛盾关系A∧—B）A→B 有的A→B 有的B→A —A∨B B→C 充分假言：前推后（A推B），肯前肯后，否后否前 如果A，那么B；只要A，就B 若A，则B 所有A，是B 凡是A，是B 为了A，一定B 为了A，必须B A指的就是B 除非不A，否则B 必要假言B推A 只有A，才B 没有A，就没有B 不A，不B 除非A，否则不B A是B的前提，保障，基础，条件/谁是条件谁在后 选言命题 P、Q √ 相容性P∨Q —P、Q √ P、—Q √ 选言—P、—Q × 不相容性P∕Q 要么P要么Q 不是P就是Q P∨Q的矛盾命题—（P∨Q）→—P ∧—Q P∨Q= —P →Q —Q →P P∨Q 排中律排除一个选中一个必须先排 —A∨B = A→B （鲁宾逊定律） —A∨B的矛盾命题是A∧—B A→B的矛盾命题是A∧—B 模态命题 必然P 上反对 必有一假 必然非P 包 容矛盾 包 容 可能P 必有一真 下反对可能非P 模态命题的具体关系 “并非必然P”等值于“可能非P”，即：不必然=可能不；“并非必然非P”等值于“可能P”，即：不必然不=可能；“并非可能P”等值于“必然非P”，即：不可能=必然不；“并非可能非P”等值于“必然P”，即：不可能不=必然； 模态命题与非模态命题的推出关系 必然P→P →可能P ; 必然非P →非P→可能非P 1、逻辑联接词的运算 从键盘输入两个命题变元P和Q的真值，输出它们的合取、析取、条件、双条件和P的否定的真值。 #include { if(P==0) P=P; else P=1; if(Q==0) Q=Q; else Q=1; if(P==1&&Q==0) return(0); else return(1); } int shuangtiaojian(int P,int Q) { if(P==0) P=P; else P=1; if(Q==0) Q=Q; else Q=1; return(!P^Q); } int Pfaoding(int P) { if(P==0) P=P; else P=1; return(!P); } int show(int a,int b) { cout<<"P Q P∧Q P∨Q P→Q P←→Q ┐P"< 《数字电路与逻辑设计》 教 案 试讲教师：孙发贵 工作单位：北京化工大学北方学院 教学内容与过程 （一）讲解新课 逻辑运算：当0和1表示逻辑状态时，两个二进制数码按照某种指定的因果关系进行的运算。即逻辑运算表示的是条件与结果之间的因果关系。 逻辑运算与算术运算完全不同，其采用的数学工具是逻辑代数。 逻辑代数——又称布尔代数或开关代数，是按一定逻辑规律进行运算的代数，是分析和设计数字电路的工具和理论基础。 逻辑代数与普通代数的异同： 相同点：变量与函数均用字母表示 不同点：ⅰ) 无论变量与函数均只有0、1两种取值 ⅱ) 0、1只表示两种对立的逻辑状态， 无数量大小的意义。 一、三种基本逻辑关系 1、与逻辑（逻辑乘） (1)定义：只有决定事物结果的全部条件同时具备时，结果才发生。 L何时点亮？只有开关A、B全部闭合时。 (2)逻辑式：L= A·B = AB (3)真值表：表示变量与函数关系的表格。 逻辑赋值：设开关A、B：闭合为“1”，断开为“0” 灯L：亮为“1”，灭为“0”。讨论与逻辑运算的逻辑口诀 逻辑功能口决：有“0”出“0”，全“1”出“1”。 即当逻辑变量A、B同时为1时，逻辑函数L才为1。其它情况下，L均为0。 （4）逻辑符号 （国标）：（国外）： 推广到n个逻辑变量情况，“与运算”的布尔代数表达式为：L=A1A2A3… A n 2、或运算（逻辑加） (1)定义：在决定事物结果的诸条件中只要任何一个满足，结果就 会发生。 (2)逻辑表达式：L=A+B (3)真值表：逻辑赋值：设开关A、B：闭合为“1”，断开为“0” 灯L：亮为“1”，灭为“0”。 讨论或逻辑运算的逻辑口诀 逻辑功能口决：有“1”出“1”全“0”出“0” （4）逻辑符号 （国标）：（国外）： 若有n个逻辑变量呢？ L=A1+A2+A3+…+A n 3、非运算（逻辑反） (1)定义：条件与结果反相 A具备时，事件L不发生；A不具备时，事件L发生。 电阻的作用：防止整个电路短路 (2)逻辑表达式：A L (3)真值表：逻辑赋值：设开关A、B：闭合为“1”，断开为“0” 灯L：亮为“1”，灭为“0”。 离散逻辑学实验 班级：10电信实验班学号：Q 姓名：王彬彬 一、实验目的 熟悉掌握命题逻辑中的联接词、真值表、主范式等，进一步能用它们来解决实际问题。 二、实验内容 1. 从键盘输入两个命题变元P和Q的真值，求它们的合取、析取、条件和双条件的真值。（A） 2. 求任意一个命题公式的真值表（B，并根据真值表求主范式（C）） 三、实验环境 C或C＋＋语言编程环境实现。 四、实验原理和实现过程（算法描述） 1.实验原理 （1）合取：二元命题联结词。将两个命题P、Q联结起来，构成一个新的命题P∧Q, 读作P、Q的合取, 也可读作P与Q。这个新命题的真值与构成它的命题P、Q的真值间的关系为只有当两个命题变项P = T, Q = T时方可P∧Q =T, 而P、Q只要有一为F则P∧Q = F。这样看来，P∧Q可用来表示日常用语P与Q, 或P并且Q。 （2）析取：二元命题联结词。将两个命题P、Q联结起来，构成一个新的命题P∨Q, 读作P、Q的析取, 也可读作P或Q。这个新命题的真值与构成它的命题P、Q的真值间的关系为只有当两个命题变项P = F, Q = F时方可P∨Q =F, 而P、Q只要有一为T则P∨Q = T。这样看来，P∨Q可用来表示日常用语P或者Q。 （3）条件：二元命题联结词。将两个命题P、Q联结起来，构成一个新的命题P→Q, 读作P条件Q, 也可读作如果P，那么Q。这个新命题的真值与构成它的命题P、Q的真值间的关系为只有当两个命题变项P = T, Q = F时方可P→Q =F, 其余均为T。 （4）双条件：二元命题联结词。将两个命题P、Q联结起来，构成一个新的命题P←→Q, 读作P双条件于Q。这个新命题的真值与构成它的命题P、Q的真值间的关系为当两个命题变项P = T, Q =T时方可P←→Q =T, 其余均为F。 （5）真值表:表征逻辑事件输入和输出之间全部可能状态的表格。列出命题公式真假值的表。通常以1表示真，0 表示假。命题公式的取值由组成命题公式的命题变元的取值和命题联结词决定，命题联结词的真值表给出了真假值的算法。真值表是在逻辑中使用的一类数学表，用来确定一个表达式是否为真或有效。 （6）主范式： 主析取范式：在含有n个命题变元的简单合取式中,若每个命题变元与其否定不同时存在,而两者之一出现一次且仅出现一次,称该简单合取式为小项。由若干个不同的小项组成的析取式称为主析取范式;与A等价的主析取范式称为A的主析取范式。任意含n个命题变元的非永假命题公式A都存在与其等价的主析取范式,并且是惟一的。 主合取范式：在含有n个命题变元的简单析取式中,若每个命题变元与其否定不同时存在,而两者之一出现一次且仅出现一次,称该简单析取式为大项。由若干个不同的大项组成的合取式称为主合取范式;与A等价的主合取范式称为A的主合取范式。任意含n个命题变元的非永真命题公式A都存在与其等价的主合取范式,并且是惟一的。 五、代码设计结果： 、必然性推理 概念间关系 直言命题的对当关系 直言命题的变形推理 三段论推理 联言命题与选言命题 假言命题 模态命题 智力推理 ? 概念间关系（概念，是构成命题与推理的基础，只有表达了一类事物的词语才是概念） 直言命题（简单命题），是断定对象是否具有某种性质的单句 ? 直言命题的对当关系（不同直言命题之间在真假方面所存在的制约关系） 所有 A 是 B 反对 ........... 所有 A 不是 B 推出 推出 有的 A 是 B. “所有A 是B ” 与“有的A 不是B ”、“.所有A 不是B ”与“有的A 是 B ”必有一真一假 “所有A 是B ”与“.所有A 不是 B ” 必有一假（可以同假） “有的 A 不是B ”与“有的 A 是 B ” 必有一真（可以同真） 一个命题前面+“并非”=这个命题的矛盾命题 所有与有的互换，有“不”的去掉，没“不”的加上 ? 直言命题的变形推理（通过改变前提中直言命题的联项或主项与谓项的关系 结论） ①换质推理 双重否定表示肯定 将“不是”改为“是”或将“是”改为“不是” ②换位推理（倒过来说） 所有A 是B 有些B 是 A 所有 A 不是 B 所有 B 不是 A 有些 A 是 B 有些 B 是 A 有些 A 不是 B 特殊词量（少数，大部分，一半）作为量项引导命题，不能换位 ? 三段论推理（两个直言命题作为前提/ 一个直言命题作为结论） （两个前提包含三个概念/ 前提和结论中，每个概念都出现两次） 两条常用规则 一特得特：两个前提不能都是特称命题（含有“有的”命题） 只有一个前提是特称，结论也是特称 一否得否：两个前反对 矛盾 . 有的A 不是 B 下反对 【实验目的】 使学生熟练掌握利用计算机语言实现逻辑运算的基本方法。 【实验内容】 对给出的任意一个命题公式（不超过四个命题变元），使学生会用C语言的程序编程表示出来，并且能够计算它在各组真值指派下所应有的真值，画出其真值表。 【实验原理】 给出任意一个命题公式，我们可以将它用C程序表示出来，并且能够计算它在各组真值指派下所应有的真值（或是逻辑运算的结果）。这有多种方法。上面我们已经给出了逻辑连结词的定义，根据这种定义方法，我们也可以把一个命题公式表示成为条件语句中的条件表达式，这样我们就可以得到该命题公式的逻辑运算结果了。 【程序代码】 #include 逻辑命题公式计算
六年级逻辑推理
八种常用逻辑门的实用知识(逻辑表达式、逻辑符号、真值表、逻辑运算规则)
逻辑判断推理中常用的逻辑公式
公务员考试判断推理常用公式
命题逻辑的推理理论(牛连强)
计算命题演算公式的真值
逻辑判断推理中常用的逻辑公式
命题逻辑复习题和答案
逻辑推理理论(简明汇总)
命题逻辑中几种常见的推理证明方法
逻辑推理公式
离散数学之逻辑运算和命题公式真值表
基本逻辑运算
离散数学,逻辑学,命题公式求真值表
判断推理——逻辑判断
离散数学实验报告命题逻辑—构造命题公式的真值表
- 八种常用逻辑门的实用知识(逻辑表达式、逻辑符号、真值表、逻辑运算规则)
- 已知条件-计算逻辑表达式的值
- 计算逻辑表达式真值和通用试题库设计
- 八种常用逻辑门的实用知识逻辑表达式逻辑符真值表逻辑运算规则
- 逻辑运算原理及计算方法
- 逻辑运算符表达(C语言)
- 逻辑命题公式计算
- 逻辑运算和逻辑表达式
- Matlab的逻辑运算
- 逻辑运算符和表达式
- 八种常用逻辑门的实用知识逻辑表达式逻辑符真值表逻辑运算规则
- 逻辑命题公式计算
- 逻辑表达式
- 布尔代数,逻辑运算公式
- 种常用逻辑门的实用知识逻辑表达式逻辑符号真值表 逻辑运算规则
- 逻辑命题公式计算
- 种常用逻辑门的实用知识逻辑表达式逻辑符真值表逻辑运算规则
- 八种常用逻辑门的实用知识逻辑表达式、逻辑符号、真值表、逻辑运算规则)
- 八种常用逻辑门的实用知识 逻辑表达式 逻辑符号 真值表 逻辑运算规则
- 数字电路的逻辑运算