1

Define the binary operation of inclusive denial, denoted by $|$ on a Boolean algebra making $x|y = x' \vee y'$.

Show that the binary operations of disjunction $\vee$, conjunction $\wedge$, the unary complement $'$ and the nullary constants $0$ and $1$ are definable from $|$ alone.

I could conclude that $x' = x' \vee x' = x|x$, but what about the others? Perhaps I'm missing some extra hypothesis?

Hugo
  • 183

1 Answers1

2

  1. Let $x|y = x' \vee y'$.

  2. Unary complement $':\quad x' = x' \vee x' = x|x$

  3. Disjunction $\vee:\quad x \vee y = (x'|y')=(x|x)|(y|y)$

  4. Conjunction $\wedge:\quad x \wedge y = (x'\vee y')'=\bigl[(x'|x')|(y'|y')\bigr]'=(x|y)'=(x|y)|(x|y)$

  5. Constant $0:\quad0 = x\wedge x'=(x|x')|(x|x')=\bigl[x|(x|x)\bigr]\Bigl\lvert\bigl[x|(x|x)\bigr]$

  6. Constant $1:\quad 1=x\vee x'= x'' \vee x' = x' \mid x = (x \mid x) \mid x$

My thanks go to @amrsa for pointing out a simplification for the constant $1$.

Ricky
  • 3,148
  • 1
    A shorter version for 5 is: $$1 = x'' \vee x' = x' \mid x = (x \mid x) \mid x$$ and then reach the same conclusion as you did for the constant $0$ by using $0 = 1'$. – amrsa Sep 01 '23 at 14:16