The elements of GF(2) may be identified with the two possible values of a bit and to the boolean values true and false.

[hongy...@gmail.com]

I noticed the following description here [1]:

```
The elements of GF(2) may be identified with the two possible values of a bit and to the boolean values true and false. It follows that GF(2) is fundamental and ubiquitous in computer science and its logical foundations.
```

I'm not sure if the phrasing "identified with the two possible values of a bit and to the boolean values true and false" is correct or not. More specifically, I think the following form should be used:

"... identified with the two possible values of a bit and
the boolean values true and false"

IMO, the "and to" can be changed to "and". Any hints/corrections will be highly appreciated.

[1] https://en.wikipedia.org/wiki/GF(2)

Regards,
HZ

[Peter T. Daniels]

With no idea of what it means, it would look better with "with ...
with" not "with ... to." Parallel items need to be parallel. Probably
you do need both "with"s.

[Peter Moylan]

>> The elements of GF(2) may be identified with the two possible
>> values of a bit and to the boolean values true and false. It
>> follows that GF(2) is fundamental and ubiquitous in computer
>> science and its logical foundations.

That looks very wrong to me. GF(2) is a field, and ordinary Boolean
algebra is not. I know that Wikipedia talks of Boolean algebras over
more than two elements, but those are even further removed from GF(2).

In conventional Boolean algebra, TRUE+TRUE = TRUE.
In GF(2), 1 + 1 = 0.

I guess you can turn Boolean algebra into a field if you take the two
operations as XOR and AND (i.e. leave inclusive OR out of the picture),
but that's not what most people think of as Boolean algebra.

Exercise for anyone interested in digital circuit design: implement an
inclusive OR function using only XOR and AND gates. Answer: it can't be
done. At the very least, you have to allow NOT gates as well.

(Well, OK, it can be done if you allow extra constant inputs, but it's a
hellishly inefficient way to implement a simple function.)

--
Peter Moylan Newcastle, NSW http://www.pmoylan.org

[Anders D. Nygaard]

Den 26-05-2022 kl. 11:07 skrev Peter Moylan:
> Exercise for anyone interested in digital circuit design: implement an
> inclusive OR function using only XOR and AND gates. Answer: it can't be
> done. At the very least, you have to allow NOT gates as well.

What am I missing when I claim that
a OR b == (a XOR b) XOR (a AND b) ?

/Anders, Denmark

[Richard Heathfield]

$ cat logic.c
#include <stdio.h>

int main(void)
{
int a, b;
int aorb;
int axorb;
int aandb;
int xorxorand;
int bugs = 0;

const char * truth[] =
{
"FALSE",
"TRUE"
};

printf("You are missing ");
for(a = 0; a < 2; a++)
{
for(b = 0; b < 2; b++)
{
aorb = a | b;
axorb = a ^ b;
aandb = a & b;
xorxorand = axorb ^ aandb;

if(aorb != xorxorand)
{
++bugs;
printf("a = %s, b = %s\n", truth[a], truth[b]);
}
}
}
if(!bugs)
{
printf("nothing.\n");
}
return 0;
}

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[Jerry Friedman]

I don't see that you're missing anything, so it seems OR is not
inXORable.

(However, I suspect that most computer scientists never give a
moment's thought to GF(2).)

--
Jerry Friedman

[Richard Heathfield]

On 26/05/2022 11:21 pm, Stefan Ram wrote:

> Richard Heathfield <r...@cpax.org.uk> writes:
>> printf("You are missing ");
>

> Or, in no more than 72 chars of Python 3.9:
>
> all((( x or y )==(( x!=y )!=( x and y )) for x in [0,1] for y in [0,1]))
>
> , which will output "True" if the expression
> ( x or y )==(( x!=y )!=( x and y ))
> evaluates to True for all values of x and y from the set {0,1}.

It didn't.

It also took five times as long to execute as my C version. Ho hum.

[Peter Moylan]

You got me, and I admit defeat. Apparently I'm not as good at
manipulating Boolean expressions as I used to be.

I still claim that the fact that a Boolean algebra with operators XOR
and AND is a field is interesting from the theoretical point of view,
but not very helpful in terms of practical applications of Boolean
algebra. Pretty much all of the electronics that uses Boolean algebra is
based on NAND and NOR operators.

I did once find an engineering use for GF(2). Some digital automata can
have their dynamic behaviour described by a state, where the state space
is vectors over GF(2). That hit me when I was working out an algorithm
for inverting the state equations of a dynamic system (where, almost
always, the state vectors are vectors over the reals), and it suddenly
hit me that the same procedure worked when the underlying scalar space
is any field at all.

There's a catch, though. A digital device is rarely linear.