5. Proposition

    는 Definition을 나타내고,      는  Theorem을 나타낸다.

proposition

A sentence that can be determined to be either true or false.

hypothesis and conclusion

Hypothesis is the given proposition.

Conclusion is the proposition that follows from the hypothesis.

 

connectives

forming new compound proposition.

p	q	~p (NOT)	p ^ q (AND)	p v q (OR)	p -> q
T	T	F	T	T	T
T	F	F	F	T	F
F	T	T	F	T	T
F	F	T	F	F	T

-conditional propositions: p->q

"If P, then q. " or "p only if q."

p: hypothesis , q: conclusion

-Biconditional proposition: p<->q

it equal (p->q) ^ (q->p)

"p if and only if q" of "p iff q"

- the order of evaluation is first ~, then ^, then v, last ->.

Logical equivalence

Two truth tables are identical, denoted P ≡ Q.

① p -> q ≡ ~p v q

② contrapositive 

p -> q ≡ ~q -> ~p

③ De Morgan's lows

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

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

④ a v ( b ^ c) ≡ (a v b) ^ (a v c) 

    a ^ ( b v c) ≡ (a ^ b) v (a ^ c) 

- p -> q ≡ ~p v q

p	q	p -> q	~p v q
T	T	T	T
T	F	F	F
F	T	T	T
F	F	T	T

-contrapositive

p	q	p -> q	~p ->~q
T	T	T	T
T	F	F	F
F	T	T	T
F	F	T	T

-converse

p	q	p -> q	q -> p
T	T	T	T
T	F	F	T
F	T	T	F
F	F	T	T

Rules of inference

if all hypotheses is true, then the conclusion is true.

simplification p^q ------ ∴p	conjunction p q ------- ∴p^q	disjunction syllogism p∨q ~p ------- ∴q	addition p ------ ∴p∨q
modus ponens p->q p ------ ∴q	modus tollens p->q ~q ------ ∴~p	hypothetical syllosism p->q q->r ------- ∴p->r

Propositional function

Let P(x) be a statement(not a proposition) involving the variable x and let D be a set. We call P a propositional function if for each x∈D, P(x) is a proposition.

P: n은 홀수이다. 여기서 P가 True이나 False이냐는 변수 n에 의해 결정되기 때문에 proposition이 아니다. n = 103이면 P는 true이고 n=8이면 P는 false이다.

quantifier

- ∀

The symbol ∀ means "for all".

Let P be a propositional function with domain of discourse D. The statement

for all x, P(x)

may be written 

(∀x)P(x).

it is true if for all x in D, P(x) is true.

-∃

The symbol ∃ means "there exists".

there exist x, P(x)

may be written 

(∃x)P(x).

it is true if for at least one x in D, P(x) is true.

quantifier가 있는 변수가 두 개인 propositional function은 주어가 중요하다. 예를 들어 y, x∈people일 때,  ∀x∃y(x loves y)은 people내에 있는 모든 x에 대하여, 참이면 참이다. 그리고 ∃x∀y(x loves y)는 people내에 있는 적어도 하나의 x에 대하여, 주어진 명제가 참이면 참이다.  

 

Generalized De Morgan's laws for Logic

~(∀x P(x)) ≡ (∃x)~P(x)

~(∃x P(x)) ≡ (∀x)~P(x)

1) ∀x P(x) is false.

if for at least one x in D, P(x) is false.

2) ∀x∃y P(x) is false.

~(∀x∃y P(x)) ≡ (∃x)~(∃y P(x)) ≡ (∃x)(∀y)(~P(x)) 

if for at least one x in D and for all y in D, P(x) is false.

문제