P3825 [NOI2017]游戏

如何证明原命题与其逆否命题具有相同的真假性,请给出证明
用反证法
设原命题为“若p则q”,则逆否命题为“若非q则非p”
假设“原命题与其逆否命题具有相同的真假性”错误
则有“若p→q为真,则 非q→非p为假”
或“若p→q为假,则 非q→非p为真”
1,若p→q为真,则 非q→非p为假
因为非q→非p为假,所以非q→p为真 这与 p→q为真 矛盾
2,若p→q为假,则 非q→非p为真
因为p→q为假,所以p→非q为真 这与 非q→非p为真 矛盾
所以假设均不成立,所以原命题与其逆否命题具有相同的真假性,得证.
反证法成立的原理就是逆否命题和原命题等价?
你瞎说什么呢.
反证法是排除其它一切可能,只剩这一种可能,和逆否命题和原命题等价一点关系都没有的好吧
证明链接：https://www.zybang.com/question/2622b4d2c390a64ddaee7580b5b23ac5.html

    #include"stdio.h"
    #include"string.h"
    #include"vector"
    #include"algorithm"
    using namespace std;
    #define OK printf("\n");
    #define exit return 0;
    const int N = 1e6 * 2 + 1010;
    const int M = 2 * N;
    int read()
    {
        int f=1,x=0;
        char ss=getchar();
        while(ss<‘0‘||ss>‘9‘){if(ss==‘-‘)f=-1;ss=getchar();}
        while(ss>=‘0‘&&ss<=‘9‘){x=x*10+ss-‘0‘;ss=getchar();}
        return f*x;
    }
    int head[N],ver[M],Next[M],tot;int n,m,num,top,cnt;
    int dfn[N],low[N],id[110];int limit = 0;
    int Stack[N],ins[N],c[N];
    int s[N];  char str[N];
    int X[N],Y[N]; char cx[N],cy[N];

    void add(int x,int y){
        ver[++ tot] = y; Next[tot] = head[x];
        head[x] = tot;
    }

    void tarjan(int x){
        dfn[x] = low[x] = ++ num;
        Stack[++ top] = x; ins[x] = 1;
        for(int i = head[x]; i; i = Next[i])
            if(!dfn[ver[i]]) {
                tarjan(ver[i]);
                low[x] = min(low[x],low[ver[i]]);
            } else if(ins[ver[i]])
             low[x] = min(low[x],dfn[ver[i]]);
        if(dfn[x] == low[x]){
            cnt ++; int y;
            do{
                y = Stack[top --];ins[y] = 0;
                c[y] = cnt;
            } while(x != y);
        }
    }

    void Build_edge()
    {
       for(int i = 1; i <= m; i ++){
            if(str[X[i]] == cx[i]) continue;
            if(str[Y[i]] == cy[i]) {
                if(cx[i] == ‘C‘ || (cx[i] == ‘B‘ && str[X[i]] == ‘C‘)) {
                   add(X[i] + n,X[i]); //printf("%d -> %d\n",X[i] + n,X[i]);
                } else {
                    add(X[i],X[i] + n); //printf("%d -> %d\n",X[i],X[i] + n);
                }
                continue;
            }
            int v1 = (cy[i] == ‘C‘ || (cy[i] == ‘B‘ && str[Y[i]] == ‘C‘)) ? 1 : 0;
            int v2 = (cx[i] == ‘C‘ || (cx[i] == ‘B‘ && str[X[i]] == ‘C‘)) ? 1 : 0;
            add(X[i] + n * (v2),Y[i] + n * v1);
            add(Y[i] + n * (v1 ^ 1),X[i] + n * (v2 ^ 1));
           // printf("%d -> %d\n",X[i] + n *(v2),Y[i] + n * v1);
          //  printf("%d -> %d\n",Y[i] + n * (v1 ^ 1),X[i] + n * (v2 ^ 1));
        }
        return ;
    }
    void init()
    {
        num = 0; memset(ins,0,sizeof(ins));
        cnt = 0; tot = 0; top = 0;
        memset(low,0,sizeof(low)); memset(c,0,sizeof(c));
        memset(dfn,0,sizeof(dfn));memset(Stack,0,sizeof(Stack));
        memset(head,0,sizeof(head));
    }
    void solve(){

        int mark = 1;
        for(int i = 0; i < (1 << limit); i ++){
            init();mark = 1;
            for(int j = 1; j <= limit; j ++){
                str[id[j]] = (i & (1 << (j - 1))) ? ‘A‘ : ‘B‘;
            }
            Build_edge();
            for(int i = 1; i <= n * 2; i ++){
                if(!dfn[i]) tarjan(i);
            }
            for(int i = 1; i <= n; i ++)
              if(c[i] == c[i + n]) {mark = 0; break;}
            if(mark == 0) continue;
            for(int i = 1; i <= n; i ++){
                if(c[i] < c[i + n]){
                    if(str[i] == ‘A‘) printf("B");
                    else printf("A");
                } else {
                    if(str[i] == ‘C‘) printf("B");
                    else printf("C");
                }
            }
            return ;
        }
        printf("-1"); return ;
    }
    int main()
    {
        int d;
        scanf("%d%d",&n,&d);
        scanf("%s",str + 1);
        for(int i = 1; i <= n; i ++)
         {
             if(str[i] == ‘x‘) id[++ limit] = i;
             else str[i] -= 32;
         }
        m = read();
        for(int i = 1; i <= m; i ++){
           scanf("%d %c %d %c",&X[i],&cx[i],&Y[i],&cy[i]);
        }
        solve();
        return 0;
    }