离散数学 偏序关系

离散数学 偏序关系

偏序，只需证明满足自反性、反对称性、传递性即可。

自反性，是显然的（把定义中的u，v分别换成x, y，即可得证）
反对称性，
由下面两个式子同时成立：
≼⇔x≼1u∨(x=u∧y≼2v)
≼⇔u≼1x∨(u=x∧v≼2y)
可以知道，下面4种情况至少有1个成立
x≼1u 且 u≼1x
x≼1u 且 u=x∧v≼2y
x=u∧y≼2v 且 u≼1x
x=u∧y≼2v 且 u=x∧v≼2y

即
x=u
x=u 且 v≼2y
x=u 且 y≼2v
x=u 且 y=v
4种情况至少有1个成立

从而x=u必然成立
y=v不一定成立（这一点，需确认一下题目是否有误）

传递性，
由
≼⇔x≼1u∨(x=u∧y≼2v)
≼⇔u≼1a∨(u=a∧v≼2b)
得到，下面4种情况至少有1个成立
x≼1u 且 u≼1a
x≼1u 且 u=a∧v≼2b
x=u∧y≼2v 且 u≼1a
x=u∧y≼2v 且 u=a∧v≼2b

则
x≼1a
x≼1a 且 u=a 且 v≼2b
x≼1a 且 x=u 且 y≼2v
x≼1a 且 x=u=a 且 y≼2v 且 v≼2b

4种情况至少有1个成立
从而x≼1a∨(x=a∧y≼2b)必然成立

根据≼⇔x≼1a∨(x=a∧y≼2b)，传递性立即得证。

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息