## 2.1. Logical Notation

### Propositional logic

You should be familiar with propositional logic. We will use the following notation.

1. AB is true if both A and B are true. That is, symbol ∧ means and. We will use that symbol or write out the word and.

2. AB is true if either A or B is true or if both are true. That is, symbol ∨ means or, meaning the inclusive or. We will use that symbol or write out the word or.

3. ¬ A is true if A is false and is false if A is true. ¬ is read not.

4. AB is true if either A is false or if B is true. Think of ⇒ as meaning A implies B. That is, if A is true then B is true. But be aware of its definition,

AB means (¬A) ∨ B.
Notice that, if A is true and AB is also true then B must be true. Work it out.

5. AB means (AB) ∧ (BA). Read AB as saying A and B are logically equivalent.

By convention, ¬ has the highest precedence, followed by ∧, then ∨, then ⇒, with ⇔ having the lowest precedence. We use parentheses to override precedence rules.

### First order logic

We will need to make use of elementary first order logic, which allows us to make logical statements about things in some universe of discourse. For now, let's assume that the universe of discourse consists of nonnegative integers.

1. A predicate takes zero or more arguments and yields either true or false. A predicate on one parameter is a property of a thing. For example, even(x) might be true if x is even. Predicate even is the property of evenness. A predicate with two parameters is a relationship between things. For example, greater(x,y) might be true if x > y.

2. x A is true if logical statement A is true for all values x in the universe of discourse. For example, ∀ x (greater(x,y) ∧ greater(y,z) ⇔ greater(x,z)) is true, since if x > y and y > z then surely x > z.

3. x A is true if there is at least one value of x that makes A true. For example, ∃ x (greater(x, 0)) is true.

4. Symbols ∀ and ∃ are called quantifiers. The formula to with a quantifier applies can also contain quantifiers. For example, ∃ x (∃ y (greater(x, y))) says that there exists a value x so that there exists a value y so that x > y. Clearly, that is true.