교환법칙 a+b=b+a
결합법칙 a+(b+c)=(a+b)+c만을 이용하여
a_1+..+a_n의 가능한 모든 두 수의 순서교환,모든 가능한 괄호에 대한 값이 모두 동일함을 "엄밀하게" 어떻게증명함?
가령,
a_1+a_2+a_3의 경우
a_1+(a_2+a_3)
a_1+(a_3+a_2)
a_2+(a_1+a_3)
a_2+(a_3+a_1)
a_3+(a_1+a_2)
a_3+(a_2+a_1)
(a_2+a_3)+a_1
(a_3+a_2)+a_1
(a_1+a_3)+a_2
(a_3+a_1)+a_2
(a_1+a_2)+a_3
(a_2+a_1)+a_3
총 12개 경우가 있고 이들 모두에 대해
교환법칙 결합법칙의 정의를 사용해 같음을 보일 수 있음.
문제는 수가 4개만 되더라도
모든 두 수 교환 & 괄호치기 경우의수가 기하급수적으로 늘어나버리는데,
이들 모두를 아우르는 n개 수에 대해
두 수 교환, 괄호치기를 어떻게하든 연산결과가 같음을
"엄밀하게" 증명하려면 어떻게해야함?
우리가 아는 사실은 두 수의 교환성, 세 수의 결합성인데
이걸로 어떻게든 다쪼개서 같아짐을 보여야되는데
경우수자체가 말이안되버리니까 일반적으로어떻게해야 증명이되는지 모르겠음
- dc official App
귀납법
1,2,..,n개에 대해된다가정하고 귀납할때n+1개를 증명하려면, 추가된1개에대한 모든 "괄호&순서교환"에대해 동일함을 보여야되는데, 수 a_1,..,a_n에 대해a_k+(n개)(n개)+a_k 값이 모든 1<=k<=(n+1)에 대해 동일그 이후,2개+n-1개k개+,n-k+1개등도 다 귀납으로보여야됨?귀납으로하는거에대한 엄밀한증명이궁금함 - dc App
가장 작은 괄호를 묶어서 하나로 보면 문자 개수가 줄테니 문자 개수로 귀납법을 쓸 수 있겠지
그런걸 자명하게 해주는게 수학적 귀납법의 제일 간단한 응용임
형식적 증명이 궁금하면 natural number game같은거 검색해서 배워보셈
랭대수 4,5,p 봐보슈 - dc App
4,5p - dc App
형식증명쪽에 proof by reflection이라고 이런거 다루는 테크닉이 있음. 위 문제같은 경우에는 덧셈식의 집합 E와 normal form의 집합 N, 평가함수 evalE : E -> ℕ, evalN : N -> ℕ, normalization 함수 norm : E -> N을 정의하고, forall e in E, evalE(e) = evalN(norm(e)) 를 증명하면됨. normalize는 예를들어서 ((b + a) + (c + d)) 를 a + (b + (c + d)) 로 바꿔주는 함수임.
이걸로 네가 질문한걸 증명할 수 있음. 먼저 e1, e2 in E가 x1, ..., xn이 정확히 1번씩 나타나는 변수일 때, norm(e1) = x1 + (x2 + (... + (x_{n-1}+ xn))) = norm(e2) 임을 보임. 그러면 앞서보인 정리에 의해 evalE(e1) = evalN(norm(e1)) = evalN(norm(e2)) = evalE(e2) 임
norm(e)의 정의는 별개 아니라 e를 트리 순회해서 등장하는 변수들의 (중복과 순서가 있는) 리스트로 바꾸고, 이 리스트를 정렬하면 됨.