Propositional Logic, Sets, Functions, and Relations TODO

Math · Day 3 / 52 · July — Discrete Math & Logic (Day 3-10)

Concept

Propositional logic consists of propositions with truth values combined with connectives (∧, ∨, ¬, →, ↔); the key points are that the implication p→q is vacuously true whenever p is false, and its contrapositive ¬q→¬p is always logically equivalent. Sets are collections of elements using notation like ∈, ⊆, ∪, ∩, complement, and Cartesian product; the quantifiers ∀ and ∃ swap when negated, with the inner proposition also negated (¬∀x P(x) ≡ ∃x ¬P(x)). A relation is defined as a subset of the Cartesian product A×B; if it has all three of reflexivity, symmetry, and transitivity, it's an equivalence relation that partitions the set into disjoint equivalence classes, and if it has reflexivity, antisymmetry, and transitivity, it's a partial order. A function is a special relation that maps each element of the domain to exactly one value, and the distinctions between injective, surjective, and bijective are the basis for comparing sizes and for the existence of an inverse function. This notation isn't content in itself so much as the language for reading every definition and proof that follows, so the goal is to practice translating symbols back into sentences.

Papers, specs, and formal verification documents are all written in this notation, so failing to read the symbols leads to misreading an algorithm's preconditions and the scope of its guarantees.

Code & Formula

# 명제논리·집합·함수·관계 — 함의(→)의 대우(¬q→¬p)가 항상 동치임을 진리표로 확인.
# 곱집합의 부분집합으로서의 "관계"와, 정의역 원소마다 값이 유일한 "함수"도 함께 점검.

def implies(p, q):
    return (not p) or q

def contrapositive(p, q):
    return implies(not q, not p)

# p -> q 와 그 대우 ¬q -> ¬p 가 모든 진리값 조합에서 같은지 확인 (진리표 4행)
rows = [(p, q) for p in (False, True) for q in (False, True)]
same = all(implies(p, q) == contrapositive(p, q) for p, q in rows)
print("p→q ≡ ¬q→¬p (모든 행 일치)?", same)
for p, q in rows:
    print(f"  p={p!s:5} q={q!s:5} p→q={implies(p,q)!s:5} ¬q→¬p={contrapositive(p,q)}")

# 관계 R ⊆ A×B: A×B 의 부분집합이면 뭐든 관계다.
A = {1, 2, 3}
B = {"a", "b"}
R = {(1, "a"), (2, "b"), (2, "a")}
print("\nR ⊆ A×B ?", R.issubset({(a, b) for a in A for b in B}))

# 함수는 "정의역의 각 원소가 정확히 하나의 값"을 갖는 특수한 관계.
def is_function(rel, domain):
    seen = {}
    for a, b in rel:
        if a in seen and seen[a] != b:
            return False
        seen[a] = b
    return set(seen.keys()) == domain

f_ok = {(1, "a"), (2, "b"), (3, "a")}      # 1->a, 2->b, 3->a : 함수
f_bad = {(1, "a"), (1, "b"), (2, "a")}     # 1이 두 값을 가짐: 함수 아님
print("f_ok 는 함수?", is_function(f_ok, A))
print("f_bad 는 함수?", is_function(f_bad, A))

docs/code/math/math-3.py

Exercise

Formalize five sentences like "verification passes for every valid signature" using quantifiers and logical connectives, then write out both the negation and the contrapositive of each, in symbols and in English.

Practical Connection

If you write a smart contract invariant (e.g., "the sum of position tokens issued across all markets equals the collateral balance") precisely in ∀ form, you can carry it directly into a test property or a formal verification spec.

If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/math-50-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.

한국어

명제논리·집합·함수·관계 TODO

Math · Day 3 / 52 · 7월 — 이산수학·논리 (Day 3–10)

표기법만 읽으면 끝

개념

명제논리는 참·거짓 값을 갖는 명제와 결합자(∧, ∨, ¬, →, ↔)로 이루어지며, 특히 함의 p→q는 p가 거짓이면 무조건 참이라는 점과 그 대우 ¬q→¬p가 항상 동치라는 점이 핵심이다. 집합은 원소의 모임으로 ∈, ⊆, ∪, ∩, 여집합, 곱집합 같은 표기를 쓰고, 한정기호 ∀와 ∃는 부정할 때 서로 뒤바뀌며 안쪽 명제가 부정된다(¬∀x P(x) ≡ ∃x ¬P(x)). 관계는 곱집합 A×B의 부분집합으로 정의되며, 반사·대칭·추이 세 성질을 모두 가지면 동치관계가 되어 집합을 서로소인 동치류로 분할하고, 반사·반대칭·추이를 가지면 부분순서가 된다. 함수는 정의역의 각 원소에 정확히 하나의 값을 대응시키는 특수한 관계이며, 단사(injective)·전사(surjective)·전단사(bijective)의 구분이 크기 비교와 역함수 존재의 기준이 된다. 이 표기법들은 그 자체가 내용이라기보다 이후의 모든 정의와 증명을 읽는 언어이므로, 기호를 문장으로 바꿔 읽는 훈련이 목표다.

논문·명세·정형 검증 문서는 전부 이 표기로 쓰여 있어서, 기호를 못 읽으면 알고리즘의 전제 조건과 보장 범위를 오해하게 된다.

코드 · 수식

# 명제논리·집합·함수·관계 — 함의(→)의 대우(¬q→¬p)가 항상 동치임을 진리표로 확인.
# 곱집합의 부분집합으로서의 "관계"와, 정의역 원소마다 값이 유일한 "함수"도 함께 점검.

def implies(p, q):
    return (not p) or q

def contrapositive(p, q):
    return implies(not q, not p)

# p -> q 와 그 대우 ¬q -> ¬p 가 모든 진리값 조합에서 같은지 확인 (진리표 4행)
rows = [(p, q) for p in (False, True) for q in (False, True)]
same = all(implies(p, q) == contrapositive(p, q) for p, q in rows)
print("p→q ≡ ¬q→¬p (모든 행 일치)?", same)
for p, q in rows:
    print(f"  p={p!s:5} q={q!s:5} p→q={implies(p,q)!s:5} ¬q→¬p={contrapositive(p,q)}")

# 관계 R ⊆ A×B: A×B 의 부분집합이면 뭐든 관계다.
A = {1, 2, 3}
B = {"a", "b"}
R = {(1, "a"), (2, "b"), (2, "a")}
print("\nR ⊆ A×B ?", R.issubset({(a, b) for a in A for b in B}))

# 함수는 "정의역의 각 원소가 정확히 하나의 값"을 갖는 특수한 관계.
def is_function(rel, domain):
    seen = {}
    for a, b in rel:
        if a in seen and seen[a] != b:
            return False
        seen[a] = b
    return set(seen.keys()) == domain

f_ok = {(1, "a"), (2, "b"), (3, "a")}      # 1->a, 2->b, 3->a : 함수
f_bad = {(1, "a"), (1, "b"), (2, "a")}     # 1이 두 값을 가짐: 함수 아님
print("f_ok 는 함수?", is_function(f_ok, A))
print("f_bad 는 함수?", is_function(f_bad, A))

docs/code/math/math-3.py

연습

'모든 유효한 서명에 대해 검증이 통과한다' 같은 문장 다섯 개를 한정기호와 논리 결합자로 형식화한 뒤, 각각의 부정과 대우를 기호와 한국어 문장으로 함께 써 보라.

실무 · Verex 연결

스마트 컨트랙트 불변식(예: 모든 마켓에서 발행된 포지션 토큰의 합은 담보 잔액과 같다)을 ∀ 형태로 정확히 적어 두면 그대로 테스트 속성이나 정형 검증 명세로 옮길 수 있다.

공부한 날 원본 커리큘럼(docs/knowledge/math-50-curriculum.md)의 이 줄에 노트 링크와 ✅ 를 붙이면, 이 자리는 노트 본문으로 바로 이어집니다. 노트 없이 이 페이지에 바로 적어도 됩니다 — 다만 다시 생성하면 덮어쓰이므로, 남길 글은 docs/algorithms/ 의 마크다운으로 쓰는 편이 안전합니다.