A generalization of the Shaffer Stroke for n-valued logic

---

NOTE: This transcription was contributed by Martin P.M. van der Burgt, who has devised a process for producing transcripts automatically. Although its markup is incomplete, we believe it serves a useful purpose by virtue of its searchability and its accessibility to text-reading software. It will be replaced by a fully marked-up version when time permits. —HR

---

A generalization of the Shaffer Stroke for n-valued logic.

by C.S.Scholten

For binary variables —i.e. ranging over {0, 1}— x and y the “Shaffer Stroke” —a1ias “alternative denial” or “nand”— is the operator —or binary function— denoted by

x | y

and (usually) defined as

	1 - x.y .
As 1 - x.y = (x.y + 1) mod 2
and x.y = min(x, y)

an alternative definition is:

x | y = (min(x, y) + 1) mod 2 .

It is well-known [1] that any binary function of k binary arguments can be expressed using the Shaffer Stroke as the only primitive operator.

In the following we regard n-ary variables —i.e. ranging over {0, 1, ..., n-1}— and shall demonstrate that any n-ary function of k n-ary arguments can be expressed, using as the only operator the generalization

x | y = (min(x, y) + 1) mod n .

In the following we shall use the notation

suc(x) = (x + 1) mod n .

in terms of which we can rewrite:

x | y = suc(min(x, y)) .

Theorem 1. The function suc —as defined above— is expressible.

Proof. suc(x) = x | x

Theorem 2. The function pred —defined by pred(x) = (x - 1) mod n— is expressible.

Proof. pred(x) = sucn-1(x)

Theorem 3. The function min is expressible.

Proof. min(x, y) = pred(x | y)

Note. Because

min(x, y, z) = min(min(x, y), z) etc.

also the minimum of more than two arguments is expressible. (End of note.)

Theorem 4. For any n-ary constant c the discriminator function d_c(x),

given by dc(x) = n - 1 for x = c
	= 0 for x ≠ c

is expressible.

Proof. Because
	sucn-c(x) = 0 for x = c
		= 0 for x ≠ c

is expressible.

we have min(1, sucn-c(x)) = 0 for x = c
	= 1 for x ≠ c ,

so that d^c(x) = pred(min(1, suc^n-c(x))) .

Theorem 5. For any n-ary constant c the weighten discriminator function w_c(x, y), given by

	wc(x, y) = y for x = c
		= n - 1 for x f c

is expressible.

Proof. min(dc(x), suc(y)) = suc(y) for x = c
	= 0 for x ≠ c

and because pred(suc(y)) = y , we find

wc(x, y) = pred(min(dc(x), suc(y))) .

Theorem 6. The selector function, defined by

sel(x, y0, y1. ... , yn-1) = yi for x = i

is expressible.

Proof. sel(x, y0, y1, ... , yn-1) =
	min(w0(x, y0). w1(x, y1). . wn-1(x, yn_1)) .

The final induction from 2 to k arguments is straightforward.

[1] Shaffer. H.M., A set of five independent postulates for Boolean algebras, with applications to logical constants. Trans.Amer.Math.Soc. vol 14, pp,481-488

---

Transcribed by Martin P.M. van der Burgt
Last revision 2014-11-15 .