flat assembler
Message board for the users of flat assembler.

Index > Heap > Boolean algebra question

Author
Thread Post new topic Reply to topic
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
Warning, elementary school undergraduate question is about to begin...

On algebra of real numbers we can have the following equation:

Code:
  X + Y = 0    


Now if we want to have X alone on the left side we just substract Y on both sides and we get a sightly more simplified equation:
Code:
  X + Y - Y = 0 - Y 
  X = -Y    


Now when I turn into boolean algebra with a very simple equation I found no way to resolve step-by-step, I just get to the end "magically"

Code:
; + is OR, * is AND, ~ is NOT

  A*~B + ~A*B = 1
; Magic:
  A = ~B    


I know that it is valid because it has the same solution set (the one that A XOR B = TRUE has). My problem here is that I jumped to the final expression without any intermediate step, something I found very hateable.

So, the question: there is no intermediate step? There is no possible step between the original equation and "the magic equivalent"?


The motivation around this is homework, but actually I don't need it at all since I'm not required at all to show in a formal way why I choose one of the conditions of a problem to make up the decision table. If an object can only be red or blue then it is no possible that can't be any of these nor both so using "red" as a condition or "blue" is enough and because I am an hysterical person I want to show mathematically by showing the aforementioned "magic equation" why in the conditions set of a given problem I keep only one of two mutualy exclusive conditions.

Thanks for reading Smile

PS: And in fact I want this for myself since doing this on the exam can cause me to take the same course the next year for doing wierd non-teached things.

PS2: In case you don't know what decision tables are: http://en.wikipedia.org/wiki/Decision_tables
Post 23 Nov 2007, 01:52
View user's profile Send private message Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid
Sorry, can't help, but... Man, am I happy to be out of university !!!

(no discouragement intended)
Post 23 Nov 2007, 02:23
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
Quote:

Man, am I happy to be out of university !!!

Perhaps this will be my last year, I will go out of there without the degree Sad

Anyway I think this is not a very universitary question Razz I just want to know if in the same way that exist an intermediate step to go from "X + Y = 0" to "X = -Y", also exists one or more intermediate steps to go from "A*~B + ~A*B = 1" to "A = ~B".
Post 23 Nov 2007, 02:54
View user's profile Send private message Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4237
Location: 2018
edfed
Code:
;* is and, + is or, - is not, -+ is nor etc ...
-1=0 | -0=1 
A*A=A 
1*1=1 | 1*0=0 | 0*0=0
1+0=1 | 0+0=0 | 1+1=1
(A*-B) + (-A*B) = 1
A*-B=-(-A*B)   ; i didn't put the 1 cause it's a constant,
 a constant doesn't have condition,
 refering to differencial computation, Constant'=0
A=A*-B*-B  ;there is no reverse and
A*A=-B*-B  ;no div equivalent
A=-B
like and is mul equivalent

and can be changed of side without changing


with 0 and 1 it's simplest

(0*-1) + (-0*1) = 1
(0*-1)=-(-0*1)
0=0*-1*-1
0*0=-1*-1
0=-1 ; ohhh, it's the relation of not!^^
    

please, note that boolean algebra is not algebra!
Post 23 Nov 2007, 03:22
View user's profile Send private message Visit poster's website Reply with quote
Xorpd!



Joined: 21 Dec 2006
Posts: 161
Xorpd!
Code:
(A*(-B))+((-A)*B) = 1 ; Given
((A*(-B))+((-A)*B))*(-B) = 1*(-B) ; Right-multiply by (-B)
((A*(-B))*(-B))+(((-A)*B)*(-B)) = -B ; Distributive law and evaluation
(A*((-B)*(-B)))+((-A)*(B*(-B))) = -B ; Associative law
(A*(-B))+((-A)*0) = -B ; Evaluation
(A*(-B))+0 = -B ; Evaluation
A*(-B) = -B ; Evaluation [equation 1]
(A*(-B))+((-A)*B) = 1 ; Given
A*((A*(-B))+((-A)*B)) = A*1 ; Left-multiply by A
(A*(A*(-B)))+(A*((-A)*B)) = A ; Distributive law and evaluation
((A*A)*(-B))+((A*(-A))*B) = A ; Associative law
(A*(-B))+(0*B) = A ; Evaluation
(A*(-B))+0 = A ; Evaluation
A*(-B) = A ; Evaluation [equation 2]
A = -B ; Equation 1, equation 2, and transitivity

What if we started with (A*(-B))+((-A)*B) = 0?
(A*(-B))+((-A)*B) = 0
((A*(-B))+((-A)*B))+B = 0+B
(((-A)*B)+(A*(-B)))+B = B
((-A)*B)+((A*(-B))+B) = B
((-A)*B)+((A+B)*((-B)+B)) = B
((-A)*B)+((A+B)*1) = B
(B*(-A))+(A+B) = B
((B*(-A))+A)+B = B
((B+A)*((-A)+A))+B = B
((A+B)*1)+B = B
(A+B)+B = B
A+(B+B) = B
A+B = B
Then if you OR both sides with A you would get
A+B = A
So that it follows that A = B
    

I assume that edfed is joking above: A+B = 1 doesn't imply that A = -B because they could both be 1.
Another possibile approach is to XOR both sides with B and simplify.
Post 23 Nov 2007, 07:27
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
۷ = OR
۸ = AND
↔ = 'iff' i.e. 'if and only if'
~ = NOT

Proof:

(A ۸ ~B) ۷ (~A ۸ B) = 1 ↔

(A ۸ ~B) = 1 ۷ (~A ۸ B) = 1 ↔

(A = 1 ۸ ~B = 1) ۷ (~A = 1 ۸ B = 1) ↔

(A = 1 ۸ B = 0) ۷ (A = 0 ۸ B = 1) ↔

(B = 0 ۸ A = ~B) ۷ (B = 1 ۸ A = ~B) ↔

(B = 0 ۷ B = 1) ۸ (A = ~B) ↔

1 ۸ (A = ~B) ↔

A = ~B

Very Happy
Post 23 Nov 2007, 08:56
View user's profile Send private message Visit poster's website Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4237
Location: 2018
edfed
i don't joke
Code:
A+B=1???     is this the joke????
A=(a*-b) ?
B=(-a*b) ?

in this condition, A=-B

A+B=0
A=(a*-b)
B=(-a*b)

and then, A=B=0
    
Post 23 Nov 2007, 15:15
View user's profile Send private message Visit poster's website Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
OK, I need to digest all this Razz

I have some doubts still, but I will think some more time before telling a word.

Thanks to all Very Happy
Post 23 Nov 2007, 16:02
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2906
Location: [RSP+8*5]
bitRAKE
edfed wrote:
please, note that boolean algebra is not algebra!
Isn't this a joke? All algebra is a simplification of boolean algebra - we only need NAND/NOR to emulate all of mathematics. Well, MANY of them. Laughing
Post 23 Nov 2007, 17:05
View user's profile Send private message Visit poster's website Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4237
Location: 2018
edfed
Quote:

All algebra is a simplification of booléan algebra


FALSE!
Boolean algebra was invented by george boole, a british mathematician.
algebra was invented by nobody-knows-because-it's-too-far
Boolean algebra is only applicated to discretes and quantified algebra
binary 0/1 logic proposition between 2 values or more
algebra covers the total mathemetic domain.
Post 23 Nov 2007, 23:13
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2906
Location: [RSP+8*5]
bitRAKE
Haha...just because it was discovered afterward doesn't mean it is any less all encompassing. Nothing is more powerful than 0 and 1. Razz
Post 24 Nov 2007, 00:05
View user's profile Send private message Visit poster's website Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4237
Location: 2018
edfed
0/1=infinite

but computer world is not real world

computers only understands 0 & 1
Code:
  --- boolean algebra is there
    

human only understand real values and variables
Code:
  --- assembler is there
    

computers only understand instructions

there are many other ways to convert mathematics
geometry, optics, analog electrronics, computers,
the cheapest and easiest to make is the digital silicium chip.
but when quantic processors will appears, we'll need one extra definition of boole algebra.
an algebra based on trinary or other.-1,0,1
Post 24 Nov 2007, 00:18
View user's profile Send private message Visit poster's website Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
Quote:

but when quantic processors will appears, we'll need one extra definition of boole algebra.

If you mean quantum computers so far them are not the future for general purpose use, the algorithms also need to be quantic but AFAIK there is no way to translate all the normal algorithms to quantum algorithms.

A fragment of the wikipedia:
Quote:
Consider a problem that has these four properties:

The only way to solve it is to guess answers repeatedly and check them,
There are n possible answers to check,
Every possible answer takes the same amount of time to check, and
There are no clues about which answers might be better: generating possibilities randomly is just as good as checking them in some special order.
An example of this is a password cracker that attempts to guess the password for an encrypted file (assuming that the password has a maximum possible length).

For problems with all four properties, the time for a quantum computer to solve this will be proportional to the square root of n (it would take an average of (n + 1)/2 guesses to find the answer using a classical computer.) That can be a very large speedup, reducing some problems from years to seconds. It can be used to attack symmetric ciphers such as Triple DES and AES by attempting to guess the secret key. Regardless of whether any of these problems can be shown to have an advantage on a quantum computer, they nonetheless will always have the advantage of being an excellent tool for studying quantum mechanical interactions, which of itself is an enormous value to the scientific community.


http://en.wikipedia.org/wiki/Quantum_computer

I felt very dissapointed when a friend, a physicist him, told me that it is not usable for general purpose, I though that all this was just replacing silicon chips by quantum hardware but keeping x86 architecture (or whatever) intact but NO, it is a completely different world Sad
Post 24 Nov 2007, 01:26
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2906
Location: [RSP+8*5]
bitRAKE
I don't deny the limitations, but there is no system without the same limitations. What reality? If we attempt to communicate any part of reality then we have in some way reduced it to binary form, and in doing so lie.

All forms of logic can be emulated with binary. Complex forms are more terse, but it acts merely as a form of compression - no special computablity is granted by brevity.

Even fuzzy logic can be represented by binary logic. A choice of percision needs to be made, and the same can be said for any system.
Post 24 Nov 2007, 01:37
View user's profile Send private message Visit poster's website Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4237
Location: 2018
edfed
the pure math system have no limit.
pure math domain is the meta domain.
everything can be explained with maths.
Post 24 Nov 2007, 18:32
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2906
Location: [RSP+8*5]
bitRAKE
Did you run that by Kurt Gödel?

[Edit By loco] Corrected link to use ASCII only chars. It is required for the forum, otherwise the url tags does not work.
Post 24 Nov 2007, 19:46
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You can attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.