判断以下符号串是不是公式

《判断以下符号串是不是公式》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、判断以下符号串是不是公式：解：对于一个不包含联结词的符号串，我们很容易判断它是否是公式，对于一个包含联结词符号串，我们使用以下的办法：（1）找出主联结词：所谓主联结词指的是一个公式最后形成所使用的联结词（注意这个联结词的使用是符合规则的）。举例：GH，GH，﹁（GH）的主联结词分别是，，﹁。假如上述符号串是公式，那么它的主联结词是。如果不能找到符合规则的主联结词，说明这个符号串不是公式。如P﹁Q.（2）将主联结词剥离掉，再找出主联结词剥离后形成的一个或两个新符号串的主联结词。同上，我们也是先假定

2、这（些）新符号串是公式，再去找它（们）的主联结词。相应地，我们去掉新符号串最外层的括号（如果有的话）。如此循环往复，直到所有的形成的新符号串是原子，这说明这个符号串是公式。如果其中某个形成的新符号串即不是原子，也无法找到合乎规则的联结词，那么这说明整个符号串不是公式。注：五种逻辑联结词的优先级如下：﹁，(，)，，所以﹁PQPQ表示(﹁P(QP))Q定理1：任给可数无穷多个集合A0,A1,…,An,…，其中每一个Ai（i是自然数）也是可数无穷的。则An也是可数无穷的。证明：我们要证明中An的元素与

3、w中的元素一一对应。用行列式枚举A0,A1,…,An,…的元素如下：A0：a00,a01,a02,a03,…,a0m,…A1：a10,a11,a12,a13,…,a1m,…A2：a20,a21,a22,a23,…,a3m,……………An：an0,an1,an2,an3,…,anm,……………现在我们可以可以用斜线法将An中的元素枚举如下：a00®a01®a10®a02®a11®a20®a03®a12®a21®a30®a04®a13®a22®a31®a40®……An中元素anm所对应的自然数，可以

4、用函数f：An®wf(n,m)=((n+m)2+3n+m)/2，其中n和m是anm的下标。易证f是双射。定理2：令L是可数无穷的，且令A是L中符号构成的所有有穷串的集合。则A是可数无穷的。证明：任给1£n}，则A就是An，所以，我们将它们排列如下：A0：<>A1：a10,a11,a12,a13,…,a1m,…A2：a20,a21,a2

5、2,a23,…,a3m,……………An：an0,an1,an2,an3,…,anm,……………显然对A1,…,An,…中的元素我们可以利用上述给出的枚举法。于是我们可以加上A0中的元素“<>”，根据前面一样的方法，可证明A是可数无穷的。