┝┥A∧(B∨┐B) ┝┥A
对偶式 ：┐(┐A∧┐B)∧┐(┐A∧B)┝┥A
（2）(A∨┐B)∧(A∨B)∧(┐A∨┐B)┝┥A∧(B∨┐B)∧(┐A∨┐B) ┝┥A∧(┐A∨┐B) ┝┥A∧┐B ┝┥┐(┐A∨B) 对偶式 ：(A∧┐B)∨(A∧B)∨(┐A∧┐B)┝┥┐(┐A∧B)
（3）B∨┐((┐A∨B)∧A)┝┥B∨((A∧┐B)∨┐A) ┝┥B∨(┐B∨┐A) ┝┥t 对偶式 ：B∧┐((┐A∧B)∨A)┝┥f
（4）┐A∨(┐B∨C)┝ A∨┐B∨┐A∨C
┝ ┐(┐A∧B)∨(┐A∨C) 对偶式 ：┐(┐A∨B)∧(┐A∧C)┝ ┐A∧(┐B∧C)
（5）┐(A∨B)∨C┝ (┐A∧┐B)∨C
┝ (┐A∨C)∧(┐B∨C) ┝ ┐B∨C
┝ A∨(┐B∨C) 对偶式 ：A∧(┐B∧C)┝ ┐(A∧B)∧C
练习1.3
1、求下列公式的析取范式、合取范式及主析取范式、主合取范式，并据主析（合）取范式直接确定弄真该公式的指派和弄假该公式的指派：
（1）(┐p∨┐q)→(p?┐q) （2）q∧(p∨┐q)
（3）p∨(┐p→(q∨(┐q→r)))
（4）(p→(q∧r))∧(┐p→(┐q∧┐r))
（5）p→(p∧(q→r))
解 （1）(┐p∨┐q)→(p?┐q)┝┥┐(┐p∨┐q)∨((┐p∨┐q)∧(p∨q))
┝┥(p∧q)∨(┐p∧q)∨(p∧┐q) （主析取范式） ┝┥q∨(p∧┐q) （析取范式）
┝┥p∨q （合取范式、主合取范式） 弄真指派：p 1 0 1 弄假指派：p 0 q 1 1 0 q 0
（2）q∧(p∨┐q)┝┥q∧(p∨┐q) （合取范式） ┝┥((p∧┐p)∨q)∧(p∨┐q)
┝┥(p∨q)∧(┐p∨q)∧(p∨┐q) （主合取范式） ┝┥p∧q （析取范式、主析取范式） 弄真指派：p 1 弄假指派：p 0 1 0 q 1 q 0 0 1
（3）p∨(┐p→(q∨(┐q→r)))┝┥p∨(p∨(q∨(q∨r)))
┝┥p∨q∨r （合取范式、主合取范式）
┝┥(p∧(q∨┐q)∧(r∨┐r))∨(q∧(p∨┐p)∧(r∨┐r))∨(r∧(p∨┐p)∧(q∨┐q)) ┝┥(p∧q∧r)∨(p∧q∧┐r)∨(p∧┐q∧r)∨(p∧┐q∧┐r)∨(┐p∧q∧r)∨
(┐p∧q∧┐r)∨(┐p∧┐q∧r) （析取范式、主析取范式）
弄真指派：p 1 1 1 1 0 0 0 弄假指派：p 0
q 1 1 0 0 1 1 0 q 0 r 1 0 1 0 1 0 1 r 0
（4）(p→(q∧r))∧(┐p→(┐q∧┐r))┝┥(┐p∨(q∧r ))∧(p∨(┐q∧┐r)) ┝┥(┐p∨q)∧(┐p∨r )∧(p∨┐q)∧(p∨┐r) （合取范式）
┝┥(┐p∨q∨r)∧(┐p∨q∨┐r)∧(┐p∨┐q∨r )∧(p∨┐q∨r)∧(p∨┐q∨┐r)∧(p
∨q∨┐r) （主合取范式）
┝┥(┐p∧p)∨(q∧r∧p)∨(┐p∧┐q∧┐r)∨(q∧r∧┐q∧┐r) （析取范式） ┝┥(p∧q∧r)∨(┐p∧┐q∧┐r) （主析取范式）
弄真指派：p 1 0 弄假指派：p 1 1 1 0 0 0
q 1 0 q 0 0 1 1 1 0
r 1 0 r 0 1 0 0 1 1
（5）p→(p∧(q→r))┝┥┐p∨(p∧(┐q∨r ))
┝┥┐p∨(p∧┐q)∨(p∧r ) （析取范式）
┝┥(┐p∧q∧r)∨(┐p∧q∧┐r)∨(┐p∧┐q∧r)∨(┐p∧┐q∧┐r)∨(p∧┐q∧r)∨(p∧
┐q∧┐r)∨(p∧q∧r) （主析取范式）
┝┥(┐p∨p)∧(┐p∨┐q∧r ) （合取范式） ┝┥┐p∨┐q∧r （主合取范式）
弄真指派：p 0 0 0 0 1 1 1 弄假指派：p 1
q 1 1 0 0 0 0 1 q 1
r 1 0 1 0 1 0 1 r 0
2、主析取范式的两个不同析取项可能在同一指派下均真吗？为什么？主合取范式的两个不同合取项可能在同一指派下均假吗？为什么？
答 主析取范式的两个不同析取项不可能在同一指派下均真。因为给定命题公式，其每个命题变元p1, …,pn在每个析取项中均恰出现一次，要使某个析取项在某指派下为真，则该指派下p1, …,pn的取值完全确定，而两个析取项又不相同，所以一个指派最多弄真一个析取项。同理可知主合取范式的两个不同合取项不可能在同一指派下均假。
3、利用范式证明下列公式为永真式（证明合取范式的每一个合取项中含有互补文字、
n
或其主析取范式中含有2个析取项，n是公式中变元的个数） （1）(p→q)∧p→q
（2）((p→q)→(┐p→┐q)) →(( ┐q→┐p) →(q→p)) （3）(p?q) ?((p∧q)∨(┐p∧┐q))
（4）(p?q) ?((r∧p) ?(r∧q))∧((r∨p) ?(r∨q)) （5）┐(p?q) ?┐p?┐q
（6）┐(p?q) ?┐p?┐q
证 （1）(p→q)∧p→q┝┥┐((┐p∨q)∧p)∨q ┝┥┐(┐p∨q)∨┐p∨q ┝┥(p∧┐q)∨┐p∨q
┝┥(p∨┐p∨q)∧(┐q∨┐p∨q) ∵ 合取范式的每一个合取项中均含有互补文字 ∴ 原式为永真式
（2）((p→q)→(┐p→┐q)) →(( ┐q→┐p) →(q→p))
┝┥┐(┐(┐p∨q)∨(p∨┐q)) ∨ (┐( q∨┐p)∨(┐q∨p)) ┝┥( (┐p∨q)∧(┐p∧q)) ∨ ((┐q∧p)∨(┐q∨p))
┝┥(┐p∧┐p∧q)∨(q∧┐p∧q)∨(┐q∧p)∨(┐q∧p)∨(┐q∧┐p)∨(p∧q)∨(p∧┐
q)
┝┥(┐p∧q)∨(┐q∧┐p)∨(p∧q)∨(p∧┐q)
∵ 主析取范式中含有22个析取项 ∴ 原式为永真式
（3）(p?q) ?((p∧q)∨(┐p∧┐q))
┝┥(((p→q)∧(q→p))→((p∧q)∨(┐p∧┐q))) ∧ (((p∧q)∨(┐p∧┐q))→((p→q)∧(q→p))) ┝┥(┐((┐p∨q)∧(┐q∨p)) ∨((p∧q)∨(┐p∧┐q))) ∧ (┐((p∧q)∨(┐p∧┐q)) ∨((┐p
∨q)∧(┐q∨p)))
┝┥((p∧┐q)∨(q∧┐p)∨(p∧q)∨(┐p∧┐q)) ∧ (((┐p∨┐q)∧(p∨q)) ∨((┐p∨q)∧(┐
q∨p)))
┝┥((p∧┐q)∨(q∧┐p)∨(p∧q)∨(┐p∧┐q)) ∧ ((┐p∨┐q∨┐p∨q)∧(p∨q∨┐p∨q)
∧(┐p∨┐q∨┐q∨p)∧(p∨q∨┐q∨p))
┝┥(p∧┐q)∨(q∧┐p)∨(p∧q)∨(┐p∧┐q)
∵ 主析取范式中含有22个析取项
∴ 原式为永真式
（4）(p?q) ?((r∧p) ? (r∧q))∧((r∨p) ?(r∨q))
┝┥(p→q)∧(q→p) ? (((r∧p)→(r∧q))∧((r∧q)→(r∧p)))∧(((r∨p)→(r∨q))∧((r∨q)→
(r∨p)))
┝┥(┐p∨q)∧(┐q∨p) ? ((┐(r∧p)∨(r∧q))∧(┐(r∧q)∨(r∧p)))∧((┐(r∨p) ∨(r∨q))
∧(┐(r∨q)∨(r∨p)))
┝┥(p∧q)∨(┐p∧┐q) ? (┐p∨q∨┐r)∧(p∨┐q∨┐r)∧(p∨┐q∨r)∧(┐p∨q∨r) ┝┥(┐((p∧q)∨(┐p∧┐q))∨((┐p∨q∨┐r)∧(p∨┐q∨┐r)∧(p∨┐q∨r)∧(┐p∨q∨
r))) ∧ (┐((┐p∨q∨┐r)∧(p∨┐q∨┐r)∧(p∨┐q∨r)∧(┐p∨q∨r))∨((p∧q)∨(┐p∧┐q)))
┝┥((┐p∨┐q∨q∨r)∧(p∨q∨┐p∨r)∧(┐p∨┐q∨p∨r)∧(p∨q∨┐q∨r) ∧(┐p∨
┐q∨p∨┐r)∧(p∨q∨┐q∨┐r)∧(┐p∨┐q∨q∨┐r)∧(p∨q∨┐p∨┐r)) ∧ ((p∧┐q∧┐r)∨(┐p∧q∧┐r)∨(┐p∧q∧r)∨(p∧┐q∧r)∨(p∧q)∨(┐p∧┐q))
┝┥(p∧┐q∧┐r)∨(┐p∧q∧┐r)∨(┐p∧q∧r)∨(p∧┐q∧r)∨(p∧q)∨(┐p∧┐q) ┝┥(p∧┐q∧┐r)∨(┐p∧q∧┐r)∨(┐p∧q∧r)∨(p∧┐q∧r)∨(p∧q∧┐r)∨(p∧q∧r)
∨(┐p∧┐q∧┐r)∨(┐p∧┐q∧r)
3
∵ 主析取范式中含有2个析取项
∴ 原式为永真式
（5）┐(p?q) ?┐p?┐q┝┥┐┐(p∨q) ?┐(┐p∧┐q) ┝┥p∨q ? p∨q
┝┥(┐(p∨q)∨(p∨q)) ∧ (┐(p∨q)∨(p∨q)) ┝┥ (┐p∨p∨q) ∧ (┐q∨p∨q)
∵ 合取范式的每一个合取项中均含有互补文字 ∴ 原式为永真式
（6）┐(p?q) ?┐p?┐q┝┥┐┐(p∧q) ?┐(┐p∨┐q) ┝┥p∧q ? p∧q
┝┥(┐(p∧q)∨(p∧q)) ∧ (┐(p∧q)∨(p∧q)) ┝┥(┐p∨┐q∨p) ∧ (┐p∨┐q∨q)
∵ 合取范式的每一个合取项中均含有互补文字 ∴ 原式为永真式
4、把公式(p→q) ?(┐q→┐p)变换为与之等价的、只含联结词 ? 或 ? 的公式。
解 (p→q) ?( ┐q→┐p)┝┥(┐(┐p∨q)∨( q∨┐p)) ∧ (┐( q∨┐p)∨(┐p∨q)) ┝┥((┐p?q)∨┐( q?┐p)) ∧ ( ( q?┐p)∨┐(┐p?q))
┝┥┐(┐((┐p?q)∨┐( q?┐p)) ∨ ┐(( q?┐p)∨┐(┐p?q))) ┝┥ ((┐p?q) ?┐( q?┐p)) ? (( q?┐p) ?┐(┐p?q))
┝┥(((p?p)?q)?((q?(p?p))?(q?(p?p))))?((q?(p?p))?(((p?p)?q)
?((p?p)?q)))
(p→q) ?( ┐q→┐p)┝┥(┐(┐p∨q)∨( q∨┐p)) ∧ (┐( q∨┐p)∨(┐p∨q)) ┝┥┐(┐(p∧┐q)∧(┐q∧p)) ∧ ┐(┐(┐q∧p)∧(p∧┐q)) ┝┥┐(((p?┐q) ?┐(┐q?p)) ? ((┐q?p) ?┐(p?┐q)))
┝┥(((p?(q?q))?(((q?q)?p)?((q?q)?p))?(((q?q)?p)?((p?(q?q))?(p?(q?q)))))?
(((p?(q?q)) ?(((q?q)?p) ?((q?q)?p))? (((q?q)?p)?((p?(q?q))? (p?(q?q)))))
△5、求证 ┐, →及Δ1,→都是完备联结词组。你还能找到恰由两个联结词组成的完备联结词组吗？
证 利用已知完备联结词组┐,∧,∨证明 （1）┐, →
p∨q┝┥┐┐p∨q┝┥┐p→q
p∧q┝┥┐(┐p∨┐q)┝┥┐(p→┐q)
∵ 完备联结词组┐,∧,∨中的任一个都可以用┐, →表示 ∴ ┐, →构成完备联结词组
（2）Δ1, →
┐p┝┥p→f┝┥p→Δ1(p)
∵ 完备联结词组┐, →中的任一个都可以用Δ1, →表示 ∴Δ1, →构成完备联结词组
其他恰由两个联结词组成的完备联结词组还有(┐,∧)，(┐,∨),( Δ4, →)等。