画鸵萌宠网
文章编号:1007 1385(2003)02 0077 02
数理逻辑在排队论中的应用
梁应仙
(沈阳大学基础课部,辽宁沈阳 110041)
摘 要:在科学研究和工程技术中,排队论(又称搏奕论)有着广泛的应用,本文将数理逻辑,确切
地说是命题逻辑中关于对偶和析取范式、合取范式的理论,应用于排队论中,给出了一个排队论
的解法,从而可以解决生产实践中的相关问题。
关键词:文字;子句;短语;范式
中图分类号:O14文献标识码:A
对偶与范式是命题逻辑中的核心理论,它几
乎涵盖了命题逻辑中的所有概念,是这些概念的
综合运用。这些知识可以用于解决显示现实生活
中的排队论问题。
文字:原子或原子的否定;
子句:有限个文字的析取;
短语:有限个文字的合取;
文字,既是子句,又是短语。
析取范式:有限个短语的析取;
合取范式:有限个子句的合取;
子句和短语,既是析取范式,又是合取范式。
定理:任何一个公式都存在着与之等价的析
取范式和合取范式。
证明:[把一个公式化为析取范式和合取范式
的方法]
第一步 根据P Q=(P※Q)∧(Q※P)和P※Q= ┐ P
∨ Q,
删去公式中的等值 和蕴涵※;
第二步 根据De Morgan律和对合律,将否定
放在原子的前面;
第三步 重复运用分配律,即可将公式化为
与之等价的析取范式和合取范式。
范例1 将公式(┐ P∨ ┐ Q)※(P ┐ Q)化为之等
价的析取范式和合取范式。
[解] (┐ P∨ ┐ Q)※(P ┐ Q)
=(┐ P∨ ┐ Q)※((P※┐ Q)∧(┐ Q※P))
=(┐ P∨ ┐ Q)※((┐ P∨ ┐ Q)∧(Q∨ P))
= ┐(┐ P∨ ┐ Q)∧((┐ P∨ ┐ Q)∧(Q∨ P))
=(P∧ Q)∨((┐ P∨ ┐ Q)∧(Q∨ P))
收稿日期:2003 03 21
作者简介:梁应仙(1963)男,黑龙江尚志县人,讲师
=(P∧ Q)∨((┐ P∧ Q)∨(┐ P∧ P)∨(┐ Q
∧ Q)∨(┐ Q∧ P))
=(P∧ Q)∨(┐ P∧ Q)∨(P∧ ┐ Q) 析取范式
=(P∨ ┐ P∨ P)∧(P∨ ┐ P∨ ┐ Q)∧(P∨ Q∨ P)∧(P∨ Q∨ ┐
Q)∧(Q∨ ┐ P∨ P)∧(Q∨ ┐ P∨ ┐ Q)∧(Q∨ Q∨ P)∧(Q∨ Q∨ ┐
Q)
= P∨ Q 这是子句,既是析取范式,又是合取范
式。
范例2 甲、乙、丙、丁四个人出去参加比赛回
来后,向外部透漏比赛结果。甲说:丙第一,乙第
二;乙说:丙第二,丁第三;丙说:甲第二,丁第四。
已知这三个人说的都是一句真,一句假,并且无并
列情况。则四个人的实际名次如何?
[解] 用C1表示丙第一;用B2表示乙第二;
用C2表示丙第二;用D3表示丁第三;
用A2表示甲第二;用D4表示丁第四;
则因为每个人的话中至少有一个真命题,所
以它们的析取为真命题,进而,这三个真命题的合
取也是真命题。即(C1∨ B2)∧(C2∨ D3)∧(A2∨ D4)是一
个真命题,同时这又是一个合取范式,现将其转化
为析取范式。
T=(C1∨ B2)∧(C2∨ D3)∧(A2∨ D4)
=(C1∧ C2∧ A2)∨(C1∧ C2∧ D4)
∨(C1∧ D3∧ A2)∨(C1∧ D3∧ D4)
∨(B2∧ C2∧ A2)∨(B2∧ C2∧ D4)
∨(B2∧ D3∧ A2)∨(B2∧ D3∧ D4)
= m1∨ m2∨ m3∨ m4∨ m5∨ m6∨ m7∨ m8
因为无并列情况,所以m1、m5、m6、m7均为假命题,又
因为分身乏术,所以m2、m4、m8也是假命题,而该公
式又是一个真命题,所以m3= C1∧ D3∧ A2就一定是
一个真命题,即丙第一,丁第三,甲第二。这样乙
就只能是第四了。
于是得出实际上的比赛名次如下:丙第一,甲
第二,丁第三,乙第四。
范例3 从甲、乙、丙、丁4个人之中派两个人
出去执行任务,按下列3个条件共有几种派法?
如何派?
(1)如果派甲去,那么丙和丁之中至少要派
一;(2)乙和丙不能同时都去;(3)如果派丙去,那
么丁必须留下。
[解] 分别用A、B、C、D表示依次派甲、乙、丙、丁
去,则
根据题意 A※C D,┐(B∧ C)和C※┐ D都是真命题,
于是
T=(A※C D)∧ ┐(B∧ C)∧(C※┐ D)
=(A※(C∧ ┐ D)∨(┐ C∧ D))∧ ┐(B∧ C)∧(C※┐ D)
=(┐ A∨(C∧ ┐ D)∨(┐ C∧ D))∧(┐ B∨ ┐ C)∧(┐ C∨ ┐=(┐ A∧ ┐ B∧ ┐ C)∨(┐ A∧ ┐ B∧ ┐ D)
∨(┐ A∧ ┐ C∧ ┐ C)∨(┐ A∧ ┐ C∧ ┐ D)
∨(C∧ ┐ D∧ ┐ B∧ ┐ C)∨(C∧ ┐ D∧ ┐ B∧ ┐ D)
D)
∨(C∧ ┐ D∧ ┐ C∧ ┐ C)∨(C∧ ┐ D∧ ┐ C∧ ┐ D)
∨(┐ C∧ D∧ ┐ B∧ ┐ C)∨(┐ C∧ D∧ ┐ B∧ ┐ D)
∨(┐ C∧ D∧ ┐ C∧ ┐ C)∨(┐ C∧ D∧ ┐ C∧ ┐ D)
= m1∨ m2∨ m3∨ m4∨ m5∨ m6∨ m7∨ m8∨ m9∨ m10∨ m11∨ m12
=(┐ A∧ ┐ B∧ ┐ C)∨(┐ A∧ ┐ B∧ ┐ D)∨(┐ A∧ ┐ C)
∨(┐ A∧ ┐ C∧ ┐ D)∨(C∧ ┐ B∧ ┐ D)∨(┐ B∧ ┐ C∧ D)∨
(┐ C∧ D)
= m1∨ m2∨ m3∨ m4∨ m6∨ m9∨ m11
因为必须派两个人去,所以m1、m2和m4均为假命
题。
于是,共有下列3种方案:
(1)A、C不去,B、D去;
(2)A、C去,B、D不去;
(3)A、D去,B、C不去。
综上,我们给出了一个用于解决排队论问题
的比较系统的方法。
参考文献:
[1]左教凌,李为坚,刘永才.离散数学[M].上海:上海科学技术文
献出版社,1982,40- 45
[2]李木,李世清,陈春光,刘桂芳.离散数学[M].沈阳:辽宁大学
出版社,1993.33- 38
Application of mathematical logic in queue theory
LIANG Ying xian
(Basic Courses Department,Shenyang University, Laoning Shenyang 110000)
Abstract:By using the theory of standard- formula in mathematical logic, this essay gives a clue to solve the queue
problems.
Keywords:character; basic- sum; basic- product; standard- formula
(上接第83页)W4,这一结果是符合实际情况的,
它为学院对系(部)工作考核提供了理论依据,学
院领导可根据计算结果制定系(部)工作评价指标
体系。
(2)由上述结果可知,对系(部)工作影响较大
的指标有:教学档案管理;教学质量监督;教学改
革等17项指标,我们可把它们列为核心指标。
(3)为了使评价的总分为100分,可将W4乘
100,以此作为各项指标的分值。
(3)为了便于操作,对W4× 100结果进行微
调,并由此制定学院对系(部)工作评价指标体系
(见沈阳航空工业学院系(部)工作评价指标体
系)。
参考文献:
[1]许树柏.层次分析原理[M].天津:天津大学出版社,1988年
[2]姜启源.数学模型[M].北京:高等教育出版社,1988年
[3]赵伟,岳德权.AHP的算法及其比较分析[ J].数学实践与认
识.1995(1):25- 46
Application of AHP method in Department work assessment
SHAN Feng1 SUNZuo an2 CHENG Cong shen3
(1.Shenyang Institute of Aeronautical Engineering,Liaoning Shenyang 110034;2.Shenyang of Electric Power Col-
lege,Liaoning Shenyang 110034;3.Shenyang University,Liaoning Shenyang 110041)
Abstract:AHP method is introduced to assessDepartmentwork in this paper,he solutionsverify thatthe model is ef-
fective.
Keywords:departmentwork assessment; order vector;AHP method
78 沈阳航空工业学院学报 第20卷玲 张立昂
因篇幅问题不能全部显示，请点此查看更多更全内容