“内容整理自：1、傅彦版《离散数学及其应用》；2、电子科技大学王丽杰老师的授课：https://www.bilibili.com/video/av2658466
“仅为学习所用，若侵权，请联系删除
“真值表能够方便的给出公式的真值情况，因此对于给定公式的判定问题总是有解的，但真值表的规模随命题变元的数量呈指数形式增长.
“另外，对于同一个命题公式可以有不同的表达形式，而不同的表达形式可以显示出不同的特征，而这些特征又可以显示出从某一角度来说极为重要的性质，为此，将引入命题公式的一种标准形式—范式，范式给各种千变万化的公式提供了一个统一的表达形式，同时，范式的研究对命题演算的发展起到了极其重要的作用，例如，要判断两个命题公式是否等价及判断一个公式是永真、永假，都将由公式的范式来解决.另外，在逻辑理论中判断公式的一些性质，或者在论证命题的完整性时都要用到范式，同时，范式在工程技术中的线路设计、自动机理论与人工智能方面等也有极其重要的作用.
范式引入
命题变元或命题变元的否定称为文字(literal)；
有限个文字的析取称为析取式，也称子句(clause)；
- 子句和短语的区别很容易理解，子句比短语范围大，而析取也是比短语的范围大
有限个文字的合取称为合取式，也称短语(phrase);
- 由于是有限个，1个也是有限个，故文字也是简单的子句和短语
P与称为互补对.
范式定义
有限个子句的合取式称为合取范式(conjunction normal form);
有限个短语的析取式称为析取范式(disjunction normal form).
几种情况?：
1、P，是文字、短语、子句、析取范式、合取范式.
- 当P视为子句时，它也是合取范式；当P视为短语时，它也是析取范式；同理.
2、是子句、合取范式、析取范式，而是子句、合取范式.
- 当P、Q、单独看做短语时，它也是析取范式；但若加了括号，不可再拆分为三个短语的析取，故加了括号时不是析取范式.
3、是短语、合取范式、析取范式，而是短语、析取范式.
- 和上面同理，当加了括号时，不可再拆分成三个子句的合取，故不是合取范式.
4、等既不是析取范式也不是合取范式，但转换为后既是析取范式也是合取范式.
- 析取范式要求是短语的析取，但不是短语;合取范式要求是子句的合取，但P与之间不是合取联结词.
范式存在定理
总结
范式关注的是命题公式的当前书写形式；
析取范式、合取范式仅含联结词集{}，且否定联结词仅出现在命题变元之前.
范式存在定理
定理：对于任意命题公式，都存在与其等价的析取范式和合取范式.
求范式的步骤?：
1、将公式的蕴含、等价联结词，用取代(通过基本等价公式中的蕴含式和等价式)；
2、将否定联结词移到各个命题变元的前端，并消去多余的否定号(通过基本等价公式中的双重否定律和德摩根律)；
3、利用分配律，将公式化为一些合取式的析取，或化为一些析取式的合取.
例子?：
范式与真值
命题公式的析取范式可用指出公式何时为真，而合取范式可以指出公式何时为假，从而能够替代真值表；
命题公式的范式表达并不唯一，比如加个括号、析取或合取自身....
一般而言，求解范式时，需要进行最后的化简步骤.
主范式引入
“由于范式的不唯一性，给研究问题带来了不便，因此对构成范式的子句或短语进一步规范化，从而形成唯一的主析取范式和主合取范式.
极小项与极大项
在含有n个命题变元P1,P2,P3，...，Pn的短语或子句中，若每个命题变元与其否定不同时存在，但二者之一恰好出现一次且仅一次，并且出现的次序与P1,P2,P3，...，Pn一致，则称此短语或子句为关于P1,P2,P3，...，Pn的一个极小项或极大项.
顾名思义，极小项对应短语即合取式，极大项对应子句即析取式.
一般来说，若有n个命题变元，则有2n个不同的极小项和2n个不同的极大项.
极小项的性质
没有两个不同的极小项是等价的；
每个极小项只有一组成真赋值，因此可用于给极小项编码，编码规律为：命题变元与1对应，命题变元的否定与0对应.
- 因为是成真赋值，命题变元的否定用0对应，则其真值为1了(因为取反了)
极大项的性质
没有两个不同的极大项是等价的；
每个极大项只有一组成假赋值，因此可用于给极大项编码，编码规律为：命题变元与0对应，命题变元的否定与1对应.
- 因为是成假赋值嘛
极大项与极小项的转换
(i≠j)
- 容易理解，因为极小项是合取式，故它与另一个极小项合取，一定会出现某一个命题变元与该命题变元的否定的合取，因此为0；极大项同理，会出现某一个命题变元与该命题变元的否定的析取，因此为1.
- 某个编码的极小项为真，该编码对应的极大项为假，二者互为否定.
- 由于极小项为成真赋值，所以全部极小项的析取一定为真(永真公式)；全部极大项的合取一定为假(永假公式).
主析取范式和主合取范式
定义
在给定的析取范式中，若每一个短语都是极小项，且按照编码从小到大的顺序排序，则称该范式为主析取范式(principal disjunctive normal form).
在给定的合取范式中，若每一个子句都是极大项，且按照编码从小到大的顺序排序，则称该范式为主合取范式(principal conjunctive normal form).
如果一个主析取范式不包含任何极小项，则称主析取范式为“空”；如果一个主合取范式不包含任何极大项，则称主合取范式为“空”.
定理
任何一个公式都有与之等价的主析取范式和主合取范式.
主范式求解步骤?：
1、先求出该公式对应的析取范式和合取范式；
2、消去重复出现的命题变元、矛盾式和重言式；
3、若析取(合取)范式的某一个短语(子句)缺少某一个命题变元，则把它添上，手段为析取1(该命题变元与其否定的析取)或合取0(该命题变元与其否定的合取)；
4、利用幂等律将重复的极小项和极大项合并，并利用交换律将极小项或极大项按编号从小到大排序.
求解
方法一、利用公式转换法
方法二、真值表技术
如上图?，由于G在某个解释下为真，那么对应的主析取范式至少要有某一项短语为真，所以选择该解释下对应的极小项；同理，当G在某个解释下为真，那么对应的主合取范式一定不能有某一项子句为假，否则由于是合取，G就为假了，所以当某个解释是成真赋值时，主合取范式不能取该解释对应的极大项，而应选择使得公式为假的解释对应的极大项，因此得出下面结论?：
列出真值表，选出公式的真值为真的所有的行，找到该行解释对应的极小项，将这些极小项进行析取即可得到主析取范式；
列出真值表，选出公式的真值为假的所有的行，找出该行解释对应的极大项，将这些极大项进行合取即可得到主合取范式.
范式的相互转化
- 由真值表技术可知，对于任何一个命题公式，主析取范式所使用的极小项的编码和主合取范式所使用的极大项的编码是“互补”关系，因此我们可以求出其中一个，然后根据公式特点直接写出另一个
“注意：利用主析取范式求主合取范式或利用主合取范式求主析取范式时，注意时求""的主析取范式的否定或""的主合取范式的否定即双重否定，而非直接求公式G的否定
主范式的应用
“说了这么多，那么主范式有什么用呢？如下?：
主范式可用于了解公式的真值情况，进行公式类型的判断以及等价关系的判定：
如果主析取范式包含所有的最小项，则该公式为永真公式；
如果主合取范式包含所有的最大项，则该公式为永假公式；
若两个公式具有相同的主析取范式或主合取范式，则两公式等价；
应用举例?：
往期回顾
【离散数学 | 数理逻辑】数理逻辑起源
【离散数学 | 数理逻辑之命题逻辑】命题及命题联结词
【离散数学 | 数理逻辑之命题逻辑】命题公式、解释与真值表