backtracking - Find a boolean circuit with prolog -

-

the problem following : considering 3 inputs a,b,c, find boolean circuit and,or , not gates such output not(a), not(b), not(c) using @ 2 not gates.

i find circuit prolog. idea compute predicate "accessible" takes function , says if exists circuit computes f.

i have following predicates : 

not([],[]). not([h|t],[g|s]) :- g #=# 1-h, not(t,s).  or([],[],[]). or([0|t],[0|s],[0|r]) :- or(t,s,r). or([1|t],[0|s],[1|r]) :- or(t,s,r). or([1|t],[1|s],[1|r]) :- or(t,s,r). or([0|t],[1|s],[1|r]) :- or(t,s,r).  and([],[],[]). and([1|t],[1|s],[1|r]) :- and(t,s,r). and([0|t],[1|s],[0|r]) :- and(t,s,r). and([1|t],[0|s],[0|r]) :- and(t,s,r). and([0|t],[0|s],[0|r]) :- and(t,s,r).  accessible(_,_,0) :- !,fail. accessible([0,1,0,1,0,1,0,1],[12],_) :- !. accessible([0,0,1,1,0,0,1,1],[11],_) :- !. accessible([0,0,0,0,1,1,1,1],[10],_) :- !. accessible(f,l,c) :- cc c-1, or(g,h,f), accessible(g,m,cc), accessible(h,n,cc), l=[0, [m,n]]. accessible(f,l,c) :- cc c-1, and(g,h,f), accessible(g,m,cc), accessible(h,n,cc), l=[1,[m,n]]. accessible(f,l,c) :- cc c-1,  not(f,x), accessible(x,m,cc), l=[2,m].

i compute function xor between 11,12 try following goal : accessible([0,1,1,0,0,1,1,0], x, 4).

but prolog runs while before getting answer. i'd know how improve program in order make faster.

p.s. how print string without ascii codes gnu prolog ?

you searching on arbitrary formed boolean expressions, , asking boolean algebra on bit arrays generated following bit arrays: 

   01010101      00110011

just recall normal forms of boolean algebra. example conjunctive normal form. conjunctive normal form reads follows:

    /\ clause_i

whereby each clause has form:

    \/ literal_i

and each literal has either 1 of following forms:

    variable     ~ variable

just take 2 variables generator bit arrays. reduces search space somehow. 2 variables there 4 different clauses. makes 2^4 different normal forms.

further, if have goal find normal form results in bit array, such specified:

 01100110

you can further prune search considering value lower bound.

bye


Comments

Post a Comment

Popular posts from this blog

c++ - OpenCV Error: Assertion failed <scn == 3 ::scn == 4> in unknown function, -

-
i read alot other solution still confused should mine... #include <opencv2/objdetect/objdetect.hpp> #include <opencv2/highgui/highgui.hpp> #include <opencv2/imgproc/imgproc.hpp> #include <iostream> #include <stdio.h> using namespace std; using namespace cv; int main(int argc, const char** argv) { //create cascade classifier object used face detection cascadeclassifier face_cascade; //use haarcascade_frontalface_alt.xml library face_cascade.load("haarcascade_frontalface_alt.xml"); //setup video capture device , link first capture device videocapture capturedevice; capturedevice.open(0); //setup image files used in capture process mat captureframe; mat grayscaleframe; //create window present results namedwindow("outputcapture", 1); //create loop capture , find faces while (true) { //capture new image frame capturedevice >> captureframe; ...
Read more

php - render data via PDO::FETCH_FUNC vs loop -

-
i've been using 2 methods render data. the first one: function name($id,$name){ return '<div id="'.$id.'">'.$name.'</div>'; } echo implode($pdo->query("select id,name user")->fetchall(pdo::fetch_func,'name')); the second one: $users = $pdo->query("select id,name user")->fetchall(pdo::fetch_obj); foreach($users $user){ echo name($user->id,$user->name); } i don't understand how pdo::fetch_func works. tried figure out. however, not well-documented. could please explain fetch mode? , also, 1 performs better? thank you. both methods wrong , have learn how use templates , how separate business logic presentation logic. $users = $pdo->query("select id,name user")->fetchall(pdo::fetch_obj); tpl::assign('users', $users); is code business logic part. then in template <?php foreach $users $row): ?> <div id="<?=$...
Read more

The canvas has been tainted by cross-origin data in chrome only -

-
uncaught securityerror: failed execute 'getimagedata' on 'canvasrenderingcontext2d': canvas has been tainted cross-origin data i getting above error in chrome. code(following) works fine in mozilla. have not corss domain issue. why above error in chrome? var wheel_canvas, wheel_context, can_w, can_h, wheel_grd; var large_radius = 160; var small_radius = 120; var wheel_canvas = document.getelementbyid('wheel_canvas'); var wheel_context = wheel_canvas.getcontext('2d'); var can_w = $(wheel_canvas).width(); var can_h = $(wheel_canvas).height(); var centerx = can_w / 2, centery = can_h / 2; var wheel_grd = null; test('#ff0000'); function test(hex) { $('#clrpicker').css({'left': 210, 'top': 210 }); inverted = hexbw(hex); $('#color_val_show').val(hex); current_color_hex_val_selected = hex; $('#color_val_show').css({'color':inverted,'background':hex}); fillgradient...
Read more