Logical Proof Ontology

FLOW ALGEBRA
TITLE: Logical Proof Ontology
DOMAIN: Discrete Mathematics > Logic > Logical Proof
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/logic/logical-proof-ontology.html
VERSION: 1.0
LANGUAGE: en-GB
AUTHORS: Mark Higgins — Sky (Recursive AI)
SITE: https://kirethresearch.org
STATUS: Formal mathematical model; live source page not independently verified.

1. PURPOSE
Represent logical proofs as typed, checkable derivations from assumptions and axioms through sound inference rules to conclusions. Distinguish syntactic derivability from semantic entailment.

2. TYPED ENTITIES
LogicSystem: {name, syntax, semantics, rules}
Formula: well_formed_expression
Proposition: Formula with no free variables
Term: syntactically valid term
Variable: bound_or_free_symbol
Assumption: Formula
Axiom: Formula or axiom schema instance
InferenceRule: {name, premises: Formula[], conclusion: Formula, side_conditions}
ProofStep: {index: Nat, formula: Formula, rule: InferenceRule|Assumption|Axiom, dependencies: Nat[]}
Proof: {logic: LogicSystem, assumptions: Set[Formula], steps: List[ProofStep], conclusion: Formula}
Model: {domain, interpretation, valuation}
Countermodel: Model satisfying premises but falsifying conclusion
Theorem: Formula derivable with no undischarged assumptions

3. CORE RELATIONS
WELL_FORMED(formula, logic)
ASSUMES(proof, formula)
INSTANCE_OF(step, rule)
DEPENDS_ON(step_i, step_j)
DERIVES(gamma, phi) := gamma |- phi
ENTAILS(gamma, phi) := gamma |= phi
SATISFIES(model, phi)
DISCHARGES(step, assumption)
PROVES(proof, phi)
COUNTEREXAMPLE_TO(model, gamma, phi)

4. FORMAL OPERATIONS
INTRODUCE_ASSUMPTION(phi) -> proof context gamma U {phi}
APPLY_RULE(rule, premises) -> conclusion, only if side conditions hold
DISCHARGE_ASSUMPTION(phi, subproof) -> conditional conclusion when licensed by the proof calculus
VERIFY_STEP(step, prior_steps, context) -> Boolean
VERIFY_PROOF(proof) -> Boolean
FIND_COUNTERMODEL(gamma, phi) -> Model? (if available)
NORMALISE_PROOF(proof) -> equivalent derivation, where the calculus supports normalisation

5. FUNDAMENTAL INFERENCE SCHEMATA (CLASSICAL LOGIC)
Modus ponens: {P, P -> Q} |- Q
Conjunction introduction: {P, Q} |- P AND Q
Conjunction elimination: {P AND Q} |- P; {P AND Q} |- Q
Disjunction introduction: {P} |- P OR Q
Implication introduction: if gamma, P |- Q then gamma |- P -> Q (discharge P)
Negation introduction: if gamma, P |- contradiction then gamma |- NOT P (discharge P)
Universal elimination: forall x P(x) |- P(t), with t free for x in P
Existential introduction: P(t) |- exists x P(x), with valid substitution
Universal introduction: gamma |- P(x) implies gamma |- forall x P(x), provided x is not free in any undischarged assumption in gamma
Existential elimination: from exists x P(x) and a subproof from P(c) to Q infer Q, provided c is fresh and does not occur free in Q or relevant undischarged assumptions
NOTE: Exact rules depend on the chosen logic and proof calculus.

6. PROOF VALIDITY
VALID_PROOF(p) iff:
  each step is well formed;
  each cited dependency precedes the dependent step;
  each rule application matches premises and side conditions;
  all assumption discharges are correctly scoped;
  final step equals the stated conclusion;
  remaining open assumptions are included in the proof context.

7. SEMANTIC GUARANTEES
SOUNDNESS: If gamma |- phi then gamma |= phi, for a sound calculus.
COMPLETENESS: If gamma |= phi then gamma |- phi, only for a complete calculus relative to its semantics.
CONSISTENCY(gamma): gamma does not derive contradiction in the chosen calculus.
INVALID_ARGUMENT: A model satisfying all premises and falsifying the conclusion refutes semantic entailment.
IMPORTANT: Absence of a discovered proof is not evidence of invalidity.

8. ALGEBRAIC AND STRUCTURAL LAWS
Reflexivity: gamma, P |- P
Weakening: gamma |- P implies gamma U delta |- P in monotonic logics
Cut: if gamma |- P and delta, P |- Q then gamma U delta |- Q where cut is admissible
Substitution: admissible substitutions preserve derivations when variable-capture and rule restrictions are respected
Proof composition: a proved lemma may replace an appropriately matched premise, subject to context and rule conditions

9. SEMANTIC RELATIONSHIPS
LogicalProof IS_A FormalDerivation
LogicalProof USES InferenceRule
LogicalProof CONTAINS ProofStep
ProofStep DEPENDS_ON ProofStep
Theorem IS_DERIVED_FROM AxiomOrPriorTheorem
Countermodel REFUTES SemanticEntailment
Soundness CONNECTS SyntacticDerivability TO SemanticEntailment
Completeness CONNECTS SemanticEntailment TO SyntacticDerivability

10. SEMANTIC_EQUIVALENCE
Two proofs are conclusion-equivalent relative to gamma if they derive the same conclusion from the same permitted assumptions; this does not imply identical proof structure.
Two formulae P and Q are logically equivalent if P |= Q and Q |= P in the selected semantics.
Do not conflate equivalent conclusions, equivalent proofs, and identical derivation traces.

11. EXAMPLE DERIVATION
Premises: P -> Q; P
1. P -> Q [premise]
2. P [premise]
3. Q [modus ponens, 1, 2]
Conclusion: {P -> Q, P} |- Q

12. VALIDATION AND ERROR STATES
Reject: malformed formula, unavailable dependency, circular step dependency, wrong rule arity, unlicensed substitution, variable capture, illegal assumption discharge, conclusion mismatch.
Report: {valid: Boolean, failing_step: Nat?, reason: String?, open_assumptions: Set[Formula]}

13. CONFIDENCE
Mathematically checked derivation: confidence=1.0 relative to explicitly specified formal system and trusted checker.
Unverified generated proof: confidence=unverified; never treat a language-model assertion as formal verification.
Semantic certainty depends on the soundness of the formal system and correct modelling of the intended problem.

14. FLOW_HASH
Canonicalise: logic identifier, symbol table, assumptions, numbered steps, inference rules, side conditions and conclusion.
FLOW_HASH := SHA256(UTF8(canonical_representation))
Hash verifies content identity only; it does not establish logical validity.

15. UPDATE_MODEL
On changes to syntax, inference rules, assumptions or steps:
  increment version;
  recompute dependent proof steps;
  rerun proof validation;
  invalidate stale verification results;
  regenerate FLOW_HASH;
  retain provenance and audit trail.

16. AI_CONSUMPTION
Input: formal language, assumptions, proposed conclusion, optional derivation.
Output: typed proof graph, machine-checkable proof steps, validation status, countermodel when supported, provenance, confidence and hash.
AI may propose candidate derivations but must not label them verified without a sound checker.

END FLOW ALGEBRA