计算命题演算公式的真值
四计算命题演算公式的真值
一．实验题目
所谓命题演算公式是指由逻辑变量（其值为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) /*将元素入栈*/
int StackPop(LSNode* head,DataType* d) /*弹出栈顶元素*/
int StackTop(LSNode* head,DataType *d) /*取栈顶元素*/
void Destroy(LSNode* head) /*撤消*/
void ExplsCorrect(char exp[]) /*检测输入表达式的括号匹配函数*/
i
3.详细设计
void StackInitiate(LSNode** head)
{
if((*head=(LSNode*)malloc(sizeof(LSNode)))==NULL)exit(1);
(*head)->next=NULL;
} /*初始化堆栈*/
int StackNotEmpty(LSNode* head)
{
if(head->next==NULL)return 0;
else return 1;
}
/*检测堆栈是否为空的函数，若为空，返回0，否则返回1*/
typedef struct snode
{
DataType data;
struct snode* next;
}LSNode;
/*定义了链表的结点用于下面检测表达式的括号匹配*/
int StackPop(LSNode* head,DataType* d)
{
LSNode* p=head->next;
if(p==NULL)
{
cout<<"堆栈已空出错"< return 0; } head->next=p->next; *d=p->data; free(p); return 1; } /*弹出栈顶元素*/ int StackPush(LSNode* head,DataType x) { LSNode* p; if((p=(LSNode*)malloc(sizeof(LSNode)))==NULL) { cout<<"内存空间不足无法插入!"< return 0; } p->data=x; p->next=head->next; head->next=p; return 1; } /*将元素入栈*/ int StackTop(LSNode* head,DataType *d) { LSNode* p=head->next; if(p==NULL) { cout<<"堆栈已空出错"< return 0; } *d=p->data; return 1; } /*取栈顶元素*/ void Destroy(LSNode* head) { LSNode* p,*p1; p=head; while(p!=NULL) { p1=p; p=p->next; free(p1); } }/*撤消*/ 三．调试分析 在运行程序的过程中，碰到了一些错误，其中有很多是括号和分号的问题，看来以后写程序要更加细心才行。 四．用户手册 此程序中'&''|''~'分别代表代表'与' '或' '非'运算 首先输入一个包含变量，运算符表达式，再按Enter执行。再依次输入各变量的值。如果不继续输入，按0退出。再按y继续或者n退出。 五．测试数据及测试结果 输入a&b&c 六．源程序清单 typedef struct { DataType stack[1000]; int top; }SeqStack1; 出真值计算 1.重新输入各变量的值）:"; cin>>i; if(i==0) break; } int v[100],p; printf("真值表如下：\n"); End=0; long count=(int)pow(2,num); for(p=0;p { v[p]=0; } for (long ii=0;ii { j=0; for(i=0;i<20;i++) { if(b[i][0]!='!'&& b[i][0]!='&'&& b[i][0]!='|') c[i]=v[j++]; } for (int jj=0;jj { printf("%d ",v[jj]); } printf("真值为：%ld\n",End=PostOrder(P,c,b,n)); printf("\n"); v[num-1]++; p=num-1; while(v[p]>=2) { v[p]%=2; v[p-1]++; p--; } } cout<<"\n'y':继续下一个表达式的计算 'n':退出程序"< cout<<"\n'y' or 'n'?"; cin>>m; cout<<"\n\n"; } } 离散数学自学笔记命题公式及其真值表 我们把表示具体命题及表示常命题的p，q，r，s等与f，t统称为命题常元（proposition constant）。深入的讨论还需要引入命题变元（proposition variable）的概念，它们是以“真、假”或“1，0”为取值范围的变元，为简单计，命题变元仍用p，q，r，s等表示。相同符号的不同意义，容易从上下文来区别，在未指出符号所表示的具体命题时，它们常被看作变元。 命题常元、变元及联结词是形式描述命题及其推理的基本语言成分，用它们可以形式地描述更为复杂的命题。下面我们引入高一级的语言成分——命题公式。 定义1.1 以下三条款规定了命题公式（proposition formula）的意义： （1）命题常元和命题变元是命题公式，也称为原子公式或原子。 （2）如果A，B是命题公式，那么（┐A），（A∧B），（A∨B），（A→B），（A？B）也是命题公式。 （3）只有有限步引用条款（1），（2）所组成的符号串是命题公式。 命题公式简称公式，常用大写拉丁字母A，B，C等表示。公式的上述定义方式称为归纳定义，第四章将对此定义方式进行讨论。 例1.8 （┐（p→（q∧r）））是命题公式，但（qp），p→r，p1∨p2∨…均非公式。 为使公式的表示更为简练，我们作如下约定： （1）公式最外层括号一律可省略。 （2）联结词的结合能力强弱依次为┐，（∧，∨），→，？，（∧，∨）表示∧与∨平等。 （3）结合能力平等的联结词在没有括号表示其结合状况时，采用左结合约定。湖南省自考网：https://www.wendangku.net/doc/9c5348742.html,/整理 例如，┐p→q∨（r∧q∨s）所表示的公式是（（┐p）→（q∨（（r∧q）∨s））） 设A是命题公式，A1是A 的一部分，且A1也是公式，则A1称为公式A的子公式。 题号：第一题 题目：电梯模拟 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()函数中。 名 称 逻 辑 表 达 式 逻 辑 符 号 真 值 表 逻辑运算规则 与 门 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 【有前件必然有后件，没有前件必然没有后件。充要条件假言命题在前件与后件等值即前件真并且后件真，或者前件假并且后件假时，命题为真，在前件与后件不等值即前真后假，或前假后真时，命题为假】 充分条件与必要条件之间可以相互转化： 我们把表示具体命题及表示常命题的p，q，r，s等与f，t统称为命题常元（proposition constant）。深入的讨论还需要引入命题变元（proposition variable）的概念，它们是以“真、假”或“1，0”为取值范围的变元，为简单计，命题变元仍用p，q，r，s等表示。相同符号的不同意义，容易从上下文来区别，在未指出符号所表示的具体命题时，它们常被看作变元。 命题常元、变元及联结词是形式描述命题及其推理的基本语言成分，用它们可以形式地描述更为复杂的命题。下面我们引入高一级的语言成分——命题公式。 定义1.1 以下三条款规定了命题公式（proposition formula）的意义： （1）命题常元和命题变元是命题公式，也称为原子公式或原子。 （2）如果A，B是命题公式，那么（┐A），（A∧B），（A∨B），（A→B），（A？B）也是命题公式。 （3）只有有限步引用条款（1），（2）所组成的符号串是命题公式。 命题公式简称公式，常用大写拉丁字母A，B，C等表示。公式的上述定义方式称为归纳定义，第四章将对此定义方式进行讨论。 例1.8 （┐（p→（q∧r）））是命题公式，但（qp），p→r，p1∨p2∨…均非公式。 为使公式的表示更为简练，我们作如下约定： （1）公式最外层括号一律可省略。 （2）联结词的结合能力强弱依次为┐，（∧，∨），→，？，（∧，∨）表示∧与∨平等。 （3）结合能力平等的联结词在没有括号表示其结合状况时，采用左结合约定。 例如，┐p→q∨（r∧q∨s）所表示的公式是（（┐p）→（q∨（（r∧q）∨s））） 设A是命题公式，A1是A 的一部分，且A1也是公式，则A1称为公式A的子公式。 如对公式A：┐p→q∨（r∧q∨s），则p，┐p ，q ，（r∧q∨s）及q∨（r∧q∨s）都是公式A的子公式，而┐q，┐p→q，虽然是公式，但确不是A的一部分，因此不是A 的子公式；q∨（r∧虽然是公式A的一部分，但不是公式，因而也不是A的子公式。 如果公式A含有命题变元p1，p2，…，pn，记为A（p1，…，pn），并把联结词看作真值运算符，那么公式A可以看作是p1，…，pn的真值函数。对任意给定的p1，…，pn 的一种取值状况，称为指派（assignments），用希腊字母a，b等表示，A均有一个确定的真值。当A对取值状况a 为真时，称指派a弄真A，或a是A的成真赋值，记为a （A）= 1；反之称指派a弄假A，或a是A的成假赋值，记为a （A）= 0.对一切可能的指派， 2 命题公式,真值表 (1) 数理逻辑是通过引入表意符号研究人类思维中的推理过程及推理正确与否的数学分支. 数学------??? 符号运算 推理---思维过程:前提 结论 命题逻辑---研究由命题为基本单位构成的前提和结论之间的可推导关系.(逻辑演算) 即将推理(不涉及内函)形式化. 例1 (a) 4是偶数. 张林学习优秀. 太阳系以外的星球上有生物. (b) 这朵花真美丽! 现在开会吗? (c) 3 5.x +> 我正在说慌. 特征分析(a) 陈述句,非真即假. (b) 感叹句,疑问句. (c) 悖论. 定义1 能辩真假的陈述句,称为命题,用,,,P Q Z 表示.其判断结果称为命题的真值. 成真的命题称为真命题,其真值为真,记为,T 或为1.成假的命题称假命题,其真值为假,记为,F 或为0. 例2 (1) 2008年奥运会在北京举行. (2) 22 5.?= (3) 计算机程序的发明者是诗人拜伦. 用符号表是上述命题,并求真值. 解 (1) :P 2008年奥运会在北京举行. .T (2) :Q 22 5.?= .F (3) :R 计算机程序的发明者是诗人拜伦. .F (2) 3, 35,+ 3(4 1).+- 例3 (1) 今天没有数学考试. (2) 下午,我写信或做练习. (3) 王芳不但用功,而且成绩优秀. (4) 如果太阳从西边出来了,那么地球停止转动. (5) 2是素数,当且仅当三角形有三条边. 特征分析(a)存在自然语言中的虚词. (b)语句可以分解,细化. 定义2 称下列符号为逻辑联结词 否定 ? 非 P ? 析取 ∨ 或者 P Q ∨ 合取 ∧ 且 P Q ∧ 蕴涵 → 若----,则----- P Q → 等价 ? 当且仅当 P Q ? 逻辑联结词真值的规定 例4 将下列命题符号化. (1) 小李聪明,但不用功. ()P Q ∧? (2) 单位派小王或小苏出差. P Q ∨ (3) 如果椅子是紫色的,且是园的,那么地是平的. ()P Q R ∧→ (4) n 是偶数当且仅当它能被2整除. P Q ? 注 1 逻辑联结词:运算符.顺序 ,,,,.?∧∨→? 2 自然语言中 虽然---,但是----; 不但---,而且----; ∧ 只有----,才----; 除非----,才-----; → 3 ∨ 可兼或(相容) ∨ 不可兼或(排斥) 小王是山东人或是河北人. ()()P Q P Q P Q ∨?∧?∨?∧ 4 ,P Q -----------------------简单命题 在设计逻辑电路图时，由真值表直接得到的函数往往比较复杂。代数法和卡诺图法等方法对于变量数目较多的逻辑函数则效果不佳，本文介绍一种可以化简复杂逻辑函数的方法──表格法，该方法可以对变量数目较多的逻辑函数也可以进行化简。 2、原理 在介绍化减法之前，先说明三个概念： 蕴涵项──在函数的任何积之和式中，每个乘积项称为该函数的蕴涵项。对应于卡诺图中的任一标1单元(最小项)以及2m个相邻单元所形成的圈都是函数的蕴涵项。 素项──若函数的一个蕴涵项不是该函数中其它蕴涵项的一个子集，则此蕴涵项称为素蕴涵项，简称素项。 实质素项──若函数的一个素项所包含的某一最小项，不包括在该函数的其它任何素项中则此素项称为实质素蕴涵项，简称实质素项。 列表化简法的基本原理是利用逻辑函数的最小项，通过对相邻最小项的合并，消去多余变量因子，获得逻辑函数的最简式的。列表化简法的思路是先找出给定函数F的全部素项，然后找出其中的实质素项；若实质素项不能覆盖F的所有最小项，则进一步找出所需素项，以构成F的最简素项集。 下面用列表化简法将下列函数化简为最简与或表达式。 F(A,B,C,D)＝Σ(0,3,4,5,6,7,8,10,11) 3、建立素项表 首先，找出给定函数的全部素项。 (1)先将每个最小项所对应的二进制数按其“1”的个数分组得表1； 表1 最小项 (2)将表1中的相邻两个组之间二进制数进行比较、合并得到一次化简结果，称为一次乘积项，其项号记为i(j－i)，其中i为最小项中的小项号，j为最小项中的大项号，得表2； 表2 一次乘积项 (3)再将表2中的相邻两组内的二进制数进行比较、合并、便得到第二次化简结果，称为二次乘积项，其项号记为i(n,m)，其中i为两个一次乘积项中的小项号，n为原最小项的项号差，m为一次乘积项的项号差，得表3； 表3 二次乘积项 不能与其它一次乘积项合并的一次乘积项是素项，分别以a,b,c,d,e,f记之，不能合并的二次乘积项也是素项，以g记之。 “离散数学”实验报告（求给定命题公式地真值表并根据真值表求公式地主范式） 专业网络工程 班级 1202班 学号 12407442 姓名张敏慧 2013.12.14 目录 一.实验目地 3 二.实验内容 (3) 求任意一个命题公式地真值表 (3) 三.实验环境 3 四. 实验原理和实现过程（算法描述）3 1.实验原理 (3) 2.实验流程图 (5) 五.实验代码 6 六. 实验结果14 七. 实验总结19 一.实验目地 本实验课程是网络工程专业学生地一门专业基础课程,通过实验,帮助学生更好地掌握计算机科学技术常用地离散数学中地概念.性质和运算；通过实验提高学生编写实验报告.总结实验结果地能力；使学生具备程序设计地思想,能够独立完成简单地算法设计和分析. 熟悉掌握命题逻辑中地真值表.主范式等,进一步能用它们来解 决实际问题. 二.实验内容 求任意一个命题公式地真值表,并根据真值表求主范式 详细说明： 求任意一个命题公式地真值表 本实验要求大家利用C/C＋＋语言,实现任意输入公式地真值表计算.一般我们将公式中地命题变元放在真值表地左边,将公式地结果放在真值表地右边.命题变元可用数值变量表示,合适公式地表示及求真值表转化为逻辑运算结果；可用一维数表示合式公式中所出现地n个命题变元,同时它也是一个二进制加法器地模拟器,每当在这个模拟器中产生一个二进制数时,就相当于给各个命题变元产生了一组真值指派.算法逻辑如下： （1）将二进制加法模拟器赋初值0 （2）计算模拟器中所对应地一组真值指派下合式公式地真值. （3）输出真值表中对应于模拟器所给出地一组真值指派及这组真值指派所对应地一行真值. （4）产生下一个二进制数值,若该数值等于2n-1,则结束,否则转（2）. 三.实验环境； 四计算命题演算公式的真值 一．实验题目 所谓命题演算公式是指由逻辑变量（其值为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) /*将元素入栈*/ . 命题逻辑 一、选择题（每题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 ） 逻辑判断推理中常用的 逻辑公式 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 实验报告 实验名称：任意命题公式的真值表 实验目的与要求：通过实验，帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算，包括联结词、真值表、运算的优先级等，提高学生编写实验报告、总结实验结果的能力，培养学生的逻辑思维能力和算法设计的思想，能够独立完成简单的算法设计和分析，进一步用它们来解决实际问题，帮助学生学习掌握C/C++语言程序设计的基本方法和各种调试手段，使学生具备程序设计的能力。 实验内容提要：求任意一个命题公式的真值表 实验步骤：（一）、关于命题公式的形式和运算符（即联结词）的运算 首先根据离散数学的相关知识，命题公式由命题变元和运算符（即联结词）组成，命题变元用大写字母英文表示（本次试验没有定义命题常元T和F，即T、F都表示命题变元），每个命题变元都有两种真值指派0和1，对应于一种真值指派，命题公式有一个真值，由所有可能的指派和命题公式相应的真值按照一定的规范构成的表格称为真值表。 目前离散数学里用到的包括扩充联结词总共有九种，即析取（或）、合取（与）、非、蕴含、等值、与非、或非、异或、蕴含否定，常用的为前五种，其中除了非运算为一元运算以外，其它四种为二元运算。所以本次实验设计时只定义了前五种运算符，同时用“/”表示非，用“*”表示合取，用“+”表示析取，用“>”表示蕴含，用“:”表示等值，且这五种运算符的优先级依次降低，如果需用括号改变运算优先级，则用小括号()改变。 以下为上述五种运算符运算时的一般真值表，用P和Q表示命题变元：1．非，用“/”表示 2．合取（与），用“*”表示 3．析取（或），用“+”表示 4.蕴含，用“>”表示 5.等值，用“:”表示 （二）、命题公式真值的计算 对于人来说，计算数学表达式时习惯于中缀表达式，例如a*b+c，a*（b+c）等等，而对于计算机来说，计算a*b+c还好，计算a*（b+c）则困难，因为括号的作用改变了运算的顺序，让计算机识别括号而改变计算顺序显得麻烦。经理论和实践研究，用一种称之为后缀表达式（逆波兰式）的公式形式能让计算机更容易计算表达式的真值。例如上面的a*（b+c），其后缀表达式为abc+*，计算时从左边开始寻找运算符，然后按照运算符的运算规则将与其相邻的前面的一个（非运算时为一个）或两个（其它四种运算为两个）操作数运算，运算结果取代原来的运算符和操作数的位置，然后重新从左边开始寻找运算符，开始下一次计算，比如上式，从左边开始寻找运算符，先找到+，则计算b+c，结果用d表示，这时后缀表达式变为ad*，又重新开始从左边开始寻找运算符，找到*，则计算a*d， 离散数学实验报告 专业班级：12级计算机本部一班姓名：鲍佳珍 学号：201212201401016 实验成绩： 1．【实验题目】 命题逻辑实验二 2．【实验目的】 熟悉掌握命题逻辑中真值表，进一步能用它们来解决实际问题。 3．【实验内容】 求任意一个命题公式的真值表 4、【实验要求】 C或C＋＋语言编程实现 5. 【算法描述】 1.实验原理 真值表:表征逻辑事件输入和输出之间全部可能状态的表格。列出命题公式真假值的表。通常以1表示真，0 表示假。命题公式的取值由组成命题公式的命题变元的取值和命题联结词决定，命题联结词的真值表给出了真假值的算法。真值表是在逻辑中使用的一类数学表，用来确定一个表达式是否为真或有效。 2.实验过程 首先是输入一个合理的式子，生成相应真值表，然后用函数运算，输出结果：要求可生成逻辑非、合取、析取、蕴含、双条件表达式的真值表，例如：输入 !a 输出真值表如下： a !a 0 1 10 输入a&&b 输出真值表如下： a b a&&b 0 0 0 0 1 0 1 0 0 1 1 1 输入a||b 输出真值表如下： a b a||b 0 0 0 0 1 1 1 0 1 1 1 1 输入a->b 输出真值表如下： a b a->b 0 0 1 0 1 1 1 0 0 1 1 1 输入a<>b (其中<>表示双条件) 输出真值表如下： a b a<>b 0 0 1 0 1 0 1 0 0 1 1 1 6.【源程序（带注释）】 #include 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"< 求给定命题公式的真值表并根据真值表求公式的主范式(求给定命题公式的真值表并根据真值表求公式的主范式) 专业网络工程 班级 1202班 学号 12407442 姓名张敏慧 2013.12.14 目录 一.实验目的 ....................................................... 3 二.实验内容 (3) 求任意一个命题公式的真值 表 ..................................................................... ..... 3 三.实验环 境 (3) 四. 实验原理和实现过程(算法描述) (3) 1.实验原 理 ..................................................................... ...................................... 3 2.实验流程 图 ..................................................................... .................................. 5 五.实验代 码 (6) 六. 实验结果 (14) 七. 实验总结 (19) - 1 - 一.实验目的 本实验课程是网络工程专业学生的一门专业基础课程，通过实验，帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算;通过实验提高学生编写实验报告、总结实验结果的能力;使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。 熟悉掌握命题逻辑中的真值表、主范式等，进一步能用它们来解决实际问题。 二.实验内容 求任意一个命题公式的真值表，并根据真值表求主范式 详细说明: 求任意一个命题公式的真值表 本实验要求大家利用C/C，，语言，实现任意输入公式的真值表计算。一般我 们将公式中的命题变元放在真值表的左边，将公式的结果放在真值表的右边。命题变元可用数值变量表示，合适公式的表示及求真值表转化为逻辑运算结果;可用一维数表示合式公式中所出现的n个命题变元，同时它也是一个二进制加法器的模拟器，每当在这个模拟器中产生一个二进制数时，就相当于给各个命题变元产生了一组真值指派。算法逻辑如下: (1)将二进制加法模拟器赋初值0 (2)计算模拟器中所对应的一组真值指派下合式公式的真值。 (3)输出真值表 中对应于模拟器所给出的一组真值指派及这组真值指派所对应的一行真值。 n(4)产生下一个二进制数值，若该数值等于2-1，则结束，否则转(2)。 三.实验环境; 使用visual C++6.0为编程软件，采用C语言为编程语言实现。 《数字电路与逻辑设计》 教 案 试讲教师：孙发贵 工作单位：北京化工大学北方学院 教学内容与过程 （一）讲解新课 逻辑运算：当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都存在与其等价的主合取范式,并且是惟一的。 五、代码设计结果：离散数学自学笔记命题公式及其真值表
逻辑命题公式计算
八种常用逻辑门的实用知识(逻辑表达式、逻辑符号、真值表、逻辑运算规则)
逻辑判断推理中常用的逻辑公式
离散数学自学笔记命题公式及其真值表
2 离散数学-命题公式,真值表
真值表化简法
求给定命题公式真值表并根据真值表求公式主范式
计算命题演算公式的真值
命题逻辑复习题和答案
逻辑判断推理中常用的逻辑公式
任意命题公式的真值表
离散数学命题公式真值表C++或C语言实验报告
离散数学之逻辑运算和命题公式真值表
求给定命题公式的真值表并根据真值表求公式的主范式
基本逻辑运算
离散数学,逻辑学,命题公式求真值表
- 任意命题公式的真值表
- 离散数学实验报告命题逻辑—构造命题公式的真值表
- 命题公式真值表培训课件
- 离散数学-逻辑学-命题公式求真值表
- 真值表公式分类命题定律代入置换PPT讲稿
- 第四讲 复合命题与命题公式(下)
- 命题公式真值表
- 离散数学,逻辑学,命题公式求真值表讲课稿
- 求给定命题公式真值表并根据真值表求公式主范式
- 离散数学,逻辑学,命题公式求真值表
- 离散数学 第1章 习题解答
- 最新离散数学命题公式真值表C或C语言试验报告
- 离散数学命题公式真值表C++或C语言实验报告
- (参考资料)求给定命题公式的真值表并根据真值表求公式的主范式
- 构造任意合式公式的真值表(可编辑修改word版)
- 1.2 真值表、公式分类、命题定律、代入置换
- 离散数学自学笔记命题公式及其真值表
- 求给定命题公式的真值表并根据真值表求公式的主范式
- 求给定命题公式的真值表并根据真值表求公式的主范式
- 离散数学,逻辑学,命题公式求真值表