3-第一章命题逻辑.ppt

第一章命题逻辑，1.1命题及其表达式1.2合取1.3命题公式和翻译1.4真值表和等价公式1.5对偶和蕴涵1.7范例1.8推理理论，命题逻辑，第一章命题逻辑，1.1命题及其表达式1.2合取1.3命题公式和翻译1.4真值表和等价公式1.5重复公式和蕴涵1.7对偶和范例1.8推理理论，命题逻辑，第10页，定义1(2)如果a是一个组合公式，那么( A)也是一个组合公式。(3)如果A和B是组合公式，(AB)，(AB)，(AB)，(AB)也是组合公式。(4)当且仅当由(1)至(3)获得的包含命题自变量、连接词和括号的符号串是复合公式。1.3命题公式和翻译，第10页，1.3命题公式和翻译，示例：判断下列公式是否是合适的公式，第12页，示例1中给出的真值表。练习：给出下列命题公式的真值表。(1)(2)、1.4真值表和等价公式，由n个命题自变量组成的命题公式有2n个赋值。定义1-4.2将A和B设置为两个命题公式。如果由A和B形成的双重条件AB是同义反复，那么A和B是等价的，并被记录为AB。第12页，1.4真值表和等价公式，第13页，1.4真值表和等价公式，定义1-4.3如果x是公式a的一部分，并且x本身是公式，那么x是公式a的子公式，定理1-4.1让x是公式a的子公式如果XY，如果a中的x被y替换，则获得的公式b等价于公式a，即a b。在第16页，复习练习1:简化以下公式。(1)(2)，第一章命题逻辑，1.1命题及其表达式1.2连词1.3命题公式和翻译1.4真值表和等价公式1.5重复和隐含公式1.7对偶性和范例1.8推理理论，命题逻辑，第16页，1.7对偶性和范例，定义1-7.1在给定的命题公式中，如果它只使用连接词，连接词被替换，并且如果有特殊变量F和T，则产生的公式被称为原始公式示例1首先，双重形式。参见第30页定理7.1-7.2，第17页定理17，第17页定理1.7对偶和范式。第二，范式，定义1-7.2命题公式被称为合取范式，当且仅当它有一种形式：所有这些都是由命题自变量或它们的否定构成的析取形式。合取范式的特征：(1)不出现和(2)否定符号出现在论元之前(3)整体上是合取公式(4)每个合取项都是析取公式(5)每个合取项只包含命题论元或其否定。在第18页，1.7二元性和范式，2。正规形式，定义1-7.3一个命题公式被称为析取正规形式，当且仅当它有一个形式：所有这些都是由命题参数或它们的否定组成的合取形式。析取范式的特征是：(1)它不出现，(2)负号出现在论元之前，(3)它是析取公式，(4)每个析取项都是合取公式，(5)每个析取项只包含命题论元或其否定。第19页，1.7二元性和范式，2。范式，例2:判断下列类型是析取范式还是合取范式。第20页，1.7二元性和范式，2，范式，例3:为合取范式。例4:为析取范式。合取范式和析取范式的还原步骤：见本书第31页、第20页，1.7二元性和范式；3，主范式，主析取范式的归约步骤：见本书第36页，(1)主析取范式的每个析取项中的所有变量必须对每个变量出现一次(命题变量或其否定)，第20页，1.7对偶与范式，3，主范式，定义1-7.4n个变量的合取形式，称为布尔合取或次项，其中每个变量及其否定定义1-7.5对于给定的命题公式， 如果有一个等价公式只由小项的析取组成，那么这个等价公式就叫做原公式的主析取范式。 定理1-7.3在真值表中，对应于公式赋值的次项的析取，该公式，主合取范式的约简步骤：见本书第38页，(2)主合取范式的每个合取项中的所有参数对于每个参数(命题参数或其否定)必须出现一次，第20页，1.7对偶和范式，以及第3页，主范式，定义1-7.6n个参数的析取表达式，称为布尔析取或大项，其中每个参数及其否定不能同时存在，但两者必须出现且只出现一次。定义1-7.7对于给定的命题公式，如果有一个等价公式只由大项的合取组成，那么这个等价公式被称为原公式的主合取范式。定理1-7.3在真值表中，公式的真值是对应于T赋值的主要项的合取，即公式的主合取范式。第21页，1.7二元性和范式，例9:通过真值表获得的主连接范式。例如，10:要求一个真正的任务。(1，133，360)一个科研机构必须