flat assembler
Message board for the users of flat assembler. Index > Heap > Boolean algebra question
Author
 Thread  LocoDelAssembly

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

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 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 23 Nov 2007, 01:52  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) 23 Nov 2007, 02:23
LocoDelAssembly

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 Anyway I think this is not a very universitary question 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". 23 Nov 2007, 02:54  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! 23 Nov 2007, 03:22
 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. 23 Nov 2007, 07:27
 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  23 Nov 2007, 08:56
 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 ``` 23 Nov 2007, 15:15
LocoDelAssembly

Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
OK, I need to digest all this I have some doubts still, but I will think some more time before telling a word.

Thanks to all  23 Nov 2007, 16:02  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.  23 Nov 2007, 17:05
 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. 23 Nov 2007, 23:13
 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.  24 Nov 2007, 00:05
 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 24 Nov 2007, 00:18
LocoDelAssembly

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  24 Nov 2007, 01:26  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. 24 Nov 2007, 01:37
 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. 24 Nov 2007, 18:32
 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. 24 Nov 2007, 19:46
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First  Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsCompiler InternalsIDE DevelopmentOS ConstructionNon-x86 architecturesHigh Level LanguagesProgramming Language DesignProjects and IdeasExamples and Tutorials Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou can attach files in this forumYou can download files in this forum