4.描述逻辑：可判断性与复杂性.ppt

语义网的逻辑基础LogicalFoundationoftheSemanticWeb主讲:黄智生ZhishengHuangVrijeUniversityAmsterdam,******@:胡伟******@::::可判断性与复杂性2为什么可判定性是重要的?描述逻辑的可判定性描述逻辑的tableau算法计算复杂性理论导论描述逻辑的复杂性讲座3:描述逻辑的可判定性与复杂性Lecture3:::可判断性与复杂性3逻辑研究的几个步骤提出一个逻辑系统(句法,语义,与公理系统)证明其公理系统的正确性(soundness)pleteness)证明其关问题的可判定性(decidability)plexity)(并说明其是否具有易处理性tractability)::可判断性与复杂性4为什么可判定性是重要的?可判定性给出了一个计算上的特征指标,来判定是否存在着一个有效的算法来解决特定的问题。不可判定性则表明寻找解决该类问题的有效算法是徒劳的。::可判断性与复杂性5算法与可判定性AlgorithmandDecidability可判定性(decidability):一个逻辑系统的一个理论(即一个逻辑封闭的公式集)被称为是可判定的,当且仅当存在着一个有效的方法来决定任意一个公式是否被包含在这个理论之中Atheory(setofformulasclosedunderlogicalconsequence)(algorithm)。Aneffectivemethodforcalculatingthevaluesofafunctionisanalgorithm;:::这个定义同上页中的定义有什么不同?::可判断性与复杂性7一些逻辑系统的判定性命题逻辑是可判定的Propositionallogicisdecidable一般来说,一阶谓词逻辑是不可判定的。First-orderlogicisnotdecidableingeneral;inparticular,-orderlogic,::可判断性与复杂性8一些可判定的一阶谓词逻辑Fragment◮戊剖精枚谰成待豁亮蚤任驭景傀态点愉炬凝***: