개요
불 대수(Boolean Algebra)를 다루는 교육용 프로젝트다. 이 프로젝트는 불 대수와 비트 연산을 학습하기 위한 일련의 연습 문제들로 구성되어 있다. 각 exercise는 불 대수, 비트 연산, 논리 회로 등의 개념을 실습할 수 있도록 설계되었다.
Exercise 목록
ex00: 비트 연산을 사용한 덧셈 (Adder)
- XOR 연산과 AND 연산을 활용하여 덧셈을 구현한다.
- 재귀적으로 캐리 비트를 처리한다.
ex01: 비트 연산을 사용한 곱셈 (Multiplier)
- 비트 시프트와 덧셈을 조합하여 곱셈을 구현한다.
- ex00의 adder 함수를 활용한다.
ex02: 그레이 코드 (Gray Code)
- 이진수를 그레이 코드로 변환한다.
- 인접한 숫자 간에 한 비트만 차이나도록 인코딩한다.
그레이 코드란? 그레이 코드(Gray Code)는 연속된 숫자들 사이에 한 비트만 차이나는 이진 인코딩 방식이다. 일반 이진수에서는 숫자가 증가할 때 여러 비트가 동시에 변경될 수 있지만, 그레이 코드는 한 번에 한 비트만 변경되어 오류 감지와 디지털 회로 설계에 유용하다.
ex03: 불 공식 평가 (Evaluate Formula)
- 역폴란드 표기법(Reverse Polish Notation)으로 작성된 불 공식을 평가한다.
- 연산자:
&(AND),|(OR),^(XOR),>(IMPLY),=(EQUIV),!(NOT)
ex04: 진리표 출력 (Print Truth Table)
- 주어진 불 공식의 모든 변수 조합에 대한 진리표를 출력한다.
ex05: 부정 정규형 (Negation Normal Form, NNF)
- 불 공식을 부정 정규형으로 변환한다.
- 모든 부정 연산자가 리터럴에만 적용되도록 변환한다.
NNF란? 부정 정규형(Negation Normal Form, NNF)은 불 공식의 정규형 중 하나로, 모든 부정 연산자(!)가 리터럴(변수나 그 부정)에만 직접 적용되도록 변환한 형태다. 즉, !(A & B) 같은 형태는 !A | !B로 변환되어 부정이 AND/OR 연산자 밖으로 나오지 않도록 한다.
ex06: 결합 정규형 (Conjunctive Normal Form, CNF)
- 불 공식을 결합 정규형으로 변환한다.
- AND의 OR 결합 형태로 변환한다.
CNF란? 결합 정규형(Conjunctive Normal Form, CNF)은 불 공식을 여러 절(clause)의 AND 결합으로 표현한 형태다. 각 절은 리터럴들의 OR 결합으로 구성된다. 예를 들어, (A | B) & (!A | C) & (B | !C) 형태가 CNF다. CNF는 SAT 문제 해결과 논리 증명에 널리 사용된다.
ex07: 만족 가능성 문제 (SAT)
- 주어진 불 공식이 만족 가능한지 판단한다.
- 진리표를 생성하여 최소 하나의 행이 true인지 확인한다.
SAT란? 만족 가능성 문제(Satisfiability Problem, SAT)는 주어진 불 공식에 대해 변수에 값을 할당하여 공식이 true가 되도록 할 수 있는지 판단하는 문제다. SAT는 계산 복잡도 이론에서 NP-완전 문제로 알려져 있으며, 많은 실제 문제들이 SAT로 환원될 수 있어 중요하다.
ex08: 멱집합 (Power Set)
- 주어진 집합의 모든 부분집합을 생성한다.
- 비트 마스킹을 사용하여 효율적으로 구현한다.
ex09: 집합 연산 평가 (Evaluate Set)
- 불 연산자를 집합 연산으로 확장하여 평가한다.
&(교집합),|(합집합),^(대칭차),>(부분집합),=(동등),!(여집합)
ex10: 숫자 매핑 (Map)
- 두 개의 16비트 정수를 하나의 32비트 실수로 매핑한다.
- [0, 1] 범위의 실수로 정규화한다.
ex11: 역매핑 (Reverse Map)
- ex10에서 생성된 실수를 다시 두 개의 16비트 정수로 역매핑한다.
실행 방법
설치
npm install
개발 모드 실행
각 exercise를 개발 모드로 실행할 수 있다:
npm run dev src/ex00
npm run dev src/ex01
npm run dev src/ex02
# ... 등등
평가 모드 실행
각 exercise를 평가 모드로 실행할 수 있다:
npm start src/ex00
npm start src/ex01
npm start src/ex02
# ... 등등
기술 스택
- TypeScript: 타입 안전성을 위한 언어
- tsx: TypeScript 실행 환경
- @fxts/core: 함수형 프로그래밍 유틸리티
- console-log-colors: 콘솔 출력 색상 지원
프로젝트 구조
src/
├── AbstractSyntaxTree/ # 불 공식 파싱 및 평가를 위한 AST 구현
│ ├── AST.class.ts # AST 기본 클래스
│ ├── AST.type.ts # 타입 정의
│ ├── AST.nnf.ts # NNF 변환
│ ├── AST.cnf.ts # CNF 변환
│ └── ...
├── ex00/ # 덧셈 구현
├── ex01/ # 곱셈 구현
├── ex02/ # 그레이 코드
├── ex03/ # 불 공식 평가
├── ex04/ # 진리표 출력
├── ex05/ # NNF 변환
├── ex06/ # CNF 변환
├── ex07/ # SAT 문제
├── ex08/ # 멱집합
├── ex09/ # 집합 연산 평가
├── ex10/ # 숫자 매핑
└── ex11/ # 역매핑
AST란? 추상 구문 트리(Abstract Syntax Tree, AST)는 프로그래밍 언어나 수식을 구문 분석한 결과를 트리 구조로 표현한 것이다. 불 공식의 경우, 연산자와 피연산자를 노드로 표현하여 공식의 구조를 명확히 나타내고, 이를 통해 평가, 변환, 최적화 등의 작업을 수행할 수 있다.