| View previous topic :: View next topic |
| Author |
Message |
Greg.Shumaker
Guest
|
 Posted: Thu Oct 09, 2008 5:23 am Post subject: boolean algebra |
 |
|
Hi, I>m new to boolean algebra and am having a lot of problems
figuring out which identities to use to solve this problem. any help
would be grately appreciated.
Given that:
xy' + x>y = z
show that
xz' + x>z = y
hint: plug Z into the second equation |
|
| |
|
 Back to top |
Mitch
Guest
|
| Posted: Thu Oct 09, 2008 1:34 pm Post subject: Re: boolean algebra |
|
|
On Oct 9, 8:46 am, William Elliot <ma...@hevanet.remove.com> wrote:
[quote]On Thu, 9 Oct 2008, Frederick Williams wrote:
"Greg.Shumaker" wrote:
Given that:
xy' + x>y = z
show that
xz' + x>z = y
If z is the symmetric difference of x and y, then
y is the symmetric difference of x and z. Interesting.
[/quote]
And also x = (y != z). And also the triple identity for the dual
z = (x + y')(x' + y)
[quote]You know that z = xy' + x>y so you can work out what z' and x>z are and
thus what xz' + x>z is. Simplify using well-known things like De
Morgan.
Let>s make this a real problem. Given
xy' + x>y = z
solve for y in terms of x and z.
Hint, what>s z' in disjunctive normal form?
Just a nanosec, that>s logic terminology.
What>s in in algebraic terminology?
[/quote]
sum of products?
The term for symmetric difference is exclusive-or.
What>s the term for the dual of symmetric difference/xor? 'Equality'
just doesn>t sound like an operation.
Mitch |
|
| |
|
| Back to top |
William Elliot
Guest
|
| Posted: Thu Oct 09, 2008 4:52 pm Post subject: Re: boolean algebra |
|
|
On Wed, 8 Oct 2008, Greg.Shumaker wrote:
[quote]Given that:
xy' + x>y = z
show that
xz' + x>z = y
hint: plug Z into the second equation
So what>s he problem? How to compute z'?[/quote]
Use DeMorgan>s rules. What do you get? Then upon simplification
what do you get for z' expressed like your other equations
without need for parenthesis?
---- |
|
| |
|
| Back to top |
Frederick Williams
Guest
|
| Posted: Thu Oct 09, 2008 5:05 pm Post subject: Re: boolean algebra |
|
|
"Greg.Shumaker" wrote:
[quote]
Hi, I>m new to boolean algebra and am having a lot of problems
figuring out which identities to use to solve this problem. any help
would be grately appreciated.
Given that:
xy' + x>y = z
show that
xz' + x>z = y
hint: plug Z into the second equation
[/quote]
You know that z = xy' + x>y so you can work out what z' and x>z are and
thus what xz' + x>z is. Simplify using well-known things like De
Morgan.
--
He is not here; but far away
The noise of life begins again
And ghastly thro' the drizzling rain
On the bald street breaks the blank day. |
|
| |
|
| Back to top |
William Elliot
Guest
|
| Posted: Thu Oct 09, 2008 5:46 pm Post subject: Re: boolean algebra |
|
|
On Thu, 9 Oct 2008, Frederick Williams wrote:
[quote]"Greg.Shumaker" wrote:
Given that:
xy' + x>y = z
show that
xz' + x>z = y
If z is the symmetric difference of x and y, then[/quote]
y is the symmetric difference of x and z. Interesting.
[quote]You know that z = xy' + x>y so you can work out what z' and x>z are and
thus what xz' + x>z is. Simplify using well-known things like De
Morgan.
[/quote]
Let>s make this a real problem. Given
xy' + x>y = z
solve for y in terms of x and z.
Hint, what>s z' in disjunctive normal form?
Just a nanosec, that>s logic terminology.
What>s in in algebraic terminology? |
|
| |
|
| Back to top |
herbzet
Guest
|
| Posted: Thu Oct 09, 2008 6:55 pm Post subject: Re: boolean algebra |
|
|
"Greg.Shumaker" wrote:
[quote]
Hi, I>m new to boolean algebra and am having a lot of problems
figuring out which identities to use to solve this problem. any help
would be grately appreciated.
Given that:
xy' + x>y = z
show that
xz' + x>z = y
hint: plug Z into the second equation
[/quote]
Some useful identities are used in the proof below:
Double negation a'' = a
De Morgan>s laws (a + b)' = a>b'
(ab)' = a' + b'
expansion laws a(b + b') = a (for introducing and removing
a + (bb') = a irrelevant variables)
idempotence laws a + a = a
aa = a
(don>t know name) a + a' = a + a' + b
aa' = aa>b
distributive laws a(b + c) = ab + ac
a + (bc) = (a + b)(a + c)
associative laws (a + b) + c = a + (b + c)
(ab)c = a(bc)
commutative laws a + b = b + a
ab = ba
Expansion and distribution together
give Poretsky>s laws of production a = (a + b)(a + b')
(not used in proof below) a = ab + ab'
=============================================================
OK, now for a not-clever proof, with some bonus slacking.
Taking your hint from above:
Since
z = xy' + x>y
we have by substitution
xz' + x>z = x(xy' + x>y)' + x'(xy' + x>y).
Taking the first disjunct:
x(xy' + x>y)' = x((xy')'(x>y)') De Morgan>s law
= x((x' + y'')(x'' + y')) De Morgan>s law (twice)
= x((x' + y)(x + y')) double negation (twice)
= (x(x' + y))(x + y') associative law
= (xx' + xy)(x + y') distributive law
= (xy)(x + y') expansion law
= (xy)x + (xy)y' distributive law
= x(yx) + x(yy') associative law (twice)
= x(xy) + x(yy') commutative law
= (xx)y + x(yy') associative law
= xy + x(yy') idempotence
= xy + yy' (don>t know name)
= xy expansion law (1)
Taking the second disjunct:
x'(xy' + x>y) = x>xy' + x>x>y distributive law
= x>x + x>x>y (don>t know name)
= x>x + x>y idempotence
= x>y expansion law (2)
Taking the disjuncts (1), (2):
xy + x>y = (x + x')y distributive law
= y expansion law
QED.
Some of the steps above (double negation, associative and
commutative operations) are commonly left out as excessively
nit-picky. I left them in (mostly) so the proof looks
scarier than it is.
But I thought you ought to see it once.
--
hz |
|
| |
|
| Back to top |
herbzet
Guest
|
| Posted: Thu Oct 09, 2008 7:02 pm Post subject: Re: boolean algebra |
|
|
Mitch wrote:
[quote]The term for symmetric difference is exclusive-or.
What>s the term for the dual of symmetric difference/xor? 'Equality'
just doesn>t sound like an operation.
[/quote]
Bi-implication.
--
hz |
|
| |
|
| Back to top |
William Elliot
Guest
|
| Posted: Fri Oct 10, 2008 7:50 am Post subject: Re: boolean algebra |
|
|
On Thu, 9 Oct 2008, Mitch wrote:
[quote]On Oct 9, 8:46 am, William Elliot <ma...@hevanet.remove.com> wrote:
On Thu, 9 Oct 2008, Frederick Williams wrote:
"Greg.Shumaker" wrote:
Given that:
xy' + x>y = z
show that
xz' + x>z = y
If z is the symmetric difference of x and y, then
y is the symmetric difference of x and z. Interesting.
And also x = (y != z). And also the triple identity for the dual
Huh? You>re not talking algebra.[/quote]
[quote]z = (x + y')(x' + y)
[/quote]
[All Google corrupted quoting hidden.] |
|
| |
|
| Back to top |
Mitch
Guest
|
| Posted: Fri Oct 10, 2008 2:15 pm Post subject: Re: boolean algebra |
|
|
On Oct 10, 1:49 am, William Elliot <ma...@hevanet.remove.com> wrote:
[quote]On Thu, 9 Oct 2008, Mitch wrote:
On Oct 9, 8:46 am, William Elliot <ma...@hevanet.remove.com> wrote:
On Thu, 9 Oct 2008, Frederick Williams wrote:
"Greg.Shumaker" wrote:
Given that:
xy' + x>y = z
show that
xz' + x>z = y
If z is the symmetric difference of x and y, then
y is the symmetric difference of x and z. Interesting.
And also x = (y != z). And also the triple identity for the dual
Huh? You>re not talking algebra.
[/quote]
Sorry, mixed languages. By 'y != z', I was abbreviating 'y or z but
not both', the exclusive-or (symmetric difference in sets). How does
'y xor z' sound? Or is that logic to you? If so, what is the algebra
way of saying that?
Using the language of the original poster (where '+' is 'or' and
concatenation is 'and'):
The triple identity is that any one of the following implies the other
two:
xy' + x>y = z
xz' + x>z = y
yz' + y>z = x
and the dual is:
any one of the following implies the other two:
(x+y')(x'+y) = z
(x+z')(x'+z) = y
(y+z')(y'+z) = x
Does that make sense?
Mitch |
|
| |
|
| Back to top |
William Elliot
Guest
|
| Posted: Sat Oct 11, 2008 8:05 am Post subject: Re: boolean algebra |
|
|
On Fri, 10 Oct 2008, Mitch wrote:
[quote]On Oct 10, 1:49 am, William Elliot <ma...@hevanet.remove.com> wrote:
Given that:
xy' + x>y = z
show that
xz' + x>z = y
If z is the symmetric difference of x and y, then
y is the symmetric difference of x and z. Interesting.
And also x = (y != z). And also the triple identity for the dual
Huh? aYou>re not talking algebra.
Sorry, mixed languages. By 'y != z', I was abbreviating 'y or z but not
both', the exclusive-or (symmetric difference in sets). How does 'y xor
z' sound? Or is that logic to you? If so, what is the algebra way of
saying that?
xor is computer talk. Logical connectives traditionallly where[/quote]
and, or, implies and the seldom used, Sheiffer>s stroke, neither... nor,
ie ~P * ~Q. Connectives in set theory are union and interesction.
[quote]Using the language of the original poster (where '+' is 'or' and
concatenation is 'and'):
[/quote]
OP * and + are the operations of a Boolean algebra and have little to
do 'and' and 'or' but much more to with inf and sup of two elements which
are neither sets nor statements, ie not sets and not statements. Using
Sheiffer>s stroke, "element is set | element is statement"
[quote]The triple identity is that any one of the following implies the other
two:
xy' + x>y = z
xz' + x>z = y
yz' + y>z = x
z = xy' + x>y[/quote]
z' = (x' + y)(x + y') = xy + x>y'
x>z = x>y; xz' = xy; thus 2nd equation
y>z = xy'; yz' = xy; thus 3rd equation or by symmetry from
1st equation premise and 2nd equaton conclusion.
[quote]and the dual is:
any one of the following implies the other two:
(x+y')(x'+y) = z
(x+z')(x'+z) = y
(y+z')(y'+z) = x
Does that make sense?
Much, a very interesting proposition.[/quote]
Using the symmetric diffence for + and keeping * as is, produces a
Boolean ring from a Boolean algebra and inversely. The associativity of
the symmetric difference is a pest to prove. Can the very interesting
propositon be used to simplify the demostration?
A Boolean ring is a ring for which all elements are idempotent.
[quote]Mitch
[/quote] |
|
| |
|
| Back to top |
herbzet
Guest
|
| Posted: Sat Oct 11, 2008 8:05 am Post subject: Re: boolean algebra |
|
|
Mitch wrote:
[quote]
Using the language of the original poster (where '+' is 'or' and
concatenation is 'and'):
[/quote]
I assumed that>s what he meant, but it could just as well be the
other way around.
Or it could mean set union and set intersection, or the other
way around.
Etc.
--
hz |
|
| |
|
| Back to top |
herbzet
Guest
|
| Posted: Sat Oct 11, 2008 2:12 pm Post subject: Re: boolean algebra |
|
|
William Elliot wrote:
[quote]xor is computer talk. Logical connectives traditionallly where
and, or, implies and the seldom used, Sheiffer>s stroke, neither... nor,
ie ~P * ~Q.
[/quote]
That>s "Sheffer". It might as well be interpreted as ~P v ~Q.
Wikipedia, in fact, so defines it:
http://en.wikipedia.org/wiki/Sheffer_stroke
Personally, I always forget which is which -- since they>re dual
operations it doesn>t matter much.
Although -- in the literature, axiomatizations of propositional
calculus using the stroke as the sole primitive operator differ
when it is interpreted as not-and (NAND) from when it is interpreted
as not-or (NOR) -- I>m pretty sure.
I>ll look it up and report back.
[quote]Connectives in set theory are union and interesction.
Mitch wrote:
Using the language of the original poster (where '+' is 'or' and
concatenation is 'and'):
OP * and + are the operations of a Boolean algebra and have little to
do 'and' and 'or' but much more to with inf and sup of two elements which
are neither sets nor statements, ie not sets and not statements. Using
Sheiffer>s stroke, "element is set | element is statement"
[/quote]
The algebra admits of a variety of interpretations, of course.
--
hz |
|
| |
|
| Back to top |
|
