Symbolic AI Ontology

FLOW_ALGEBRA AutomatedReasoningOntology v1.0
TARGET_URL := "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/mathematical-logic-ontologies/ai-logic/automated-reasoning-ontology.html"
LANGUAGE := "en-GB"
DOMAIN := MathematicalOntologies > MathematicalLogicOntologies > AILogic > AutomatedReasoningOntology

BEGIN_FLOW

ENTITY AutomatedReasoning {
 TYPE := ComputationalFormalReasoning
 DEFINITION := "The use of algorithms and formal logical procedures to derive, verify, refute or evaluate conclusions from machine-represented premises, axioms, rules, constraints or models."
}
ENTITY Premise { TYPE := AssertedFormulaOrKnowledgeItem }
ENTITY Axiom { TYPE := AssumedFormalStatement }
ENTITY InferenceRule { TYPE := ValidTransformationSchema }
ENTITY Proof { TYPE := VerifiedDerivation }
ENTITY ReasoningEngine { TYPE := ComputationalInferenceMechanism }

RELATIONSHIP AutomatedReasoning --uses--> Premise
RELATIONSHIP AutomatedReasoning --uses--> Axiom
RELATIONSHIP AutomatedReasoning --uses--> InferenceRule
RELATIONSHIP AutomatedReasoning --produces--> Proof
RELATIONSHIP AutomatedReasoning --implemented_by--> ReasoningEngine
RELATIONSHIP AutomatedReasoning --supports--> ArtificialIntelligence

REASONING_SYSTEM {
 COMPONENTS := {
  FormalLanguage,Syntax,Semantics,KnowledgeBase,
  Calculus,SearchProcedure,Verifier,ExplanationTrace
 }
}

FORMAL_PROBLEM {
 INPUT := {Premises,Axioms,Goal,Logic,Calculus}
 OUTPUT := {Proof,Countermodel,Model,UNSAT,SAT,Unknown,Timeout}
}

SEMANTIC_ENTAILMENT {
 Gamma entails phi
 IFF every model_of_Gamma satisfies phi
}
SYNTACTIC_DERIVABILITY {
 Gamma proves phi
 IFF phi derivable_from_Gamma using selected_calculus
}
SOUNDNESS {
 Gamma proves phi -> Gamma entails phi
 REQUIRE sound_calculus
}
COMPLETENESS {
 Gamma entails phi -> Gamma proves phi
 REQUIRE completeness_for_selected_logic_and_calculus
}
DECIDABILITY {
 DecisionProblem has terminating_correct_algorithm
 for every valid_input
}

PROOF {
 STRUCTURE := SequenceTreeOrDAGOfInferenceSteps
}
PROOF_STEP {
 Premises + InferenceRule + SideConditions -> Conclusion
}
PROOF_CHECKING {
 ProofCandidate -> VerifyEveryStep -> ValidOrInvalidProof
}
PROOF_CERTIFICATE {
 TYPE := MachineCheckableEvidence
}

THEOREM_PROVING {
 Axioms + Conjecture -> SearchForProof
}
REFUTATION_PROVING {
 Axioms + NOT(Conjecture) -> DeriveContradiction
}
MODEL_FINDING {
 FormulaSet -> SearchForSatisfyingInterpretation
}
COUNTERMODEL_FINDING {
 Premises + CandidateConclusion
 -> ModelSatisfyingPremisesAndFalsifyingConclusion
}
MODEL_CHECKING {
 Model + Property -> SatisfactionResult
}

PROPOSITIONAL_REASONING {
 Formulae -> SATOrProofProcedures
}
FIRST_ORDER_REASONING {
 QuantifiedFormulae -> UnificationResolutionTableauOrOtherCalculus
}
DESCRIPTION_LOGIC_REASONING {
 OntologyAxioms -> ConsistencySubsumptionClassificationInstanceChecking
}
MODAL_REASONING {
 ModalFormulae -> FrameOrProofReasoning
}
TEMPORAL_REASONING {
 TemporalFormulae -> TraceStateOrAutomataReasoning
}

RESOLUTION {
 ComplementaryLiteralsInClauses -> Resolvent
}
FIRST_ORDER_RESOLUTION {
 Clauses + MGU -> Resolvent
}
UNIFICATION {
 TermsOrAtoms -> Substitution -> MatchingExpressions
}
MOST_GENERAL_UNIFIER {
 ABBREVIATION := MGU
}
FACTORING {
 Clause + UnifiableLiterals -> SimplifiedClause
}
CLAUSIFICATION {
 Formula -> Normalisation -> Skolemisation -> CNF -> ClauseSet
}
SKOLEMISATION {
 PRESERVES := Equisatisfiability
 MUST_NOT be treated_as UnrestrictedEquivalence
}

NATURAL_DEDUCTION {
 IntroductionRules + EliminationRules -> Proof
}
SEQUENT_CALCULUS {
 Sequents + SequentRules -> Derivation
}
TABLEAU_REASONING {
 Formulae -> ExpansionRules -> OpenOrClosedBranches
}
TERM_REWRITING {
 Terms + RewriteRules -> NormalFormsOrDerivedEqualities
}
SUPERPOSITION {
 EqualityReasoning + OrderedInference -> TheoremProvingWithEquality
}

SAT_SOLVING {
 BooleanCNF -> SatisfyingAssignmentOrUNSAT
}
DPLL {
 Branching + UnitPropagation + Backtracking -> SATDecision
}
CDCL {
 Decisions + Propagation + ConflictAnalysis
 + ClauseLearning + Backjumping
 -> SATDecision
}
UNIT_PROPAGATION {
 UnitClause -> ForcedLiteralAssignment
}
CLAUSE_LEARNING {
 Conflict -> LearnedClause -> FutureSearchPruning
}
UNSAT_PROOF {
 UNSATResult -> ProofCertificateWhereSupported
}

SMT_SOLVING {
 BooleanStructure + TheoryConstraints -> SATModuloTheoriesOrUNSAT
}
DPLL_T {
 SATCore + TheorySolver -> SMTProcedure
}
THEORY_PROPAGATION {
 TheoryFacts -> ImpliedTheoryLiterals
}
THEORY_CONFLICT {
 TheoryInconsistentAssignment -> ConflictExplanation
}

CONSTRAINT_REASONING {
 Variables + Domains + Constraints -> Propagation + Search
}
CONSTRAINT_PROPAGATION {
 RemoveUnsupportedValues -> ReducedDomains
}
BACKTRACKING {
 Branch -> Propagate -> FailureOrContinue -> RestoreState
}
NOGOOD_LEARNING {
 FailedPartialAssignment -> LearnedNogood
}

FORWARD_CHAINING {
 Facts + Rules -> IterativeConsequences -> FixedPointOrGoal
}
BACKWARD_CHAINING {
 Goal -> SupportingRules -> Subgoals -> ProofOrFailureStatus
}
DATALOG_EVALUATION {
 PositiveFunctionFreeRules -> LeastFixedPoint
}
SLD_RESOLUTION {
 HornClauses + SelectedGoal + Unification -> GoalReduction
}

ONTOLOGY_REASONING {
 TBox + ABox + RBox -> Entailments
}
CLASSIFICATION {
 AssertedHierarchy + Axioms -> InferredHierarchy
}
INSTANCE_CHECKING {
 KB + C(a) -> EntailedOrNotEntailed
}
CONSISTENCY_CHECKING {
 KB -> ModelExistsOrInconsistent
}
CONCEPT_SATISFIABILITY {
 Concept + KB -> SatisfiableOrUnsatisfiable
}

KNOWLEDGE_GRAPH_REASONING {
 GraphStatements + Schema + Rules -> DerivedStatements
}
TRANSITIVE_REASONING {
 R(a,b) AND R(b,c) -> R(a,c)
 REQUIRE R declared_transitive
}
SUBCLASS_REASONING {
 C subclass_of D
 D subclass_of E
 -> C subclass_of E
}
INSTANCE_PROPAGATION {
 a instance_of C
 C subclass_of D
 -> a instance_of D
}

SEARCH_SPACE {
 NODES := ReasoningStates
 EDGES := InferenceChoices
}
DEPTH_FIRST_SEARCH {
 explores_one_branch_deeply
}
BREADTH_FIRST_SEARCH {
 explores_states_level_by_level
}
BEST_FIRST_SEARCH {
 prioritises_states_by_heuristic
}
ITERATIVE_DEEPENING {
 repeated_depth_limited_search_with_increasing_bound
}
HEURISTIC {
 estimates promising_inference_or_state
}
HEURISTIC_WARNING {
 FailedHeuristicSearch DOES_NOT prove NonDerivability
}
FAIRNESS {
 CompleteSearchClaim SHOULD ensure
 necessary_eligible_inferences eventually_considered
}
LOOP_DETECTION {
 RepeatedReasoningState -> PruneOrMemoise
}
MEMOISATION {
 CachePreviouslySolvedSubproblems
}
TABLING {
 StoreGoalAnswersToAvoidRepeatedSearch
}

SATURATION {
 RepeatedlyApplyEligibleInferences
 Until FixedPointOrGoalOrResourceLimit
}
GIVEN_CLAUSE_ALGORITHM {
 PassiveClauses + ActiveClauses
 -> Select -> Simplify -> Infer -> Repeat
}
SUBSUMPTION {
 RemoveClausesRedundantUnderDeclaredSemantics
}
TAUTOLOGY_DELETION {
 RemoveTautologicalClausesWhereSound
}
ORDERED_INFERENCE {
 RestrictInferenceByTermOrLiteralOrdering
 REQUIRE completeness_conditions_if_claimed
}
PROOF_SEARCH_CONTROL {
 MAY_USE := {
  GoalRelevance,ClauseWeight,Age,LiteralSelection,
  TermOrdering,SetOfSupport,UnitPreference
 }
}
SEARCH_EXPLOSION {
 MITIGATION := {
  Indexing,Caching,Subsumption,Ordering,
  Learning,RelevanceFiltering,Parallelism
 }
}

INDEXING {
 MAY_INDEX := {
  Terms,Literals,Predicates,Clauses,Facts,Classes,Properties
 }
}
DISCRIMINATION_TREE_RELATIONSHIP {
 term_indexing_for_candidate_retrieval
}
SUBSTITUTION_TREE_RELATIONSHIP {
 unification_or_instance_retrieval_index
}

PARALLEL_REASONING {
 IndependentInferences MAY execute_concurrently
 REQUIRE sound_merge_semantics
}
DISTRIBUTED_REASONING {
 KnowledgeAndSearch MAY be_partitioned
 REQUIRE coordination_and_consistency_model
}
INCREMENTAL_REASONING {
 KnowledgeChange -> RecomputeAffectedConsequencesOnly
}
MATERIALISATION {
 PrecomputeEntailments -> StoreDerivedKnowledge
}
QUERY_TIME_REASONING {
 DeriveConsequencesDuringQuery
}

NONMONOTONIC_AUTOMATED_REASONING {
 Defaults + Exceptions + Priorities -> RetractableConclusions
 REQUIRE nonmonotonic_semantics
}
PARACONSISTENT_AUTOMATED_REASONING {
 ContradictionsDoNotNecessarilyExplode
 REQUIRE paraconsistent_semantics
}
FUZZY_AUTOMATED_REASONING {
 GradedTruth + FuzzyRules -> FuzzyConclusions
 REQUIRE fuzzy_semantics
}
PROBABILISTIC_AUTOMATED_REASONING {
 ProbabilisticModel + Evidence -> PosteriorOrProbabilityResult
 REQUIRE probability_semantics
}

PROOF_TRACE {
 RECORD := {
  Step,Premises,Rule,Substitution,
  SideConditions,Conclusion,Dependencies
 }
}
PROVENANCE {
 DerivedConclusion -> SourceAxiomsFactsRules -> ReasoningProcedure
}
JUSTIFICATION {
 Entailment -> SupportingKnowledgeSubset
}
MINIMAL_JUSTIFICATION {
 subset_minimal_support
}
EXPLANATION {
 Result -> ProofTraceOrModel -> Justification -> Provenance
}

VERIFY_INFERENCE_STEP(S) {
 CHECK Premises
 CHECK Rule
 CHECK Substitution
 CHECK SideConditions
 CHECK Conclusion
 RETURN ValidOrFailure
}
VERIFY_PROOF(P) {
 FOR_EACH Step:
  VERIFY_INFERENCE_STEP
 RETURN ValidProofIfAllStepsValid
}
VERIFY_MODEL(M,KB) {
 CHECK every_axiom_and_constraint
 under declared_semantics
 RETURN ModelValidity
}

RESULT_STATUS {
 TYPES := {
  Proven,Refuted,Satisfiable,Unsatisfiable,
  Entailed,NotEntailed,Unknown,Timeout,Invalid
 }
}
UNKNOWN_WARNING {
 Unknown MUST_NOT be interpreted_as False
}
TIMEOUT_WARNING {
 Timeout MUST_NOT be interpreted_as NonEntailmentOrSatisfiability
}
SEARCH_FAILURE_WARNING {
 FailureToFindProofWithinBounds
 MUST_NOT automatically establish NoProofExists
}

RESOURCE_LIMIT {
 MAY_INCLUDE := {
  Time,Memory,Depth,InferenceCount,ClauseCount
 }
}
ANYTIME_REASONING {
 MAY return partial_results
 REQUIRE completeness_and_status_metadata
}
APPROXIMATE_REASONING {
 MAY relax search_coverage_or_completeness
 REQUIRE explicit_approximation_metadata
}
CORRECTNESS_FIRST {
 Optimisation MUST_NOT silently alter formal_semantics
}

AUTOMATED_REASONING_VS_MACHINE_LEARNING {
 AutomatedReasoning := FormalRulesSemanticsAndSearch
 MachineLearning := LearnedStatisticalOrFunctionalModels
 MAY_COMBINE := TRUE
}
AUTOMATED_REASONING_VS_INFERENCE_ENGINE {
 AutomatedReasoning := DisciplineAndMethods
 InferenceEngine := ComputationalMechanismExecutingReasoning
}
AUTOMATED_REASONING_VS_SEARCH {
 Search := ExploreAlternatives
 AutomatedReasoning := SearchConstrainedByFormalInferenceAndSemantics
}

NEURO_SYMBOLIC_RELATIONSHIP {
 LearnedModels + SymbolicRepresentations + AutomatedReasoning
 -> HybridSystem
}
LANGUAGE_MODEL_RELATIONSHIP {
 LanguageModel MAY propose {
  CandidatePremises,CandidateRules,CandidateProofSteps,Explanations
 }
 REQUIRE formal_verification_before_acceptance_as_proof
}
GENERATED_PROOF_WARNING {
 FluentOrPlausibleProofText DOES_NOT equal VerifiedProof
}
TOOL_AUGMENTED_REASONING {
 Reasoner -> SolverOrProverTool -> Result -> Verification -> IntegratedReasoningState
}

RECURSIVE_REASONING {
 Goal -> Decompose -> SolveSubgoal -> Verify -> Integrate -> Continue
}
RECURSION_TERMINATION {
 STOP_WHEN := {
  ProofFound,CountermodelFound,FixedPoint,
  UNSAT,SAT,NoValidProgress,ResourceLimit
 }
}
SELF_VERIFICATION {
 CandidateProofOrResult -> FormalChecker -> AcceptOrReject
}

APPLICATION_RELATIONSHIPS {
 AutomatedReasoning --supports--> ArtificialIntelligence
 AutomatedReasoning --supports--> AutomatedTheoremProving
 AutomatedReasoning --supports--> FormalVerification
 AutomatedReasoning --supports--> KnowledgeRepresentation
 AutomatedReasoning --supports--> Ontologies
 AutomatedReasoning --supports--> KnowledgeGraphs
 AutomatedReasoning --supports--> ConstraintSolving
 AutomatedReasoning --supports--> LogicProgramming
 AutomatedReasoning --supports--> Planning
 AutomatedReasoning --supports--> DecisionSupport
}

ONTOLOGY_LINKS {
 PARENT := AILogicOntology
 RELATED := {
  ArtificialIntelligenceLogicOntology,
  LogicalInferenceOntology,
  DeductiveReasoningOntology,
  ResolutionOntology,
  ConstraintReasoningOntology,
  RuleBasedReasoningOntology,
  DescriptionLogicOntology,
  InferenceEngineOntology,
  KnowledgeGraphLogicOntology,
  SatisfiabilityOntology,
  ProofTheoryOntology
 }
}

SEMANTIC_EQUIVALENCE {
 AutomatedReasoning ≈ MachineAutomatedFormalReasoning
 AutomatedTheoremProving ≈ AutomatedProofSearch
  WHEN theorem_proving_context
 ProofChecking ≈ FormalProofVerification
 CountermodelFinding ≈ SemanticRefutationByModel
}

CONSTRAINTS {
 C1 := EveryDerivedStep MUST be valid under selected_calculus
 C2 := SoundnessCompletenessDecidability claims MUST be scoped to logic_and_procedure
 C3 := SyntacticDerivability MUST_NOT be conflated with SemanticEntailment
 C4 := FailureToFindProof MUST_NOT automatically establish NonEntailment
 C5 := Timeout MUST_NOT be interpreted_as logical_falsehood
 C6 := HeuristicAndApproximateSearch MUST disclose relaxed_guarantees
 C7 := Proofs SHOULD preserve premises_rules_substitutions_and_dependencies
 C8 := Countermodel claims MUST satisfy premises and falsify target
 C9 := NonmonotonicFuzzyProbabilisticParaconsistent reasoning MUST identify semantics
 C10 := OptimisationAndParallelisation MUST preserve correctness unless approximation_declared
 C11 := GeneratedProofCandidates MUST be formally_verified before accepted_as_proofs
 C12 := ResultStatus MUST accurately represent proof_model_search_or_resource_outcome
}

REASONING_CHAIN Query Q {
 IDENTIFY logic
 IDENTIFY premises_or_axioms
 IDENTIFY goal
 IDENTIFY reasoning_task
 IDENTIFY calculus_or_solver
 IDENTIFY search_strategy
 IDENTIFY resource_limits

 VALIDATE syntax_and_semantics
 NORMALISE input_if_required

 IF proof_task:
  SEARCH derivation

 IF refutation_task:
  ADD negated_goal
  SEARCH contradiction

 IF model_task:
  SEARCH satisfying_model

 IF countermodel_task:
  SEARCH model_satisfying_premises_and_falsifying_goal

 IF SAT_task:
  RUN SAT_procedure

 IF SMT_task:
  RUN SMT_procedure

 IF ontology_task:
  RUN selected_ontology_reasoner

 IF constraint_task:
  PROPAGATE_and_SEARCH

 VERIFY proof_or_model_certificate
 BUILD provenance
 BUILD explanation
 ASSIGN accurate_result_status
 VALIDATE constraints
 RETURN automated_reasoning_result WITH trace
}

CONFIDENCE {
 CORE_AUTOMATED_REASONING := 1.00
 SOUNDNESS_COMPLETENESS_DISTINCTION := 1.00
 PROOF_MODEL_DISTINCTION := 1.00
 RESOLUTION_RELATIONSHIP := 1.00
 SAT_SMT_RELATIONSHIP := 1.00
 ONTOLOGY_CONSTRAINT_RELATIONSHIP := 1.00
 GENERATED_PROOF_VERIFICATION := 1.00
}

UPDATE_MODEL {
 IMMUTABLE_CORE := {
  FormalInference,
  SemanticValidity,
  ProofVerification,
  ResultStatus,
  Provenance
 }

 EXTENSIBLE := {
  ProofCalculi,
  SATSolvers,
  SMTSolvers,
  ModelFinders,
  OntologyReasoners,
  ConstraintSolvers,
  SearchStrategies,
  IndexingMethods,
  ApplicationDomains,
  RelatedOntologies
 }

 ON_NEW_KNOWLEDGE {
  IDENTIFY new_axiom_rule_or_procedure
  VALIDATE semantics
  UPDATE indexes
  CHECK consistency
  RECOMPUTE affected_results
  UPDATE provenance
  UPDATE confidence
 }
}

AI_CONSUMPTION {
 MACHINE_READABLE := TRUE
 HUMAN_INTERPRETABLE := TRUE
 RECURSIVE_REASONING := TRUE
 FORMAL_PROOF_SEARCH := TRUE
 MODEL_SEARCH := TRUE
 COUNTERMODEL_SEARCH := TRUE
 RESOLUTION_REASONING := TRUE
 SAT_REASONING := TRUE
 SMT_REASONING := TRUE
 ONTOLOGY_REASONING := TRUE
 CONSTRAINT_REASONING := TRUE
 RULE_REASONING := TRUE
 PROOF_VERIFICATION := TRUE
 MODEL_VERIFICATION := TRUE
 PROVENANCE_TRACKING := TRUE
 JUSTIFICATION_GENERATION := TRUE
 VALIDATION_REQUIRED := TRUE
}

FLOW_HASH {
 TARGET := TARGET_URL
 SUBJECT := "Automated Reasoning Ontology"
 VERSION := "1.0"
 CANONICAL_SIGNATURE := HASH(TARGET + SUBJECT + DOMAIN + VERSION)
}

OUTPUT {
 PRIMARY_ENTITY := AutomatedReasoning
 INTERPRETATION := "Automated reasoning applies formal calculi and algorithms to machine-represented knowledge in order to construct proofs, find models or countermodels, decide satisfiability, derive ontology and rule consequences, and solve constraints. Reliable automated reasoning preserves the distinction between derivability and entailment, verifies proof or model certificates, records provenance, and reports unknown or resource-limited outcomes without converting search failure into a logical conclusion."
}

END_FLOW