判断以下符号串是不是公式
判断以下符号串是不是公式：
(P →(Q ←R )) (⌝Q ∨(P →⌝(P ∧(Q R ))))
解：对于一个不包含联结词的符号串，我们很容易判断它是否是公式，
对于一个包含联结词符号串，我们使用以下的办法：
（1）找出主联结词：
所谓主联结词指的是一个公式最后形成所使用的联结词（注意这个联结词的使用
是符合规则的）。
举例：G ∧H ，G ∨H ，﹁（G ∧H ）的主联结词分别是∧，∨，﹁。
假如上述符号串是公式，那么它的主联结词是。
如果不能找到符合规则的主联结词，说明这个符号串不是公式。如P ﹁Q.
（2）将主联结词剥离掉，再找出主联结词剥离后形成的一个或两个新符号串的主联结词。
同上，我们也是先假定这（些）新符号串是公式，再去找它（们）的主联结词。相应地，我们去掉新符号串最外层的括号（如果有的话）。
如此循环往复，直到所有的形成的新符号串是原子，这说明这个符号串是公式。 如果其中某个形成的新符号串即不是原子，也无法找到合乎规则的联
结词，那么这说明整个符号串不是公式。
(P →(Q ←R )) (⌝Q ∨(P →⌝(P ∧(Q R ) ) ) )
P →(Q ←R ) ⌝Q ∨(P →⌝(P ∧(Q R ) ) )
P Q R ⌝Q P →⌝(P ∧(Q R ))
Q R Q P ⌝(P ∧(Q R ))
P ∧(Q R )
P Q R
Q
注：五种逻辑联结词的优先级如下：﹁，(∧，∨) ，→，
所以﹁P → Q ∧P Q 表示 (﹁P →( Q∧P)) Q
定理1：任给可数无穷多个集合A 0,A 1, …,A n , …，其中每一个A （i i 是自然数）也是可数无穷的。则n
证明：我们要证明中n
A 0：a 00,a 01,a 02,a 03, …,a 0m , …
A 1：a 10,a 11,a 12,a 13, …,a 1m , …
A 2：a 20,a 21,a 22,a 23, …,a 3m , …
…… ……
A n ：a n0,a n1,a n2,a n3, …,a nm , …
…… ……
现在我们可以可以用斜线法将n
a 00→
a 01→ a10→
a 02→ a11→ a20→
a 03→ a12→ a21→ a30→ ⋃⋃⋃
a 04→ a13→ a22→ a31→ a40→
……
n
⋃函数f ：n
f(n,m)=((n+m)+3n+m)/2，其中n 和m 是a nm 的下标。易证f 是双射。
定理2：令L 是可数无穷的，且令A 是L 中符号构成的所有有穷串的集合。则A 是可数无穷的。
证明：任给1≤n
显然A n 是可数无穷的。所以，我们可以枚举的A n 元素如下：
A n ：a n0,a n1,a n2,a n3, …,a nm , …
令A 0＝{}，则A 就是⋃A n ，所以，我们n
将它们排列如下：
A 0：
A 1：a 10,a 11,a 12,a 13, …,a 1m , …
A 2：a 20,a 21,a 22,a 23, …,a 3m , …
…… ……
A n ：a n0,a n1,a n2,a n3, …,a nm , …
…… ……
显然对A 1, …,A n , …中的元素我们可以利用上述给出的枚举法。于是我们可以加上A 0中的元素“”，根据前面一样的方法，可证明A 是可数无穷的。