Computer Science GRE Study Guide, Boolean operators

Table of Contents

III. Theory and Mathematical Background – 40%

C.     Discrete structures

1.      Mathematical logic

d.      We may express all Boolean operators using other operators. Said differently, there are logical equivalents for each Boolean operator using other operators. The result is that one does not really need all of the Boolean operators to express Boolean functions. It is possible to use just a subset of the operators. Any subset of Boolean operators that can express all Boolean functions is complete. You will note that it is impossible to have a complete set of operators without including at least one negating operator. Here are some examples of logical equivalence

i.        P Ú Q = Ø(ØP Ù ØQ)

ii.      P Þ Q = ØP Ú Q

iii.    P Û Q = (P Þ Q) Ù (Q Þ P) (of course!)

iv.    P Å Q = Ø(P Û Q)

e.       If you have a statement that always evaluates to true, then it is a tautology (or is valid). If you create a statement that always evaluates as false, then it is a contradiction. We say that two statements p and q are logically equivalent, written p º q, if p Û q. If a statement has at least one way to evaluate to true, then we say it satisfiable.

f.       Logic gates are graphical representations of Boolean logic. The symbols are in the instructions for the test. They include graphical representations for AND, OR, XOR, NOT, NAND, and NOR. NAND is an AND followed by a NOT. NOR is an OR followed by a NOT. A circuit is a bunch of logic gates connected together. We can represent any circuit using a Boolean statement (although it may be very complex statement).

⇒ Next section

Liked it? Take a second to support Hunter Hogan on Patreon!