人工知能的代数学(9)

マグマの計算(3)

前回の「マグマの左単位元と右単位元」では、等式の集合から推移律によって新しい等式の集合を作っていましたが、等式の数が多くなりすぎるので、「エレファントな群とリー代数(1) - エレファント・ビジュアライザー調査記録」と同様に一つの式から等式によって変形していくようにしました。結果的には「エレファントな群とリー代数(1) - エレファント・ビジュアライザー調査記録」のプログラムを Python で書き換えたようになっています。こうするとブログで書けるぐらいの数になりました。

class Exp:
    pass

# Multiplication クラス
class Multiplication(Exp):
    def __init__(self, left, right):
        self.left = left
        self.right = right
        self.operator = " * "
        self.tex_operator = " "

    def __str__(self):
        if isinstance(self.left, Multiplication):
            left_str = "(" + str(self.left) + ")"
        else:
            left_str = str(self.left)
        if isinstance(self.right, Multiplication):
            right_str = "(" + str(self.right) + ")"
        else:
            right_str = str(self.right)
        return left_str + self.operator + right_str

    def __repr__(self):
        return f"Multiplication({self.left}, {self.right})"

    def texstr(self):
        if isinstance(self.left, Multiplication):
            left_str = "(" + self.left.texstr() + ")"
        else:
            left_str = self.left.texstr()
        if isinstance(self.right, Multiplication):
            right_str = "(" + self.right.texstr() + ")"
        else:
            right_str = self.right.texstr()
        return left_str + self.tex_operator + right_str

    def visit_sub_expressions(self, sub_expressions):
        sub_expressions.append(self)
        self.left.visit_sub_expressions(sub_expressions)
        self.right.visit_sub_expressions(sub_expressions)

    def count_sub_expressions(self):
        count1 = self.left.count_sub_expressions()
        count2 = self.right.count_sub_expressions()
        return count1 + count2 + 1

    def replace_sub_expression(self, index_here, index, exp):
        if index_here == index:
            return exp
        else:
            exp1 = self.left.replace_sub_expression(index_here + 1, index, exp)
            count1 = self.left.count_sub_expressions()
            exp2 = self.right.replace_sub_expression(index_here + count1 + 1, index, exp)
            return Multiplication(exp1, exp2)

# Variable クラス
class Variable(Exp):
    def __init__(self, name):
        self.name = name

    def __str__(self):
        return self.name

    def __repr__(self):
        return f"Variable({self.name})"

    def texstr(self):
        return self.name

    def visit_sub_expressions(self, sub_expressions):
        sub_expressions.append(self)

    def count_sub_expressions(self):
        return 1

    def replace_sub_expression(self, index_here, index, exp):
        if index_here == index:
            return exp
        else:
            return self

# Constant クラス
class Constant(Exp):
    def __init__(self, name):
        self.name = name

    def __str__(self):
        return self.name

    def __repr__(self):
        return f"Constant({self.name})"

    def texstr(self):
        return self.name

    def visit_sub_expressions(self, sub_expressions):
        sub_expressions.append(self)

    def count_sub_expressions(self):
        return 1

    def replace_sub_expression(self, index_here, index, exp):
        if index_here == index:
            return exp
        else:
            return self

class SubExpressions:
    def __init__(self):
        self.sub_expressions = []

    def append(self, node):
            self.sub_expressions.append(node)

class Equation:
    def __init__(self, left, right):
        self.left = left
        self.right = right

    def __str__(self):
        return str(self.left) + " = " + str(self.right)

    def __repr__(self):
        return f"Equation({self.left} = {self.right})"

    def texstr(self):
        return self.left.texstr() + " = " + self.right.texstr()
    
    def reverse(self):
        return Equation(self.right, self.left)
    
from lark import Transformer, v_args

@v_args(inline=True)  # 引数をリストではなく個別の要素として受け取る
class CustomTransformer(Transformer):
    def equation(self, left, right):
        return Equation(left, right)  # 等式

    def multiplication(self, left, right):
        return Multiplication(left, right)  # Multiplication オブジェクトとして返す

    def expression(self, item):
        return item

    def term(self, item):
        return item

    def atom(self, item):
        return item

    def VARIABLE(self, name):
        return Variable(str(name))  # Variable オブジェクトとして返す

    def CONSTANT(self, name):
        return Constant(str(name))  # Constant オブジェクトとして返す
    
# グラマー定義
grammar = """
?start: equation

equation: expression "=" expression

expression: term
    | expression "*" term -> multiplication  # 二項演算子

term: atom
    | "(" expression ")"  # 括弧を使った演算

atom: VARIABLE
    | CONSTANT  # 変数と定数

VARIABLE: /[A-Z][a-zA-Z_]*/  # 大文字で始まる変数
CONSTANT: /[a-z][a-zA-Z_]*/  # 小文字で始まる定数

%ignore " "  # 空白を無視
"""

class Unifier:
    def __init__(self):
        self.substitutions = {}  # 置き換えのマップ

    def unify(self, expr1, x1, expr2, x2):
        if isinstance(expr1, Variable):
            if (expr1.name, x1) in self.substitutions:
                val_expr, val_x = self.substitutions[(expr1.name, x1)]
                return self.unify(val_expr, val_x, expr2, x2)
            else:
                self.substitutions[(expr1.name, x1)] = (expr2, x2)
                return True
        elif isinstance(expr2, Variable):
            return self.unify(expr2, x2, expr1, x1)
        elif isinstance(expr1, Constant):
            return isinstance(expr2, Constant) and expr1.name == expr2.name
        elif isinstance(expr1, Multiplication):
            return isinstance(expr2, Multiplication) and self.unify(expr1.left, x1, expr2.left, x2) and self.unify(expr1.right, x1, expr2.right, x2)
        else:
            return False

    def value(self, expr, x):
        if isinstance(expr, Variable):
            if (expr.name, x) in self.substitutions:
                val_expr, val_x = self.substitutions[(expr.name, x)]
                return self.value(val_expr, val_x)
            else:
                return expr
        elif isinstance(expr, Multiplication):
            return Multiplication(self.value(expr.left, x), self.value(expr.right, x))
        else:
            return expr

class TransitiveTransformer:
    def __init__(self, equations, exp):
        self.equations = equations
        self.expressions = [exp]
        self.history = [[exp]]

    def compose_transitive(self, expr1, eq2, his):
        # 式 expr1 と等式 eq2 を組み合わせる
        # expr1 (の一部)と eq2 の左辺が一致するとき
        # expr1 = eq2.left = eq2.right と変形する
        expr2 = eq2.left
        sub_expressions = SubExpressions()
        expr1.visit_sub_expressions(sub_expressions)
        for index, sub_exp1 in enumerate(sub_expressions.sub_expressions):
            unifier = Unifier()
            if unifier.unify(sub_exp1, 1, expr2, 2):
                # expr1 の一部と eq2 の左辺が一致
                # expr1 の一部を eq2 の右辺で置き換える
                exp_new2 = expr1.replace_sub_expression(0, index, eq2.right)
                exp2 = unifier.value(exp_new2, 2)
                self.expressions.append(exp2)
                self.history.append(his + [exp2])

    def compose_transitive_all(self):
        expressions = self.expressions
        history = self.history
        self.expressions = []
        self.history = []
        for index, exp in enumerate(expressions):
            for eq in self.equations:
                self.compose_transitive(exp, eq, history[index])
                self.compose_transitive(exp, eq.reverse(), history[index])

    def transitive_degree(self, deg):
        for n in range(1, deg + 1):
            transitive_transformer.compose_transitive_all()
            print(f"結果({n}回目)のリスト")
            for his in transitive_transformer.history:
                print(" = ".join([e.texstr() for e in his]))

# 構文解析
from lark import Lark
parser = Lark(grammar, parser="lalr")
custom_transformer = CustomTransformer()

eq1 = custom_transformer.transform(parser.parse("X*e_r=X"))
eq2 = custom_transformer.transform(parser.parse("e_l*X=X"))

# 左辺が最初の式(右辺は使わない)
exp = custom_transformer.transform(parser.parse("e_l=e_r")).left

# 入力として等式のリストを提供
equations = [eq1, eq2]
print("元の等式のリスト")
for eq in equations:
    print(eq.texstr())

transitive_transformer = TransitiveTransformer(equations, exp)

transitive_transformer.transitive_degree(2)

結果

元の等式のリスト


結果(1回目)のリスト


結果(2回目)のリスト

代数学のレッスン---計算体験を重視する入門

代数学１　群論入門　第２版

代数学２　環と体とガロア理論　第２版

代数入門（新装版）　群と加群 数学シリーズ

代数学入門 NBS (日評ベーシック・シリーズ)

加群からはじめる代数学入門---線形代数学から抽象代数学へ

群論への第一歩　集合、写像から準同型定理まで

群論入門　対称性をはかる数学 (ブルーバックス)

群論　NBS (日評ベーシック・シリーズ)

独習　ガロア理論

ガロア理論の頂を踏む

今度こそわかるガロア理論 (今度こそわかるシリーズ)

ガロア理論12講 概念と直観でとらえる現代数学入門

ガロア理論入門 (ちくま学芸文庫 ア 33-1 Math&Science)