离散数学及应用 课件 1.5-7 联结词全功能集

DiscreteMathematics鄢小虎

离散数学21.5联结词全功能集

联结词全功能集与非联结词,或非联结词3课程引入为什么要有联结词全功能集？

目前有很多的联结词，但是不同的联结词之间是可以相互推导的，存在一定的冗余（例如：蕴涵、等价等值式）。一个形式系统中，有多少个联结词是最合适的呢？全功能集不仅需要少，而且能表达所有真值函数。4联结词的全功能集定义

设S是一个联结词集合，如果任何n(n

1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词全功能集.说明：若S是联结词全功能集，则任何命题公式都可用S中的联结词表示.

设S1,S2是两个联结词集合，且S1

S2.若S1是全功能集，则S2也是全功能集.

反之，若S2不是全功能集，则S1也不是全功能集.5联结词全功能集实例定理{

,∧,∨}、{

,∧}、{

,∨}、{

,→}都是联结词全功能集.证明每一个真值函数都可以用一个主析取范式表示,故{

,∧,∨}是联结词全功能集.p∨q

(

p∧

q)，由德摩根律（反用），则∨可以由{

,∧}替代，故{

,∧}是全功能集.

p∧q

(

p∨

q)，同理，故{

,∨}是全功能集.p→q

p∨q，同理，故{

,→}也是全功能集.6复合联结词

与非式:p

q(p

q)或非式:p

q(p

q)

定理{

},{

}是联结词全功能集.证明：{

},{

}包括{

，∧,∨}，因此{

},{

}是全功能集.组合电路逻辑门:实现逻辑运算的电子元件.与门,或门,非门组合电路:实现命题公式的由电子元件组成的电路.7与门（合取）或门（析取）非门（否定）xx∧yx∨y

xyxyx课堂练习

习题12中(3)-(4)，计算析取范式、合取范式请同学上台推理91.7

推理理论

推理的形式结构判断推理是否正确的方法推理定律与推理规则构造证明

直接证明法,附加前提证明法,归缪法10推理的形式结构—问题的引入

推理举例:(1)正项级数收敛当且仅当部分和有上界.(2)若AÈCÍBÈD，则AÍB且CÍD.推理:从前提出发推出结论的思维过程上面(1)是正确的推理，而(2)是错误的推理.证明:描述推理正确的过程.11推理的形式结构定义若对于每组赋值，或者A1ÙA2Ù…Ù

Ak

均为假，或者当A1ÙA2Ù…ÙAk为真时,B也为真,则称由A1,A2,…,Ak推B的推理正确,否则推理不正确（错误）.“A1,A2,…,Ak

推B”的推理正确当且仅当A1ÙA2Ù…ÙAk®B为重言式.推理的形式结构:A1ÙA2Ù…ÙAk®B或前提：A1,A2,…,Ak

结论：B

若推理正确，则记作：A1ÙA2Ù…ÙAkÞB.12判断推理是否正确的方法真值表法等值演算法判断推理是否正确主析取范式法构造证明法证明推理正确说明：用前3个方法时采用形式结构

“A1ÙA2Ù…ÙAk®B”.用构造证明时,采用

“前提:A1,A2,…,Ak,结论:B”.

13实例例判断下面推理是否正确

(1)若今天是1号，则明天是5号.今天是1号.所以明天是5号.

解设p：今天是1号，q：明天是5号.推理的形式结构为:(p®q)Ùp®q证明（用等值演算法）

(p®q)Ùp®q

Û

Ø((ØpÚq)Ùp)Úq

Û

ØpÚØqÚq

Û1得证推理正确14实例(续)(2)若今天是1号，则明天是5号.明天是5号.所以今天是1号.解设p：今天是1号，q：明天是5号.

推理的形式结构为:(p®q)Ùq®p

证明（用主析取范式法）

(p®q)Ùq®p

Û(ØpÚq)Ùq®p

Û

Ø((ØpÚq)Ùq)Úp

Û

ØqÚp

Û(ØpÙØq)Ú(pÙØq)Ú(pÙØq)Ú(pÙq)

Û

m0Úm2Úm3

结果不含m1,故01是成假赋值，所以推理不正确.15推理定律——重言蕴涵式

重要的推理定律

A

Þ(AÚB)附加律

(AÙB)Þ

A

化简律

(A®B)ÙA

Þ

B

假言推理

(A®B)ÙØB

Þ

ØA

拒取式

(AÚB)ÙØB

Þ

A

析取三段论

(A®B)Ù(B®C)Þ(A®C)假言三段论

(A«B)Ù(B«C)Þ(A«C)等价三段论

(A®B)Ù(C®D)Ù(AÚC)Þ(BÚD)构造性二难16推理定律(续)(A®B)Ù(ØA®B)Þ

B

构造性二难（特殊形式）(A®B)Ù(C®D)Ù(ØBÚØD)Þ(ØAÚØC)

破坏性二难证明:描述推理过程的命题公式序列，其中每个命题公式或者是已知的前提，或者是由前面的命题公式应用推理规则得到的结论.17推理规则

(1)前提引入规则(2)结论引入规则(3)置换规则(4)假言推理规则

A®BA

\B(5)附加规则

A

\AÚB

(6)化简规则

AÙB

\A(7)拒取式规则

A®B

ØB

\ØA(8)假言三段论规则

A®B

B®C

\A®C

18构造证明之一——直接证明法例构造下面推理的证明：若明天是星期一或星期三，我就有课.若有课，今天必备课.我今天下午没备课.所以，明天不是星期一和星期三.解

设p：明天是星期一，q：明天是星期三，

r：我有课，s：我备课推理的形式结构为前提：(pÚq)®r,r®s,Øs

结论：ØpÙØq

19直接证明法(续)证明①r®s

前提引入②Øs

前提引入③Ør①②拒取式④(pÚq)®r

前提引入⑤Ø(pÚq)③④拒取式⑥ØpÙØq⑤置换编程实践作业根据推理理论，开发医疗专家系统，可以3-4人分组完成，比较系统的智能化水平。可以利用PyKe、PyClips库，或者自己开发推理引擎。如何实现有界面的？医疗诊断专家系统优化方向给出控制台的程序，对医疗专家系统进行优化，使系统更加智能好用，参考以下方向：1、增加规则库2、增加诊断建议3、使用rule-engine，PyKe、PyClips等推理引擎，比较不同情况4、使用界面实现输入输出推荐用rule-engine引擎#!/usr/bin/envpython3importrule_enginefromrule_engineimportRule,Context,SymbolResolutionErrorclassMedicalExpertSystem:def__init__(self):#初始化系统信息self.patient_data={}self.diagnoses=[]#定义所有可能的症状self.symptoms=["发烧","咳嗽","流鼻涕","喉咙痛","打喷嚏","头痛","肌肉疼痛","疲劳","呕吐","腹泻","胃痛","呼吸困难","胸闷","皮疹","关节疼痛"]#定义疾病知识库self.diseases={"普通感冒":{"rule":"咳嗽and流鼻涕and喉咙痛and打喷嚏andnot呼吸困难andnot胸闷","description":"普通感冒是一种病毒感染，通常影响上呼吸道，症状包括咳嗽、流鼻涕等。","recommendation":"多休息，多喝水，可服用非处方感冒药缓解症状。如症状持续超过一周，请就医。"},"流感":{"rule":"发烧and咳嗽and头痛and肌肉疼痛and疲劳","description":"流感是由流感病毒引起的急性呼吸道传染病，症状通常比普通感冒更严重。","recommendation":"建议休息，补充水分，可使用抗病毒药物。如出现高烧不退或呼吸困难，请立即就医。"},"肠胃炎":{"rule":"呕吐and腹泻and(胃痛or发烧)","description":"肠胃炎是胃肠道的炎症，通常由病毒或细菌感染引起，表现为呕吐和腹泻。","recommendation":"补充水分防止脱水，避免刺激性食物。如呕吐腹泻严重或持续超过24小时，请就医。"},"过敏反应":{"rule":"流鼻涕and打喷嚏and皮疹andnot发烧","description":"过敏反应是免疫系统对某些物质的过度反应，常见症状包括皮疹、打喷嚏等。","recommendation":"避免接触过敏原，可服用抗组胺药物缓解症状。如出现严重反应，请立即就医。"},"肺炎":{"rule":"发烧and咳嗽and呼吸困难and胸闷","description":"肺炎是肺部的感染，可能由细菌、病毒或真菌引起，需要及时治疗。","recommendation":"这可能是严重的疾病，请立即就医进行诊断和治疗。可能需要抗生素或其他药物。"},"关节炎":{"rule":"关节疼痛and(肌肉疼痛or疲劳)andnot发烧andnot咳嗽","description":"关节炎是关节的炎症，可能导致疼痛和肿胀，通常不伴随呼吸道症状。","recommendation":"建议休息，避免过度使用受影响的关节。如症状持续或加重，请咨询医生进行进一步评估。"}}#编译所有规则piled_rules=self._compile_rules()def_compile_rules(self):"""编译所有诊断规则"""compiled={}fordisease,infoinself.diseases.items():try:#编译规则rule=Rule(info["rule"])compiled[disease]={"rule":rule,"description":info["description"],"recommendation":info["recommendation"]}exceptrule_engine.errors.RuleSyntaxErrorase:print(f"规则编译错误（{disease}）:{e}")returncompileddefcollect_patient_data(self):"""收集患者症状数据"""print("\n请回答以下症状是否存在（是/否）：")forsymptominself.symptoms:whileTrue:response=input(f"-您有{symptom}吗？").strip().lower()ifresponsein["是","y","yes"]:self.patient_data[symptom]=Truebreakelifresponsein["否","n","no"]:self.patient_data[symptom]=Falsebreakelse:print("请输入'是'或'否'")returnself.patient_datadefdiagnose(self):"""根据患者数据进行诊断"""self.diagnoses=[]#创建上下文context=Context(default_value=False)#应用每条规则进行诊断fordisease,infoinpiled_rules.items():try:#检查规则是否满足ifinfo["rule"].evaluate(self.patient_data,context=context):self.diagnoses.append({"disease":disease,"description":info["description"],"recommendation":info["recommendation"]})exceptSymbolResolutionError:#如果有未定义的符号（症状），跳过这条规则continuereturnself.diagnosesdefrun(self):"""运行专家系统"""print("="*60)print("基于rule-engine的医疗专家诊断系统")print("注意：本系统仅提供参考，不能替代专业医生的诊断")print("="*60)#收集患者数据self.collect_patient_data()#显示收集到的症状print("\n您报告的症状：")forsymptom