e书联盟好书下载www.book118.com 值为T.即A取T有三种可能的情形，或第一种情形，或第二种情形，或第三种情形.从 而有 A=(…)1V(…)2V(…) 进而分析每种使A为真的情形.第一种情形是P=F,Q=F同时出现，也即一P∧∽Q出 现（为真）.于是可将(…)1写成（一PAQ).同理(…）2和(…)3应分别写成(7PQ)和(PA Q).于是得 A=(-PA-Q)VO-PAQ)V(PAQ) 同样可得 B=(-PA-Q)V-PAQ). 考虑到对A来说，取T的解释个数（为3）多于取F的解释个数（为1），自然在真值表 中补上一A列为好，以便对一A列写 -A=PA7Q 便可得 A=-(PA-Q). 2.3.2从F来列写 从图2.3.1看B的真值F,如何依赖于P,Q的真值.在图中的第3、第4行，B值为F, 即B取F有两种可能的情形，或第一种情形，或第二种情形.从而有 B=(…)1A(…)2 进而分析每种使B为假的情形.第一种情形是P=T,Q=F出现，也即一PVQ为假，于 是可将(…)1写成(PVQ).同理(…)z写成(nPVQ).于是得 B=(PVQ)A(PV7Q). 同样可得 A=(PVQ). 要注意的是这两种列写公式的区别，首先是区分从T还是从F来列写，分别得到 (··)V(·A·)V(·A·) 形和 (·V·)A(·V·)A(·V·) 形的不同结构，再者，在填写文字P,Q时，何时加否定也是有区别的 再有当列写公式C时，因图2.3.1中对解释{P,Q}=T,T}时，C取何值可任意，或 说C与{P,Q}={T,T}无关，这时可适当选取C的真值，以使C的表达式简单， 2.4联结词的完备集 除了所详述过的五个联结词外，还可定义更多的联结词，像计算机的硬件电路设计分 析就常使用它们，如 异或（半加）V:PVQ=(PAQ)V(PQ) 非 年：P*Q=n(PΛQ) ·20·
e书联盟好书下载www.book118.com
e书联盟好书下载www.book118.com 或非 ￥：PYQ二1(PVQ) 等联结词. 问题是对n个命题变项”，…，P来说，共可定义出多少个联结词？还可以问，在：那么 多联结词中有多少是独立的？ 2.4.1命题联结词的个数 按照合式公式的定义，由命题变项和命题联结词可以构造出无限多个合式公式.可把所 有的合式公式加以分类，将等值的公式视为同一类，从中选一个作代表称之为真值函项.对 …个真值函项就有一个联结词与之对应 一元联结词是联结·个命题变项的，如P,它取值只有真假两种情形，于是联结词作用 寸P,可建立4种不同的真值函项·相应的可定义出四个不同的一元联结词厂，f,,∫， 图2.4.1给出了这些联结词f,或说真值函项∫(P)的定义， P f,(P) f(P) (P) f,(P) F F F T T T T T 图2.4,1 写出真值函项： f(P)=F, fi(P)=P. f2P）=nP, f,(P)=T. 其中f(P)是永假式，∫(P)是永真式，均与P无关，而f,(P)就是变项P本身，从而新的 公式只有f(P)了，这就是由否定词所建立的真值函项. 二元联结词联结两个命题变项，两个变项P,Q共有4种取值情形，于是联结词作用于 P,Q可建寸起16种不同的真值函项，相应的可定义出16个不同的二元联结词g:·g1,·, g:5.图2.4.2给出了这些联结词g,或说真值函项g,(P,Q》的定义. Qg(P,Q)g1(P.Q)g2(P,Q)(P.Q)(P,Q)8:(P.Q)g6(P.Q) F F F F F T F F F T T T T F F T T F T T T F T F T 入 g-(P.Q)g(P,Q)8(P,Q)g:(P.Q)gu(p,Q)812(P.Q)g(P,Q)guP.Q)8(P.R) T T T T T F F F T T T T F T T F F T T 、7 F T F F T 图2.4.2 时出各真伯函项： g.(P,Q)=F, ÷2]*
e书联盟好书下载www.book118.com
e书联盟好书下载www.book118.com g:(P.Q)=PAQ. g(P,Q)=PA-Q, g(P.Q)=(PA-Q)V(PAQ)=PA(-QVQ)=P. g(P,Q)=PAQ, g.(P.Q)=(PAQ)V(PAQ)=(PVP)AQ=Q. gn(P,Q)=PVQ, g(P.Q)=PVQ. ga(P.Q)-PAQ=P￥Q, gs(P.Q)=P+Q, B(P,Q)-PA-Q)V(PA-Q)=(-PVP)A-Q--Q, g11(P,Q)=PVnQ=Q→P. g(P,Q)=PA-Q)V(-PAQ)=-PA(-QVQ)=-P, g(P,Q)=“PVQ=P-*Q, g1:(P,Q)=7PVQ=P↑Q, gi(P.Q)=T. 所能定义的二元联结词就这些了，所熟悉的V、A、→、一以及V、忄、都包括在内了. 水真式水假式还有？种联结诃，不甚常用，本书不予讨论 一般地说，对n个命题变元P,…,P,每个P,有两种取值，从而对P1,…,P,来说共有 2种取值情形.于是相应的真值函项就有22”个，或说可定义22“个n元联结词. 2.4.2联结词的完备集 由于可定义的联结词的数量是极大的，需要考虑它们是否都是独立的，也就是说这些 联结词是否能相互表示， 定义2,4.1设C是联结词的集合，如果对任一命题公式都有由C中的联结词表示出 来的公式与之等值，就说C是完备的联结词集合，或说C是联结词的完备集. 显然全体联结词的无限集合是完备的，而{V},{V,八}就不是完备的 定理2.4.1{，V，A}是完备的联结词集合. 从节2.3介绍的由真值表列写逻辑公式的过程可知，任一公式都可由一，V,八表示出 来，从而一，V,A}是完备的，一般情形下，该定理的证明可使用数学归纳法，施归纳于联 结词的个数来论证. 又由于 PAQ=-(-PV-Q) PVQ=-0-PA-Q) 这说明，A可由一，V)表示，V可由{，A}表示，故口，V},《一，A)都是联结词的完 备集.还可证明{，+}，{◆}，《}也都是联结词的完备集.但{V,A},{-、一}不是完 备的 尽管{门，V}·一·A是完备的，但使用起来不够方便，我们愿意采取折衷方案，不是 ·22·
e书联盟好书下载www.book118.com
e书联盟好书下载www.book118.com 又喝成个被过多的联吉河.还是选用菲细讨论过的五个联结词集-，A,V、, +··灯然是完备的.只地相并不独辽. 2.5对偶式 节之.2防给出的基本等值公式，有些形式上.看是很“相像”的，考查·下这些“相像” 悍是有益的.希煨，个么心的或可必然导出和它“相像“的公式的成立，如果足这样的话，对 等们公式的讨论可得到相当的的化，另外，从逻辑关系上看，这也是·种逻辑规律·是我所 感兴的 这书所讨论的命题公式1、假定其仪出现，V·A这三个联结词， 定义2.5.1将A中出现的V·八，T,F分别以八·V,F,T代换，得到公式A'、则称 1·是小的对偶式，或说A和月红为对偶式， 节2.2.1中有许多对偶式现，知 PV(Q)AR的对偶式为(PA)VR, PVE 的对偶式为PAT. 不雉知逍，者 (PVQ)AR=(PAR)V(QAR) 成7、相应的对偶式 (PAQ)VR=(PVR)A(QVR) 也成立， 为方使，若A=A(P,…、P),令A=(P,、…,nP,). 定理2.5.1·(A)=(-4)°，-(A)=(”A)· 定理2.5.2(h)=小，（小）=A. 定理2.5.3A=A'· 可用数学明纳法，施归纳于A中出现的联结词个数n来证明 基始：设0，A中尤联结词、便有A=P,从而一A=一P.但A·=一P,所以二0 时定理成立， 纳：设n时定理成立，来证=十1时定理也成立， 因为H=为十1≥1，A中至少有个联结词，可分为三种情形： 月A.,A=AAA,A=AVA2, 其中A,A中联结词个数≤. 依纳法假设，A,=1:·一A一A: 片A一A,时.有 -1二(41) -(A) 归纳法假设 =(…4) 定理2.5.1,2.5.2 一】° 当1-…1A时，有 .1}.1） ·23·
e书联盟好书下载www.book118.com
e书联盟好书下载www.book118.com =7A,V7A2 摩根律 =A-VA2' 归纳法假设 =(AiVA)- A定义 兰 =(A1AA2) A·定义 =A*. 当A=A,VA2时，有 A=(AVA2) =7A1八“A2 摩根律 =A”-AA 归纳法假设 =(AiAA) A定义 =(A:VA2)- A·定义 =A. 从而定理得证，此定理实为摩根律的另一种形式.它把一、、一联系起来了， 定理2.5.4若A=B,必有A·=B· 证明因为A=B等价于AB永真.从而一A一一B永真. 依定理2.5,3，A=A·-,B=B·-,于是A·-B·-永真，必有A·一B·永真，故 A°=B, 定理2.5.5若A→B永真，必有B·→A永真， 定理2.5.6A与A同永真，同可满足： 一A与A·同永真，同可满足. 对偶性是逻辑规律，给证明公式的等值和求否定都带来了方便 2.6范 式 由n个命题变项所能组成的具有不同真值的命题公式有2个，然而与任何一个命题 公式等值而形式不同的命题公式可以有无穷多个，这样，首先就要问凡与命题公式A等值 的公式，能否都可以化为某一个统一的标准形式.希望这种标准形能为我们的讨论带来些方 便，如猎助于标准形对任意两个形式上不同的公式，可判断它们是否等值.借助于标准形容 易判断任一公式是否为重言式或矛盾式. 标准形或范式这类术语在数学上是常见的：如几何学中+少=r,等+茶=1分别是 圆和椭圆的范式。 2.6.1范式 为叙述方便，先定义几个术语 简单命题P及其否定式一P统称文字， …些文字的合取称合取式 一些文字的析取称析取式（也称子句）. ·21·
e书联盟好书下载www.book118.com