Propositional Logic
Propositional logic is kind of like arithmetic, where instead of working on numbers, it works on the values "true" and "false", and instead of operations like addition and multiplication, the operations are "and", "or", "if/then", etc. Operations in logic usually take two values as input, except the "not" operator which takes only one. For logic operations with two inputs there are four possible combinations: (1) both inputs are true, (2) both are false, (3) the first is true and the second is false, and (4) the first is false and second is true. Operations are organized into truth tables (see below) showing the results of all four combinations.
| ∧ AND | ||
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
| ∨ OR | ||
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
| ⊕ EXCLUSIVE OR | ||
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
| → IF-THEN | ||
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
| ↔ IF AND ONLY IF | ||
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
| ¬ NOT | ||
| T | F | |
| T | T | |
A value that can be true or false is a proposition and are represented by letters. Often the letters P and Q are used.
Logical operators can be combined to form complex statements. One example of a logical statement is (P→Q)↔(¬Q→¬P). This statement justifies a method of mathematical proofs called contraposition.
Predicate Logic
Predicate logic consists of predicates, atoms, and variables. Atoms are the nouns of predicate logic, and can represent numbers, objects, or people. Variables stand for atoms. Predicates show the relationships between atoms and variables.
There are many different notations for predicate logic. The notation I will use is based on the Prolog programming language. In this notation, predicates and atoms begin with lower case letters and variables begin with capital letters. Predicates are written first, followed by their arguments in parenthesis, separated by commas. The arguments are atoms or variables. In the example inside(X, box), the term inside is a predicate and its arguments are X and box. The term X is a variable and the term box is an atom. The expression can mean "X is inside the box." A predicate with its arguments has a value of true or false.
Quantifiers
Variables in predicate logic are quantified to indicate if they stand for a single value or for any value.