Boolean Algebra and Nodes

The Algebra

Let A, B, C, … be diagnostic tests or, more precisely, the Boolean variables that hold the answers to “Did test A come out positive?” and so on. Boolean negation, alias NOT, swaps T and F, indicating, in our example, whether a test came out negative:

¬A = (not A) = (false if A is true; true if A is false) = (F if A, otherwise T).

Note that ¬(¬A) = A. Other basic operations are AND and OR:

AND (“Did both A and B come out positive?”):

A ∧ B = (A and B) = (T if both A and B, otherwise F);

OR (“Did A, B, or both, come out positive?”):

A ∨ B = (A or B) = (F if neither A nor B, otherwise T) =¬(¬A ∧ ¬B)

The mirror image of the rightmost identity also works:

A ∧ B = (A ∨ B) = (F if one or both of A and B are false, otherwise T).

Set theory involves set intersection (∩), union (∪), and complementing, which are the precise analogs of ∧, ∨, and ¬, respectively.

OR and AND are associative operations: More than two terms can be ORed (or ANDed), in arbitrary order, to reflect “at least one true” (“all true”). Distributive properties include

The former may be read: To be a “female diabetic or female with hypertension” means to be a “female with diabetes or hypertension.” Self-combination:

Finally, test A must be either positive or negative, but cannot be both:

The former expression is a tautology, that is, a necessarily true proposition.

The OR described so far is the inclusive OR, as in the “or both” above. Informatics (checksums, cryptography) makes frequent use of the exclusive OR, abbreviated EXOR. Equivalence (=), in the sense of having the same truth value, and EXOR are each other's negations:

Now, ((A EXOR B) EXOR C) is true if just one or all three terms are true. Extending this rule to repeated EXORs of multiple Boolean terms, one finds that the result is true if the number of true terms is odd and false if it is even.

The Implication Symbol

The implication symbol (→) is a treacherous abbreviation:

That is, if A, then the expression reproduces the truth value of U; if not A, then the result is T—regardless of U!

...