How to define Xor in Coq and prove its properties -

-

this should easy question. i'm new coq.

i want define exclusive or in coq (which best of knowledge not predefined). important part allow multiple propositions (e.g. xor b c d).

i need 2 properties:

(xor a1 a2 ... an)/\~a1 -> xor a2... (xor a1 a2 ... an)/\a1 -> ~a2/\.../\~an

i'm having trouble defining function undefined number of variables. tried define hand two, three, 4 , 5 variables (that's how many need). proving properties pain , seems inefficient.

given second property, assume definition of exclusive or @ higher arities “exactly 1 of these propositions true” (and not “an odd number of these propositions true” or “at least 1 of these propositions true , @ least 1 false”, other possible generalizations).

this exclusive or not associative property. means can't define higher-arity xor xor(a1,…,an)=xor(a1,xor(a2,…)). need global definition, , means type constructor must take list of arguments (or other data structure, list obvious choice).

inductive xor : list prop -> prop := …

you have 2 reasonable choices: build definition of xor inductively first principles, or invoke list predicate. list predicate “there unique element in list matching predicate”. since standard list library not define predicate, , defining harder defining xor, we'll build xor inductively.

the argument list, let's break down cases:

  • xor of empty list false;
  • xor of list (cons l) true iff either of these 2 conditions met:
    • a true , none of elements of l true;
    • a false , 1 of elements of l true.

this means need define auxiliary predicate on lists of propositions, nand, characterizing lists of false propositions. there many possibilities here: fold /\ operator, induct hand, or call list predicate (again, not in standard list library). i'll induct hand, folding /\ reasonable choice.

require import list. inductive nand : list prop -> prop :=   | nand_nil : nand nil   | nand_cons : forall (a:prop) l, ~a -> nand l -> nand (a::l). inductive xor : list prop -> prop :=   | xor_t : forall (a:prop) l, -> nand l -> xor (a::l)   | xor_f : forall (a:prop) l, ~a -> xor l -> xor (a::l). hint constructors nand xor.

the properties want prove simple corollaries of inversion properties: given constructed type, break down possibilities (if have xor, it's either xor_t or xor_f). here's manual proof of first; second similar.

lemma xor_tail : forall l, xor (a::l) -> ~a -> xor l. proof.   intros. inversion_clear h.     contradiction.     assumption. qed.

another set of properties you're want equivalences between nand , built-in conjunction. example, here's proof nand (a::nil) equivalent ~a. proving nand (a::b::nil) equivalent ~a/\~b , on merely more of same. in forward direction, once more inversion property (analyse possible constructors of nand type). in backward direction, simple application of constructors.

lemma nand1 : forall a, nand (a::nil) <-> ~a. proof.   split; intros.     inversion_clear h. assumption.     constructor. assumption. constructor. qed.

you're need substitution , rearrangement properties @ point. here few key lemmas may want prove (these shouldn't difficult, induct on right stuff):

  • forall a1 b2 l, (a1<->a2) -> (xor (a1::l) <-> xor (a2::l))
  • forall k l1 l2, (xor l1 <-> xor l2) -> (xor (k++l1) <-> xor (k++l2))
  • forall k b l, xor (k++a::b::l) <-> xor (k::b::a::l)
  • forall k l m n, xor (k++l++m++n) <-> xor (k++m++l++n)

Comments

Post a Comment

Popular posts from this blog

c# - How to set Z index when using WPF DrawingContext? -

-
how set z-index drawing object when using drawingcontext.drawxxx() methods? the object drawn last have higher z index. can't change index of drawn objects. way draw in order. if using wpf (as placed tag), can use, example, canvas control. create shapes need like polyline obj = new polyline(); //... // ... set properties of obj and add them canvas uielementcollection: yourcanvasname.children.add(obj); //or yourcanvasname.children.insert(i, obj); first items of collection have higher z index. advantages in way: no need redraw on window changes, can anytime move objects , change order.
Read more

razor - Is this a bug in WebMatrix PageData? -

-
i think may have found bug in webmatrix's pagedata, not sure. concerns how pass data partial page calling page. in webmatrix documentation (tutorials, e.g. " 3 - creating consistent look ", , example code), pagedata recommended mechanism pass data between pages (e.g. content page layout page, or partial page). however have found not work other way, pass data partial page calling page. modifying or adding entries in pagedata in partial page, not seem calling page. cutting right down simplest possible example, in test page may have this: @{ pagedata["test"] = "initial entry"; } <p>before calling partial page, test value @pagedata["test"]</p> @renderpage("_testpartial.cshtml") <p>after returning calling page, test value @pagedata["test"]</p> and in _testpartial.cshtml page might have this: @{ pagedata["test"] = "modified entry"; } <p>in partial page...
Read more

visual c++ - Using relative values in array sorting ( asm ) -

-
i need sort through array , sort each individual row in array in ascending order. doesn't seem going (surprise!) keep getting hit 2 errors: a2101: cannot add 2 relocatable labels , a2026: constant expected here's sort, makes sense me, think i'm still trying implement high-lvl language techniqes assembly. there way around not being able use relative values? (the array 7 rows 9 columns, btw). mov cx, 7; cx = number of rows outer: ; outer loop walk through rows push cx mov cx, 9 mov row, cx ;rows middle: ; middle-loop walk through columns push cx sub cx, 1 ;cx = cx-1 mov column, cx ;columns inner: ;inner loop - compare , exchange column values cmp marray[row*9 + column], marray[row*9 + column+1] xchg marray[row*9 + column+1], marray[row*9 + column] ; compare , exchange values marray table inc column loop inner pop cx loop mid...
Read more