Question

2道离散数学的题目

1. 求命题公式 (p→¬q)←→r 的主合取范式与主析取范式。

2. 定义连接词↓为：p↓q = ¬(p∨q)
a) 写出p↓q的真值表
b) 证明由¬、∨、∧构成的命题公式都可仅用↓来表示。

Answer 1

1）
(p→¬q)↔r
⇔ (¬p∨¬q)↔r
⇔ [(¬p∨¬q)→r] ∧ [r→(¬p∨¬q)]
⇔ (¬(¬p∨¬q)∨r)∧ (¬r∨¬p∨¬q)
⇔ ((p∧q)∨r)∧ (¬p∨¬q∨¬r)
⇔ (p∨r)∧(q∨r)∧ (¬p∨¬q∨¬r)
⇔ [p∨(q∧¬q)∨r]∧[(p∧¬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∨r)∧(¬p∨q∨r) ∧ (¬p∨¬q∨¬r)
得到主合取范式
检查遗漏的4个主项
p∨q∨¬r，p∨¬q∨¬r，¬p∨q∨¬r，¬p∨¬q∨r

⇔(¬p∧¬q∧r)∨(¬p∧q∧r)∨(p∧¬q∧r)∨(p∧q∧¬r)
得到主析取范式

2）
p↓q = ¬(p∨q)

a) 真值表
p q ¬(p∨q) p↓q
1 1 0 0

1 0 0 0
0 1 0 0
0 0 1 1

b)
¬p ⇔ ¬(p∨p) ⇔ p↓p ①
p∧q ⇔ ¬(¬p∨¬q) ⇔(¬p)↓(¬q) ⇔根据①式 (p↓p)↓(q↓q)
p∨q ⇔ ¬¬(p∨q) ⇔¬(p↓q) ⇔根据①式 (p↓q)↓ (p↓q)

因此
¬、∨、∧构成的命题公式都可仅用↓来表示

Answer 2

1. 用真值表：         
   

    p        q        r        ┐q        p→¬q        (p→¬q)←→r

    0        0        0        1            1                        0

    0        0        1        1            1                        1

    0        1        0        0            1                        0

    0        1        1        0            1                        1

    1        0        0        1            1                        0

    1        0        1        1            1                        1

    1        1        0        0            0                        1

    1        1        1        0            0                        0

主合取范式：(P∨Q∨R) ∧(P∨┐Q∨R) ∧(┐P∨Q∨R)∧(┐P∨┐Q∨┐R)

主析取范式：(┐P∧┐Q∧R)∨(┐P∧Q∧R)∨(P∧┐Q∧R)∨(P∧Q∧┐R)

2.    p↓q = ¬(p∨q)

    p        q        p∨q        p↓q

    0        0            0            1

    0        1            1            0

    1        0            1            0

    1        1            1            0

┐A <=> ┐(A∨A) <=> A↓A

A∨B <=> ┐┐(A ∨B) <=> ┐(A↓B) <=>  (A↓B)↓(A↓B)

A∧B <=> ┐┐(A∧B)  <=> ┐(┐A∨┐B)   <=> ┐((A↓A)∨(B↓B)) 

  <=> ┐(((A↓A)↓(B↓B))↓((A↓A)↓(B↓B)))

  <=> (((A↓A)↓(B↓B))↓((A↓A)↓(B↓B))) ↓  (((A↓A)↓(B↓B))↓((A↓A)↓(B↓B)))