%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Diagnosis of faults in logical circuits % % % % Version 2: Consistent fault assumption % % % % - and optionally correct-results-produced-in-correct-way assumption % % % % (c) 2005, Henning Christiansen % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % The file contains circuit definitions with diagnosis capabilities: % % halfadder/4, fulladder/5 % :- use_module(library(chr)). handler diagnosis. constraints perfect/2, defect/2, % applied for "not" perfect/3, defect/3. % applied for the others %%% Integrity constraints % - for the one "/2" versions defect(X,In) \ defect(X,In) <=> true. perfect(X,In) \ perfect(X,In) <=> true. defect(X,In) , perfect(X,In) <=> fail. % - for the "/3" versions defect(X,In1,In2) \ defect(X,In1,In2) <=> true. perfect(X,In1,In2) \ perfect(X,In1,In2) <=> true. defect(X,In1,In2) , perfect(X,In1,In2) <=> fail. disturbe(0,1). disturbe(1,0). not(0, 1). not(1, 0). and(0, 0, 0). and(0, 1, 0). and(1, 0, 0). and(1, 1, 1). xor(0, 0, 0). xor(0, 1, 1). xor(1, 0, 1). xor(1, 1, 0). or(0, 0, 0). or(0, 1, 1). or(1, 0, 1). or(1, 1, 1). not(A,X,ComponentId):- not(A,X), perfect(ComponentId,A). not(A,X,ComponentId):- not(A,Z), disturbe(Z,X), defect(ComponentId,A). and(A,B,X,ComponentId):- and(A,B,X), perfect(ComponentId,A,B). and(A,B,X,ComponentId):- and(A,B,Z), disturbe(Z,X), defect(ComponentId,A,B). or(A,B,X,ComponentId):- or(A,B,X), perfect(ComponentId,A,B). or(A,B,X,ComponentId):- or(A,B,Z), disturbe(Z,X), defect(ComponentId,A,B). xor(A,B,X,ComponentId):- xor(A,B,X), perfect(ComponentId,A,B). xor(A,B,X,ComponentId):- xor(A,B,Z), disturbe(Z,X), defect(ComponentId,A,B). % Original version of circuits without diagnosis halfadderOrig(A, B, Carry, Sum):- and(A, B, Carry), xor(A, B, Sum). fulladderOrig(Carryin, A, B, Carryout, Sum):- xor(A, B, X), and(A, B, Y), and(X, Carryin, Z), xor(Carryin, X, Sum), or(Y, Z, Carryout). % Version with diagnosis; notice identifier on each gate halfadder(A, B, Carry, Sum):- and(A, B, Carry,and0), xor(A, B, Sum,xor0). fulladder(Carryin, A, B, Carryout, Sum):- xor(A, B, X,xor1), and(A, B, Y,and1), and(X, Carryin, Z,and2), xor(Carryin, X, Sum,xor2), or(Y, Z, Carryout,or1). /********************************************** TEST RUNS: | ?- halfadder(1,1,1,1). perfect(and0,1,1), defect(xor0,1,1) ? ; no | ?- halfadder(1,1,0,1), halfadder(1,0,0,1). defect(and0,1,1), defect(xor0,1,1), perfect(and0,1,0), perfect(xor0,1,0) ? ; no | ?- halfadder(1,1,1,0), halfadder(1,1,1,1), halfadder(0,0,1,0). no This "no" can be interpreted in two ways: - the consistent-fault-assumption is two strong for explaining this behaviour, or - the observations are wrong. | ?- fulladder(1,0,1,1,1). 8 solutions See the end of this for explanation of the use of "fail", etc. | ?- fulladder(1,0,1,1,1), fulladder(1,1,1,0,0), fulladder(0,0,0,0,1), write(*), fail. 144 solutions Extending example: first line consists of correct samples - notice that this information reduces the number of solutions | ?- fulladder(1,1,0,1,0), fulladder(0,1,0,0,1), fulladder(0,0,1,0,1), fulladder(1,0,1,1,1), fulladder(1,1,1,0,0), fulladder(0,0,0,0,1), write(*), fail. 48 solutions This still high number of solutions is caused by combinations of mutually compensation faults - including in the processing of the correct samples Here is another example, also with observations of correct behaviour in the first line, and faulty behaviour in the second: | ?- fulladder(0,1,1,1,0), fulladder(0,1,0,0,1), fulladder(0,0,1,0,1), fulladder(1,0,1,1,1), fulladder(1,1,1,0,0), fulladder(0,0,0,0,1), write(*),fail. 72 solutions. The following cut (!) put in after the correct observations implements the correct-results-produced-in-correct-way assumption | ?- fulladder(0,1,1,1,0), fulladder(0,1,0,0,1), fulladder(0,0,1,0,1), !, fulladder(1,0,1,1,1), fulladder(1,1,1,0,0), fulladder(0,0,0,0,1). <15 * perfect> defect(xor2,1,1), defect(and2,0,1), defect(xor2,1,0), defect(or1,1,1), defect(xor1,0,0) ? ; no Only one solution :) --- To see no. of solution without having to type a lot semicolons, use this pattern: | ?- QUERY, write(*), fail. Explanation: Read from inside, "write(*)" will print out a star when a solution is found; the "fail" provokes backtracking, so this will force Prolog to go try out all solution. NB: Since all solutions continue into fail, Prolog will answer "No", but the number of stars indicates the number of possible solutions. **************************************/