离散数学

2023-08-13 13:46| 来源: 网络整理| 查看: 265

1.9 用等值演算法判断下列公式的类型

（2） ( ( p → q ) ∧ ( q → p ) ) ↔ ( p ↔ q ) ((p \rightarrow q) \wedge(q \rightarrow p) ) \leftrightarrow (p \leftrightarrow q) ((p→q)∧(q→p))↔(p↔q)

解：

↔ ( p → q ) ↔ ( p ↔ q ) ( 蕴含等值式 ) \leftrightarrow (p \rightarrow q ) \leftrightarrow (p \leftrightarrow q ) (蕴含等值式) ↔(p→q)↔(p↔q)(蕴含等值式)

公式无成假赋值，为重言式

1.12 求下列命题公式的主析取范式、主合取范式、成真赋值、成假赋值。

(1) ( p ∨ ( q ∧ r ) ) → ( p ∧ q ∧ r ) (p \vee (q \wedge r)) \rightarrow (p \wedge q \wedge r) (p∨(q∧r))→(p∧q∧r)

解：

A ↔ ( p ∨ ( q ∧ r ) ) → ( p ∧ q ∧ r ) A \leftrightarrow (p \vee (q \wedge r)) \rightarrow (p \wedge q \wedge r) A↔(p∨(q∧r))→(p∧q∧r)

A ↔ ¬ ( p ∨ ( q ∧ r ) ) ⋁ ( p ∧ q ⋀ r ) A \leftrightarrow \lnot (p \vee (q \wedge r)) \bigvee (p \wedge q \bigwedge r) A↔¬(p∨(q∧r))⋁(p∧q⋀r)

A ↔ ¬ p ∧ ( ¬ q ∧ ¬ r ) ) ∨ ( p ∧ q ∧ r ) A \leftrightarrow \lnot p \wedge (\lnot q \wedge \lnot r)) \vee (p \wedge q \wedge r) A↔¬p∧(¬q∧¬r))∨(p∧q∧r)

A ↔ ( ¬ p ∧ ¬ q ) ∨ ( ¬ q ∧ ¬ r ) ) ⋁ ( p ∧ q ∧ r ) A \leftrightarrow (\lnot p \wedge \lnot q) \vee (\lnot q \wedge \lnot r)) \bigvee (p \wedge q \wedge r) A↔(¬p∧¬q)∨(¬q∧¬r))⋁(p∧q∧r)

A ↔ ( ¬ p ∧ ¬ q ∧ ( ¬ r ∧ r ) ∨ ( ¬ p ∧ q ∧ r ) ∧ ¬ r ) ∨ ( p ∧ q ∧ r ) ∨ ( ¬ p ∧ q ∧ ¬ r ) ∨ ( p ∧ q ∧ r ) A \leftrightarrow (\lnot p \wedge \lnot q \wedge (\lnot r \wedge r)\vee (\lnot p \wedge q \wedge r) \wedge \lnot r) \vee (p \wedge q \wedge r) \vee (\lnot p \wedge q \wedge \lnot r) \vee(p \wedge q \wedge r) A↔(¬p∧¬q∧(¬r∧r)∨(¬p∧q∧r)∧¬r)∨(p∧q∧r)∨(¬p∧q∧¬r)∨(p∧q∧r)

A ↔ m 0 ∨ m 1 ∨ m 7 A \leftrightarrow m_0 \vee m_1 \vee m_7 A↔m0∨m1∨m7

所以：

主析取范式： m 0 ∧ m 1 ∧ m 2 ∧ m 7 m_0 \wedge m_1 \wedge m_2 \wedge m_7 m0∧m1∧m2∧m7

主合取范式： M 3 ∨ M 4 ∨ M 5 ∨ M 6 M_3 \vee M_4 \vee M_5 \vee M_6 M3∨M4∨M5∨M6

成真赋值： 000 , 001 , 010 , 111 000,001,010,111 000,001,010,111

成假赋值： 011 , 100.101.110 011,100.101.110 011,100.101.110

1.8 用三种方法证明下列等值公式

( ( p → q ) ⋀ ( p → r ) ) ↔ ( p → ( q ⋀ r ) ) ((p \rightarrow q) \bigwedge (p \rightarrow r)) \leftrightarrow (p \rightarrow (q \bigwedge r)) ((p→q)⋀(p→r))↔(p→(q⋀r))

解：第一种方法

( ( p → q ) ⋀ ( p → r ) ) ((p \rightarrow q) \bigwedge (p \rightarrow r)) ((p→q)⋀(p→r))

↔ ( ¬ p ∨ q ) ∧ ( ¬ p ∨ r ) ( 蕴含等值式 ) \leftrightarrow (\lnot p \vee q) \wedge (\lnot p \vee r )(蕴含等值式) ↔(¬p∨q)∧(¬p∨r)(蕴含等值式)

↔ ¬ p ∨ ( q ∧ r ) ( 分配律 ) \leftrightarrow \lnot p \vee (q \wedge r)(分配律) ↔¬p∨(q∧r)(分配律)

↔ p → ( q ∧ r ) ( 蕴含等值式 ) \leftrightarrow p \rightarrow (q \wedge r )(蕴含等值式) ↔p→(q∧r)(蕴含等值式)

第二种方法

p → ( q ∧ r ) p \rightarrow (q \wedge r) p→(q∧r)

↔ ¬ p ∨ ( q ∧ r ) ( 蕴含等值式 ) \leftrightarrow \lnot p \vee (q \wedge r)(蕴含等值式) ↔¬p∨(q∧r)(蕴含等值式)

↔ ( ¬ p ∨ q ) ∧ ( ¬ p ∨ r ) ( 分配律 ) \leftrightarrow (\lnot p \vee q) \wedge (\lnot p \vee r)(分配律) ↔(¬p∨q)∧(¬p∨r)(分配律)

↔ ( p → q ) ∧ ( p → r ) ( 蕴含等值式 ) \leftrightarrow (p \rightarrow q) \wedge (p \rightarrow r)(蕴含等值式) ↔(p→q)∧(p→r)(蕴含等值式)

第三种方法

真值表法

( ( p → q ) ⋀ ( p → r ) ) ((p \rightarrow q) \bigwedge (p \rightarrow r)) ((p→q)⋀(p→r))

列出真值表

pqr ( ( p → q ) ⋀ ( p → r ) ) ((p \rightarrow q) \bigwedge (p \rightarrow r)) ((p→q)⋀(p→r))00010011010101111000101011001111

p → ( q ∧ r ) p \rightarrow (q \wedge r) p→(q∧r)

列出真值表

xyz p → ( q ∧ r ) p \rightarrow (q \wedge r) p→(q∧r)00010011010101111000101011001111

真值表相同，所以等价

1.15

某勘探队有 3 名队员。有一天取得一块矿样，3 人的判断如下

甲说：这不是铁，也不是铜；

乙说：这不是铁，是锡；

丙说：这不是锡，是铁

经实验室鉴定后发现，其中ー人两个判断都正确，一个人判对一半，另一个人全错了。根据以上情况判断矿样的种类，并指出谁的判断全对？谁的判断对一半？谁的判断全错？

解：

设 p : p: p:是铁 q : q: q:是铜 r : r: r:是锡

F 1 ↔ ( 甲全对 ) ∧ ( 乙对一半 ) ∧ ( 丙全错 ) F1 \leftrightarrow (甲全对) \wedge (乙对一半) \wedge (丙全错) F1↔(甲全对)∧(乙对一半)∧(丙全错)

↔ ( ¬ p ∧ ¬ q ) ∧ ( ( ¬ p ∧ ¬ r ) ∨ ( p ∧ r ) ) ∧ ( ¬ p ∧ r ) \leftrightarrow (\lnot p \wedge \lnot q) \wedge ((\lnot p \wedge \lnot r) \vee (p \wedge r)) \wedge (\lnot p \wedge r) ↔(¬p∧¬q)∧((¬p∧¬r)∨(p∧r))∧(¬p∧r)

↔ 0 ∨ 0 ↔ 0 \leftrightarrow0 \vee 0 \leftrightarrow 0 ↔0∨0↔0

F 2 ↔ ( 甲全对 ) ∧ ( 乙全错 ) ∧ ( 丙对一半 ) F2 \leftrightarrow (甲全对) \wedge (乙全错) \wedge (丙对一半) F2↔(甲全对)∧(乙全错)∧(丙对一半)

↔ ( ¬ p ∧ ¬ q ) ∧ ( p ∧ ¬ r ) ∧ ( ( p ∧ r ) ∨ ( ¬ p ∧ ¬ r ) ) \leftrightarrow (\lnot p \wedge \lnot q) \wedge (p \wedge \lnot r) \wedge((p \wedge r) \vee (\lnot p \wedge \lnot r)) ↔(¬p∧¬q)∧(p∧¬r)∧((p∧r)∨(¬p∧¬r))

↔ 0 ∨ 0 ↔ 0 \leftrightarrow 0 \vee 0 \leftrightarrow 0 ↔0∨0↔0

F 3 ↔ ( 甲对一半 ) ∧ ( 乙全对 ) ∧ ( 丙全错 ) F3 \leftrightarrow (甲对一半) \wedge (乙全对) \wedge (丙全错) F3↔(甲对一半)∧(乙全对)∧(丙全错)

↔ ( ( ¬ p ∧ q ) ∨ ( p ∧ ¬ q ) ) ∧ ( ¬ p ∧ r ) ∨ ( ¬ p ∧ ¬ r ) \leftrightarrow ((\lnot p \wedge q ) \vee (p \wedge \lnot q)) \wedge (\lnot p \wedge r ) \vee (\lnot p \wedge \lnot r) ↔((¬p∧q)∨(p∧¬q))∧(¬p∧r)∨(¬p∧¬r)

↔ ¬ p ∧ q ∧ r \leftrightarrow \lnot p \wedge q \wedge r ↔¬p∧q∧r

F 4 ↔ ( 甲对一半 ) ∧ ( 乙全错 ) ∧ ( 丙全对 ) F4 \leftrightarrow (甲对一半) \wedge (乙全错) \wedge (丙全对) F4↔(甲对一半)∧(乙全错)∧(丙全对)

↔ ( ( ¬ p ∧ q ) ∨ ( p ∧ ¬ q ) ) ∧ ( p ∧ ¬ r ) ∧ ( p ∧ ¬ r ) \leftrightarrow ((\lnot p \wedge q ) \vee (p \wedge \lnot q)) \wedge ( p \wedge \lnot r ) \wedge ( p \wedge \lnot r) ↔((¬p∧q)∨(p∧¬q))∧(p∧¬r)∧(p∧¬r)

↔ p ∧ ¬ q ∧ ¬ r \leftrightarrow p \wedge \lnot q \wedge \lnot r ↔p∧¬q∧¬r

F 5 ↔ ( 甲全错 ) ∧ ( 乙对一半 ) ∧ ( 丙全对 ) F5 \leftrightarrow (甲全错) \wedge (乙对一半) \wedge (丙全对) F5↔(甲全错)∧(乙对一半)∧(丙全对)

↔ ( p ∧ q ) ∧ ( ( ¬ p ∧ ¬ r ) ∨ ( p ∧ r ) ) ∧ ( p ∧ ¬ r ) \leftrightarrow ( p \wedge q) \wedge ((\lnot p \wedge \lnot r) \vee (p \wedge r)) \wedge ( p \wedge \lnot r) ↔(p∧q)∧((¬p∧¬r)∨(p∧r))∧(p∧¬r)

↔ 0 ∨ 0 ↔ 0 \leftrightarrow 0 \vee 0 \leftrightarrow 0 ↔0∨0↔0

F 6 ↔ ( 甲全错 ) ∧ ( 乙全对 ) ∧ ( 丙对一半 ) F6 \leftrightarrow (甲全错) \wedge (乙全对) \wedge (丙对一半) F6↔(甲全错)∧(乙全对)∧(丙对一半)

↔ ( p ∧ q ) ∧ ( ¬ p ∧ r ) ∧ ( ( p ∧ r ) ∨ ( ¬ p ∧ ¬ r ) ) \leftrightarrow ( p \wedge q) \wedge ( \lnot p \wedge r) \wedge((p \wedge r) \vee (\lnot p \wedge \lnot r)) ↔(p∧q)∧(¬p∧r)∧((p∧r)∨(¬p∧¬r))

↔ 0 ∨ 0 ↔ 0 \leftrightarrow 0 \vee 0 \leftrightarrow 0 ↔0∨0↔0

设 F ↔ ( 一人全对 ) ∧ ( 一人对一半 ) ∧ ( 一人全错 ) F \leftrightarrow (一人全对) \wedge (一人对一半) \wedge (一人全错) F↔(一人全对)∧(一人对一半)∧(一人全错)

F为真，且

F ↔ F 1 ∨ F 2 ∨ F 3 ∨ F 4 ∨ F 5 ∨ F 6 F \leftrightarrow F1 \vee F2 \vee F3 \vee F4 \vee F5 \vee F6 F↔F1∨F2∨F3∨F4∨F5∨F6

↔ ( ¬ p ∧ q ∧ r ) ∨ ( p ∧ ¬ q ∧ ¬ r ) ↔ 1 \leftrightarrow (\lnot p \wedge q \wedge r) \vee (p \wedge \lnot q \wedge \lnot r) \leftrightarrow 1 ↔(¬p∧q∧r)∨(p∧¬q∧¬r)↔1

q，r中必有假命题，所以 ¬ p ∧ q ∧ r ↔ 0 \lnot p \wedge q \wedge r \leftrightarrow 0 ¬p∧q∧r↔0

则 p ∧ ¬ q ∧ ¬ r ↔ 1 p \wedge \lnot q \wedge \lnot r \leftrightarrow 1 p∧¬q∧¬r↔1

所以p为真 q和r 为假所以矿物为铁

1.16

有一盏灯由 3 个开关控制，要求按任何一个开关都能使灯由亮变黑或由黑变亮试设计一个这样的组合电路。

解：

用. p , q , r p,q,r\;\;\;\;\; p,q,r分别表示3个开关的状态，开关的状态分别是0和1 用F表示灯灯状态，打开为1，关闭为0

列出真值表

pqrF(p,q,r)00000011010101111001101111011111

列出F的主析取范式

F = m 1 ∨ m 2 ∨ m 3 ∨ m 4 ∨ m 5 ∨ m 6 ∨ m 7 F = m_1 \vee m_2 \vee m_3 \vee m_4 \vee m_5 \vee m_6 \vee m_7 F=m1∨m2∨m3∨m4∨m5∨m6∨m7

F = ( ¬ p ∧ ¬ q ∧ r ) ∨ ( ¬ p ∧ q ∧ ¬ r ) ∨ ( ¬ p ∧ q ∧ r ) ∨ ( p ∧ ¬ q ∧ ¬ r ) ∨ ( p ∧ ¬ q ∧ r ) ∨ ( p ∧ q ∧ ¬ r ) ∨ ( p ∧ q ∧ r ) F = (\lnot p \wedge \lnot q \wedge r) \vee (\lnot p \wedge q \wedge \lnot r) \vee (\lnot p \wedge q \wedge r) \vee (p \wedge \lnot q \wedge \lnot r) \vee (p \wedge \lnot q \wedge r) \vee (p \wedge q \wedge \lnot r) \vee ( p \wedge q \wedge r) F=(¬p∧¬q∧r)∨(¬p∧q∧¬r)∨(¬p∧q∧r)∨(p∧¬q∧¬r)∨(p∧¬q∧r)∨(p∧q∧¬r)∨(p∧q∧r)

列表1 编号极小项角标标记1 ¬ p ∧ ¬ q ∧ r \lnot p \wedge \lnot q \wedge r ¬p∧¬q∧r001*2 ¬ p ∧ q ∧ ¬ r \lnot p \wedge q \wedge \lnot r ¬p∧q∧¬r010*3 ¬ p ∧ q ∧ r \lnot p \wedge q \wedge r ¬p∧q∧r011*4 p ∧ ¬ q ∧ ¬ r p \wedge \lnot q \wedge \lnot r p∧¬q∧¬r100*5 p ∧ ¬ q ∧ r p \wedge \lnot q \wedge r p∧¬q∧r101*6 p ∧ q ∧ ¬ r p \wedge q \wedge \lnot r p∧q∧¬r110*7 p ∧ q ∧ r p \wedge q \wedge r p∧q∧r111* 第一批合并项项表示串标记(1,5) ¬ q ∧ r \lnot q \wedge r ¬q∧r-01*(2,3) ¬ p ∧ q \lnot p \wedge q ¬p∧q01-*(2,6) q ∧ ¬ r q \wedge \lnot r q∧¬r-10*(3,7) q ∧ r q \wedge r q∧r-11*(4,5) p ∧ ¬ q p \wedge \lnot q p∧¬q10-*(4,6) p ∧ ¬ r p \wedge \lnot r p∧¬r1-0*(5,7) p ∧ r p \wedge r p∧r1-1*(6,7) p ∧ q p \wedge q p∧q11-* 第二批合并项项表示串(1,3,5,7) r r r–1(2,3,6,7) q q q-1-(4,5,6,7) p p p1–

选择

选择(1,3,5,7)和(2,3,6,7)和(4,5,6,7)

即最简展开式： F = p ∨ q ∨ r F=p \vee q \vee r F=p∨q∨r

1.19 构造下面推理的证明

(2) 标注用直接证明法和附加前提证明法

解：

前提： p → ( q → s ) , q , p ⋁ ¬ r p \rightarrow (q \rightarrow s) , q , p \bigvee \lnot r p→(q→s),q,p⋁¬r

结论： r → s r \rightarrow s r→s

直接证明法 1、 p → ( q → s ) p \rightarrow (q \rightarrow s) p→(q→s)前提引入2、 q → ( p → s ) q \rightarrow (p \rightarrow s) q→(p→s)1、置换3、$q $前提引入4、 p → s p \rightarrow s p→s2、3假言推理5、 p ⋁ ¬ r p \bigvee \lnot r p⋁¬r前提引入6、 r → p r \rightarrow p r→p5置换7、 r → s r \rightarrow s r→s4、6假言三段论附加前提证明法 1、 p → ( q → s ) p \rightarrow (q \rightarrow s) p→(q→s)前提引入2、 q → ( p → s ) q \rightarrow (p \rightarrow s) q→(p→s)1置换3、 q q q前提引入4、 p → s p \rightarrow s p→s2、3假言推理5、 p ⋁ ¬ r p \bigvee \lnot r p⋁¬r前提引入6、 r → p r \rightarrow p r→p5置换7、 r r r附加前提引入8、 s s s假言推理 1.20 标注用直接证明法和归谬法

判断下述推理是否正确，并证明你的结论。如果他是理科学生，他必学好数学。如果他不是文科学生，他必是理科学生。他没学好数学。所以他是文科学生

解：直接证明法

令 p p p：小王是理科生 q q q：小王是文科生， r r r：小王学好数学

前提： p → r p \rightarrow r p→r , ¬ q → p \lnot q \rightarrow p ¬q→p, ¬ r \lnot r ¬r

结论： q q q

证明：

1、 p → r p \rightarrow r p→r前提引入2、 ¬ r \lnot r ¬r前提引入3、 ¬ p \lnot p ¬p1 、2 拒取式4、 ¬ q → p \lnot q \rightarrow p ¬q→p前提引入5、 q q q3、4拒取式归谬法 1、 p → r p \rightarrow r p→r前提引入2、 ¬ r \lnot r ¬r前提引入3、 ¬ p \lnot p ¬p1 、2 拒取式4、 ¬ q → p \lnot q \rightarrow p ¬q→p前提引入5、 ¬ q \lnot q ¬q否定结论引入6、 p p p4、5 假言推理7、 p ∧ ¬ p p \wedge \lnot p p∧¬p3、6 合取

7出现了矛盾，根据归谬法，推理正确

【本文地址】

公司简介

联系我们