Is Boolean algebra a finite field?
Newberry
William Elliot
> Is Boolean algebra a finite field?
>
No.
Every element has a complement but
not every element has a reciprocal.
herbzet
Newberry wrote:
>
> Is Boolean algebra a finite field?
Boolean algebra has infinite models as well as finite models,
e.g. the power set of any set is a Boolean algebra under
conjunction, disjunction, and relative complementation.
I don't think a Boolean algebra can be construed as a field
either, at least in any simple and obvious way.
If we interpret the addition operator as disjunction (a + b)
and the multiplicative operator as conjunction (a * b) then,
letting '0' be'false' and '1' be 'true', we have the identities
a + 0 = a and a * 1 = a but we don't have for each element a an
inverse -a such that a + -a = 0 and an inverse a' such that
a * a' = 1, as the field axioms dictate.
(I'm not saying that a more devious mind than mine couldn't come
up with an interpretation that makes a Boolean algebra a field
also!)
--
hz
herbzet
herbzet wrote:
> Newberry wrote:
> >
> > Is Boolean algebra a finite field?
>
> Boolean algebra has infinite models as well as finite models,
> e.g. the power set of any set is a Boolean algebra under
> conjunction, disjunction, and relative complementation.
Oops, I mean set intersection and union respectively (as well
as relative complementation).
My mind wandered!
--
hz
Brian Chandler
> Is Boolean algebra a finite field?
(I didn't understand the other answer, but anyway...)
No. "Boolean algebra" (at least according to Wikipedia) consists of a
(finite) set of "Truth values", typically {T, F}, and "logical
operations, numbering at least three, viz AND, OR, NOT.
A finite field consists of a finite set of entities, and *two*
operations, typically called "+" and "x".
So they are different. But "Boolean algebra under AND and XOR" is a
finite set of entities and two operations, and you only need a piece
of A7 paper to write it all down, so why not check for yourself if it
meets the full set of field axioms.
Does that answer your question?
Brian Chandler
Aatu Koskensilta
> No. "Boolean algebra" (at least according to Wikipedia) consists of a
> (finite) set of "Truth values", typically {T, F}, and "logical
> operations, numbering at least three, viz AND, OR, NOT.
This is an idiosyncratic definition of Boolean algebra -- or, rather,
sounds more like a description, not of a class of mathematical
structures, but of Boolean algerba as a field of mathematics, the
algebraic study of propositional logic. The more usual definition has it
that a Boolean algebra is a "complemented distributive bounded lattice",
or something to that effect, i.e. a partially ordered set such that
infima and suprema of any two elements exist, the distributivity holds
for join and meet, there is a least element and a greatest element, and
every element has a complement.
--
Aatu Koskensilta (aatu.kos...@uta.fi)
"Wovon mann nicht sprechen kann, dar�ber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
herbzet
Here is a definition of a Boolean algebra; the postulates
are independent (Huntington 1904):
A class of elements B closed under two binary operations
(+) and (*) (where a * b will be written ab) is a Boolean
algebra if and only if the following postulates hold:
P1. The operations are commutative.
P2. Each operation is distributive over the other.
P3. There exist in B distinct identity elements 0 and 1
relative to the operations (+) and (*), respectively.
P4. For every a in B there exists an element a' in B
such that
a + a' = 1 and aa' = 0.
(Taken from a book by John Eldon Whitesitt.)
--
hz
Jan Burse
> Brian Chandler <imagin...@despammed.com> writes:
>
>> No. "Boolean algebra" (at least according to Wikipedia) consists of a
>> (finite) set of "Truth values", typically {T, F}, and "logical
>> operations, numbering at least three, viz AND, OR, NOT.
>
> This is an idiosyncratic definition of Boolean algebra -- or, rather,
> sounds more like a description, not of a class of mathematical
> structures, but of Boolean algerba as a field of mathematics, the
> algebraic study of propositional logic. The more usual definition has it
> that a Boolean algebra is a "complemented distributive bounded lattice",
> or something to that effect, i.e. a partially ordered set such that
> infima and suprema of any two elements exist, the distributivity holds
> for join and meet, there is a least element and a greatest element, and
> every element has a complement.
>
How do you define truth in a boolean algebra with more than
two elements? Assume we have a boolean algebra R, which has
more than two elements and a formula A, there are the following
options:
1) A is true in R, iff R(A)>0
2) A is true in R, iff R(A)=1
3) What else?
I think for the option 2), this will inevitable
lead to a corresponding 2-valued boolean algebra R' as
follows:
Construct an ideal via the truth condition you are
using. Make it prime P, it will be maximal, and thus
R' := R/P will isomorphic to the 2-valued field.
Bye
Jan Burse
Oops, I think it works for R(A) != 0, i.e. for a notion
of "satisfiability" and not for a notion of "tautology"
(which would be R(A) = 1).
We will then have an ideal I with R(A) !=0 iff A not in I.
And from this the rest.
Bye
Aatu Koskensilta
> How do you define truth in a boolean algebra with more than two
> elements?
Being equal to 1.
David C. Ullrich
wrote:
>Aatu Koskensilta schrieb:
>> Brian Chandler <imagin...@despammed.com> writes:
>>
>>> No. "Boolean algebra" (at least according to Wikipedia) consists of a
>>> (finite) set of "Truth values", typically {T, F}, and "logical
>>> operations, numbering at least three, viz AND, OR, NOT.
>>
>> This is an idiosyncratic definition of Boolean algebra -- or, rather,
>> sounds more like a description, not of a class of mathematical
>> structures, but of Boolean algerba as a field of mathematics, the
>> algebraic study of propositional logic. The more usual definition has it
>> that a Boolean algebra is a "complemented distributive bounded lattice",
>> or something to that effect, i.e. a partially ordered set such that
>> infima and suprema of any two elements exist, the distributivity holds
>> for join and meet, there is a least element and a greatest element, and
>> every element has a complement.
>>
>
>How do you define truth in a boolean algebra with more than
>two elements?
You don't. It's not clear to me how one constructs an ideal
"according to a truth condition" as you suggest below,
but yes, it's the elements of the quotient of a Boolean
algebra by a maximal ideal that are true or false.
Hmm. That's a (possibly correct) answer to the question
"how do you define which elements of a Boolean algebra
are true?", which is what I thought your question meant.
Looking below, it seems you may have meant something else.
>Assume we have a boolean algebra R, which has
>more than two elements and a formula A, there are the following
>options:
>
> 1) A is true in R, iff R(A)>0
For that matter it's not clear to me what you mean by R(A)
here. Unless you mean that A is an FOL wff in the language
of Boolean algebra and you're talking about the truth value
of A in the structure R (presumably together with an
assignment of elements of R to the free variables in A).
In that case the definition is the same as for any structure
in FOL - it has nothing to do with the 0 and 1 in the
Boolean algebra per se.
For example, the formula x v x = x is true in any Boolean
algebra. But the just means it follows from the axioms;
its truth value is the ordinary True in logic, not the element
1 of the Boolean algebra in question.
> 2) A is true in R, iff R(A)=1
> 3) What else?
>
>I think for the option 2), this will inevitable
>lead to a corresponding 2-valued boolean algebra R' as
>follows:
>
> Construct an ideal via the truth condition you are
> using. Make it prime P, it will be maximal, and thus
> R' := R/P will isomorphic to the 2-valued field.
>
>Bye
David C. Ullrich
"Understanding Godel isn't about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.)
Jon Slaughter
"Newberry" <newbe...@gmail.com> wrote in message
news:6bb0586c-f328-41bc...@x29g2000prf.googlegroups.com...
> Is Boolean algebra a finite field?
or is equivalent to max(a,b) and is equivalent to min(a,b) where a, b are in
{0,1} and 'and' is also equal to 1 - max(a,b).
It should be obvious by several methods there is no unique inverses
0 1
0 0 1
1 1 1
0 1
0 0 0
1 0 1
But for xor we do have a inverse(this is why it's used in
encoding/encryption)
we have
0 1
0 0 1
1 1 0
and maybe we can have someting like xnd which gives
0 1
0 1 0
1 0 1
of course xnd = neg xor and not all that useful and there isn't anyway to
recover or and and from them.
Newberry
Newberry
Here is a definition from Wikipedia
Additive and multiplicative inverses
For every a in F, there exists an element -a in F, such that a + (-a)
= 0. Similarly, for any a in F other than 0, there exists an element a
-1 in F, such that a · a-1 = 1. (The elements a + (-b) and a · b-1 are
also denoted a - b and a/b, respectively.) In other words, subtraction
and division operations exist.
Doesn't Boolean algebra satisfy this?
Newberry
What about boolean algebra with only two elements?
Newberry
> "Newberry" <newberr...@gmail.com> wrote in message
>
> news:6bb0586c-f328-41bc...@x29g2000prf.googlegroups.com...
>
> > Is Boolean algebra a finite field?
>
> or is equivalent to max(a,b) and is equivalent to min(a,b) where a, b are in
> {0,1} and 'and' is also equal to 1 - max(a,b).
>
> It should be obvious by several methods there is no unique inverses
Here is a definition from Wikipedia
Additive and multiplicative inverses
For every a in F, there exists an element -a in F, such that a + (-a)
= 0. Similarly, for any a in F other than 0, there exists an element a
-1 in F, such that a · a-1 = 1. (The elements a + (-b) and a · b-1 are
also denoted a - b and a/b, respectively.) In other words, subtraction
and division operations exist.
It says "there exists an element -a." It does not say that -a must be
unique.
Jon Slaughter
On Jun 13, 4:29 am, "Jon Slaughter" <Jon_Slaugh...@Hotmail.com> wrote:
> "Newberry" <newberr...@gmail.com> wrote in message
>
> news:6bb0586c-f328-41bc...@x29g2000prf.googlegroups.com...
>
> > Is Boolean algebra a finite field?
>
> or is equivalent to max(a,b) and is equivalent to min(a,b) where a, b are
> in
> {0,1} and 'and' is also equal to 1 - max(a,b).
>
> It should be obvious by several methods there is no unique inverses
Here is a definition from Wikipedia
Additive and multiplicative inverses
For every a in F, there exists an element -a in F, such that a + (-a)
= 0. Similarly, for any a in F other than 0, there exists an element a
-1 in F, such that a � a-1 = 1. (The elements a + (-b) and a � b-1 are
also denoted a - b and a/b, respectively.) In other words, subtraction
and division operations exist.
It says "there exists an element -a." It does not say that -a must be
unique.
---
If the element exists it must be unique. This is a basic proof in group
theory 101.
Suppose you have two inverses a' and a'' to a.
By the definition of inverses, a'a = e = a''a. Right multiplying by a' one
has a'aa' = a''aa' or a' = a'' by cancellation(using associativity).
Aatu Koskensilta
> It says "there exists an element -a." It does not say that -a must be
> unique.
What Wikipedia says or leaves unsaid is immaterial. That -a is unique
follows from the field axioms.
Jussi Piitulainen
> It says "there exists an element -a." It does not say that -a must
> be unique.
You can prove that it is. Just repeat these steps:
(1) Assume s and t are additive inverses of a.
(2) Then a + s = 0 = a + t.
(3) Then s + (a + s) = s + (a + t).
(4) Then (s + a) + s = (s + a) + t.
(5) Then 0 + s = 0 + t.
(6) Then s = t.
Its uniqueness, incidentally, is why the inverse can be notated -a
without ambiguity.
Brian Chandler
It might help if you clarified just what your question was. I
interpreted "Boolean algebra" as meaning simply "the algebra of truth
values and operations on them" which is what one of the Wikipedia
entries refers to. One reason for thinking this is that the other
meaning (and WP entry) is for *a* Boolean algebra, which is one of a
class of abstract structures; if you had meant this, you might have
been expected to write "Is a Boolean algebra a finite field?" --
except that this is an odd thing to ask, rather than simply "Is a
Boolean algebra the same as a finite field?" (to which the answer is
fairly obviously "No".
Anyway, perhaps you did mean the variety (without an article)
described here:
http://en.wikipedia.org/wiki/Boolean_algebra_(introduction)
In this case my answer stands. Obviously, since a finite field is a
structure with two operators, general "truth value arithmetic" can't
be a finite field as such, because it has more operators. But write
out the tables for AND(&) and XOR(x) on T and F (should look OK in
fixed font):
& F T x F T
F F F F F T
T F T T T F
Compare with the tables for the field of order 2.
HTH
Brian Chandler
Chip Eastham
No, not necessarily. Division is not required for a
Boolean algebra.
A basic example of a (finite) Boolean algebra is the
algebra of subsets of a (finite) set S. Addition &
subtraction are the same thing, symmetric difference
of sets. Multiplication is set intersection. Zero
is the empty set and "one" is the universal set.
It seems intuitively clear that the only unit (an
invertible multiplicative element) is "one" (the
universal set) in these examples, e.g. that a set
intersection cannot be "undone" by another (unless
the set intersection did "nothing" to begin with).
However a field extension of Z/2Z would be both a
field and a Boolean algebra, if that helps.
regards, chip
Jan Burse
> Is Boolean algebra a finite field?
I would say yes in the two valued case,
with + defined as xor.
The additive inverse is identity function.
a+(-a) = a+a = a xor a = 0
The multiplicative inverse is identify function.
a*(a^-1) = a*a = a and a = 1 for a!=0.
The complement is neither the additive nor the multiplicative
inverse, it can be viewed as the shift by 1:
~a = 1 + a = 1 xor a
In the multivalued case (take the variable to
range over sets), with + define as symmetric
difference we have:
The additive inverse is again the identity function:
a + (-a) = a + a = a symdiff a = (a \ a) u (a \ a) = 0
But a multiplicative inverse does not exist, there-
fore in the general case:
A boolean algebra is only a boolean ring, but not a field.
Best Regards
Jan Burse
> therefore in the general case:
>
> A boolean algebra is only a boolean ring, but not a field.
>
> Best Regards
Or as William Elliot has already put it:
> No.
> Every element has a complement but
> not every element has a reciprocal.
Yes in the multi-valued case the complement is
again a shift, but neither the multiplicative
nor the additive inverse. Namely:
~a = U + a = U simdiff a = (U \ a) u (a \ U) = U \ a u {} = U \ a
Where U is the top element.
Bye
Jan Burse
And there is still the infinite case.
Bye
herbzet
Newberry wrote:
> herbzet wrote:
> > Newberry wrote:
> >
> > > Is Boolean algebra a finite field?
> >
> > Boolean algebra has infinite models as well as finite models,
> > e.g. the power set of any set is a Boolean algebra under
> > conjunction, disjunction, and relative complementation.
I'm glad you responded, so I can *finally* get this right
(third try):
The power set of any set is a Boolean algebra under
set intersection and set union.
> > I don't think a Boolean algebra can be construed as a field
> > either, at least in any simple and obvious way.
> >
> > If we interpret the addition operator as disjunction (a + b)
> > and the multiplicative operator as conjunction (a * b) then,
> > letting '0' be'false' and '1' be 'true', we have the identities
> > a + 0 = a and a * 1 = a but we don't have for each element a an
> > inverse -a such that a + -a = 0
That's correct.
> > and an inverse a' such that a * a' = 1
That's incorrect; in this interpretation a is its own multiplicative
inverse: (a * a') = (a * a) = a = 1 for a =/= 0.
> > as the field axioms dictate.
> >
> > (I'm not saying that a more devious mind than mine couldn't come
> > �up with an interpretation that makes a Boolean algebra a field
> > �also!)
>
> What about boolean algebra with only two elements?
As has been pointed out by others, a set of two elements, call
them 0 and 1, is a Boolean algebra under conjunction (*) and
disjunction (+), and is a field under conjunction (*) and
exclusive disjunction (xor).
--
hz
Bill Dubuque
The question doesn't make any sense as posed since
you don't specify what the operations are supposed
to be on the finite field. Any finite set of the
same cardinality as a finite field can be given
the structure of a finite field - that is trivial.
Every boolean algebra is, in a certain sense, equivalent
to a boolean ring (i.e. a ring where x^2 = x) where
product = intersection, sum = symmetric difference
i.e. xy = x/\y, x+y = (x'/\y)\/(x/\y')
But x^2 = x => x = 0 or x = 1 in a field. Hence
the only such field is the field of two elements F_2.
--Bill Dubuque
Marshall
> The more usual definition has it
> that a Boolean algebra is a "complemented distributive bounded lattice",
> or something to that effect, i.e. a partially ordered set such that
> infima and suprema of any two elements exist, the distributivity holds
> for join and meet, there is a least element and a greatest element, and
> every element has a complement.
Which is the more usual definition is a matter of convention,
I suppose. But the above, while pleasingly algebraic, assumes
a specific signature, despite the fact that others are possible.
What seems most significant to me about the various signatures
of boolean algebras is that they completely axiomatize "the"
two-element model. This immediately leads me to wonder if
"the" three element model has ever been completely axiomatized.
Anyone know?
Here's a smallish but complete set of axioms for boolean
algebra, with the and/or/not signature (^/2 v/2 -/1).
x ^ 1 = x.
x v 0 = x.
x ^ -x = 0.
x v -x = 1.
x ^ y = y ^ x.
x ^ (y v z) = (x ^ y) v (x ^ z).
x v (y ^ z) = (x v y) ^ (x v z).
Its little fillip of asymmetry amuses me.
Marshall
Jon Slaughter
"Marshall" <marshal...@gmail.com> wrote in message
news:d8461a38-231b-40e1...@c19g2000prh.googlegroups.com...
----
I remember reading somewhere a long time ago about someone creating a
ternary based computer. It wasn't any better than a binary computer and more
complex. Since you can do everything with binary and it is more
efficient(atleast as far as we know) to do this electrically(much easier to
determine if a state is on/off rather than something else).
cbr...@cbrownsystems.com
> herbzet wrote:
> Here is a definition of a Boolean algebra; the postulates
> are independent (Huntington 1904):
>
> A class of elements B closed under two binary operations
> (+) and (*) (where a * b will be written ab) is a Boolean
> algebra if and only if the following postulates hold:
>
> P1. The operations are commutative.
> P2. Each operation is distributive over the other.
> P3. There exist in B distinct identity elements 0 and 1
> relative to the operations (+) and (*), respectively.
> P4. For every a in B there exists an element a' in B
> such that
>
> a + a' = 1 and aa' = 0.
>
> (Taken from a book by John Eldon Whitesitt.)
I'm surprised not to see explicit postulation of associativity:
a(bc) = (ab)c
a+(b+c) = (a+b)+c
Are these theorems given the above?
Cheers - Chas
herbzet
Marshall wrote:
>
> On Jun 13, 1:28�am, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:
> > The more usual definition has it
> > that a Boolean algebra is a "complemented distributive bounded lattice",
> > or something to that effect, i.e. a partially ordered set such that
> > infima and suprema of any two elements exist, the distributivity holds
> > for join and meet, there is a least element and a greatest element, and
> > every element has a complement.
>
> Which is the more usual definition is a matter of convention,
> I suppose. But the above, while pleasingly algebraic, assumes
> a specific signature, despite the fact that others are possible.
>
> What seems most significant to me about the various signatures
> of boolean algebras is that they completely axiomatize "the"
> two-element model. This immediately leads me to wonder if
> "the" three element model has ever been completely axiomatized.
> Anyone know?
There is no three element model. Every finite boolean
algebra has 2^n elements, for positive n in N (Huntington 1904).
Can't remember how the proof goes at the moment.
> Here's a smallish but complete set of axioms for boolean
> algebra, with the and/or/not signature (^/2 v/2 -/1).
> x ^ 1 = x.
> x v 0 = x.
>
> x ^ -x = 0.
> x v -x = 1.
>
> x ^ y = y ^ x.
>
> x ^ (y v z) = (x ^ y) v (x ^ z).
> x v (y ^ z) = (x v y) ^ (x v z).
>
> Its little fillip of asymmetry amuses me.
Absolutely!
(These are the same four postulates I posted before,
more or less: news:4A3363D1...@gmail.com )
--
hz
Marshall
Marshall
>
> I'm glad you responded, so I can *finally* get this right
> (third try):
>
> The power set of any set is a Boolean algebra under
> set intersection and set union.
And complement.
Marshall
Marshall
wrote:
>
> I remember reading somewhere a long time ago about someone creating a
> ternary based computer. It wasn't any better than a binary computer and more
> complex. Since you can do everything with binary and it is more
> efficient(atleast as far as we know) to do this electrically(much easier to
> determine if a state is on/off rather than something else).
Bleah! I wasn't proposing it as a hardware design; the idea turns
my stomach. I don't like three-valued logic in programming
languages, either; see any of a million essays on how awful
SQL null is.
Marshall
Marshall
> Marshall wrote:
>
> > On Jun 13, 1:28 am, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:
> > > The more usual definition has it
> > > that a Boolean algebra is a "complemented distributive bounded lattice",
> > > or something to that effect, i.e. a partially ordered set such that
> > > infima and suprema of any two elements exist, the distributivity holds
> > > for join and meet, there is a least element and a greatest element, and
> > > every element has a complement.
>
> > Which is the more usual definition is a matter of convention,
> > I suppose. But the above, while pleasingly algebraic, assumes
> > a specific signature, despite the fact that others are possible.
>
> > What seems most significant to me about the various signatures
> > of boolean algebras is that they completely axiomatize "the"
> > two-element model. This immediately leads me to wonder if
> > "the" three element model has ever been completely axiomatized.
> > Anyone know?
>
> There is no three element model.
Hmmm, you have misunderstood me. I didn't mean "three element
model of boolean algebra"; I meant "three element model."
We can consider (two-element) boolean algebra as a
description of "the" (the quotes mean "up to isomorphism!")
complete axiomatization of "the" two-element model:
Start with two elements. We can construct four unary
functions and sixteen binary ones. We can also get away
with fewer such functions and still be functionally complete:
and/or/not, just nand, etc.
We might try the same thing for a three element model.
What operations would we need to be functionally
complete? What might the axiom sets look like?
(I am interested in considering the smallest cases;
this is how I came up with the somewhat-regrettable
"x=y" theory; it does the above for "the" one-element
model.)
> (These are the same four postulates I posted before,
> more or less:news:4A3363D1...@gmail.com)
Yeah, I saw that right after I posted.
Marshall
Newberry
>
> - Show quoted text -
OK, based on this:
"For every a in F, there exists an element -a in F, such that a + (-a)
= 0"
If a = 1 there is no -a such that 1 + (-a) = 0.
So what kind of algebra is Boolean algebra? Is it a category on its
own?
Newberry
This is the answer I was looking for:
Based on this:
"For every a in F, there exists an element -a in F, such that a + (-a)
= 0"
If a = 1 there is no -a such that 1 + (-a) = 0.
I got somehow mixed up, that is why I asked the question.
herbzet
"cbr...@cbrownsystems.com" wrote:
Yeah -- for the trickery involved try this URL:
It's theorem 5 of chapter 2, page 30.
Theorem 1 is on page 28.
"Boolean Algebra and Its Applications"
by John Eldon Whitesitt -- at google books.
--
hz
herbzet
Marshall wrote:
> herbzet wrote:
> >
> > I'm glad you responded, so I can *finally* get this right
> > (third try):
> >
> > The power set of any set is a Boolean algebra under
> > set intersection and set union.
>
> And complement.
Your axioms use an operation of complementation.
My postulates don't -- they just say that for
every element a there is an element b such that
a + b = 1 and a * b = 0.
It remains a fact that the powerset of every (non-empty, that's
four times) set S is a Boolean algebra under union and intersection,
since such an element b obviously exists for each a in P(S).
Does anyone allow a trivial Boolean algebra of one object? In that
case we'll have to have 0 = 1.
I think some people allow trivial Boolean rings.
--
hz
herbzet
Marshall wrote:
> herbzet wrote:
> > Marshall wrote:
> > Aatu Koskensilta wrote:
You want a set of axioms that can only be satisfied
by a three-element model?
> What operations would we need to be functionally
> complete? What might the axiom sets look like?
>
> (I am interested in considering the smallest cases;
> this is how I came up with the somewhat-regrettable
> "x=y" theory;
Lol!
> it does the above for "the" one-element model.)
>
> > (These are the same four postulates I posted before,
> > �more or less: news:4A3363D1...@gmail.com )
>
> Yeah, I saw that right after I posted.
--
hz
Marshall
> Marshall wrote:
> > herbzet wrote:
>
> > > I'm glad you responded, so I can *finally* get this right
> > > (third try):
>
> > > The power set of any set is a Boolean algebra under
> > > set intersection and set union.
>
> > And complement.
>
> Your axioms use an operation of complementation.
> My postulates don't -- they just say that for
> every element a there is an element b such that
>
> a + b = 1 and a * b = 0.
D'oh! You are absolutely right; my mistake.
I plead ... uh, insanity. No, twinkies! Mom!
herbzet is looking at me!
Marshall
herbzet
Marshall wrote:
> Here's a smallish but complete set of axioms for boolean
> algebra, with the and/or/not signature (^/2 v/2 -/1).
>
> x ^ 1 = x.
> x v 0 = x.
>
> x ^ -x = 0.
> x v -x = 1.
>
> x ^ y = y ^ x.
>
> x ^ (y v z) = (x ^ y) v (x ^ z).
> x v (y ^ z) = (x v y) ^ (x v z).
Are you sure we don't need x v y = y ^ x ?
Hm, since each pair of formula above are dual pairs
(swap '^' and 'v', and '0' and '1') I wonder if we
can get away with just one formula from each pair ...
--
hz
Marshall
Not exactly.
In the two-element case, I start with the model, and
I get some set of operators, and some set of axioms
that describe those operators. Done a certain way,
I have completely described "the" two-element
model. However the resulting theory also has
four element models. (And others.) (Those
higher cardinality models are necessarily not
completely described by the theory, but the
theory nonetheless is satisfied by those models.)
Now, start with the three element model.
1) What are some sets of operators that will
be functionally complete over this model?
(In the two-element case, some answers are
{and, or, not} and {nor}.)
2) For each of those sets of operators, what
set of axioms completely describes them?
(Has this work been done? I haven't been
able to find it.)
The resulting answers might or might not
also have, say, nine element models, but
I'm OK with that; I just want answers to
1 and 2. I have them for 1 element and
2 element models, so now I'm naturally
asking about 3 element models. Once I
have that, guess what I want next? :-)
And no, I don't have that for four element
models, because even though the boolean
algebra has four element models, boolean
algebras don't fully characterize four element
models; they are not functionally complete
over four elements.
It occurs to me that if T is a theory that
is functionally complete on a model M of
cardinality m, and T is also a theory of
model N of cardinality n where n > m,
then T is not functionally complete on N.
I bet that's a theorem somewhere with
some famous mathematician and/or
logician's name all over it. If not, dibs.
Marshall
PS. There are millions of famous people,
so there are probably millions of famous
logicians, but not Quine, because Quine
was not a logician.
PPS. If you don't get the joke of the PS,
just ignore it.
herbzet
Marshall wrote:
I win! I WIN!
BOO-YAH, sucker!
--
hz
Aatu Koskensilta
> I win! I WIN!
>
> BOO-YAH, sucker!
This is, I believe, classic "bully" behaviour.
--
Aatu Koskensilta (aatu.kos...@uta.fi)
"Wovon mann nicht sprechen kann, dar�ber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
Newberry
Is it a really cool book? I have been looking for a good reference on
Boolean algebra. It seems this books treats propositional logic as
well as switching circuits.
Marshall
> Marshall wrote:
> > Here's a smallish but complete set of axioms for boolean
> > algebra, with the and/or/not signature (^/2 v/2 -/1).
>
> > x ^ 1 = x.
> > x v 0 = x.
>
> > x ^ -x = 0.
> > x v -x = 1.
>
> > x ^ y = y ^ x.
>
> > x ^ (y v z) = (x ^ y) v (x ^ z).
> > x v (y ^ z) = (x v y) ^ (x v z).
>
> Are you sure we don't need x v y = y ^ x ?
[You meant to say "Are you sure we don't need x v y = y v x ?"]
Yes. Although it is of course a theorem. Alternatively,
we can include the commutativity of 'or' as an axiom
and take the commutativity of 'and' as a theorem.
That's the amusing fillip of asymmetry. Are you
not entertained?
http://www.youtube.com/watch?v=rbg5AAm2_XM
> Hm, since each pair of formula above are dual pairs
> (swap '^' and 'v', and '0' and '1') I wonder if we
> can get away with just one formula from each pair ...
Alas, no. If we omit any of the seven we don't have
a basis any more.
----------------
At the complete other end of the spectrum, we
can get the whole issue completely solved with
just this:
(((x v y)' v z)' v (x v (z' v (z v u)')')')' = z
for the signature {or, not}. (That is, the above
is a complete axiomatization of the boolean
algebra.)
Or again:
(x | ((y | x) | x)) | (y | (z | x)) = y
for the signature {nand}.
Any equational axiomatization of the boolean algebra
must have at least one equation of three variables.
I think it might still be an open question whether there exist
{or, not} axiomatizations with three variables, or with
"size" smaller than the above one, which is 22.
(Counting operators, including equals, and variables,
but not parentheses.)
Starting with the "--------" the results are all from
the paper "Short Single Axioms for the Boolean Algebra"
by McCune et al. (The earlier stuff I figgered out
m'self.) Bill McCune is one cool cat.
Marshall
herbzet
Aatu Koskensilta wrote:
> herbzet writes:
>
> > I win! I WIN!
> >
> > BOO-YAH, sucker!
>
> This is, I believe, classic "bully" behaviour.
YES! YES! YES!
I'm in with the in crowd!
--
hz
herbzet
Um, maybe google for three-valued logic, models of?
I think Tom Hanks is a logician.
--
hz
herbzet
Newberry wrote:
Let's put it this way -- when I read it a long time ago, it didn't
make my head hurt too much.
I liked it.
Suggest you preview it at the above URL. Check out the user reviews.
--
hz
Chip Eastham
Hi, Newberry:
You seem to confuse additive and multiplicative
inverses. Algebras are rings; as such there is
always an additive inverse. Boolean algebras
are special in that each element is its own
additive inverse. In particular 1 + 1 = 0.
But your question was whether a Boolean algebra
is necessarily "a finite field". This is false
on two accounts. Trivially a Boolean algebra
need not be finite; the example of a power set
of S, described in my earlier post, is finite
if and only if S is finite.
But let's assume you meant to ask whether a
finite Boolean algebra is necessarily a field.
[After all finiteness does help in some ways,
such as Wedderburn's theorem that a finite
division ring is a field.] The answer is no,
again with examples in which the only unit
of a Boolean algebra happens to be 1. In a
field every nonzero element would be a unit.
> So what kind of algebra is Boolean algebra?
> Is it a category on its own?
An algebra is generally defined as a ring
with a vector space structure with respect
to a field, which may be viewed if helpful
as a subring. Thus a Boolean algebra is
exactly an algebra over Z/2Z.
regards, chip
Marshall
>
> > (Has this work been done? I haven't been
> > able to find it.)
>
> Um, maybe google for three-valued logic, models of?
Aw, geeze, Google? I was hoping someone would
just tell me the answer. Better yet, tell me where I
can buy a pill I can swallow that will make it so
I know the answer.
Come to think of it, taking a pill is too much work.
More seriously, I have googled the question in the
past and come up dry. I don't think I know the right
terms to search for (I believe I've tried the ones you
mention) and/or this question isn't generally interesting
enough that anyone besides me cares. I'll just have
to derive it myself; so much easier and educational.
> > PS. There are millions of famous people,
> > so there are probably millions of famous
> > logicians, but not Quine, because Quine
> > was not a logician.
>
> I think Tom Hanks is a logician.
And do not forget that fraction of an electron
in Tom Hanks's spleen holds to Objectivism.
Marshall
PS. "Instant gratification takes too long."
-- C. Fischer
Jan Burse
> Um, maybe google for three-valued logic, models of?
Here is a proof that a boolean algebra cannot have a
three-valued model. Such a model would consist of
the elements {0, x, 1}. So we have naturally:
1!=0
1!=x
x!=0
Since a boolean algebra has a complement, we have
an element y=~x. And since the model is 3-valued
we have either y=1, y=x or y=0. By double negation
we have also ~y=x.
Check y=1:
~y=0!=x, so cannot be.
Check y=0:
~y=1!=x, so cannot be.
Check y=x:
~y=~x=x.
So question is whether ~x=x is possible. Recall the
ring, we have ~x=u+x, so question is whether 1+x=x
is possible. Recall again the ring, add x on both
sides and we have, 1+x+x=1+0=x+x=0, so cannot be.
Q.E.D.
Jan Burse
> herbzet schrieb:
>
>> Um, maybe google for three-valued logic, models of?
>
> Here is a proof that a boolean algebra cannot have a
> three-valued model.
Three-valued logic is not classical, what is the same
as to say it is not based on a boolean algebra.
Maybe on a distribute lattice, but not on a
boolean algebra.
Bye
Jan Burse
> So question is whether ~x=x is possible. Recall the
> ring, we have ~x=u+x, so question is whether 1+x=x
> is possible. Recall again the ring, add x on both
> sides and we have, 1+x+x=1+0=x+x=0, so cannot be.
> Q.E.D.
Kleenes 3-valued logic K3, has exactly such a complement,
such that ~x=x.
Newberry
What on earth are you talking about?? In a Boolean algebra + os OR not
XOR.
> But your question was whether a Boolean algebra
> is necessarily "a finite field". This is false
> on two accounts. Trivially a Boolean algebra
> need not be finite; the example of a power set
> of S, described in my earlier post, is finite
> if and only if S is finite.
>
> But let's assume you meant to ask whether a
> finite Boolean algebra is necessarily a field.
> [After all finiteness does help in some ways,
> such as Wedderburn's theorem that a finite
> division ring is a field.] The answer is no,
> again with examples in which the only unit
> of a Boolean algebra happens to be 1. In a
> field every nonzero element would be a unit.
>
> > So what kind of algebra is Boolean algebra?
> > Is it a category on its own?
>
> An algebra is generally defined as a ring
> with a vector space structure with respect
> to a field, which may be viewed if helpful
> as a subring. Thus a Boolean algebra is
> exactly an algebra over Z/2Z.
>
> regards, chip- Hide quoted text -
>
> - Show quoted text -
Let me rephrase my question: is Boolean algebra a field?
Newberry
Three-valued logic can certainly exist and
1+x+x = 1
1+0 = 1
x+x=x
Chip Eastham
[snip much repetition of basic question and answer]
I think I'm beginning to understand the root of the
confusion here. You asked if a Boolean algebra is
a finite field. I assumed you were thinking in terms
of the Boolean algebra being a ring extension of Z/2Z,
which is one way of defining Boolean algebras that is
consistent with the usual meaning of "algebra" in
ring theory.
> What on earth are you talking about?? In a Boolean
> algebra + os OR not XOR.
Stop and think. We should at least agree that Z/2Z
is both a Boolean algebra and a field. What is 1+1
in Z/2Z? Is it 1 OR 1? [Hint: no.] In fact for
the "standard" example of a Boolean algebra I gave
twice already, the complete family of subsets of
some set S (aka power set of S), addition is XOR
(aka the symmetric difference of two sets).
You may prefer to define a Boolean algebra in terms
of AND, OR, and NOT, the logical operators. But it
would still not be correct to identify OR with an
addition operator for a ring. The error in trying
to make OR into an addition operator is that OR
does not have elementwise inverses for nonzero
elements.
> Let me rephrase my question: is Boolean algebra a field?
Let me repeat my answer. Not all Boolean algebras
are fields. Those that are fields are precisely
the field extensions of Z/2Z (all of which are
indeed Boolean algebras). But being a field is
really quite a special case, since as discussed
before, the only multiplicative inverse in the
Boolean algebra example given by subsets of S
is "1" (which is concretely the universal set S
itself in this example).
Are we at least clear on what we disagree about?
I'm saying there are infinitely many Boolean
algebras which are not fields (even if we restrict
consideration to finite Boolean algebras). Take
a finite set S with more than one element. Its
power set is a Boolean algebra with respect to
addition = symmetric difference of sets (XOR)
and multiplication = intersection of sets (AND).
regards, chip
galathaea
> On Jun 13, 3:52 pm, herbzet <herb...@gmail.com> wrote:
>
>
>
> > > (Has this work been done? I haven't been
> > > able to find it.)
>
> > Um, maybe google for three-valued logic, models of?
>
> Aw, geeze, Google? I was hoping someone would
> just tell me the answer. Better yet, tell me where I
> can buy a pill I can swallow that will make it so
> I know the answer.
>
> Come to think of it, taking a pill is too much work.
>
> More seriously, I have googled the question in the
> past and come up dry. I don't think I know the right
> terms to search for (I believe I've tried the ones you
> mention) and/or this question isn't generally interesting
> enough that anyone besides me cares. I'll just have
> to derive it myself; so much easier and educational.
when you get to n-valued logics
there is a more complex classification theory
two big starting points for a study would be
lukasiewicz
and post
jan lukasiewickz
from the lvov-warsaw school
was one of the first
to systematically study these logics
and their various interpretations
around the same time
emil post derived logical implication rules
for n-valued logics
from functional interpretations
some possible hits
"lukasiewicz algebra"
"post algebras"
http://en.wikipedia.org/wiki/%C5%81ukasiewicz_logic
http://en.wikipedia.org/wiki/Multi-valued_logic
there are a number of interpretations of three-valued logic
including implication with quantum observables
and descriptive theories of ignorance, meaning, and paradox
> > > PS. There are millions of famous people,
> > > so there are probably millions of famous
> > > logicians, but not Quine, because Quine
> > > was not a logician.
>
> > I think Tom Hanks is a logician.
>
> And do not forget that fraction of an electron
> in Tom Hanks's spleen holds to Objectivism.
there are no fractions of electrons
leptons are atomic units of entity
that hold only one opinion at a time
it is said that opinion
is usually an ethical evaluation of sam-a-el
in relation to the universal problem of good and bad
but i forget whether it was electron or positron
who held the pro sam-a-el position
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
galathaea: prankster, fablist, magician, liar
Brian Chandler
> On Jun 13, 8:00 am, Brian Chandler <imaginator...@despammed.com>
> wrote:
> > Newberry wrote:
> > > On Jun 13, 1:13 am, Brian Chandler <imaginator...@despammed.com>
> > > wrote:
> > > > Newberry wrote:
> > > > > Is Boolean algebra a finite field?
> > > > No. "Boolean algebra" (at least according to Wikipedia) consists of a
> > > > (finite) set of "Truth values", typically {T, F}, and "logical
> > > > operations, numbering at least three, viz AND, OR, NOT.
<snip>
> > ... the tables for AND(&) and XOR(x) on T and F (should look OK in
> > fixed font):
> >
> > & F T x F T
> > F F F F F T
> > T F T T T F
> >
> > Compare with the tables for the field of order 2.
> This is the answer I was looking for:
Good!
> Based on this:
>
> "For every a in F, there exists an element -a in F, such that a + (-a)
> = 0"
>
> If a = 1 there is no -a such that 1 + (-a) = 0.
Yes there is (in the above context), because "F" is the 0 of the
field, "T" is the 1 of the field, "x" (XOR) is the + of the field, and
"&" is the * of the field. So translating to canonical terminology:
> "For every a in F, there exists an element -a in F, such that a + (-a)
> = 0"
Means (remembering that "F" is now "False", not "Field") for any
(either) of {F, T}, there is an inverse under x (XOR) -- and of course
everything is its own inverse under XOR.
Thus:
If a = T, T x T = F, so -T = T
> I got somehow mixed up, that is why I asked the question.
>
> So what kind of algebra is Boolean algebra? Is it a category on its
> own?
Ouch! Say that and someone will start ranting about category theory.
Like all other noun phrases in mathematics, "Boolean algebra" is
rather ambiguous. The meaning I took from your question was the more
elementary one simply meaning "arithmetic with truth values". But
there is another meaning, which *usually* puts an indefinite article
-- "a Boolean algebra" -- which refers to the structure of a power set
with union and intersect. This is not a field.
Brian Chandler
Newberry
My original question was about Boolean algebras defined in terms of
AND, OR (+), NOT (~). I did not say anything about identifying OR with
Newberry
So where did xor come from?
> This is not a field.
So what is it?
> Brian Chandler
Chip Eastham
> My original question was about Boolean algebras defined in terms of
> AND, OR (+), NOT (~). I did not say anything about identifying OR with
> an addition operator for a ring.
But you did. You asked if a Boolean algebra is a finite field.
Fields are rings. Look back at your posts.
Boolean OR is a binary operation that satisfies some but not all
of the axioms for + in a field (or ring), namely OR is associative
and commutative (as well as mutually distributive with respect to
the AND operation). Also OR has an identity element, False or
as we often say, Boolean zero.
But that is not enough to define a field (or ring). Addition must
have an inverse for each element. OR does not allow that. The
simplest Boolean algebra is an example, {True,False} or {1,0}, as
you prefer. While (0 OR 0) = 0, there is no value X such that
(1 OR X) = 0.
However this can be fixed! The binary operation that does have
all the properties we require for (ring or field) addition is
the symmetric difference (aka exclusive OR):
X + Y = (X AND NOT(Y)) OR (Y AND NOT(X))
With this definition for "addition" it turns out 0 is still the
identity, and each element is its own "additive inverse".
X + Y = (X AND NOT(X)) OR (X AND NOT(X)) = 0
regard, chip
Musatov
As it turns out the solution to the P Versus NP propblem is another
problem:
http://groups.google.com/group/sci.math/search?group=sci.math&q=musat...
Sorted by relevance Sort by date
1 result for musat.
Permutation Problem Why not just use random permutations? There are
well-known fast algorithms for
that. If you generated, say 1000 permutations per second for 2 weeks,
you would
process 1209600000 permutations out of a total of about 3.47 x
10^1166
so your
probability of a repetition musat be minute. Derek Holt.
May 23 2003 by ma...@mimosa.csv.warwick.ac.uk - 14 messages - 10
authors
http://groups.google.com/group/sci.math/search?group=sci.math&q=musat...
Natural numbers [was: Diagonal wanderings...] Theorem lt_s: forall
np:nat , n< p ...http://www.ncc.up.pt/~nam/aulas/0506/
t_coq/exemplos/pred.v - Similar pages Yes, this was all part of
technique first
pioneered by Musatov when he proved P==NP. On May 22, 11:17 pm, David
Bernier <
david...@videotron.ca> wrote: Edward Nelson, the formalist and
ultrafinitist,
On Jun 13, 11:54 pm, Musatov <marty.musa...@gmail.com> wrote:
> On Jun 13, 11:29 pm, Musatov <marty.musa...@gmail.com> wrote:
>
>
>
>
>
> > Natural numbers [was: Diagonal wanderings...] Theorem lt_s: for all
> > np:nat , n< p
>
> >http://www.ncc.up.pt/~nam/aulas/0506/t_coq/exemplos/pred.v
>
> > Part of technique when he proved P==NP. On May 22, 11:17 pm, DavidBernier <david...@videotron.ca> wrote: Edward Nelson, the formalist
>
> > and ultrafinitist.
>
> > Mechanical Witness:http://mathforum.org/kb/message.jspa?messageID=6751446&tstart=0-Hide
> > quoted text -
>
> > Here is the isomorphism:
> > Re: P=NP (proof)
> > I recently read about this problem and how it is
> > (according to Tim
> > Gowers, who I believe) the most important
> > problem in combinatorics
> > today. But I am used to being able to
> > immediately apprehend problems
> > in combinatorics. Is there actually a simple
> > formulation of the P=NP
> > question as purely regarding finite sets,
> > without any mention of
> > complexity classes and such?
>
> > Considering that P and NP are complexity classes,
> > it's hard to imagine
> > a formulation of the question without any mention
> > of complexity classes.
> > But here goes.
>
> > I take it you know what a graph is, and what it
> > means for two (finite)
> > graphs to be isomorphic. The graph isomorphism
> > problem asks you
> > to determine whether two given graphs are
> > isomorphic. In theory,
> > there is no difficulty in solving this problem;
> > you just look at each
> > map from the one vertex set to the other in turn
> > until either you find
> > one that's an isomorphism or you exhaust the set
> > of maps without
> > finding an isomorphism. In practice, this takes
> > too long; if each graph
> > has n vertices then there are n-factorial maps to
> > look at (counting just
> > those that are one-one), and n-factorial is big.
>
> > On the other hand, if someone shows you an
> > alleged isomorphism,
> > you can quickly verify or refute her allegation;
> > at worst, you have to
> > check about n^2 edges, and n^2 is small.
>
> > So graph isomorphism is easy to verify; the P =
> > NP question is
> > whether graph isomorphism is easy to solve. That
> > is, is there a way
> > to solve graph isomorphism that, instead of
> > requiring n-factorial
> > amount of work, requires only n^2, or n^3, or
> > even n^1000,
> > which is still tiny compared to n-factorial, for
> > large n.
>
> > Perhaps I'm mistaken and there has been a recent
> > development but I thought it wasn't known if
> > graph isomorphism is an NP complete problem.
>
> > Subgraph isomorphism is known to be though.
>
> > You're probably right about graph isomorphism, and I
> > simply
> > misremembered what I thought I had learned about it.
> > You're
> > certainly right about subgraph isomorphism, which for
> > the
> > record is the following problem; given two graphs, G
> > and H,
> determine whether G has a subgraph isomorphic to H.
Natural numbers [was: Diagonal wanderings...] Theorem lt_s: for all
np:nat , n< p
http://www.ncc.up.pt/~nam/aulas/0506/t_coq/exemplos/pred.v
Part of technique when he proved P==NP. On May 22, 11:17 pm,
DavidBernier <david...@videotron.ca> wrote: Edward Nelson, the
formalist
and ultrafinitist.
Mechanical Witness:http://mathforum.org/kb/message.jspa?
messageID=6751446&tstart=0-Hide
Here is the isomorphism:
Re: P=NP (proof)
I recently read about this problem and how it is
(according to Tim
Gowers, who I believe) the most important
problem in combinatorics
today. But I am used to being able to
immediately apprehend problems
in combinatorics. Is there actually a simple
formulation of the P=NP
question as purely regarding finite sets,
without any mention of
complexity classes and such?
Considering that P and NP are complexity classes,
it's hard to imagine
a formulation of the question without any mention
of complexity classes.
But here goes.
I take it you know what a graph is, and what it
means for two (finite)
graphs to be isomorphic. The graph isomorphism
problem asks you
to determine whether two given graphs are
isomorphic. In theory,
there is no difficulty in solving this problem;
you just look at each
map from the one vertex set to the other in turn
until either you find
one that's an isomorphism or you exhaust the set
of maps without
finding an isomorphism. In practice, this takes
too long; if each graph
has n vertices then there are n-factorial maps to
look at (counting just
those that are one-one), and n-factorial is big.
On the other hand, if someone shows you an
alleged isomorphism,
you can quickly verify or refute her allegation;
at worst, you have to
check about n^2 edges, and n^2 is small.
So graph isomorphism is easy to verify; the P =
NP question is
whether graph isomorphism is easy to solve. That
is, is there a way
to solve graph isomorphism that, instead of
requiring n-factorial
amount of work, requires only n^2, or n^3, or
even n^1000,
which is still tiny compared to n-factorial, for
large n.
Perhaps I'm mistaken and there has been a recent
development but I thought it wasn't known if
graph isomorphism is an NP complete problem.
Subgraph isomorphism is known to be though.
You're probably right about graph isomorphism, and I
simply
misremembered what I thought I had learned about it.
You're
certainly right about subgraph isomorphism, which for
the
record is the following problem; given two graphs, G
and H,
determine whether G has a subgraph isomorphic to H.
William Elliot
> On Jun 12, 10:02 pm, William Elliot <ma...@rdrop.remove.com> wrote:
>>> Is Boolean algebra a finite field?
>>
>> No.
>> not every element has a reciprocal.
>
> Here is a definition from Wikipedia
> Additive and multiplicative inverses
What does a # a-1 mean? The notation for multiplicative inverse
is a^-1 and not a - 1 = a + (-1).
> also denoted a - b and a/b, respectively.) In other words, subtraction
> and division operations exist.
>
> Doesn't Boolean algebra satisfy this?
No. Let a' be the complement of a,
a + b is union or join of a and b,
ab the intersection or meet of a and b.
Given a Boolean algebra with three elements, 0,a,1,
there is no x with ax = 1 even though a /= 0, for we
would have a = a1 = a(1 + x) = a1 + ax = a + 1 = 1.
OTOH, a Boolean algebra of two elements is a field.
A Boolean algebra can be converted to a ring by
defining a new ++ with a ++ b = ab' + a'b,
and keeping ab as is.
Jan Burse
> Three-valued logic can certainly exist and
> 1+x+x = 1
> 1+0 = 1
> x+x=x
No, it cannot. A finite boolean algebra has
2^n elements. Because it is isomorphic to an
n copies product of the 2-valued boolean alegbra.
And x+x=x is only the case for x=0. But if
everything amounts to 1 and 0, than your
boolean algebra has not 3 elements, but only 2.
Please show me your third element!
Newberry
OK, let me ask you this then:
Does Z/2Z behave like xor, and, not?
Does "xor, and, not" give you the ability to define all the
combinatorial functions?
Can xor be defined for the algebra of sets (0 = empty, 1 = universal
etc.) or for multi-valued Boolean algebras?
Are you saying that 2-valued Boolean algebra is a field and
multivalued algebras are not fields?
If Boolean algebra (in general) is not a field then what is it?
Newberry
The third element has been defined by Lukasiwicz. I could dig up the
tables. But let us consider the general case of fuzzy logic where the
values are in the interval <0,1>.
a or B =def max(a,b)
a and b =def min(a,b)
not a = def 1-a
Then take a subset of the values S = {0, 0.5, 1). 0.5 is you third
element. Then
0+0=0, 0+0.5 = 0.5, 0+1 = 1, 0.5 + 1 = 1
0*0 = 0, 0.* 0.5 = 0, 0*1 = 0, 0.5*0.5 = 0.5, 1*1 = 1
~0=1, ~0.5 = 0.5, ~1 = 0
Newberry
OK, let me ask you this then:
Does ++, ., ' give you the ability to define all the combinatorial
functions?
Are you saying that 2-valued Boolean algebra is a field (or can be
massaged into a field) and multivalued Boolean algebras are not
Chip Eastham
If by combinatorial functions you mean Boolean
operations, then yes:
1) Z/2Z (aka {True = 1, False = 0}) is a Boolean algebra
2) NOT together with AND will define all Boolean operations
3) XOR for an algebra of sets is the symmetric difference
(as previously defined in terms of AND/OR/NOT, see above)
> Are you saying that 2-valued Boolean algebra is a field and
> multivalued algebras are not fields?
I'm saying that Z/2Z and all of its field extensions are
both Boolean algebras and fields. The algebra of sets
for S = {a,b} is not a field, at least not with respect
to an interpretation in which multiplication is AND.
That's again because existence of multiplicative inverses
fails (although we do have a multiplicative identity,
always for Boolean algebras, since X AND 1 = X).
My point in discussion Boolean algebras as algebras (in
the sense of commutative ring theory) is to clarify how
close we come to having a field.
> If Boolean algebra (in general) is not a field then what is it?
A Boolean algebra is always a ring extension of Z/2Z.
Google for Boolean ring and you'll see the construction
of addition as symmetric difference is a standard one.
regards, chip
cbr...@cbrownsystems.com
Thanks. Looks like I'll have to pick up the book - google doesn't
allow me to go to the indicated pages. Or I can just chew on it a bit
myself (the proof, not the book!).
Cheers - Chas
Jan Burse
> The third element has been defined by Lukasiwicz.
But Lukasiwicz Logic is not based on Boolean Algebra.
What ever 3-valued logic you take, it is not based
on Boolean Algebra, or a Boolean Lattic. It is maybe
based on some other lattice.
You lousy fuck. Why don't you get it. A boolean algebra
can never have a carrier of 3 elements. I just proofed
it, and everybody knows it. So conclusion is when you
step over something with 3 elements, that is not a boolean
algebra.
Bye
Jan Burse
> 0+0=0, 0+0.5 = 0.5, 0+1 = 1, 0.5 + 1 = 1
> 0*0 = 0, 0.* 0.5 = 0, 0*1 = 0, 0.5*0.5 = 0.5, 1*1 = 1
> ~0=1, ~0.5 = 0.5, ~1 = 0
So you have
~0.5 = 0.5
Lukacivics logic violates Boolean Lattic in that
it has an element with ~x=x. This does not happen
in a boolean lattic.
Look see, for every boolean lattice, there is a
boolean ring with + define as follows:
a + b = (a & ~b) v (b & ~a)
Now we have:
~a = 1 + a
Now check whether ~a=a is possible:
~a = 1 + a = a ?
Add a on both sides:
1 + a + a = a + a ?
Simplify by a + a = 0:
1 + 0 = 0 ?
Simplify by 1 + 0 = 1:
1 = 0 ?
++ No ++ ++ No ++ ++ No ++ ++ No ++
In a non trivial boolean lattice we have 1!=0. So the
assumption ~x=x leads to a contradiction. So it cannot
be in a boolean lattice that ~x=x.
Hence the Lukacivics system is not a boolean lattice.
Bye
Jan Burse
> In a non trivial boolean lattice we have 1!=0. So the
> assumption ~x=x leads to a contradiction. So it cannot
> be in a boolean lattice that ~x=x.
>
> Hence the Lukacivics system is not a boolean lattice.
If you still have doubts please let me know. I am
happy to invest time to produce an alternative proof
without a detour on the boolean ring.
Best Regards
Newberry
But is this statement true or false? "All two element boolean algebras
are fields and all Boolean algebras such that the number of element n
> 2 are not fields."
> My point in discussion Boolean algebras as algebras (in
> the sense of commutative ring theory) is to clarify how
> close we come to having a field.
OK.
> > If Boolean algebra (in general) is not a field then what is it?
>
> A Boolean algebra is always a ring extension of Z/2Z.
> Google for Boolean ring and you'll see the construction
> of addition as symmetric difference is a standard one.
>
Jan Burse
And by Kleene as well. So there is Lukasiwicz Algebra, Kleene Algebra
in the same sense that there is Boolean Algebra, going back
to George Boole.
And because we don't have Lukasiwicz-Kleene-Bool Algebra, it is
to assume, that by this simple name reasoning, that those algebras
and/or structures are not the same.
Here is the promised proof, based on boolean algebra alone, without
detour over boolean ring, that ~x=x is not possible.
Case 1: Assume x=0,
Since ~0=1!=0, we get already a contradiction.
Case 2: Assume x!=0.
Now observer when we have y=z, then y & z=y=z.
So we can apply this to ~x=x whereby we assume x!=0.
Thus we have ~x&x=x.
But it is ~x&x=0, hence x=0, contrary to our assumption x!=0.
Q.E.D.
Bye
Newberry
I did not understabd your notation. Are you saying that if you have a
universal set with two elements {a, b} then you have four subsets?
0, {a}, {b}, {a, b} = 1
and if you have a universal set with only one element b then you have
only two subsets?
0, {a} = 1
If this is so it opens another question. What kind of algebra is
multivalued logic?
Aatu Koskensilta
> If this is so it opens another question. What kind of algebra is
> multivalued logic?
Have a look at
http://plato.stanford.edu/entries/logic-manyvalued/#AlgSem
and
http://en.wikipedia.org/wiki/MV-algebra
--
Aatu Koskensilta (aatu.kos...@uta.fi)
"Wovon mann nicht sprechen kann, dar�ber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
Jan Burse
> I did not understabd your notation.
Why are you then asking about finite fields and boolean algebra.
Its exactly the notation of those. Namely:
x: A variable, a place holder for an element of the field/algebra.
~: Complement function symbol.
+: Addition function symbol.
&: Conjunction functionn symbol.
=: Equality relation symbol.
1: Constant for top element.
0: Constant for bottom element.
> Are you saying that if you have a
> universal set with two elements {a, b} then you have four subsets?
> 0, {a}, {b}, {a, b} = 1
No I didn't say that. And the "universal set" and "sets" usually
only exist after the insight that a finite boolean algebra is
isomorpohic to n copies of 2-valued boolean algebra.
But right, there is also a notion of atoms in lattice theory.
I think {a} and {b} might count as atoms, since they are just
above 0. If these are the only atoms, then yes 1={a,b}.
And yes, if there are n atoms, then the boolean algebra has
2^n elements.
Bye
Jan Burse
> Newberry <newbe...@gmail.com> writes:
>
>> If this is so it opens another question. What kind of algebra is
>> multivalued logic?
>
> Have a look at
>
> http://plato.stanford.edu/entries/logic-manyvalued/#AlgSem
>
> and
>
> http://en.wikipedia.org/wiki/MV-algebra
>
http://math.chapman.edu/cgi-bin/structures
For example the Lukasiewicz algebras are located somewhere here:
Boolean algebra
|
Lukasiewicz algebras
|
de Morgan Algebra
Whereby towards the bottom we have less axioms.
Bye
herbzet
galathaea wrote:
> leptons are atomic units of entity
> that hold only one opinion at a time
This is true of all fermions, by the Pauli exclusion principle.
--
hz
herbzet
"cbr...@cbrownsystems.com" wrote:
That's odd -- I have no problem. Try going to the link marked
"Table of Contents" and thence to Chapter 2.
> Or I can just chew on it a bit
> myself (the proof, not the book!).
Though the book is indeed very tasty, the proof goes:
1) a + 1 = 1
1 = a + a' P4
= a + a'(1) P2
= (a + a')(a + 1) P3
= 1(a + 1) P4
= a + 1 P2
2) a + ab = a
a = 1a P2
= (1 + b)a by (1), P1
= 1a + ba P3, P1
= a + ba P2
= a + ab P1
3) a + a(bc) = a + (ab)c
a + a(bc) = a by (2)
= a(a + c) by (2)
= (a + ab)(a + c) by (2)
= a + (ab)c P3
4) a' + a(bc) = a' + (ab)c
a' + a(bc) = (a' + a)(a' + bc) P3
= 1( a' + bc) P4
= a' + bc P2
= (a' + b)(a' + c) P3
= [1(a' + b)](a' + c) P2
= [(a' + a)(a' + b)](a' + c) P4
= (a' + ab)(a' + c) P3
= a' + (ab)c P3
Multiply (3) and (4) to obtain:
5) [a + a(bc)][a' + a(bc)] = [a + (ab)c][a' + (ab)c]
Reduce left side:
[a + a(bc)][a' + a(bc)] = aa' + a(bc)
= 0 + a(bc)
= a(bc)
Reduce right side:
[a + (ab)c][a' + (ab)c] = aa' + (ab)c
= 0 + (ab)c
= (ab)c
So (5) becomes a(bc) = (ab)c and its dual is a + (b + c) = (a + b) + c.
The principal of duality follows immediately from "the symmetry of the
postulates with regard to the two operations and the two identities".
--
hz
William Elliot
> On Jun 14, 2:29�am, William Elliot <ma...@rdrop.remove.com> wrote:
>>>>> Is Boolean algebra a finite field?
>>
>>>> No.
>>>> Every element has a complement but
>>>> not every element has a reciprocal.
>>
>>> Here is a definition from Wikipedia
<clipped, of a field>
>>> Doesn't Boolean algebra satisfy this?
>>
>> No. Let a' be the complement of a,
>> a + b is union or join of a and b,
>> ab the intersection or meet of a and b.
>>
>> Given a Boolean algebra with three elements, 0,a,1,
>> there is no x with ax = 1 even though a /= 0, for we
>> would have a = a1 = a(1 + x) = a1 + ax = a + 1 = 1.
>>
This shows that any Boolean that is also a field,
has only two elements, 0 and 1.
>> OTOH, a Boolean algebra of two elements is a field.
>>
>> A Boolean algebra can be converted to a ring by
>> defining a new ++ with a ++ b = ab' + a'b,
>> and keeping ab as is.
>
> OK, let me ask you this then:
>
> Does ++, ., ' give you the ability to define all the combinatorial
> functions?
I don't care. It can do whatever a ring can do.
> Are you saying that 2-valued Boolean algebra is a field (or can be
> massaged into a field) and multivalued Boolean algebras are not
> fields?
No! I'm saying the only Boolean algebra which is also a field
the Boolean algebra of two elements. What is a 2-valued Boolean
algebra? Seems it's something to do with logic instead of algebra.
> If Boolean algebra (in general) is not a field then what is it?
>
It's a Boolean algebra, neither more nor less.
It has two closed binary operations and one closed
uniary operator and some axioms that are much
different than the field axioms.
Do a Yahoo.com search on 'Boolean algebra'.
herbzet
Bill Dubuque wrote:
> Newberry writes:
> >
> > Is Boolean algebra a finite field?
>
> The question doesn't make any sense as posed since
> you don't specify what the operations are supposed
> to be on the finite field. Any finite set of the
> same cardinality as a finite field can be given
> the structure of a finite field - that is trivial.
>
> Every boolean algebra is, in a certain sense, equivalent
> to a boolean ring (i.e. a ring where x^2 = x) where
> product = intersection, sum = symmetric difference
>
> i.e. xy = x/\y, x+y = (x'/\y)\/(x/\y')
>
> But x^2 = x => x = 0 or x = 1 in a field. Hence
> the only such field is the field of two elements F_2.
Let me see if I understand you:
In a boolean algebra xx = x for every x.
In a field xx = x implies x = 1 or x = 0.
So if we take field multiplication as boolean meet, then
the only boolean algebra that can be a field is a boolean
algebra of two elements.
Is that right?
--
hz
herbzet
Marshall wrote:
> herbzet wrote:
> >
> > > (Has this work been done? I haven't been
> > > able to find it.)
> >
> > Um, maybe google for three-valued logic, models of?
...
> More seriously, I have googled the question in the
> past and come up dry. I don't think I know the right
> terms to search for (I believe I've tried the ones you
> mention) and/or this question isn't generally interesting
> enough that anyone besides me cares. I'll just have
> to derive it myself; so much easier and educational.
Off the top of my head:
1) Proving the independence of axioms for propositional calculus
(a two-valued boolean algebra) often involves using a more-
than-two valued model in which the inference rule(s) preserve
a "distinguished value", and all the axioms (but one!) always
take the distinguished value -- thus the one axiom is independent
from the others.
So independence proofs for propositional logic might be of help.
There are several such independence proofs for modal propositional
logic in the appendices to "Symbolic Logic" by Lewis & Langford
(excellent chance it's in any decent library near you).
2) There's a very good and accessible discussion of 3-valued logic
in A. N. Prior's "Formal Logic". In addition, one of the appendices
has a lot of axiom systems listed, including (I think) axioms systems
for a bunch of 3-valued logics, some not discussed in the main text.
I love the book, btw. Great book on logic, if a little musty (1962).
My copy was stolen. :-( Check the library while you're there, or
buy a new or used copy at Amazon or somewhere. There are more
recent editions, too.
Be lifted by Prior's puissant pen!
--
hz
William Elliot
> On Jun 14, 2:29�am, William Elliot <ma...@rdrop.remove.com> wrote:
>> On Sat, 13 Jun 2009, Newberry wrote:
>>>>> Is Boolean algebra a finite field?
>>
>>>> Every element has a complement but
>>>> not every element has a reciprocal.
>>
>>> Here is a definition from Wikipedia
<of a field>
>>> Doesn't Boolean algebra satisfy this?
>>
>> No. �Let a' be the complement of a,
>> a + b is union or join of a and b,
>> ab the intersection or meet of a and b.
>>
>> Given a Boolean algebra with three elements, 0,a,1,
>> there is no x with ax = 1 even though a /= 0, for we
>> would have a = a1 = a(1 + x) = a1 + ax = a + 1 = 1.
>>
>> OTOH, a Boolean algebra of two elements is a field.
>>
>> A Boolean algebra can be converted to a ring by
>> defining a new ++ with a ++ b = ab' + a'b,
>> and keeping ab as is.
>
> OK, let me ask you this then:
>
> Does ++, ., ' give you the ability to define all the combinatorial
> functions?
> Are you saying that 2-valued Boolean algebra is a field (or can be
> massaged into a field) and multivalued Boolean algebras are not
> fields?
That is restricted logic view of Boolean algebra.
In Wikipedia, don't read Boolean algebra (logic),
read Boolean algebra (algebra).
> If Boolean algebra (in general) is not a field then what is it?
>
An example of a Boolean algebra which isn't a "2-valued" thing
is the collection of subsets of the real numbers using
intersection, union and complement as the operators.
herbzet
Jan Burse wrote:
> Jan Burse schrieb:
> > herbzet schrieb:
> >
> >> Um, maybe google for three-valued logic, models of?
> >
> > Here is a proof that a boolean algebra cannot have a
> > three-valued model.
> > Q.E.D.
>
> Three-valued logic is not classical, what is the same
> as to say it is not based on a boolean algebra.
Right.
> Maybe on a distribute lattice, but not on a
> boolean algebra.
--
hz
herbzet
Marshall wrote:
> ----------------
> At the complete other end of the spectrum, we
> can get the whole issue completely solved with
> just this:
>
> (((x v y)' v z)' v (x v (z' v (z v u)')')')' = z
>
> for the signature {or, not}. (That is, the above
> is a complete axiomatization of the boolean
> algebra.)
>
> Or again:
>
> (x | ((y | x) | x)) | (y | (z | x)) = y
>
> for the signature {nand}.
>
> Any equational axiomatization of the boolean algebra
> must have at least one equation of three variables.
>
> I think it might still be an open question whether there exist
> {or, not} axiomatizations with three variables, or with
> "size" smaller than the above one, which is 22.
> (Counting operators, including equals, and variables,
> but not parentheses.)
>
> Starting with the "--------" the results are all from
> the paper "Short Single Axioms for the Boolean Algebra"
> by McCune et al. (The earlier stuff I figgered out
> m'self.) Bill McCune is one cool cat.
http://en.wikipedia.org/wiki/Edward_Vermilye_Huntington :
"In 1904, Huntington put Boolean algebra on a sound axiomatic foundation. He
revisited Boolean axiomatics in 1933, proving that Boolean algebra required
but a single binary operation (denoted below by infix '+') that commutes and
associates, and a single unary operation, complementation, denoted by a
postfix prime. The only further axiom Boolean algebra requires is:
(a' + b')' + (a' + b)' = a,
now known as Huntington's axiom."
IOW, we need
1) ab = ba
2) a(bc) = (ab)c
3) (a'b')'(a'b)' = a
In G. Spencer Brown's "Laws of Form" his notation /assumes/ (1) and (2),
and doesn't need parentheses.
So we might be able to get along with just (3) -- one axiom, two variables,
size eleven.
--
hz
herbzet
Marshall wrote:
> herbzet wrote:
> > Marshall wrote:
> > > Here's a smallish but complete set of axioms for boolean
> > > algebra, with the and/or/not signature (^/2 v/2 -/1).
> >
> > > x ^ 1 = x.
> > > x v 0 = x.
> >
> > > x ^ -x = 0.
> > > x v -x = 1.
> >
> > > x ^ y = y ^ x.
> >
> > > x ^ (y v z) = (x ^ y) v (x ^ z).
> > > x v (y ^ z) = (x v y) ^ (x v z).
> >
> > Are you sure we don't need x v y = y ^ x ?
>
> [You meant to say "Are you sure we don't need x v y = y v x ?"]
!@#$% yes.
> Yes. Although it is of course a theorem. Alternatively,
> we can include the commutativity of 'or' as an axiom
> and take the commutativity of 'and' as a theorem.
>
> That's the amusing fillip of asymmetry. Are you
> not entertained?
How very peculiar, that we can dispose of one, but
only one, of 4 pair! In two different ways!
I thought the asymmetry you were referring to was
that we *don't* have:
x ^ 1 = x.
x ^ -x = 1
x v 0 = x.
x v -x = 0
Which looks like a sort of double group thingie.
What we *do* have is a kind of twist on that. Reminds
me of a Moebius strip, somehow. Also reminds me of an
oscillator circuit, where you have two transistors and
the output of each one is fed to the input of the other ...
> http://www.youtube.com/watch?v=rbg5AAm2_XM
Unfortunately, my ancient laptop is too underpowered to watch videos.
> > Hm, since each pair of formula above are dual pairs
> > (swap '^' and 'v', and '0' and '1') I wonder if we
> > can get away with just one formula from each pair ...
>
> Alas, no. If we omit any of the seven we don't have
> a basis any more.
>
> ----------------
--
hz
herbzet
Of course, not all fermions are elementary.
--
hz
herbzet
William Elliot wrote:
> Newberry wrote:
> >> A Boolean algebra can be converted to a ring by
> >> defining a new ++ with a ++ b = ab' + a'b,
> >> and keeping ab as is.
> >
> > OK, let me ask you this then:
> >
> > Does ++, ., ' give you the ability to define all the combinatorial
> > functions?
Yes, because *,' already give you the ability to define all the
combinatorial functions, e.g.,
a v b =def (a' * b')'
a -> b =def a' v b
etc.
The operators ++, * alone do not allow the definition of, e.g.,
the operator ->.
Proof:
0 -> 0 = 1
but
0 ++ 0 = 0
and
0 * 0 = 0
so there's no way to generate f(0,0) = 1 where f is composed only
from ++ and *.
Neither is ++, ' a complete basis, though I havn't got a proof yet.
It fails quickly in a two-element structure.
(I don't know how it all works out for a Boolean *ring*.)
--
hz
Marshall
> Marshall wrote:
>
> > That's the amusing fillip of asymmetry. Are you
> > not entertained?
>
>
> Unfortunately, my ancient laptop is too underpowered to watch videos.
It's just a few seconds of some yahoo yelling "Are you not
entertained" at the Coliseum. It's a reference to the
overrated "Gladiator" starring the overrated Russel Crowe,
with the slightly overrated Joaquin Phoenix, directly by
the justly-revered Ridley Scott.
Marshall
herbzet
Newberry wrote:
>
> Is Boolean algebra a finite field?
We've already established that not every Boolean algebra is finite,
but just to add to the fun:
"In mathematics, Stone's representation theorem for Boolean algebras
states that every Boolean algebra is isomorphic to a field of sets."
http://en.wikipedia.org/wiki/Stone_representation_theorem
--
hz
Alan Smaill
> William Elliot wrote:
> > Newberry wrote:
>
> > >> A Boolean algebra can be converted to a ring by
> > >> defining a new ++ with a ++ b = ab' + a'b,
> > >> and keeping ab as is.
> > >
> > > OK, let me ask you this then:
> > >
> > > Does ++, ., ' give you the ability to define all the combinatorial
> > > functions?
>
> Yes, because *,' already give you the ability to define all the
> combinatorial functions, e.g.,
>
> a v b =def (a' * b')'
> a -> b =def a' v b
> etc.
>
> The operators ++, * alone do not allow the definition of, e.g.,
> the operator ->.
>
> Proof:
>
> 0 -> 0 = 1
>
> but
>
> 0 ++ 0 = 0
>
> and
>
> 0 * 0 = 0
>
> so there's no way to generate f(0,0) = 1 where f is composed only
> from ++ and *.
well, but usually you have constants for 0 and 1, so this is not a problem.
And you even have a' = 1 ++ a.
> Neither is ++, ' a complete basis, though I havn't got a proof yet.
> It fails quickly in a two-element structure.
Why doesn't that give a proof?
> (I don't know how it all works out for a Boolean *ring*.)
>
> --
> hz
--
Alan Smaill
cbr...@cbrownsystems.com
Only the First chapters through 1-8 are linkable for me; the others
are not included in the "Preview". Is there some account I'm supposed
to open?
>
> > Or I can just chew on it a bit
> > myself (the proof, not the book!).
>
> Though the book is indeed very tasty, the proof goes:
>
<snip of tasty proof>
You are too kind! Thanks for the effort. One question: I follow
everything but the step in (1)
= a + a'(1) P2
= (a + a')(a + 1) P3
I assume P3 is the distributive property; but I don't see how it
applies here to produce the latter from the former here.
Cheers - Chas
herbzet
Marshall wrote:
>
> On Jun 15, 5:03�am, herbzet <herb...@gmail.com> wrote:
> > Marshall wrote:
> >
> > > That's the amusing fillip of asymmetry. Are you
> > > not entertained?
> >
> > �>http://www.youtube.com/watch?v=rbg5AAm2_XM
> >
> > Unfortunately, my ancient laptop is too underpowered to watch videos.
>
> It's just a few seconds of some yahoo yelling "Are you not
> entertained" at the Coliseum. It's a reference to the
> overrated "Gladiator"
Usually toga films die a quick death these days. "Gladiator"
inspired some new efforts -- "300" did very well.
> starring the overrated Russel Crowe,
When I first saw him in "L.A. Confidential" I _knew_ the critics
would love this big hunk of beef. I liked Guy Pearce better.
He carried "Gladiator" easily. I think he's actually pretty good.
> with the slightly overrated Joaquin Phoenix,
vastly overrated
> directly by the justly-revered Ridley Scott.
Agreed.
--
hz
cbr...@cbrownsystems.com
Ahh! Symmtery again: For P3, I was thinking only
a(b+c) = ab + ac
but by symmetry we also have
a + bc = (a + b)(a + c)
so I get it.
Cheers - Chas
Marshall
> Marshall wrote:
>
> > It's just a few seconds of some yahoo yelling "Are you not
> > entertained" at the Coliseum. It's a reference to the
> > overrated "Gladiator"
>
> Usually toga films die a quick death these days. "Gladiator"
> inspired some new efforts -- "300" did very well.
>
> > starring the overrated Russel Crowe,
>
> When I first saw him in "L.A. Confidential" I _knew_ the critics
> would love this big hunk of beef. I liked Guy Pearce better.
Yes! Yes! I *knew* you had good taste. Pearce was
so good in that film, and Crowe's Bud White was just
a thick-browed testosterone-poisoned German Shepard.
You even spelled "Pearce" correctly. Bravo!
Marshall
herbzet
We don't need 0, we already have 0 =def a ++ a.
> And you even have a' = 1 ++ a.
Well, ahem, the axiomatizations I usually see for propositional
calculus don't have either 0 or 1, e.g., Lukasiewicz's 3-axiom sets.
> > Neither is ++, ' a complete basis, though I havn't got a proof yet.
> > It fails quickly in a two-element structure.
>
> Why doesn't that give a proof?
Well, it does, but I've left it to the reader to see for him/herself.
Marshall
Uh, but we do have those. The thing that's omitted
is the fixpoint equations.
x ^ 0 = 0
x v 1 = 1
Amusingly, thinking about your typo "x v y = y ^ x",
it occurs to me that it says that for any two values,
the meet is equal to the join. That would seem to
suggest (if my lattice intuition is working correctly)
that this is another way to specify "single-element
models only please."
Marshall
Alan Smaill
Well, the thread talks about Boolean Algebra;
the context in the post I replied to was about the definition of
Boolean rings in terms of Boolean algebras, so, strangely
enough, I took it that Boolean algebras were involved.
In that context, ++ and * will suffice, no?