# Logic 1

**Computer Logic:**

- Propositional Logic
- Predicate Logic

## proposition Logic

- basic block is proposition: whither true or false
- cannot be question, command, and contain variables
- could represented by using some variables
- shorthand notation:

**and**: shorthand ∧

**or**: shorthand ∨

**not**: shorthand ¬

**implies**: shorthand →

**if and only if**: ↔

**exclusive or**: XOR

**logically equivalent to**: ≡

for implies, it often written out as "if/then" in English; if p, then q, p is called the "hypothesis" and q is the "conclusion."

Examples:

p | q | p XOR q |
---|---|---|

T | T | F |

T | F | T |

F | T | T |

F | F | F |

p | ¬p | q | p→q | q∨¬p |
---|---|---|---|---|

T | F | T | T | T |

T | F | F | F | F |

F | T | T | T | T |

F | T | F | T | T |

## DeMorgan's laws

$$ ¬(p∧q)≡(¬p)∨(¬q) $$

$$ ¬(p∨q)≡(¬p)∧(¬q) $$

p | ¬p | q | ¬q | p∧q | ¬(p∧q) | (¬p)∨(¬q) |
---|---|---|---|---|---|---|

T | F | T | F | T | F | F |

T | F | F | T | F | T | T |

F | T | T | F | F | T | T |

F | T | F | T | F | T | T |

# Logic 2

$$ p→q≡(¬p)∨q $$

or

$$ ¬¬p≡p $$

By Apply DeMorgan's law to the formal above, we get:

$$ ¬(p→q)≡¬(q∨(¬p))≡p∧(¬q) $$

## quantifiers

∀: for all

∃: there exists

*example: For every integer x, x2≥x*

## Scope for quantifier

- when use theorem, restate variable before use
- statement end when new variable introduced

# Logic 3

$$ ¬∀x,P(x)≡∃x,¬P(x) $$

$$ ¬∃x,P(x)≡∀x,¬P(x) $$

*example:*

For any cookie c, if c is not small and c is tasty, then c is not healthy

$$ ∀c∈cookies,(¬S(c)∧T(c))→¬H(c) $$

then, wrap a negation

$$ ¬∀c∈cookies,(¬S(c)∧T(c))→¬H(c) $$

it becomes

$$ ∃c∈cookies,¬((¬S(c)∧T(c))→¬H(c)) $$

finally, apply logic 2

$$ ∃c∈cookies,(¬S(c)∧T(c))∧H(c) $$

drop the harmless parentheses

$$ ∃c∈cookies,¬S(c)∧T(c)∧H(c) $$

**Negation: There is a cookie c, such that c is not small and c is tasty but c is healthy**

## contrapositive

fact:

$$ p→q≡¬q→¬p $$

$$ ∀x,p(x)→q(x)≡∀x,¬q(x)→¬p(x) $$

still take cookie as an example

For any cookie c, if c is not small and c is tasty, then c is not healthy

$$ ∀c∈cookies,(¬S(c)∧T(c))→¬H(c) $$

then, the contrapositive should be

$$ ∀c∈cookies,H(c)→¬(¬S(c)∧T(c)) $$

simplified

$$ ∀c∈cookies,H(c)→S(c)∨¬T(c) $$

**For any cookie c, if c is healthy, then c is small or c is not tasty**

## negation

for the claim:

Claim: ∀x,y∈R∀x,y∈R, if x is irrational and y is irrational, then x+y is irrational.

¬(∀x,y∈R¬(∀x,y∈R, if x is irrational and y is irrational, then x+y is irrational).

∃x,y∈R,¬∃x,y∈R,¬(if x is irrational and y is irrational, then x+y is irrational).

∃x,y∈R,∃x,y∈R, x is irrational and y is irrational and x+y is rational.

## Propositions

- cannot contain variable
- cannot be question
- cannot state the claim
- true/false
- use symbol to turn complex propositions to simple one

**Negating**: p ¬p

## Implication

if propositions1, then, proposition2

propositions1 called hypothesis

propositions2 called conclusion

- represent by ->
- only false when T -> F
- doesn’t have to be any causal connection
- timeless and static

**Converse**: p → q q → p always a bug because implication frequently hold in only one direction

**Contrapositive**: p → q ¬q → ¬p equivalent to the original statement

• If it’s below zero, my car won’t start.

• converse: If my car won’t start, it’s below zero

• contrapositive: If my car will start, then it’s not below zero.

## Complex statements

simplified by using set of propositions with connectives

## Logical equivalence

two propositions p and q are logically equivalence if they are true if they are exactly for the same input value

- represent by p ≡ q

**Useful equivalence**

$$ p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) $$

$$ p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) $$

## De Morgan’s Laws

$$ ¬(p ∧ q) ≡ ¬p ∨ ¬q $$

$$ ¬(p ∨ q) ≡ ¬p ∧ ¬q $$

## Predicates and Variables

A statement that becomes true or false if you substitute in values for its variables.

x 2 ≥ 10 or y is winter hardy

- also state the condition x is better than loss type statement

## Quantifier

expresses how many of the values in the domain make the claim true

in math, we have three quantifier, and mainly use:

- universal quantifier: for all
- existential quantifier: there exists

for the other quantifier, they included:

- unique existence quantifier: there is a unique... such that

## Notation

$$ ∀x ∈ R, x_2 + 3 ≥ 0 $$

- for all: ∀
- R: domain or replacement set
- x2 + 3 ≥ 0: predicate
- there exist: ∃

- when transfer there exist to English, we should add:
`such that`

**useful notation:**

when state claim on two variable, we can write as:

- ∀x ∈ R, ∀y ∈ R, x + y ≥ x
- ∀x, y ∈ R, x + y ≥ x
- for all real numbers x and y, x + y ≥ x