广东工业大学离散数学Anyview习题答案
——更新于2014年12月作者Seasand2014 1.00①试设计一算法，
判断元素与集合之间的关系。
实现下列函数：
/**
* 判断元素与集合之间的关系。元素和集合之间的关系只有两种。
* @param elem：元素
* @param pA：集合
* @return: 如果elem ∈pA，则返回TRUE，否则返回FALSE
*/
Boolean IsInSet(SetElem elem, pSet pA){
//Add your code here
}
//1.00
Boolean IsInSet ( SetElem elem, pSet pA )
{
//Add your code here
SetElem * a = outToBuffer ( pA );
for ( ; *a != '\n'; a++ )
{
if ( elem == *a )
{
return true;
}
}
return false;
}
1.01③试设计一算法，
实现集合的并运算。
实现下列函数：
/**
* 进行两个集合的并运算
* @param pA：要进行并运算的集合
* @param pB：要进行并运算的集合
* @return: 将pA和pB进行并运算后得到的集合
*/
pSet SetUnion(pSet pA, pSet pB){
//Add your code here
}
//1.01
pSet SetUnion ( pSet pA, pSet pB )
{
SetElem * a = outToBuffer ( pA );
SetElem * b = outToBuffer ( pB );
pSet pC = createNullSet();
int i = 0;
for ( ; *b != '\n'; b++ )
{
directInsertSetElem ( pC ,*b );
}
for ( a = outToBuffer ( pA ); *a != '\n'; a++ )
{
if ( isInSet ( pB,*a ) != true )
{
directInsertSetElem ( pC ,*a );
}
}
return pC;
}
1.02②试设计一算法，
实现集合的交运算。
实现下列函数：
/**
* 进行两个集合的交运算
* @param pA：要进行交运算的集合
* @param pB：要进行交运算的集合
* @return: 将pA和pB进行交运算后得到的集合*/
pSet SetIntersection(pSet pA, pSet pB){
//Add your code here
}
//1.02
pSet SetIntersection ( pSet pA, pSet pB )
{
SetElem * a = outToBuffer ( pA );
SetElem * b = outToBuffer ( pB );
pSet pC = createNullSet();
for ( ; *b != '\n'; b++ )
{
if ( isInSet ( pA,*b ) == true )
{
directInsertSetElem ( pC ,*b );
}
}
return pC;
}
1.03②试设计一算法，
实现集合的差运算。
实现下列函数：
/**
* 进行两个集合的差运算
* @param pA：要进行差运算的集合，相当于A - B中的A
* @param pB：要进行差运算的集合，相当于A - B中的B
* @return: 将pA和pB进行差运算后得到的集合
*/
pSet SetSubtraction(pSet pA, pSet pB){
//Add your code here
}
//1.03
pSet SetSubtraction ( pSet pA, pSet pB )
{
SetElem * a = outToBuffer ( pA );
SetElem * b = outToBuffer ( pB );
pSet pC = createNullSet();
for ( ; *a != '\n'; a++ )
{
if ( isInSet ( pB,*a ) == true ) continue;
directInsertSetElem ( pC ,*a );
}
return pC;
}
1.04②试设计一算法，
实现集合的求补集运算。
实现下列函数：
/**
* 进行集合的求补集运算。
* @param pA：要进行求补集运算的集合
* @param pI：全集
* @return: 返回pA相对于pI的补集。注意：有可能存在pA不是PI的子集的情况，* 在这种情况下pA的补集不存在，应当返回NULL
*/
pSet SetComplement(pSet pA, pSet pI){
//Add your code here
}
//1.04
pSet SetComplement ( pSet pA, pSet pI )
{
SetElem * a = outToBuffer ( pA );
SetElem * i = outToBuffer ( pI );
pSet pC = createNullSet();
int b = 0, k = 0;
for ( ; *i != '\n'; i++ )
{
if ( isInSet ( pA,*i ) == true )
{
b++;
continue;
}
directInsertSetElem ( pC ,*i );
}
for ( ; *a != '\n'; a++ )
{
if ( isInSet ( pI,*a ) == true )
{
continue;
}
k++;
directInsertSetElem ( pC ,*i );
}
if ( ( b == 0&&isNullSet ( pA ) != true ) || ( b != 0&&k != 0 ) ) return NULL;
if ( isNullSet ( pA ) == true&&isNullSet ( pI ) != true ) return pI;
else return pC;
}
1.05②试设计一算法，
实现集合的对称差运算。
实现下列函数：
/**
* 进行集合的对称差运算。
* @param pA：需要进行对称差运算的集合
* @param pB：需要进行对称差运算的集合
* @return: 返回pA与pB进行对称差运算后得到的集合。
*/
pSet SetSysmmetricDifference(pSet pA, pSet pB){
//Add your code here
}
//1.05
pSet SetSysmmetricDifference ( pSet pA, pSet pB )
{
//Add your code here
pSet pS;
pS=createNullSet();
SetElem *pAElems;
SetElem *pBElems;
pAElems=outToBuffer ( pA );
pBElems=outToBuffer ( pB );
while ( *pAElems!='\n' )
{
if ( !isInSet ( pB,*pAElems ) )
{
directInsertSetElem ( pS,*pAElems );
}
pAElems++;
}
while ( *pBElems!='\n' )
{
if ( !isInSet ( pA,*pBElems ) )
{
directInsertSetElem ( pS,*pBElems );
}
pBElems++;
}
return pS;
}
1.06③试设计一算法，
判断两个集合之间的包含关系。
实现下列函数：
/**
* 判断两个集合之间的包含关系。规定集合之间的包含关系为：* 真包含，被真包含于，相等。
* @param pA：需要进行包含关系判断的集合
* @param pB：需要进行包含关系判断的集合
* @return: 如果pA真包含pB，返回REALINCLUDING;
* 如果pA被真包含于pB，返回REALINCLUDED;
* 如果pA等于pB，返回EQUAL；
* 对于其它情况，返回NOT_INCLUSIVE。
*/
SetRelationshipStatus SetRelationship(pSet pA, pSet pB){
//Add your code here
}
//1.06
SetRelationshipStatus SetRelationship ( pSet pA, pSet pB )
{
//Add your code here
pSet pS;
pS=createNullSet();
SetElem *pAElems;
SetElem *pBElems;
pAElems=outToBuffer ( pA );
pBElems=outToBuffer ( pB );
pS=pB;
if ( isNullSet ( pA ) &&!isNullSet ( pB ) ) return REALINCLUDED;
if ( !isNullSet ( pA ) &&isNullSet ( pB ) ) return REALINCLUDING;
if ( isNullSet ( pA ) &&isNullSet ( pB ) ) return EQUAL;
if ( !isNullSet ( pA ) &&!isNullSet ( pB ) )
{
while ( *pAElems!='\n' )
{
if ( isInSet ( pS,*pAElems ) ) pAElems++;
else
{
while ( *pBElems!='\n' )
{
if ( isInSet ( pA,*pBElems ) ) pBElems++;
else return NOT_INCLUSIVE;
if ( *pBElems=='\n' ) return REALINCLUDING;
}
}
}
if ( *pAElems=='\n' )
{
while ( *pBElems!='\n' ) if ( isInSet ( pA,*pBElems ) ) pBElems++;
else return REALINCLUDED;
if ( *pBElems=='\n' ) return EQUAL;
}
}
}
1.07⑤试设计一个非递归算法，
实现集合的求幂集运算。
实现下列函数：
/**
* 求一个集合的幂集。
* @param pA：需要进行幂集的集合
* @return: 返回pA的幂集
*/
pSetFamily PowerSet(pSet pA){
//Add your code here
}
//1.07
pSet miji ( pSet pB,pSet pC )
{
SetElem *pBElems;
SetElem *pCElems;
pSet pS;
pS=createNullSet();
pBElems=outToBuffer ( pB );
pCElems=outToBuffer ( pC );
while ( *pBElems!='\n' )
{
directInsertSetElem ( pS,*pBElems );
pBElems++;
}
while ( *pCElems!='\n' )
{
if ( !isInSet ( pB,*pCElems ) )
{
directInsertSetElem ( pS,*pCElems );
}
++pCElems;
}
return pS;
}
pFamilyOfSet PowerSet ( pSet pA )
{
//Add your code here
int i;
pSet pI=createNullSet();
pFamilyOfSet pF=createNullFamilyOfSet();
SetElem *pBElems=outToBuffer ( pA ); insertToFamilyOfSet ( pF,pI );
if ( isNullSet ( pA ) ==FALSE )
while ( *pBElems!='\n' )
{
pSet pK=createNullSet();
directInsertSetElem ( pK,*pBElems );
pSet *pS=outFamilyOfSetToBuffer ( pF );
for ( i=0; * ( pS+i ) !=NULL; i++ )
insertToFamilyOfSet ( pF,miji ( pK,* ( pS+i ) ) );
pBElems++;
}
return pF;
}
1.08④试设计一个递归算法，
实现集合的求幂集运算。
实现下列函数：
/**
* 求一个集合的幂集。
* @param pA：需要进行幂集的集合
* @return: 返回pA的幂集
*/
pFamilyOfSet PowerSet(pSet pA){
//Add your code here
}
//1.08
pSet miji ( pSet pB,pSet pC )
{
SetElem *pBElems;
SetElem *pCElems;
pSet pS;
pS=createNullSet();
pBElems=outToBuffer ( pB );
pCElems=outToBuffer ( pC );
while ( *pBElems!='\n' )
{
directInsertSetElem ( pS,*pBElems );
pBElems++;
}
while ( *pCElems!='\n' )
{
if ( !isInSet ( pB,*pCElems ) )
{
directInsertSetElem ( pS,*pCElems );
}
++pCElems;
}
return pS;
}
pFamilyOfSet PowerSet ( pSet pA )
{
//Add your code here
int i;
pSet pI=createNullSet();
pFamilyOfSet pF=createNullFamilyOfSet();
SetElem *pBElems=outToBuffer ( pA ); insertToFamilyOfSet ( pF,pI );
if ( isNullSet ( pA ) ==FALSE )
while ( *pBElems!='\n' )
{
pSet pK=createNullSet();
directInsertSetElem ( pK,*pBElems );
pSet *pS=outFamilyOfSetToBuffer ( pF );
for ( i=0; * ( pS+i ) !=NULL; i++ )
insertToFamilyOfSet ( pF,miji ( pK,* ( pS+i ) ) );
pBElems++;
}
return pF;
}
3.01⑤试设计一个非递归算法，
验证一个表达式是不是命题公式(statement formula)。
实现下列函数：
/**
* 判断一个表达式是不是命题公式。
* @param pFormula: 要进行判断的表达式。该表达式的最后一个元素为“#”，而且规定* '#'仅用于指示该表达式的结尾，并不属于表达式的一部分。
* @return: 如果pFormula是命题公式，返回TRUE；否则返回FALSE。
*/
Boolean IsStatementFormula(pStatementFormula pFormula){
//Add your code here
}
Boolean IsStatementFormula(pStatementFormula pFormula){ //Add your code here StatementFormulaSymbles preS,currS,nextS;
int leftNum = 0,rightNum = 0;
preS = getCurrentSymbleType(pFormula);
switch(preS){
case Exception:return false;
case Conjunction:
case Disjunction:
case Implication:
case Equivalence:
case LeftParenthesis:leftNum++;break;
case RightParenthesis:
case EndOfFormula:return true; } nextPos(pFormula); currS = getCurrentSymbleType(pFormula);
switch(currS){
case LeftParenthesis:leftNum++;break;
case RightParenthesis:rightNum++;break;
case PropositionalVariable:
if(preS == PropositionalVariable)
return false; }
while (nextS != EndOfFormula){
nextPos(pFormula);
nextS = getCurrentSymbleType(pFormula);
if(nextS == LeftParenthesis) leftNum++;
if(nextS == RightParenthesis) rightNum++;
if(preS == Exception||currS == Exception||nextS == Exception)
return false;
if(currS == PropositionalVariable)
if(nextS == PropositionalVariable||preS == PropositionalVariable)
return false;
if(currS == Conjunction||currS == Disjunction||currS == Implication||currS == Equivalence)
if((preS != PropositionalVariable && preS != RightParenthesis) || (nextS != PropositionalVariable && nextS != LeftParenthesis && nextS != Negation))
return false;
if(nextS == Negation)
if(currS == PropositionalVariable||currS == RightParenthesis)
return false;
preS = currS;
currS = nextS; }
if(leftNum != rightNum)
return false;
return true; }
3.02⑤试设计一个递归算法，
验证一个表达式是不是命题公式(statement formula)。
实现下列函数：
/**
* 判断一个表达式是不是命题公式。
* @param pFormula: 要进行判断的表达式。该表达式的最后一个元素为“#”，而且规定
* '#'仅用于指示该表达式的结尾，并不属于表达式的一部分。
* @return: 如果pFormula是命题公式，返回TRUE；否则返回FALSE。
*/
Boolean IsStatementFormula(pStatementFormula pFormula){
//Add your code here
}
Boolean Function(int leftNum,int rightNum,StatementFormulaSymbles preS,StatementFormulaSymbles currS,StatementFormulaSymbles nextS,pStatementFormula pFormula)
{
nextPos(pFormula);//解释同上题所示
nextS = getCurrentSymbleType(pFormula);
if(nextS == LeftParenthesis)
leftNum++;
if(nextS == RightParenthesis)
rightNum++;
if(preS == Exception||currS == Exception||nextS == Exception)
return false;
if(currS == PropositionalVariable)
if(nextS == PropositionalVariable||preS == PropositionalVariable)
return false;
if(currS == Conjunction||currS == Disjunction||currS == Implication||currS == Equivalence) if((preS != PropositionalVariable && preS != RightParenthesis) || (nextS != PropositionalVariable && nextS != LeftParenthesis && nextS != Negation))
return false;
if(nextS == Negation)
if(currS == PropositionalVariable||currS == RightParenthesis)
return false;
preS = currS;
currS = nextS;
if(nextS != EndOfFormula)
{
return Function(leftNum,rightNum,preS,currS,nextS,pFormula);
}
if(leftNum != rightNum)
return false;
return true;
}
Boolean IsStatementFormula(pStatementFormula pFormula){
//Add your code here
StatementFormulaSymbles preS,currS,nextS;
/int leftNum = 0,rightNum = 0;
preS = getCurrentSymbleType(pFormula);
switch(preS)
{
case Exception:return false;//若取得了公式外的字符，则不是合法的命题公式case Conjunction:return false;
case Disjunction:return false;
case Implication:return false;
case Equivalence:return false;
case LeftParenthesis:leftNum++;break;//若为左括号，则leftNum的值自增一case RightParenthesis:return false;
case EndOfFormula:return true;//若命题公式只有结束符号‘#’，则为合法的命题公式
}
nextPos(pFormula);//指示器指向下一个字符
currS = getCurrentSymbleType(pFormula);
switch(currS)
{
case LeftParenthesis:leftNum++;break;//若为左括号，则leftNum的值自增一case RightParenthesis:rightNum++;break;//若为有括号，则RightNum的值自增一
case PropositionalVariable:
if(preS == PropositionalVariable)//当currS为命题变元时，若preS也为命题变元return false;
}
return Function(leftNum,rightNum,preS,currS,nextS,pFormula); //返回值的真假，同时调用函数Function }
6.01③试设计一算法，
实现集合的卡氏积运算。
实现下列函数：
/**
* 进行两个集合的卡氏积运算
* @param pA：要进行卡氏积运算的集合
* @param pB：要进行卡氏积运算的集合
* @return: 将pA和pB进行卡氏积运算后得到的集合
*/
pCartersianSet CartesianProduct(pOriginalSet pA, pOriginalSet pB)
{
//Add your code here
}
CH06 EX01
pCartersianSet CartesianProduct(pOriginalSet pA, pOriginalSet pB)
{
pOriginalSetElem pX=NULL;
pOriginalSetElem pY=NULL;
pOrderedCouple pOrder=NULL;
pCartersianSet pCarter=createNullCartersianSet(); //创建空的卡氏积集合
if(!isNullOriginalSet(pA) && !isNullOriginalSet(pB)) { //判断集合是否为空
resetOriginalSet(pA); //使A集合指针指向第一个元素
while(!isEndOfOriginalSet(pA)){
pX=getCurrentOriginalSetElem(pA); //取得A集合当前指针指向的元素
resetOriginalSet(pB); //使B集合指针指向第一个元素
while(!isEndOfOriginalSet(pB)){
pY=getCurrentOriginalSetElem(pB); //取得B集合当前指针指向的元素
pOrder=createOrderedCouple(pX,pY); //构造序偶对
OrderedCoupleInsertToCartersianSet(pCarter,pOrder); //将序偶插入到卡氏积集合
nextOriginalSetPos(pB); //指针后移
}
nextOriginalSetPos(pA); //指针后移
}
}
return pCarter;
}
6.02②试设计一算法，
给定集合A、集合B和集合C，判断集合C是否为A到B的一个二元关系。
实现下列函数：
/**
* 给定集合A、集合B和集合C，判断集合C是否为A到B的一个二元关系。
* @param pA：集合A
* @param pB：集合B
* @param pC：集合C
* @return: 如果集合C是A到B的一个二元关系，则返回true，否则返回false。
*/
boolean isBinaryRelation(pOriginalSet pA, pOriginalSet pB, pCartersianSet pC)
{
//Add your code here
}
CH06 EX02
boolean isBinaryRelation(pOriginalSet pA, pOriginalSet pB, pCartersianSet pC)
{
pOriginalSetElem pX=NULL;
pOriginalSetElem pY=NULL;
pOrderedCouple pZ=NULL;
pOrderedCouple pOrder=NULL;
pCartersianSet pCarter=createNullCartersianSet(); //创建空的卡氏积集合
boolean b=true;
if(!isNullOriginalSet(pA) && !isNullOriginalSet(pB)) { //判断集合是否为空
resetOriginalSet(pA); //使A集合指针指向第一个元素
while(!isEndOfOriginalSet(pA)){
pX=getCurrentOriginalSetElem(pA); //取得A集合当前指针指向的元素
resetOriginalSet(pB); //使B集合指针指向第一个元素
while(!isEndOfOriginalSet(pB)){
pY=getCurrentOriginalSetElem(pB); //取得B集合当前指针指向的元素
pOrder=createOrderedCouple(pX,pY); //构造序偶对
OrderedCoupleInsertToCartersianSet(pCarter,pOrder); //将序偶插入到卡氏积集合
nextOriginalSetPos(pB); //指针后移
}
nextOriginalSetPos(pA); //指针后移
}
}
resetCartersianSet(pC); //使C集合指针指向第一个元素
while(!isNullCartersianSet(pC) && !isEndOfCartersianSet(pC)){
pZ=getCurrentCartersianSetElem(pC); //取得C集合当前指针指向的元素
b=isInCartersianSet(pCarter,pZ); //判断序偶是否在pCArter集合中
if(b==false) break;
nextCartersianSetPos(pC); //指针后移
}
return b;
}
6.03②试设计一算法，求集合A上的恒等关系。
实现下列函数：
/**
* 给定集合A，求集合A上的恒等关系。
* @param pSet：原始集合
* @return: 集合A上的恒等关系。
*/
pCartersianSet IdentityRelation(pOriginalSet pSet)
{
//Add your code here
}
CH06 EX03
pCartersianSet IdentityRelation(pOriginalSet pSet)
{
pOriginalSetElem pX=NULL;
pOrderedCouple pOrder=NULL;
pCartersianSet pCarter=createNullCartersianSet(); //创建空的卡氏积集合
if(!isNullOriginalSet(pSet)) { //判断集合是否为空
resetOriginalSet(pSet); //使集合指针指向第一个元素
while(!isEndOfOriginalSet(pSet)){
pX=getCurrentOriginalSetElem(pSet); //取得集合当前指针指向的元素
pOrder=createOrderedCouple(pX,pX); //构造序偶对
OrderedCoupleInsertToCartersianSet(pCarter,pOrder); //将序偶插入到卡氏积集合
nextOriginalSetPos(pSet); //指针后移
}
}
return pCarter;
}
6.04③试设计一算法，求两个卡氏积集合的复合运算。
实现下列函数：
/**
* 给定两个集合，求该两个集合的复合运算。
* @param pA：卡氏积集合
* @param pB：卡氏积集合
* @return: pA与pB的复合运算结果。
*/
pCartersianSet CompositeOperation(pCartersianSet pA, pCartersianSet pB)
{
//Add your code here
}
CH06 EX04
pCartersianSet CompositeOperation(pCartersianSet pA, pCartersianSet pB)
{
pOriginalSetElem pX;
pOriginalSetElem pY;
pOriginalSetElem pXX;
pOriginalSetElem pYY;
pOrderedCouple pOrderA=NULL;
pOrderedCouple pOrderB=NULL;
pOrderedCouple pOrder=NULL;
pCartersianSet pCarter=createNullCartersianSet(); //创建空的卡氏积集合
if(!isNullCartersianSet(pA) && !isNullCartersianSet(pB))
{
resetCartersianSet(pA); //使A集合指针指向第一个元素
while(!isEndOfCartersianSet(pA)){
pOrderA=getCurrentCartersianSetElem(pA); //取得A集合当前指针指向的元素
resetCartersianSet(pB); //使B集合指针指向第一个元素
while(!isEndOfCartersianSet(pB)){
pOrderB=getCurrentCartersianSetElem(pB); //取得B集合当前指针指向的元素
pX=getFirstElemOfOrderedCouple(pOrderA); //取得A序偶的第一元
pY=getSecondElemOfOrderedCouple(pOrderA); //取得A序偶的第二元
pXX=getFirstElemOfOrderedCouple(pOrderB); //取得B序偶的第一元
pYY=getSecondElemOfOrderedCouple(pOrderB); //取得B序偶的第二元
if(pY==pXX)
{
pOrder=createOrderedCouple(pX,pYY); //构造序偶对
OrderedCoupleInsertToCartersianSet(pCarter,pOrder); //将序偶插入到卡氏积集合}
nextCartersianSetPos(pB); //指针后移
}
nextCartersianSetPos(pA); //指针后移
}
}
return pCarter;
}
6.05②试设计一算法，求一个关系的逆运算。
实现下列函数：
/**
* 求一个关系的逆运算。
* @param pA：卡氏积集合
* @return: pA的逆运算结果。
*/
pCartersianSet InverseOperation(pCartersianSet pA)
{
//Add your code here
}
CH06 EX05
pCartersianSet InverseOperation(pCartersianSet pA)
{
pOriginalSetElem pX;
pOriginalSetElem pY;
pOrderedCouple pOrderA=NULL;
pOrderedCouple pOrder=NULL;
pCartersianSet pCarter=createNullCartersianSet(); //创建空的卡氏积集合
if(!isNullCartersianSet(pA))
{
resetCartersianSet(pA); //使A集合指针指向第一个元素
while(!isEndOfCartersianSet(pA)){
pOrderA=getCurrentCartersianSetElem(pA); //取得A集合当前指针指向的元素
pX=getFirstElemOfOrderedCouple(pOrderA); //取得A序偶的第一元
pY=getSecondElemOfOrderedCouple(pOrderA); //取得A序偶的第二元
pOrder=createOrderedCouple(pY,pX); //构造序偶对
OrderedCoupleInsertToCartersianSet(pCarter,pOrder); //将序偶插入到卡氏积集合
nextCartersianSetPos(pA); //指针后移
}
}
return pCarter;
}
6.06④试设计一算法，对某集合A上的一个二元关系，求该关系的幂运算。
实现下列函数：
/**
* 求一个关系的幂运算。
* @param pA：原始集合
* @param pBinaryRelationR：pA上的关系R
* @param n：幂运算的次数，且n >= 0
* @return: pBinaryRelationSet的n次幂运算结果。
*/
pCartersianSet PowOperation(pOriginalSet pA,
pCartersianSet pBinaryRelationR,
int n)
{
//Add your code here
}
CH06 EX06
pCartersianSet CompositeOperation(pCartersianSet pA, pCartersianSet pB)
{ pCartersianSet pC=createNullCartersianSet();
for(resetCartersianSet(pA);!isEndOfCartersianSet(pA); nextCartersianSetPos(pA))
{
for(resetCartersianSet(pB);!isEndOfCartersianSet(pB); nextCartersianSetPos(pB))
if(isEqualOriginalSetElem(getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pA)),getFirstElemOfOrd eredCouple(getCurrentCartersianSetElem(pB))))
//获取A卡氏积中序偶的第二元//获取第二元
OrderedCoupleInsertToCartersianSet(pC,createOrderedCouple(getFirstElemOfOrderedCouple(getCurrentCartersia nSetElem(pA)),getSecondElemOfOrderedCouple(getCurrentCartersianSetElem(pB))) );
}
return pC;
}
pCartersianSet PowOperation(pOriginalSet pA,
pCartersianSet pBinaryRelationR,
int n)
{
pCartersianSet pC=createNullCartersianSet();
pC=copyCartersianSet(pBinaryRelationR);
if(n==0)
{
/********** 【习题】请编写函数func(char s[], char t[], int n)， 由数组s中长度为n的字符序列构造其逆序列，并存储在数组t中。例如，由给定字符序列?慜敲求得逆序列?敜慲；由?瑜浩履 求得?敜業屴。 **********/ void func(char s[], char t[], int n) /* 数组s的前n个元素存放给定的字符序列， 数组t的前n个元素存放s的逆序列。 注意：数组的下标从0开始。 */ { for(int i=0;i 《离散数学》题库答案 一、选择或填空 (数理逻辑部分) 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q →P (2)?Q=>P →Q (3)P=>P →Q (4)?P ∧(P ∨Q)=>?P 答:(1),(4) 2、下列公式中哪些就是永真式？( ) (1)(┐P ∧Q)→(Q →?R) (2)P →(Q →Q) (3)(P ∧Q)→P (4)P →(P ∨Q) 答:(2),(3),(4) 3、设有下列公式,请问哪几个就是永真蕴涵式?( ) (1)P=>P ∧Q (2) P ∧Q=>P (3) P ∧Q=>P ∨Q (4)P ∧(P →Q)=>Q (5) ?(P →Q)=>P (6) ?P ∧(P ∨Q)=>?P 答:(2),(3),(4),(5),(6) 4、公式?x((A(x)→B(y,x))∧ ?z C(y,z))→D(x)中,自由变元就是( ),约束变元就是( )。 答:x,y, x,z 5、判断下列语句就是不就是命题。若就是,给出命题的真值。( ) (1) 北京就是中华人民共与国的首都。 (2) 陕西师大就是一座工厂。 (3) 您喜欢唱歌不？ (4) 若7+8＞18,则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答:(1) 就是,T (2) 就是,F (3) 不就是 (4) 就是,T (5) 不就是 (6) 不就是 6、命题“存在一些人就是大学生”的否定就是( ),而命题“所有的人都就是要死的”的否定就是( )。 答:所有人都不就是大学生,有些人不会死 7、设P:我生病,Q:我去学校,则下列命题可符号化为( )。 (1) 只有在生病时,我才不去学校 (2) 若我生病,则我不去学校 (3) 当且仅当我生病时,我才不去学校(4) 若我不生病,则我一定去学校 答:(1) P Q →? (2) Q P ?→ (3) Q P ?? (4)Q P →? 8、设个体域为整数集,则下列公式的意义就是( )。 (1) ?x ?y(x+y=0) (2) ?y ?x(x+y=0) 答:(1)对任一整数x 存在整数 y 满足x+y=0(2)存在整数y 对任一整数x 满足x+y=0 9、设全体域D 就是正整数集合,确定下列命题的真值: (1) ?x ?y (xy=y) ( ) (2) ?x ?y(x+y=y) ( ) (3) ?x ?y(x+y=x) ( ) (4) ?x ?y(y=2x) ( ) 答:(1) F (2) F (3)F (4)T 10、设谓词P(x):x 就是奇数,Q(x):x 就是偶数,谓词公式 ?x(P(x)∨Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答:(1) 11、命题“2就是偶数或-3就是负数”的否定就是( )。 答:2不就是偶数且-3不就是负数。 12、永真式的否定就是( ) (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( A )。 (A) 您打算考硕士研究生不？ (B) 太阳系以外的星球上有生物。 (C) 离散数学就是计算机系的一门必修课。 (D) 雪就是黑色的。 ?命题公式P→(P∨?P)的类型就是( A ) (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A就是重言式,那么A的否定式就是( A ) A、矛盾式 B、重言式 C、可满足式 D、不能确定 ?以下命题公式中,为永假式的就是( C ) A、p→(p∨q∨r) B、(p→┐p)→┐p C、┐(q→q)∧p D、┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值就是( D ) A、 00,11 B、 00,01,11 C、10,11 D、 10 ?谓词公式) x xP∧ ?中,变元x就是 ( B ) R , ( x ) (y A、自由变元 B、既就是自由变元也就是约束变元 C、约束变元 D、既不就是自由变元也不就是约束变元 ?命题公式P→(Q∨?Q)的类型就是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x,) x x→ ?等值于( A ) A ) ( (B A、B (D、B x xA→ x ?) ( ( ?C、B x∧ A ?) (B、) ?) xA→ x ) ( A x (B x∨ ?下列语句中就是真命题的就是( D )。 A.您就是杰克不？ B.凡石头都可练成金。 C.如果2+2=4,那么雪就是黑的。 D.如果1+2=4,那么雪就是黑的。 ?从集合分类的角度瞧,命题公式可分为( B ) A、永真式、矛盾式 B、永真式、可满足式、矛盾式 C、可满足式、矛盾式 D、永真式、可满足式 ?命题公式﹁p∨﹁q等价于( D )。 A、﹁p∨q B、﹁(p∨q) C、﹁p∧q D、 p→﹁q ?一个公式在等价意义下,下面写法唯一的就是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ?下列含有命题p,q,r的公式中,就是主析取范式的就是( D )。 离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（pr）∧(﹁q∨s) ?（01）∧(1∨1) ?0∧1?0. （3）（?p∧?q∧r）(p∧q∧﹁r) ?（1∧1∧1） (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧r) ?(?p∧?q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 （5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q) ?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(?p→q)→(?q∨p) /********** 【习题5.002】编写程序，利用while语句在同一行中 逐个显示从1至5的数字，每个数字之前保留2个空格。**********/ void main() { int i=1; while(i<=5) { printf(" %d",i); i++; } } /********** 【习题5.003】编写程序，利用for语句在同一行中逐个 显示从1至6的数字，每个数字之前保留2个空格。 **********/ void main() { for(int i=1;i<=6;i++) printf(" %d",i); } /********** 【习题5.004】n是系统给定的外部整型变量（不需要 自行定义）。编写程序，利用循环语句在同一行中逐 个显示从1至n的数字，每个数字之前保留2个空格。**********/ void main() { for(int i=1;i<=n;i++) printf(" %d",i) ; } /********** 【习题5.012】请仅在程序空缺处填入合适内容，使其 实现功能：依次输入5个整数，计算它们之和并输出。**********/ #include { scanf("%d",&n); sum=sum+n; } printf("sum = %d",sum); } /********** 【习题5.020】n和s是系统给定的外部整型变量（不需要 自行定义）。编写程序，求1到n之间的整数之和，并将结果存放到s。 **********/ void main() { for(int i=1;i<=n;i++) s+=i; } /********** 【习题5.022】n是系统给定的外部变量。编写程序， 求1到n间的自然数之和。请定义局部变量s存放求和 的结果，并用下列语句输出结果 printf("1+2+...+n=%d\n",s); 《离散数学》题库与答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( A ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别） 2、下列公式中哪些是永真式？( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）可用蕴含等值式证明 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式 4、公式x((A(x)B(y，x))z C(y，z))D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z（考察定义在公式x A和x A中，称x为指导变元，A为量词的辖域。在x A和x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元） 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1)北京是中华人民共和国的首都。(2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？(4) 若7+8＞18，则三角形有4条边。 (5) 前进！(6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是（命题必须满足是陈述句，不能是疑问句或者祈使句。） 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死（命题的否定就是把命题前提中的量词“换成存在，换成”，然后将命题的结论否定，“且变或或变且”） 7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校(2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1）P ?（注意“只有……才……”和“除非……就……”两者都是一个 Q→ 形式的）（2）Q P→ ? P? ?（4）Q P? →（3）Q 8、设个体域为整数集，则下列公式的意义是( )。 (1) x y(x+y=0) (2) y x(x+y=0) 答：（1）对任一整数x存在整数y满足x+y=0 （2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值： (1) x y (xy=y) ( ) (2) x y(x+y=y) ( ) (3) x y(x+y=x) ( ) (4) x y(y=2x) ( ) 答：（1）F (反证法：假若存在，则（x- 1）*y=0 对所有的x都成立，显然这个与前提条件相矛盾) （2）F （同理）（3）F （同理）（4）T（对任一整数x存在整数y满足条件y=2x 很明显是正确的） 试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统 二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。 本科高等数学离散数学试题及答案 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________，_____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。 【题目】若两棵二叉树T1和T2皆为空，或者皆不空且T1的左、右子树和T2的左、右子树分别相似，则称二叉树T1和T2相似。试编写算法，判别给定两棵二叉树是否相似。 二叉链表类型定义： typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; **********/ Status Similar(BiTree T1, BiTree T2) /* 判断两棵二叉树是否相似的递归算法*/ { if(!T1&&!T2)//同为空时，两树相似 return TRUE; else if(T1&&T1){ if(Similar(T1 -> lchild,T2 -> lchild) && Similar(T1 -> rchild,T2 -> rchild)) //两树都不为空时，判断左右子树是否相似 return TRUE; else return FALSE; }else//以上两种情况都不符合，就直接返回FALSE return FALSE; } /********** 【题目】编写递归算法，求对二叉树T先序遍历时 第k个访问的结点的值。 二叉链表类型定义： typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; **********/ TElemType PreOrder(BiTree T, int &k) { TElemType x='#'; if(T==NULL)return '#'; if(k==1)return T->data; if(T->lchild!=NULL) { k--; x=PreOrder(T->lchild,k); } if(T->rchild!=NULL&&x=='#') 《离散数学》期末复习题 一、填空题（每空2分，共20分） 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c}，B={a,b,c,d,e}，则A?B= 。 4、集合A={1,2,3,4}，B={1,3,5,7,9}，则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3｝，A上的二元运算定义为：a* b = a和b两者的最大值，则 2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法，是加法的幂等元， 是乘法的幂等元。 9、设a,b,c是阿贝尔群 19、代数系统是指由及其上的或 组成的系统。 20、设 离散数学试题及答案 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B ＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________， _____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。 广工Anyview试题答案-第五章 /********** 【习题5.002】编写程序，利用while语句在同一行中 逐个显示从1至5的数字，每个数字之前保留2个空格。 **********/ void main() { int i=1; while(i<=5) { printf(" %d",i); i++; } } /********** 【习题5.003】编写程序，利用for语句在同一行中逐个 显示从1至6的数字，每个数字之前保留2个空格。 **********/ void main() { for(int i=1;i<=6;i++) printf(" %d",i); } /********** 【习题5.004】n是系统给定的外部整型变量（不需要 自行定义）。编写程序，利用循环语句在同一行中逐 个显示从1至n的数字，每个数字之前保留2个空格。 **********/ void main() { for(int i=1;i<=n;i++) printf(" %d",i) ; } /********** 【习题5.012】请仅在程序空缺处填入合适内容， 使其 实现功能：依次输入5个整数，计算它们之和并输出。 **********/ #include 《离散数学》题库答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q →P (2)?Q=>P →Q (3)P=>P →Q (4)?P ∧(P ∨Q)=>?P 答：（1），（4） 2、下列公式中哪些是永真式？( ) (1)(┐P ∧Q)→(Q →?R) (2)P →(Q →Q) (3)(P ∧Q)→P (4)P →(P ∨Q) 答：（2），（3），（4） 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P ∧Q (2) P ∧Q=>P (3) P ∧Q=>P ∨Q (4)P ∧(P →Q)=>Q (5) ?(P →Q)=>P (6) ?P ∧(P ∨Q)=>?P 答：（2），（3），（4），（5），（6） 4、公式 x((A(x) B(y ，x)) z C(y ，z))D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1） 是，T （2） 是，F （3） 不是 （4） 是，T （5） 不是 （6） 不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死 7、设P ：我生病，Q ：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校 答：（1） P Q →? （2） Q P ?→ （3） Q P ?? （4）Q P →? 8、设个体域为整数集，则下列公式的意义是( )。 (1) x y(x+y=0) (2) y x(x+y=0) 答：（1）对任一整数x 存在整数 y 满足x+y=0（2）存在整数y 对任一整数x 满足x+y=0 9、设全体域D 是正整数集合，确定下列命题的真值： (1) x y (xy=y) ( ) (2) x y(x+y=y) ( ) (3) x y(x+y=x) ( ) (4) x y(y=2x) ( ) 答：（1） F （2） F （3）F （4）T 10、设谓词P(x)：x 是奇数，Q(x)：x 是偶数，谓词公式 x(P(x)Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答：（1） 11、命题“2是偶数或-3是负数”的否定是（ ）。 答：2不是偶数且-3不是负数。 12、永真式的否定是（ ） (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 答：（2） 13、公式(?P ∧Q)∨(?P ∧?Q)化简为（ ），公式 Q →(P ∨(P ∧Q))可化简为（ ）。 答：?P ，Q →P 离散数学练习题 第一章 一．填空 1.公式) ∨ ? ∧的成真赋值为 01；10 ? p∧ ( (q ) p q 2.设p, r为真命题，q, s 为假命题，则复合命题) ? ? →的真值为 0 p→ ( q (s ) r 3.公式) ∨ ? p∧ q ?与共同的成真赋值为 01；10 ? ∧ p ( ) ) (q q p ( 4.设A为任意的公式，B为重言式，则B A∨的类型为重言式 5．设p, q均为命题，在不能同时为真条件下，p与q的排斥也可以写成p与q的相容或。 二．将下列命题符合化 1. 7不是无理数是不对的。 解：) ? ?，其中p: 7是无理数；或p，其中p: 7是无理数。 (p 2.小刘既不怕吃苦，又很爱钻研。 解：其中 ?p: 小刘怕吃苦，q：小刘很爱钻研 p∧ ,q 3.只有不怕困难，才能战胜困难。 解：p →，其中p: 怕困难，q: 战胜困难 q? 或q →，其中p: 怕困难， q: 战胜困难 p? 4.只要别人有困难，老王就帮助别人，除非困难解决了。 解：) → ?，其中p: 别人有困难，q:老王帮助别人，r: 困难解决了 p (q r→ 或：q ?) (，其中p:别人有困难，q: 老王帮助别人，r: 困难解决了r→ ∧ p 5.整数n是整数当且仅当n能被2整除。 解：q p?，其中p: 整数n是偶数，q: 整数n能被2整除 三、求复合命题的真值 P：2能整除5， q：旧金山是美国的首都， r：在中国一年分四季 1. )) p∧ → q ∨ r → ∧ ((q r ( ) ( ) p 2.r ?) → (( → (( ∨ ) ( )) p r p ∨ p q ? ∧ ? q∧ 解：p, q 为假命题，r为真命题 1.)) p∧ → q ∨的真值为0 r → ∧ ( ) ( ) ((q p r /**********【习题】请编写函数func(char s[], char t[], int n)， 由数组s中长度为n的字符序列构造其逆序列，并存储在数组t中。 例如，由给定字符序列s="are"求得逆序列t="era"；由s="time" 求得t="emit"。 **********/ void func(char s[], char t[], int n) /* 数组s的前n个元素存放给定的字符序列， 数组t的前n个元素存放s的逆序列。 注意：数组的下标从0开始。 */ { for(int i=0;i 1 / 15 离散数学（2）复习题 一、单项选择题 1、由集合运算定义，下列各式正确的有（ A ）。 A.X ?X ?Y B.X ?X ?Y C.X ?X ?Y D.Y ?X ?Y 2、设A B -=?，则有（ C ）。 A.B =? B.B ≠? C.A B ? D.A B ? 3、对任意的集合A 、全集U ，下列命题为假的是（ D ）。 A.A ?? ＝A ， B.A ?U = U C.A ?? = ?， D.A ?U = U 4、集合A={1，2，…，10}上的关系R={ /********** 【习题4.011】关系表达式，if语句第一种形式 在以下程序空缺处填写合适内容，使得程序判断用户输入的字符是否为'@'，若是则显示："输入正确"。**********/ #include printf("False!\n"); return 0; } /********** 【习题4.016】if语句的子句为复合语句 在以下程序空缺处填写合适内容，使得程序将输入到变量a和b的两个整数按照由大到小的顺序输出。**********/ #include 离散数学习题答案 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ?→∧∧ 解：原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式， 所以成真赋值为011，111。 6、求下列公式的主合取范式，并求成假赋值： | （2）()()p q p r ∧∨?∨ 解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式， 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()p q r ∧∨ 解：原式()(()())p q r r p p q 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 p q r ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨，此即主析取范式。 ； 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式： （1）()()p q p r ∨∨?∧ 解：公式的真值表如下： , 由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式 1234567m m m m m m m ?∨∨∨∨∨∨ 习题三及答案：（P52-54） 11、填充下面推理证明中没有写出的推理规则。 前提：,,,p q q r r s p ?∨?∨→ 结论：s 证明： ① p 前提引入 ② p q ?∨ 前提引入 — ③ q ①②析取三段论 ④ q r ?∨ 前提引入 ⑤ r ③④析取三段论 ⑥ r s → 前提引入 ⑦ s ⑤⑥假言推理 15、在自然推理系统P 中用附加前提法证明下面推理： （2）前提：()(),()p q r s s t u ∨→∧∨→ 结论：p u → 证明：用附加前提证明法。 ' ① p 附加前提引入 ② p q ∨ ①附加 ③ ()()p q r s ∨→∧ 前提引入山东大学离散数学题库及答案
离散数学题库及答案
离散数学答案屈婉玲版第二版 高等教育出版社课后答案
广工Anyview试题答案第五章
《离散数学》题库及答案
离散数学试题与答案
大学本科高等数学《离散数学》试题及答案
2016最新广工anyview数据结构答案
中国石油大学大学《离散数学》期末复习题及答案
离散数学试题及答案(1)
广工Anyview试题答案-第五章
山东大学离散数学题库及答案
离散数学章练习题及答案
广工Anyview试题答案第八章
021046[离散数学(2)] 天津大学机考题库答案
广工Anyview试题答案 第四章
离散数学习题答案(耿素云屈婉玲)
相关主题
文本预览