2023年离散数学实验报告

AU4H2总

实验报告

（2023/2O23学年第一学期）

课程名称离散数学

实验名称运用真值表法求取主析取范式以及主合取范

式的实现

实验报告

实验名称运用真值表法求取主析取范式指导教师

以及主合取范式的实现

实验类型验证实验学时4实验时间

一、实验目的和规定

内容：

编程实现用真值表法求取任意数量变量的合式公式的主析取范式

和主合取范式。

规定：

可以列出任意合式公式的真值表并给出相应主析取和主合取范

式。

二、实验环境（实验设备）

X86架构计算机

操作系统：Windows732bit

IDE:CodeBlokcs16.02

编程语言：C++

编译器:GCC

三、实验原理及内容

内容:一

编程实现用真值表法求取任意数量变量的合式公式的主机取范式和主

合取范式上_

原理：

先将史缀表达式转换成后缀表达式瘦将后缀表达式生集二个生母变量

二二赋值,—用递归枚举的方法枚举所有赋值情况「并且用电LP一映射将每二

个字母变量与当前被枚举的值二二映射5对每二种J赋值情况调用后缀表达式

计算函数让算后缀表达式的值打印真假情况「假如是真」记录到名为工hen

的咽上丕定员数组也―假如是假设录到名为_亚上的_Y££/.丕定售数组

生。―最后根据一zh典和一口头的丕定长数组来扛比主板取范式和主合取范式」

此程序亘以实现任意数量的字母变量的主板取范式求取和主合取范式

求取」以及真值表打耳L

实验报告

第一步：预解决

一预解决二去除空缀表达式史条件2:史的》和双条件0三史的三到一之一这

挂所直的运算符反遢二仝至符一，一后期解决起来更加方便

voidddd()

1.

!stringj__:_iJe_rator__i=zhpng.be良inQj___L/_澳1口g_娄迭代盎.L_需在•头文献

力口入#inc1ude<strin_g>

intflag=1；

while(flag)

___1,

f1ag=0；

for(i=zhonq.begin();i!=zhonq.end()；++i)

_______1

if(巧=='>，)

________1

zhon」.erase(i);

_____________f_l_a_g=_l；

break;

_________1

if(*i=='=，)

zhong.erase(i)；

__________________Xlag=l；.

break；

__________________]

J_______________________________

第二步:将中缀表达式转换后缀表达式

运用栈羽优先级函数来将史缀表达式转换成后缀表达式_「此函数另二仝功能

是将史缀表达式史所直出现过的生母变量都保在包名为卫Lp_nT的旦民

类生⑸itnS.类为_S_TL_虫的_£震要在头文献加i_n_clude<strin_

并且到ph史史丕出现反复字母」这样」逋过砧蛆逅2。函数就可以摄到所有

字显变量的个数注且方便后面枚举赋值映射上一

金局变量：

乳山里___马士32旦&___〃史缀表达式

charhou[1000];//后缀表达式

s.tring__aJ_pha_L____〃叠放所直字母变量

优先级函数二____

inti&p(_cJiara)___〃栈处优先级

if(a=='#')return0;

•f(a=='(')return12;

if(a=='!!)return10；

◎if(a=='&')return8;

if(a==T)return6：

if(a=='-')return4;

if(a=='<')return2；

if(a==')')return1;

1

_iJlt.—isp(ch.ar_a)______0戋内优先级

1.

oif(a=='#')return0;

。if(a=='(')return1;

Uf(a=='!')return11;

if(a=='&')return9;

if(a==T)return7;

if(a=='-')return5；

if(a=='<')return3；

◎if(a==')')return12；

]___________________________

yoictcJia^n_g^ejj____〃史缀表达式转_换后缀表达式

1.

____血上。，一

____stack<ch_a左S；___/底义!临时梭s需要在头文献加△翅P_clud.e_<_s_ta_cJc>

charch,y：

s.push('#');

ochart1,t2;

»strings_t_reamss{_zhon___〃字符串血盗要在头文^jJJlA#include_<_s^tr

eam>

。whi1e(ss»ch,ch!='#')

兄

2嗔位Np上隹[断是丕是主理」假如是二加2k到a」_曲生字控串史

皿

2______hou_[j++]_=ch;_____〃注且加△到后缀表达式字筱串史

。if(alpha.find(ch)==-1)

。alpha..push_back(_ch)；

00}

______

。elseif(ch==')')

2fpL（»三s£。卫Q一工4皿0；丫上二工丫一三也P_PQPQ）

hou[i++]=y；

»else

___

_________foifes-tpgCk_s-P_2.EC)_；_i_c_J2i_ch)<T_l^CY_l；y=s.__s_.pop

_O_1

001

2_____?h_0u__Lj++j5X；.

_____1

___________旦配ush_m

gs.push(ch);

®}_

awhileQs.empty())

______Y.=s.tJ)_p__(h

_______s_._e_P_pf);..

♦if(y!='#')

__________hou_Jj++15y；

___

n

昨生；

j________

第三步:递归枚举每一个字母变量的取值情况

用途度优先搜数击血的思想进任递归枚举「假如当前递归深度已经达成至符

里长度,就说明所直字母旦经取值成功「生母的二值二用期yR遗任映射(需要在

头文献加△米LAQlude<map>)2_所有字理都已经枚举后调用_c_a_l__(_),_函数对当

前取值情况的卮缀表达式进行计算?—由壬⑪叫<i?_tr_i_n_g®._M对象是金局

变量」近以一函数可以查看到相应定母的取值情况__计算完毕后一扛

印真值一假如当前计复结果是总旦色「那么加△到独弧数组也以待后面的主

近取范式打印遍乱假如是皿混加△到』.数组二以待卮面的主合取范式扛电

jiJIo____________

金局变量：

map<^c_harjnt>_M；___加失射?_弟字母变量与_P_或_1_二二型应

structnote

1.

°inta[100|;

上

_v_ectp^r<note>__zhen/丕定■氐数组i_存放主板取范式才1应字母变量的

虹情况，也就是表达式真值为工

yecto_r_<nct上史Jj@；___〃丕定长数组，一存放主合取范式相应生母变量的_Q1_情

选也就是表达式真值是上一

ypJ&df§_(L里士_m)…”递归枚举每二独字符变量的取值情况

_{

if(cur==alpha.size())

sintans=cal@

gfoKinti=0;i<a1pha.size();i++)

皿

◎"if(Mfalpha£ij_1)

______

。Drintf("T\t")；

8]

8。e1se

be{

。printf("F\t")；

£___1

理也只S三?_LL_//真值为工让△乳独典数组」以饯后面主析取范式使用

8Y

Drintf("T'n"):

motet二

ogfor(inti=0;i<a1pha.size();i++)

8t.ali]=M[alpha[i]];

2____J.

丝,__4hf_IL卫ush_back(t);

_____

一蓟且…〃真值为一F_计人到LL生数组，―以往后面主合取范式使用

。。printf("F\n");

notet;

♦for(inti=0;i〈alpha,size();i++)

。t.a[i]=M[aIphafi]];

so}

ooJLia.pushback(6

so}

8return;

吐

____MLa_lRha[curl]^l；_______//簧度优先搜索泌任递归枚举

dfs(cur+lj；

MLalphaicuii|=。；

od_fs(c_ur+l_)j__

___

皿"10__/对赋值卮的后缀表达式进行计算延回让算结果

1.

stack<int>s;

charch；

血匚_上。；

ajnttl,t2;

while(l)

8ch=hou[j];

♦f(ch=='#')break;

if(ch==O)break；

叱j_土土

oif((ch>='A'&&ch<='Z')||(ch>='a&&ch<='z'»

。s.push(M[ch]);

eelse

______1

84f(ch=='!'_)

81

。“1=s.top()；

___A__®s._p_opfh

ggs.push(!t1);

2_____.}.

。8e1seif(ch=='&')

00I

。tl=s.to_pO;

______f___AJBQPil；

。8t2=s.top();

.__S.__p9pQ__；

“f(tl==l&&t2==l)

__________

。80S,push⑴;

2_________1

°else

boe{

_________A..^pus.hLQJj

2______J.

elseif(ch=='|')

。tl=s.toD()：

80S,pop。；

ot2=s.toj^01

_______________s_.__pp_p__(h

gsif(tl==0&&t2==0)

-os.push(0);

®else

bbb{

。os.push(1);

2__________1

吧}

。。eIseif(ch=='-')

“1=s.top();

___________^pop0;

oooot2=S.tOp01

吵一____S正2儿_0；

o。if(tl==0&&t2==l)

861

。。s.push(0);

。seise

_________________s^__P_u_sh(lh

。《elseif(ch=='<')

000{

。"tl=s.topQ;

0°aS.P0PQ；

。t2=s.top。；

____咨PPfiOi一

°。if((tl==1&&t2==1)1I(tl==0&&t2==0))

2_________1

bgs.push(l)；

00001

8。eIse

___A_____{

ss.push(0)；

______J」

8]

____J.

intans=s.top();

returnans：

}________________

最后一步：打印主析取范式和主合取范式

_____最后二步也是最简朴隹1二会打包主折取范式和主合取范式由壬前面在

递归枚举工垃一的过程里已经把直值表顺带打史工团以前只剩工主板取范式和

士会取范式了」在df_s_过程史」所有取值为真的情遁已经加△2?典的上屈

上如数组史上，—所直取值为假的以及加△到工迫效x攵其区数组史工」虽然

存放的是0L序理但是回ML史空理顺底自始至终丕变庭以根据下标亘以形成

二Z1相应关系_?一

main函数

intmainQ

1.

while(true)

o»inti;

♦a1pha.clear();

zhen.cleaKk

ajia.clear();

俎辿f。或运算为与运算为_&_」单条件为一二_一双一条住我

士壬，韭运算为」也'上

…一6Pm上或请输△表达式胆车结束)里‘)」

»cin>>zhong;

£___zh__ojig.j^)pen_d(_［把)_

oddd0;

-.change();

。for(i=O;i<alpha.size()；i++)

____吐

Printf(11%c\t11*ah)ha「i1)：

00)

"Pi_Ln±fC表达式真值_\工二)；_

______dfMQh

2?PI_i旦土工C主板取范式为\R」上

gint1ena=zhen.size();

•for(i=0；i<lena；i++)

____4

。“if(i!=0)printf("V"):

8int*p=zhen[i].a；

for(intj=0；(<aIpha.size()；j++)

。。<if(i!-intf("/\")；

________城工旦_血2)

bo{

。叩rintf("%c",alphalj]);

8else

。。printfC'""1%c",alpha[jD；

_______

00

2______P_r_intfCH).l

____d

printf

j_n_tX_L2'_主盒取范式为\n_1)；

£—M=0；_1<jiarsizen;i土土)

皿

o“if(i!=0)Drintf("/?')；

。Unt*p=jia[i].a;

。ofor(jnta.lphaqsize()；j_±+)

回.

。。if(i!=0)r>i'intf("V")：

。if(pljl==。)

Q°{

。。Drintf("%c”.a1pha[j])：

。。else

_______1

。。叩rintfC'""1%^,a1pha[j])；

______4

。printf(")”):

____4

。printf("\n\n

return0;

]_________________________________________________________________

程序测i西^j&.

由壬使用JLST_LJLYf_箕蛇教组和里面上―娄二所以可以实现让算县直任意数

量的生母变量的表达式2

生程序史或运算为_」―_与运算为单条件为__二三_一双条件我

三三'，韭运算为._!

测试二一

1IAP&Q

运营截图二

结果：对的

测试三

输△书上第3工页上方例题上粤0)1£1续&

或运算为1,与运算为s，单条件为->，双条件我<=>，非运算为»

请输入表达式,回车结束

(PSQ)I(!P2R)

PQR表达式真值

TTTT

TTFT

TFTF

TFFF

FTTT

FTFF

FFTT

FFFF

主析取范式为

(PAQAR)V(PAQA^R)VC^PAQAR)V(-'PA-，QAR)

主合取范式为

(-1PVQV-nR)AC^PVQVR)ACPV^QVR)A(PVQVR)

结果一处的

测试三

课本39页(4)d)(P->(O&R))&(!P->(!Q&!R))

或运算为I,与运算为2，单条件为->，双条件我">，非运算为?

储输入表达式，回车结束

(P->(Q&R))3(»P->(»Qfi?R))

PQR表达式真值

TTTT

TTFF

TFTF

TFFF

FTTF

FTFF

FFTF

FFFT

主析取范式为_

(PAQAR)V(^PA^QA^R)

主合取范式为

(—PVQVR)A(-'PVQV-，R)AC^PVOVR)A(PV-'QV-，R)ACPV-'QVR)A(PVQV

R)

测试四

输入A&B&C&D&E

广C:\Users\ZL\Desktop\exercise\codeblocks\主析取范式\bin\Debug\3242.exe

IA&B&C&DAE▲

ABcDE表达式真值

TTTTTT

TTTTFF

TTTFTF

TTTFFF

TTFTTF

TTFTFF

TTFFTF

TTFFFF

TFTTTF

TFTTFF

TFTFTF

TFTFFF

TFFTTF

TFFTFF

TFFFTF

TFFFFF

FTTTTF

FTTTFF

FTTFTF

FTTFFF

FTFTTF

FTFTFF

FTFFTF

FTFFFF

FFTTTF

FFTTFF

FFTFTF

FFTFFF

FFFTTF

FFFTFF

FFFFTF

FFFFFF

主析取范式为

(AABAcADAE)

主合取范式为

(^AV^BVCV^DVE)A("nAV-nBV-，CVDV^E)AC-'AV^BV^CVDVE)A(^AV

PBVCV’「DV一E)A(^AV^BVCV^DVE)A(^AV^BVCVDV~"E)AC^AVBVCVD

VE)A(""AVBV^cv-，DV-1E)A(-，AVBV-，CV-，DVE)A(-，AVBV_1CVDV'^E)A(^

AVBV,CVDVE)A(~■WBVCV-W「E)AC^AVBVCV-'DVE)A(^AVBVCVDV'"E

)A(^AVBVCVDVE)A(AV^BV^CV^DV^E)A(AV^BV-^CV^DVE)A(AV""BV

ncVDV,^E)A(AV-nBV^CVDVE)A(AV-"BVCV-nDV-，E)A(AV-，BVCV-，DVE)A(

lAV^BVCVDVE)ACAV^BVCVDVE)A(AVBV-，CV_1DV-"E)ACAVBV^CV^DVE

)A(AVBV^CVDV^E)ACAVBVCVDVE)ACAVBVCV^DV^E)A(AVBVCV^DVE

)ACAVBVCVDV^E)A(AVBVCVDVE)

对的

测试五

输△课至32页―Q2)_b_)

P->((0&R)—>S)

请输入表达式，回车结束

P->((QSR)->S)

PQRS表达式真值

TTTTT

TTTFF

TT