4
$\begingroup$

Let’s consider algebras with the following axioms in addition to commutativity and associativity: $x \vee x=x$ $\neg \neg x = x$

Does the Huntington axiom ( $\neg (\neg x \vee y) \vee \neg (\neg x ∨ \neg y) = x$ ) follow from the axioms? If yes prove it by showing how the axioms entail it, if not, give an interpretation that contradicts it, but satisfies the axioms above together with the commutativity and associativity axioms.

This is a homework assignment for my AI class, but I have no idea where to start. Could you give me some pointers?

  • 0
    Why can you simply define $\neg x := x$? Is it because there was no definition provided yet (i.e. we only got comm, assoc, and the two written above)?2014-04-24

1 Answers 1

2

Based on the comments I think I have the solution now:

Let's define $\neg x = x$, that is consistent with $\neg \neg x = x$, and let $x \vee x$ be the logical AND operation, that's associative, commutative, and $x$ AND $x=x$ holds.

Now let's work with the Huntington axiom: $\neg (\neg x \vee y) \vee \neg (\neg x ∨ \neg y) = x$ Using $\neg x = x$ we get: $(x \vee y) \vee (x ∨ y) = x$ Then applying $x \vee x = x$ yields $(x \vee y) = x$

But for the logical AND operation if $x$ is true and $y$ is false $x$ AND $y$ is false, and that a contradicts with the result. So we found a counterexample, and that means that the Huntington axiom does not follow from the given axioms.