题目内容
(请给出正确答案)
[单选题]
【多选题】问题的状态生成法有()
A.子集树生成法
B.深度优先生成法
C.宽度优先生成法
D.排列树生成法
答案
命题为真.事实上可以证明,若R在A上是自反的、对称的或可传递的,则R'在A'上也分别是自反的、对称的或可传递的. 设R是自反的.对任意a∈A',则a∈A,因为R是自反的,所以〈a,a〉∈R,又〈a,a〉∈A'×A',所以〈a,a〉∈(R∩(A'×A')),即〈a,a〉∈R',故R'是自反的. 设R是对称的.对任意a,b∈A',若〈a,b〉∈R',则〈a,b〉∈R且〈a,b〉∈A'×A'.因为R是对称的,所以〈b,a〉∈R,又显然〈b,a〉∈A'×A',所以〈b,a〉∈(R∩(A'×A')),即〈b,a〉∈R'.故R'是对称的. 设R是可传递的.对任意a,b,c∈A',若〈a,b〉∈R',〈b,c〉∈R',则〈a,b〉∈R,〈a,b〉∈A'×A',〈b,c〉∈R,〈b,c〉∈A'×A'.因为R是可传递的,所以〈a,c〉∈R,又显然〈a,c〉∈A'×A',所以〈a,c〉∈(R∩(A'×A')),即〈a,c〉∈R',故R'是可传递的. 由以上证明可知,若R是A上的等价关系,则R'就是A'上的等价关系.$命题为真.在题(1)中已经证明,若R是A上的自反、传递关系,则R'是A'上的自反、传递关系.下面证明,若R是A上的反对称关系,则R'是A'上的反对称关系. 设R是反对称的,对任意a,b∈A',若〈a,b〉∈R',〈b,a〉∈R',则〈a,b〉∈R,〈b,a〉∈R.因为R是反对称的,所以a=b,故R'是反对称的. 因此,若R是A上的偏序关系,则R'是A'上的偏序关系.$命题为真.在题(1)中已经证明,若R具有传递性,则R'也具有传递性.所以只需证明,若R具有反自反性,则R'也具有反自反性. 设R具有反自反性,假若R'不具有反自反性,则存在a∈A',使得〈a,a〉∈R',而 ,所以〈a,a〉∈R,这与R具有反自反性矛盾,故R'具有反自反性. 因此,若R是A上的拟序关系,则R'也是A'上的拟序关系.$命题为真.设R是A上的线序关系。则R是A上的偏序关系,且A中任两个元素都有关系.由题(2)知,R'应是A'上的偏序关系.对于任意的a,b∈A'.因为 ,所以a,b∈A.因此〈a,b〉∈R或〈b,a〉∈R(注意,R是偏序关系,所以只能有一种情况成立).又〈a,b〉∈A'×A',〈b,a〉∈A'×A',所以得到〈a,b〉∈R∪(A'×A')=R'或〈b,a〉∈R'.这说明A'中任两个元素都有关系R',故R'是A'上的线序关系.$命题为真.设R是A上的良序关系,则R是A上的偏序关系,且A的每一个非空子集都存在最小元素.由题(2)知,R'应是A'上的偏序关系.又设任意的 且S≠ ,因为 ,所以 ,即S是A的非空子集,所以S关于R存在最小元素a,因此对任意的x∈S,有〈a,x〉∈R,又a,x∈A',所以〈a,x〉∈A'×A'.因此〈a,x〉∈R∩(A'×A')=R',即a也是S关于R'的最小元素.这说明A'中的任意非空子集都存在最小元素.故R'是良序关系.
![](https://lstatic.shangxueba.com/sxbcn/h5/images/tips_org.png)