flat assembler
Message board for the users of flat assembler.

 Index > Heap > Boolean algebra question
Author
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.

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