이신수학 정리1

명제 = 참과 거짓을 구별할수 있는 문장및 수학적식
명제) 철수는 영희보다 키가 작다
명제 아님) 철수는 공부를 잘한다.
명제함수=2x+1=2
x가 뭔지에 따라 참 거짓이 왔다갔따하는것 이것을 명제함수라함.

명제의 진리값=참, 거짓
명제종류 3~5개
합성명제=하나이상의 명제와 논리연산자로 이루어짐
조건명제, 쌍조건명제
항진명제, 모순명제

반례=명제가 거짓이라는 것을 보여주는 것.
예)x에 대해 x가 짞수이면 x<10이다  라는 명제가 있다면
12 14 16등이 들어가면 10보다 큰짝수가 있기 떄문에 반례가 된다.

합성명제=하나이상의 명제와 논리연산자로 이루어짐
논리합=하나라고 T명 T
논리곱=둘다T 일때만 T
베타적논리합(XOR)=동성F, 남여T9
xor=(Aand~B) 합 (~AandB)
곱들의합
조건명제 역이대우

조건명제=조건 a,b가 있을떄 a가 역할, b가 결론
가정(앞)이 F이면 무조건 T이다.
둘다 T이면 T이다.
둘다 F이면 T이다.

쌍조건명제
P가 Q이면서 and Q가P이다
둘다T이면 T이고
둘다F이면 T이다.

항진명제=항상 T인 명제
모순명제=항상F인 명제

논리
명제논리=명제
술어논리=명제함수
멱집합=모든부분집합+공집합
집합A가 {0,1}이면 아래와 같다.

부울행렬
반사적=대각선이 모두 1인것. 1.1 2.2. 3.3 4.4 ....
대칭적=대각선기준으로 양옆이 똒같은것
추이적=a가b이고 b가c이면 a가 c이다
역관계=A->B이면 B->A인것.
합성관계=A->B->C이면 A->C인것. AoB
동치관계=반사적이며,대칭적이며,추이적 이면!!! 동치관계
대각행렬=주대각을 제외한 나머지가 0인 행렬
! 팩토리얼=1부터 n까지 모두 곱한값.
서로소=각 수의 약수가 1이외에 없는것

그래프
한붓그리기=홀수점의 갯수가 0 또는 2개만 가능
인접=열결된 두 꼭지점은 서로 인접
병렬변=두 꼭지점을 열결하는 변이 2개이상.
고립된꼭지점= 어떠한 변도 연결안됨.
동형=변과 꼭지점명은 다르지만 겉모습이 같은것.
발생행렬, 인접행렬, 인접리스트
방향 그래프=변이 방향있음
무향 그래프=변이 방향없음
단순 그래프=루프도 없고 병렬변도 없는 무향그래프
부분 그래프 = 각 꼭지점, 변이 옆에 그래프 안에 포함될경우

신장부분그래프=꼭지점은 반드시 같은것. 무조건 다 그려놔야함. 그후 엣지들 있는것 포함

오일러그래프

 차수
deg(v)=꼭지점과 연결된 변 수
degG(v)=그래픽의 총차수=각 꼮지점의 차수를 다 더함 
핸드쉐이킹램마=2|E|  = 2곱하기 변의 갯수
그래프의 차수가 홀수이면 꼭지점은 짝수.
워크 = v1부터~ vk까지 가는 꼭지점과 변을 순서대로 나열.
v0e1v1e2v2e3.....
워크의 길이=v0를 뺸 나머지 꼭지점 수!!
v0로에서 시작해서v0로 오면 닫혀있다. 즉 시작과 끝이 같은것.
워크는 루프가 있어도됨
트레일=워크에서 변들이 겹치지않고 모두 다른것! 엣지e는 다 달라야함 v꼭지점은 겹쳐도됨.
트레일은 루프가 있어도됨.
오일러트레일=모든변을 한번만 지나는 트레일
오일러 투어=닫힌 오일러 트레일

 
해밀턴경로=모든 꼭지점 한번씩
해밀턴사이클=닫힌 해밀턴 경로

경로=트레일의 꼭지점과 변이 모두 다르면 경로 라고함.
경로는 루프가 있으면 안되는것이다.
쌍으로 서로소=교집합이 공집합인 애들.
완전 그래프 = 별네트워크 모양
n개 꼭지점에서 각 꼭지점차수=n-1개
n개 꼭지점의 변의 수 = 2분의 n(n-1)개

이분그래프=아래는 완전이분 그래프

정규그래프=모든 꼭지점의 차수가 같은것.

평면그래프=서로 교차하지 않는 그래프.