Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**mikau****Member**- Registered: 2005-08-22
- Posts: 1,504

does anyone know a way to prove demorgans law without breaking the possibilities into separate cases?

(note i'm using for AND, + for OR and ' for NOT)

suppose these are the postulates you may use:

P1 Boolean algebra is closed under the AND, OR, and NOT operations.

P2 The identity element with respect to is one and + is zero. There is no identity element with respect to logical NOT.

P3 The and + operators are commutative.

P4 and + are distributive with respect to one another. That is, A (B + C) = (A B) + (A C) and A + (B C) = (A + B) (A + C).

P5 For every value A there exists a value A such that AA = 0 and A+A = 1. This value is the logical complement (or NOT) of A.

P6 and + are both associative. That is, (AB)C = A(BC) and (A+B)+C = A+(B+C)

and you may use the following thoerems:

Th1: A + A = A

Th2: A A = A

Th3: A + 0 = A

Th4: A 1 = A

Th5: A 0 = 0

Th6: A + 1 = 1

**use all of the above to prove (a + b) = a b**

i begin by proving the following lemma:

lemma 1: if A * B' = 0 and A + B' = 1, then A=B

proof by contrapositive: suppose A ≠ B, then A = B' therefore

A*B' = A*A = 0 and by theorem 2,

A = 0, but likewise

A + B' = A+A = 1 and by theorem 2

A+A = A = 1, thus we have A = 1 and A = 0, a contradiction. Thus the lemma is proved.

Now we use this to prove (a + b) = a b

we use the lemma, if A * B' = 0 and A + B' = 1, then A=B

let A = a' * b' and let B = (a + b)'

first we show A * B' = 0

A*B' = (a' * b')*(a + b), using the distributive and commutative postulates,

= a'*a * b' + a'*b'*b now using postulate 5

= 0 * b' + a'* 0, now by theorem 5

= 0 * 0 = 0

now we show A + B' = 1

A + B' = a' * b' + a + b

suppose a = b (this is what i don't like doing )

then

a' * 'b + a + b = a' * a' + a + a. by theorems 1 and 2,

= a' + a. by postulate 5

= 1

suppose now that a ≠ b, then (and so a = b' and b = a')

then

a' * b' + a + b = a' * a + a + a'. by postulate 5

= 0 + 1 = 1

therefore the lemma applies so A = B, or more specifically, (a + b) = a b qed.

I guess this works but is there any way to avoid breaking it up into cases? If i'm going to use that, i might as well use a truth table to prove it.

A logarithm is just a misspelled algorithm.

Offline

**John E. Franklin****Member**- Registered: 2005-08-29
- Posts: 3,588

When you say A ≠ B, do you mean some of the time or all of time?

Since A is 1 or 0 and B is 1 or 0, just because A is not equal to B,

doesn't necessarily mean that A is equal to negative B, or does it?

It all depends on how independent your variables are?

**igloo** **myrtilles** **fourmis**

Offline

**mikau****Member**- Registered: 2005-08-22
- Posts: 1,504

agreed, john. In fact i'm wondering if its okay to say A ≠ B ⇒ A = Not B at this point, or if we need to establish it using other postulates.

A logarithm is just a misspelled algorithm.

Offline

**John E. Franklin****Member**- Registered: 2005-08-29
- Posts: 3,588

I'm no mathmatician, so I'm not sure if there are different kinds of "not equal" signs; one that means unequal no matter what, and one that means not equal at least in one case.

If it means always unequals, then you are right that they are opposites since it is a two-state {0, 1} arena.

Let me just fiddle around here, this

stuff below can be ignored if it

doesn't help.

I'm gonna just use variables beside one another to mean AND'ing to make this faster typing.

a = a

a = a ( 1 + b`)

a = a + ab`

...

a = a

a = a (1 + 0)

a = a (b + b`) = a(b`+ b)

a = ab + ab`

...

Likewise use b instead of a.

b = b

b = b (1 + 0)

b = b (a + a`) = b(a` + a)

b = ba + ba`

b = ab + a`b

...**I think "P5" is the key to solving this.Can you use these rules? 1` = 0 0`=1 **

I'd like to add a comment on this

particular boolean algebra described above.

There is no mention that the values of

A and B can be only 0 and 1, and that

A and B are variables that can each be

independent or related to one another

in some circumstances or something.

Is this all just assumed???

If we don't lay down a strong foundation,

then loop-holes can be found, and you

can get funny weird results, that are an

algebra that is less fully constrained than

the one you wanted in the first place.

I'll edit this and add more...

*Last edited by John E. Franklin (2008-01-26 05:19:23)*

**igloo** **myrtilles** **fourmis**

Offline

**mikau****Member**- Registered: 2005-08-22
- Posts: 1,504

I'm no mathmatician, so I'm not sure if there are different kinds of "not equal" signs; one that means unequal no matter what, and one that means not equal at least in one case.

If it means always unequals, then you are right that they are opposites since it is a two-state {0, 1} arena.

first i'm using 1 and 0 to represent the boolean values true and false respectively, thats just notation

the above are all postulates, I think there are probably some axioms that i'm allowed to use. For instance, a boolean value is either true or false. If it isn't false, its true, and vice versa.

when working with variables, the actual values are not given, however you can be sure that either A = B or A ≠ B no matter what values for A and B are being dealt with. If you can show that it works in both cases, then you have proved it in the general case.

But yeah, the question remains, is it okay to say A ≠ B ⇒ A = B'

I think if we are working with boolean values, we have to be able to assume that much, right?

A logarithm is just a misspelled algorithm.

Offline

**John E. Franklin****Member**- Registered: 2005-08-29
- Posts: 3,588

Well, the thing is, there are so many ways folks have

used symbols, that almost anything is true and false

at the same time, depending on the exact meaning

of your symbols. Like the ⇒ symbol is unfamiliar to me,

but I also use ---> in my own posts. But since you

are trying to do a "proof", this is where I have to

drop out and say I'm not formal enough or legit yet.

The operators and equality statement and implication

symbols can all get confused, because there are

similarities between them. Like the non-equal symbol

is similar to the XOR operator, but one is an operator,

and the other separates two sides of an equation.

The ⇒ symbol also reminds me of the imply logic symbol,

and parallels can probably be stated along these lines.

The other thing is that, Venn diagrams are a useful tool,

and one can visualize DeMorgans Law with Venn diagrams

quite easily, if you know how to shade it in and take

the negative image, but I hesitated to even bring up this

because you are trying to stick to certain rules; and

perhaps the boolean algebra mentioned here is not

exactly the same as Venn diagrams anyway, because the

entire set of rules and original structure may be allowing

for things to be stated that are not true for Venn diagrams.

I just don't want to jump to conclusions since this is

what I normally do...

**igloo** **myrtilles** **fourmis**

Offline

**Melanie1988****Guest**

I need help proving the DeMorgan's Law with Boolean Algebra. No "and" nor "or".

( a + b )' = a' * b'

For example, Proof of Absorption Law:

a ( a + b ) = a

( a * a ) + ( a * b ) => distributive property

a + a * b => idempotent law

a ( 1 + b ) => distributive property

a ( 1 ) => boundedness law

a => identity property

**sima****Guest**

please help mi , proof of de morgans low: (xy)'=x'+y'

**Dharmendra Kumar Verma****Guest**

for every x in a Boolean

algebra there is a unique x' such that

x + x' = 1 and x x' = 0

So it is sufficient to show that x'y' is the complement of x + y. We'll do this by showing that

(x + y) + (x'y') = 1 and (x + y) (x'y') = 0

(x + y) + (x'y') = [(x + y) + x'] [(x + y) + y'] OR distributes over AND

= [(y + x) + x'] [(x + y) + y'] OR is commutative

= [y + (x + x')] [x + (y + y')] OR is associative

= (y + 1)(x + 1) Complement, x + x' = 1

= 1 1 x + 1 = 1

= 1 Idempotent,

x x = x

Also,

(x + y)(x'y') = (x'y')(x + y) AND is commutative

= [(x'y')x] + [(x'y')y] AND distributes over OR

= [(y'x')x] + [(x'y')y] AND is commutative

= [y'(x'x)] + [x'(y'y)] AND is associative

= [y'(xx')] + [x'(yy')] AND is commutative

= [y' 0] + [x' 0] Complement, x x' = 0

= 0 + 0 x 0 = 0

= 0 Idempotent, x + x = x

Pages: **1**