# Logic 1

Computer Logic:

1. Propositional Logic
2. 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:

pqp XOR q
TTF
TFT
FTT
FFF
p¬pqp→qq∨¬p
TFTTT
TFFFF
FTTTT
FTFTT

## DeMorgan's laws

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

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

p¬pq¬qp∧q¬(p∧q)(¬p)∨(¬q)
TFTFTFF
TFFTFTT
FTTFFTT
FTFTFTT

# 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

1. when use theorem, restate variable before use
2. 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:

1. universal quantifier: for all
2. existential quantifier: there exists

for the other quantifier, they included:

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

## Notation

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

1. for all: ∀
2. R: domain or replacement set
3. x2 + 3 ≥ 0: predicate
4. there exist: ∃
• when transfer there exist to English, we should add: such that

useful notation:

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

1. ∀x ∈ R, ∀y ∈ R, x + y ≥ x
2. ∀x, y ∈ R, x + y ≥ x
3. for all real numbers x and y, x + y ≥ x