[📃칼럼] 집합으로 알아보는 논리게이트 - 집합편

[달애옹쓰(slugcatmonk)]

김물붕은 궁금증이 생겼다

이 시리즈의 이름은 집합으로 알아보는 논리게이트인데 왜 집합얘기는 하나도 없는걸까?

좆냥이의 릭트쇼에 또 당한걸까?

쿨... 돌려야겠지?

사실 이전의 두 이야기는 이번화를 위한 빌드업이었다

우선 기본적인 발상은 이러하다

이런 벤다이어 그램을 생각해보자

x안의 원소라는건 x라는 사실이 참인 부분, 즉 x가 참인 부분이다

그렇다면 가운데의 교집합 부분은 x와 y가 참인 부분

이런식으로 생각해보자

해당 범위는 어떤 상황을 나타내는 걸까?

마치 AND게이트의 그것과 비슷하다

x와 y가 모두 참일 때의 범위를 나타낸다는 것이다.

x 또는 y중 하나라도 참이 아니라면 해당 범위에 포함되지 않는다

즉, 거짓인것이다

방금 집합을 통해 완벽하게 and게이트를 표현해 낸 것이다!

한편 이것의 범위를 집합 기호를 사용해서 나타내면 A∩B 가 될 것이다.

xor의 경우 이렇게 나타날 것이고,

(편의를 위해 여집합을 나타내는 c 윗첨자 대신 !를 쓰겠다. !x 는 x의 여집합이다)

이를 !(!(x∩!y)∩!(!x∩y)) 로 나타낼 수 있을 것이다

근데 이 상황은 마치 다음의 그림을 생각나게 한다

x 와 y중 하나를 not 게이트를 통과시킨뒤 and 게이트를 통과시키고, 각각 not 게이트를 씌워 and 게이트에 넣은뒤 not 게이트에 넣은 모습이다

말이 길긴 하지만 그냥 위의 집합 표기와 아래의 게이트 구조를 보면 완전히 똑같다는 것을 알 수 있다.

이쯤 되면 or 게이트는 x∪y로 나타냄을 깨달았을 것이고,

not, and , or 게이트는 각각 ∩ ! ∪ 로 나타낼 수 있음을 알았을 것이다.

즉, 해당 세가지 게이트만으로 만들어진 모든 게이트 조합방식을 저 세가지 집합기호로 나타낼 수 있단거다.

그리고 지난 게시글에서 not 과 and 를 조합해서 모든 게이트를 만들었던것에서 알수있듯이,

∩ ! 두개 만으로 모든 게이트와 동치인 집합을 만들어 낼 수 있음을 알 수 있다.

이를 통해 not, or 게이트로 and 게이트를 구현해 내는 것을 이해해 보자.

이때 필요한 것이 바로 드모르간 법칙이다

! (x∩y ) = !x ∪ !y

! (x∪ y ) = !x∩ !y

이것을 보면 뭘할건지 이해가 될것이다

! (x∪ y ) = !x∩ !y 에서 !를 우변으로 넘기면

x∪ y = !(!x∩ !y ) 가 될 것이고,

합집합을 여집합과 교집합만으로 나타낼수 있었으며, 이는 게이트에서 or을 not와 and만으로 나타냈음을 의미한다

또한 우변의 모습은

괴상했던 이 게이트와 동치임을 쉽게 알 수 있다.

xor 게이트는 위에선 정말 발상적으로 구했다.

상식적으로 구하는 법을 이해해보자

우선 xor 게이트의 범위는

(x∪y) - (x∩y) 임을 쉽게 알 수 있고

차집합의 변형공식인

a - b = a ∩ !b 에서

(x∪y) - (x∩y) = (x∪y) ∩ !(x∩y) (차집합의 변형공식)

= !(!x∩ !y ) ∩ !(x∩y) ( 드모르간의 법칙)

사실 이시점에서 좆됐다 이거도 되지만 그동안 보여주던 식이 아니다...

뭐가 문제지 씨발

이어가자면

= !((!x∩ !y ) ∪ (x∩y)) ( 드모르간의 법칙) 이과정을 통해 우선 내부의 여집합을 없앴다

= !( (!x ∪ (x∩y)) ∩ (!y ∪ (x∩y)) ) (분배법칙)

= !( ((!x ∪ x)∩ (!x ∪y)) ∩ ( (!y ∪ y)∩ (!y ∪x) ) ) (분배법칙)

= !( ( U ∩ (!x ∪y)) ∩ ( U ∩ (!y ∪x) ) ) (여집합의 성질)

= !( (!x ∪y) ∩ (!y ∪x) ) (자명)

= !( !(x ∩!y) ∩ !(!x ∪y) ) (드모르간)

병신같은 과정이었지만, 오히려 이를 통해 집합의 법칙들로 모든 게이트를 유도할 수 있음을 알 수 있었을 것이다

and 하나만으로 해볼까?

not 부터 시도해보자

우리가 할 수 있는것은 여러개의 게이트를 조합하는 것 뿐이다.

그러나 교집합 만으로는 집합 x의 여집합을 만들어낼 수 없다는 것을 금방 알 수 있을 것이다

x끼리의 교집합을 아무리 구해봤자 x일 뿐이다.

! ∩ ∪ 만으로 모든 집합을 나타낼 수 있다는 것은 쉽게 알 수 있지만,

이들을 서로 만들어내는 것은 드모르간 법칙이 유일하다.

또한 드모르간 법칙은 ! 가 있을때 ∩ ∪ 를 서로 교환하는 능력이 전부이다

결국 not, and, or 중 하나로는 새로운 게이트를 만들어 낼 수 없으며

and or 게이트 두개로는 not 를 만들어 낼 수 없다.

드모르간 법칙에 의한 교환으로 not과 and 에서 or 을 도출해내는 방법이 유일하단 것이다.

nand 는 왜 모든 게이트를 만들 수 있는걸까?

이는 ! ∩ ∪ 세가지 연산을 유도해낼 수 있다는 말과 동치이다

nand는 !(x∩y) 이다

이때 y에도 x 를 넣으면

!(x∩x) = !(x) (자명) = !x 가 되어 ! 를 유도해냈고,

이를 nand에 다시 씌워주면

!( !(x∩y) ) = x∩y 에서 ∩ 가 유도된다 (실제로는 !(!(x∩y)∩!(x∩y))) 처럼 될것이며 이러한 nand만으로 이루어진 게이트를 그려보면 and게이트를 잘 나타낼 것이다)

nor 이 가능한것은 위와 동일하다

xor은 어떨까? 해보면 and, or 도출이 안된다 증명은 길어서 생략하겠다

인풋으로 가능한 것은 x, y , U( 전체집합, 즉 언제나 참이란뜻, 즉 전원), 공집합(언제나 거짓이란 뜻, 즉 접지)과 이를 집어넣어서 나온 결과물들인데

모든 케이스를 해보면 아웃풋의 종류가 정해져 있음을 알 수 있을것이다.

결국 집합을 통해 게이트들을 표현하고,

이를 집합의 법칙들을 통해 게이트로 다른 게이트를 어떻게 도출할 것인지, 혹은 불가능한지를 파악할 수 있음을 알 수 있다.

이는 게이트로 다른 게이트를 만드는 방법을 발상을 통해 찾던 것을 벗어나

수학적으로 발상적이지 않게 찾아내는것을 가능하게 한다

글이 뭔가 증명이 부족한 느낌이 많이 들것이다

그렇다 나도 이거 발견하고 여기까지 생각하다 말았다

그냥 일종의 지적유희였고 꽤 괜찮아 보였었다...

그래도 논리회로를 다루게 된다면 아주 도움이 안되진 않을거라고 본다

[샛별이반짝이는새벽에(aerospace2)]

개추!

[익명(110.11)]

게이트 조합은 간단하게 알고있었는데 집합으로 표현한다는게 흥미롭네

[익명(110.11)]

[안티프리즈(ronaldo1029384756)]

기계과 가면 이런거 배우는건가

[익명(ds3new)]

이번편은 최근에 그냥 대가리 굴리다 깨달은 내용임

[안티프리즈(ronaldo1029384756)]

기억을 되찾은 애옹쓰는 대단하군요

[익명(ds3new)]

난... 다토?

[HLE_Sеikon(samgukji)]

주딱의 품격

[익명(49.167)]

클리너돌아갈예정 ㅋㅋ