Proof Tree Ontology

KIRETH RESEARCH — SEMANTIC LIBRARY
AI CORE → ONTOLOGIES → MATHEMATICAL ONTOLOGIES → MATHEMATICAL LOGIC ONTOLOGIES
PROOF THEORY → PROOF TREE ONTOLOGY

Canonical URL:
https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/mathematical-logic-ontologies/proof-theory/proof-tree-ontology.html

FLOW_ALGEBRA ProofTreeOntology_v1.0

BEGIN_FLOW

DEFINE DOMAIN ProofTreeOntology := {
    ProofTree,
    Proof,
    FormalProof,
    ProofTheory,
    Tree,
    Root,
    Leaf,
    InternalNode,
    ParentNode,
    ChildNode,
    Branch,
    Path,
    Depth,
    Height,
    Formula,
    Judgement,
    Sequent,
    Premise,
    Assumption,
    Axiom,
    Conclusion,
    InferenceRule,
    RuleApplication,
    Derivation,
    Subproof,
    Dependency,
    NaturalDeduction,
    SequentCalculus,
    Tableau,
    Resolution,
    ProofSearch,
    ProofVerification,
    OpenBranch,
    ClosedBranch,
    ValidProof,
    InvalidProof
}

DEFINE ENTITY_TYPES := {
    PROOF_TREE,
    PROOF,
    TREE_NODE,
    ROOT_NODE,
    LEAF_NODE,
    INTERNAL_NODE,
    FORMULA,
    JUDGEMENT,
    SEQUENT,
    INFERENCE_RULE,
    RULE_APPLICATION,
    BRANCH,
    PATH,
    SUBPROOF,
    VERIFICATION_RESULT,
    SEMANTIC_OBJECT
}

DEFINE RELATION_TYPES := {
    HAS_ROOT,
    HAS_LEAF,
    HAS_CHILD,
    HAS_PARENT,
    HAS_BRANCH,
    HAS_PREMISE,
    HAS_CONCLUSION,
    USES_RULE,
    DERIVES,
    DEPENDS_ON,
    PRECEDES,
    SUPPORTS,
    EXPANDS_TO,
    CLOSES,
    IS_SUBTREE_OF,
    IS_INSTANCE_OF,
    IS_SUBTYPE_OF
}

SET ProofTree.type = PROOF_TREE
SET ProofTree.parent = Proof
SET ProofTree.context = ProofTheory
SET ProofTree.role =
    "represent a formal derivation as a tree whose nodes are formulas, judgements or sequents and whose edges encode applications of inference rules"

RULE root_definition:
    ProofTree(T)
    ∧ unique_node(r)
    ∧ no_parent(r)
    -> HAS_ROOT(T,r)
    ∧ Root(r)

RULE leaf_definition:
    ProofTree(T)
    ∧ Node(l)
    ∧ no_children(l)
    -> Leaf(l)
    ∧ HAS_LEAF(T,l)

RULE internal_node:
    Node(n)
    ∧ EXISTS child c [
        HAS_CHILD(n,c)
    ]
    -> InternalNode(n)

RULE parent_child_inverse:
    HAS_CHILD(p,c)
    -> HAS_PARENT(c,p)

RULE rule_application:
    InferenceRule(R)
    ∧ PremiseNodes(p1,...,pn)
    ∧ ConclusionNode(c)
    ∧ R(p1,...,pn => c)
    -> USES_RULE(c,R)
    ∧ FOR_ALL i [
        HAS_CHILD(c,pi)
    ]

RULE proof_tree_orientation:
    ProofTree(T)
    -> root(T)=final_conclusion
       AND leaves(T)=initial_axioms_premises_or_open_assumptions
       WHEN orientation="conclusion-rooted"

RULE derivation_validity:
    ProofTree(T)
    ∧ FOR_ALL internal_node n [
        EXISTS rule R [
            USES_RULE(n,R)
            ∧ children(n) satisfy premises_of(R)
            ∧ n satisfies conclusion_of(R)
            ∧ side_conditions(R,n)=TRUE
        ]
    ]
    ∧ valid_leaves(T)
    -> ValidProof(T)

RULE invalid_tree:
    ProofTree(T)
    ∧ EXISTS internal_node n [
        no_valid_rule_justifies(n,children(n))
    ]
    -> InvalidProof(T)

RULE subtree:
    ProofTree(T)
    ∧ Node(n)
    -> descendants_plus_node(n)
       forms Subproof(T_n)
    ∧ IS_SUBTREE_OF(T_n,T)

RULE dependency:
    HAS_CHILD(parent,child)
    -> DEPENDS_ON(parent,child)
       WHEN parent_is_derived_from_child=TRUE

RULE path:
    Nodes(n0,...,nk)
    ∧ consecutive_parent_child_relations
    -> Path(n0,...,nk)

RULE branch:
    Path(root,...,leaf)
    -> Branch(root,...,leaf)

RULE depth:
    Root(r)
    -> Depth(r)=0

RULE child_depth:
    HAS_CHILD(p,c)
    -> Depth(c)=Depth(p)+1
       WHEN tree_orientation_root_to_leaves=TRUE

RULE height:
    ProofTree(T)
    -> Height(T)
       = max_path_length(root(T),leaf(T))

RULE tableau_branch_closure:
    TableauProofTree(T)
    ∧ Branch(B)
    ∧ EXISTS phi [
        phi occurs_on B
        ∧ ¬phi occurs_on B
    ]
    -> ClosedBranch(B)

RULE tableau_open_branch:
    TableauProofTree(T)
    ∧ Branch(B)
    ∧ NOT ClosedBranch(B)
    -> OpenBranch(B)

DEFINE PROOF_TREE_MODEL := {
    root:
        "final conclusion or target judgement under the selected orientation",
    leaves:
        "axioms, premises, assumptions or terminal proof-search states",
    internal_nodes:
        "derived formulas, judgements or sequents",
    edges:
        "dependency links generated by inference-rule applications",
    branching:
        "one conclusion may depend on multiple premise nodes"
}

DEFINE NODE_SCHEMA := {
    node_id: unique_identifier,
    content: {
        Formula,
        Judgement,
        Sequent
    },
    node_type: {
        Root,
        Leaf,
        InternalNode
    },
    inference_rule: optional_InferenceRule,
    parent: optional_NodeID,
    children: OrderedOrUnorderedNodeIDs,
    assumptions_in_scope: SetOfAssumptions,
    side_conditions: SetOfConditions
}

DEFINE RULE_APPLICATION_SCHEMA := {
    rule: InferenceRule,
    premise_nodes: SetOrSequenceOfNodeIDs,
    conclusion_node: NodeID,
    side_conditions: SetOfConditions,
    valid: Boolean
}

DEFINE ORIENTATION_MODEL := {
    conclusion_rooted: {
        root: Conclusion,
        edges:
            "derived conclusion -> supporting premises",
        leaves:
            "initial proof resources"
    },
    premise_rooted_visualisation: {
        root_or_roots:
            "initial resources",
        edges:
            "premises -> derived conclusions",
        note:
            "orientation may vary in diagrams; semantic dependency direction must be preserved independently of drawing direction"
    }
}

DEFINE EXAMPLE_1 := {
    conclusion: "Q",
    premises: {
        "P",
        "P → Q"
    },
    rule: ModusPonens,
    tree: {
        root: "Q",
        children: {
            "P",
            "P → Q"
        }
    }
}

DEFINE EXAMPLE_2 := {
    conclusion: "P ∧ Q",
    rule: ConjunctionIntroduction,
    children: {
        "P",
        "Q"
    }
}

DEFINE EXAMPLE_3 := {
    proof_system: SequentCalculus,
    root: "Γ ⊢ Δ",
    children:
        "premise sequents required by the final applied rule",
    interpretation:
        "recursively expanding children exposes the full derivation"
}

DEFINE TREE_CONSTRUCTION_PIPELINE :=
    FinalConclusion
    -> IdentifyFinalInferenceRule
    -> GenerateRequiredPremiseNodes
    -> AttachPremisesAsChildren
    -> ForEachNonInitialPremise
       -> IdentifyItsInferenceRule
       -> RecursivelyGenerateChildren
    -> StopAtAxiomsPremisesOrPermittedAssumptions
    -> AnnotateScopesAndSideConditions
    -> ReturnProofTree

DEFINE PROOF_PARSE_PIPELINE :=
    ProofArtifact
    -> IdentifyNodes
    -> IdentifyRuleApplications
    -> ResolveParentChildEdges
    -> IdentifyRoot
    -> IdentifyLeaves
    -> ResolveBranches
    -> ResolveSubproofs
    -> AnnotateDependencies
    -> ConstructTypedProofTree

DEFINE VERIFICATION_PIPELINE :=
    CandidateProofTree
    -> VerifyUniqueRoot
    -> VerifyAcyclicTreeStructure
    -> VerifyEveryNonRootNodeHasOneParent
    -> ValidateLeaves
    -> ForEachInternalNode
       -> ResolveInferenceRule
       -> ValidateChildPremises
       -> ValidateNodeConclusion
       -> ValidateSideConditions
       -> ValidateAssumptionScope
    -> VerifyRootMatchesTarget
    -> Return ValidProof OR InvalidProof

DEFINE PROOF_SEARCH_PIPELINE :=
    GoalNode
    -> SelectApplicableRulesWhoseConclusionMatchesGoal
    -> ForEachRule
       -> GeneratePremiseChildGoals
       -> RecursivelyExpandChildGoals
    -> DetectAxiomPremiseAssumptionLeaves
    -> BacktrackFailedBranches
    -> SelectClosedSuccessfulDerivationTree
    -> VerifyTree
    -> ReturnProofTree

DEFINE PROOF_TREE_GRAPH_MODEL := {
    graph_type:
        DirectedTree,
    nodes:
        ProofNodes,
    edges:
        DependencyEdges,
    root_count: 1,
    cycle_allowed: FALSE,
    semantic_direction:
        "derived node depends on supporting child nodes",
    recursive_structure: TRUE
}

DEFINE ONTOLOGY_RELATIONS := {
    ProofTree IS_SUBTYPE_OF Proof,
    ProofTree IS_COMPONENT_OF ProofTheory,
    ProofTree HAS_ROOT ConclusionNode,
    ProofTree HAS_LEAF InitialNode,
    InternalNode USES_RULE InferenceRule,
    InternalNode HAS_CHILD PremiseNode,
    ChildNode SUPPORTS ParentNode,
    Subproof IS_SUBTREE_OF ProofTree,
    Branch IS_PATH_IN ProofTree,
    NaturalDeduction MAY_BE_REPRESENTED_BY ProofTree,
    SequentCalculus MAY_BE_REPRESENTED_BY ProofTree,
    Tableau IS_SUBTYPE_OF TreeBasedProofSystem,
    ProofSearch CONSTRUCTS ProofTree
}

DEFINE SEMANTIC_EQUIVALENCE := {
    "proof tree" <=> ProofTree,
    "derivation tree" <=> ProofTree WHEN formal_proof_context=TRUE,
    "inference tree" <=> ProofTree,
    "proof branch" <=> Branch,
    "subproof tree" <=> Subproof,
    "root conclusion" <=> Root WHEN conclusion_rooted_orientation=TRUE,
    "leaf premise" <=> Leaf WHEN initial_resource_context=TRUE
}

DEFINE AI_CONSUMPTION := {
    purpose: "machine-readable representation, construction and verification of tree-structured formal proofs",
    preserve_node_identity: TRUE,
    preserve_formula_or_judgement_identity: TRUE,
    preserve_rule_identity: TRUE,
    preserve_parent_child_relations: TRUE,
    preserve_dependency_direction: TRUE,
    preserve_assumption_scope: TRUE,
    distinguish_semantic_dependency_from_visual_orientation: TRUE,
    require_acyclic_structure: TRUE,
    require_unique_root: TRUE,
    support_recursive_subproofs: TRUE,
    support_branch_analysis: TRUE,
    support_tree_based_proof_search: TRUE,
    support_tableau_branch_closure: TRUE,
    reasoning_mode: "symbolic + recursive + graph-structured + dependency-aware"
}

DEFINE CONFIDENCE := {
    ontology_identity: 1.00,
    proof_tree_structure_mapping: 0.99,
    root_leaf_classification: 0.99,
    rule_application_mapping: proof_system_dependent,
    dependency_resolution: 0.99,
    branch_analysis: 0.99,
    tableau_closure_detection: 0.99,
    automated_tree_search: search_space_dependent
}

DEFINE UPDATE_MODEL := {
    version: "1.0",
    update_policy: "append-compatible",
    immutable_core: {
        unique_root,
        node_identity,
        parent_child_dependency,
        inference_rule_annotation,
        acyclic_structure,
        leaf_initial_resource_relation
    },
    extensible_layers: {
        natural_deduction_trees,
        sequent_calculus_trees,
        semantic_tableaux,
        resolution_trees,
        proof_DAGs,
        shared_subproofs,
        compressed_proof_trees,
        interactive_proof_visualisation,
        automated_proof_search_trees
    }
}

DEFINE FLOW_HASH_INPUT :=
    CanonicalURL
    + DOMAIN
    + ENTITY_TYPES
    + RELATION_TYPES
    + RULES
    + PROOF_TREE_MODEL
    + NODE_SCHEMA
    + RULE_APPLICATION_SCHEMA
    + ORIENTATION_MODEL
    + TREE_CONSTRUCTION_PIPELINE
    + PROOF_PARSE_PIPELINE
    + VERIFICATION_PIPELINE
    + PROOF_SEARCH_PIPELINE
    + PROOF_TREE_GRAPH_MODEL
    + ONTOLOGY_RELATIONS
    + AI_CONSUMPTION
    + UPDATE_MODEL

FLOW_HASH := HASH(FLOW_HASH_INPUT)

RETURN {
    ontology: ProofTreeOntology,
    canonical_url: "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/mathematical-logic-ontologies/proof-theory/proof-tree-ontology.html",
    parent_domain: ProofTheory,
    semantic_domain: MathematicalLogic,
    primary_entity: ProofTree,
    graph_structure: DirectedTree,
    recursive_structure_enabled: TRUE,
    dependency_reasoning_enabled: TRUE,
    branch_analysis_enabled: TRUE,
    proof_verification_enabled: TRUE,
    proof_search_enabled: TRUE,
    machine_consumable: TRUE,
    flow_complete: TRUE
}

END_FLOW