欢迎阅读

0命题逻辑

一章，

数 = 质数，合数有因子

和 或 假必真 同为真 →q)∧(q←→r)，(p∧q)∧┐r，p∧(q∧┐r)等都是合式公式，而pq→r，（p→(r→q)等不是合式公式。 公式A是单个的命题变项，则称A为0层合式 ┐p∧q)→r，(┐(p→┐q))∧((r∨s)┐p)分别为3层和4层公式 例】求下列公式的真值表，并求成真赋值和成假赋值。 (┐p∧q)→┐r 式(1)的成假赋值为011，其余7个赋值都是成真赋值 二章， 命题逻辑等值演算 1）双重否定律 ??A?A 2）等幂律 A∧A?A ； A∨A?A 3）交换律 A∧B?B∧A ； A∨B?B∨A 4）结合律 （A∧B）∧C?A∧（B∧C） ； （A∨B）∨C?A∨（B∨C） 5）分配律 （A∧B）∨C?（A∨C）∧（B∨C） ； （A∨B）∧C?（A∧C）∨（B∧C） 6）德·摩根律 ?（A∨B）??A∧?B ； ?（A∧B）??A∨?B 7）吸收律 A∨（A∧B）?A；A∧（A∨B）?A 8）零一律 A∨1?1 ； A∧0?0 9）同一律 A∨0?A ； A∧1?A 10）排中律 A∨?A?1 11）矛盾律 A∧?A?0 12）蕴涵等值式 A→B??A∨B 13）假言易位 A→B??B→?A 14）等价等值式 A?B?（A→B）∧（B→A） 15）等价否定等值式 A?B??A??B??B??A 16）归缪式 （A→B）∧（A→?B）??A i=1,2,…,s)为简单合取式，则A=A1∨A2∨…∨As为析取范式 (p∧┐q)∨(┐q∧┐r)∨p A1∧A2∧…∧As为合取范式 (p∨q∨r)∧(┐p∨┐q)∧r 个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式 个合取范式是重言式当且仅当它的每个简单析取式都是重言式 范式 【∧小真，∨大假】 ∧ 成真 小写 例】 (p→q)→(┐q→┐p) = ┐(┐p∨q)∨(q∨┐p) (消去→)

= (p∧┐q)∨┐p∨q (┐内移) (已为析取范式) = (p∧┐q)∨(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q) （*） = m2∨m0∨m1∨m1∨m3

= m0∨m1∨m2∨m3 (幂等律、排序) (*)由┐p及q派生的极小项的过程如下： ┐p = ┐p∧(┐q∨q)

= (┐p∧┐q)∨(┐p∧q) q = (┐p∨p)∧q

欢迎阅读

欢迎阅读

= (┐p∧q)∨(p∧q)

熟练之后，以上过程可不写在演算过程中。

该公式中含n=2个命题变项，它的主析取范式中含了22=4个极小项，故它为重言式， ，01，10，11全为成真赋值。 例】(p→q)∧┐p

= (┐p∨q)∧┐p (消去→)

= ┐p∨(┐p∧q) (分配律、幂等律) 已为析取范式 = (┐p∧┐q)∨(┐p∧q) = m0∨m1 例】(p∧┐q)∨(┐p∧q) = (p∨┐p)∧(p∨q)∧(┐q∨┐p)∧(┐q∨q) = (p∨q)∧┐(p∧q) 言蕴涵式 例】用附加前提证明法证明下面推理。 提：P→（Q→R），?S∨P，Q 结论：S→R 明：（1）?S∨P 前提引入规则 2）S 附加前提引入规则 3）P （1）（2）析取三段论规则 4）P→（Q→R） 前提引入规则 5）Q→R （3）（4）假言推理规则 6）Q 前提引入规则 7）R （5）（6）假言推理规则 例】用归缪法证明。 提：P∨Q，P→R，Q→S 结论：S∨R 明（1）?（S∨R） 附加前提引入规则 2）?S∧?R （1）置换规则 3）?S （2）化简规则 4）?R （2）化简规则 5）Q→S 前提引入规则 6）?Q∨S （5）置换规则 7）?Q （3）（6）析取三段论 8）P∨Q 前提引入规则 9）P （7）（8）析取三段论规则 10）P→R 前提引入规则 11）?P∨R （10）置换规则 12）R （9）（11）析取三段论规则 13）?R∧R （4）（12）合取引入规则

全称量词\?\对\存在量词\?\

\ xyF(x,y) x(F(x,a)∧F(x,b)∧F(x,c))

欢迎阅读

欢迎阅读

(F(a,a)∧F(a,b)∧F(a,c))∨(F(b,a)∧F(b,b)∧F(b,c))∨(F(c,a)∧F(c,b)∧F(c,c)) 词逻辑的等价公式

理1 设A（x）是谓词公式，有关量词否定的两个等价公式： 1）﹁?x A（x）??x﹁A（x） 2）﹁?x A（x）??x﹁A（x）

理2 设A（x）是任意的含自由出现个体变项x的公式，B是不含x出现的公式，则有 1）?x（A（x）∨B）??x A（x）∨B 2）?x（A（x）∧B）??x A（x）∧B 3）?x（A（x）→ B）??x A（x）→ B 4）?x（B→A（x））?B→ ?x A（x） 5）?x（A（x）∨B）? ?x A（x）∨B 6）?x（A（x）∧B）??x A（x）∧B 7）?x（A（x）→ B）??x A（x）→ B 8）?x（B→A（x））?B→?x A（x） 理3 设A（x）、B（x）是任意包含自由出现个体变元x的公式,则有： 1）?x（A（x）∧B（x））??x A（x）∧?x B（x） 2）?x（A（x）∨B（x））??x A（x）∨?x B（x） 理4 下列蕴涵式成立 1）?x A（x）∨?x B（x）??x（A（x）∨B（x）） 2）?x（A（x）∧B（x））??x A（x）∧?x B（x） 3）?x（A（x）→ B（x））??x A（x）→ ?x B（x） 4）?x（A（x）→ B（x））??x A（x）→ ?x B（x） 5）?x A（x）→ ?x B（x）??x（A（x）→ B（x）） 例】 例】

欢迎阅读