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:

DeMorgan's laws

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

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

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