The Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.


Math Forum » Discussions » Math Topics » discretemath

Topic: Sets of Dependent Boolean Equations
Replies: 5   Last Post: Nov 14, 2017 8:43 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Steven Evans

Posts: 14
Registered: 7/20/06
Sets of Dependent Boolean Equations
Posted: Nov 12, 2017 7:00 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

I'm working with sets of dependent boolean equations. In order to describe what I mean, here's an example.

A = ~B&C|J
D = ~J&B|~C
E = D&F
H = E&~A|D

As you can see, certain equations are dependent on the values of other equations.

Now suppose I think of two instances of this set. In one instance, I let B=0. In another instance, I let B=1. Changing the value for B, will ultimately change the value for H. So let H(B=0) describe H when B=0, and H(B=1) describe H when B=1.

So H(B=0) would make the equations look like this:

A = C|J
D = ~C
E = D&F
H = E&~A|D

And H(B=1) would make the equations look like this:

A = J
D = ~J|~C
E = D&F
H = E&~A|D

Now what if I wanted a new set of equations, which describes:

H(B=0) | H(B=1)

How would I do it so that my new set will still have the same form as before? When I say "same form", I mean a new set of equations which maintains the same dependence as before, yet provides the same answer as H(B=0) | H(B=1). For example:

A = C|J
D = ~J&C
E = ~D|F
H = ~E|A&D

This example isn't correct because I don't know how to do it. But the idea is that the variables would be redefined so that it would give me a correct truth table with a similar structure (i.e. approximately four equations which are still dependent on J, C, and F).

The following set would yield the correct result. However, it doesn't have the similar form that I'm talking about:

A0 = C|J
D0 = ~C
E0 = D0&F
H0 = E0&~A0|D0

A1 = J
D1 = ~J|~C
E1 = D1&F
H1 = E1&~A1|D1

H = H0 | H1

As you can see, it doubles the number of equations, which means it doesn't have a similar form as the first example.

It would seem that a simpler form, such as the first example, could be obtained. This is because the final equation is still a function of three variables, J, C and F. So its truth table wouldn't be any larger. Because of this, it makes sense that doubling the number of equations wouldn't be necessary.

My suspicion is that what I'm trying to do isn't very common. I haven't been able to find anything online which talks about dependence boolean equation sets, or any books either. It may be that there's a more correct name for this, but I just don't know it. Perhaps someone's already figured out how to do this. If that's the case, and any of you are aware, I'd love to have you point me in the right direction so that I could learn more about it. If not, does anyone know of a way to accomplish what I'm asking?

Thanks for your time, and I look forward to any suggestions that anyone is able/willing to give.



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.