命题逻辑的基本概念

1.命题与联结词

命题：非真即假的陈述句。
真值：命题的判断结果。只有真假两个取值,真为1，假为0。
真命题：真值为1的命题。
假命题：真值为0的命题。
简单命题：不能分解为更简单的命题。
复合命题：由简单命题和联结词组合而成的命题。
定义1.1：设p为命题，复合命题“非p”称为p的否定式。记做﹁p，符号﹁为否定联结词。规定﹁p为真当且仅当p为假。
定义1.2：设p，q两个命题，复合命题“p并且q”（或“p与q”）称为p与q的合取式。记做p∧q。∧称作合取联结词，规定p∧q为真当且仅当p与q同时为真。
定义1.3：设p，q为两个命题，复合命题“p或q”称作p与q的析取式，记做p∨q，∨称为析取联结词，规定p∨q为假当且仅当p与q同时为假。
定义1.4：设p，q为两个命题，复合命题“如果p，则q”称为p与q的蕴含式，记做p→q，并称p为蕴含式的前件，q为蕴含式的后件。→称为蕴含联结词，并规定p→q为假，当且仅当p为真，q为假。
定义1.5：设p，q为两个命题，复合命题“p当且仅当q”称作p与q的等价式，记做p←→q。←→称作等价联结词。规定p←→q为真当且仅当p与q同时为真或同时为假。

2.命题公式与其赋值

命题常项：真值确定的。
命题变项：真值是0或者1，但仍未确定。
合式公式：将命题变项用联结词和圆括号按照一定的逻辑关系联结起来的符号串。
定义1.6：
（1）单个命题变项和命题常项是合适公式，并成为原子命题。
（2）若A为合式公式，则非A是合式公式。
（3）若A，B是合式公式，则(A∧B)，(A∨B)，(A→B)，(A←→B)是合式公式。
（4）有限次使用上诉1-3形成的符号串是合式公式。
定义1.7：
（1）若公式A是单个命题变项，则称A为0层公式。
（2）称A是n+1（n>=0）层是指下面情况之一。
（a）A=﹁B，B为n层公式。
（b）A=B∧C或(A∨B)或(A→B)或(A←→B)，其中B为i层和j层公式，且n=max(i,j)；
（3）若公式A的层次为k，则称A是k层公式。
定义1.8：设A为任一命题公式：
（1）A在任何赋值下为真，则称为永真式。
（2）A在任何赋值下为假，则称为矛盾式。
（3）A不是矛盾式，则称为可满足式。