이산수학 - 논리·집합·그래프가 코드에 나타나는 곳

이 장에서 배우는 것

앞 장에서 개발에 필요한 전공 과목의 위치를 살펴보았다. 이제 조건문 하나를 읽는 데서 출발해 이산수학이 코드와 만나는 자리를 확인한다. 이산수학은 참과 거짓, 원소의 포함 여부, 점 사이의 연결처럼 서로 구별되는 대상을 다루는 수학이다. 연속적으로 변하는 양보다 선택과 관계를 다루므로 프로그램의 판단을 설명하는 데 자주 쓰인다.

다른 전공에서 개발로 옮겨 왔다면 이미 조건문, 목록, 화면 사이의 이동을 작성해 보았을 수 있다. 이산수학은 그 경험에 이름과 판단 기준을 붙여 준다. 전공 수업의 용어를 외우는 데서 멈추지 않고, 요구사항을 어떤 조건으로 옮겼는지 설명하고 잘못 옮긴 조건을 작은 입력으로 찾아내는 것이 이 장의 목표다.

• 조건문을 참과 거짓이 정해지는 문장으로 읽고, 모든 입력 조합을 표로 확인한다.
• 집합의 교집합·합집합·차집합을 학습 대상 선정에 적용하고 SQL 조회와 연결한다.
• 과목 사이의 선행 관계를 그래프로 표현하고, 주어진 순서가 연결을 따르는지 확인한다.
• 틀린 주장을 깨뜨리는 반례를 찾고, 몇 번의 성공과 증명의 차이를 설명한다.
• 진리표를 생성하여 드모르간 법칙 두 가지를 확인하는 프로그램을 완성한다.

문제 상황

개발자로 일하기 위해 학습 계획을 세운다고 하자. 전체 과목 목록에서 이미 익힌 과목을 빼고, 지원하려는 역할에 필요한 과목을 골라야 한다. 어떤 과목은 먼저 배울 과목도 있다. 단순히 과목 이름을 줄 세우면 공부할 수 있는 순서인지 알기 어렵다.

학습 관리 도구에는 다음 요구사항이 들어왔다. “선행 과목을 마쳤고 학습 시간을 확보한 경우에만 이번 주 과목으로 등록한다.” 여기서 “그리고”를 “또는”으로 옮기면 선행 과목을 끝내지 않았어도 시간이 있다는 이유로 등록된다. 실행 오류가 나지 않으므로 화면만 살펴서는 문제를 놓치기 쉽다.

과목 필터도 비슷하다. “필요 과목 중 아직 익히지 않은 것”과 “모든 과목 중 아직 익히지 않은 것”은 다른 결과다. 앞의 결과는 이번 목표에 집중한 목록이고, 뒤의 결과에는 현재 역할과 관계없는 과목도 들어간다. 필터의 출발 범위를 정하지 않으면 같은 “미학습 과목”이라는 말로 서로 다른 기능을 만들게 된다.

이 장에서는 등록 조건을 논리로, 과목 묶음을 집합으로, 선행 관계를 그래프로 표현한다. 세 표현은 서로 경쟁하는 도구가 아니다. 한 기능에서도 판단, 대상 선정, 연결 관계를 각각 설명하는 데 함께 쓰인다.

조건문을 명제로 읽기

참과 거짓을 결정할 수 있는 문장

현재 상태가 정해졌을 때 참인지 거짓인지 판단할 수 있는 문장을 전공 수업에서는 명제(proposition)라고 부른다. “선행 과목을 마쳤다”는 완료 기록이 주어지면 판단할 수 있다. 반면 “어떤 과목을 좋아하는가?”는 질문이므로 그대로는 명제가 아니다. 코드에서는 앞의 문장을 변수 p에, “이번 주 학습 시간이 있다”를 q에 담아 생각할 수 있다.

참과 거짓 두 값을 다루는 논리를 명제 논리라고 한다. Python의 True와 False는 두 값을 표현하는 불리언(bool) 값이다. and는 두 조건이 모두 참일 때 참이고, or는 하나 이상이 참일 때 참이다. not은 참과 거짓을 뒤집는다. 일상어의 “또는”과 달리 or는 둘 다 참인 경우도 포함한다.

학습 등록 요구사항을 논리식과 Python으로 옮기는 방법

판단	논리 표기	Python	참이 되는 조건
선행 과목을 마쳤다	p	p	완료 기록이 있다
두 조건을 모두 만족한다	p ∧ q	p and q	p와 q가 모두 참이다
하나 이상을 만족한다	p ∨ q	p or q	둘 중 하나 이상이 참이다
선행 과목을 마치지 않았다	¬p	not p	p가 거짓이다

기호 ∧, ∨, ¬는 각각 그리고, 또는, 부정을 뜻한다. 여기서는 기호를 빠르게 계산하기보다 문장과 코드를 서로 바꿔 읽는 데 사용한다. 다음 코드는 시간이 있어도 선행 과목을 마치지 않았다면 등록할 수 없다는 사실을 확인한다.

prerequisite_done = False
has_time = True
can_register = prerequisite_done and has_time
print(can_register)  # False

진리표와 드모르간 법칙

입력의 참·거짓 조합과 식의 결과를 모두 나열한 표를 진리표(truth table)라고 한다. 입력이 두 개라면 각 입력에 두 가지 값이 있으므로 조합은 2 × 2 = 4개다. 참인 상황 하나만 검사하는 대신 네 상황을 모두 확인하면 and와 or를 잘못 옮긴 곳을 찾을 수 있다.

“등록 조건을 만족하지 않는다”는 not (p and q)다. 이를 “선행 과목을 마치지 않았거나 시간이 없다”로 풀면 (not p) or (not q)가 된다. 두 표현은 입력 네 조합에서 결과가 모두 같다. 모든 허용 입력에서 결과가 같은 관계를 논리적 동치라고 한다.

드모르간 법칙(De Morgan's laws)은 묶인 조건을 부정할 때 각 조건을 부정하고 그리고와 또는을 서로 바꾸는 규칙이다. 두 형태는 not (p and q) == ((not p) or (not q))와 not (p or q) == ((not p) and (not q))다. 아래 그림은 첫 번째 형태를 보여 준다.

첫 번째 식에서 참이 되는 상황은 등록 실패 상황이다. 선행 과목만 미완료여도, 시간만 없어도, 두 조건이 모두 부족해도 참이다. 두 번째 식은 뜻이 다르다. “두 조건 중 하나라도 만족한다”를 부정하므로 두 조건이 모두 거짓이어야 참이다. 괄호 밖의 부정을 안쪽으로 옮기면서 연산자를 그대로 두면 이 차이를 잃는다.

Python에서는 괄호를 써서 판단 범위를 드러내는 편이 읽기 쉽다. 또한 and와 or는 실제 언어 기능으로는 항상 불리언을 반환하는 연산자가 아니다. 피연산자 중 하나를 반환한다. 이 장의 논리 실험은 입력을 False와 True로 제한하여 두 값의 논리만 확인한다.

과목을 집합으로 고르고 관계를 그래프로 읽기

같은 과목을 한 번만 세는 집합

중복을 구별하지 않고 원소의 포함 여부를 다루는 모음을 집합(set)이라고 한다. 원소는 집합에 들어가는 대상이다. 여기서는 과목 이름 하나가 원소다. 전공 수업에서 배우는 교집합은 양쪽에 모두 있는 원소, 합집합은 어느 한쪽에라도 있는 원소, 차집합은 왼쪽에 있으면서 오른쪽에는 없는 원소의 집합이다.

전체 과목 집합을 U, 이미 익힌 과목을 K, 목표 역할의 필요 과목을 R이라고 하자. 이번에 메울 과목은 R − K다. U − K는 전체 목록에서 남은 모든 과목이다. K에 없는 대상을 말하려면 어느 범위에서 찾는지 먼저 정해야 한다. 이렇게 기준으로 삼는 전체 범위를 전체집합이라고 한다.

known = {"논리", "집합"}
required = {"집합", "그래프"}

print(sorted(known & required))  # ['집합']
print(sorted(known | required))  # ['그래프', '논리', '집합']
print(sorted(required - known))  # ['그래프']

Python에서 &, |, -는 집합의 교집합, 합집합, 차집합을 만든다. 집합은 원소의 순서를 약속하지 않으므로 출력할 때는 sorted()로 정렬한다. 집합 연산으로 학습 대상을 고를 수 있지만, 그 결과가 곧 학습 순서는 아니다. 순서가 필요한 목록과 포함 여부가 필요한 집합은 구별해야 한다. 구체적인 자료구조 선택 기준은 다음 장에서 이어 간다.

데이터를 조회하는 언어인 SQL에서도 집합 관점이 도움이 된다. 다만 SQL의 일반 조회 결과에는 중복 행이 남을 수 있다. 수학의 집합과 항상 같다고 생각하면 개수를 잘못 셀 수 있다. 다음 실험은 표준 라이브러리 sqlite3로 메모리 안에 작은 데이터베이스를 열어 중복 차이만 확인한다. 파일이나 외부 서버는 사용하지 않는다.

import sqlite3

with sqlite3.connect(":memory:") as connection:
    connection.execute("CREATE TABLE needed (subject TEXT)")
    connection.executemany(
        "INSERT INTO needed VALUES (?)",
        [("그래프",), ("그래프",)],
    )
    rows = connection.execute("SELECT subject FROM needed").fetchall()
    unique_rows = connection.execute(
        "SELECT DISTINCT subject FROM needed"
    ).fetchall()

print(len(rows), len(unique_rows))  # 2 1

CREATE TABLE은 표를 만들고 INSERT는 행을 넣는다. SELECT는 행을 조회하며, DISTINCT는 선택한 열의 값이 같은 결과를 하나로 줄인다. 여기서는 과목 하나가 두 번 저장되었으므로 일반 조회는 두 행, 중복 제거 조회는 한 행을 돌려준다. SQL을 집합과 연결해 이해하되, 중복 처리 규칙은 별도로 확인해야 한다.

연결을 보존하는 그래프

대상과 대상 사이의 연결을 표현한 구조를 그래프(graph)라고 한다. 대상을 나타내는 점은 정점(vertex), 두 정점을 잇는 연결은 간선(edge)이라고 부른다. 여기서는 과목이 정점이고 “앞 과목을 알아야 뒤 과목을 배우기 수월하다”라는 관계가 간선이다. 막대나 꺾은선으로 수치를 그린 도표와는 다른 뜻이다.

선행 관계는 방향이 중요하다. “논리에서 집합으로”라는 연결이 있다고 해서 반대 방향의 연결도 있는 것은 아니다. 간선에 방향이 있는 그래프를 방향 그래프라고 한다. 정점들을 간선 방향에 따라 차례로 이은 것을 여기서는 경로라고 부른다. 반복 정점의 허용 여부에 따라 더 세밀한 용어 구분도 있지만, 이 장의 예제는 정점이 반복되지 않는 경로만 사용한다.

그림의 선행 관계는 개념 연결을 설명하기 위해 정한 작은 예시다. 실제 교육과정의 고정된 선수 과목 규칙을 뜻하지 않는다. 그래프는 관계를 표현하는 수단이므로 무엇을 간선으로 정했는지 설명할 수 있어야 한다.

edges = {("논리", "집합"), ("집합", "그래프"), ("그래프", "경로")}
route = ["논리", "집합", "그래프", "경로"]
valid = all(
    (start, end) in edges
    for start, end in zip(route, route[1:])
)
print(valid)  # True

route[1:]는 첫 항목을 제외한 목록이다. zip()은 두 목록의 항목을 같은 위치끼리 묶으므로 이 코드에서는 연속한 과목 쌍을 만든다. all()은 만들어진 판단이 모두 참인지 확인한다. 이 코드는 주어진 경로를 검사할 뿐, 가능한 경로를 찾아 주거나 가장 짧은 경로를 계산하지는 않는다. 경로를 찾는 절차는 알고리즘을 다룰 때 이어서 살펴본다.

증명할 주장과 반례로 깨뜨릴 주장

전공 수업에서 증명은 주장이 정해진 전제 아래 항상 성립하는 이유를 논리적으로 설명하는 일이다. 반례(counterexample)는 “항상 그렇다”는 주장이 성립하지 않는 입력 하나다. “두 등록 조건을 그리고로 묶어도 또는으로 묶어도 결과가 같다”는 주장은 선행 과목은 미완료이고 시간은 있는 경우 하나로 깨진다.

반례를 찾으면 잘못된 주장을 빠르게 고칠 수 있다. 그러나 반례를 찾지 못했다고 곧바로 참이라고 결론 내릴 수는 없다. 검사한 입력이 전체인지 일부인지가 중요하다. 정수 전체를 대상으로 몇 개를 넣어 본 결과와 불리언 두 개의 네 조합을 전부 확인한 결과는 근거의 범위가 다르다.

이번 완성 코드의 드모르간 법칙 검사는 입력을 불리언 두 개로 제한한다. 네 조합이 허용 입력의 전부이므로 각 식의 결과를 모두 비교하면 이 범위의 동치를 확인할 수 있다. 반면 과목 이름과 간선을 몇 개 넣어 경로 검사 결과가 맞았다는 사실만으로 모든 학습 계획에 대한 프로그램의 정확성이 증명되는 것은 아니다.

반례를 찾을 때는 경계부터 살펴보면 좋다. 조건이 하나만 참인 경우, 집합이 비어 있는 경우, 경로에 연결이 하나 빠진 경우가 출발점이다. 특히 all([])은 True다. 거짓인 항목이 하나도 없기 때문이다. 이를 전공 수업에서는 공허한 참이라고 부른다. 기능 요구사항이 “검사 대상이 하나 이상 있어야 한다”라면 그 조건을 따로 넣어야 한다.

checks = []
print(all(checks))                 # True
print(bool(checks) and all(checks))  # False

bool(checks)는 빈 목록이면 거짓, 원소가 있으면 참이다. 따라서 두 번째 표현은 검사 대상의 존재와 모든 검사의 성공을 함께 요구한다. 수학의 규칙을 바꾸는 것이 아니라 기능에 필요한 조건을 추가한 것이다.

완성 코드

다음 내용을 main.py로 저장한다. 중심 실험은 진리표 생성과 드모르간 법칙 검사다. 이어서 같은 과목 데이터로 집합과 경로를 확인하고, 잘못된 논리식의 첫 반례를 출력한다. 외부 패키지와 입력은 필요 없다.

from itertools import product


def main():
    # 1. 불리언 두 개의 모든 조합과 드모르간 법칙
    pairs = list(product((False, True), repeat=2))
    print("p q | not_and de_or | not_or de_and")
    law_results = []
    counterexamples = []

    for p, q in pairs:
        not_and = not (p and q)
        de_or = (not p) or (not q)
        not_or = not (p or q)
        de_and = (not p) and (not q)
        law_results.append(not_and == de_or and not_or == de_and)
        print(
            f"{int(p)} {int(q)} | "
            f"{int(not_and)} {int(de_or)} | "
            f"{int(not_or)} {int(de_and)}"
        )
        if (p and q) != (p or q):
            counterexamples.append((p, q))

    print(f"드모르간 법칙: {all(law_results)}")

    # 2. 집합으로 이번에 메울 과목 선정
    known = {"논리", "집합"}
    required = {"집합", "그래프"}
    print("겹치는 과목:", ", ".join(sorted(known & required)))
    print("합친 과목:", ", ".join(sorted(known | required)))
    print("메울 과목:", ", ".join(sorted(required - known)))

    # 3. 주어진 경로의 연속한 연결 검사
    edges = {
        ("논리", "집합"),
        ("집합", "그래프"),
        ("그래프", "경로"),
    }
    route = ["논리", "집합", "그래프", "경로"]
    valid_route = len(route) >= 2 and all(
        (start, end) in edges
        for start, end in zip(route, route[1:])
    )
    print(f"학습 경로: {valid_route}")

    # 4. 틀린 주장에 대한 반례와 빈 입력 확인
    p, q = counterexamples[0]
    print(f"and와 or가 다름: p={int(p)}, q={int(q)}")
    print(f"빈 검사 all: {all([])}")


if __name__ == "__main__":
    main()

줄별 해설

from itertools import product는 표준 라이브러리에서 조합 생성 도구를 가져온다. product는 각 위치에 들어갈 값을 서로 조합한다. repeat=2는 같은 후보 묶음을 두 위치에 사용한다는 뜻이다. 결과 순서는 거짓·거짓, 거짓·참, 참·거짓, 참·참이다. 이를 목록으로 보관한 pairs가 진리표의 입력이다.

def main(): 아래에 실행할 작업을 모았다. 첫 번째 print()는 열 제목을 출력한다. not_and와 not_or는 괄호 전체를 부정한 결과이고, de_or와 de_and는 드모르간 법칙으로 바꾼 결과다. 변수 이름은 표의 열과 대응한다.

law_results는 각 입력에서 두 법칙이 모두 맞는지 기록한다. ==는 두 값이 같은지 비교하고 and는 두 비교가 모두 참이어야 참을 만든다. 따라서 두 법칙 중 하나라도 어긋나면 해당 입력의 기록은 거짓이다.

반복문 안의 출력은 int()로 불리언을 숫자로 바꾼다. 거짓은 0, 참은 1이 된다. 여러 줄로 나눈 문자열은 괄호 안에서 이어져 한 줄로 출력된다. 세로 막대는 비교할 열을 구분하는 문자이며 계산에는 참여하지 않는다.

if (p and q) != (p or q):는 두 식의 결과가 다를 때만 실행된다. !=는 같지 않다는 비교다. 서로 다른 입력을 counterexamples에 모은다. 이 목록은 드모르간 법칙의 반례가 아니라 “그리고와 또는은 같다”라는 별도 주장의 반례다.

all(law_results)는 네 입력에서 얻은 검사 결과를 모아 판단한다. 여기서는 product가 네 조합을 만들었다는 사실을 알고 있으므로 빈 목록 문제는 없다. 일반 프로그램에서 검사 대상이 누락될 수 있다면 대상의 개수도 함께 확인해야 한다.

known과 required는 과목 이름을 담은 집합이다. 세 출력문은 교집합, 합집합, 차집합을 각각 계산한다. sorted()는 문자열의 순서에 따라 정렬한 목록을 만들고, ", ".join(...)은 항목 사이에 쉼표와 공백을 넣어 한 문자열로 만든다. 집합 자체의 나열 순서에 기대지 않으므로 출력이 일정하다.

edges의 각 원소는 두 과목 이름을 순서대로 묶은 튜플이다. 튜플은 항목을 순서대로 보관하며 만든 뒤 항목을 바꿀 수 없는 자료형이다. 첫 과목은 출발점, 두 번째 과목은 도착점이다. (start, end) in edges는 해당 방향의 연결이 집합에 들어 있는지 검사한다.

len(route) >= 2는 이 기능에서 과목 두 개 이상을 가진 순서만 경로 검사 대상으로 받겠다는 규칙이다. 수학에서는 정점 하나만 있는 경로도 다룰 수 있다. 코드의 입력 규칙과 수학 용어의 범위를 구별해야 한다. and는 왼쪽이 거짓이면 오른쪽을 평가하지 않는다. 이 평가 방식을 단락 평가라고 한다.

마지막 부분은 첫 반례를 꺼내 출력하고 빈 검사 결과도 보여 준다. 이 코드에서는 서로 다른 식의 반례가 실제로 존재하므로 첫 원소를 읽을 수 있다. 다른 주장을 실험할 때는 목록이 비었는지 먼저 검사해야 한다. 마지막 두 줄은 파일을 직접 실행했을 때 main()을 호출한다.

실행 결과

macOS 또는 Linux에서 Python 3.12 이상의 python3로 실행한다. 출력은 다음과 같다.

$ python3 main.py
p q | not_and de_or | not_or de_and
0 0 | 1 1 | 1 1
0 1 | 1 1 | 0 0
1 0 | 1 1 | 0 0
1 1 | 0 0 | 0 0
드모르간 법칙: True
겹치는 과목: 집합
합친 과목: 그래프, 논리, 집합
메울 과목: 그래프
학습 경로: True
and와 or가 다름: p=0, q=1
빈 검사 all: True

진리표의 가운데 두 열은 모든 행에서 같고, 오른쪽 두 열도 모든 행에서 같다. 이것이 두 드모르간 법칙을 확인하는 근거다. 반례의 p=0, q=1은 선행 과목을 마치지 않았지만 시간은 있는 경우다. 이때 and는 거짓, or는 참이다.

실무에서 자주 틀리는 것

부정을 나누면서 연산자를 그대로 두기

“두 조건을 모두 만족하지는 않는다”를 “두 조건을 모두 만족하지 않는다”로 옮기면 의미가 달라진다. 선행 과목만 마친 경우를 넣어 보면 차이가 드러난다.

틀린 코드는 두 조건이 모두 거짓일 때만 실패로 본다.

p, q = True, False
rejected = (not p) and (not q)
print(rejected)  # False

고친 코드는 어느 한 조건이라도 부족하면 실패로 본다.

p, q = True, False
rejected = (not p) or (not q)
print(rejected)  # True

교집합을 관계없는 집합 연산으로 계산하기

Python 집합에는 and를 쓸 수 있지만 교집합을 계산하지는 않는다. 왼쪽 집합이 비어 있지 않으면 오른쪽 집합이 반환된다. 결과가 집합처럼 보여 오류를 놓치기 쉽다.

틀린 코드는 오른쪽 집합 전체를 반환한다.

known = {"논리", "집합"}
required = {"집합", "그래프"}
overlap = known and required
print(sorted(overlap))  # ['그래프', '집합']

고친 코드는 공통 원소만 고른다.

known = {"논리", "집합"}
required = {"집합", "그래프"}
overlap = known & required
print(sorted(overlap))  # ['집합']

방향 간선을 뒤집어 검사하기

선행 관계에서 순서쌍의 앞뒤는 의미를 가진다. “논리를 익힌 뒤 집합을 배운다”는 연결은 반대 방향의 연결을 보장하지 않는다.

틀린 코드는 도착점과 출발점을 바꾸어 확인한다.

edges = {("논리", "집합")}
start, end = "논리", "집합"
print((end, start) in edges)  # False

고친 코드는 입력 순서 그대로 확인한다.

edges = {("논리", "집합")}
start, end = "논리", "집합"
print((start, end) in edges)  # True

검사 대상이 없어도 완료로 처리하기

“필수 항목을 하나 이상 검사했고 모두 통과했다”는 요구에는 개수 조건이 들어 있다. 빈 입력에 all()만 적용하면 그 조건을 놓친다.

틀린 코드는 검사할 항목이 없어도 완료로 처리한다.

checks = []
completed = all(checks)
print(completed)  # True

고친 코드는 항목의 존재와 검사 결과를 함께 확인한다.

checks = []
completed = bool(checks) and all(checks)
print(completed)  # False

한눈에 보기

이산수학의 핵심 개념을 실무 판단과 면접 질문에 연결하기

핵심	실무에서 쓰는 곳	면접에서 묻는 방식	설명할 요점
명제 논리	등록·권한·필터 조건	이 조건을 부정하면 어떻게 되는가	괄호의 범위와 드모르간 법칙을 설명한다
집합	중복 제거와 대상 선정	필요하지만 없는 항목을 어떻게 고르는가	차집합의 방향과 SQL의 중복을 구별한다
그래프	의존 관계와 이동 경로	점과 연결을 무엇으로 모델링하겠는가	정점·간선·방향의 의미를 먼저 정한다
반례와 전수 검사	요구사항 검증과 오류 재현	이 주장이 틀리는 입력을 제시하라	검사한 입력의 범위와 빈 입력을 확인한다

면접에서는 용어 정의만 말하기보다 작은 입력을 곁들이면 설명을 검토하기 쉽다. 예를 들어 “그리고와 또는은 다르다” 다음에 False, True를 제시하고 결과를 각각 말한다. “집합으로 처리한다” 다음에는 중복을 버려도 되는 이유와 출력 순서가 필요한지를 설명한다. 그래프 문제에서는 무엇을 정점과 간선으로 삼았는지부터 밝힌다.

더 깊게 볼 서재의 책으로는 Kenneth H. Rosen의 Discrete Mathematics and Its Applications와 Susanna S. Epp의 Discrete Mathematics with Applications가 있다. 전자는 논리·집합·관계·그래프가 한 과목 안에서 어떻게 이어지는지 찾아볼 때, 후자는 논리 문장을 해석하고 증명의 근거를 차근차근 확인할 때 참고할 수 있다. 처음부터 모두 읽기보다 이 장에서 막힌 용어를 기준으로 해당 부분을 찾아보는 방식이 알맞다.

이 장의 도착점은 집합과 그래프를 구현하는 모든 방법을 익히는 것이 아니다. 조건의 뜻, 원소의 포함, 연결의 방향을 코드와 말로 일치시키는 것이다. 다음 장에서는 같은 대상을 보관하더라도 어떤 자료구조를 고르느냐에 따라 작업의 성능이 어떻게 달라지는지 살펴본다.

연습 문제

1. “선행 과목을 마쳤거나 대체 과제를 통과하면 등록한다”라는 조건이 있다. p와 q를 각각 두 조건으로 두고 등록 불가 조건을 두 가지 동치인 식으로 작성하라. 완성 코드의 네 입력을 사용해 비교하라.
2. 이미 익힌 과목이 {"논리", "집합"}, 필요 과목이 {"집합", "그래프", "경로"}다. 이번에 메울 과목과 공통 과목을 정렬하여 출력하라. 차집합의 좌우를 바꾸면 어떤 결과가 나오는지도 확인하라.
3. 완성 코드의 route를 ["논리", "그래프", "경로"]로 바꾸라. 경로 검사 결과를 예측하고, 존재하지 않는 연속 쌍만 출력하라. 정점 이름이 모두 알려진 과목인데도 실패하는 이유를 설명하라.
4. “두 조건이 모두 거짓이 아니면 두 조건이 모두 참이다”라는 주장의 반례를 모든 불리언 조합에서 찾으라. 앞부분을 not ((not p) and (not q)), 뒷부분을 p and q로 두고, 앞부분은 참인데 뒷부분은 거짓인 입력을 출력하라.

정답과 해설

등록 불가 조건

등록 조건은 p or q이므로 등록 불가는 not (p or q)다. 드모르간 법칙을 적용하면 (not p) and (not q)다. 두 조건이 모두 거짓일 때만 등록할 수 없다.

from itertools import product

for p, q in product((False, True), repeat=2):
    left = not (p or q)
    right = (not p) and (not q)
    print(int(p), int(q), left == right)

# 0 0 True
# 0 1 True
# 1 0 True
# 1 1 True

메울 과목과 차집합의 방향

메울 과목은 필요 과목에서 이미 익힌 과목을 뺀 결과다. 좌우를 바꾸면 이미 익혔지만 이번 필요 목록에는 없는 과목이 나온다. 차집합은 순서를 바꾸어도 같은 연산이 아니다.

known = {"논리", "집합"}
required = {"집합", "그래프", "경로"}
print(sorted(required - known))
print(sorted(known & required))
print(sorted(known - required))

# ['경로', '그래프']
# ['집합']
# ['논리']

알려진 정점과 존재하는 연결은 다르다

논리와 그래프라는 과목이 모두 있어도 두 과목 사이에 직접 간선이 있지는 않다. 이 검사에서는 중간 과목을 자동으로 찾아 끼워 넣지 않는다. 주어진 순서의 연속 쌍이 실제 간선인지 확인한다.

edges = {
    ("논리", "집합"),
    ("집합", "그래프"),
    ("그래프", "경로"),
}
route = ["논리", "그래프", "경로"]
missing = [
    (start, end)
    for start, end in zip(route, route[1:])
    if (start, end) not in edges
]
print(not missing)
print(missing)

# False
# [('논리', '그래프')]

여기서는 과목 세 개가 주어졌으므로 not missing으로 결과를 판단했다. 빈 목록이나 과목 하나만 받는 기능으로 넓힌다면 완성 코드처럼 길이 조건도 따로 정해야 한다.

앞부분이 참인데 결론이 거짓인 입력

“A이면 B다”라는 주장을 전공 수업에서는 함의라고 부른다. 이를 깨뜨리는 반례는 A가 참이면서 B가 거짓인 경우다. 앞부분이 거짓인 입력은 그 주장에 대한 반례가 아니다.

from itertools import product

for p, q in product((False, True), repeat=2):
    premise = not ((not p) and (not q))
    conclusion = p and q
    if premise and not conclusion:
        print(int(p), int(q))

# 0 1
# 1 0

두 조건이 모두 거짓인 상황을 제외했다고 해서 두 조건이 모두 참인 것은 아니다. 하나만 참인 두 상황이 남는다. 모호한 문장을 입력과 출력으로 바꾸고, 그 사이에 빠진 경우를 찾아내는 습관이 이산수학을 개발에 사용하는 출발점이다.