【定义1.3】命题公式A的复杂程度deg(A)定义为：
[1]. 如果A是原子项，则deg(A) = 0；
[2]. deg(ØA) = deg(A) + 1;
[3]. deg(A * B) = max(deg(A), deg(B)) + 1，其中*代表Ù、Ú、®、«之一。
此定义等价于教材p11的定义1.7。只不过我们在这里给出的是递归定义。使用归纳法，我们可证明下面定理：
【定理1.4】deg(A)小于等于命题公式A中的命题联结符号的数目。
【证明】根据命题公式A的结构进行归纳证明：
1. 归纳基：如果A是原子项，则根据定义1.3有deg(A) = 0，显然定理成立。
2. 归纳步：假设定理对于命题公式A和B成立（归纳假设），记命题公式A中的命题联结符号数为Sym(A)，即有deg(A) £ Sym(A)和deg(B) £ Sym(B)。那么由于deg(ØA) = deg(A) + 1，而Sym(ØA) = Sym(A) + 1，所以定理对于ØA也成立。同样由于deg(A * B) = max(deg(A), deg(B)) + 1，而Sym(A * B) = Sym(A) + Sym(B) + 1，因而有deg(A * B)£ Sym(A * B)，从而定理对所有的命题公式都成立。
【定理1.5】任意命题逻辑公式A中出现相等数目的左右园括号，实际上，左右园括号的个数都等于A中的命题联结符号数。
【定理1.6】任意命题逻辑公式A具有下列6种形式之一，且只具有其中一种形式：
[1]. A为原子项；[2]. (ØA)[3]. (AÙB)
[4]. (AÚB)[5]. (A®B)[6]. (A«B)
