Boolean Algebra Boolean algebra deals with formalised logic and reasoning, the results of which can only be one of two (binary) values - true or false. In QuickBasic these are represented by the values -1 and 0 respectively. However, when we go to bitwise operations true will be represented by the binary digit 1. These two values can be generated by comparing two, non-boolean, values and there are six different comparison methods, with corresponding operators, that can be used. These six different comparisons are equality, inequality, greater than, less than, greater than or equal to and less than or equal to, with the corresponding standard operators =, <>, >, <, >=, <=. While these comparison operators are useful, it is often required to be able to manipulate the results of two or more such comparisons. For this reason there are also a group of operators that work exclusively with the boolean results generated. In order to illustrate the way these operators work I will be using truth tables in conjunction with the textual explanation. Standard truth tables usually have one or two boolean values on the left (marked either A or A and B) which are the input values, and always a single value on the right (marked either B or C), which is the output value. For each operator I have given two truth tables, the left hand one for purely logical operations and the right hand one for bitwise operations. NOT - The first operator that I am dealing with is the only boolean unary operator that I am aware of, that is it takes a single input value returns a single value. The operation performed by this operator is to make it's output the inverse of it's input, so true becomes false and vice versa. +---------------+ +-------+ | NOT | | NOT | +-------+-------+ +---+---+ | A | B | | A | B | +-------+-------+ +---+---+ | FALSE | TRUE | | 0 | 1 | | TRUE | FALSE | | 1 | 0 | +-------+-------+ +---+---+ The other eight operators are all binary operators in the sense that they take two input values and return a single value. AND - The action of this operator is that the output is true only if both the inputs are true, otherwise it is false. +---------------------+ +----------+ | AND | | AND | +-------------+-------+ +------+---+ | A B | C | | A B | C | +-------------+-------+ +------+---+ | FALSE FALSE | FALSE | | 0 0 | 0 | | FALSE TRUE | FALSE | | 0 1 | 0 | | TRUE FALSE | FALSE | | 1 0 | 0 | | TRUE TRUE | TRUE | | 1 1 | 1 | +-------------+-------+ +------+---+ OR - Inclusive OR. The action of this operator is that the output is false only if both inputs are false. An alternative definition for this operator is that the output is true if either or both of the inputs are true. +---------------------+ +----------+ | OR | | OR | +-------------+-------+ +------+---+ | A B | C | | A B | C | +-------------+-------+ +------+---+ | FALSE FALSE | FALSE | | 0 0 | 0 | | FALSE TRUE | TRUE | | 0 1 | 1 | | TRUE FALSE | TRUE | | 1 0 | 1 | | TRUE TRUE | TRUE | | 1 1 | 1 | +-------------+-------+ +------+---+ XOR - Exclusive OR. The action of this operator is that the output is true only when one of the inputs is true and the other one is false. An alternative definition for this operator is that the output is true if either of the inputs is true but not if both are. This is the logical equivalent of the inequality operator i.e. <>. +---------------------+ +----------+ | Exclusive OR | | XOR | +-------------+-------+ +------+---+ | A B | C | | A B | C | +-------------+-------+ +------+---+ | FALSE FALSE | FALSE | | 0 0 | 0 | | FALSE TRUE | TRUE | | 0 1 | 1 | | TRUE FALSE | TRUE | | 1 0 | 1 | | TRUE TRUE | FALSE | | 1 1 | 0 | +-------------+-------+ +------+---+ NAND - Not AND, inverse AND. The action of this operator is that the output is false only if both inputs are true. This is equivalent to inverting the output of the AND operator. +---------------------+ +----------+ | NOT AND | | NAND | +-------------+-------+ +------+---+ | A B | C | | A B | C | +-------------+-------+ +------+---+ | FALSE FALSE | TRUE | | 0 0 | 1 | | FALSE TRUE | TRUE | | 0 1 | 1 | | TRUE FALSE | TRUE | | 1 0 | 1 | | TRUE TRUE | FALSE | | 1 1 | 0 | +-------------+-------+ +------+---+ NOR - Not OR, inverse OR. The action of this operator is that the output is true only when both inputs are false. This is equivalent to inverting the output of the OR operator. +---------------------+ +----------+ | NOT OR | | NOR | +-------------+-------+ +------+---+ | A B | C | | A B | C | +-------------+-------+ +------+---+ | FALSE FALSE | TRUE | | 0 0 | 1 | | FALSE TRUE | FALSE | | 0 1 | 0 | | TRUE FALSE | FALSE | | 1 0 | 0 | | TRUE TRUE | FALSE | | 1 1 | 0 | +-------------+-------+ +------+---+ XNOR - Not Exclusive OR, inverse Exclusive OR. The action of this operator is that the output is false only when one input is true and the other is false. This is equivalent to inverting the output of the XOR operator. It is also the logical equivalent of the equality operator i.e. =. +---------------------+ +----------+ | NOT Exclusive OR | | XNOR | +-------------+-------+ +------+---+ | A B | C | | A B | C | +-------------+-------+ +------+---+ | FALSE FALSE | TRUE | | 0 0 | 1 | | FALSE TRUE | FALSE | | 0 1 | 0 | | TRUE FALSE | FALSE | | 1 0 | 0 | | TRUE TRUE | TRUE | | 1 1 | 1 | +-------------+-------+ +------+---+ A IMPLIES B - The action of this operator is that the output is false only when input A is true and input B is false. This is QB's IMP boolean operator. (NOTE - What we are dealing with here is an operator that is used in the formal logic of boolean algebra. The statement A ===> B is usually pronounced 'A implies B'. An alternative pronunciation is 'if A then B'. This operator is the means by which we state that one proposition implies another. Beware, this is maths and not either everyday english or programming terminology. In "pure" maths you would usually find this operator used on one (or both) sides of an equation.) +---------------------+ +----------+ | A IMPLIES B | | ===> | +-------------+-------+ +------+---+ | A B | C | | A B | C | +-------------+-------+ +------+---+ | FALSE FALSE | TRUE | | 0 0 | 1 | | FALSE TRUE | TRUE | | 0 1 | 1 | | TRUE FALSE | FALSE | | 1 0 | 0 | | TRUE TRUE | TRUE | | 1 1 | 1 | +-------------+-------+ +------+---+ IF AND ONLY IF - The action of this operator is that the output is false only if the two inputs have differing values. This is also sometimes referred to as the boolean equivalence operator, which is why the operator that QB uses to implement this operation is EQV. +---------------------+ +----------+ | IF AND ONLY IF | | <==> | +-------------+-------+ +------+---+ | A B | C | | A B | C | +-------------+-------+ +------+---+ | FALSE FALSE | TRUE | | 0 0 | 1 | | FALSE TRUE | FALSE | | 0 1 | 0 | | TRUE FALSE | FALSE | | 1 0 | 0 | | TRUE TRUE | TRUE | | 1 1 | 1 | +-------------+-------+ +------+---+ So far I have dealt with simple conditional statements such as C = A AND B, but as in the rest of algebra more complex statements can be built up using these simpler forms and parentheses, for example X = A OR (B AND C). Just as in the rest of algebra, some of these expressions can be proved to be overly complex and such expressions can be simplified. The way these simplifications are carried out are governed by rules, which in mathematics are generally termed laws. I will only be covering those laws which are valid from a programmers standpoint, and I will try to use everyday terminology where possible. The first law states that if you have an expression that can be regarded as a series of OR statements and one of these expressions always evaluates to true then the whole of the statement can be reduced to the value true. For example LET Q = 2 X = (A AND B) OR (C XOR D) OR (Q^0 = 1) can be reduced to X = true. The next law states that if you have an expression that can be regarded as a series of AND statements and one of these expressions always evaluates to false then the whole of the statement can be reduced to the value false. For example LET Q = 2 X = (A OR B) AND (C XOR D) AND (Q^0 <> 1) can be reduced to X = false. The next law states that if you have an expression such as X = A OR (A AND B), or an expression such as X = A AND (A OR B) then the expression can be simplified to X = A. The final law that I will deal with states that if you have an expression such as X = A OR false, or an expression such as X = A AND true, then the expression can be simplified to X = A. ___________________________________________________________________________ Putting it all together This rest of this document deals with how the above is used in conjunction with programming. Boolean algebra The first thing that I should point out is that the last two boolean operators (A implies B, if and only if) are normally only used for program specification (such as in the specification language Z) and not in everyday programming. The next thing to point out is that only six of the remaining operators are obviously implemented in QB. They are AND, OR, NOT, XOR, IMP and EQV. Do not despair because XNOR is implemented, but with a different name, and the operators NAND and NOR are easily implemented with the use of parentheses and the operators AND, OR and NOT. If you check out the truth table for XNOR you will see that the results are the same as for the equivalence operator. Both NAND and NOR are almost as easy to implement as XNOR. All you need to do is to use the inversion operator (NOT) on the output of either the AND (NAND) operation or the OR (NOR) operation as illustrated below. NAND NOT(A AND B) NOR NOT(A OR B) One thing to be careful of is the fact that NOT A AND NOT B is equivalent to NOT(A OR B), and NOT A OR NOT B is equivalent to NOT(A AND B). This is because both NAND and NOR invert the OUTPUT of the AND and OR operators respectively, and not the input. Bitwise Operations While more commonly associated with assembly language programming, the manipulation of the individual bits (from BInary digITS) in a number do have thier uses in QB. For example if you wish to ensure that a number that is passed is less than 256, it is much quicker to bitwise AND the test-value with &HFF (255 decimal) than to find the modulus of the division of the test-value by &H100 (256 decimal), or to put it another way TestValue = TestValue AND 255 is much faster than TestValue = TestValue MOD 256 Bitwise AND The action of the bitwise AND is to 'mask' the desired bits and to drop all others. For example, using the above variable and its associated mask. If TestValue initially has the value of 511 decimal, 1FF hex, 0000000111111111 binary and we AND it with FF hex, 255 decimal, 0000000011111111 binary the result will also be FF Hex. 0000000111111111 AND 0000000011111111 = 0000000011111111 This is especially useful when you are using interrupts and you need to load one of the registers with a guaranteed byte value (as opposed to a word value). Bitwise NOT This operation performs what is termed an inversion - all the bits that were originally 0 become 1 and the bits that were 1 become 0. So if we have a byte with a value of 170 decimal (AA Hex, 10101010 binary) and we perform a bitwise NOT operation on it we get the result of 85 (55 Hex, 01010101 binary). NOT 10101010 = 01010101 Bitwise (inclusive) OR The action of the bitwise OR operator is as follows. Each bit in the result will be set to 1 unless the corresponding bit in both input values is a 0. This is best illustrated with an example. Say we have a value of 170 decimal (AA Hex, 10101010 binary) and we OR it with a value of 87 decimal (57 Hex, 01010111 binary) we will get a result of 255 (FF Hex, 11111111 binary). 0000000010101010 OR 0000000001010111 = 0000000011111111 Bitwise XOR This operator has a more complex action the preceding one. Each bit in the result will be set to one if the corresponding bits in the input values are not equal. So taking the same values as used in our example for the bitwise (inclusive) OR operator we get a result of decimal (FD Hex, 0000000011111101 binary). 0000000010101010 XOR 0000000001010111 = 0000000011111101 This can be useful where we wish to have a value that alternately switches between true and false in QB where true is represented by -1 decimal. This is because the scheme adopted to represent negative numbers (called 2's compliment) means that at the binary level -1 is represented by 1111111111111111. To illustrate this here is a small program. Test% = 0 DO Test% = Test% XOR -1 IF Test% THEN PRINT "TRUE" ELSE PRINT "FALSE" END IF LOOP Simply run this and when you have a nice long list of text on screen, hit control-break to see that it has worked. Some other areas where bitwise XOR is used are in graphics (as are the other bitwise operations mentioned here), simple checksums and simple encryption and to efficiently swap whole values in those languages that don't have a swap command. NIGEL TRAVES (9/1996 - Revised 6/1997 - revised for QB 1/1998)