离散数学及其应用重要名词中英对应以及重要概念解释与举例.pdfVIP

离散数学及其应用重要名词中英对应以及重要概念解释与举例

1TheFoundations:LogicandProofs（逻辑与证明）

1.1PropositionalLogic（命题逻辑）

Propositions（命题）——declarativesentencethatiseithertrueorfalse,butnotboth.判断性语句，

正确性唯一。

TruthTable（真值表）

Conjunction（合取，“与”，and），Disjunction（析取，or，“相容或”），Exclusive（异或），

Negation（非，not），Biconditional（双条件，双向，ifandonlyif）

TranslatingEnglishSentences

1.2PropositionalEquivalences（命题等价）

Tautology（永真式、重言式），Contradiction（永假式、矛盾式），Contingency（偶然式）

LogicalEquivalences（逻辑等价）——Compoundpropositionsthathavethesametruthvaluesin

allpossiblecasesarecalledlogicalequivalent.（真值表相同的式子，p-q是重言式）

LogicalEquivalences——Page24

Disjunctivenormalform(DNF，析取范式)

Conjunctivenormalform(CNF，合取范式)见Page27～29

1.3PredicatesandQuantifiers（谓词和量词）

Predicates——谓词，说明关系、特征的修饰词

Quantifiers——量词

ØUniversalQuantifier(全称量词))

全部满足

ØExistentialQuantifier(存在量词)$

至少有一个

BindingVariables(变量绑定，量词作用域与重名的问题)

LogicalEquivalenceInvolvingQuantifiers

NegatingQuantifiedExpressions(量词否定表达：否定全称=存在否定，否定存在=全程否定)

TranslatingfromEnglishintoLogicalExpressions(自然语句转化为逻辑表达)

UsingQuantifiersinSystemSpecifications

ExamplesfromLewisCarrol——全称量词与条件式(p-q)搭配，存在量词与合取式搭配。

1.4NestedQuantifiers（量词嵌套）Page5912、1313

$x$yP(x,y)Û$y$xP(x,y)$x$yP(x,y)Û$y$xP(x,y)$x$yP(x,y)Û$y$xP(x,y)$x$yP(x,y)Û$y$xP(x,y)$x$yP(x,y)Û$y$xP(x,y)$x$yP(x,y)Û$y$xP(x,y)$x$yP(x,y)Û$y$xP(x,y)$x$yP(x,y)Û$y$xP(x,y)$x$yP(x,y)Û$y$xP(x,y)$x$yP(x,y)Û$y$xP(x,y)

$y$xP(x,y)$y$xP(x,y)

$x$yP(x,y)

Prenexnormalform(PNF前束范式)：所有量词变换到最前面，否定变换到后面。

1.5RulesofInference(推理规则)

ValidArgumentsinPropositionnalLogic(命题逻辑中的正确论点)

Premises(前提)——allbutthefinalpropositionintheargument

Conclusion(结论)

RulesofInferenceforPropositionnalLogic

Page66～67，证明方法及过程示范

Resolution(归结):((p∨q)∧(┐p