– Closed: Sentence without a variable. ex:) 6+2=8, The grass is green.

– They must be closed to be truth/false.

– ex:) True: A square has equal side lengths.

False: A pentagon has 67 sides.

Open: It has a right angle.

– Symbol ~

Symbols: Representations of sentences, usually in letter form.

ex.) P: I passed my test.

negation: ~P

I did not pass my test.

To be true, both parts must be true.

– Or (Disjunction): Two things do not depend on each other. Symbol: V.

– Examples:

And- C= All cats bark.

E= 7+4=11

C^E (False)

~C^E (True)

C^~E (False)

~E^~C (False)

Or- M= I go to the mall.

B: I buy sneakers.

MVB (True)

~MVB (True)

MV~B (True)

~MV~B (False)

To be true, both parts must be true.

– Flip the sign.

– Symbol: ~.

– Ex.) ~(P^Q) : ~PV~Q

~(~CVB) : C^~B

– A compound sentence.

– Every action has a reaction.

– Parts of the sentence:

*hypothesis- Sentence or phrase that starts with “if.”

*conclusion- Sentence or phrase that starts with “then.”

ex.) If I eat a lot of icecream, then I get a brainfreeze.

– Symbol: ->

ex.) P: I go on a field trip, W: I miss schoolwork.

P->W (Truth Value- T->T equals T)

P Q P-> Q

T T T

T F F

F T T

F F T

– Symbol: ->

– Symbol: <-->.

ex.) P: A triangle is isosceles. (T)

Q: A triangle has 2 congruent sides. (T)

P <--> Q (T)

P Q P<-->Q

T T T

T F F

F T F

F F T

– Change the sign.

– ex.) If I like chocolate, then I eat kisses.

If I do not like chocolate, then I do not eat kisses.

– Change order.

– ex.) If I put on shoes, then I tie my shoes.

If I tie my shoes, then I put on my shoes.

– Change the order and the sign.

– Same truth value.

– ex.) If I get married, then I say I do.

If I do not say I do, then I do not get married.

ex. American Idol contestants hope for recognition

No S are P.

Some S are P.

Some S are not P.

Therefore, it is false that all trade spies are masters at bribery.)

(ex: 1. All A are B.

Therefore, some A are B.

2. No A are B.

Therefore, some A are not B.

~p

*q

*p *q

p

*q

*pVq *pVq

*~q→~p

q→r

*p→r

~q p

*~p *q

~(pΛq)↔ (~pV~q) ~(pVq)↔ (~pΛ~q)

p

q

/

~p v ~q or ~p ^ ~q

/

~q –> p

~q

/

~p

“the maid or butler did it”

~p or ~b

/

b or p

(a) 1 is in S

(b) If k is in S , then k + 1 is in S.

Then S is the set of all positive integers

(a) 1 is in S

(b) If k is a positive integer such that 1, 2, . . . , k are in S , then k +1 is S.

Then S is the set of all positive integers

Proof:

since the gcd(a,b)=1, 1=ax+by for x,y in Z

so c=(ax+by)c=acx+bcy

since a l ac and a l bc, a l (acx + bcy)

so a l c(ax+by). Therefore a l c

Corollary:

If p is a prime, then a^p ≡ a (mod p) for any integer a.

x ≡ a1 (mod n1)

.

.

.

x ≡ ar (mod nr)

has a simultaneous solution, which is unique modulo n = n1n2 . . . nr

(b) A inter B = B inter A

(b) (A inter B) inter C = A inter (B inter C)

(b)A inter (B U C) = (A inter B) U (A inter C)

(b)A inter 0 = 0

(b)A inter A^c^ = 0

(b)A inter A = A

(b)A inter 0 = 0

(b)(A inter B)^c^ = A^c^ U B^c^

(b)A inter (A U B) = A

(b)0^c^=Univ

ex. A={1, 2, 3, 4}

Statement 3 is made of the beginning of Statement 1 and the end of statement 2.

If A, then B.

If B, then C.

If A, then C.

– p if and only if q

– used if you can prove that a conditional statement and its converse are true.

– only true for statement and contrapositive, converse and inverse

————

T T T

T F T

F T T

F F F

————

T T T

T F F

F T F

F F F

————

T T T

T F F

F T T

F F T

***Note this is only false when the conclusion is false and the hypotheses is true.

2. (t+0=t) ⇒ (t+0 = t ⇒ t=t) (S1′)

3. t+0 = t ⇒ t = t (1,2,MP)

4. t=t (1,3,MP)

1. If R(k_1, …, k_n) is true, then ⊦K A(bar{k}_1,…, bar{k}_n)

2. If R(k_1, …, k_n) is false, then ⊦K ¬ A(bar{k}_1,…, bar{k}_n)

1. If f(k_1, …, k_n) = m then ⊦K A(bar{k}_1,…, bar{k}_n, m)

2. ⊦K (∃_1 x_n+1) A(bar{k}_1,…, bar{k}_n, x_n+1)

2′. ⊦K (∃_1 x_n+1) A(x_1,…, x_n, x_n+1)

0 if R(x_1, …, x_n) is true

1 if R(x_1, …, x_n) is false

2. Successor Function N(x) = x + 1 for all x

3. Projection Functions

U_i^n (x_1, …, x_n) = x_i for all x_1, …, x_n

and p

______

.. q

and ~q

______

.. ~p

q -> r

p

____

.. r

~p

____

. . q

T | T | T

T | F | F

F | T | T

F | F | T

OR

Converse (q –> p) === Inverse (~p –> ~q)

p

… q [VALID]

modus ponendo ponens: “the way that affirms by affirming”

~ q

… ~ p [VALID]

modus tollendo tollens: “the way that denies by denying”

~ p

… q [VALID]

q –> r

… p –> r [VALID]

… p v q

… p

p –> r

q –> r

… r [VALID]

q

… p ^ q

… p

q

… p [INVALID]

~ p

… ~ q [INVALID]

~(p v q) === ~p ^ ~q

(p ^ q) v (~p ^ ~q)

(p(T) –> q(F))

[(p ∨ q) ∧ ~p] → q

[(p → q) ∧ p ]→ q

(p → q) ↔ (~q → ~p)

Inverse + Converse

[(p → q) ∧ ~p] → ~q

~(p ∨ q) ↔ (~p ∧ ~q)

(p → q) ↔ (~p ∨ q)

can use demorgans law to find:

~(p → q) ↔ ~(~p) ∧ ~q

then law of double negation:

~(p → q) ↔ p ∧ ~q

p ∧ q → (p ∧ q)