집합과 명제 편집하기 (부분)

===명제 연산 몇가지===
{{노잼}}

* conjuction=p∧q로 쓰며, p와 q 모두 T일때만 T인 명제이다

* disconjuction=p∨q로 쓰며, p나 q 둘 중 하나가 T이면 T인 명제이다

* p→q=p가 T, q가 F이면 F인 명제이다. 이 명제가 T일때 p를 충분조건, q를 필요조건이라 한다

* p↔q=p와 q의 진리값이 같을때 T인 명제이다. 이 명제가 T일때 p,q를 필요충분조건 이라 한다

conjuction, disconjuction, 부정(T,F 바꾸는거)에 대해 집합의 연산법칙과 같이 분배법칙, 드모르간 등이 성립한다

p→q≡~p∨q≡=~q→~p이다(≡는 두 명제의 진리값이 같게 나오면 쓰는거)(~는 부정의 기호)

p↔q≡(p→q)∧(q→p)이다.

~(p↔q)≡~p↔q≡~q↔p이다.

기호 순서의 혼동을 피하기 위해, 부정, con, discon 순으로 연산한다.

exclusive disconjuction : 두 명제 중 하나만 T일 수 있는 명제들의 V

* P(p,q,....) : p,q,...의 하위 명제들로 이루어진 P를 기호로 쓴다

하위 명제들이 n개이면 진리표의 줄 갯수는 2^n개이다

* Tautology : P(p,q,...)에서 p,q,...의 진리값에 상관없이 무조건 P가 T인 명제를 말한다

* Contradicton : " 무조건 P가 F인 명제를 말한다

ex) pv(~p)는 tautology, p∧(~p)는 contradiction

* Principle of substitution : P(p,q,...)이 tautology이면 아무 명제 p1,p2,...에 대해 P(p1,p2,...)도 tautology이다

적분변수를 x에서 t로 a로 홍진호로 바꾸는 것과 똑같다 애초에 명제는 T아니면 F니까

* Logical equivalence : P(p,q,..) 와 Q(p,q,..)는 같은 진리표를 가지면(최하부 명제들에 대해 나오는 마지막 진리값이 같으면)

논리적으로 같다고 한다. 기호는 위에 짝대기 3개 긋는거 저거

* 명제 규칙이 몇 개 있다
(=를 짝대기 3개라고 생각, T와 F는 각각 무조건 참이고 거짓인 명제)
1. pvp=p, p∧p=p

2. (pvq)vr=pv(qvr), (p∧q)∧r=p∧(q∧r)

3. pvq=qvp, p∧q=q∧p

4. pv(q∧r)=(pvq)∧(pvr), p∧(qvr)=(p∧q)v(p∧r)

5. p∧T=p, pvF=p, pvT=T, p∧F=F

6. pv~p=T, p∧~p=F, ~T=F, ~F=T

7. ~~p=p

8. ~(pvq)=~p∧~q, ~(p∧q)=~pv~q

진리표를 하나하나 그려가며 증명해보는 유익한 시간을 갖도록 하자.

* Argument : 몇몇 명제들 p1,p2,...이 새로운 명제 Q를 도출해 내는 것을 말한다. 

기호로는 ⊥를 오른쪽으로 90도 눕힌 것을을 써서 p1,p2,...|-Q (p1,p2,...를 premise 전제라 하고 Q를 결론이라 한다)

p1,p2,...|-Q가, 전제가 전부 참일 때, 결론이 참이면 이 주장은 valid하다고 한다. 아닐 경우 이 주장은 fallacy이다.

예를 들어 p,q에 대해 p,p→q|-q는 진리표를 그려보면 valid하다(q, p→q|-p는 fallacy이다).

* Argument p1,p2,....|-Q가 valid하려면 p1,p2,...가 전부 참일때, 즉 p1∧p2∧....∧pn?이 참일 때 Q가 참이여야 한다.

여기서 조건명제를 생각하면, (p1∧p2∧..∧pn)→Q가 Tautology여야 한다는 뜻이 된다(조건명제는 T→F만 F였다).

그래서 (p1∧p2∧..∧pn)→Q가 Tautology라는 것과 p1,p2,....|-Q가 valid하다는 건 상호..뭐더라 ⇔이다.

* 연쇄법칙(law of syllogism) p→q, q→r|-p→r은 valid하다

[(p→q)∧(q→r)]→(p→r)이 tautology인지 진리표를 그리면 알 수 있다.

* Logical implication: 명제 P(p,q,...)는 Q(p,q,...)를 logically imply하다 한다, 기호로는 P(p,q,...)⇒Q(p,q,...)

if Q(p,q,...) is true whenever P(p,q,...) is true(tautology와 비슷해 보인다)

ex)p logically implies pvq

P(p,q,...)가 참일때 Q(p,q,..)가 참이면 P(p,q,..)|-Q(p,q,...)가 valid하고, P→Q가 tautology이며, P(p,q,...)⇒Q(p,q,...)이다.

그래서 저 세개는 상호..그거다

for any propositions P(p,q,..) and Q(p,q,...), 3 statements are equivalent

1)P(p,q,..)|-Q(p,q,...)가 valid

2)P→Q가 tautology

3)P(p,q,...)⇒Q(p,q,...)

* 명제함수

집합 A에서 정의된 명제함수 p(x)는 모든 a∈A에 대해 p(a)가 참이거나 거짓인(예를 들어 p(x)=x>3에 대해 p(1)은 F이고 p(4)는 T이다)

명제를 말한다. 치역을 (T,F)로 생각하는건지 그래서 함수인건진 [[사용자:Flytofreedomikaros|내]]가 모른다.

집합 A를 p(x)의 domain이라 하고, p(a)가 T인 모든 a∈A의 집합을 truth set이라 한다.

* Quantifier(읍읍위키에선 무슨 양화사 라고 한다)

★Universal Quantifier: p(x)가 집합 A에서 정의된 명제함수라 할때, (∀x∈A)p(x) or ∀xp(x)는

모든 x in A에 대해 p(x)가 T이다 라는 뜻이다. 이때 truth set은 A이고. 턴에이를 쓴 이유는 All의 A를 뒤집어서라 카더라.

∀는 번호가 매겨진 집합들의 교집합을 표현할때도 사용될 수 있다

A1∩A2∩...∩An=∩(Ai:i∈P)={x:∀i∈P, x∈Ai}

★Existential Quantifier: p(x)가 집합 A에서 정의된 명제함수라 할때, (∃x∈A)p(x) or ∃x,p(x)는

p(x)가 T가 되게 하는 x가 A에 하나 이상 있단 뜻이다. 기호의 뜻은 somE의 E를 뒤집은거라 카더라.

이때 truth set은 공집합은 아니다.

∃는 번호가 매겨진 집합들의 합집합을 표현할때도 사용될 수 있다

A1uA2u...uAn=u(Ai:i∈P)={x:∃i∈P, x∈Ai}

* ex)A={2,3,5} and p(x)를 x는 소수다 라는, A에서 정의된 명제함수라 하자.

'2는 소수고 3도 소수고 5도 소수다' 라는 명제는

p(2)∧p(3)∧p(5) 또는 ∧(a∈A, p(a))로 쓸 수 있으며 (con, discon이 이런 의미로 쓰일 수 있다)

이는 'A의 모든 수가 소수이다', 또는 ∀a∈A, p(a)로 쓸 수 있다.

비슷하게, '2가 소수가나 3이 소수거나 5가 소수다' 라는 명제는

p(2)vp(3)vp(5) 또는 v(a∈A, p(a))로 쓸 수 있으며

이는 'A의 원소 중 하나 이상이 소수이다', 또는 ∃a∈A, p(a)로 쓸 수 있다.

즉, ∧(a∈A, p(a))≡∀a∈A, p(a) / v(a∈A, p(a))≡∃a∈A, p(a)로 쓸 수 있다.

* Negation of Quantified statements 양화문장의 부정 ㅋㅋㅋㅋ양화대교 ㅋㅋㅋ

예를 들어 'All Starleague 3-times winners have the [[골든마우스|golden mouse]]'의 부정은

'There exists at least one SL 3times winners doesnt have the [[골든마우스|golden mouse]]'이다.

W를 모든 스타리그 3회우승자들의 집합, p(x)를 x have the golden mouse로 정의하면

~(∀x∈W)p(x)≡(∃x∈W)~p(x)이다. 또는 ~∀x,p(x)≡∃x~p(x)≡[[임요환|그분]]이다.

여기서 이를 알 수 있따.

★ ~(∀x∈A)p(x)≡(∃x∈A)~p(x)<br>
★ ~(∃x∈A)p(x)≡(∀x∈A)~p(x)

＃v,∧를 명제함수에서도 명제에 쓸 때와 유사한 의미로 쓸 수 있다.

위에 말한건데, 저 p(2)∧p(3)∧p(5)는 2,3,5 모두 소수여야 T인 명제라고 할 수 있겠다.

v의 경우도 마찬가지이고, 이들도 명제 법칙들이 성립한다.

ex)~(p(x)∧q(x))≡~p(x)v~q(x), ~(p(x)vq(x))≡~p(x)∧~q(x)


* 변수가 하나 이상인 명제함수

곱집합에서 정의된 변수가 여러개인 명제함수도 생각할 수 있다 기호로 뭐 p(x1,x2,...,xn) 이런식으로 쓴다카더라

얘네들도 quantifier들을 써서 뭐 만들 수 있고 부정할수도 있는데 부정할때 예를들어 ∀x∃yp(x,y)이면 ∃x∀y~p(x,y) 이렇게 순서대로 하면 된다.

∀x∃yp(x,y)와 ∃x∀y~p(x,y)의 문장 뜻을 떠올려보면 쉽게 알 수 있다.

* 알아두면 좋은것들

(~p∧~q)v(~p∧q)는 뭘까? 집합 계산할때 처럼 똑같이 묶어보자 ~p∧(~qvq)가되고 ~p∧T이고 이건 ~p이다. 와~대단해~

오늘의 영단어 : contrapositive(대우)

* 명제함수의 정확한 정의<br>
ex)A={1,2,...10}일때

(∀x∈A)(∃y∈A)(x+y<14)는 명제함수일까 아닐까?

명제함수가 아니라 카더라. 모든 x에 대해 만족하는 y를 하나 이상 찾아줄수 있긴 한데 이게 위에 써둔 명제함수랑 어디가 다른거냐고 나도 생각했지만

이건 x와 y 모든 문자의 조건을 잠가버린 일종의 문장, 즉 모든 A에 속하는 x에 대해 x+y<14를 만족하는 A에 속하는 y를 적어도 하나 찾아줄 수 있다 라는 문장

이지 명제함수가 아니라고 한다.

(∀y∈A)(x+y<14)는 x의 truth set이 {1,2,3}인 명제함수이다.

한편 음의 정수에서 정의된 x+2>5도 truth set이 공집합인 명제함수이다.

하지만 복소수에서 정의된 x+2>5는 명제함수가 아니다. x+2>5가 아무런 의미를 갖지 못하기에.

*오늘의 영문법 : Being rich를 p, Being happy를 q라 할때

To be poor is to be unhappy≡~p↔~q이다.

*오늘의 논리 : A={1,2,...10}에서 정의된 명제함수 (∃y∈A)(x+y<14)의 truth set은 {1,2,...10}=A이다.