## 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 ) ).

%--------------------------------------------------------------------------
```