How to define Xor in Coq and prove its properties

Question

This should be an easy question. I'm new with Coq.

I want to define the exclusive or in Coq (which to the best of my knowledge is not predefined). The important part is to allow for multiple propositions (e.g. Xor A B C D).

I also need the two properties:

(Xor A1 A2 ... An)/\~A1 -> Xor A2... An
(Xor A1 A2 ... An)/\A1 -> ~A2/\.../\~An

I'm currently having trouble defining the function for an undefined number of variables. I tried to define it by hand for two, three, four and five variables (that's how many I need). But then proving the properties is a pain and seems very inefficient.

Answer 1

Given your second property, I assume that your definition of exclusive or at higher arities is “exactly one of these propositions is true” (and not “an odd number of these propositions is true” or “at least one of these propositions is true and at least one is false”, which are other possible generalizations).

This exclusive or is not an associative property. This means you can't just define higher-arity xor as xor(A1,…,An)=xor(A1,xor(A2,…)). You need a global definition, and this means that the type constructor must take a list of arguments (or some other data structure, but a list is the most obvious choice).

Inductive xor : list Prop -> Prop := …

You now have two reasonable choices: build your definition of xor inductively from first principles, or invoke a list predicate. The list predicate would be “there is a unique element in the list matching this predicate”. Since the standard list library does not define this predicate, and defining it is slightly harder than defining xor, we'll build xor inductively.

The argument is a list, so let's break down the cases:

• xor of an empty list is always false;
• xor of the list (cons A L) is true iff either of these two conditions is met:
  • A is true and none of the elements of L are true;
  • A is false and exactly one of the elements of L is true.

This means we need to define an auxiliary predicate on lists of propositions, nand, characterizing the lists of false propositions. There are many possibilities here: fold the /\ operator, induct by hand, or call a list predicate (again, not in the standard list library). I'll induct by hand, but folding /\ is another 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, A -> nand L -> xor (A::L)
  | xor_f : forall (A:Prop) L, ~A -> xor L -> xor (A::L).
Hint Constructors nand xor.

The properties you want to prove are simple corollaries of inversion properties: given a constructed type, break down the possibilities (if you have a xor, it's either a xor_t or a xor_f). Here's a manual proof of the first; the second is very similar.

Lemma xor_tail : forall A L, xor (A::L) -> ~A -> xor L.
Proof.
  intros. inversion_clear H.
    contradiction.
    assumption.
Qed.

Another set of properties you're likely to want is the equivalences between nand and the built-in conjunction. As an example, here's a proof that nand (A::nil) is equivalent to ~A. Proving that nand (A::B::nil) is equivalent to ~A/\~B and so on are merely more of the same. In the forward direction, this is once more an inversion property (analyse the possible constructors of the nand type). In the backward direction, this is a simple application of the constructors.

Lemma nand1 : forall A, nand (A::nil) <-> ~A.
Proof.
  split; intros.
    inversion_clear H. assumption.
    constructor. assumption. constructor.
Qed.

You're also likely to need substitution and rearrangement properties at some point. Here are a few key lemmas that you may want to prove (these shouldn't be very difficult, just induct on the 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 A 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)

Answer 2

Well, I suggest you start with Xor for 2 arguments and prove its properties.

Then if you want to generalize it you can define Xor taking a list of arguments -- you should be able to define it and prove its properties using your 2-argument Xor.

I could give some more details but I think it's more fun to do it on your own, let me know how it goes :).