一、命题公式
二、重言式、矛盾式，可满足式
命题公式及分类
重点：(1) 掌握命题公式的定义及公式的真值表。
(2) 掌握重言式和矛盾式的定义及使用真值表进行判断。
通俗地说，命题公式是由命题常项，命题变项，联结词，括号等组成的字符串。以下给出递归定义。
1、定义：合式公式(即命题公式，简称为公式)
(1) 单个命题常项或变项 
是合式公式。
(2) 若 
是合式公式，则 
也是合式公式。
(3) 若 
是合式公式，则 
也是合式公式。
(4) 只有有限次地应用(1)—(3)组成的符号串才是合式公式。
规定：公式中最外层的括号，及
的括号可省略。
例1、判断以下字符串中哪些是命题公式。
(1) 
(2) 
(3) 
(4) 
(5) 
(6) 
解：(1)、(2)、(6)是公式，(3)、(4)、(5)不是。
2、命题公式的层次。
(1) 若
是单个命题(常项或变项)，如 
等，则称
为0层公式。
(2) 称
是 
层公式是指符合下列情况之一：
① 
， 
是 
层公式。
② 
，其中 
分别为 
层和 
层公式，且 
。
③ 
，其中
层次同②。
④ 
，其中
层次同②。
⑤ 
，其中
层次同②。
(3) 若
的最高层次为 
，则称
为 
层公式。
例2、 
为5层公式。
3、真值表。
公式
的解释或赋值——给
中所有的命题变项 
指定一组真值，称对
的一个赋值(或解释)。
如公式 
，110( 
，按字典序)为
的成假赋值，111，011，010……等是
的成真赋值。
含 
个命题变项的命题公式，共有 
组不同赋值。
的真值表——指
在所有赋值之下取值列成的表。
构造
的真值表步骤：
(1) 列出所有命题变项的所有赋值(
个，掌握 
)。
(2) 从低到高写出
的各层次。
(3) 对应每个赋值，计算各层次的值，直至整个公式。
例3、求下列命题公式的真值表。
(1) 
(2) 
(3) 
解：(1)
|
(2)
|
(3)
|
1、定义：设
为一个命题公式。
(1) 若
在它的各种赋值下取值均为真，则称
为重言式或永真式。
(2) 若
在它的各种赋值下取值均为假，则称
为矛盾式或永假式。
(3) 若
至少存在一组赋值是成真赋值，则称
为可满足式。
2、判定方法 (此处仅限真值表法，以后还会有其它办法)
真值表法：在一个公式
的真值表中，由最后一列的值而定，全为1，即重言式，全为0，即矛盾式，既有0又有1，即非重言式的可满足式。例3中的(1)为矛盾式，(2)、(3)为可满足式(非重言式)，另外，大家可考虑 
，即(1)的否定式为重言式。
例4、给定命题公式如下，请判断哪些是重言式，哪些是矛盾式，哪些是可满足式？
(1) 
(2) 
(3) 
(4) 
(5) 
(6) 
(7) 
(8) 
(9) 
(10) 
解：列出各题真值表如下(步骤简略)
|
|
(1)、(2)、(5)、(6)、(9)为重言式；
(3)、(8)为矛盾式；
(4)、(7)、(10)及以上的重言式均为可满足式。