%--------------------------------------------------------------------------
% File     : HWV002-1 : TPTP v8.2.0. Released v1.1.0.
% Domain   : Hardware Verification
% Problem  : Invert 3 inputs with 2 not gates
% Version  : [ANL] axioms : Reduced > Complete.
% English  : This is made to validate the circuit that inverts 3 inputs
%            using as many AND and OR gates as you like, but using only
%            two NOT gates.

% Refs     : [WO+92] Wos et al. (1992), Automated Reasoning: Introduction a
% Source   : [ANL]
% Names    : two.inverter.val.ver1.in [ANL]

% Status   : Unsatisfiable
% Rating   : 0.50 v8.2.0, 0.33 v7.5.0, 0.10 v7.4.0, 0.11 v7.2.0, 0.12 v7.1.0, 0.14 v6.4.0, 0.29 v6.3.0, 0.17 v6.2.0, 0.00 v6.1.0, 0.20 v6.0.0, 0.56 v5.5.0, 0.69 v5.4.0, 0.67 v5.3.0, 0.75 v5.2.0, 0.50 v5.1.0, 0.57 v4.1.0, 0.67 v4.0.1, 0.50 v3.7.0, 0.33 v3.3.0, 0.43 v3.1.0, 0.56 v2.7.0, 0.67 v2.6.0, 0.57 v2.5.0, 0.40 v2.4.0, 0.67 v2.2.1, 1.00 v2.0.0
% Syntax   : Number of clauses     :   51 (  50 unt;   0 nHn;  34 RR)
%            Number of literals    :   53 (  47 equ;   3 neg)
%            Maximal clause size   :    3 (   1 avg)
%            Maximal term depth    :    3 (   1 avg)
%            Number of predicates  :    2 (   1 usr;   0 prp; 1-2 aty)
%            Number of functors    :   39 (  39 usr;  35 con; 0-2 aty)
%            Number of variables   :   28 (   2 sgn)
% SPC      : CNF_UNS_RFO_SEQ_HRN

% Comments : Some duplicate clauses have been removed from the [ANL] version.
%--------------------------------------------------------------------------
%----Canonicalizing an exclusive-or/and expression
cnf(xor_definition1,axiom,
    xor(n0,X) = X ).

cnf(xor_definition2,axiom,
    xor(X,n0) = X ).

cnf(xor_definition3,axiom,
    xor(X,X) = n0 ).

cnf(xor_simplification1,axiom,
    xor(X,xor(X,Y)) = Y ).

cnf(and_definition1,axiom,
    and(n0,X) = n0 ).

cnf(and_definition2,axiom,
    and(X,n0) = n0 ).

cnf(and_definition3,axiom,
    and(n1,X) = X ).

cnf(and_definition4,axiom,
    and(X,n1) = X ).

cnf(and_simplification1,axiom,
    and(X,X) = X ).

cnf(and_simplification2,axiom,
    and(X,and(X,Y)) = and(X,Y) ).

cnf(and_xor_simplification,axiom,
    and(X,xor(Y,Z)) = xor(and(X,Y),and(X,Z)) ).

cnf(not_to_xor,axiom,
    not(X) = xor(n1,X) ).

cnf(or_to_xor,axiom,
    or(X,Y) = xor(and(X,Y),xor(X,Y)) ).

%----Associativity and symmetry
cnf(xor_symmetry,negated_conjecture,
    xor(X,Y) = xor(Y,X) ).

cnf(xor_commutativity,negated_conjecture,
    xor(Y,xor(X,Z)) = xor(X,xor(Y,Z)) ).

cnf(and_symmetry,negated_conjecture,
    and(X,Y) = and(Y,X) ).

cnf(and_commutativity,negated_conjecture,
    and(Y,and(X,Z)) = and(X,and(Y,Z)) ).

%----Problem clauses
cnf(constructor1,negated_conjecture,
    o1 = n13 ).

cnf(constructor2,negated_conjecture,
    o2 = n17 ).

cnf(constructor3,negated_conjecture,
    o3 = n5 ).

cnf(constructor4,negated_conjecture,
    a1 = and(inv1,i2) ).

cnf(constructor5,negated_conjecture,
    n2 = and(inv1,i3) ).

cnf(constructor6,negated_conjecture,
    n3 = or(a1,n24) ).

cnf(constructor7,negated_conjecture,
    n4 = or(n15,n3) ).

cnf(constructor8,negated_conjecture,
    n5 = or(n4,n21) ).

cnf(constructor9,negated_conjecture,
    n6 = and(i1,i2) ).

cnf(constructor10,negated_conjecture,
    n7 = and(n6,i3) ).

cnf(constructor11,negated_conjecture,
    n8 = or(a1,n10) ).

cnf(constructor12,negated_conjecture,
    n9 = or(n8,n2) ).

cnf(constructor13,negated_conjecture,
    n10 = or(n24,n7) ).

cnf(constructor14,negated_conjecture,
    n11 = or(a1,n2) ).

cnf(constructor15,negated_conjecture,
    n12 = or(n11,n16) ).

cnf(constructor16,negated_conjecture,
    n13 = or(n12,n21) ).

cnf(constructor17,negated_conjecture,
    n14 = and(i2,i3) ).

cnf(constructor18,negated_conjecture,
    n15 = and(inv2,n6) ).

cnf(constructor19,negated_conjecture,
    n16 = and(n14,inv2) ).

cnf(constructor20,negated_conjecture,
    n17 = or(n18,n21) ).

cnf(constructor21,negated_conjecture,
    n18 = or(n19,n25) ).

cnf(constructor22,negated_conjecture,
    n19 = and(n23,inv2) ).

cnf(constructor23,negated_conjecture,
    n20 = or(n22,n14) ).

cnf(constructor24,negated_conjecture,
    n21 = and(inv1,inv2) ).

cnf(constructor25,negated_conjecture,
    n22 = or(n23,n6) ).

cnf(constructor26,negated_conjecture,
    n23 = and(i1,i3) ).

cnf(constructor27,negated_conjecture,
    n24 = and(i1,inv1) ).

cnf(constructor28,negated_conjecture,
    n25 = or(n2,n24) ).

cnf(constructor29,negated_conjecture,
    inv1 = not(n20) ).

cnf(constructor30,negated_conjecture,
    inv2 = not(n9) ).

cnf(output1,negated_conjecture,
    circuit(o1) ).

cnf(output2,negated_conjecture,
    circuit(o2) ).

cnf(output3,negated_conjecture,
    circuit(o3) ).

cnf(prove_inversion,negated_conjecture,
    ( ~ circuit(not(i1))
    | ~ circuit(not(i2))
    | ~ circuit(not(i3)) ) ).

%--------------------------------------------------------------------------