Short explanation of mathematical logic and links to practice problems.

Here is a link to practice problems for mathematical logic.

There are four major logical operators we will be using.

AND, represented by the symbol ^.
OR, represented by the symbol v.
NOT, represented by the symbol ~
IMPLIES, represented by the symbol => (supposed to be an arrow, but no single symbol availabe to the blogger editor works.

There are only two values in logic, TRUE (represented by 1) and FALSE (represented by 0). A logical variable, often represented by the letters p, q and sometimes r, though other letters are legal, is an ordered list of 1s and 0s, known as a bitstring.

Here are the rules for AND, an operator that needs two variables.
1 ^ 1 = 1
1 ^ 0 = 0
0 ^ 1 = 0
0 ^ 0 = 0


In English, the simplest way to explain AND is to say p ^ q is only true if BOTH p and q are true, otherwise the operation produces a false outcome.


Here are the rules for OR, an operator that needs two variables.
1 v 1 = 1
1 v 0 = 1
0 v 1 = 1
0 v 0 = 0



In English, the simplest way to explain OR is to say p v q is true if EITHER p or q are true, and only false if both are false.


NOT is an operator that applies to a single variable.


~1 = 0
~0 = 1


NOT is like a switch. "NOT true" is the same as "false" and "NOT false" is the same as "true".


Mathematical logic is similar to set theory, where AND is like intersection, OR is like union and NOT is like the complement (or bar over the set).


IMPLIES is an operation in mathematical logic that doesn't have an analog to a basic set theory operator.  The rules are as follows.


1 => 1 = 1
1 => 0 = 0

0 => 1 = 1
0 => 0 = 1


If you have trouble remembering the rules for p => q, it works the same as ~p v q, where the NOT at the beginning only applies to the variable p. (The standard order of operations in logic is left to right, unless there are parentheses and ~ only applies to the variable immediately following it.)