数理逻辑第一章

命题逻辑的基本概念

命题及符号化

命题：能够判断真假的陈述句
命题的真值：真、假
真命题：真值为真的命题
定义：设p为命题，复合命题“非p”记为$\rceil p$，p为真当且仅当“非p”是假
定义：设p，q为两个命题，复合命题“p并且q”记为$p\wedge$q,$p\wedge$q为真当且仅当p和q都为真
定义设p，q为两个命题，复合命题“p或q”记为$p\vee$q，$p\vee$q为假当且仅当p和q都为假

注意：数理逻辑的析取运算只能表示自然语言里面的“相容或”，自然语言里面的“排斥或”可以写成($p\wedge\rceil$q)$\vee$$(\rceil p\wedge q)$

定义：设p，q为两个命题，复合命题“如过p则q”记为$p\to$q，$p\to$q为假当且仅当p为真q为假

注意：蕴涵运算$p\to$q表示的逻辑关系是q是p的必要条件，p是q的充分条件。

定义：设p，q为两个命题，复合命题“p当且仅当q”记为$p\leftrightarrow$q，$p\leftrightarrow$为真当且仅当p、q都为为假或都为假

注意：$p\leftrightarrow q\Leftrightarrow(p\to q)\wedge(q\to p)$

命题公式及其赋值

基本概念

命题常项：确指或具体的命题
命题变项：不确指或抽象的命题
命题公式：将命题变项用连接词或圆括号按一定逻辑关系连接起来的符号串

定义：(合式公式Well-Formed Formulas）
（1）单个命题变项是合式公式，并称为原子命题公式。
（2）若A是合式公式，则($\rceil$ A)也是合式公式。
（3）若A，B是合式公式，则(A $\vee$B)，(A $\wedge$ B)，(A $\to$B)，(A$\leftrightarrow$ B)也是合式公式。
（4）由有限次地应用(1)~(3)形成的符号串是合式公式。

注意：合式公式在命题逻辑中也称为命题公式，并简称为公式。

定义：（公式的层次）
（1）若公式A是单个的命题变项，则称A为0层合式公式。
（2）若公式A的层次为k，则称A是k层公式。
（3）称A是n+1(n≥0)层公式是指下列情况之一：

(a) A= $\rceil$ B,B是n层公式；
(b) A=B$\wedge$C,其中B,C分别为i层和j层公式,且n=max(i,j) ；
(c ) A=B $\vee$C,其中B,C的层次及n同(b);
(d) A=B $\to$C,其中B,C的层次及n同(b);
(e) A=B $\leftrightarrow$C,其中B,C的层次及n同(b);

解释：将公式中的每个命题变项都指定一个具体的命题，抽象的公式就具有了实际的意义，成了命题，具有了真值，这称为公式的解释

定义：（公式的赋值）
设$p_1 ，p_2 ，…，p_n$是出现在公式A中的全部的命题变项，给$p_1，p_2，…，p_n$各指定一个真值，称为对A的一个赋值。将n个命题变项按下标顺序或字典顺序排列后，赋值就相当于一长为n 的0，1字符串。

若指定的一组值使A的真值为1，则称这组值为A 的成真赋值。
若指定的一组值使A的真值为0，则称这组值为A 的成假赋值。

定义：（公式的分类）
（1）若A在其各种赋值下的取值均为真，则称A是重言式或永真式。
（2）若A在其各种赋值下的取值均为假，则称A是矛盾式或永假式。
（3）若A不是矛盾式，则称A为可满足式。
（4）若A是可满足式，且至少存在一个成假赋值，则称A为非重言式的可满足式。

真值表的作用：
（1）表示出公式的成真或成假赋值。
（2）判断公式类型：
(a)若真值表最后一列全为1，则为重言式；
(b)若真值表最后一列全为0，则为矛盾式；
(c )若真值表最后一列至少有一个1，则为可满足式；
(d)若真值表最后一列至少有一个1和一个0，则为非重言的可满足式。