英文网站建,静宁门户网站,和国外做贸易用什么网站,网站建设挂什么费用简单析取式与简单合取式
定义#xff1a; 仅由有限个命题变项或其否定构成的析取式称为简单析取式。仅由有限个命题变项或其否定构成的合取式称为简单合取式。
例如#xff1a; p p p、 p \lnot p p、 p ∨ q p\lor q p∨q、 p ∨ q p\lor\lnot q p∨q、 p ∨ q ∨ r \…简单析取式与简单合取式
定义 仅由有限个命题变项或其否定构成的析取式称为简单析取式。仅由有限个命题变项或其否定构成的合取式称为简单合取式。
例如 p p p、 ¬ p \lnot p ¬p、 p ∨ q p\lor q p∨q、 p ∨ ¬ q p\lor\lnot q p∨¬q、 ¬ p ∨ q ∨ r \lnot p\lor q\lor r ¬p∨q∨r等都是简单析取式 p p p、 ¬ p \lnot p ¬p、 p ∧ q p\land q p∧q、 p ∧ ¬ q p\land\lnot q p∧¬q、 ¬ p ∧ q ∧ r \lnot p\land q\land r ¬p∧q∧r等都是简单合取式。
由以上定义可以得到两点结论
一个简单析取式是重言式当且仅当它同时含有一个命题变项及其否定一个简单合取式是矛盾式当且仅当它同时含有一个命题变项及其否定。
例如 简单析取式 p ∨ ¬ q ∨ q p\lor \lnot q\lor q p∨¬q∨q是重言式简单合取式 p ∧ ¬ q ∧ q p\land\lnot q\land q p∧¬q∧q是矛盾式。
析取范式与合取范式
定义 仅由有限个简单合取式构成的析取式称为析取范式仅由有限个简单析取式构成的合取式称为合取范式。
例如 p ∨ q ∨ ¬ r p\lor q\lor\lnot r p∨q∨¬r、 ¬ p ∨ ¬ q ∨ r \lnot p\lor\lnot q\lor r ¬p∨¬q∨r、 ( p 1 ∧ ¬ q 1 ) ∨ ( ¬ p 1 ∧ p 2 ) ∨ ( p 1 ∧ p 2 ∧ p 3 ) (p_1\land\lnot q_1)\lor(\lnot p_1\land p_2)\lor(p_1\land p_2\land p_3) (p1∧¬q1)∨(¬p1∧p2)∨(p1∧p2∧p3)是析取范式 p ∧ q ∧ ¬ r p\land q\land\lnot r p∧q∧¬r、 ¬ p ∧ ¬ q ∧ r \lnot p\land\lnot q\land r ¬p∧¬q∧r、 ( p 1 ∨ ¬ q 1 ) ∧ ( ¬ p 1 ∨ p 2 ) ∧ ( p 1 ∨ p 2 ∨ p 3 ) (p_1\lor\lnot q_1)\land(\lnot p_1\lor p_2)\land(p_1\lor p_2\lor p_3) (p1∨¬q1)∧(¬p1∨p2)∧(p1∨p2∨p3)是合取范式
由以上定义可以得到两点结论
一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。
范式存在定理与范式求解
范式存在定理 任一命题公式都存在着不唯一的与之等值的析取范式和合取范式。
根据范式存在定理可知任一命题公式都能通过等值演算求出与之等值的析取范式与合取范式。步骤如下
消去 → \to →和 ↔ \leftrightarrow ↔ p → q ThickSpace; ⟺ ThickSpace; ¬ p ∨ q p\to q \iff\lnot p\lor q p→q⟺¬p∨q p ↔ q ThickSpace; ⟺ ThickSpace; ( ¬ p ∨ q ) ∧ ( p ∨ ¬ q ) p\leftrightarrow q \iff (\lnot p\lor q)\land(p\lor \lnot q) p↔q⟺(¬p∨q)∧(p∨¬q)否定号的消去或内移 ¬ ¬ p ThickSpace; ⟺ ThickSpace; q \lnot\lnot p\iff q ¬¬p⟺q ¬ ( p ∧ q ) ThickSpace; ⟺ ThickSpace; ¬ p ∨ ¬ q \lnot(p\land q)\iff\lnot p\lor\lnot q ¬(p∧q)⟺¬p∨¬q ¬ ( p ∨ q ) ThickSpace; ⟺ ThickSpace; ¬ p ∧ ¬ q \lnot(p\lor q)\iff\lnot p\land \lnot q ¬(p∨q)⟺¬p∧¬q使用分配率。对析取范式应使用 ∧ \land ∧对 ∨ \lor ∨的分配率对合取范式应使用 ∨ \lor ∨对 ∧ \land ∧的分配率。
举例求 ( ( p ∨ q ) → r ) → p ((p\lor q)\to r)\to p ((p∨q)→r)→p的合取范式和析取范式 解 ( ( p ∨ q ) → r ) → p ¬ ( ¬ ( p ∨ q ) ∨ r ) ∨ p (消去 → ) ( ( ¬ ¬ p ∨ ¬ ¬ q ) ∧ ¬ r ) ∨ p ( ¬ 内移) ( ( p ∨ q ) ∧ ¬ r ) ∨ p ( ¬ 消去) ( p ∨ q ) ∧ ( ¬ r ∨ p ) ( ∨ 对 ∧ 分配率得合取范式) ( p ∧ ¬ r ) ∨ ( q ∧ ¬ r ) ∨ p ( ∧ 对 ∨ 分配率得析取范式) \begin{aligned} ((p\lor q)\to r)\to pamp; \lnot(\lnot(p\lor q)\lor r)\lor p amp; \text{(消去$\to$)}\\ amp; ((\lnot\lnot p\lor\lnot\lnot q)\land \lnot r)\lor pamp; \text{($\lnot$内移)}\\ amp; ((p\lor q)\land \lnot r)\lor p amp; \text{($\lnot$消去)}\\ amp; (p\lor q)\land(\lnot r\lor p) amp; \text{($\lor$对$\land$分配率得合取范式)}\\ amp; (p\land\lnot r)\lor(q\land\lnot r)\lor p amp; \text{($\land$对$\lor$分配率得析取范式)} \end{aligned} ((p∨q)→r)→p¬(¬(p∨q)∨r)∨p((¬¬p∨¬¬q)∧¬r)∨p((p∨q)∧¬r)∨p(p∨q)∧(¬r∨p)(p∧¬r)∨(q∧¬r)∨p(消去→)(¬内移)(¬消去)(∨对∧分配率得合取范式)(∧对∨分配率得析取范式)
主析取范式与主合取范式
定义 如果公式 A A A的析取范式中的简单合取式全是极小项则称该析取范式为主析取范式如果公式 A A A的合取范式中的简单析取式全是极大项则称该合取范式为主合取范式。
极小项与极大项
极小项定义 在有 n n n个命题变项的简单合取式中若每个命题变项及其否定有且仅有其中一个出现一次则称这样的简单合取式为极小项。
通常极小项的命题变项用1表示命题变项的否定用0表示这就组成了一段二进制码按二进制码的大小进行排序后用小写字母 m ( m i n i m u m ) m(minimum) m(minimum)加从0开始递增的脚标命名例: m 0 m_0 m0、 m 1 m_1 m1。
例如2个命题变项 p p p、 q q q可形成4个极小项3个命题变项 r r r、 s s s、 t t t可形成8个极小项
极小项二进制码命名极小项二进制码命名 ¬ p ∧ ¬ q \lnot p \land \lnot q ¬p∧¬q00 m 0 m_0 m0 ¬ r ∧ ¬ s ∧ ¬ t \lnot r\land \lnot s\land \lnot t ¬r∧¬s∧¬t000 m 0 m_0 m0 ¬ p ∧ q \lnot p\land q ¬p∧q01 m 1 m_1 m1 ¬ r ∧ ¬ s ∧ t \lnot r\land \lnot s\land t ¬r∧¬s∧t001 m 1 m_1 m1 p ∧ ¬ q p \land \lnot q p∧¬q10 m 2 m_2 m2 ¬ r ∧ s ∧ ¬ t \lnot r\land s\land \lnot t ¬r∧s∧¬t010 m 2 m_2 m2 p ∧ q p\land q p∧q11 m 3 m_3 m3 ¬ r ∧ s ∧ t \lnot r\land s\land t ¬r∧s∧t011 m 3 m_3 m3 r ∧ ¬ s ∧ ¬ t r\land \lnot s\land \lnot t r∧¬s∧¬t100 m 4 m_4 m4 r ∧ ¬ s ∧ t r\land \lnot s\land t r∧¬s∧t101 m 5 m_5 m5 r ∧ s ∧ ¬ t r\land s\land \lnot t r∧s∧¬t110 m 6 m_6 m6 r ∧ s ∧ t r\land s\land t r∧s∧t111 m 7 m_7 m7
极大项定义 在有 n n n个命题变项的简单析取式中若每个命题变项及其否定有且仅有其中一个出现一次则称这样的简单析取式为极大项。
通常极大项的命题变项用0表示命题变项的否定用1表示这就组成了一段二进制码按二进制码的大小进行排序后用大写字母 m ( m a x i m u m ) m(maximum) m(maximum)加从0开始递增的脚标命名例: M 0 M_0 M0、 M 1 M_1 M1。
例如2个命题变项 p p p、 q q q可形成4个极大项3个命题变项 r r r、 s s s、 t t t可形成8个极大项
极小项二进制码命名极小项二进制码命名 p ∧ q p \land q p∧q00 M 0 M_0 M0 r ∧ s ∧ t r\land s\land t r∧s∧t000 M 0 M_0 M0 p ∧ ¬ q p\land \lnot q p∧¬q01 M 1 M_1 M1 r ∧ s ∧ ¬ t r\land s\land \lnot t r∧s∧¬t001 M 1 M_1 M1 ¬ p ∧ q \lnot p \land q ¬p∧q10 M 2 M_2 M2 r ∧ ¬ s ∧ t r\land \lnot s\land t r∧¬s∧t010 M 2 M_2 M2 ¬ p ∧ ¬ q \lnot p\land\lnot q ¬p∧¬q11 M 3 M_3 M3 r ∧ ¬ s ∧ ¬ t r\land \lnot s\land\lnot t r∧¬s∧¬t011 M 3 M_3 M3 ¬ r ∧ s ∧ t \lnot r\land s\land t ¬r∧s∧t100 M 4 M_4 M4 ¬ r ∧ s ∧ ¬ t \lnot r\land s\land \lnot t ¬r∧s∧¬t101 M 5 M_5 M5 ¬ r ∧ ¬ s ∧ t \lnot r\land \lnot s\land t ¬r∧¬s∧t110 M 6 M_6 M6 ¬ r ∧ ¬ s ∧ ¬ t \lnot r\land \lnot s\land \lnot t ¬r∧¬s∧¬t111 M 7 M_7 M7
主范式存在定理 任何命题公式都有唯一的主析取范式或主合取范式。
求解主范式的步骤
求出析取范式或合取范式扩展命题变项将简单合取式(简单析取式)扩展为极小项(极大项)形式合并重复项求余项求出主析取范式后余下的项就是主合取范式的组成项求出主合取范式后余下的项就是主析取范式的组成项
例如求 ( ( p ∨ q ) → r ) → p ((p\lor q)\to r)\to p ((p∨q)→r)→p的主析取范式与主合取范式主范式 解 ( ( p ∨ q ) → r ) → p ( p ∧ ¬ r ) ∨ ( q ∧ ¬ r ) ∨ p 求出析取范式 ( p ∧ ( ¬ q ∨ q ) ∧ ¬ r ) ∨ ( ( ¬ p ∨ p ) ∧ q ∧ ¬ r ) ∨ ( p ∧ ( ¬ q ∨ q ) ∧ ( ¬ r ∨ 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 ) 扩展命题变项 m 4 ∨ m 6 ∨ m 2 ∨ m 6 ∨ m 4 ∨ m 5 ∨ m 6 ∨ m 7 m 2 ∨ m 4 ∨ m 5 ∨ m 6 ∨ m 7 合并重复项得出主析取范式 M 0 ∧ M 1 ∧ M 3 求余项得出主合取范式 \begin{aligned} ((p\lor q)\to r)\to p amp; (p\land\lnot r)\lor(q\land\lnot r)\lor p amp; \text{求出析取范式}\\ amp; (p\land(\lnot q \lor q)\land\lnot r)\lor((\lnot p \lor p)\land q\land\lnot r)\lor (p\land (\lnot q \lor q)\land (\lnot r \lor r))\\ amp; (p\land\lnot q\land\lnot r)\lor(p\land q\land\lnot r)\lor(\lnot p \land q\land\lnot r)\lor(p \land q\land\lnot r)\lor\\amp;(p\land \lnot q\land \lnot r)\lor(p\land \lnot q\land r)\lor(p\land q\land \lnot r)\lor(p\land q\land r)amp; \text{扩展命题变项}\\ amp; m_4\lor m_6\lor m_2\lor m_6\lor m_4\lor m_5\lor m_6\lor m_7\\ amp; m_2\lor m_4\lor m_5\lor m_6\lor m_7amp; \text{合并重复项得出主析取范式}\\ amp; M_0\land M_1\land M_3amp; \text{求余项得出主合取范式}\\ \end{aligned} ((p∨q)→r)→p(p∧¬r)∨(q∧¬r)∨p(p∧(¬q∨q)∧¬r)∨((¬p∨p)∧q∧¬r)∨(p∧(¬q∨q)∧(¬r∨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)m4∨m6∨m2∨m6∨m4∨m5∨m6∨m7m2∨m4∨m5∨m6∨m7M0∧M1∧M3求出析取范式扩展命题变项合并重复项得出主析取范式求余项得出主合取范式
