Boolean Algebra Questions
Rosella Bowlan
i got really confused every time when i encounterd bit operations,especially those shifts,rotates,overflow things etc.I wonder if there's any book/article on the web introducing boolean algebra,which could give me a solid background of boolean algebra,thanks!
I don't know of any books on this subject, but here are some online resources... It sounds to me like what you want is to understand binary better to start with. Here is a little treatment of Binary from MathWorld, which is the web's best mathematics reference. Here is an applet on binary shift. There is a wikipedia article on Bitwise Operation. Ben Fry has created a good calculator that includes Bit Roll (Rotation) in it - be sure to look at the help on the calculator as it does much more than is obvious at first - try changing the Mode to Bin, for example.
I'm a retired college teacher now teaching things like Boolean logic to students in several middle schools (ages: 11-14). I taught that module for the first time last week and discovered to my chagrin that I had mixed two different notations. I'm teaching specifically logic expressions, with very little manipulation using the identities of Boolean algebra.
I hesitate to use the notation of programming because it seems Java and Python are equally popular, but with very different notations. Java's use of ^ for exclusive disjunction further muddles things.
Edit: OK, I've accepted an answer, and decided to use the engineering notation, but to present a table comparing notations near the end of the module. I chose end rather than beginning because I want the students familiar with one notation before I present the others. I'm going to start another question about how to explain + as OR.
I would, myself, provide them with a handout giving names to the concepts and various notations used for each. Then, I'd use the various symbols as naturally as possible, responding to the inevitable questions.
The rationale here is that students will likely see different symbols sooner rather than later if they do any reading or research outside your instruction. It is better that they have some preparation and at least a hint that the terminology isn't entirely consistent or standardized.
As per ctrl-alt-delor's response, I use different systems with different groups. It has been my experience that most of my students use no formal system of Boolean Algebra prior to beginning studies in CS, so I will typically start with whatever programming language they have the most experience with.
In my program they traditionally use Java. (Here's a hint from the trenches: while Java does indeed use ^ for $\oplus$, most students are unaware of this operator or its function. You may find that there are fewer translation issues for the students if you use !=, which accomplishes the same thing in a purely Boolean world. This gives you the side benefit of being able to describe $\overlineA \oplus B$ as A == B, which is instantly and intuitively understandable.)
No matter which system you use, it is worth it to give all of the symbols once when doing the truth tables. (I also include the gates when I do this). This way, they will at least see the systems once, and if you accidentally write a symbol from the wrong system on the board while you are talking, they will not become nearly as confused.
You may still have to correct what you wrote for the sake of consistency, but at least they will know that there are additional notational systems in the first place, so they'll see your correction as a notational translation instead of something more perplexing.
I am recently studying computer science and I was introduced into boolean algebra. It seems that boolean algebra is used to simplify logic gates in hardware in order to make the circuit design minimal and thus cheaper. Is there any similar way that you can use it to reduce the number of code lines in your software in higher level languages like C++, C# or any other language?
Note it is not a tool for just simplifying logic gates in hardware as well. However, it can sometimes be used for such cases (as well as for the opposite, or for completely different purposes).
For example, if your program contains an overly complicated boolean expression or sequence of conditionals, boolean algebra might help you to simplify the expression and the surrounding code. But that does not necessarily lead to less lines of code. In fact, sometimes complex one-line boolean code snippets get more maintainable when you split them up into several lines of code, and boolean algebra can help you to do this correctly.
So IMHO your question is like "can I use a pocket calculator to find the shortest route when traveling from A to B"? Sure you can, when you take a map with distance information for individual roads and use the calculator to add them up, and then pick the route with the smallest sum. But you could also use the calculator for finding longer routes, or for calculating completely different things.
This is a list of checks on the object person, and will exit the function as soon as one of those is true. The meaning of that is pretty clear, and anyone that reads it, even a non-programmer, can understand what checks we're doing.
So no, you do not reduce the number of code lines using boolean algebra. You use it whenever there is a binary choice to be made. If your problem is complex, you are going to have a lot of choices in your software solution.
Well, OK. The reason electronics engineers want to reduce the number of logic gates in a circuit is probably a matter of construction cost and operational performance of their final product. They are building the very thing that will do the work in the end.
When you are programming in any language other than assembly, the computer in the end will not execute your code, but a transformed version of it. This transformation from the programmer friendly language to the computer friendly language may be called compilation. Boolean logic is indeed used by the compiler to achieve operational efficiency.
You may code in assembly and do the compiler's job yourself, but on a day-to-day basis, it becomes less and less worth the hassle. Modern compilers know more and more of the tricks, and better than you.
On the contrary, if you ask whether there exist a similar practice in higher-level languages, yes, it's called refactoring, which means applying well-defined transformations to code chat change the structure and not the behaviour. In the 90s, Martin Fowler published a book that is a catalog of probably the most recurring basic refactorings in object languages.
However in case of High-level languages it may result in more problems. HLL languages are designed for readability and ease of understanding. You can simplify your several lines of code into a single one, but it will become unreadable and complex, so much more time is required to grasp the idea of the code.Most of compilers perform such kind of optimizations by default.
All in all, I suggest not to think a lot about reducing lines of code, but consider behavior of the program in runtime, memory usage and architectual design. Generally when you are applying Boolean Algebra to your circuits you are acting as a compiler for most of existing languages.
Usually, breaking a complex line into multiple, simpler lines will increase readability without significantly reducing performance. Only if benchmarking shows that there is a unacceptable performance issue should you refactor to increase performance at the expense of readability.
To add to the existing discussion, including its idea that fewer lines is good if it also enhances readability, I'll just mention one thing you can do with Boolean algebra in a language where all values all truthy or falsy, such as Python. Here's a FizzBuzz solution in Python, written in a style that's achievable in just about any high-level language:
In this case the benefit came because the same function needn't be mentioned in two lines of which only one is called, and we therefore seek an expression that equals this argument in every scenario, and we can get it using this not-all-that-little-known fact about how Python handles Boolean operators. I'd hate to have to write
You'll find several Python solutions to FizzBuzz here, using this trick but differing in what further Pythonic tricks they use to shorten the code even further. (They even show you can do the whole thing in one line, once you learn what happens when you multiply strings by integers.) These might be less conducive to readability, although of course they're worth learning how to do.
I need to show what law/theorem/postulate is used for each step of the proof - and I don't even know where to start. The last time I did any sort of algebra was at least 7 years ago, and even then it was very basic.
Being thrown into Boolean algebra, only provided a sheet with all the theorems/etc... is proving to be impossible for me. I understand the methodology behind mathematical proofs and boolean simplification, I just don't see what theorems/laws can be used when I look at these....
Essentially, we manipulate the equation in whatever way possible, trying to make the left-hand side look like the right-hand side. There's no real magic method here, we just keep trying until we succeed.
I see that Rebecca has already worked through the second one. I will concur heartily with her that there isn't just one magic method. Some problems are amenable to a few slick tricks. Some may require a great deal more manipulation, and several of the rules are used. Keep at it, and get a lot of practice, to see how and when certain methods help us.
Boolean Algebra questions and answers will assist students in quickly understanding the basics of the concept. These questions can be used by students to acquire a quick overview of the topics and to try answering them in order to improve their knowledge. Learn the complete solutions for each question to check your answers. To understand more about Boolean Algebra, click here.
c80f0f1006