命题逻辑
一、命题逻辑与真值函数
命题逻辑：（又称命题演算、布尔逻辑）是最简单的一种形式逻辑系统。
主要研究对象：命题（常用p,q,r…代表任意命题即命题变元）每个命题可能为真，也可能为假（通常用1/0或T/F或T/⊥表示）。
真值函数：在真假值集合上定义一些运算函数，一个n元真值函数是从{0,1}^n到{0,1}的映射。
连接符/词（connectives）：真值函数的名字
常见真值函数：“与”（合取，^），“或”（析取，V），“非”（否定，﹁），“蕴涵”（记为‘→’），“等价”（记为‘↔’），“异或”（记为‘⊕’）
注意，这些连接词描述的是命题之间的逻辑关系，而不是因果关系。它们通过对命题的真值进行组合来构建复合命题。因果关系通常涉及事件或因果链的因果联系，而在命题逻辑中，只关注命题的真值。
例如，在“蕴涵”（→）中，如果P蕴涵Q为真，这并不意味着P是Q的因果条件，而只表示在P为真的情况下，Q也为真。“等价”只表示二者具有相同的真值，不关心具体真值。“异或”表示了“排他性或互斥”的关系。当且仅当两个命题中有一个为真时，异或的结果为真；如果两个命题都为真或都为假，异或的结果为假。
当命题变元的个数n>2时，使用真值表（truth table）进行运算处理；当命题变元的个数为n时，真值表一般有2^n行；真值表左边是变元的各种可能取值，右边是运算结果。
命题逻辑公式：命题变元和连接符在一定规则下形成命题逻辑公式。
- 命题变元是命题逻辑公式（原子公式）
- 若ȹ是公式，则﹁ȹ也是公式
- 若ȹ1和ȹ2是公式，则（ȹ1*ȹ2）也是公式
- 只由上面三条规则生成的表达式是命题逻辑公式
(此处‘*’是指任意二元连接符)
连接符的优先级问题：﹁ > (^或V) > (→或↔)
二、命题逻辑相关定义梳理总结
真值赋值（truth assignment）：从命题变元集合到真假值集合的函数叫真值赋值，简称赋值，又叫解释。如果这个函数没有完全定义，则其被称为部分赋值。
如果有一个赋值使公式ȹ的值为1，那么命题逻辑公式ȹ是可满足的.使它得到这个满足的赋值就是ȹ的一个模型(model)。
重言式（tautology）：如果对于任何赋值，公式ȹ的值都为1，又称为永真公式。
等值定义：如果对于任何赋值，公式ȹ1和ȹ2都具有相同的真假值，那么称这两个公式为等值，记为ȹ1=ȹ2.
运算定义：满足代数运算的交换律、结合律和分配律以及特殊的德摩根律
德摩根律：
﹁(P^Q)↔(﹁P)V(﹁Q)
﹁(PVQ)↔(﹁P)^(﹁Q)
6.完备性定义：连接符集合M是完备的，任何n元连接符都能由M中的连接符定义（n为正整数）。
常见完备集：{﹁,V},{﹁,^},{﹁,→}和{﹁,V,^}。
7.称原子公式或其否定为文字（literal），原子公式本身为正文字，而原子公式的否定为负文字。若干个文字的析取构成子句（clause），其长度是所含文字的个数；只有一个文字的子句称为单子句（unit clause）,没有文字的子句称为空子句（empty clause）。
子句的可满足性：一般来说，文字越多，子句越易满足；极端情形而言，空子句不可满足。
8.互补的定义：原子公式p与其否定﹁p互补，又称p的补为﹁p。
9.合取范式与析取范式：
合取范式（conjunctive normal form,简写CNF）,其一般形式：F = c1∧c2∧...∧cm，这里的c是若干文字的析取。
析取范式（disjunctive normal form,简写DNF），其一般形式为：F = c1Vc2V...Vcm，这里的c是若干文字的合取。
定理：对任意公式，都有与之等值的合取范式和析取范式。
可满足性问题（SAT）
可满足性(SAT)：考虑一个由布尔变量、括号和以下运算符构成的布尔表达式： AND（连接）、OR（析取）和 NOT（否定）。在这里，布尔表达式是分句的连接，分句是字面的析取。字面是布尔变量或其否定。问题是找到所有变量的布尔标签，使给定表达式为真，或者确定不存在这样的标签赋值。
也可以这么描述：对于一个确定的逻辑，是否存在一种输入使得输出为真。
可满足性（英语：Satisfiability）是用来解决给定的真值方程式，是否存在一组变量赋值，使问题为可满足。布尔可满足性问题（Boolean satisfiability problem；SAT ）属于决定性问题，也是第一个被证明属于NP完全的问题。
最大独立集问题（MIS）
最大独立集(MIS)：给定一个无向图，找出其中没有两条边相连的最大顶点子集。
独立集（英语：Independent set）是图论中的概念。一个独立集（也称为稳定集）是一个图中一些两两不相邻的顶点所形成的集合。
最小顶点覆盖问题（MVC）
最小顶点覆盖(MVC)：给定一个无向图，找出最小的顶点子集，使得图中的每条边都至少与所选集合中的一个顶点相连。
最大团问题（MC）
最大团(MC)：给定一个无向图，找出形成一个小群的最大顶点子集。
最大团、最大独立集和最小顶点覆盖这三个组合优化问题在理论上是等价的。
特别的，MVC、MC 和 SAT 问题都可以表示为 MIS 问题的实例
MVC（最小顶点覆盖）和 MIS（最大独立集）互补关系：
给定一个图，MVC 是指在图中选择尽可能少的顶点，使得每条边都至少与其中一个选定的顶点相邻。而 MIS 是指在图中选择尽可能多的顶点，使得这些顶点之间没有直接相连的边。上述引用提到，MVC 和 MIS 是互补的，意味着一个图的最小顶点覆盖与其最大独立集的补集相等。换句话说，一个顶点集合是独立集，当且仅当它的补集是顶点覆盖。
MC（最大团）和 MIS（最大独立集）的关系：
最大团是图中的一个完全子图（即子图中的任意两个顶点都相邻），且无法再添加其他顶点使其依然保持完全子图的性质。与之对应的是最大独立集，它是图中顶点的一个集合，其中任意两个顶点都不相邻。引用中提到，最大团与其补图的最大独立集是一致的，也就是说一个图的最大团等于其补图的最大独立集。
SAT（布尔可满足性问题）和 MIS（最大独立集）的关系：
SAT 是一个经典的计算机科学问题，它涉及布尔逻辑中的命题和变量，判断是否存在一组变量的赋值使得整个布尔表达式为真。引用中描述了如何将 SAT 实例转换为图的形式：每个子句中的文字（变量或其否定形式）在图中对应一个顶点，同一个子句中的文字相邻（有边相连），而在不同子句中的文字之间也有边相连（表示它们不能同时为真）。然后，如果能找到一个与子句数目相等的最大独立集，就意味着找到了使得整个 SAT 公式为真的变量赋值，这也就是 SAT 实例的解。这是因为在最大独立集中，图中的每个顶点都不相邻，而在 SAT 图中，不相邻的顶点对应于可以同时为真的文字。
总结：图论中的顶点覆盖、最大独立集、最大团可与 SAT（布尔可满足性问题）联系起来，它们在某些条件下可以互相转化。
