Sudoku谜题（命题可满足问题）There are 9 X 9 X 9=729Sxyz：第x行第y列的格子里填上数字z.such propositionsN-1 9-1 V2-1 8rye?????A=19=1 2=1 =2+1(8ryz V-8ryi)?????N-1 N-1 V-1 8ryzevery column contains every numberN-1 N2-1 V9=1 Sryeveryrow contains everynumberA2=0 N=0 V2=1 2=1 y=1 8(3i+r)(3j+y)zeachofthenine3X3blockscontainseverynumber11
Sudoku谜题（命题可满足问题） ⚫ sxyz : 第x行第y列的格子里填上数字z. . 11 every row contains every number every column contains every number each of the nine 3 × 3 blocks contains every number There are 9 × 9 × 9 = 729 such propositions ????? ?????
命题逻辑公式的范式为何要“范式”？对于给定公式的判定问题，可用真值表方法加以解释但当公式中命题变元的数目较大时，计算量较大，每增加一个命题变元，真值表的行数要翻倍，计算量加倍4此外，对于同一问题，可以从不同的角度去考虑，产生不同的但又等价的命题公式，即同一个命题可以有不同的表达形式。这样给命题演算带来了一定的困难，因此有必要使命题公式规范化12
命题逻辑公式的范式 ⚫ 为何要“范式”？ ⚫ 对于给定公式的判定问题，可用真值表方法加以解释， 但当公式中命题变元的数目较大时，计算量较大，每增 加一个命题变元，真值表的行数要翻倍，计算量加倍， 此外，对于同一问题，可以从不同的角度去考虑，产生 不同的但又等价的命题公式，即同一个命题可以有不同 的表达形式。这样给命题演算带来了一定的困难，因此 有必要使命题公式规范化。 12
命题逻辑公式的范式一些术语：命题变元或命题变元的否定称为文字有限个文字的析取式称为简单析取式(基本和)有限个文字的合取式称为简单合取式(基本积)：由有限个简单合取式构成的析取式称为析取范式(DNF, Disjunctive Normal From),由有限个简单析取式构成的合取式称为合取范式(CNF,ConjunctiveNormalFrom)。13
命题逻辑公式的范式 ⚫ 一些术语： ⚫ 命题变元或命题变元的否定称为文字； ⚫ 有限个文字的析取式称为简单析取式(基本和)， 有限个文字的合取式称为简单合取式(基本积)； ⚫ 由有限个简单合取式构成的析取式称为析取范式 (DNF，Disjunctive Normal From)， 由有限个简单析取式构成的合取式称为合取范式 (CNF，Conjunctive Normal From)。 13