For those who know Boolean algebra...

My prof in my digital logic design course neglected to explain the implication operation properly and I’m having a hard time understanding what to do in a question on my current assignment. All the references (friends and web) I’ve tried don’t give me a very good explanation with regards to this problem, so here goes…
The question is basically as follows:

a) Show if the implication operation x–>y defined in the table is commutative and associative.

x   y   x-->y
0   0     1
0   1     1
1   0     0
1   1     1

Finding the minterm expansion gives the function x’+y, which is obviously commutative given it is an OR function, and I suppose it’s associative as well since there are only two variables, although I’m unsure if there’s anything more to the explanation than just that.

b) Is the operation (x–>y)(y–>x) commutative?

Since (x’+y)(y+x’) = (x’+y) = (y+x’) I assume this operation is commutative.

Then again, I’m not entirely clear on what x–>y and y–>x are supposed to mean. I guess this is my main problem: I don’t understand the implication function.

Thanks very much to whoever can help!

Well… x–>y is read “x implies y” and the --> is an operator just like the union symbol is used for AND and the intersection symbol is used for OR. Boolean logic was something I studied on my own, rather than in school, and it’s been a while, and I can’t quite remember all of the details.

The first argument (x) is called the “premise” and the second (y) is called the “conclusion”. If the premise false it doesn’t matter what the conclusion is, the function is true; otherwise, the value of the function is equal to the value of the conclusion (as show in your truth table).

I recall that, in general, the same rules for associativeness and commutativeness apply in Boolean algebra as in standard algebra, but you have to be careful to test your results in both directions. That is, try swapping your premise and conclusion and apply it to your equations before making a decision.

In application, the implication function can be used in computer systems to describe IF/THEN logic, looping conditions, that sort of thing.

I don’t know if that’s any more or less muddy than what you already had; like I said, it’s been a long time. If you don’t get anything more helpful and you want to go over it some more, please post again, and I’ll be happy to go through my old references and come up with something (hopefully) more lucid.

Thanks for your response, Captain Jack. I had a brainwave after re-reading the wikipedia article on implication and figured it out. For part a) it involves:

x–>y = x’+y and y–>x = y’+x, so the function is not commutative but it is associative since only 2 variables are involved and they are OR’d.

For part b) the operation (x–>y)(y–>x) is commutative since (x’+y)(y’+x) = (y’+x)(x’+y), obviously. I’m pretty sure this is right.

I dunno, maybe this would help? If so, can you explain it to me? Way over my head! :slight_smile:

Okay, even though I’m taking a course on Algebra this year, we have not worked on bolean algebra yet.

Therefore, all of my intellectual experiments may be false :wink:

a) Well, actually I don’t even know what a minterm expansion is (I looked it up though), I’d approach this differently.
Commutative - no, see the function table why.
If I get it right, commutative means that x => y = y => x. That is not true, if you set x = 0, y = 1.
Associative - no. Again, simply prove it by setting values, e.g. x = z = 0, y = 1.
(x => y) => z =/= x => (y => z)

Whoops, I forgot b) I guess that means (x => y) * (y => x)?
If so, we look at the case x = y, which is true in either case. Now for the case x =/= y. That means x = 1 and y = 0 or the other way round, not that it would matter. The result is always 0 since it’s now always 1*0 or the other way round. Therefore, this operation is commutative.

Tell me if I just got it all way wrong or if this might be looking right to you…

For those over their heads, a little simple programming makes things clear.
Captain Jack explained it best, so re-read his post first.

 x  y  x-->y
 0  0    1
 0  1    1

If the initial premise is false, you always know the outcome.

val = 12
if val != 12:
  print 'Fooey'

You know that x (“val != 12”) will always evaluate to FALSE, or zero, so it doesn’t matter what y (“print ‘Fooey’”) is. The point is that you always know the outcome --nothing.

Hence, x = 0 always implies certainty as to the outcome, without needing to recur to the value of y.

Admittedly, this seems a little backwards thinking for us. Why don’t we just write:

val = 12
if val == 12:

The difference is that this time the outcome of the expression is wholly dependant on y (“do_some_func()”). We know that x is true either way. But what does y do? Does it print “Fooey”? Or something else? Who knows?

Thus we could say:

 x  y  x-->y
 1  0    0

is the same as:

if 12 == 12:
  return 0

and that:

 x  y  x-->y
 0  1    1

is the same as:

if 12 == 12:
  return 1

Thus, to say that x implies y is a simple way of asking whether “positive” (or known/desired/etc) output of a complex expression is dependant on the first part (antecedent) or second part (consequent).

A result is commutative if you switch the antecedent and consequent and get the same result.

Associativity is just a tad more complex. Now we ask if

(x-->y)-->z == x-->(y-->z)

The best way to answer the question is to plug some numbers in.

Hope this helps.

Ok, I’m finally understanding it all now. Merci beacoup!

Mais oui, mon plaisir.

Just to be sure you get it right with your professor, remember that in order to be commutative or associative (or anything else) the test for commutativity (or whatever the adjective) must always prove true no matter what values you plug in for x and y (and z).

If it is false for even one possible set of values then the “implies” operation cannot be <insert proper adjective here>.


“For those who know boolean algebra…

I gaze across a field of marigolds,
glistening in the autumn light
and think of subtracting matrices
from one another
and solving for X
always, solving for X
in multivariable equations.

the end


X =



Where’s teh money???

I assume that I was right then (if anyone could confirm the results, please do so - or tell me if they are wrong)…sorry for simply solving the problem instead of explaining it properly. I know that it always sucks to see the solution before you actually think about the problem (I’m serious…) =/

Yup, I’m pretty sure your solution was correct, Myke.

valarking Thanks for trying, but you left z out of your denominator. That and your response time was 36 minutes, which is 35 minutes 31 seconds too long… :wink:

Aorus and Myke You need to make a table that looks like this:

  x   y   z   (x-&gt;y)   (y-&gt;z)   (x-&gt;y)-&gt;z   x-&gt;(y-&gt;z)
  0   0   0     1        1          1           1
  0   0   1     1        1          ...
  0   1   0     ...
  0   1   1

and see if the last two columns match pairwise.

x=20394709347209373=phi alph+34808n = 42

Duoas, yup, that’s what I did. Thanks. :slight_smile:

The z is there but it’s just invisible to human eyes.

so is the money…