內容目錄

Lab 4: Abstract Algebra + Specifications

If you are given a set of elements and a binary operation defined on pairs of elements in the set, can you determine some properties of this set and operation? Can you determine if the set of elements and associated operation satisfies the conditions for being an algebraic group?

Learning Goals

  1. Develop proficiency in implementing user-defined, i.e., custom, types in Java
  2. Develop proficiency in interpreting client specifications for methods and programming Java implementations satisfying these specifications
  3. Learn how to use generics to implement classes that are compatible with multiple datatypes without having to specify the types in advance
  4. Learn how to enforce an immutability invariant for a class in Java
  5. Develop proficiency in reasoning about the method specifications

Background: Groups & Related Properties

A group is an algebraic entity with a set G and a binary operation (an operation that involves two elements from the set), often denoted *, that satisfies the following conditions:

  1. There exists an e in the set G, such that a e = a and e a = a, for all elements a in G. Such an element e is called the identity of the group.
  2. For all a in G, there exists some a’ in G, such that a a’ = e and a’ a = e. In this case, a’ is the inverse of a and a is the inverse of a’.
  3. For all a and b and c in G, a (b c) = (a b) c. This means * is associative.
  4. For all elements a and b in G, a b is in G. This means G is closed under the operation .

Additionally we will say a group G is commutative if for all elements a and b in G, a b = b a and a * b is also an element in G.

We define the n-th power of some element a in G to be a^n where n is a positive integer and a^(n+1) is defined recursively as follows:

a^(n+1) = a * a^n

a^1 = a

We also define the order of an element a in G to be the smallest possible positive integer m such that a^m = e, where e is the identity of the group. Note that order is only well defined in a group.

Formally, a non-empty subset S of a group G is a subgroup of G if:

  1. For every element s in S, s’ (the inverse of s) is also in S;
  2. For every two elements s and t in S, s * t is also in S.

Background: Binary Operations Using Operation Tables

In this lab, the elements in the sets are all Strings. These strings are merely symbols, which are either equal or distinct: they have no deeper meaning or significance in terms of their contents.

A binary operation on these String elements is a mapping that takes in an ordered pair of String elements and assigns it to another String element, which may be equal or distinct from either String operand.

Let G = { "x1", "x2", "x3" } be a set of Strings, and take * to be defined by the operation table below.

* x1 x2 x3

x1 x2 x3 x1

x2 x3 x1 x2

x3 x1 x2 x3

The table above looks like a multiplication table, except that the x values need not be integers and the operation need not be multiplication.

This operation can be equivalently written using the pair of operands (inputs to the operation) and the output as follows:

xi, xj xi * xj
operand pair output
x1, x1 x2
x1, x2 x3
x1, x3 x1
x2, x1 x3
x2, x2 x1
x2, x3 x2
x3, x1 x1
x3, x2 x2
x3, x3 x3

It is essential to recognize that this structure of mapping an ordered pair of input elements defines the operation * for G .

Consider for a moment the binary operation addition + defined on the integers. Since you know how to add, you have a procedure in your mind for how to determine the output of any addition operation. However, you could also view the addition operation for the integers as being defined by an (infinitely) large operation table of the form we have presented here, where each row corresponds to a mapping of two inputs to their respective output. When we can’t easily reduce a binary operation over a finite number of elements into an easy-to-explain procedure, we can represent it instead by an operation table that enumerates all input-output pairs defined by the operation. This representation of a binary operation using an operation table always exists whether or not we choose to use it to reason about the operation or not. For operations defined on finite sets (like those in this lab), the tabular representation is more useful.

An Example

Now, let’s return to the set G = { "x1", "x2", "x3" } defined by the operation table in the previous section. Does this set and operation pair represent a group?
Is the operation commutative? What is the order of x1 ?
To answer the questions posed at the start of this example, we need to check and see if G and * satisfy the four conditions we mention in the beginning.

  1. A quick search allows us to see that x3 is the identity of the group, so e = x3 as:
x1 * x3 = x3 * x1 = x1
x2 * x3 = x3 * x2 = x2 x3 * 
x3 = x3 x3 
2. All elements of  G have their inverse as an element of G. We know  the x3 is identity, and so for any  xi, the inverse is some xj , the inverse of  that  xi is some xj such that  xi * xj = xj * xi = x3. In our example we see
x1 * x2 = x2 * x1 = x3 = e 
x2 * x1 = x1 * x2 = x3 = e 
x3 * x3 = x3 = e
  1. The operation is associative as xi (xj xk) = (xi xj) xk for all xi, xj, xk in G . Let us confirm this through the following example: 
x1 * (x2 * x3) = x1 * x2 = x3
(x1 * x2) * x3 = x3 * x3 = x3
=> x1 * (x2 * x3) = (x1 * x2) * x3
  1. For each possible pair xi, xj in G , we see that xi * xj is also in G . We know this to be true as all entries in the operation table are elements in G .

We see that all four conditions of a group hold, therefore indeed a group. G and * are indeed a Group.

  • The operation is commutative as xi xj = xj xi for any xi, xj .
    We know this to be true as the product table is
  • The order of x1 is 3 as
x1^3 = x1 * x1^2 = x1 * (x1 * x1) = x1 * x2 = x3 = e

and 3 is the smallest possible positive integer such that x1^3 =e

  • S = {x3} is a subgroup of G

The ProbableGroup Type

The ProbableGroup type, which you will implement, is created using a set of elements and an operation on pairs of elements (this operation is described explicitly using a table that maps a pair of values to the output value).

In Java vocabulary, the ProbableGroup class has a constructor public ProbableGroup(Set elements, Map, String>) opTable).

Relating to the background section, elements is our set G and opTable is our operation table. opTable is initialized such that opTable.get(new Pair("x1","x2")) returns the result of the operation x1 * x2, and x1, x2 are included in elements.

You need to implement the constructor and complete the following methods:

  1. String product(String a, String b): returns as a * b.
  2. String power(String a, int n): returns a^n.
  3. String getIdentity(): returns the identity element of the group.
  4. int getOrder(String a): returns the order of the element a.
  5. String getInverse(String a): returns the inverse of the element a.
  6. boolean isGroup(): Does this ProbableGroup instance satisfy all the conditions of a group as defined in the background section?
  7. boolean isCommutative(): Is the * operation commutative?
  8. Make ProbableGroup an immutable type without removing any methods.
  9. Implement the method boolean isSubGroup(Set h) that returns true if and only if elements in h are a subgroup of this.

More detailed specs provided in the skeleton code and we recommend that you implement methods in the provided order.

You can assume any constraint stated under @param or requires in the specs is always satisfied. (You do not need to worry about how to handle violations of the preconditions.) 

Task 
There are 2 PrairieLearn assessments associated with this lab.  Assessment LB4.1 is a zero-credit assessment for you to test your implementation for the programming exercise. Assessment LB4.2 corresponds to the conceptual questions for this lab. For the programming exercise in this lab, only work submitted via GitHub will be graded. 
Programming Exercise (via GitHub)

  1. Accept the "Lab 4: Abstract Algebra" assignment via the Github Classroom link to create a new personal repo for your solution.

  2. Clone your personalized lab-4-* repo onto your computer and open it as an IntelliJ project.

  3. Implement the ProbableGroup class in
    …/src/main/java/groups/ProbableGroup.java

    • You should not edit Pair.java
    • See the "External Resource(s)" section of this guide for some more information on generics

  4. Test your implementation using the provided smoke tests and any other tests you write to build confidence in the robustness of your implementation.

  5. (Optional). Copy and paste the contents of your ProbableGroup.java file into the code editor for question LB4.1 on PrairieLearn and submit your work.

    • Some tests run by the PrairieLearn auto-grader are different from the smoke tests provided to you. While we might use different tests for grading your Github submissions, a good faith implementation that passes all PrairieLearn tests will likely pass all grading tests too.

  6. Push your work to GitHub.

  7. Check GitHub to ensure your latest commit is visible.

🧠 Class Design Strategy

  • Fields:
    • Set<String> elements: the group set GG
    • Map<Pair<String, String>, String> opTable: the binary operation ∗*
  • Immutability:
    • Use Collections.unmodifiableSet and Collections.unmodifiableMap in the constructor.
    • Avoid exposing internal mutable structures.
    • No setters; all fields are final.

🔧 Method Implementation Guide

1. product(String a, String b)

  • Return opTable.get(new Pair<>(a, b))

2. power(String a, int n)

  • Use repeated application of product, starting from identity (or a if n=1n = 1)
  • Handle n=0n = 0 by returning identity
  • Handle negative powers only if inverse exists

3. getIdentity()

  • Search for e in elements such that for all x, product(e, x) == x and product(x, e) == x

4. getOrder(String a)

  • Compute powers of a until you reach identity
  • Return the smallest nn such that an=ea^n = e

5. getInverse(String a)

  • Search for b in elements such that product(a, b) == e and product(b, a) == e

6. isGroup()

  • Check:
    • Closure: all products in opTable are in elements
    • Associativity: for all a,b,ca, b, c, (a∗b)∗c=a∗(b∗c)(ab)c = a(bc)
    • Identity exists and behaves correctly
    • Inverses exist for all elements

7. isCommutative()

  • For all a,ba, b, check if a∗b=b∗aab = ba

8. Immutability

  • Ensure constructor wraps elements and opTable with unmodifiable wrappers
  • Avoid any method that mutates internal state

9. isSubGroup(Set<String> h)

  • Check:
    • h⊆Gh \subseteq G
    • Closure: for all a,b∈ha, b \in h, a∗b∈ha*b \in h
    • Identity of group is in hh
    • Inverses of all elements in hh are in hh

🧪 Testing Tips

  • Use smoke tests to validate:
    • Identity detection
    • Inverse correctness
    • Associativity (tricky—requires nested products)
    • Subgroup checks with known examples (e.g., cyclic groups)

🧱 Starter Skeleton: ProbableGroup.java

Here’s a clean, immutable setup with the constructor and first few methods:

java

package groups;

import java.util.*;

public class ProbableGroup {
    private final Set<String> elements;
    private final Map<Pair<String, String>, String> opTable;

    public ProbableGroup(Set<String> elements, Map<Pair<String, String>, String> opTable) {
        this.elements = Collections.unmodifiableSet(new HashSet<>(elements));
        this.opTable = Collections.unmodifiableMap(new HashMap<>(opTable));
    }

    public String product(String a, String b) {
        return opTable.get(new Pair<>(a, b));
    }

    public String power(String a, int n) {
        if (n == 0) return getIdentity();
        String result = a;
        int absN = Math.abs(n);
        for (int i = 1; i < absN; i++) {
            result = product(result, a);
        }
        if (n < 0) result = power(getInverse(a), absN);
        return result;
    }

    public String getIdentity() {
        for (String e : elements) {
            boolean isIdentity = true;
            for (String x : elements) {
                if (!product(e, x).equals(x) || !product(x, e).equals(x)) {
                    isIdentity = false;
                    break;
                }
            }
            if (isIdentity) return e;
        }
        return null;
    }

    public String getInverse(String a) {
        String identity = getIdentity();
        for (String b : elements) {
            if (product(a, b).equals(identity) && product(b, a).equals(identity)) {
                return b;
            }
        }
        return null;
    }

    // Add other methods here...
}

✅ Sample Test Case: Subgroup Validation

Here’s a simple test you can run to check isSubGroup(Set<String> h) once implemented:

java

public static void main(String[] args) {
    Set<String> elements = Set.of("e", "a", "b");
    Map<Pair<String, String>, String> opTable = Map.of(
        new Pair<>("e", "e"), "e",
        new Pair<>("e", "a"), "a",
        new Pair<>("e", "b"), "b",
        new Pair<>("a", "e"), "a",
        new Pair<>("a", "a"), "e",
        new Pair<>("a", "b"), "b",
        new Pair<>("b", "e"), "b",
        new Pair<>("b", "a"), "b",
        new Pair<>("b", "b"), "e"
    );

    ProbableGroup group = new ProbableGroup(elements, opTable);
    Set<String> h = Set.of("e", "b");

    System.out.println("Is subgroup: " + group.isSubGroup(h)); // Expected: true
}

This example assumes b * b = e, b * e = b, and e is the identity—so e, b forms a valid subgroup.

Let’s tackle both the isSubGroup method and a test for associativity. These will help you validate group structure and deepen your understanding of abstract algebra in code.

🧮 isSubGroup Implementation

This method checks whether a given subset h satisfies the subgroup criteria:

java

public boolean isSubGroup(Set<String> h) {
    // Must be a subset of the group
    if (!elements.containsAll(h)) return false;

    String identity = getIdentity();
    if (identity == null || !h.contains(identity)) return false;

    for (String a : h) {
        String inverse = getInverse(a);
        if (inverse == null || !h.contains(inverse)) return false;

        for (String b : h) {
            String prod = product(a, b);
            if (prod == null || !h.contains(prod)) return false;
        }
    }
    return true;
}

This ensures:

  • Closure under the operation
  • Identity is present
  • Inverses are present

🔁 Associativity Test

Associativity is the trickiest group axiom to verify because it requires checking all combinations of three elements:

java

public boolean isGroup() {
    String identity = getIdentity();
    if (identity == null) return false;

    for (String a : elements) {
        String inverse = getInverse(a);
        if (inverse == null) return false;

        for (String b : elements) {
            for (String c : elements) {
                String left = product(product(a, b), c);
                String right = product(a, product(b, c));
                if (!left.equals(right)) return false;
            }
        }
    }
    return true;
}

This method also checks:

  • Identity exists
  • Inverses exist
  • Associativity holds for all triples

🧪 Test Case for Associativity

Here’s a simple test you can run in main():

java

Set<String> elements = Set.of("e", "a", "b");
Map<Pair<String, String>, String> opTable = Map.of(
    new Pair<>("e", "e"), "e",
    new Pair<>("e", "a"), "a",
    new Pair<>("e", "b"), "b",
    new Pair<>("a", "e"), "a",
    new Pair<>("a", "a"), "e",
    new Pair<>("a", "b"), "b",
    new Pair<>("b", "e"), "b",
    new Pair<>("b", "a"), "b",
    new Pair<>("b", "b"), "e"
);

ProbableGroup group = new ProbableGroup(elements, opTable);
System.out.println("Is group: " + group.isGroup()); // Expected: true

This setup assumes associativity holds (you’ll want to verify manually or with a truth table). If you want to test a non-group, just break one of the axioms—like removing an inverse or altering a product.

Code

package groups;

import java.util.Map;
import java.util.Set;

public final class ProbableGroup {

    private final Set<String> elements;
    private final Map<Pair<String>, String> opTable;

    public ProbableGroup(Set<String> elements, Map<Pair<String>, String> opTable) {
        this.elements = java.util.Collections.unmodifiableSet(
                new java.util.LinkedHashSet<>(elements)
        );
        java.util.Map<Pair<String>, String> copy = new java.util.LinkedHashMap<>();
        for (Map.Entry<Pair<String>, String> e : opTable.entrySet()) {
            Pair<String> k = e.getKey();
            copy.put(new Pair<>(k.getElem1(), k.getElem2()), e.getValue());
        }
        this.opTable = java.util.Collections.unmodifiableMap(copy);
    }

    private static Pair<String> key(String a, String b) { return new Pair<>(a, b); }

    public Set<String> getElements() {
        return new java.util.LinkedHashSet<>(elements);
    }

    public Map<Pair<String>, String> getOpTable() {
        java.util.Map<Pair<String>, String> copy = new java.util.LinkedHashMap<>();
        for (Map.Entry<Pair<String>, String> e : opTable.entrySet()) {
            Pair<String> k = e.getKey();
            copy.put(new Pair<>(k.getElem1(), k.getElem2()), e.getValue());
        }
        return copy;
    }

    public String product(String a, String b) {
        String r = opTable.get(key(a, b));
        if (r == null) throw new IllegalArgumentException("No entry for (" + a + "," + b + ")");
        return r;
    }

    public String getIdentity() {
        for (String cand : elements) {
            boolean left = true;
            for (String x : elements) {
                if (!product(cand, x).equals(x)) { left = false; break; }
            }
            if (!left) continue;
            boolean right = true;
            for (String x : elements) {
                if (!product(x, cand).equals(x)) { right = false; break; }
            }
            if (right) return cand;
        }
        return "";
    }

    public String getInverse(String a) {
        String e = getIdentity();
        if (e.isEmpty()) return "";
        for (String b : elements) {
            if (product(a, b).equals(e) && product(b, a).equals(e)) return b;
        }
        return "";
    }

    public String power(String a, int n) {
        if (n <= 0) throw new IllegalArgumentException("power requires n > 0, got " + n);
        String acc = a;
        for (int i = 1; i < n; i++) acc = product(acc, a);
        return acc;
    }

    public int order(String a) {
        String e = getIdentity();
        if (e.isEmpty()) return Integer.MAX_VALUE;
        String acc = a;
        int limit = Math.max(1, elements.size());
        for (int m = 1; m <= limit; m++) {
            if (acc.equals(e)) return m;
            acc = product(acc, a);
        }
        for (int m = limit + 1; m <= limit + elements.size(); m++) {
            if (acc.equals(e)) return m;
            acc = product(acc, a);
        }
        return Integer.MAX_VALUE;
    }

    public boolean isGroup() {
        for (String a : elements) for (String b : elements) {
            String r = opTable.get(key(a, b));
            if (r == null || !elements.contains(r)) return false;
        }
        for (String a : elements)
            for (String b : elements)
                for (String c : elements) {
                    String left = product(product(a, b), c);
                    String right = product(a, product(b, c));
                    if (!left.equals(right)) return false;
                }
        String e = getIdentity();
        if (e.isEmpty()) return false;
        for (String a : elements) if (getInverse(a).isEmpty()) return false;
        return true;
    }

    public boolean isCommutative() {
        for (String a : elements) for (String b : elements) {
            if (!product(a, b).equals(product(b, a))) return false;
        }
        return true;
    }

    public boolean isSubgroup(Set<String> h) {
        if (h == null || h.isEmpty()) return false;
        if (!isGroup()) return false;
        if (!elements.containsAll(h)) return false;

        String e = getIdentity();
        if (e.isEmpty() || !h.contains(e)) return false;

        for (String s : h) for (String t : h) {
            if (!h.contains(product(s, t))) return false;
        }
        for (String s : h) {
            String inv = getInverse(s);
            if (inv.isEmpty() || !h.contains(inv)) return false;
        }
        return true;
    }
}

Copilot 說

這段 Java 程式碼定義了一個不可變的類別 ProbableGroup，用來表示一個可能是群（Group）的代數結構。它使用集合和映射來描述元素與其二元運算表，並提供一系列方法來檢查這個結構是否滿足群的性質。以下是詳細解釋：

🧩 類別結構與成員

java

複製

private final Set<String> elements;
private final Map<Pair<String>, String> opTable;
  • elements：群的元素集合。
  • opTable：二元運算表，定義了每對元素的乘積結果。

🏗️ 建構子

java

複製

public ProbableGroup(Set<String> elements, Map<Pair<String>, String> opTable)
  • 將輸入的元素集合與運算表複製並設為不可變（unmodifiableSet 和 unmodifiableMap），確保外部無法修改。

🔧 核心方法解析

product(String a, String b)

  • 回傳元素 a 和 b 的乘積。
  • 若查不到對應的運算，則丟出例外。

getIdentity()

  • 嘗試找出單位元（identity element）：
    • 對所有元素 x，若 e * x = x 且 x * e = x，則 e 為單位元。
    • 若找不到，回傳空字串。

getInverse(String a)

  • 找出元素 a 的反元素 b，使得 a * b = e 且 b * a = e。
  • 若找不到，回傳空字串。

power(String a, int n)

  • 計算 a^n，即 a 自乘 n 次。
  • n 必須大於 0。

order(String a)

  • 計算元素 a 的階（order），即最小的正整數 m 使得 a^m = e。
  • 若無法找到，回傳 Integer.MAX_VALUE。

✅ 群性質檢查

isGroup()

  • 檢查是否滿足群的四個條件：
    1. 封閉性：所有 a * b 都在元素集合中。
    2. 結合律：(a * b) * c = a * (b * c)。
    3. 單位元存在。
    4. 每個元素都有反元素。

isCommutative()

  • 檢查是否為交換群（Abelian group）：a * b = b * a。

isSubgroup(Set<String> h)

  • 檢查子集合 h 是否為子群：
    • h 不為空。
    • h 是原群的子集。
    • 包含單位元。
    • 對任意 s, t ∈ h，s * t ∈ h。
    • 每個元素的反元素也在 h 中。

🧠 額外補充

  • Pair<String> 是自訂的泛型類別，用來表示二元運算的鍵。
  • 所有資料結構都使用 LinkedHashSet 和 LinkedHashMap，保留插入順序。
  • 類別是 final，表示不能被繼承。

如果你正在設計代數結構模擬器或想驗證某個集合與運算是否構成群，這個類別就是你的數學助手。你想要我幫你測試一個具體的例子嗎？比如 Z3 加法模 3？

在頁面中編輯

您說

final 的意思

Copilot 說

在 Java 中，final 是一個關鍵字，用來表示「不可變」或「不可修改」的語意。它可以用在 變數、方法、類別 上，意思略有不同：

🔒 final 變數

java

複製

final int x = 5;
  • 表示 x 是常數，一旦賦值後就不能再改變。
  • 對於物件參考（如 final List<String> list），不能改變參考，但可以修改物件內容（例如向 list 加元素）。

🚫 final 方法

java

複製

public final void doSomething() { ... }
  • 表示這個方法 不能被子類覆寫（override）。
  • 常用來保護核心邏輯不被改變。

🧱 final 類別

java

複製

public final class ProbableGroup { ... }
  • 表示這個類別 不能被繼承。
  • 用來防止擴充，確保類別行為不被改變。

在你提供的程式碼中：

java

複製

public final class ProbableGroup

這表示 ProbableGroup 是一個 封閉的類別，不能被其他類別繼承。這樣做通常是為了安全性、設計完整性，或是避免錯誤擴充。

如果你想知道什麼時候該用 final，或它在設計模式中的角色，我可以幫你深入探討。你有在用 final 來保護 FSM 模組嗎？

在頁面中編輯

最後修改日期: 2025 年 10 月 6 日

作者

留言

撰寫回覆或留言

發佈留言必須填寫的電子郵件地址不會公開。