## Propositional Logic

A proposition (often denoted by capital letters P, Q, etc) is a statement, that can be either true or false. Its negation Β¬P is obtained by prepending “it is not true that …” to P. If you negate twice, you get P back again: `Β¬(Β¬P) = P`

.

Two propositions are equivalent `P βΊ Q`

if their truth values are same.

P βΊ Q | Q = 1 | Q = 0 |

P = 1 | 1 | 0 |

P = 0 | 0 | 1 |

We can join 2 propositions by 2 logical operations ‘and’, ‘or’, ‘exclusive or’:

P β§ Q | Q = 1 | Q = 0 |

P = 1 | 1 | 0 |

P = 0 | 0 | 0 |

P β¨ Q | Q = 1 | Q = 0 |

P = 1 | 1 | 1 |

P = 0 | 1 | 0 |

P β Q | Q = 1 | Q = 0 |

P = 1 | 0 | 1 |

P = 0 | 1 | 0 |

Implication: P implies Q means either ‘P is false’ or ‘P is true and Q is true’. Implication is fundamental to science. Scientists want to establish `( (P βΉ Q) β§ P ) βΉ Q`

. One more to note: `(P βΉ Q) βΊ (Β¬P β¨ Q)`

.

P βΉ Q | Q = 1 | Q = 0 |

P = 1 | 1 | 0 |

P = 0 | 1 | 1 |

### Transforming Logical Expressions

Logical expressions often consist of many joined subject expressions. First, associative law:

```
(P β¨ Q) β¨ R βΊ P β¨ (Q β¨ R) βΊ P β¨ Q β¨ R
(P β§ Q) β§ R βΊ P β§ (Q β§ R) βΊ P β§ Q β§ R
```

Second distributive law, when joining ‘and’ and ‘or’:

```
P β§ (Q β¨ R) βΊ (P β§ Q) β¨ (P β§ R)
P β¨ (Q β§ R) βΊ (P β¨ Q) β§ (P β¨ R)
```

Third De Morgan’s law:

```
Β¬(P β§ Q) βΊ Β¬P β¨ Β¬Q
Β¬(P β¨ Q) βΊ Β¬P β§ Β¬Q
```

Implication is equivalent to this expression below:

`(P βΉ Q) βΊ Β¬P β¨ Q`

## Predicate Logic

Propositional logic is about simple statements about individuals. Predicate logic is logic involving statements like “for all” or “there exists”, which is about a universe of discourse. We find many universes of discourse. In math, it is often like sets, e.g.: the set of real number. A famous statement is about swan.

- R: All swans are white. (Quantifier for all)
- Β¬R: There is a swan that is not white. (Quantifier for some)

We have 1 rule about two quantifiers: “for all x, P(x)” is equivalent to “it is not the case that there exists an x such that not P(x)”:

`βx P(x) βΊ Β¬(βx Β¬P(x))`

Equivalently, if there exists an x such that P(x) holds, is equivalent to it is not true that for all x, not P(x) holds.

`βx P(x) βΊ Β¬(βx Β¬P(x))`

### Set Notation

Predicate logic most often comes along in the guise of set theory. A set is just a collection of objects. More often we work in set R, i.e. the set of real numbers. Such a big set has a tendency to function like the universe of discourse in predicate logic. The objects that make up a set are called elements of the set.

In predicate logic, we have these 2 things together to define a set S and it complement S^{c}:

- A universe of discourse Ξ©, which is called universal set in set theory.
- Some statement P(x) which is true or false, depending on the value of x (which ranges over Ξ©).

```
S = {x β Ξ© | P(x)}
S
```^{c} = {x β Ξ© | Β¬P(x)}

There are 4 main set theoretic notions:

Subset | A set S is a subset of another set R, if every element of S is also an element of R. S β R. |

Intersection | The intersection of S and R is formed by all elements of S that are also elements of R. S β R. |

Union | The union of S and R is formed by all elements of S together with all elements of R. S β R. |

Difference | The difference of S and R is formed by all elements of S that are not in R. S \ R. |

## Functions and Graphs

A function consists of 3 things: 2 sets and a rule. The first set D is called the domain. The second set R is called the range. The rule specifies how, to every element of D, an element of R is associated.

`f: D -> R`

A function is a triple. If two functions are with the same domain, the same rule, but with different ranges, they are two different functions.

### Cartesian product

Let A and B be sets. The Cartesian product A Γ B is the set of all ordered pairs (a, b), a β A, b β B . The most famous example is R^{2} = R Γ R = {(x, y) | x β R, y β R}, as the notation of the plane.

### Graphs

Usually the graph is a subset of a Cartesian product. It is a quick and rather convenient visual representation of the function. And the graph just tells you exactly about a rule with which elements from the domain are associated to the elements in the range.

```
f: D -> R
Graph(f) = {(x, y) β D Γ R | y = f(x) }
```

### Injective and Surjective

For f: D-> R, if a β D, b β R, such that f(a) = b; then we call b ** the image** of a, and a

**of b.**

*an original*A function is called ** injective** if every b β R has

**at most**1 original. So injectivity of a function is about the number of solutions the equation f(a) = b can have.

A function is called ** surjective** if every b β R has

**1 original.**

*at least*A function is called ** bijective** if every b β R has

**exactly**1 original. (Both injective and surjective.) Also there is a function g, which goes from R to D, such that g(b) = a. Function g is called the inverse of f. If you are in a situation where you’re neither injective nor surjective, you often can remedy the situation by restricting domain and range to a part of the function which is then bijective and where you can define an inverse.

## Natural Numbers

The set of natural numbers N = {0, 1, 2, 3, … }.

The natural numbers have been created by God. All others, all other numbers that is, are the handiwork of man.

Kronecker, German mathematician

The existence of the natural numbers is postulated by a number of axioms: Peano axioms for the natural numbers:

- 0 is a natural number.
- Every natural number n has a successor that is also a natural number n’.
- 0 is not the successor of any natural number.
- Natural numbers whose successors are equal, are themselves equal.
- If a set, X, contains zero and for every natural number n, it also contains its successor n’, then X contains all of N, or put differently N as a subset of X. (Famous principle of mathematical induction)

Addition | n + 0 = n n + m’ = (n + m)’ |

Multiplication | n * 0 = 0 n * m’ = (n * m) + n |

## The other numbers

### Negative numbers

Definition: the number -a, where a is a natural number, is the solution to the equation x + a = 0.

### Rational numbers

These numbers have been introduced from a need from economics. It is needed to divide things.

`Q = { (p, q) | p β Z, q β Z \ {0} }, Z is integer`

Addition | (p, q) + (r, s) = (ps + qr, qs) |

Multiplication | (p, q) * (r, s) = (pr, qs) |

### Real numbers

Due to the theory of Pythagoras, a^{2} + b^{2} = c^{2}, if a = b = 1, c will be β2, which is not a rational number. For every rational number we can decide whether it’s bigger or smaller than β2. Because if p/q is smaller than β2 that would imply that p^{2}/q^{2} is smaller than 2. But for 2 integers I can always decide whether p^{2}/q^{2} is smaller than 2 or bigger than 2. So we can make a set of all rational number p/q:

`{ p/q β Q | p2/q2 < 2 }`

The set has no largest element, we define β2 as the supreme of this set. In this way, every element of the real line corresponds to a real number.

### Complex numbers

They arise again from the need to solve a certain equation x^{2} = -1. In general, a quadratic equation has two roots. It might be interesting to postulate that any quadratic equation has two roots. So a number i is introduced, such that i^{2} = -1. A complex number is a pair of real numbers (a, b), also written as `a + ib`

. The set of complex numbers is the set of all the pairs (a, b) such that a and b are real numbers.

## Proofs

A proof is just a bit of precise reasoning. It is hard to be precise. Some types of proofs:

Transformation | `a x` to derive x |

Induction | 1 + 2 + 3 + … + n = n (n + 1) / 2 |

Contradiction | Theorem: There are infinitely many prime numbers. |

Exhaustion of possibility | Theorem: β2 β Q |

Existence | 100 drawers, 101 socks. Assume each sock lies in one of the 100 drawers. Then there is one drawer with at least two socks in it. |

## My Certificate

For more on Logic for Economists, please refer to the wonderful course here https://www.coursera.org/learn/logic-for-economists

*I am Kesler Zhu, thank you for visiting my website. Check out more course reviews at https://KZHU.ai*