18.92/7.38	YES
19.06/7.47	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
19.06/7.47	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
19.06/7.47	
19.06/7.47	
19.06/7.47	Termination of the given ETRS could be proven:
19.06/7.47	
19.06/7.47	(0) ETRS
19.06/7.47	(1) EquationalDependencyPairsProof [EQUIVALENT, 84 ms]
19.06/7.47	(2) EDP
19.06/7.47	(3) EDependencyGraphProof [EQUIVALENT, 0 ms]
19.06/7.47	(4) AND
19.06/7.47	    (5) EDP
19.06/7.47	        (6) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
19.06/7.47	        (7) EDP
19.06/7.47	        (8) EUsableRulesReductionPairsProof [EQUIVALENT, 30 ms]
19.06/7.47	        (9) EDP
19.06/7.47	        (10) EDependencyGraphProof [EQUIVALENT, 0 ms]
19.06/7.47	        (11) TRUE
19.06/7.47	    (12) EDP
19.06/7.47	        (13) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
19.06/7.47	        (14) EDP
19.06/7.47	        (15) EDPPoloProof [EQUIVALENT, 19 ms]
19.06/7.47	        (16) EDP
19.06/7.47	        (17) PisEmptyProof [EQUIVALENT, 0 ms]
19.06/7.47	        (18) YES
19.06/7.47	    (19) EDP
19.06/7.47	        (20) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
19.06/7.47	        (21) EDP
19.06/7.47	        (22) EDPPoloProof [EQUIVALENT, 199 ms]
19.06/7.47	        (23) EDP
19.06/7.47	        (24) EDependencyGraphProof [EQUIVALENT, 0 ms]
19.06/7.47	        (25) EDP
19.06/7.47	        (26) EDPPoloProof [EQUIVALENT, 454 ms]
19.06/7.47	        (27) EDP
19.06/7.47	        (28) EDPPoloProof [EQUIVALENT, 412 ms]
19.06/7.47	        (29) EDP
19.06/7.47	        (30) EDPPoloProof [EQUIVALENT, 382 ms]
19.06/7.47	        (31) EDP
19.06/7.47	        (32) PisEmptyProof [EQUIVALENT, 0 ms]
19.06/7.47	        (33) YES
19.06/7.47	    (34) EDP
19.06/7.47	        (35) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
19.06/7.47	        (36) EDP
19.06/7.47	        (37) EDPPoloProof [EQUIVALENT, 664 ms]
19.06/7.47	        (38) EDP
19.06/7.47	        (39) PisEmptyProof [EQUIVALENT, 0 ms]
19.06/7.47	        (40) YES
19.06/7.47	
19.06/7.47	
19.06/7.47	----------------------------------------
19.06/7.47	
19.06/7.47	(0)
19.06/7.47	Obligation:
19.06/7.47	Equational rewrite system:
19.06/7.47	The TRS R consists of the following rules:
19.06/7.47	
19.06/7.47	   U101(tt, A, B) -> U102(isBool(B), A, B)
19.06/7.47	   U102(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B))
19.06/7.47	   U11(tt, A) -> A
19.06/7.47	   U111(tt) -> false
19.06/7.47	   U121(tt, A) -> A
19.06/7.47	   U131(tt, B, U', U) -> U132(isS(U'), B, U', U)
19.06/7.47	   U132(tt, B, U', U) -> U133(isS(U), B, U')
19.06/7.47	   U133(tt, B, U') -> U134(equal(_isNotEqualTo_(B, true), true), U')
19.06/7.47	   U134(tt, U') -> U'
19.06/7.47	   U141(tt, U) -> U142(isS(U), U)
19.06/7.47	   U142(tt, U) -> U
19.06/7.47	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.47	   U152(tt) -> tt
19.06/7.47	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.47	   U162(tt) -> tt
19.06/7.47	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.47	   U172(tt) -> tt
19.06/7.47	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.47	   U182(tt) -> tt
19.06/7.47	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.47	   U192(tt) -> tt
19.06/7.47	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.47	   U202(tt) -> tt
19.06/7.47	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.47	   U211(tt) -> tt
19.06/7.47	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.47	   U221(tt, A) -> _xor_(A, true)
19.06/7.47	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.47	   U31(tt) -> false
19.06/7.47	   U41(tt, A) -> A
19.06/7.47	   U51(tt, A, B) -> U52(isBool(B), A, B)
19.06/7.47	   U52(tt, A, B) -> not_(_xor_(A, _and_(A, B)))
19.06/7.47	   U61(tt, U', U) -> U62(isS(U), U', U)
19.06/7.47	   U62(tt, U', U) -> U63(equal(_isNotEqualTo_(U, U'), true))
19.06/7.47	   U63(tt) -> false
19.06/7.47	   U71(tt) -> true
19.06/7.47	   U81(tt, U', U) -> U82(isS(U), U', U)
19.06/7.47	   U82(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true)
19.06/7.47	   U91(tt) -> false
19.06/7.47	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.47	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.47	   _and_(false, A) -> U31(isBool(A))
19.06/7.47	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.47	   _implies_(A, B) -> U51(isBool(A), A, B)
19.06/7.47	   _isEqualTo_(U, U') -> U61(isS(U'), U', U)
19.06/7.47	   _isEqualTo_(U, U) -> U71(isS(U))
19.06/7.47	   _isNotEqualTo_(U, U') -> U81(isS(U'), U', U)
19.06/7.47	   _isNotEqualTo_(U, U) -> U91(isS(U))
19.06/7.47	   _or_(A, B) -> U101(isBool(A), A, B)
19.06/7.47	   _xor_(A, A) -> U111(isBool(A))
19.06/7.47	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.47	   equal(X, X) -> tt
19.06/7.47	   if_then_else_fi(B, U, U') -> U131(isBool(B), B, U', U)
19.06/7.47	   if_then_else_fi(true, U, U') -> U141(isS(U'), U)
19.06/7.47	   isBool(false) -> tt
19.06/7.47	   isBool(true) -> tt
19.06/7.47	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.47	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.47	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.47	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.47	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.47	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.47	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.47	   not_(A) -> U221(isBool(A), A)
19.06/7.47	   not_(false) -> true
19.06/7.47	   not_(true) -> false
19.06/7.47	
19.06/7.47	The set E consists of the following equations:
19.06/7.47	
19.06/7.47	   _and_(x, y) == _and_(y, x)
19.06/7.47	   _or_(x, y) == _or_(y, x)
19.06/7.47	   _xor_(x, y) == _xor_(y, x)
19.06/7.47	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.47	   _or_(_or_(x, y), z) == _or_(x, _or_(y, z))
19.06/7.47	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.47	
19.06/7.47	
19.06/7.47	----------------------------------------
19.06/7.47	
19.06/7.47	(1) EquationalDependencyPairsProof (EQUIVALENT)
19.06/7.47	Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem:
19.06/7.47	The TRS P consists of the following rules:
19.06/7.47	
19.06/7.47	   U101^1(tt, A, B) -> U102^1(isBool(B), A, B)
19.06/7.47	   U101^1(tt, A, B) -> ISBOOL(B)
19.06/7.47	   U102^1(tt, A, B) -> _XOR_(_and_(A, B), _xor_(A, B))
19.06/7.47	   U102^1(tt, A, B) -> _AND_(A, B)
19.06/7.47	   U102^1(tt, A, B) -> _XOR_(A, B)
19.06/7.47	   U131^1(tt, B, U', U) -> U132^1(isS(U'), B, U', U)
19.06/7.47	   U132^1(tt, B, U', U) -> U133^1(isS(U), B, U')
19.06/7.47	   U133^1(tt, B, U') -> U134^1(equal(_isNotEqualTo_(B, true), true), U')
19.06/7.47	   U133^1(tt, B, U') -> EQUAL(_isNotEqualTo_(B, true), true)
19.06/7.47	   U133^1(tt, B, U') -> _ISNOTEQUALTO_(B, true)
19.06/7.47	   U141^1(tt, U) -> U142^1(isS(U), U)
19.06/7.47	   U151^1(tt, V2) -> U152^1(isBool(V2))
19.06/7.47	   U151^1(tt, V2) -> ISBOOL(V2)
19.06/7.47	   U161^1(tt, V2) -> U162^1(isBool(V2))
19.06/7.47	   U161^1(tt, V2) -> ISBOOL(V2)
19.06/7.47	   U171^1(tt, V2) -> U172^1(isUniversal(V2))
19.06/7.47	   U181^1(tt, V2) -> U182^1(isUniversal(V2))
19.06/7.47	   U191^1(tt, V2) -> U192^1(isBool(V2))
19.06/7.47	   U191^1(tt, V2) -> ISBOOL(V2)
19.06/7.47	   U201^1(tt, V2) -> U202^1(isBool(V2))
19.06/7.47	   U201^1(tt, V2) -> ISBOOL(V2)
19.06/7.47	   U21^1(tt, A, B, C) -> U22^1(isBool(B), A, B, C)
19.06/7.47	   U21^1(tt, A, B, C) -> ISBOOL(B)
19.06/7.47	   U22^1(tt, A, B, C) -> U23^1(isBool(C), A, B, C)
19.06/7.47	   U22^1(tt, A, B, C) -> ISBOOL(C)
19.06/7.47	   U221^1(tt, A) -> _XOR_(A, true)
19.06/7.47	   U23^1(tt, A, B, C) -> _XOR_(_and_(A, B), _and_(A, C))
19.06/7.47	   U23^1(tt, A, B, C) -> _AND_(A, B)
19.06/7.47	   U23^1(tt, A, B, C) -> _AND_(A, C)
19.06/7.47	   U51^1(tt, A, B) -> U52^1(isBool(B), A, B)
19.06/7.47	   U51^1(tt, A, B) -> ISBOOL(B)
19.06/7.47	   U52^1(tt, A, B) -> NOT_(_xor_(A, _and_(A, B)))
19.06/7.47	   U52^1(tt, A, B) -> _XOR_(A, _and_(A, B))
19.06/7.47	   U52^1(tt, A, B) -> _AND_(A, B)
19.06/7.47	   U61^1(tt, U', U) -> U62^1(isS(U), U', U)
19.06/7.47	   U62^1(tt, U', U) -> U63^1(equal(_isNotEqualTo_(U, U'), true))
19.06/7.47	   U62^1(tt, U', U) -> EQUAL(_isNotEqualTo_(U, U'), true)
19.06/7.47	   U62^1(tt, U', U) -> _ISNOTEQUALTO_(U, U')
19.06/7.47	   U81^1(tt, U', U) -> U82^1(isS(U), U', U)
19.06/7.47	   U82^1(tt, U', U) -> IF_THEN_ELSE_FI(_isEqualTo_(U, U'), false, true)
19.06/7.47	   U82^1(tt, U', U) -> _ISEQUALTO_(U, U')
19.06/7.47	   _AND_(A, A) -> U11^1(isBool(A), A)
19.06/7.47	   _AND_(A, A) -> ISBOOL(A)
19.06/7.47	   _AND_(A, _xor_(B, C)) -> U21^1(isBool(A), A, B, C)
19.06/7.47	   _AND_(A, _xor_(B, C)) -> ISBOOL(A)
19.06/7.47	   _AND_(false, A) -> U31^1(isBool(A))
19.06/7.47	   _AND_(false, A) -> ISBOOL(A)
19.06/7.47	   _AND_(true, A) -> U41^1(isBool(A), A)
19.06/7.47	   _AND_(true, A) -> ISBOOL(A)
19.06/7.47	   _IMPLIES_(A, B) -> U51^1(isBool(A), A, B)
19.06/7.47	   _IMPLIES_(A, B) -> ISBOOL(A)
19.06/7.47	   _ISEQUALTO_(U, U') -> U61^1(isS(U'), U', U)
19.06/7.47	   _ISEQUALTO_(U, U) -> U71^1(isS(U))
19.06/7.47	   _ISNOTEQUALTO_(U, U') -> U81^1(isS(U'), U', U)
19.06/7.47	   _ISNOTEQUALTO_(U, U) -> U91^1(isS(U))
19.06/7.47	   _OR_(A, B) -> U101^1(isBool(A), A, B)
19.06/7.47	   _OR_(A, B) -> ISBOOL(A)
19.06/7.47	   _XOR_(A, A) -> U111^1(isBool(A))
19.06/7.47	   _XOR_(A, A) -> ISBOOL(A)
19.06/7.47	   _XOR_(false, A) -> U121^1(isBool(A), A)
19.06/7.47	   _XOR_(false, A) -> ISBOOL(A)
19.06/7.47	   IF_THEN_ELSE_FI(B, U, U') -> U131^1(isBool(B), B, U', U)
19.06/7.47	   IF_THEN_ELSE_FI(B, U, U') -> ISBOOL(B)
19.06/7.47	   IF_THEN_ELSE_FI(true, U, U') -> U141^1(isS(U'), U)
19.06/7.47	   ISBOOL(_and_(V1, V2)) -> U151^1(isBool(V1), V2)
19.06/7.47	   ISBOOL(_and_(V1, V2)) -> ISBOOL(V1)
19.06/7.47	   ISBOOL(_implies_(V1, V2)) -> U161^1(isBool(V1), V2)
19.06/7.47	   ISBOOL(_implies_(V1, V2)) -> ISBOOL(V1)
19.06/7.47	   ISBOOL(_isEqualTo_(V1, V2)) -> U171^1(isUniversal(V1), V2)
19.06/7.47	   ISBOOL(_isNotEqualTo_(V1, V2)) -> U181^1(isUniversal(V1), V2)
19.06/7.47	   ISBOOL(_or_(V1, V2)) -> U191^1(isBool(V1), V2)
19.06/7.47	   ISBOOL(_or_(V1, V2)) -> ISBOOL(V1)
19.06/7.47	   ISBOOL(_xor_(V1, V2)) -> U201^1(isBool(V1), V2)
19.06/7.47	   ISBOOL(_xor_(V1, V2)) -> ISBOOL(V1)
19.06/7.47	   ISBOOL(not_(V1)) -> U211^1(isBool(V1))
19.06/7.47	   ISBOOL(not_(V1)) -> ISBOOL(V1)
19.06/7.47	   NOT_(A) -> U221^1(isBool(A), A)
19.06/7.47	   NOT_(A) -> ISBOOL(A)
19.06/7.47	   _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext)
19.06/7.47	   _AND_(_and_(A, A), ext) -> U11^1(isBool(A), A)
19.06/7.47	   _AND_(_and_(A, A), ext) -> ISBOOL(A)
19.06/7.47	   _AND_(_and_(A, _xor_(B, C)), ext) -> _AND_(U21(isBool(A), A, B, C), ext)
19.06/7.47	   _AND_(_and_(A, _xor_(B, C)), ext) -> U21^1(isBool(A), A, B, C)
19.06/7.47	   _AND_(_and_(A, _xor_(B, C)), ext) -> ISBOOL(A)
19.06/7.47	   _AND_(_and_(false, A), ext) -> _AND_(U31(isBool(A)), ext)
19.06/7.47	   _AND_(_and_(false, A), ext) -> U31^1(isBool(A))
19.06/7.47	   _AND_(_and_(false, A), ext) -> ISBOOL(A)
19.06/7.47	   _AND_(_and_(true, A), ext) -> _AND_(U41(isBool(A), A), ext)
19.06/7.47	   _AND_(_and_(true, A), ext) -> U41^1(isBool(A), A)
19.06/7.47	   _AND_(_and_(true, A), ext) -> ISBOOL(A)
19.06/7.47	   _OR_(_or_(A, B), ext) -> _OR_(U101(isBool(A), A, B), ext)
19.06/7.47	   _OR_(_or_(A, B), ext) -> U101^1(isBool(A), A, B)
19.06/7.47	   _OR_(_or_(A, B), ext) -> ISBOOL(A)
19.06/7.47	   _XOR_(_xor_(A, A), ext) -> _XOR_(U111(isBool(A)), ext)
19.06/7.47	   _XOR_(_xor_(A, A), ext) -> U111^1(isBool(A))
19.06/7.47	   _XOR_(_xor_(A, A), ext) -> ISBOOL(A)
19.06/7.47	   _XOR_(_xor_(false, A), ext) -> _XOR_(U121(isBool(A), A), ext)
19.06/7.47	   _XOR_(_xor_(false, A), ext) -> U121^1(isBool(A), A)
19.06/7.47	   _XOR_(_xor_(false, A), ext) -> ISBOOL(A)
19.06/7.47	
19.06/7.47	The TRS R consists of the following rules:
19.06/7.47	
19.06/7.47	   U101(tt, A, B) -> U102(isBool(B), A, B)
19.06/7.47	   U102(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B))
19.06/7.47	   U11(tt, A) -> A
19.06/7.47	   U111(tt) -> false
19.06/7.47	   U121(tt, A) -> A
19.06/7.47	   U131(tt, B, U', U) -> U132(isS(U'), B, U', U)
19.06/7.47	   U132(tt, B, U', U) -> U133(isS(U), B, U')
19.06/7.47	   U133(tt, B, U') -> U134(equal(_isNotEqualTo_(B, true), true), U')
19.06/7.47	   U134(tt, U') -> U'
19.06/7.47	   U141(tt, U) -> U142(isS(U), U)
19.06/7.47	   U142(tt, U) -> U
19.06/7.47	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.47	   U152(tt) -> tt
19.06/7.47	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.47	   U162(tt) -> tt
19.06/7.47	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.47	   U172(tt) -> tt
19.06/7.47	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.47	   U182(tt) -> tt
19.06/7.47	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.47	   U192(tt) -> tt
19.06/7.47	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.47	   U202(tt) -> tt
19.06/7.47	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.47	   U211(tt) -> tt
19.06/7.47	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.47	   U221(tt, A) -> _xor_(A, true)
19.06/7.47	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.47	   U31(tt) -> false
19.06/7.47	   U41(tt, A) -> A
19.06/7.47	   U51(tt, A, B) -> U52(isBool(B), A, B)
19.06/7.47	   U52(tt, A, B) -> not_(_xor_(A, _and_(A, B)))
19.06/7.47	   U61(tt, U', U) -> U62(isS(U), U', U)
19.06/7.47	   U62(tt, U', U) -> U63(equal(_isNotEqualTo_(U, U'), true))
19.06/7.47	   U63(tt) -> false
19.06/7.47	   U71(tt) -> true
19.06/7.47	   U81(tt, U', U) -> U82(isS(U), U', U)
19.06/7.47	   U82(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true)
19.06/7.47	   U91(tt) -> false
19.06/7.47	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.47	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.47	   _and_(false, A) -> U31(isBool(A))
19.06/7.47	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.47	   _implies_(A, B) -> U51(isBool(A), A, B)
19.06/7.47	   _isEqualTo_(U, U') -> U61(isS(U'), U', U)
19.06/7.47	   _isEqualTo_(U, U) -> U71(isS(U))
19.06/7.47	   _isNotEqualTo_(U, U') -> U81(isS(U'), U', U)
19.06/7.47	   _isNotEqualTo_(U, U) -> U91(isS(U))
19.06/7.47	   _or_(A, B) -> U101(isBool(A), A, B)
19.06/7.47	   _xor_(A, A) -> U111(isBool(A))
19.06/7.47	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.47	   equal(X, X) -> tt
19.06/7.47	   if_then_else_fi(B, U, U') -> U131(isBool(B), B, U', U)
19.06/7.47	   if_then_else_fi(true, U, U') -> U141(isS(U'), U)
19.06/7.47	   isBool(false) -> tt
19.06/7.47	   isBool(true) -> tt
19.06/7.47	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.47	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.47	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.47	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.47	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.47	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.47	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.47	   not_(A) -> U221(isBool(A), A)
19.06/7.47	   not_(false) -> true
19.06/7.47	   not_(true) -> false
19.06/7.47	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.47	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.47	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.47	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.47	   _or_(_or_(A, B), ext) -> _or_(U101(isBool(A), A, B), ext)
19.06/7.47	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.47	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.47	
19.06/7.47	The set E consists of the following equations:
19.06/7.47	
19.06/7.47	   _and_(x, y) == _and_(y, x)
19.06/7.47	   _or_(x, y) == _or_(y, x)
19.06/7.47	   _xor_(x, y) == _xor_(y, x)
19.06/7.47	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.47	   _or_(_or_(x, y), z) == _or_(x, _or_(y, z))
19.06/7.47	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.47	
19.06/7.47	The set E# consists of the following equations:
19.06/7.47	
19.06/7.47	   _AND_(x, y) == _AND_(y, x)
19.06/7.47	   _OR_(x, y) == _OR_(y, x)
19.06/7.47	   _XOR_(x, y) == _XOR_(y, x)
19.06/7.47	   _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z))
19.06/7.47	   _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z))
19.06/7.47	   _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z))
19.06/7.47	
19.06/7.47	We have to consider all minimal (P,E#,R,E)-chains
19.06/7.47	
19.06/7.47	----------------------------------------
19.06/7.47	
19.06/7.47	(2)
19.06/7.47	Obligation:
19.06/7.47	The TRS P consists of the following rules:
19.06/7.47	
19.06/7.47	   U101^1(tt, A, B) -> U102^1(isBool(B), A, B)
19.06/7.47	   U101^1(tt, A, B) -> ISBOOL(B)
19.06/7.47	   U102^1(tt, A, B) -> _XOR_(_and_(A, B), _xor_(A, B))
19.06/7.47	   U102^1(tt, A, B) -> _AND_(A, B)
19.06/7.47	   U102^1(tt, A, B) -> _XOR_(A, B)
19.06/7.47	   U131^1(tt, B, U', U) -> U132^1(isS(U'), B, U', U)
19.06/7.47	   U132^1(tt, B, U', U) -> U133^1(isS(U), B, U')
19.06/7.47	   U133^1(tt, B, U') -> U134^1(equal(_isNotEqualTo_(B, true), true), U')
19.06/7.47	   U133^1(tt, B, U') -> EQUAL(_isNotEqualTo_(B, true), true)
19.06/7.47	   U133^1(tt, B, U') -> _ISNOTEQUALTO_(B, true)
19.06/7.47	   U141^1(tt, U) -> U142^1(isS(U), U)
19.06/7.47	   U151^1(tt, V2) -> U152^1(isBool(V2))
19.06/7.47	   U151^1(tt, V2) -> ISBOOL(V2)
19.06/7.47	   U161^1(tt, V2) -> U162^1(isBool(V2))
19.06/7.47	   U161^1(tt, V2) -> ISBOOL(V2)
19.06/7.47	   U171^1(tt, V2) -> U172^1(isUniversal(V2))
19.06/7.47	   U181^1(tt, V2) -> U182^1(isUniversal(V2))
19.06/7.47	   U191^1(tt, V2) -> U192^1(isBool(V2))
19.06/7.47	   U191^1(tt, V2) -> ISBOOL(V2)
19.06/7.47	   U201^1(tt, V2) -> U202^1(isBool(V2))
19.06/7.47	   U201^1(tt, V2) -> ISBOOL(V2)
19.06/7.47	   U21^1(tt, A, B, C) -> U22^1(isBool(B), A, B, C)
19.06/7.47	   U21^1(tt, A, B, C) -> ISBOOL(B)
19.06/7.47	   U22^1(tt, A, B, C) -> U23^1(isBool(C), A, B, C)
19.06/7.47	   U22^1(tt, A, B, C) -> ISBOOL(C)
19.06/7.47	   U221^1(tt, A) -> _XOR_(A, true)
19.06/7.47	   U23^1(tt, A, B, C) -> _XOR_(_and_(A, B), _and_(A, C))
19.06/7.47	   U23^1(tt, A, B, C) -> _AND_(A, B)
19.06/7.47	   U23^1(tt, A, B, C) -> _AND_(A, C)
19.06/7.47	   U51^1(tt, A, B) -> U52^1(isBool(B), A, B)
19.06/7.47	   U51^1(tt, A, B) -> ISBOOL(B)
19.06/7.47	   U52^1(tt, A, B) -> NOT_(_xor_(A, _and_(A, B)))
19.06/7.47	   U52^1(tt, A, B) -> _XOR_(A, _and_(A, B))
19.06/7.47	   U52^1(tt, A, B) -> _AND_(A, B)
19.06/7.47	   U61^1(tt, U', U) -> U62^1(isS(U), U', U)
19.06/7.47	   U62^1(tt, U', U) -> U63^1(equal(_isNotEqualTo_(U, U'), true))
19.06/7.47	   U62^1(tt, U', U) -> EQUAL(_isNotEqualTo_(U, U'), true)
19.06/7.47	   U62^1(tt, U', U) -> _ISNOTEQUALTO_(U, U')
19.06/7.47	   U81^1(tt, U', U) -> U82^1(isS(U), U', U)
19.06/7.48	   U82^1(tt, U', U) -> IF_THEN_ELSE_FI(_isEqualTo_(U, U'), false, true)
19.06/7.48	   U82^1(tt, U', U) -> _ISEQUALTO_(U, U')
19.06/7.48	   _AND_(A, A) -> U11^1(isBool(A), A)
19.06/7.48	   _AND_(A, A) -> ISBOOL(A)
19.06/7.48	   _AND_(A, _xor_(B, C)) -> U21^1(isBool(A), A, B, C)
19.06/7.48	   _AND_(A, _xor_(B, C)) -> ISBOOL(A)
19.06/7.48	   _AND_(false, A) -> U31^1(isBool(A))
19.06/7.48	   _AND_(false, A) -> ISBOOL(A)
19.06/7.48	   _AND_(true, A) -> U41^1(isBool(A), A)
19.06/7.48	   _AND_(true, A) -> ISBOOL(A)
19.06/7.48	   _IMPLIES_(A, B) -> U51^1(isBool(A), A, B)
19.06/7.48	   _IMPLIES_(A, B) -> ISBOOL(A)
19.06/7.48	   _ISEQUALTO_(U, U') -> U61^1(isS(U'), U', U)
19.06/7.48	   _ISEQUALTO_(U, U) -> U71^1(isS(U))
19.06/7.48	   _ISNOTEQUALTO_(U, U') -> U81^1(isS(U'), U', U)
19.06/7.48	   _ISNOTEQUALTO_(U, U) -> U91^1(isS(U))
19.06/7.48	   _OR_(A, B) -> U101^1(isBool(A), A, B)
19.06/7.48	   _OR_(A, B) -> ISBOOL(A)
19.06/7.48	   _XOR_(A, A) -> U111^1(isBool(A))
19.06/7.48	   _XOR_(A, A) -> ISBOOL(A)
19.06/7.48	   _XOR_(false, A) -> U121^1(isBool(A), A)
19.06/7.48	   _XOR_(false, A) -> ISBOOL(A)
19.06/7.48	   IF_THEN_ELSE_FI(B, U, U') -> U131^1(isBool(B), B, U', U)
19.06/7.48	   IF_THEN_ELSE_FI(B, U, U') -> ISBOOL(B)
19.06/7.48	   IF_THEN_ELSE_FI(true, U, U') -> U141^1(isS(U'), U)
19.06/7.48	   ISBOOL(_and_(V1, V2)) -> U151^1(isBool(V1), V2)
19.06/7.48	   ISBOOL(_and_(V1, V2)) -> ISBOOL(V1)
19.06/7.48	   ISBOOL(_implies_(V1, V2)) -> U161^1(isBool(V1), V2)
19.06/7.48	   ISBOOL(_implies_(V1, V2)) -> ISBOOL(V1)
19.06/7.48	   ISBOOL(_isEqualTo_(V1, V2)) -> U171^1(isUniversal(V1), V2)
19.06/7.48	   ISBOOL(_isNotEqualTo_(V1, V2)) -> U181^1(isUniversal(V1), V2)
19.06/7.48	   ISBOOL(_or_(V1, V2)) -> U191^1(isBool(V1), V2)
19.06/7.48	   ISBOOL(_or_(V1, V2)) -> ISBOOL(V1)
19.06/7.48	   ISBOOL(_xor_(V1, V2)) -> U201^1(isBool(V1), V2)
19.06/7.48	   ISBOOL(_xor_(V1, V2)) -> ISBOOL(V1)
19.06/7.48	   ISBOOL(not_(V1)) -> U211^1(isBool(V1))
19.06/7.48	   ISBOOL(not_(V1)) -> ISBOOL(V1)
19.06/7.48	   NOT_(A) -> U221^1(isBool(A), A)
19.06/7.48	   NOT_(A) -> ISBOOL(A)
19.06/7.48	   _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext)
19.06/7.48	   _AND_(_and_(A, A), ext) -> U11^1(isBool(A), A)
19.06/7.48	   _AND_(_and_(A, A), ext) -> ISBOOL(A)
19.06/7.48	   _AND_(_and_(A, _xor_(B, C)), ext) -> _AND_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _AND_(_and_(A, _xor_(B, C)), ext) -> U21^1(isBool(A), A, B, C)
19.06/7.48	   _AND_(_and_(A, _xor_(B, C)), ext) -> ISBOOL(A)
19.06/7.48	   _AND_(_and_(false, A), ext) -> _AND_(U31(isBool(A)), ext)
19.06/7.48	   _AND_(_and_(false, A), ext) -> U31^1(isBool(A))
19.06/7.48	   _AND_(_and_(false, A), ext) -> ISBOOL(A)
19.06/7.48	   _AND_(_and_(true, A), ext) -> _AND_(U41(isBool(A), A), ext)
19.06/7.48	   _AND_(_and_(true, A), ext) -> U41^1(isBool(A), A)
19.06/7.48	   _AND_(_and_(true, A), ext) -> ISBOOL(A)
19.06/7.48	   _OR_(_or_(A, B), ext) -> _OR_(U101(isBool(A), A, B), ext)
19.06/7.48	   _OR_(_or_(A, B), ext) -> U101^1(isBool(A), A, B)
19.06/7.48	   _OR_(_or_(A, B), ext) -> ISBOOL(A)
19.06/7.48	   _XOR_(_xor_(A, A), ext) -> _XOR_(U111(isBool(A)), ext)
19.06/7.48	   _XOR_(_xor_(A, A), ext) -> U111^1(isBool(A))
19.06/7.48	   _XOR_(_xor_(A, A), ext) -> ISBOOL(A)
19.06/7.48	   _XOR_(_xor_(false, A), ext) -> _XOR_(U121(isBool(A), A), ext)
19.06/7.48	   _XOR_(_xor_(false, A), ext) -> U121^1(isBool(A), A)
19.06/7.48	   _XOR_(_xor_(false, A), ext) -> ISBOOL(A)
19.06/7.48	
19.06/7.48	The TRS R consists of the following rules:
19.06/7.48	
19.06/7.48	   U101(tt, A, B) -> U102(isBool(B), A, B)
19.06/7.48	   U102(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B))
19.06/7.48	   U11(tt, A) -> A
19.06/7.48	   U111(tt) -> false
19.06/7.48	   U121(tt, A) -> A
19.06/7.48	   U131(tt, B, U', U) -> U132(isS(U'), B, U', U)
19.06/7.48	   U132(tt, B, U', U) -> U133(isS(U), B, U')
19.06/7.48	   U133(tt, B, U') -> U134(equal(_isNotEqualTo_(B, true), true), U')
19.06/7.48	   U134(tt, U') -> U'
19.06/7.48	   U141(tt, U) -> U142(isS(U), U)
19.06/7.48	   U142(tt, U) -> U
19.06/7.48	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.48	   U152(tt) -> tt
19.06/7.48	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.48	   U162(tt) -> tt
19.06/7.48	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.48	   U172(tt) -> tt
19.06/7.48	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.48	   U182(tt) -> tt
19.06/7.48	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.48	   U192(tt) -> tt
19.06/7.48	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.48	   U202(tt) -> tt
19.06/7.48	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.48	   U211(tt) -> tt
19.06/7.48	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.48	   U221(tt, A) -> _xor_(A, true)
19.06/7.48	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.48	   U31(tt) -> false
19.06/7.48	   U41(tt, A) -> A
19.06/7.48	   U51(tt, A, B) -> U52(isBool(B), A, B)
19.06/7.48	   U52(tt, A, B) -> not_(_xor_(A, _and_(A, B)))
19.06/7.48	   U61(tt, U', U) -> U62(isS(U), U', U)
19.06/7.48	   U62(tt, U', U) -> U63(equal(_isNotEqualTo_(U, U'), true))
19.06/7.48	   U63(tt) -> false
19.06/7.48	   U71(tt) -> true
19.06/7.48	   U81(tt, U', U) -> U82(isS(U), U', U)
19.06/7.48	   U82(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true)
19.06/7.48	   U91(tt) -> false
19.06/7.48	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.48	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.48	   _and_(false, A) -> U31(isBool(A))
19.06/7.48	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.48	   _implies_(A, B) -> U51(isBool(A), A, B)
19.06/7.48	   _isEqualTo_(U, U') -> U61(isS(U'), U', U)
19.06/7.48	   _isEqualTo_(U, U) -> U71(isS(U))
19.06/7.48	   _isNotEqualTo_(U, U') -> U81(isS(U'), U', U)
19.06/7.48	   _isNotEqualTo_(U, U) -> U91(isS(U))
19.06/7.48	   _or_(A, B) -> U101(isBool(A), A, B)
19.06/7.48	   _xor_(A, A) -> U111(isBool(A))
19.06/7.48	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.48	   equal(X, X) -> tt
19.06/7.48	   if_then_else_fi(B, U, U') -> U131(isBool(B), B, U', U)
19.06/7.48	   if_then_else_fi(true, U, U') -> U141(isS(U'), U)
19.06/7.48	   isBool(false) -> tt
19.06/7.48	   isBool(true) -> tt
19.06/7.48	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.48	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.48	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.48	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.48	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.48	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.48	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.48	   not_(A) -> U221(isBool(A), A)
19.06/7.48	   not_(false) -> true
19.06/7.48	   not_(true) -> false
19.06/7.48	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.48	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.48	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.48	   _or_(_or_(A, B), ext) -> _or_(U101(isBool(A), A, B), ext)
19.06/7.48	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.48	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.48	
19.06/7.48	The set E consists of the following equations:
19.06/7.48	
19.06/7.48	   _and_(x, y) == _and_(y, x)
19.06/7.48	   _or_(x, y) == _or_(y, x)
19.06/7.48	   _xor_(x, y) == _xor_(y, x)
19.06/7.48	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.48	   _or_(_or_(x, y), z) == _or_(x, _or_(y, z))
19.06/7.48	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.48	
19.06/7.48	The set E# consists of the following equations:
19.06/7.48	
19.06/7.48	   _AND_(x, y) == _AND_(y, x)
19.06/7.48	   _OR_(x, y) == _OR_(y, x)
19.06/7.48	   _XOR_(x, y) == _XOR_(y, x)
19.06/7.48	   _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z))
19.06/7.48	   _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z))
19.06/7.48	   _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z))
19.06/7.48	
19.06/7.48	We have to consider all minimal (P,E#,R,E)-chains
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(3) EDependencyGraphProof (EQUIVALENT)
19.06/7.48	The approximation of the Equational Dependency Graph [DA_STEIN] contains 4 SCCs with 73 less nodes.
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(4)
19.06/7.48	Complex Obligation (AND)
19.06/7.48	
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(5)
19.06/7.48	Obligation:
19.06/7.48	The TRS P consists of the following rules:
19.06/7.48	
19.06/7.48	   U161^1(tt, V2) -> ISBOOL(V2)
19.06/7.48	   ISBOOL(_and_(V1, V2)) -> ISBOOL(V1)
19.06/7.48	   ISBOOL(_implies_(V1, V2)) -> U161^1(isBool(V1), V2)
19.06/7.48	   ISBOOL(_xor_(V1, V2)) -> U201^1(isBool(V1), V2)
19.06/7.48	   U151^1(tt, V2) -> ISBOOL(V2)
19.06/7.48	   ISBOOL(not_(V1)) -> ISBOOL(V1)
19.06/7.48	   ISBOOL(_or_(V1, V2)) -> ISBOOL(V1)
19.06/7.48	   ISBOOL(_implies_(V1, V2)) -> ISBOOL(V1)
19.06/7.48	   U201^1(tt, V2) -> ISBOOL(V2)
19.06/7.48	   ISBOOL(_or_(V1, V2)) -> U191^1(isBool(V1), V2)
19.06/7.48	   ISBOOL(_and_(V1, V2)) -> U151^1(isBool(V1), V2)
19.06/7.48	   U191^1(tt, V2) -> ISBOOL(V2)
19.06/7.48	   ISBOOL(_xor_(V1, V2)) -> ISBOOL(V1)
19.06/7.48	
19.06/7.48	The TRS R consists of the following rules:
19.06/7.48	
19.06/7.48	   U101(tt, A, B) -> U102(isBool(B), A, B)
19.06/7.48	   U102(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B))
19.06/7.48	   U11(tt, A) -> A
19.06/7.48	   U111(tt) -> false
19.06/7.48	   U121(tt, A) -> A
19.06/7.48	   U131(tt, B, U', U) -> U132(isS(U'), B, U', U)
19.06/7.48	   U132(tt, B, U', U) -> U133(isS(U), B, U')
19.06/7.48	   U133(tt, B, U') -> U134(equal(_isNotEqualTo_(B, true), true), U')
19.06/7.48	   U134(tt, U') -> U'
19.06/7.48	   U141(tt, U) -> U142(isS(U), U)
19.06/7.48	   U142(tt, U) -> U
19.06/7.48	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.48	   U152(tt) -> tt
19.06/7.48	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.48	   U162(tt) -> tt
19.06/7.48	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.48	   U172(tt) -> tt
19.06/7.48	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.48	   U182(tt) -> tt
19.06/7.48	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.48	   U192(tt) -> tt
19.06/7.48	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.48	   U202(tt) -> tt
19.06/7.48	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.48	   U211(tt) -> tt
19.06/7.48	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.48	   U221(tt, A) -> _xor_(A, true)
19.06/7.48	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.48	   U31(tt) -> false
19.06/7.48	   U41(tt, A) -> A
19.06/7.48	   U51(tt, A, B) -> U52(isBool(B), A, B)
19.06/7.48	   U52(tt, A, B) -> not_(_xor_(A, _and_(A, B)))
19.06/7.48	   U61(tt, U', U) -> U62(isS(U), U', U)
19.06/7.48	   U62(tt, U', U) -> U63(equal(_isNotEqualTo_(U, U'), true))
19.06/7.48	   U63(tt) -> false
19.06/7.48	   U71(tt) -> true
19.06/7.48	   U81(tt, U', U) -> U82(isS(U), U', U)
19.06/7.48	   U82(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true)
19.06/7.48	   U91(tt) -> false
19.06/7.48	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.48	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.48	   _and_(false, A) -> U31(isBool(A))
19.06/7.48	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.48	   _implies_(A, B) -> U51(isBool(A), A, B)
19.06/7.48	   _isEqualTo_(U, U') -> U61(isS(U'), U', U)
19.06/7.48	   _isEqualTo_(U, U) -> U71(isS(U))
19.06/7.48	   _isNotEqualTo_(U, U') -> U81(isS(U'), U', U)
19.06/7.48	   _isNotEqualTo_(U, U) -> U91(isS(U))
19.06/7.48	   _or_(A, B) -> U101(isBool(A), A, B)
19.06/7.48	   _xor_(A, A) -> U111(isBool(A))
19.06/7.48	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.48	   equal(X, X) -> tt
19.06/7.48	   if_then_else_fi(B, U, U') -> U131(isBool(B), B, U', U)
19.06/7.48	   if_then_else_fi(true, U, U') -> U141(isS(U'), U)
19.06/7.48	   isBool(false) -> tt
19.06/7.48	   isBool(true) -> tt
19.06/7.48	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.48	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.48	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.48	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.48	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.48	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.48	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.48	   not_(A) -> U221(isBool(A), A)
19.06/7.48	   not_(false) -> true
19.06/7.48	   not_(true) -> false
19.06/7.48	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.48	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.48	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.48	   _or_(_or_(A, B), ext) -> _or_(U101(isBool(A), A, B), ext)
19.06/7.48	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.48	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.48	
19.06/7.48	The set E consists of the following equations:
19.06/7.48	
19.06/7.48	   _and_(x, y) == _and_(y, x)
19.06/7.48	   _or_(x, y) == _or_(y, x)
19.06/7.48	   _xor_(x, y) == _xor_(y, x)
19.06/7.48	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.48	   _or_(_or_(x, y), z) == _or_(x, _or_(y, z))
19.06/7.48	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.48	
19.06/7.48	The set E# consists of the following equations:
19.06/7.48	
19.06/7.48	   _AND_(x, y) == _AND_(y, x)
19.06/7.48	   _OR_(x, y) == _OR_(y, x)
19.06/7.48	   _XOR_(x, y) == _XOR_(y, x)
19.06/7.48	   _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z))
19.06/7.48	   _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z))
19.06/7.48	   _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z))
19.06/7.48	
19.06/7.48	We have to consider all minimal (P,E#,R,E)-chains
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(6) ESharpUsableEquationsProof (EQUIVALENT)
19.06/7.48	We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
19.06/7.48	   _AND_(x, y) == _AND_(y, x)
19.06/7.48	   _OR_(x, y) == _OR_(y, x)
19.06/7.48	   _XOR_(x, y) == _XOR_(y, x)
19.06/7.48	   _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z))
19.06/7.48	   _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z))
19.06/7.48	   _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z))
19.06/7.48	
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(7)
19.06/7.48	Obligation:
19.06/7.48	The TRS P consists of the following rules:
19.06/7.48	
19.06/7.48	   U161^1(tt, V2) -> ISBOOL(V2)
19.06/7.48	   ISBOOL(_and_(V1, V2)) -> ISBOOL(V1)
19.06/7.48	   ISBOOL(_implies_(V1, V2)) -> U161^1(isBool(V1), V2)
19.06/7.48	   ISBOOL(_xor_(V1, V2)) -> U201^1(isBool(V1), V2)
19.06/7.48	   U151^1(tt, V2) -> ISBOOL(V2)
19.06/7.48	   ISBOOL(not_(V1)) -> ISBOOL(V1)
19.06/7.48	   ISBOOL(_or_(V1, V2)) -> ISBOOL(V1)
19.06/7.48	   ISBOOL(_implies_(V1, V2)) -> ISBOOL(V1)
19.06/7.48	   U201^1(tt, V2) -> ISBOOL(V2)
19.06/7.48	   ISBOOL(_or_(V1, V2)) -> U191^1(isBool(V1), V2)
19.06/7.48	   ISBOOL(_and_(V1, V2)) -> U151^1(isBool(V1), V2)
19.06/7.48	   U191^1(tt, V2) -> ISBOOL(V2)
19.06/7.48	   ISBOOL(_xor_(V1, V2)) -> ISBOOL(V1)
19.06/7.48	
19.06/7.48	The TRS R consists of the following rules:
19.06/7.48	
19.06/7.48	   U101(tt, A, B) -> U102(isBool(B), A, B)
19.06/7.48	   U102(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B))
19.06/7.48	   U11(tt, A) -> A
19.06/7.48	   U111(tt) -> false
19.06/7.48	   U121(tt, A) -> A
19.06/7.48	   U131(tt, B, U', U) -> U132(isS(U'), B, U', U)
19.06/7.48	   U132(tt, B, U', U) -> U133(isS(U), B, U')
19.06/7.48	   U133(tt, B, U') -> U134(equal(_isNotEqualTo_(B, true), true), U')
19.06/7.48	   U134(tt, U') -> U'
19.06/7.48	   U141(tt, U) -> U142(isS(U), U)
19.06/7.48	   U142(tt, U) -> U
19.06/7.48	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.48	   U152(tt) -> tt
19.06/7.48	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.48	   U162(tt) -> tt
19.06/7.48	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.48	   U172(tt) -> tt
19.06/7.48	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.48	   U182(tt) -> tt
19.06/7.48	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.48	   U192(tt) -> tt
19.06/7.48	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.48	   U202(tt) -> tt
19.06/7.48	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.48	   U211(tt) -> tt
19.06/7.48	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.48	   U221(tt, A) -> _xor_(A, true)
19.06/7.48	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.48	   U31(tt) -> false
19.06/7.48	   U41(tt, A) -> A
19.06/7.48	   U51(tt, A, B) -> U52(isBool(B), A, B)
19.06/7.48	   U52(tt, A, B) -> not_(_xor_(A, _and_(A, B)))
19.06/7.48	   U61(tt, U', U) -> U62(isS(U), U', U)
19.06/7.48	   U62(tt, U', U) -> U63(equal(_isNotEqualTo_(U, U'), true))
19.06/7.48	   U63(tt) -> false
19.06/7.48	   U71(tt) -> true
19.06/7.48	   U81(tt, U', U) -> U82(isS(U), U', U)
19.06/7.48	   U82(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true)
19.06/7.48	   U91(tt) -> false
19.06/7.48	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.48	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.48	   _and_(false, A) -> U31(isBool(A))
19.06/7.48	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.48	   _implies_(A, B) -> U51(isBool(A), A, B)
19.06/7.48	   _isEqualTo_(U, U') -> U61(isS(U'), U', U)
19.06/7.48	   _isEqualTo_(U, U) -> U71(isS(U))
19.06/7.48	   _isNotEqualTo_(U, U') -> U81(isS(U'), U', U)
19.06/7.48	   _isNotEqualTo_(U, U) -> U91(isS(U))
19.06/7.48	   _or_(A, B) -> U101(isBool(A), A, B)
19.06/7.48	   _xor_(A, A) -> U111(isBool(A))
19.06/7.48	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.48	   equal(X, X) -> tt
19.06/7.48	   if_then_else_fi(B, U, U') -> U131(isBool(B), B, U', U)
19.06/7.48	   if_then_else_fi(true, U, U') -> U141(isS(U'), U)
19.06/7.48	   isBool(false) -> tt
19.06/7.48	   isBool(true) -> tt
19.06/7.48	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.48	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.48	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.48	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.48	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.48	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.48	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.48	   not_(A) -> U221(isBool(A), A)
19.06/7.48	   not_(false) -> true
19.06/7.48	   not_(true) -> false
19.06/7.48	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.48	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.48	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.48	   _or_(_or_(A, B), ext) -> _or_(U101(isBool(A), A, B), ext)
19.06/7.48	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.48	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.48	
19.06/7.48	The set E consists of the following equations:
19.06/7.48	
19.06/7.48	   _and_(x, y) == _and_(y, x)
19.06/7.48	   _or_(x, y) == _or_(y, x)
19.06/7.48	   _xor_(x, y) == _xor_(y, x)
19.06/7.48	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.48	   _or_(_or_(x, y), z) == _or_(x, _or_(y, z))
19.06/7.48	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.48	
19.06/7.48	E# is empty.
19.06/7.48	We have to consider all minimal (P,E#,R,E)-chains
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(8) EUsableRulesReductionPairsProof (EQUIVALENT)
19.06/7.48	By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the  usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.
19.06/7.48	
19.06/7.48	The following dependency pairs can be deleted:
19.06/7.48	
19.06/7.48	   ISBOOL(_and_(V1, V2)) -> ISBOOL(V1)
19.06/7.48	   ISBOOL(_implies_(V1, V2)) -> U161^1(isBool(V1), V2)
19.06/7.48	   ISBOOL(_xor_(V1, V2)) -> U201^1(isBool(V1), V2)
19.06/7.48	   ISBOOL(not_(V1)) -> ISBOOL(V1)
19.06/7.48	   ISBOOL(_or_(V1, V2)) -> ISBOOL(V1)
19.06/7.48	   ISBOOL(_implies_(V1, V2)) -> ISBOOL(V1)
19.06/7.48	   ISBOOL(_or_(V1, V2)) -> U191^1(isBool(V1), V2)
19.06/7.48	   ISBOOL(_and_(V1, V2)) -> U151^1(isBool(V1), V2)
19.06/7.48	   ISBOOL(_xor_(V1, V2)) -> ISBOOL(V1)
19.06/7.48	The following rules are removed from R:
19.06/7.48	
19.06/7.48	   U101(tt, A, B) -> U102(isBool(B), A, B)
19.06/7.48	   U102(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B))
19.06/7.48	   U11(tt, A) -> A
19.06/7.48	   U111(tt) -> false
19.06/7.48	   U121(tt, A) -> A
19.06/7.48	   U131(tt, B, U', U) -> U132(isS(U'), B, U', U)
19.06/7.48	   U132(tt, B, U', U) -> U133(isS(U), B, U')
19.06/7.48	   U133(tt, B, U') -> U134(equal(_isNotEqualTo_(B, true), true), U')
19.06/7.48	   U134(tt, U') -> U'
19.06/7.48	   U141(tt, U) -> U142(isS(U), U)
19.06/7.48	   U142(tt, U) -> U
19.06/7.48	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.48	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.48	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.48	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.48	   U221(tt, A) -> _xor_(A, true)
19.06/7.48	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.48	   U31(tt) -> false
19.06/7.48	   U41(tt, A) -> A
19.06/7.48	   U51(tt, A, B) -> U52(isBool(B), A, B)
19.06/7.48	   U52(tt, A, B) -> not_(_xor_(A, _and_(A, B)))
19.06/7.48	   U61(tt, U', U) -> U62(isS(U), U', U)
19.06/7.48	   U62(tt, U', U) -> U63(equal(_isNotEqualTo_(U, U'), true))
19.06/7.48	   U63(tt) -> false
19.06/7.48	   U71(tt) -> true
19.06/7.48	   U81(tt, U', U) -> U82(isS(U), U', U)
19.06/7.48	   U82(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true)
19.06/7.48	   U91(tt) -> false
19.06/7.48	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.48	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.48	   _and_(false, A) -> U31(isBool(A))
19.06/7.48	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.48	   _implies_(A, B) -> U51(isBool(A), A, B)
19.06/7.48	   _isEqualTo_(U, U') -> U61(isS(U'), U', U)
19.06/7.48	   _isEqualTo_(U, U) -> U71(isS(U))
19.06/7.48	   _isNotEqualTo_(U, U') -> U81(isS(U'), U', U)
19.06/7.48	   _isNotEqualTo_(U, U) -> U91(isS(U))
19.06/7.48	   _or_(A, B) -> U101(isBool(A), A, B)
19.06/7.48	   _xor_(A, A) -> U111(isBool(A))
19.06/7.48	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.48	   equal(X, X) -> tt
19.06/7.48	   if_then_else_fi(B, U, U') -> U131(isBool(B), B, U', U)
19.06/7.48	   if_then_else_fi(true, U, U') -> U141(isS(U'), U)
19.06/7.48	   isBool(false) -> tt
19.06/7.48	   isBool(true) -> tt
19.06/7.48	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.48	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.48	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.48	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.48	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.48	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.48	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.48	   not_(A) -> U221(isBool(A), A)
19.06/7.48	   not_(false) -> true
19.06/7.48	   not_(true) -> false
19.06/7.48	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.48	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.48	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.48	   _or_(_or_(A, B), ext) -> _or_(U101(isBool(A), A, B), ext)
19.06/7.48	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.48	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.48	The following equations are removed from E:
19.06/7.48	
19.06/7.48	   _and_(x, y) == _and_(y, x)
19.06/7.48	   _or_(x, y) == _or_(y, x)
19.06/7.48	   _xor_(x, y) == _xor_(y, x)
19.06/7.48	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.48	   _or_(_or_(x, y), z) == _or_(x, _or_(y, z))
19.06/7.48	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.48	Used ordering: POLO with Polynomial interpretation [POLO]:
19.06/7.48	
19.06/7.48	   POL(ISBOOL(x_1)) = 2*x_1
19.06/7.48	   POL(U151(x_1, x_2)) = 2*x_1 + 3*x_2
19.06/7.48	   POL(U151^1(x_1, x_2)) = 2*x_1 + 3*x_2
19.06/7.48	   POL(U152(x_1)) = x_1
19.06/7.48	   POL(U161(x_1, x_2)) = 2*x_1 + 3*x_2
19.06/7.48	   POL(U161^1(x_1, x_2)) = 2*x_1 + 3*x_2
19.06/7.48	   POL(U162(x_1)) = x_1
19.06/7.48	   POL(U171(x_1, x_2)) = 2 + 2*x_1 + 3*x_2
19.06/7.48	   POL(U172(x_1)) = x_1
19.06/7.48	   POL(U181(x_1, x_2)) = 2*x_1 + 3*x_2
19.06/7.48	   POL(U182(x_1)) = x_1
19.06/7.48	   POL(U191(x_1, x_2)) = 2*x_1 + 3*x_2
19.06/7.48	   POL(U191^1(x_1, x_2)) = 2*x_1 + 3*x_2
19.06/7.48	   POL(U192(x_1)) = x_1
19.06/7.48	   POL(U201(x_1, x_2)) = 1 + 2*x_1 + 3*x_2
19.06/7.48	   POL(U201^1(x_1, x_2)) = 2*x_1 + 3*x_2
19.06/7.48	   POL(U202(x_1)) = x_1
19.06/7.48	   POL(U211(x_1)) = 2*x_1
19.06/7.48	   POL(_and_(x_1, x_2)) = 2 + 3*x_1 + 3*x_2
19.06/7.48	   POL(_implies_(x_1, x_2)) = 3 + 3*x_1 + 3*x_2
19.06/7.48	   POL(_isEqualTo_(x_1, x_2)) = 2 + 3*x_1 + 3*x_2
19.06/7.48	   POL(_isNotEqualTo_(x_1, x_2)) = 1 + 3*x_1 + 3*x_2
19.06/7.48	   POL(_or_(x_1, x_2)) = 3*x_1 + 3*x_2
19.06/7.48	   POL(_xor_(x_1, x_2)) = 1 + 3*x_1 + 3*x_2
19.06/7.48	   POL(false) = 0
19.06/7.48	   POL(isBool(x_1)) = 2*x_1
19.06/7.48	   POL(isUniversal(x_1)) = 2*x_1
19.06/7.48	   POL(not_(x_1)) = 3 + 3*x_1
19.06/7.48	   POL(true) = 0
19.06/7.48	   POL(tt) = 0
19.06/7.48	
19.06/7.48	
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(9)
19.06/7.48	Obligation:
19.06/7.48	The TRS P consists of the following rules:
19.06/7.48	
19.06/7.48	   U161^1(tt, V2) -> ISBOOL(V2)
19.06/7.48	   U151^1(tt, V2) -> ISBOOL(V2)
19.06/7.48	   U201^1(tt, V2) -> ISBOOL(V2)
19.06/7.48	   U191^1(tt, V2) -> ISBOOL(V2)
19.06/7.48	
19.06/7.48	The TRS R consists of the following rules:
19.06/7.48	
19.06/7.48	   U162(tt) -> tt
19.06/7.48	   U202(tt) -> tt
19.06/7.48	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.48	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.48	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.48	   U152(tt) -> tt
19.06/7.48	   U172(tt) -> tt
19.06/7.48	   U192(tt) -> tt
19.06/7.48	   U182(tt) -> tt
19.06/7.48	   U211(tt) -> tt
19.06/7.48	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.48	
19.06/7.48	E is empty.
19.06/7.48	E# is empty.
19.06/7.48	We have to consider all minimal (P,E#,R,E)-chains
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(10) EDependencyGraphProof (EQUIVALENT)
19.06/7.48	The approximation of the Equational Dependency Graph [DA_STEIN] contains 0 SCCs with 4 less nodes.
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(11)
19.06/7.48	TRUE
19.06/7.48	
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(12)
19.06/7.48	Obligation:
19.06/7.48	The TRS P consists of the following rules:
19.06/7.48	
19.06/7.48	   _XOR_(_xor_(A, A), ext) -> _XOR_(U111(isBool(A)), ext)
19.06/7.48	   _XOR_(_xor_(false, A), ext) -> _XOR_(U121(isBool(A), A), ext)
19.06/7.48	
19.06/7.48	The TRS R consists of the following rules:
19.06/7.48	
19.06/7.48	   U101(tt, A, B) -> U102(isBool(B), A, B)
19.06/7.48	   U102(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B))
19.06/7.48	   U11(tt, A) -> A
19.06/7.48	   U111(tt) -> false
19.06/7.48	   U121(tt, A) -> A
19.06/7.48	   U131(tt, B, U', U) -> U132(isS(U'), B, U', U)
19.06/7.48	   U132(tt, B, U', U) -> U133(isS(U), B, U')
19.06/7.48	   U133(tt, B, U') -> U134(equal(_isNotEqualTo_(B, true), true), U')
19.06/7.48	   U134(tt, U') -> U'
19.06/7.48	   U141(tt, U) -> U142(isS(U), U)
19.06/7.48	   U142(tt, U) -> U
19.06/7.48	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.48	   U152(tt) -> tt
19.06/7.48	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.48	   U162(tt) -> tt
19.06/7.48	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.48	   U172(tt) -> tt
19.06/7.48	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.48	   U182(tt) -> tt
19.06/7.48	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.48	   U192(tt) -> tt
19.06/7.48	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.48	   U202(tt) -> tt
19.06/7.48	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.48	   U211(tt) -> tt
19.06/7.48	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.48	   U221(tt, A) -> _xor_(A, true)
19.06/7.48	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.48	   U31(tt) -> false
19.06/7.48	   U41(tt, A) -> A
19.06/7.48	   U51(tt, A, B) -> U52(isBool(B), A, B)
19.06/7.48	   U52(tt, A, B) -> not_(_xor_(A, _and_(A, B)))
19.06/7.48	   U61(tt, U', U) -> U62(isS(U), U', U)
19.06/7.48	   U62(tt, U', U) -> U63(equal(_isNotEqualTo_(U, U'), true))
19.06/7.48	   U63(tt) -> false
19.06/7.48	   U71(tt) -> true
19.06/7.48	   U81(tt, U', U) -> U82(isS(U), U', U)
19.06/7.48	   U82(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true)
19.06/7.48	   U91(tt) -> false
19.06/7.48	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.48	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.48	   _and_(false, A) -> U31(isBool(A))
19.06/7.48	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.48	   _implies_(A, B) -> U51(isBool(A), A, B)
19.06/7.48	   _isEqualTo_(U, U') -> U61(isS(U'), U', U)
19.06/7.48	   _isEqualTo_(U, U) -> U71(isS(U))
19.06/7.48	   _isNotEqualTo_(U, U') -> U81(isS(U'), U', U)
19.06/7.48	   _isNotEqualTo_(U, U) -> U91(isS(U))
19.06/7.48	   _or_(A, B) -> U101(isBool(A), A, B)
19.06/7.48	   _xor_(A, A) -> U111(isBool(A))
19.06/7.48	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.48	   equal(X, X) -> tt
19.06/7.48	   if_then_else_fi(B, U, U') -> U131(isBool(B), B, U', U)
19.06/7.48	   if_then_else_fi(true, U, U') -> U141(isS(U'), U)
19.06/7.48	   isBool(false) -> tt
19.06/7.48	   isBool(true) -> tt
19.06/7.48	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.48	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.48	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.48	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.48	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.48	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.48	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.48	   not_(A) -> U221(isBool(A), A)
19.06/7.48	   not_(false) -> true
19.06/7.48	   not_(true) -> false
19.06/7.48	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.48	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.48	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.48	   _or_(_or_(A, B), ext) -> _or_(U101(isBool(A), A, B), ext)
19.06/7.48	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.48	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.48	
19.06/7.48	The set E consists of the following equations:
19.06/7.48	
19.06/7.48	   _and_(x, y) == _and_(y, x)
19.06/7.48	   _or_(x, y) == _or_(y, x)
19.06/7.48	   _xor_(x, y) == _xor_(y, x)
19.06/7.48	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.48	   _or_(_or_(x, y), z) == _or_(x, _or_(y, z))
19.06/7.48	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.48	
19.06/7.48	The set E# consists of the following equations:
19.06/7.48	
19.06/7.48	   _AND_(x, y) == _AND_(y, x)
19.06/7.48	   _OR_(x, y) == _OR_(y, x)
19.06/7.48	   _XOR_(x, y) == _XOR_(y, x)
19.06/7.48	   _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z))
19.06/7.48	   _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z))
19.06/7.48	   _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z))
19.06/7.48	
19.06/7.48	We have to consider all minimal (P,E#,R,E)-chains
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(13) ESharpUsableEquationsProof (EQUIVALENT)
19.06/7.48	We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
19.06/7.48	   _AND_(x, y) == _AND_(y, x)
19.06/7.48	   _OR_(x, y) == _OR_(y, x)
19.06/7.48	   _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z))
19.06/7.48	   _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z))
19.06/7.48	
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(14)
19.06/7.48	Obligation:
19.06/7.48	The TRS P consists of the following rules:
19.06/7.48	
19.06/7.48	   _XOR_(_xor_(A, A), ext) -> _XOR_(U111(isBool(A)), ext)
19.06/7.48	   _XOR_(_xor_(false, A), ext) -> _XOR_(U121(isBool(A), A), ext)
19.06/7.48	
19.06/7.48	The TRS R consists of the following rules:
19.06/7.48	
19.06/7.48	   U101(tt, A, B) -> U102(isBool(B), A, B)
19.06/7.48	   U102(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B))
19.06/7.48	   U11(tt, A) -> A
19.06/7.48	   U111(tt) -> false
19.06/7.48	   U121(tt, A) -> A
19.06/7.48	   U131(tt, B, U', U) -> U132(isS(U'), B, U', U)
19.06/7.48	   U132(tt, B, U', U) -> U133(isS(U), B, U')
19.06/7.48	   U133(tt, B, U') -> U134(equal(_isNotEqualTo_(B, true), true), U')
19.06/7.48	   U134(tt, U') -> U'
19.06/7.48	   U141(tt, U) -> U142(isS(U), U)
19.06/7.48	   U142(tt, U) -> U
19.06/7.48	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.48	   U152(tt) -> tt
19.06/7.48	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.48	   U162(tt) -> tt
19.06/7.48	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.48	   U172(tt) -> tt
19.06/7.48	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.48	   U182(tt) -> tt
19.06/7.48	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.48	   U192(tt) -> tt
19.06/7.48	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.48	   U202(tt) -> tt
19.06/7.48	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.48	   U211(tt) -> tt
19.06/7.48	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.48	   U221(tt, A) -> _xor_(A, true)
19.06/7.48	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.48	   U31(tt) -> false
19.06/7.48	   U41(tt, A) -> A
19.06/7.48	   U51(tt, A, B) -> U52(isBool(B), A, B)
19.06/7.48	   U52(tt, A, B) -> not_(_xor_(A, _and_(A, B)))
19.06/7.48	   U61(tt, U', U) -> U62(isS(U), U', U)
19.06/7.48	   U62(tt, U', U) -> U63(equal(_isNotEqualTo_(U, U'), true))
19.06/7.48	   U63(tt) -> false
19.06/7.48	   U71(tt) -> true
19.06/7.48	   U81(tt, U', U) -> U82(isS(U), U', U)
19.06/7.48	   U82(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true)
19.06/7.48	   U91(tt) -> false
19.06/7.48	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.48	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.48	   _and_(false, A) -> U31(isBool(A))
19.06/7.48	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.48	   _implies_(A, B) -> U51(isBool(A), A, B)
19.06/7.48	   _isEqualTo_(U, U') -> U61(isS(U'), U', U)
19.06/7.48	   _isEqualTo_(U, U) -> U71(isS(U))
19.06/7.48	   _isNotEqualTo_(U, U') -> U81(isS(U'), U', U)
19.06/7.48	   _isNotEqualTo_(U, U) -> U91(isS(U))
19.06/7.48	   _or_(A, B) -> U101(isBool(A), A, B)
19.06/7.48	   _xor_(A, A) -> U111(isBool(A))
19.06/7.48	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.48	   equal(X, X) -> tt
19.06/7.48	   if_then_else_fi(B, U, U') -> U131(isBool(B), B, U', U)
19.06/7.48	   if_then_else_fi(true, U, U') -> U141(isS(U'), U)
19.06/7.48	   isBool(false) -> tt
19.06/7.48	   isBool(true) -> tt
19.06/7.48	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.48	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.48	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.48	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.48	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.48	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.48	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.48	   not_(A) -> U221(isBool(A), A)
19.06/7.48	   not_(false) -> true
19.06/7.48	   not_(true) -> false
19.06/7.48	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.48	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.48	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.48	   _or_(_or_(A, B), ext) -> _or_(U101(isBool(A), A, B), ext)
19.06/7.48	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.48	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.48	
19.06/7.48	The set E consists of the following equations:
19.06/7.48	
19.06/7.48	   _and_(x, y) == _and_(y, x)
19.06/7.48	   _or_(x, y) == _or_(y, x)
19.06/7.48	   _xor_(x, y) == _xor_(y, x)
19.06/7.48	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.48	   _or_(_or_(x, y), z) == _or_(x, _or_(y, z))
19.06/7.48	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.48	
19.06/7.48	The set E# consists of the following equations:
19.06/7.48	
19.06/7.48	   _XOR_(x, y) == _XOR_(y, x)
19.06/7.48	   _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z))
19.06/7.48	
19.06/7.48	We have to consider all minimal (P,E#,R,E)-chains
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(15) EDPPoloProof (EQUIVALENT)
19.06/7.48	We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented.
19.06/7.48	
19.06/7.48	
19.06/7.48	   _XOR_(_xor_(A, A), ext) -> _XOR_(U111(isBool(A)), ext)
19.06/7.48	   _XOR_(_xor_(false, A), ext) -> _XOR_(U121(isBool(A), A), ext)
19.06/7.48	With the implicit AFS we had to orient the following set of usable rules of R non-strictly.
19.06/7.48	
19.06/7.48	
19.06/7.48	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.48	   _xor_(A, A) -> U111(isBool(A))
19.06/7.48	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.48	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.48	   U111(tt) -> false
19.06/7.48	   U121(tt, A) -> A
19.06/7.48	We had to orient the following equations of E# equivalently.
19.06/7.48	
19.06/7.48	
19.06/7.48	   _XOR_(x, y) == _XOR_(y, x)
19.06/7.48	   _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z))
19.06/7.48	With the implicit AFS we had to orient the following usable equations of E equivalently.
19.06/7.48	
19.06/7.48	
19.06/7.48	   _xor_(x, y) == _xor_(y, x)
19.06/7.48	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.48	Used ordering: POLO with Polynomial interpretation [POLO]:
19.06/7.48	
19.06/7.48	   POL(U111(x_1)) = 1
19.06/7.48	   POL(U121(x_1, x_2)) = x_2
19.06/7.48	   POL(U151(x_1, x_2)) = 3 + 3*x_2
19.06/7.48	   POL(U152(x_1)) = 3
19.06/7.48	   POL(U161(x_1, x_2)) = 3 + 3*x_2
19.06/7.48	   POL(U162(x_1)) = 3
19.06/7.48	   POL(U171(x_1, x_2)) = 3 + 3*x_2
19.06/7.48	   POL(U172(x_1)) = 3
19.06/7.48	   POL(U181(x_1, x_2)) = 3 + 3*x_2
19.06/7.48	   POL(U182(x_1)) = 3
19.06/7.48	   POL(U191(x_1, x_2)) = 3 + 3*x_2
19.06/7.48	   POL(U192(x_1)) = 3
19.06/7.48	   POL(U201(x_1, x_2)) = 3 + 3*x_2
19.06/7.48	   POL(U202(x_1)) = 3
19.06/7.48	   POL(U211(x_1)) = 3
19.06/7.48	   POL(_XOR_(x_1, x_2)) = x_1 + x_2
19.06/7.48	   POL(_and_(x_1, x_2)) = 0
19.06/7.48	   POL(_implies_(x_1, x_2)) = 0
19.06/7.48	   POL(_isEqualTo_(x_1, x_2)) = 0
19.06/7.48	   POL(_isNotEqualTo_(x_1, x_2)) = 0
19.06/7.48	   POL(_or_(x_1, x_2)) = 0
19.06/7.48	   POL(_xor_(x_1, x_2)) = 2 + x_1 + x_2
19.06/7.48	   POL(false) = 1
19.06/7.48	   POL(isBool(x_1)) = 0
19.06/7.48	   POL(isUniversal(x_1)) = 0
19.06/7.48	   POL(not_(x_1)) = 0
19.06/7.48	   POL(true) = 0
19.06/7.48	   POL(tt) = 0
19.06/7.48	
19.06/7.48	
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(16)
19.06/7.48	Obligation:
19.06/7.48	P is empty.
19.06/7.48	The TRS R consists of the following rules:
19.06/7.48	
19.06/7.48	   U101(tt, A, B) -> U102(isBool(B), A, B)
19.06/7.48	   U102(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B))
19.06/7.48	   U11(tt, A) -> A
19.06/7.48	   U111(tt) -> false
19.06/7.48	   U121(tt, A) -> A
19.06/7.48	   U131(tt, B, U', U) -> U132(isS(U'), B, U', U)
19.06/7.48	   U132(tt, B, U', U) -> U133(isS(U), B, U')
19.06/7.48	   U133(tt, B, U') -> U134(equal(_isNotEqualTo_(B, true), true), U')
19.06/7.48	   U134(tt, U') -> U'
19.06/7.48	   U141(tt, U) -> U142(isS(U), U)
19.06/7.48	   U142(tt, U) -> U
19.06/7.48	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.48	   U152(tt) -> tt
19.06/7.48	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.48	   U162(tt) -> tt
19.06/7.48	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.48	   U172(tt) -> tt
19.06/7.48	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.48	   U182(tt) -> tt
19.06/7.48	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.48	   U192(tt) -> tt
19.06/7.48	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.48	   U202(tt) -> tt
19.06/7.48	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.48	   U211(tt) -> tt
19.06/7.48	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.48	   U221(tt, A) -> _xor_(A, true)
19.06/7.48	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.48	   U31(tt) -> false
19.06/7.48	   U41(tt, A) -> A
19.06/7.48	   U51(tt, A, B) -> U52(isBool(B), A, B)
19.06/7.48	   U52(tt, A, B) -> not_(_xor_(A, _and_(A, B)))
19.06/7.48	   U61(tt, U', U) -> U62(isS(U), U', U)
19.06/7.48	   U62(tt, U', U) -> U63(equal(_isNotEqualTo_(U, U'), true))
19.06/7.48	   U63(tt) -> false
19.06/7.48	   U71(tt) -> true
19.06/7.48	   U81(tt, U', U) -> U82(isS(U), U', U)
19.06/7.48	   U82(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true)
19.06/7.48	   U91(tt) -> false
19.06/7.48	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.48	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.48	   _and_(false, A) -> U31(isBool(A))
19.06/7.48	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.48	   _implies_(A, B) -> U51(isBool(A), A, B)
19.06/7.48	   _isEqualTo_(U, U') -> U61(isS(U'), U', U)
19.06/7.48	   _isEqualTo_(U, U) -> U71(isS(U))
19.06/7.48	   _isNotEqualTo_(U, U') -> U81(isS(U'), U', U)
19.06/7.48	   _isNotEqualTo_(U, U) -> U91(isS(U))
19.06/7.48	   _or_(A, B) -> U101(isBool(A), A, B)
19.06/7.48	   _xor_(A, A) -> U111(isBool(A))
19.06/7.48	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.48	   equal(X, X) -> tt
19.06/7.48	   if_then_else_fi(B, U, U') -> U131(isBool(B), B, U', U)
19.06/7.48	   if_then_else_fi(true, U, U') -> U141(isS(U'), U)
19.06/7.48	   isBool(false) -> tt
19.06/7.48	   isBool(true) -> tt
19.06/7.48	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.48	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.48	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.48	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.48	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.48	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.48	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.48	   not_(A) -> U221(isBool(A), A)
19.06/7.48	   not_(false) -> true
19.06/7.48	   not_(true) -> false
19.06/7.48	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.48	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.48	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.48	   _or_(_or_(A, B), ext) -> _or_(U101(isBool(A), A, B), ext)
19.06/7.48	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.48	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.48	
19.06/7.48	The set E consists of the following equations:
19.06/7.48	
19.06/7.48	   _and_(x, y) == _and_(y, x)
19.06/7.48	   _or_(x, y) == _or_(y, x)
19.06/7.48	   _xor_(x, y) == _xor_(y, x)
19.06/7.48	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.48	   _or_(_or_(x, y), z) == _or_(x, _or_(y, z))
19.06/7.48	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.48	
19.06/7.48	The set E# consists of the following equations:
19.06/7.48	
19.06/7.48	   _XOR_(x, y) == _XOR_(y, x)
19.06/7.48	   _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z))
19.06/7.48	
19.06/7.48	We have to consider all minimal (P,E#,R,E)-chains
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(17) PisEmptyProof (EQUIVALENT)
19.06/7.48	The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(18)
19.06/7.48	YES
19.06/7.48	
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(19)
19.06/7.48	Obligation:
19.06/7.48	The TRS P consists of the following rules:
19.06/7.48	
19.06/7.48	   _AND_(_and_(A, _xor_(B, C)), ext) -> _AND_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext)
19.06/7.48	   _AND_(_and_(A, _xor_(B, C)), ext) -> U21^1(isBool(A), A, B, C)
19.06/7.48	   _AND_(_and_(false, A), ext) -> _AND_(U31(isBool(A)), ext)
19.06/7.48	   U23^1(tt, A, B, C) -> _AND_(A, C)
19.06/7.48	   _AND_(_and_(true, A), ext) -> _AND_(U41(isBool(A), A), ext)
19.06/7.48	   U21^1(tt, A, B, C) -> U22^1(isBool(B), A, B, C)
19.06/7.48	   U22^1(tt, A, B, C) -> U23^1(isBool(C), A, B, C)
19.06/7.48	   U23^1(tt, A, B, C) -> _AND_(A, B)
19.06/7.48	   _AND_(A, _xor_(B, C)) -> U21^1(isBool(A), A, B, C)
19.06/7.48	
19.06/7.48	The TRS R consists of the following rules:
19.06/7.48	
19.06/7.48	   U101(tt, A, B) -> U102(isBool(B), A, B)
19.06/7.48	   U102(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B))
19.06/7.48	   U11(tt, A) -> A
19.06/7.48	   U111(tt) -> false
19.06/7.48	   U121(tt, A) -> A
19.06/7.48	   U131(tt, B, U', U) -> U132(isS(U'), B, U', U)
19.06/7.48	   U132(tt, B, U', U) -> U133(isS(U), B, U')
19.06/7.48	   U133(tt, B, U') -> U134(equal(_isNotEqualTo_(B, true), true), U')
19.06/7.48	   U134(tt, U') -> U'
19.06/7.48	   U141(tt, U) -> U142(isS(U), U)
19.06/7.48	   U142(tt, U) -> U
19.06/7.48	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.48	   U152(tt) -> tt
19.06/7.48	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.48	   U162(tt) -> tt
19.06/7.48	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.48	   U172(tt) -> tt
19.06/7.48	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.48	   U182(tt) -> tt
19.06/7.48	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.48	   U192(tt) -> tt
19.06/7.48	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.48	   U202(tt) -> tt
19.06/7.48	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.48	   U211(tt) -> tt
19.06/7.48	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.48	   U221(tt, A) -> _xor_(A, true)
19.06/7.48	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.48	   U31(tt) -> false
19.06/7.48	   U41(tt, A) -> A
19.06/7.48	   U51(tt, A, B) -> U52(isBool(B), A, B)
19.06/7.48	   U52(tt, A, B) -> not_(_xor_(A, _and_(A, B)))
19.06/7.48	   U61(tt, U', U) -> U62(isS(U), U', U)
19.06/7.48	   U62(tt, U', U) -> U63(equal(_isNotEqualTo_(U, U'), true))
19.06/7.48	   U63(tt) -> false
19.06/7.48	   U71(tt) -> true
19.06/7.48	   U81(tt, U', U) -> U82(isS(U), U', U)
19.06/7.48	   U82(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true)
19.06/7.48	   U91(tt) -> false
19.06/7.48	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.48	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.48	   _and_(false, A) -> U31(isBool(A))
19.06/7.48	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.48	   _implies_(A, B) -> U51(isBool(A), A, B)
19.06/7.48	   _isEqualTo_(U, U') -> U61(isS(U'), U', U)
19.06/7.48	   _isEqualTo_(U, U) -> U71(isS(U))
19.06/7.48	   _isNotEqualTo_(U, U') -> U81(isS(U'), U', U)
19.06/7.48	   _isNotEqualTo_(U, U) -> U91(isS(U))
19.06/7.48	   _or_(A, B) -> U101(isBool(A), A, B)
19.06/7.48	   _xor_(A, A) -> U111(isBool(A))
19.06/7.48	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.48	   equal(X, X) -> tt
19.06/7.48	   if_then_else_fi(B, U, U') -> U131(isBool(B), B, U', U)
19.06/7.48	   if_then_else_fi(true, U, U') -> U141(isS(U'), U)
19.06/7.48	   isBool(false) -> tt
19.06/7.48	   isBool(true) -> tt
19.06/7.48	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.48	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.48	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.48	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.48	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.48	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.48	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.48	   not_(A) -> U221(isBool(A), A)
19.06/7.48	   not_(false) -> true
19.06/7.48	   not_(true) -> false
19.06/7.48	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.48	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.48	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.48	   _or_(_or_(A, B), ext) -> _or_(U101(isBool(A), A, B), ext)
19.06/7.48	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.48	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.48	
19.06/7.48	The set E consists of the following equations:
19.06/7.48	
19.06/7.48	   _and_(x, y) == _and_(y, x)
19.06/7.48	   _or_(x, y) == _or_(y, x)
19.06/7.48	   _xor_(x, y) == _xor_(y, x)
19.06/7.48	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.48	   _or_(_or_(x, y), z) == _or_(x, _or_(y, z))
19.06/7.48	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.48	
19.06/7.48	The set E# consists of the following equations:
19.06/7.48	
19.06/7.48	   _AND_(x, y) == _AND_(y, x)
19.06/7.48	   _OR_(x, y) == _OR_(y, x)
19.06/7.48	   _XOR_(x, y) == _XOR_(y, x)
19.06/7.48	   _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z))
19.06/7.48	   _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z))
19.06/7.48	   _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z))
19.06/7.48	
19.06/7.48	We have to consider all minimal (P,E#,R,E)-chains
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(20) ESharpUsableEquationsProof (EQUIVALENT)
19.06/7.48	We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
19.06/7.48	   _OR_(x, y) == _OR_(y, x)
19.06/7.48	   _XOR_(x, y) == _XOR_(y, x)
19.06/7.48	   _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z))
19.06/7.48	   _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z))
19.06/7.48	
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(21)
19.06/7.48	Obligation:
19.06/7.48	The TRS P consists of the following rules:
19.06/7.48	
19.06/7.48	   _AND_(_and_(A, _xor_(B, C)), ext) -> _AND_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext)
19.06/7.48	   _AND_(_and_(A, _xor_(B, C)), ext) -> U21^1(isBool(A), A, B, C)
19.06/7.48	   _AND_(_and_(false, A), ext) -> _AND_(U31(isBool(A)), ext)
19.06/7.48	   U23^1(tt, A, B, C) -> _AND_(A, C)
19.06/7.48	   _AND_(_and_(true, A), ext) -> _AND_(U41(isBool(A), A), ext)
19.06/7.48	   U21^1(tt, A, B, C) -> U22^1(isBool(B), A, B, C)
19.06/7.48	   U22^1(tt, A, B, C) -> U23^1(isBool(C), A, B, C)
19.06/7.48	   U23^1(tt, A, B, C) -> _AND_(A, B)
19.06/7.48	   _AND_(A, _xor_(B, C)) -> U21^1(isBool(A), A, B, C)
19.06/7.48	
19.06/7.48	The TRS R consists of the following rules:
19.06/7.48	
19.06/7.48	   U101(tt, A, B) -> U102(isBool(B), A, B)
19.06/7.48	   U102(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B))
19.06/7.48	   U11(tt, A) -> A
19.06/7.48	   U111(tt) -> false
19.06/7.48	   U121(tt, A) -> A
19.06/7.48	   U131(tt, B, U', U) -> U132(isS(U'), B, U', U)
19.06/7.48	   U132(tt, B, U', U) -> U133(isS(U), B, U')
19.06/7.48	   U133(tt, B, U') -> U134(equal(_isNotEqualTo_(B, true), true), U')
19.06/7.48	   U134(tt, U') -> U'
19.06/7.48	   U141(tt, U) -> U142(isS(U), U)
19.06/7.48	   U142(tt, U) -> U
19.06/7.48	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.48	   U152(tt) -> tt
19.06/7.48	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.48	   U162(tt) -> tt
19.06/7.48	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.48	   U172(tt) -> tt
19.06/7.48	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.48	   U182(tt) -> tt
19.06/7.48	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.48	   U192(tt) -> tt
19.06/7.48	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.48	   U202(tt) -> tt
19.06/7.48	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.48	   U211(tt) -> tt
19.06/7.48	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.48	   U221(tt, A) -> _xor_(A, true)
19.06/7.48	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.48	   U31(tt) -> false
19.06/7.48	   U41(tt, A) -> A
19.06/7.48	   U51(tt, A, B) -> U52(isBool(B), A, B)
19.06/7.48	   U52(tt, A, B) -> not_(_xor_(A, _and_(A, B)))
19.06/7.48	   U61(tt, U', U) -> U62(isS(U), U', U)
19.06/7.48	   U62(tt, U', U) -> U63(equal(_isNotEqualTo_(U, U'), true))
19.06/7.48	   U63(tt) -> false
19.06/7.48	   U71(tt) -> true
19.06/7.48	   U81(tt, U', U) -> U82(isS(U), U', U)
19.06/7.48	   U82(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true)
19.06/7.48	   U91(tt) -> false
19.06/7.48	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.48	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.48	   _and_(false, A) -> U31(isBool(A))
19.06/7.48	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.48	   _implies_(A, B) -> U51(isBool(A), A, B)
19.06/7.48	   _isEqualTo_(U, U') -> U61(isS(U'), U', U)
19.06/7.48	   _isEqualTo_(U, U) -> U71(isS(U))
19.06/7.48	   _isNotEqualTo_(U, U') -> U81(isS(U'), U', U)
19.06/7.48	   _isNotEqualTo_(U, U) -> U91(isS(U))
19.06/7.48	   _or_(A, B) -> U101(isBool(A), A, B)
19.06/7.48	   _xor_(A, A) -> U111(isBool(A))
19.06/7.48	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.48	   equal(X, X) -> tt
19.06/7.48	   if_then_else_fi(B, U, U') -> U131(isBool(B), B, U', U)
19.06/7.48	   if_then_else_fi(true, U, U') -> U141(isS(U'), U)
19.06/7.48	   isBool(false) -> tt
19.06/7.48	   isBool(true) -> tt
19.06/7.48	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.48	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.48	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.48	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.48	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.48	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.48	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.48	   not_(A) -> U221(isBool(A), A)
19.06/7.48	   not_(false) -> true
19.06/7.48	   not_(true) -> false
19.06/7.48	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.48	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.48	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.48	   _or_(_or_(A, B), ext) -> _or_(U101(isBool(A), A, B), ext)
19.06/7.48	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.48	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.48	
19.06/7.48	The set E consists of the following equations:
19.06/7.48	
19.06/7.48	   _and_(x, y) == _and_(y, x)
19.06/7.48	   _or_(x, y) == _or_(y, x)
19.06/7.48	   _xor_(x, y) == _xor_(y, x)
19.06/7.48	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.48	   _or_(_or_(x, y), z) == _or_(x, _or_(y, z))
19.06/7.48	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.48	
19.06/7.48	The set E# consists of the following equations:
19.06/7.48	
19.06/7.48	   _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z))
19.06/7.48	   _AND_(x, y) == _AND_(y, x)
19.06/7.48	
19.06/7.48	We have to consider all minimal (P,E#,R,E)-chains
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(22) EDPPoloProof (EQUIVALENT)
19.06/7.48	We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. The following set of Dependency Pairs of this DP problem can be strictly oriented.
19.06/7.48	
19.06/7.48	
19.06/7.48	   _AND_(_and_(A, _xor_(B, C)), ext) -> U21^1(isBool(A), A, B, C)
19.06/7.48	   _AND_(_and_(true, A), ext) -> _AND_(U41(isBool(A), A), ext)
19.06/7.48	   _AND_(A, _xor_(B, C)) -> U21^1(isBool(A), A, B, C)
19.06/7.48	The remaining Dependency Pairs were at least non-strictly oriented.
19.06/7.48	
19.06/7.48	
19.06/7.48	   _AND_(_and_(A, _xor_(B, C)), ext) -> _AND_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext)
19.06/7.48	   _AND_(_and_(false, A), ext) -> _AND_(U31(isBool(A)), ext)
19.06/7.48	   U23^1(tt, A, B, C) -> _AND_(A, C)
19.06/7.48	   U21^1(tt, A, B, C) -> U22^1(isBool(B), A, B, C)
19.06/7.48	   U22^1(tt, A, B, C) -> U23^1(isBool(C), A, B, C)
19.06/7.48	   U23^1(tt, A, B, C) -> _AND_(A, B)
19.06/7.48	With the implicit AFS we had to orient the following set of usable rules of R non-strictly.
19.06/7.48	
19.06/7.48	
19.06/7.48	   U182(tt) -> tt
19.06/7.48	   U121(tt, A) -> A
19.06/7.48	   U172(tt) -> tt
19.06/7.48	   _and_(false, A) -> U31(isBool(A))
19.06/7.48	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.48	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.48	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.48	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.48	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.48	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.48	   U162(tt) -> tt
19.06/7.48	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.48	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.48	   U152(tt) -> tt
19.06/7.48	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.48	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.48	   U202(tt) -> tt
19.06/7.48	   U11(tt, A) -> A
19.06/7.48	   U41(tt, A) -> A
19.06/7.48	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.48	   _xor_(A, A) -> U111(isBool(A))
19.06/7.48	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.48	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.48	   U192(tt) -> tt
19.06/7.48	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.48	   U111(tt) -> false
19.06/7.48	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.48	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.48	   isBool(true) -> tt
19.06/7.48	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.48	   isBool(false) -> tt
19.06/7.48	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.48	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.48	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.48	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.48	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.48	   U211(tt) -> tt
19.06/7.48	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.48	   U31(tt) -> false
19.06/7.48	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.48	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.48	We had to orient the following equations of E# equivalently.
19.06/7.48	
19.06/7.48	
19.06/7.48	   _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z))
19.06/7.48	   _AND_(x, y) == _AND_(y, x)
19.06/7.48	With the implicit AFS we had to orient the following usable equations of E equivalently.
19.06/7.48	
19.06/7.48	
19.06/7.48	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.48	   _and_(x, y) == _and_(y, x)
19.06/7.48	   _xor_(x, y) == _xor_(y, x)
19.06/7.48	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.48	Used ordering: POLO with Polynomial interpretation [POLO]:
19.06/7.48	
19.06/7.48	   POL(U11(x_1, x_2)) = x_2
19.06/7.48	   POL(U111(x_1)) = 0
19.06/7.48	   POL(U121(x_1, x_2)) = x_2
19.06/7.48	   POL(U151(x_1, x_2)) = 1
19.06/7.48	   POL(U152(x_1)) = x_1
19.06/7.48	   POL(U161(x_1, x_2)) = 1
19.06/7.48	   POL(U162(x_1)) = x_1
19.06/7.48	   POL(U171(x_1, x_2)) = 1
19.06/7.48	   POL(U172(x_1)) = x_1
19.06/7.48	   POL(U181(x_1, x_2)) = 1
19.06/7.48	   POL(U182(x_1)) = x_1^2
19.06/7.48	   POL(U191(x_1, x_2)) = x_1
19.06/7.48	   POL(U192(x_1)) = x_1^2
19.06/7.48	   POL(U201(x_1, x_2)) = 1
19.06/7.48	   POL(U202(x_1)) = x_1
19.06/7.48	   POL(U21(x_1, x_2, x_3, x_4)) = 1 + x_1*x_2 + x_1*x_2*x_3 + x_2 + x_2*x_4 + x_3 + x_4
19.06/7.48	   POL(U211(x_1)) = x_1^2
19.06/7.48	   POL(U21^1(x_1, x_2, x_3, x_4)) = x_1*x_2*x_3 + x_1*x_2*x_4 + x_1*x_3 + x_1*x_4 + x_2
19.06/7.48	   POL(U22(x_1, x_2, x_3, x_4)) = 1 + x_1*x_2 + x_2 + x_2*x_3 + x_2*x_4 + x_3 + x_4
19.06/7.48	   POL(U22^1(x_1, x_2, x_3, x_4)) = x_2 + x_2*x_3 + x_2*x_4 + x_3 + x_4
19.06/7.48	   POL(U23(x_1, x_2, x_3, x_4)) = 1 + x_1*x_2 + x_1*x_2*x_3 + x_1*x_2*x_4 + x_1*x_4 + x_2 + x_3
19.06/7.48	   POL(U23^1(x_1, x_2, x_3, x_4)) = x_1*x_2*x_3 + x_1*x_3 + x_2 + x_2*x_4 + x_4
19.06/7.48	   POL(U31(x_1)) = 0
19.06/7.48	   POL(U41(x_1, x_2)) = x_2
19.06/7.48	   POL(_AND_(x_1, x_2)) = x_1 + x_1*x_2 + x_2
19.06/7.48	   POL(_and_(x_1, x_2)) = x_1 + x_1*x_2 + x_2
19.06/7.48	   POL(_implies_(x_1, x_2)) = 1 + x_1 + x_1*x_2 + x_2
19.06/7.48	   POL(_isEqualTo_(x_1, x_2)) = 1 + x_1 + x_1*x_2 + x_2
19.06/7.48	   POL(_isNotEqualTo_(x_1, x_2)) = 1 + x_1 + x_1*x_2 + x_2
19.06/7.48	   POL(_or_(x_1, x_2)) = 1 + x_1 + x_1*x_2 + x_2
19.06/7.48	   POL(_xor_(x_1, x_2)) = 1 + x_1 + x_2
19.06/7.48	   POL(false) = 0
19.06/7.48	   POL(isBool(x_1)) = 1
19.06/7.48	   POL(isUniversal(x_1)) = 1
19.06/7.48	   POL(not_(x_1)) = 0
19.06/7.48	   POL(true) = 1
19.06/7.48	   POL(tt) = 1
19.06/7.48	
19.06/7.48	
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(23)
19.06/7.48	Obligation:
19.06/7.48	The TRS P consists of the following rules:
19.06/7.48	
19.06/7.48	   _AND_(_and_(A, _xor_(B, C)), ext) -> _AND_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext)
19.06/7.48	   _AND_(_and_(false, A), ext) -> _AND_(U31(isBool(A)), ext)
19.06/7.48	   U23^1(tt, A, B, C) -> _AND_(A, C)
19.06/7.48	   U21^1(tt, A, B, C) -> U22^1(isBool(B), A, B, C)
19.06/7.48	   U22^1(tt, A, B, C) -> U23^1(isBool(C), A, B, C)
19.06/7.48	   U23^1(tt, A, B, C) -> _AND_(A, B)
19.06/7.48	
19.06/7.48	The TRS R consists of the following rules:
19.06/7.48	
19.06/7.48	   U101(tt, A, B) -> U102(isBool(B), A, B)
19.06/7.48	   U102(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B))
19.06/7.48	   U11(tt, A) -> A
19.06/7.48	   U111(tt) -> false
19.06/7.48	   U121(tt, A) -> A
19.06/7.48	   U131(tt, B, U', U) -> U132(isS(U'), B, U', U)
19.06/7.48	   U132(tt, B, U', U) -> U133(isS(U), B, U')
19.06/7.48	   U133(tt, B, U') -> U134(equal(_isNotEqualTo_(B, true), true), U')
19.06/7.48	   U134(tt, U') -> U'
19.06/7.48	   U141(tt, U) -> U142(isS(U), U)
19.06/7.48	   U142(tt, U) -> U
19.06/7.48	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.48	   U152(tt) -> tt
19.06/7.48	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.48	   U162(tt) -> tt
19.06/7.48	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.48	   U172(tt) -> tt
19.06/7.48	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.48	   U182(tt) -> tt
19.06/7.48	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.48	   U192(tt) -> tt
19.06/7.48	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.48	   U202(tt) -> tt
19.06/7.48	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.48	   U211(tt) -> tt
19.06/7.48	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.48	   U221(tt, A) -> _xor_(A, true)
19.06/7.48	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.48	   U31(tt) -> false
19.06/7.48	   U41(tt, A) -> A
19.06/7.48	   U51(tt, A, B) -> U52(isBool(B), A, B)
19.06/7.48	   U52(tt, A, B) -> not_(_xor_(A, _and_(A, B)))
19.06/7.48	   U61(tt, U', U) -> U62(isS(U), U', U)
19.06/7.48	   U62(tt, U', U) -> U63(equal(_isNotEqualTo_(U, U'), true))
19.06/7.48	   U63(tt) -> false
19.06/7.48	   U71(tt) -> true
19.06/7.48	   U81(tt, U', U) -> U82(isS(U), U', U)
19.06/7.48	   U82(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true)
19.06/7.48	   U91(tt) -> false
19.06/7.48	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.48	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.48	   _and_(false, A) -> U31(isBool(A))
19.06/7.48	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.48	   _implies_(A, B) -> U51(isBool(A), A, B)
19.06/7.48	   _isEqualTo_(U, U') -> U61(isS(U'), U', U)
19.06/7.48	   _isEqualTo_(U, U) -> U71(isS(U))
19.06/7.48	   _isNotEqualTo_(U, U') -> U81(isS(U'), U', U)
19.06/7.48	   _isNotEqualTo_(U, U) -> U91(isS(U))
19.06/7.48	   _or_(A, B) -> U101(isBool(A), A, B)
19.06/7.48	   _xor_(A, A) -> U111(isBool(A))
19.06/7.48	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.48	   equal(X, X) -> tt
19.06/7.48	   if_then_else_fi(B, U, U') -> U131(isBool(B), B, U', U)
19.06/7.48	   if_then_else_fi(true, U, U') -> U141(isS(U'), U)
19.06/7.48	   isBool(false) -> tt
19.06/7.48	   isBool(true) -> tt
19.06/7.48	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.48	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.48	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.48	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.48	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.48	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.48	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.48	   not_(A) -> U221(isBool(A), A)
19.06/7.48	   not_(false) -> true
19.06/7.48	   not_(true) -> false
19.06/7.48	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.48	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.48	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.48	   _or_(_or_(A, B), ext) -> _or_(U101(isBool(A), A, B), ext)
19.06/7.48	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.48	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.48	
19.06/7.48	The set E consists of the following equations:
19.06/7.48	
19.06/7.48	   _and_(x, y) == _and_(y, x)
19.06/7.48	   _or_(x, y) == _or_(y, x)
19.06/7.48	   _xor_(x, y) == _xor_(y, x)
19.06/7.48	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.48	   _or_(_or_(x, y), z) == _or_(x, _or_(y, z))
19.06/7.48	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.48	
19.06/7.48	The set E# consists of the following equations:
19.06/7.48	
19.06/7.48	   _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z))
19.06/7.48	   _AND_(x, y) == _AND_(y, x)
19.06/7.48	
19.06/7.48	We have to consider all minimal (P,E#,R,E)-chains
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(24) EDependencyGraphProof (EQUIVALENT)
19.06/7.48	The approximation of the Equational Dependency Graph [DA_STEIN] contains 1 SCC with 4 less nodes.
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(25)
19.06/7.48	Obligation:
19.06/7.48	The TRS P consists of the following rules:
19.06/7.48	
19.06/7.48	   _AND_(_and_(A, _xor_(B, C)), ext) -> _AND_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext)
19.06/7.48	   _AND_(_and_(false, A), ext) -> _AND_(U31(isBool(A)), ext)
19.06/7.48	
19.06/7.48	The TRS R consists of the following rules:
19.06/7.48	
19.06/7.48	   U101(tt, A, B) -> U102(isBool(B), A, B)
19.06/7.48	   U102(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B))
19.06/7.48	   U11(tt, A) -> A
19.06/7.48	   U111(tt) -> false
19.06/7.48	   U121(tt, A) -> A
19.06/7.48	   U131(tt, B, U', U) -> U132(isS(U'), B, U', U)
19.06/7.48	   U132(tt, B, U', U) -> U133(isS(U), B, U')
19.06/7.48	   U133(tt, B, U') -> U134(equal(_isNotEqualTo_(B, true), true), U')
19.06/7.48	   U134(tt, U') -> U'
19.06/7.48	   U141(tt, U) -> U142(isS(U), U)
19.06/7.48	   U142(tt, U) -> U
19.06/7.48	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.48	   U152(tt) -> tt
19.06/7.48	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.48	   U162(tt) -> tt
19.06/7.48	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.48	   U172(tt) -> tt
19.06/7.48	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.48	   U182(tt) -> tt
19.06/7.48	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.48	   U192(tt) -> tt
19.06/7.48	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.48	   U202(tt) -> tt
19.06/7.48	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.48	   U211(tt) -> tt
19.06/7.48	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.48	   U221(tt, A) -> _xor_(A, true)
19.06/7.48	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.48	   U31(tt) -> false
19.06/7.48	   U41(tt, A) -> A
19.06/7.48	   U51(tt, A, B) -> U52(isBool(B), A, B)
19.06/7.48	   U52(tt, A, B) -> not_(_xor_(A, _and_(A, B)))
19.06/7.48	   U61(tt, U', U) -> U62(isS(U), U', U)
19.06/7.48	   U62(tt, U', U) -> U63(equal(_isNotEqualTo_(U, U'), true))
19.06/7.48	   U63(tt) -> false
19.06/7.48	   U71(tt) -> true
19.06/7.48	   U81(tt, U', U) -> U82(isS(U), U', U)
19.06/7.48	   U82(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true)
19.06/7.48	   U91(tt) -> false
19.06/7.48	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.48	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.48	   _and_(false, A) -> U31(isBool(A))
19.06/7.48	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.48	   _implies_(A, B) -> U51(isBool(A), A, B)
19.06/7.48	   _isEqualTo_(U, U') -> U61(isS(U'), U', U)
19.06/7.48	   _isEqualTo_(U, U) -> U71(isS(U))
19.06/7.48	   _isNotEqualTo_(U, U') -> U81(isS(U'), U', U)
19.06/7.48	   _isNotEqualTo_(U, U) -> U91(isS(U))
19.06/7.48	   _or_(A, B) -> U101(isBool(A), A, B)
19.06/7.48	   _xor_(A, A) -> U111(isBool(A))
19.06/7.48	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.48	   equal(X, X) -> tt
19.06/7.48	   if_then_else_fi(B, U, U') -> U131(isBool(B), B, U', U)
19.06/7.48	   if_then_else_fi(true, U, U') -> U141(isS(U'), U)
19.06/7.48	   isBool(false) -> tt
19.06/7.48	   isBool(true) -> tt
19.06/7.48	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.48	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.48	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.48	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.48	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.48	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.48	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.48	   not_(A) -> U221(isBool(A), A)
19.06/7.48	   not_(false) -> true
19.06/7.48	   not_(true) -> false
19.06/7.48	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.48	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.48	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.48	   _or_(_or_(A, B), ext) -> _or_(U101(isBool(A), A, B), ext)
19.06/7.48	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.48	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.48	
19.06/7.48	The set E consists of the following equations:
19.06/7.48	
19.06/7.48	   _and_(x, y) == _and_(y, x)
19.06/7.48	   _or_(x, y) == _or_(y, x)
19.06/7.48	   _xor_(x, y) == _xor_(y, x)
19.06/7.48	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.48	   _or_(_or_(x, y), z) == _or_(x, _or_(y, z))
19.06/7.48	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.48	
19.06/7.48	The set E# consists of the following equations:
19.06/7.48	
19.06/7.48	   _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z))
19.06/7.48	   _AND_(x, y) == _AND_(y, x)
19.06/7.48	
19.06/7.48	We have to consider all minimal (P,E#,R,E)-chains
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(26) EDPPoloProof (EQUIVALENT)
19.06/7.48	We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. The following set of Dependency Pairs of this DP problem can be strictly oriented.
19.06/7.48	
19.06/7.48	
19.06/7.48	   _AND_(_and_(false, A), ext) -> _AND_(U31(isBool(A)), ext)
19.06/7.48	The remaining Dependency Pairs were at least non-strictly oriented.
19.06/7.48	
19.06/7.48	
19.06/7.48	   _AND_(_and_(A, _xor_(B, C)), ext) -> _AND_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext)
19.06/7.48	With the implicit AFS we had to orient the following set of usable rules of R non-strictly.
19.06/7.48	
19.06/7.48	
19.06/7.48	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.48	   _xor_(A, A) -> U111(isBool(A))
19.06/7.48	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.48	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.48	   U31(tt) -> false
19.06/7.48	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.48	   _and_(false, A) -> U31(isBool(A))
19.06/7.48	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.48	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.48	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.48	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.48	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.48	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.48	   U41(tt, A) -> A
19.06/7.48	   U202(tt) -> tt
19.06/7.48	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.48	   U162(tt) -> tt
19.06/7.48	   U152(tt) -> tt
19.06/7.48	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.48	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.48	   U182(tt) -> tt
19.06/7.48	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.48	   U192(tt) -> tt
19.06/7.48	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.48	   U172(tt) -> tt
19.06/7.48	   U111(tt) -> false
19.06/7.48	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.48	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.48	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.48	   isBool(true) -> tt
19.06/7.48	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.48	   isBool(false) -> tt
19.06/7.48	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.48	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.48	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.48	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.48	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.48	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.48	   U121(tt, A) -> A
19.06/7.48	   U211(tt) -> tt
19.06/7.48	   U11(tt, A) -> A
19.06/7.48	We had to orient the following equations of E# equivalently.
19.06/7.48	
19.06/7.48	
19.06/7.48	   _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z))
19.06/7.48	   _AND_(x, y) == _AND_(y, x)
19.06/7.48	With the implicit AFS we had to orient the following usable equations of E equivalently.
19.06/7.48	
19.06/7.48	
19.06/7.48	   _xor_(x, y) == _xor_(y, x)
19.06/7.48	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.48	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.48	   _and_(x, y) == _and_(y, x)
19.06/7.48	Used ordering: POLO with Polynomial interpretation [POLO]:
19.06/7.48	
19.06/7.48	   POL(U11(x_1, x_2)) = x_1*x_2
19.06/7.48	   POL(U111(x_1)) = 1 + x_1
19.06/7.48	   POL(U121(x_1, x_2)) = x_2
19.06/7.48	   POL(U151(x_1, x_2)) = 2*x_2
19.06/7.48	   POL(U152(x_1)) = x_1
19.06/7.48	   POL(U161(x_1, x_2)) = 2*x_1 + 3*x_1*x_2
19.06/7.48	   POL(U162(x_1)) = 2 + 3*x_1
19.06/7.48	   POL(U171(x_1, x_2)) = 0
19.06/7.48	   POL(U172(x_1)) = 2*x_1^2
19.06/7.48	   POL(U181(x_1, x_2)) = 0
19.06/7.48	   POL(U182(x_1)) = x_1^2
19.06/7.48	   POL(U191(x_1, x_2)) = 2*x_1 + 2*x_2
19.06/7.48	   POL(U192(x_1)) = 2
19.06/7.48	   POL(U201(x_1, x_2)) = 2*x_2
19.06/7.48	   POL(U202(x_1)) = x_1
19.06/7.48	   POL(U21(x_1, x_2, x_3, x_4)) = 1 + 2*x_2 + 2*x_2*x_3 + 2*x_2*x_4 + x_3 + x_4
19.06/7.48	   POL(U211(x_1)) = x_1^2
19.06/7.48	   POL(U22(x_1, x_2, x_3, x_4)) = 1 + 2*x_2 + 2*x_2*x_3 + 2*x_2*x_4 + x_3 + x_4
19.06/7.48	   POL(U23(x_1, x_2, x_3, x_4)) = 1 + 2*x_2 + 2*x_2*x_3 + 2*x_2*x_4 + x_3 + x_4
19.06/7.48	   POL(U31(x_1)) = 2*x_1
19.06/7.48	   POL(U41(x_1, x_2)) = 1 + x_2
19.06/7.48	   POL(_AND_(x_1, x_2)) = x_1 + 2*x_1*x_2 + x_2
19.06/7.48	   POL(_and_(x_1, x_2)) = x_1 + 2*x_1*x_2 + x_2
19.06/7.48	   POL(_implies_(x_1, x_2)) = 2*x_1 + 3*x_1*x_2
19.06/7.48	   POL(_isEqualTo_(x_1, x_2)) = 0
19.06/7.48	   POL(_isNotEqualTo_(x_1, x_2)) = 2*x_1
19.06/7.48	   POL(_or_(x_1, x_2)) = 3*x_1 + 3*x_1*x_2 + 2*x_2
19.06/7.48	   POL(_xor_(x_1, x_2)) = 1 + x_1 + x_2
19.06/7.48	   POL(false) = 3
19.06/7.48	   POL(isBool(x_1)) = 2*x_1
19.06/7.48	   POL(isUniversal(x_1)) = 0
19.06/7.48	   POL(not_(x_1)) = 3*x_1^2
19.06/7.48	   POL(true) = 2
19.06/7.48	   POL(tt) = 2
19.06/7.48	
19.06/7.48	
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(27)
19.06/7.48	Obligation:
19.06/7.48	The TRS P consists of the following rules:
19.06/7.48	
19.06/7.48	   _AND_(_and_(A, _xor_(B, C)), ext) -> _AND_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext)
19.06/7.48	
19.06/7.48	The TRS R consists of the following rules:
19.06/7.48	
19.06/7.48	   U101(tt, A, B) -> U102(isBool(B), A, B)
19.06/7.48	   U102(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B))
19.06/7.48	   U11(tt, A) -> A
19.06/7.48	   U111(tt) -> false
19.06/7.48	   U121(tt, A) -> A
19.06/7.48	   U131(tt, B, U', U) -> U132(isS(U'), B, U', U)
19.06/7.48	   U132(tt, B, U', U) -> U133(isS(U), B, U')
19.06/7.48	   U133(tt, B, U') -> U134(equal(_isNotEqualTo_(B, true), true), U')
19.06/7.48	   U134(tt, U') -> U'
19.06/7.48	   U141(tt, U) -> U142(isS(U), U)
19.06/7.48	   U142(tt, U) -> U
19.06/7.48	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.48	   U152(tt) -> tt
19.06/7.48	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.48	   U162(tt) -> tt
19.06/7.48	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.48	   U172(tt) -> tt
19.06/7.48	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.48	   U182(tt) -> tt
19.06/7.48	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.48	   U192(tt) -> tt
19.06/7.48	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.48	   U202(tt) -> tt
19.06/7.48	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.48	   U211(tt) -> tt
19.06/7.48	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.48	   U221(tt, A) -> _xor_(A, true)
19.06/7.48	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.48	   U31(tt) -> false
19.06/7.48	   U41(tt, A) -> A
19.06/7.48	   U51(tt, A, B) -> U52(isBool(B), A, B)
19.06/7.48	   U52(tt, A, B) -> not_(_xor_(A, _and_(A, B)))
19.06/7.48	   U61(tt, U', U) -> U62(isS(U), U', U)
19.06/7.48	   U62(tt, U', U) -> U63(equal(_isNotEqualTo_(U, U'), true))
19.06/7.48	   U63(tt) -> false
19.06/7.48	   U71(tt) -> true
19.06/7.48	   U81(tt, U', U) -> U82(isS(U), U', U)
19.06/7.48	   U82(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true)
19.06/7.48	   U91(tt) -> false
19.06/7.48	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.48	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.48	   _and_(false, A) -> U31(isBool(A))
19.06/7.48	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.48	   _implies_(A, B) -> U51(isBool(A), A, B)
19.06/7.48	   _isEqualTo_(U, U') -> U61(isS(U'), U', U)
19.06/7.48	   _isEqualTo_(U, U) -> U71(isS(U))
19.06/7.48	   _isNotEqualTo_(U, U') -> U81(isS(U'), U', U)
19.06/7.48	   _isNotEqualTo_(U, U) -> U91(isS(U))
19.06/7.48	   _or_(A, B) -> U101(isBool(A), A, B)
19.06/7.48	   _xor_(A, A) -> U111(isBool(A))
19.06/7.48	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.48	   equal(X, X) -> tt
19.06/7.48	   if_then_else_fi(B, U, U') -> U131(isBool(B), B, U', U)
19.06/7.48	   if_then_else_fi(true, U, U') -> U141(isS(U'), U)
19.06/7.48	   isBool(false) -> tt
19.06/7.48	   isBool(true) -> tt
19.06/7.48	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.48	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.48	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.48	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.48	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.48	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.48	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.48	   not_(A) -> U221(isBool(A), A)
19.06/7.48	   not_(false) -> true
19.06/7.48	   not_(true) -> false
19.06/7.48	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.48	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.48	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.48	   _or_(_or_(A, B), ext) -> _or_(U101(isBool(A), A, B), ext)
19.06/7.48	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.48	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.48	
19.06/7.48	The set E consists of the following equations:
19.06/7.48	
19.06/7.48	   _and_(x, y) == _and_(y, x)
19.06/7.48	   _or_(x, y) == _or_(y, x)
19.06/7.48	   _xor_(x, y) == _xor_(y, x)
19.06/7.48	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.48	   _or_(_or_(x, y), z) == _or_(x, _or_(y, z))
19.06/7.48	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.48	
19.06/7.48	The set E# consists of the following equations:
19.06/7.48	
19.06/7.48	   _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z))
19.06/7.48	   _AND_(x, y) == _AND_(y, x)
19.06/7.48	
19.06/7.48	We have to consider all minimal (P,E#,R,E)-chains
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(28) EDPPoloProof (EQUIVALENT)
19.06/7.48	We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. The following set of Dependency Pairs of this DP problem can be strictly oriented.
19.06/7.48	
19.06/7.48	
19.06/7.48	   _AND_(_and_(A, _xor_(B, C)), ext) -> _AND_(U21(isBool(A), A, B, C), ext)
19.06/7.48	The remaining Dependency Pairs were at least non-strictly oriented.
19.06/7.48	
19.06/7.48	
19.06/7.48	   _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext)
19.06/7.48	With the implicit AFS we had to orient the following set of usable rules of R non-strictly.
19.06/7.48	
19.06/7.48	
19.06/7.48	   U31(tt) -> false
19.06/7.48	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.48	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.48	   U41(tt, A) -> A
19.06/7.48	   U152(tt) -> tt
19.06/7.48	   U211(tt) -> tt
19.06/7.48	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.48	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.48	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.48	   U202(tt) -> tt
19.06/7.48	   U162(tt) -> tt
19.06/7.48	   _and_(false, A) -> U31(isBool(A))
19.06/7.48	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.48	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.48	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.48	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.48	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.48	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.48	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.48	   U111(tt) -> false
19.06/7.48	   U11(tt, A) -> A
19.06/7.48	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.48	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.48	   U192(tt) -> tt
19.06/7.48	   U172(tt) -> tt
19.06/7.48	   U182(tt) -> tt
19.06/7.48	   U121(tt, A) -> A
19.06/7.48	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.48	   isBool(true) -> tt
19.06/7.48	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.48	   isBool(false) -> tt
19.06/7.48	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.48	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.48	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.48	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.48	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.48	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.48	   _xor_(A, A) -> U111(isBool(A))
19.06/7.48	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.48	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.48	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.48	We had to orient the following equations of E# equivalently.
19.06/7.48	
19.06/7.48	
19.06/7.48	   _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z))
19.06/7.48	   _AND_(x, y) == _AND_(y, x)
19.06/7.48	With the implicit AFS we had to orient the following usable equations of E equivalently.
19.06/7.48	
19.06/7.48	
19.06/7.48	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.48	   _and_(x, y) == _and_(y, x)
19.06/7.48	   _xor_(x, y) == _xor_(y, x)
19.06/7.48	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.48	Used ordering: POLO with Polynomial interpretation [POLO]:
19.06/7.48	
19.06/7.48	   POL(U11(x_1, x_2)) = x_1 + x_1*x_2 + 3*x_2
19.06/7.48	   POL(U111(x_1)) = 0
19.06/7.48	   POL(U121(x_1, x_2)) = x_1*x_2
19.06/7.48	   POL(U151(x_1, x_2)) = x_1
19.06/7.48	   POL(U152(x_1)) = x_1^2
19.06/7.48	   POL(U161(x_1, x_2)) = 1
19.06/7.48	   POL(U162(x_1)) = x_1^2
19.06/7.48	   POL(U171(x_1, x_2)) = 0
19.06/7.48	   POL(U172(x_1)) = 2*x_1^2
19.06/7.48	   POL(U181(x_1, x_2)) = 1 + 3*x_1
19.06/7.48	   POL(U182(x_1)) = x_1^2
19.06/7.48	   POL(U191(x_1, x_2)) = 1
19.06/7.48	   POL(U192(x_1)) = 1
19.06/7.48	   POL(U201(x_1, x_2)) = 1
19.06/7.48	   POL(U202(x_1)) = x_1
19.06/7.48	   POL(U21(x_1, x_2, x_3, x_4)) = 1 + 3*x_1 + 2*x_1*x_2 + 3*x_2 + 2*x_2*x_3 + 2*x_2*x_4 + 2*x_3 + 2*x_4
19.06/7.48	   POL(U211(x_1)) = x_1^2
19.06/7.48	   POL(U22(x_1, x_2, x_3, x_4)) = 3 + x_1 + 2*x_1*x_2 + 2*x_1*x_3 + x_1*x_4 + 3*x_2 + 2*x_2*x_3 + 2*x_2*x_4 + x_4
19.06/7.48	   POL(U23(x_1, x_2, x_3, x_4)) = 1 + 3*x_1 + 3*x_1*x_2 + x_1*x_2*x_3 + x_1*x_3 + x_1*x_4 + 2*x_2 + x_2*x_3 + 2*x_2*x_4 + x_3 + x_4
19.06/7.48	   POL(U31(x_1)) = 0
19.06/7.48	   POL(U41(x_1, x_2)) = x_2
19.06/7.48	   POL(_AND_(x_1, x_2)) = 2*x_1 + 2*x_1*x_2 + 2*x_2
19.06/7.48	   POL(_and_(x_1, x_2)) = 1 + 2*x_1 + 2*x_1*x_2 + 2*x_2
19.06/7.48	   POL(_implies_(x_1, x_2)) = 0
19.06/7.48	   POL(_isEqualTo_(x_1, x_2)) = 0
19.06/7.48	   POL(_isNotEqualTo_(x_1, x_2)) = 0
19.06/7.48	   POL(_or_(x_1, x_2)) = 0
19.06/7.48	   POL(_xor_(x_1, x_2)) = 2 + x_1 + x_2
19.06/7.48	   POL(false) = 0
19.06/7.48	   POL(isBool(x_1)) = 1
19.06/7.48	   POL(isUniversal(x_1)) = 0
19.06/7.48	   POL(not_(x_1)) = 0
19.06/7.48	   POL(true) = 0
19.06/7.48	   POL(tt) = 1
19.06/7.48	
19.06/7.48	
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(29)
19.06/7.48	Obligation:
19.06/7.48	The TRS P consists of the following rules:
19.06/7.48	
19.06/7.48	   _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext)
19.06/7.48	
19.06/7.48	The TRS R consists of the following rules:
19.06/7.48	
19.06/7.48	   U101(tt, A, B) -> U102(isBool(B), A, B)
19.06/7.48	   U102(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B))
19.06/7.48	   U11(tt, A) -> A
19.06/7.48	   U111(tt) -> false
19.06/7.48	   U121(tt, A) -> A
19.06/7.48	   U131(tt, B, U', U) -> U132(isS(U'), B, U', U)
19.06/7.48	   U132(tt, B, U', U) -> U133(isS(U), B, U')
19.06/7.48	   U133(tt, B, U') -> U134(equal(_isNotEqualTo_(B, true), true), U')
19.06/7.48	   U134(tt, U') -> U'
19.06/7.48	   U141(tt, U) -> U142(isS(U), U)
19.06/7.48	   U142(tt, U) -> U
19.06/7.48	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.48	   U152(tt) -> tt
19.06/7.48	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.48	   U162(tt) -> tt
19.06/7.48	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.48	   U172(tt) -> tt
19.06/7.48	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.48	   U182(tt) -> tt
19.06/7.48	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.48	   U192(tt) -> tt
19.06/7.48	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.48	   U202(tt) -> tt
19.06/7.48	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.48	   U211(tt) -> tt
19.06/7.48	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.48	   U221(tt, A) -> _xor_(A, true)
19.06/7.48	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.48	   U31(tt) -> false
19.06/7.48	   U41(tt, A) -> A
19.06/7.48	   U51(tt, A, B) -> U52(isBool(B), A, B)
19.06/7.48	   U52(tt, A, B) -> not_(_xor_(A, _and_(A, B)))
19.06/7.48	   U61(tt, U', U) -> U62(isS(U), U', U)
19.06/7.48	   U62(tt, U', U) -> U63(equal(_isNotEqualTo_(U, U'), true))
19.06/7.48	   U63(tt) -> false
19.06/7.48	   U71(tt) -> true
19.06/7.48	   U81(tt, U', U) -> U82(isS(U), U', U)
19.06/7.48	   U82(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true)
19.06/7.48	   U91(tt) -> false
19.06/7.48	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.48	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.48	   _and_(false, A) -> U31(isBool(A))
19.06/7.48	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.48	   _implies_(A, B) -> U51(isBool(A), A, B)
19.06/7.48	   _isEqualTo_(U, U') -> U61(isS(U'), U', U)
19.06/7.48	   _isEqualTo_(U, U) -> U71(isS(U))
19.06/7.48	   _isNotEqualTo_(U, U') -> U81(isS(U'), U', U)
19.06/7.48	   _isNotEqualTo_(U, U) -> U91(isS(U))
19.06/7.48	   _or_(A, B) -> U101(isBool(A), A, B)
19.06/7.48	   _xor_(A, A) -> U111(isBool(A))
19.06/7.48	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.48	   equal(X, X) -> tt
19.06/7.48	   if_then_else_fi(B, U, U') -> U131(isBool(B), B, U', U)
19.06/7.48	   if_then_else_fi(true, U, U') -> U141(isS(U'), U)
19.06/7.48	   isBool(false) -> tt
19.06/7.48	   isBool(true) -> tt
19.06/7.48	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.48	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.48	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.48	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.48	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.48	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.48	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.48	   not_(A) -> U221(isBool(A), A)
19.06/7.48	   not_(false) -> true
19.06/7.48	   not_(true) -> false
19.06/7.48	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.48	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.48	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.48	   _or_(_or_(A, B), ext) -> _or_(U101(isBool(A), A, B), ext)
19.06/7.48	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.48	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.48	
19.06/7.48	The set E consists of the following equations:
19.06/7.48	
19.06/7.48	   _and_(x, y) == _and_(y, x)
19.06/7.48	   _or_(x, y) == _or_(y, x)
19.06/7.48	   _xor_(x, y) == _xor_(y, x)
19.06/7.48	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.48	   _or_(_or_(x, y), z) == _or_(x, _or_(y, z))
19.06/7.48	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.48	
19.06/7.48	The set E# consists of the following equations:
19.06/7.48	
19.06/7.48	   _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z))
19.06/7.48	   _AND_(x, y) == _AND_(y, x)
19.06/7.48	
19.06/7.48	We have to consider all minimal (P,E#,R,E)-chains
19.06/7.48	----------------------------------------
19.06/7.48	
19.06/7.48	(30) EDPPoloProof (EQUIVALENT)
19.06/7.48	We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented.
19.06/7.48	
19.06/7.48	
19.06/7.48	   _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext)
19.06/7.48	With the implicit AFS we had to orient the following set of usable rules of R non-strictly.
19.06/7.48	
19.06/7.48	
19.06/7.48	   U31(tt) -> false
19.06/7.48	   U152(tt) -> tt
19.06/7.48	   U162(tt) -> tt
19.06/7.48	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.48	   _xor_(A, A) -> U111(isBool(A))
19.06/7.48	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.48	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.48	   U111(tt) -> false
19.06/7.48	   U121(tt, A) -> A
19.06/7.48	   _and_(false, A) -> U31(isBool(A))
19.06/7.48	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.48	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.48	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.48	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.48	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.48	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.48	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.48	   U202(tt) -> tt
19.06/7.48	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.48	   U211(tt) -> tt
19.06/7.48	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.48	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.48	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.48	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.48	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.48	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.48	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.48	   isBool(true) -> tt
19.06/7.48	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.48	   isBool(false) -> tt
19.06/7.48	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.48	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.48	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.48	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.48	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.48	   U11(tt, A) -> A
19.06/7.48	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.48	   U172(tt) -> tt
19.06/7.48	   U192(tt) -> tt
19.06/7.48	   U41(tt, A) -> A
19.06/7.48	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.48	   U182(tt) -> tt
19.06/7.48	We had to orient the following equations of E# equivalently.
19.06/7.48	
19.06/7.48	
19.06/7.48	   _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z))
19.06/7.48	   _AND_(x, y) == _AND_(y, x)
19.06/7.48	With the implicit AFS we had to orient the following usable equations of E equivalently.
19.06/7.48	
19.06/7.48	
19.06/7.48	   _xor_(x, y) == _xor_(y, x)
19.06/7.48	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.48	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.48	   _and_(x, y) == _and_(y, x)
19.06/7.48	Used ordering: POLO with Polynomial interpretation [POLO]:
19.06/7.48	
19.06/7.48	   POL(U11(x_1, x_2)) = 2*x_2
19.06/7.48	   POL(U111(x_1)) = 0
19.06/7.48	   POL(U121(x_1, x_2)) = x_2
19.06/7.48	   POL(U151(x_1, x_2)) = 2
19.06/7.48	   POL(U152(x_1)) = x_1
19.06/7.48	   POL(U161(x_1, x_2)) = 2
19.06/7.48	   POL(U162(x_1)) = 2
19.06/7.48	   POL(U171(x_1, x_2)) = 2*x_1
19.06/7.48	   POL(U172(x_1)) = x_1
19.06/7.48	   POL(U181(x_1, x_2)) = 2*x_1
19.06/7.48	   POL(U182(x_1)) = 2
19.06/7.48	   POL(U191(x_1, x_2)) = 2
19.06/7.48	   POL(U192(x_1)) = 2
19.06/7.49	   POL(U201(x_1, x_2)) = 2
19.06/7.49	   POL(U202(x_1)) = x_1
19.06/7.49	   POL(U21(x_1, x_2, x_3, x_4)) = 3 + 2*x_1*x_2 + 2*x_2*x_3 + 2*x_2*x_4 + 2*x_3 + 2*x_4
19.06/7.49	   POL(U211(x_1)) = 2
19.06/7.49	   POL(U22(x_1, x_2, x_3, x_4)) = 3 + x_1*x_2 + 2*x_2 + 2*x_2*x_3 + 2*x_2*x_4 + 2*x_3 + 2*x_4
19.06/7.49	   POL(U23(x_1, x_2, x_3, x_4)) = 3 + 2*x_1*x_2 + 2*x_2*x_3 + 2*x_2*x_4 + 2*x_3 + 2*x_4
19.06/7.49	   POL(U31(x_1)) = 1
19.06/7.49	   POL(U41(x_1, x_2)) = 2*x_1 + 2*x_1*x_2
19.06/7.49	   POL(_AND_(x_1, x_2)) = 2*x_1 + 2*x_1*x_2 + 2*x_2
19.06/7.49	   POL(_and_(x_1, x_2)) = 1 + 2*x_1 + 2*x_1*x_2 + 2*x_2
19.06/7.49	   POL(_implies_(x_1, x_2)) = 0
19.06/7.49	   POL(_isEqualTo_(x_1, x_2)) = 0
19.06/7.49	   POL(_isNotEqualTo_(x_1, x_2)) = 0
19.06/7.49	   POL(_or_(x_1, x_2)) = 0
19.06/7.49	   POL(_xor_(x_1, x_2)) = 1 + x_1 + x_2
19.06/7.49	   POL(false) = 0
19.06/7.49	   POL(isBool(x_1)) = 2
19.06/7.49	   POL(isUniversal(x_1)) = 0
19.06/7.49	   POL(not_(x_1)) = 0
19.06/7.49	   POL(true) = 3
19.06/7.49	   POL(tt) = 2
19.06/7.49	
19.06/7.49	
19.06/7.49	----------------------------------------
19.06/7.49	
19.06/7.49	(31)
19.06/7.49	Obligation:
19.06/7.49	P is empty.
19.06/7.49	The TRS R consists of the following rules:
19.06/7.49	
19.06/7.49	   U101(tt, A, B) -> U102(isBool(B), A, B)
19.06/7.49	   U102(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B))
19.06/7.49	   U11(tt, A) -> A
19.06/7.49	   U111(tt) -> false
19.06/7.49	   U121(tt, A) -> A
19.06/7.49	   U131(tt, B, U', U) -> U132(isS(U'), B, U', U)
19.06/7.49	   U132(tt, B, U', U) -> U133(isS(U), B, U')
19.06/7.49	   U133(tt, B, U') -> U134(equal(_isNotEqualTo_(B, true), true), U')
19.06/7.49	   U134(tt, U') -> U'
19.06/7.49	   U141(tt, U) -> U142(isS(U), U)
19.06/7.49	   U142(tt, U) -> U
19.06/7.49	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.49	   U152(tt) -> tt
19.06/7.49	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.49	   U162(tt) -> tt
19.06/7.49	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.49	   U172(tt) -> tt
19.06/7.49	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.49	   U182(tt) -> tt
19.06/7.49	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.49	   U192(tt) -> tt
19.06/7.49	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.49	   U202(tt) -> tt
19.06/7.49	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.49	   U211(tt) -> tt
19.06/7.49	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.49	   U221(tt, A) -> _xor_(A, true)
19.06/7.49	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.49	   U31(tt) -> false
19.06/7.49	   U41(tt, A) -> A
19.06/7.49	   U51(tt, A, B) -> U52(isBool(B), A, B)
19.06/7.49	   U52(tt, A, B) -> not_(_xor_(A, _and_(A, B)))
19.06/7.49	   U61(tt, U', U) -> U62(isS(U), U', U)
19.06/7.49	   U62(tt, U', U) -> U63(equal(_isNotEqualTo_(U, U'), true))
19.06/7.49	   U63(tt) -> false
19.06/7.49	   U71(tt) -> true
19.06/7.49	   U81(tt, U', U) -> U82(isS(U), U', U)
19.06/7.49	   U82(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true)
19.06/7.49	   U91(tt) -> false
19.06/7.49	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.49	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.49	   _and_(false, A) -> U31(isBool(A))
19.06/7.49	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.49	   _implies_(A, B) -> U51(isBool(A), A, B)
19.06/7.49	   _isEqualTo_(U, U') -> U61(isS(U'), U', U)
19.06/7.49	   _isEqualTo_(U, U) -> U71(isS(U))
19.06/7.49	   _isNotEqualTo_(U, U') -> U81(isS(U'), U', U)
19.06/7.49	   _isNotEqualTo_(U, U) -> U91(isS(U))
19.06/7.49	   _or_(A, B) -> U101(isBool(A), A, B)
19.06/7.49	   _xor_(A, A) -> U111(isBool(A))
19.06/7.49	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.49	   equal(X, X) -> tt
19.06/7.49	   if_then_else_fi(B, U, U') -> U131(isBool(B), B, U', U)
19.06/7.49	   if_then_else_fi(true, U, U') -> U141(isS(U'), U)
19.06/7.49	   isBool(false) -> tt
19.06/7.49	   isBool(true) -> tt
19.06/7.49	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.49	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.49	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.49	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.49	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.49	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.49	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.49	   not_(A) -> U221(isBool(A), A)
19.06/7.49	   not_(false) -> true
19.06/7.49	   not_(true) -> false
19.06/7.49	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.49	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.49	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.49	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.49	   _or_(_or_(A, B), ext) -> _or_(U101(isBool(A), A, B), ext)
19.06/7.49	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.49	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.49	
19.06/7.49	The set E consists of the following equations:
19.06/7.49	
19.06/7.49	   _and_(x, y) == _and_(y, x)
19.06/7.49	   _or_(x, y) == _or_(y, x)
19.06/7.49	   _xor_(x, y) == _xor_(y, x)
19.06/7.49	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.49	   _or_(_or_(x, y), z) == _or_(x, _or_(y, z))
19.06/7.49	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.49	
19.06/7.49	The set E# consists of the following equations:
19.06/7.49	
19.06/7.49	   _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z))
19.06/7.49	   _AND_(x, y) == _AND_(y, x)
19.06/7.49	
19.06/7.49	We have to consider all minimal (P,E#,R,E)-chains
19.06/7.49	----------------------------------------
19.06/7.49	
19.06/7.49	(32) PisEmptyProof (EQUIVALENT)
19.06/7.49	The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
19.06/7.49	----------------------------------------
19.06/7.49	
19.06/7.49	(33)
19.06/7.49	YES
19.06/7.49	
19.06/7.49	----------------------------------------
19.06/7.49	
19.06/7.49	(34)
19.06/7.49	Obligation:
19.06/7.49	The TRS P consists of the following rules:
19.06/7.49	
19.06/7.49	   _OR_(_or_(A, B), ext) -> _OR_(U101(isBool(A), A, B), ext)
19.06/7.49	
19.06/7.49	The TRS R consists of the following rules:
19.06/7.49	
19.06/7.49	   U101(tt, A, B) -> U102(isBool(B), A, B)
19.06/7.49	   U102(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B))
19.06/7.49	   U11(tt, A) -> A
19.06/7.49	   U111(tt) -> false
19.06/7.49	   U121(tt, A) -> A
19.06/7.49	   U131(tt, B, U', U) -> U132(isS(U'), B, U', U)
19.06/7.49	   U132(tt, B, U', U) -> U133(isS(U), B, U')
19.06/7.49	   U133(tt, B, U') -> U134(equal(_isNotEqualTo_(B, true), true), U')
19.06/7.49	   U134(tt, U') -> U'
19.06/7.49	   U141(tt, U) -> U142(isS(U), U)
19.06/7.49	   U142(tt, U) -> U
19.06/7.49	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.49	   U152(tt) -> tt
19.06/7.49	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.49	   U162(tt) -> tt
19.06/7.49	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.49	   U172(tt) -> tt
19.06/7.49	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.49	   U182(tt) -> tt
19.06/7.49	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.49	   U192(tt) -> tt
19.06/7.49	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.49	   U202(tt) -> tt
19.06/7.49	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.49	   U211(tt) -> tt
19.06/7.49	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.49	   U221(tt, A) -> _xor_(A, true)
19.06/7.49	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.49	   U31(tt) -> false
19.06/7.49	   U41(tt, A) -> A
19.06/7.49	   U51(tt, A, B) -> U52(isBool(B), A, B)
19.06/7.49	   U52(tt, A, B) -> not_(_xor_(A, _and_(A, B)))
19.06/7.49	   U61(tt, U', U) -> U62(isS(U), U', U)
19.06/7.49	   U62(tt, U', U) -> U63(equal(_isNotEqualTo_(U, U'), true))
19.06/7.49	   U63(tt) -> false
19.06/7.49	   U71(tt) -> true
19.06/7.49	   U81(tt, U', U) -> U82(isS(U), U', U)
19.06/7.49	   U82(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true)
19.06/7.49	   U91(tt) -> false
19.06/7.49	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.49	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.49	   _and_(false, A) -> U31(isBool(A))
19.06/7.49	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.49	   _implies_(A, B) -> U51(isBool(A), A, B)
19.06/7.49	   _isEqualTo_(U, U') -> U61(isS(U'), U', U)
19.06/7.49	   _isEqualTo_(U, U) -> U71(isS(U))
19.06/7.49	   _isNotEqualTo_(U, U') -> U81(isS(U'), U', U)
19.06/7.49	   _isNotEqualTo_(U, U) -> U91(isS(U))
19.06/7.49	   _or_(A, B) -> U101(isBool(A), A, B)
19.06/7.49	   _xor_(A, A) -> U111(isBool(A))
19.06/7.49	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.49	   equal(X, X) -> tt
19.06/7.49	   if_then_else_fi(B, U, U') -> U131(isBool(B), B, U', U)
19.06/7.49	   if_then_else_fi(true, U, U') -> U141(isS(U'), U)
19.06/7.49	   isBool(false) -> tt
19.06/7.49	   isBool(true) -> tt
19.06/7.49	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.49	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.49	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.49	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.49	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.49	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.49	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.49	   not_(A) -> U221(isBool(A), A)
19.06/7.49	   not_(false) -> true
19.06/7.49	   not_(true) -> false
19.06/7.49	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.49	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.49	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.49	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.49	   _or_(_or_(A, B), ext) -> _or_(U101(isBool(A), A, B), ext)
19.06/7.49	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.49	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.49	
19.06/7.49	The set E consists of the following equations:
19.06/7.49	
19.06/7.49	   _and_(x, y) == _and_(y, x)
19.06/7.49	   _or_(x, y) == _or_(y, x)
19.06/7.49	   _xor_(x, y) == _xor_(y, x)
19.06/7.49	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.49	   _or_(_or_(x, y), z) == _or_(x, _or_(y, z))
19.06/7.49	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.49	
19.06/7.49	The set E# consists of the following equations:
19.06/7.49	
19.06/7.49	   _AND_(x, y) == _AND_(y, x)
19.06/7.49	   _OR_(x, y) == _OR_(y, x)
19.06/7.49	   _XOR_(x, y) == _XOR_(y, x)
19.06/7.49	   _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z))
19.06/7.49	   _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z))
19.06/7.49	   _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z))
19.06/7.49	
19.06/7.49	We have to consider all minimal (P,E#,R,E)-chains
19.06/7.49	----------------------------------------
19.06/7.49	
19.06/7.49	(35) ESharpUsableEquationsProof (EQUIVALENT)
19.06/7.49	We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
19.06/7.49	   _AND_(x, y) == _AND_(y, x)
19.06/7.49	   _XOR_(x, y) == _XOR_(y, x)
19.06/7.49	   _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z))
19.06/7.49	   _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z))
19.06/7.49	
19.06/7.49	----------------------------------------
19.06/7.49	
19.06/7.49	(36)
19.06/7.49	Obligation:
19.06/7.49	The TRS P consists of the following rules:
19.06/7.49	
19.06/7.49	   _OR_(_or_(A, B), ext) -> _OR_(U101(isBool(A), A, B), ext)
19.06/7.49	
19.06/7.49	The TRS R consists of the following rules:
19.06/7.49	
19.06/7.49	   U101(tt, A, B) -> U102(isBool(B), A, B)
19.06/7.49	   U102(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B))
19.06/7.49	   U11(tt, A) -> A
19.06/7.49	   U111(tt) -> false
19.06/7.49	   U121(tt, A) -> A
19.06/7.49	   U131(tt, B, U', U) -> U132(isS(U'), B, U', U)
19.06/7.49	   U132(tt, B, U', U) -> U133(isS(U), B, U')
19.06/7.49	   U133(tt, B, U') -> U134(equal(_isNotEqualTo_(B, true), true), U')
19.06/7.49	   U134(tt, U') -> U'
19.06/7.49	   U141(tt, U) -> U142(isS(U), U)
19.06/7.49	   U142(tt, U) -> U
19.06/7.49	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.49	   U152(tt) -> tt
19.06/7.49	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.49	   U162(tt) -> tt
19.06/7.49	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.49	   U172(tt) -> tt
19.06/7.49	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.49	   U182(tt) -> tt
19.06/7.49	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.49	   U192(tt) -> tt
19.06/7.49	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.49	   U202(tt) -> tt
19.06/7.49	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.49	   U211(tt) -> tt
19.06/7.49	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.49	   U221(tt, A) -> _xor_(A, true)
19.06/7.49	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.49	   U31(tt) -> false
19.06/7.49	   U41(tt, A) -> A
19.06/7.49	   U51(tt, A, B) -> U52(isBool(B), A, B)
19.06/7.49	   U52(tt, A, B) -> not_(_xor_(A, _and_(A, B)))
19.06/7.49	   U61(tt, U', U) -> U62(isS(U), U', U)
19.06/7.49	   U62(tt, U', U) -> U63(equal(_isNotEqualTo_(U, U'), true))
19.06/7.49	   U63(tt) -> false
19.06/7.49	   U71(tt) -> true
19.06/7.49	   U81(tt, U', U) -> U82(isS(U), U', U)
19.06/7.49	   U82(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true)
19.06/7.49	   U91(tt) -> false
19.06/7.49	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.49	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.49	   _and_(false, A) -> U31(isBool(A))
19.06/7.49	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.49	   _implies_(A, B) -> U51(isBool(A), A, B)
19.06/7.49	   _isEqualTo_(U, U') -> U61(isS(U'), U', U)
19.06/7.49	   _isEqualTo_(U, U) -> U71(isS(U))
19.06/7.49	   _isNotEqualTo_(U, U') -> U81(isS(U'), U', U)
19.06/7.49	   _isNotEqualTo_(U, U) -> U91(isS(U))
19.06/7.49	   _or_(A, B) -> U101(isBool(A), A, B)
19.06/7.49	   _xor_(A, A) -> U111(isBool(A))
19.06/7.49	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.49	   equal(X, X) -> tt
19.06/7.49	   if_then_else_fi(B, U, U') -> U131(isBool(B), B, U', U)
19.06/7.49	   if_then_else_fi(true, U, U') -> U141(isS(U'), U)
19.06/7.49	   isBool(false) -> tt
19.06/7.49	   isBool(true) -> tt
19.06/7.49	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.49	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.49	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.49	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.49	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.49	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.49	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.49	   not_(A) -> U221(isBool(A), A)
19.06/7.49	   not_(false) -> true
19.06/7.49	   not_(true) -> false
19.06/7.49	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.49	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.49	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.49	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.49	   _or_(_or_(A, B), ext) -> _or_(U101(isBool(A), A, B), ext)
19.06/7.49	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.49	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.49	
19.06/7.49	The set E consists of the following equations:
19.06/7.49	
19.06/7.49	   _and_(x, y) == _and_(y, x)
19.06/7.49	   _or_(x, y) == _or_(y, x)
19.06/7.49	   _xor_(x, y) == _xor_(y, x)
19.06/7.49	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.49	   _or_(_or_(x, y), z) == _or_(x, _or_(y, z))
19.06/7.49	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.49	
19.06/7.49	The set E# consists of the following equations:
19.06/7.49	
19.06/7.49	   _OR_(x, y) == _OR_(y, x)
19.06/7.49	   _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z))
19.06/7.49	
19.06/7.49	We have to consider all minimal (P,E#,R,E)-chains
19.06/7.49	----------------------------------------
19.06/7.49	
19.06/7.49	(37) EDPPoloProof (EQUIVALENT)
19.06/7.49	We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented.
19.06/7.49	
19.06/7.49	
19.06/7.49	   _OR_(_or_(A, B), ext) -> _OR_(U101(isBool(A), A, B), ext)
19.06/7.49	With the implicit AFS we had to orient the following set of usable rules of R non-strictly.
19.06/7.49	
19.06/7.49	
19.06/7.49	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.49	   U172(tt) -> tt
19.06/7.49	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.49	   isBool(true) -> tt
19.06/7.49	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.49	   isBool(false) -> tt
19.06/7.49	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.49	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.49	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.49	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.49	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.49	   U11(tt, A) -> A
19.06/7.49	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.49	   U152(tt) -> tt
19.06/7.49	   U41(tt, A) -> A
19.06/7.49	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.49	   U192(tt) -> tt
19.06/7.49	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.49	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.49	   U31(tt) -> false
19.06/7.49	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.49	   U182(tt) -> tt
19.06/7.49	   U121(tt, A) -> A
19.06/7.49	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.49	   U101(tt, A, B) -> U102(isBool(B), A, B)
19.06/7.49	   U102(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B))
19.06/7.49	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.49	   U162(tt) -> tt
19.06/7.49	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.49	   _xor_(A, A) -> U111(isBool(A))
19.06/7.49	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.49	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.49	   _or_(_or_(A, B), ext) -> _or_(U101(isBool(A), A, B), ext)
19.06/7.49	   _or_(A, B) -> U101(isBool(A), A, B)
19.06/7.49	   U211(tt) -> tt
19.06/7.49	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.49	   _and_(false, A) -> U31(isBool(A))
19.06/7.49	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.49	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.49	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.49	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.49	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.49	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.49	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.49	   U202(tt) -> tt
19.06/7.49	   U111(tt) -> false
19.06/7.49	We had to orient the following equations of E# equivalently.
19.06/7.49	
19.06/7.49	
19.06/7.49	   _OR_(x, y) == _OR_(y, x)
19.06/7.49	   _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z))
19.06/7.49	With the implicit AFS we had to orient the following usable equations of E equivalently.
19.06/7.49	
19.06/7.49	
19.06/7.49	   _xor_(x, y) == _xor_(y, x)
19.06/7.49	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.49	   _or_(x, y) == _or_(y, x)
19.06/7.49	   _or_(_or_(x, y), z) == _or_(x, _or_(y, z))
19.06/7.49	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.49	   _and_(x, y) == _and_(y, x)
19.06/7.49	Used ordering: POLO with Polynomial interpretation [POLO]:
19.06/7.49	
19.06/7.49	   POL(U101(x_1, x_2, x_3)) = x_2 + 2*x_2*x_3 + x_3
19.06/7.49	   POL(U102(x_1, x_2, x_3)) = x_2 + 2*x_2*x_3 + x_3
19.06/7.49	   POL(U11(x_1, x_2)) = x_1*x_2
19.06/7.49	   POL(U111(x_1)) = x_1
19.06/7.49	   POL(U121(x_1, x_2)) = x_2
19.06/7.49	   POL(U151(x_1, x_2)) = 2*x_1*x_2
19.06/7.49	   POL(U152(x_1)) = x_1
19.06/7.49	   POL(U161(x_1, x_2)) = 3*x_1*x_2 + x_2
19.06/7.49	   POL(U162(x_1)) = x_1
19.06/7.49	   POL(U171(x_1, x_2)) = 0
19.06/7.49	   POL(U172(x_1)) = 2*x_1^2
19.06/7.49	   POL(U181(x_1, x_2)) = 0
19.06/7.49	   POL(U182(x_1)) = x_1^2
19.06/7.49	   POL(U191(x_1, x_2)) = x_1
19.06/7.49	   POL(U192(x_1)) = 1
19.06/7.49	   POL(U201(x_1, x_2)) = 2*x_2
19.06/7.49	   POL(U202(x_1)) = x_1
19.06/7.49	   POL(U21(x_1, x_2, x_3, x_4)) = 2*x_2*x_3 + 2*x_2*x_4
19.06/7.49	   POL(U211(x_1)) = x_1
19.06/7.49	   POL(U22(x_1, x_2, x_3, x_4)) = 2*x_2*x_3 + 2*x_2*x_4
19.06/7.49	   POL(U23(x_1, x_2, x_3, x_4)) = 2*x_2*x_3 + 2*x_2*x_4
19.06/7.49	   POL(U31(x_1)) = x_1
19.06/7.49	   POL(U41(x_1, x_2)) = 2*x_2
19.06/7.49	   POL(_OR_(x_1, x_2)) = 2*x_1 + 2*x_1*x_2 + 2*x_2
19.06/7.49	   POL(_and_(x_1, x_2)) = 2*x_1*x_2
19.06/7.49	   POL(_implies_(x_1, x_2)) = 3*x_1 + 3*x_1*x_2 + x_2
19.06/7.49	   POL(_isEqualTo_(x_1, x_2)) = 3 + 3*x_1 + 3*x_1*x_2 + 3*x_2
19.06/7.49	   POL(_isNotEqualTo_(x_1, x_2)) = x_1 + 2*x_2
19.06/7.49	   POL(_or_(x_1, x_2)) = 2 + 3*x_1 + 3*x_1*x_2 + 3*x_2
19.06/7.49	   POL(_xor_(x_1, x_2)) = x_1 + x_2
19.06/7.49	   POL(false) = 1
19.06/7.49	   POL(isBool(x_1)) = 2*x_1
19.06/7.49	   POL(isUniversal(x_1)) = 0
19.06/7.49	   POL(not_(x_1)) = x_1 + x_1^2
19.06/7.49	   POL(true) = 1
19.06/7.49	   POL(tt) = 1
19.06/7.49	
19.06/7.49	
19.06/7.49	----------------------------------------
19.06/7.49	
19.06/7.49	(38)
19.06/7.49	Obligation:
19.06/7.49	P is empty.
19.06/7.49	The TRS R consists of the following rules:
19.06/7.49	
19.06/7.49	   U101(tt, A, B) -> U102(isBool(B), A, B)
19.06/7.49	   U102(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B))
19.06/7.49	   U11(tt, A) -> A
19.06/7.49	   U111(tt) -> false
19.06/7.49	   U121(tt, A) -> A
19.06/7.49	   U131(tt, B, U', U) -> U132(isS(U'), B, U', U)
19.06/7.49	   U132(tt, B, U', U) -> U133(isS(U), B, U')
19.06/7.49	   U133(tt, B, U') -> U134(equal(_isNotEqualTo_(B, true), true), U')
19.06/7.49	   U134(tt, U') -> U'
19.06/7.49	   U141(tt, U) -> U142(isS(U), U)
19.06/7.49	   U142(tt, U) -> U
19.06/7.49	   U151(tt, V2) -> U152(isBool(V2))
19.06/7.49	   U152(tt) -> tt
19.06/7.49	   U161(tt, V2) -> U162(isBool(V2))
19.06/7.49	   U162(tt) -> tt
19.06/7.49	   U171(tt, V2) -> U172(isUniversal(V2))
19.06/7.49	   U172(tt) -> tt
19.06/7.49	   U181(tt, V2) -> U182(isUniversal(V2))
19.06/7.49	   U182(tt) -> tt
19.06/7.49	   U191(tt, V2) -> U192(isBool(V2))
19.06/7.49	   U192(tt) -> tt
19.06/7.49	   U201(tt, V2) -> U202(isBool(V2))
19.06/7.49	   U202(tt) -> tt
19.06/7.49	   U21(tt, A, B, C) -> U22(isBool(B), A, B, C)
19.06/7.49	   U211(tt) -> tt
19.06/7.49	   U22(tt, A, B, C) -> U23(isBool(C), A, B, C)
19.06/7.49	   U221(tt, A) -> _xor_(A, true)
19.06/7.49	   U23(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C))
19.06/7.49	   U31(tt) -> false
19.06/7.49	   U41(tt, A) -> A
19.06/7.49	   U51(tt, A, B) -> U52(isBool(B), A, B)
19.06/7.49	   U52(tt, A, B) -> not_(_xor_(A, _and_(A, B)))
19.06/7.49	   U61(tt, U', U) -> U62(isS(U), U', U)
19.06/7.49	   U62(tt, U', U) -> U63(equal(_isNotEqualTo_(U, U'), true))
19.06/7.49	   U63(tt) -> false
19.06/7.49	   U71(tt) -> true
19.06/7.49	   U81(tt, U', U) -> U82(isS(U), U', U)
19.06/7.49	   U82(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true)
19.06/7.49	   U91(tt) -> false
19.06/7.49	   _and_(A, A) -> U11(isBool(A), A)
19.06/7.49	   _and_(A, _xor_(B, C)) -> U21(isBool(A), A, B, C)
19.06/7.49	   _and_(false, A) -> U31(isBool(A))
19.06/7.49	   _and_(true, A) -> U41(isBool(A), A)
19.06/7.49	   _implies_(A, B) -> U51(isBool(A), A, B)
19.06/7.49	   _isEqualTo_(U, U') -> U61(isS(U'), U', U)
19.06/7.49	   _isEqualTo_(U, U) -> U71(isS(U))
19.06/7.49	   _isNotEqualTo_(U, U') -> U81(isS(U'), U', U)
19.06/7.49	   _isNotEqualTo_(U, U) -> U91(isS(U))
19.06/7.49	   _or_(A, B) -> U101(isBool(A), A, B)
19.06/7.49	   _xor_(A, A) -> U111(isBool(A))
19.06/7.49	   _xor_(false, A) -> U121(isBool(A), A)
19.06/7.49	   equal(X, X) -> tt
19.06/7.49	   if_then_else_fi(B, U, U') -> U131(isBool(B), B, U', U)
19.06/7.49	   if_then_else_fi(true, U, U') -> U141(isS(U'), U)
19.06/7.49	   isBool(false) -> tt
19.06/7.49	   isBool(true) -> tt
19.06/7.49	   isBool(_and_(V1, V2)) -> U151(isBool(V1), V2)
19.06/7.49	   isBool(_implies_(V1, V2)) -> U161(isBool(V1), V2)
19.06/7.49	   isBool(_isEqualTo_(V1, V2)) -> U171(isUniversal(V1), V2)
19.06/7.49	   isBool(_isNotEqualTo_(V1, V2)) -> U181(isUniversal(V1), V2)
19.06/7.49	   isBool(_or_(V1, V2)) -> U191(isBool(V1), V2)
19.06/7.49	   isBool(_xor_(V1, V2)) -> U201(isBool(V1), V2)
19.06/7.49	   isBool(not_(V1)) -> U211(isBool(V1))
19.06/7.49	   not_(A) -> U221(isBool(A), A)
19.06/7.49	   not_(false) -> true
19.06/7.49	   not_(true) -> false
19.06/7.49	   _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext)
19.06/7.49	   _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(isBool(A), A, B, C), ext)
19.06/7.49	   _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext)
19.06/7.49	   _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext)
19.06/7.49	   _or_(_or_(A, B), ext) -> _or_(U101(isBool(A), A, B), ext)
19.06/7.49	   _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext)
19.06/7.49	   _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext)
19.06/7.49	
19.06/7.49	The set E consists of the following equations:
19.06/7.49	
19.06/7.49	   _and_(x, y) == _and_(y, x)
19.06/7.49	   _or_(x, y) == _or_(y, x)
19.06/7.49	   _xor_(x, y) == _xor_(y, x)
19.06/7.49	   _and_(_and_(x, y), z) == _and_(x, _and_(y, z))
19.06/7.49	   _or_(_or_(x, y), z) == _or_(x, _or_(y, z))
19.06/7.49	   _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z))
19.06/7.49	
19.06/7.49	The set E# consists of the following equations:
19.06/7.49	
19.06/7.49	   _OR_(x, y) == _OR_(y, x)
19.06/7.49	   _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z))
19.06/7.49	
19.06/7.49	We have to consider all minimal (P,E#,R,E)-chains
19.06/7.49	----------------------------------------
19.06/7.49	
19.06/7.49	(39) PisEmptyProof (EQUIVALENT)
19.06/7.49	The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
19.06/7.49	----------------------------------------
19.06/7.49	
19.06/7.49	(40)
19.06/7.49	YES
19.06/7.52	EOF