TPTP Problem File: HWV003-3.p

View Solutions - Solve Problem

%--------------------------------------------------------------------------
% File     : HWV003-3 : TPTP v8.1.0. Released v2.7.0.
% Domain   : Hardware Verification
% Problem  : One bit Full Adder
% Version  : Especial.
% English  : Prove that the given implementation of a one-bit full adder
%            using only NAND gates is correct

% Refs     : [WO+92] Wos et al. (1992), Automated Reasoning: Introduction a
%          : [Bur]   Burris, Comments on Boolean Algebra
%          : [Bur98] Burris (1998), Logic for Mathematics and Computer Scie
%          : [Bou03] Boule (2003), Email to G. Sutcliffe
% Source   : [Bou03]
% Names    :

% Status   : Unsatisfiable
% Rating   : 0.00 v4.1.0, 0.20 v3.7.0, 0.25 v3.5.0, 0.00 v3.3.0, 0.33 v3.2.0, 0.00 v2.7.0
% Syntax   : Number of clauses     :   61 (   0 unt;  34 nHn;  61 RR)
%            Number of literals    :  152 (   0 equ;  71 neg)
%            Maximal clause size   :    3 (   2 avg)
%            Maximal term depth    :    0 (   0 avg)
%            Number of predicates  :   22 (  22 usr;  22 prp; 0-0 aty)
%            Number of functors    :    0 (   0 usr;   0 con; --- aty)
%            Number of variables   :    0 (   0 sgn)
% SPC      : CNF_UNS_PRP

% Comments : This is an alternate encoding of HWV003-1.p. By using
%            propositional logic, the problem is fully-decidable (as it
%            should be) and run-times are much quicker.
%--------------------------------------------------------------------------
%----a11 = NAND(A,B)
cnf(clause_1A,negated_conjecture,
    ( a11
    | a ) ).

cnf(clause_1B,negated_conjecture,
    ( a11
    | b ) ).

cnf(clause_1C,negated_conjecture,
    ( ~ a11
    | ~ a
    | ~ b ) ).

%----a12 = NAND(A,A11)
cnf(clause_2A,negated_conjecture,
    ( a12
    | a ) ).

cnf(clause_2B,negated_conjecture,
    ( a12
    | a11 ) ).

cnf(clause_2C,negated_conjecture,
    ( ~ a12
    | ~ a
    | ~ a11 ) ).

%----a13 = NAND(B,A11)
cnf(clause_3A,negated_conjecture,
    ( a13
    | b ) ).

cnf(clause_3B,negated_conjecture,
    ( a13
    | a11 ) ).

cnf(clause_3C,negated_conjecture,
    ( ~ a13
    | ~ b
    | ~ a11 ) ).

%----a14 = NAND(A12,A13)
cnf(clause_4A,negated_conjecture,
    ( a14
    | a12 ) ).

cnf(clause_4B,negated_conjecture,
    ( a14
    | a13 ) ).

cnf(clause_4C,negated_conjecture,
    ( ~ a14
    | ~ a12
    | ~ a13 ) ).

%----a15 = NAND(A14,CI)
cnf(clause_5A,negated_conjecture,
    ( a15
    | a14 ) ).

cnf(clause_5B,negated_conjecture,
    ( a15
    | cI ) ).

cnf(clause_5C,negated_conjecture,
    ( ~ a15
    | ~ a14
    | ~ cI ) ).

%----a16 = NAND(A14,A15)
cnf(clause_6A,negated_conjecture,
    ( a16
    | a14 ) ).

cnf(clause_6B,negated_conjecture,
    ( a16
    | a15 ) ).

cnf(clause_6C,negated_conjecture,
    ( ~ a16
    | ~ a14
    | ~ a15 ) ).

%----a17 = NAND(A15,CI)
cnf(clause_7A,negated_conjecture,
    ( a17
    | a15 ) ).

cnf(clause_7B,negated_conjecture,
    ( a17
    | cI ) ).

cnf(clause_7C,negated_conjecture,
    ( ~ a17
    | ~ a15
    | ~ cI ) ).

%----s1 = NAND(A16,A17)
cnf(clause_8A,negated_conjecture,
    ( s1
    | a16 ) ).

cnf(clause_8B,negated_conjecture,
    ( s1
    | a17 ) ).

cnf(clause_8C,negated_conjecture,
    ( ~ s1
    | ~ a16
    | ~ a17 ) ).

%----c1 = NAND(A15,A11)
cnf(clause_9A,negated_conjecture,
    ( c1
    | a15 ) ).

cnf(clause_9B,negated_conjecture,
    ( c1
    | a11 ) ).

cnf(clause_9C,negated_conjecture,
    ( ~ c1
    | ~ a15
    | ~ a11 ) ).

%----a21 = XOR(A,B)
cnf(clause_10A,negated_conjecture,
    ( a21
    | a
    | ~ b ) ).

cnf(clause_10B,negated_conjecture,
    ( a21
    | ~ a
    | b ) ).

cnf(clause_10C,negated_conjecture,
    ( ~ a21
    | a
    | b ) ).

cnf(clause_10D,negated_conjecture,
    ( ~ a21
    | ~ a
    | ~ b ) ).

%----a22 = AND(CI,A23)
cnf(clause_11A,negated_conjecture,
    ( ~ a22
    | cI ) ).

cnf(clause_11B,negated_conjecture,
    ( ~ a22
    | a23 ) ).

cnf(clause_11C,negated_conjecture,
    ( a22
    | ~ cI
    | ~ a23 ) ).

%----a23 = OR(A,B)
cnf(clause_12A,negated_conjecture,
    ( a23
    | ~ a ) ).

cnf(clause_12B,negated_conjecture,
    ( a23
    | ~ b ) ).

cnf(clause_12C,negated_conjecture,
    ( ~ a23
    | a
    | b ) ).

%----a24 = NOT(CI)
cnf(clause_13A,negated_conjecture,
    ( a24
    | cI ) ).

cnf(clause_13B,negated_conjecture,
    ( ~ a24
    | ~ cI ) ).

%----a25 = AND(A,B)
cnf(clause_14A,negated_conjecture,
    ( ~ a25
    | a ) ).

cnf(clause_14B,negated_conjecture,
    ( ~ a25
    | b ) ).

cnf(clause_14C,negated_conjecture,
    ( a25
    | ~ a
    | ~ b ) ).

%----a26 = AND(A24,A25)
cnf(clause_15A,negated_conjecture,
    ( ~ a26
    | a24 ) ).

cnf(clause_15B,negated_conjecture,
    ( ~ a26
    | a25 ) ).

cnf(clause_15C,negated_conjecture,
    ( a26
    | ~ a24
    | ~ a25 ) ).

%----s2 = XOR(CI,A21)
cnf(clause_16A,negated_conjecture,
    ( s2
    | cI
    | ~ a21 ) ).

cnf(clause_16B,negated_conjecture,
    ( s2
    | ~ cI
    | a21 ) ).

cnf(clause_16C,negated_conjecture,
    ( ~ s2
    | cI
    | a21 ) ).

cnf(clause_16D,negated_conjecture,
    ( ~ s2
    | ~ cI
    | ~ a21 ) ).

%----c2 = OR(A22,A26)
cnf(clause_17A,negated_conjecture,
    ( c2
    | ~ a22 ) ).

cnf(clause_17B,negated_conjecture,
    ( c2
    | ~ a26 ) ).

cnf(clause_17C,negated_conjecture,
    ( ~ c2
    | a22
    | a26 ) ).

%----conjline18 = XOR(S1,S2)  %(S1 = S2)
cnf(clause_18A,negated_conjecture,
    ( conjline18
    | s1
    | ~ s2 ) ).

cnf(clause_18B,negated_conjecture,
    ( conjline18
    | ~ s1
    | s2 ) ).

cnf(clause_18C,negated_conjecture,
    ( ~ conjline18
    | s1
    | s2 ) ).

cnf(clause_18D,negated_conjecture,
    ( ~ conjline18
    | ~ s1
    | ~ s2 ) ).

%----conjline19 = XOR(C1,C2)  %(C1 = C2)
cnf(clause_19A,negated_conjecture,
    ( conjline19
    | c1
    | ~ c2 ) ).

cnf(clause_19B,negated_conjecture,
    ( conjline19
    | ~ c1
    | c2 ) ).

cnf(clause_19C,negated_conjecture,
    ( ~ conjline19
    | c1
    | c2 ) ).

cnf(clause_19D,negated_conjecture,
    ( ~ conjline19
    | ~ c1
    | ~ c2 ) ).

cnf(clause_20,negated_conjecture,
    ( conjline18
    | conjline19 ) ).

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