User:H. H. P. M. P. Cole/Modulo 2

Modulo 2 is a meta-programming-language (?) created by Cole. The output of every syntactically-valid Modulo 2 program is a Boolean function.

Objective

To represent all possible Boolean functions using as simple of an alphabet and as intuitive a syntax as possible.

Symbols

Modulo 2 uses the following symbols:

( ) p ˈ 0 1 + ×

Syntax

A valid Modulo 2 program must satisfy the following conditions:

- It starts with either one of (, p, 0, or 1.

- It ends with either one of ), p, ', 0, or 1.

- The following ordered pairs of symbols are not allowed:

(), (ˈ, (+, (×, )(, )p, )ˈ, )0, )1, p(, pp, p0, p1, ˈ(, ˈp, ˈ0, ˈ1, +), +ˈ, ++, +×, ×), ×ˈ, ×+, ××, 0(, 0p, 0ˈ, 00, 01, 1(, 1p, 1ˈ, 10, 11

- There must be an equal number of ( and ) symbols.

Semantics

Variables are designated by p, p'...

The usual algebraic meaning of brackets with no character between them meaning the × operator does not hold. Rather, operators between expressions must be specified at all times.

Order of operations is always × then +. Both operators are given their meanings in modulo-2 arithmetic.

All possible small programs

Length-1

There are 3 valid length-1 programs.

p
0
1

Length-2

There is 1 valid length-2 program.

pˈ

Length-3

There are 22 valid length-3 programs.

(p)
(0)
(1)
pˈˈ
p+p
p+0
p+1
p×p
p×0
p×1
0+p
0+0
0+1
0×p
0×0
0×1
1+p
1+0
1+1
1×p
1×0
1×1

Length-4

There are 14 valid length-4 programs.

(pˈ)
pˈˈˈ
pˈ+p
pˈ+0
pˈ+1
pˈ×p
pˈ×0
pˈ×1
p+pˈ
p×pˈ
0+pˈ
0×pˈ
1+pˈ
1×pˈ

Longer programs

There are:

• 181 valid length-5 programs,
• 163 valid length-6 programs,
• 1614 valid length-7 programs, and
• 1840 valid length-8 programs,