Truth Table Ontology

FLOW ALGEBRA
TITLE: Truth Table Ontology
DOMAIN: Discrete Mathematics / Logic
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/logic/truth-table-ontology-2.html
VERSION: 1.0
LANGUAGE: en-GB
AUTHORS: Mark Higgins — Sky (Recursive AI)
SITE: https://kirethresearch.org

1. PURPOSE
Model truth tables as finite, exhaustive evaluations of propositional formulae under Boolean valuations. Provide machine-readable semantics, inference, equivalence checking, and validation.

2. TYPED ENTITIES
Proposition := atomic Boolean variable.
Formula := Proposition | NOT Formula | (Formula AND Formula) | (Formula OR Formula) | (Formula IMPLIES Formula) | (Formula IFF Formula).
Valuation := mapping from propositions to {FALSE, TRUE}.
TruthRow := (valuation: Valuation, outputs: mapping Formula -> Boolean).
TruthTable := (variables: ordered list of distinct Proposition, formulae: list of Formula, rows: list of TruthRow).
Connective := NOT | AND | OR | IMPLIES | IFF | XOR.
Classification := TAUTOLOGY | CONTRADICTION | CONTINGENCY.

3. FORMAL SEMANTICS
Let v be a Boolean valuation and [[F]]_v the evaluation of formula F.
[[p]]_v = v(p).
[[NOT A]]_v = NOT [[A]]_v.
[[A AND B]]_v = [[A]]_v AND [[B]]_v.
[[A OR B]]_v = [[A]]_v OR [[B]]_v.
[[A IMPLIES B]]_v = (NOT [[A]]_v) OR [[B]]_v.
[[A IFF B]]_v = ([[A]]_v = [[B]]_v).
[[A XOR B]]_v = ([[A]]_v != [[B]]_v).

4. TRUTH TABLE GENERATION
INPUT: formulae F1..Fm.
V := sorted unique propositions occurring in formulae.
n := |V|.
GENERATE all 2^n Boolean valuations, exactly once, in deterministic lexicographic order (FALSE before TRUE).
FOR EACH valuation v:
  COMPUTE [[Fi]]_v recursively for every formula Fi.
  EMIT TruthRow(v, outputs).
OUTPUT: TruthTable(V, formulae, rows).
NOTE: For n=0, there is one empty valuation, not zero rows.

5. BINARY CONNECTIVE TABLE
A B | NOT A | A AND B | A OR B | A -> B | A <-> B | A XOR B
F F |   T   |    F    |   F    |    T   |     T    |    F
F T |   T   |    F    |   T    |    T   |     F    |    T
T F |   F   |    F    |   T    |    F   |     F    |    T
T T |   F   |    T    |   T    |    T   |     T    |    F

6. CLASSIFICATION
TAUTOLOGY(F) iff for all valuations v, [[F]]_v = TRUE.
CONTRADICTION(F) iff for all valuations v, [[F]]_v = FALSE.
CONTINGENCY(F) iff some v satisfies F and some v falsifies F.
SATISFIABLE(F) iff there exists v such that [[F]]_v = TRUE.
UNSATISFIABLE(F) iff CONTRADICTION(F).

7. SEMANTIC_EQUIVALENCE
EQUIVALENT(A,B) iff for all v over variables(A) union variables(B), [[A]]_v = [[B]]_v.
EQUIVALENT(A,B) iff TAUTOLOGY(A IFF B).
ENTAILS(Gamma,F) iff no valuation satisfies every member of Gamma while falsifying F.
ENTAILS(Gamma,F) iff UNSATISFIABLE((AND Gamma) AND NOT F).

8. ALGEBRAIC LAWS
NOT NOT A == A.
A AND TRUE == A; A OR FALSE == A.
A AND FALSE == FALSE; A OR TRUE == TRUE.
A AND A == A; A OR A == A.
A AND NOT A == FALSE; A OR NOT A == TRUE.
NOT(A AND B) == (NOT A OR NOT B).
NOT(A OR B) == (NOT A AND NOT B).
A -> B == (NOT A OR B).
A <-> B == ((A -> B) AND (B -> A)).
A AND (B OR C) == (A AND B) OR (A AND C).
A OR (B AND C) == (A OR B) AND (A OR C).

9. INFERENCE RULES
MODUS_PONENS: A, (A -> B) entails B.
MODUS_TOLLENS: (A -> B), NOT B entails NOT A.
HYPOTHETICAL_SYLLOGISM: (A -> B), (B -> C) entails (A -> C).
DISJUNCTIVE_SYLLOGISM: (A OR B), NOT A entails B.
CHECK_INFERENCE(premises, conclusion): return VALID iff no counterexample valuation exists.
COUNTEREXAMPLE: a valuation satisfying all premises and falsifying conclusion.

10. RELATIONSHIPS
TruthTable EVALUATES Formula.
TruthTable ENUMERATES Valuation.
TruthRow ASSIGNS Proposition -> Boolean.
Formula CONTAINS Proposition.
Connective COMPOSES Formula.
SemanticEquivalence COMPARES Formula with Formula.
LogicalEntailment LINKS PremiseSet to Conclusion.
Counterexample REFUTES ProposedEntailment.

11. VALIDATION
ASSERT each proposition has exactly one Boolean value per row.
ASSERT row_count == 2^number_of_distinct_variables.
ASSERT valuations are unique and exhaustive.
ASSERT every formula output agrees with recursive semantics.
ASSERT variable order and row order are deterministic.
ASSERT implication is false only when antecedent is TRUE and consequent FALSE.
ASSERT equivalence checks use the union of formula variables.
ASSERT a counterexample is supplied for any rejected entailment when feasible.

12. COMPUTATIONAL CONSIDERATIONS
Explicit truth tables require O(2^n) rows for n distinct variables.
Formula evaluation cost per row depends on formula size; naive total cost O(2^n * total_formula_size).
For large n, use SAT/SMT, BDDs or symbolic reasoning where appropriate rather than materialising every row.
Three-valued, fuzzy and probabilistic logics require separate truth domains and must not be silently treated as classical Boolean tables.

13. CONFIDENCE
FORMAL_DEFINITIONS: 1.00 (within classical two-valued propositional logic).
DERIVED_RESULT: 1.00 when exhaustive enumeration and validation succeed.
EXTERNAL_CLAIM: requires separate evidence and provenance.
CONFIDENCE describes correctness under declared assumptions, not empirical certainty.

14. FLOW_HASH
HASH_INPUT := canonical_utf8(version, title, source_url, typed_entities, semantics, laws, inference_rules, validation).
FLOW_HASH := SHA256(HASH_INPUT).
IMPLEMENTATION: calculate hash after canonical serialization; no hash is asserted here.

15. UPDATE_MODEL
On edit: increment version, preserve provenance, rerun truth-table test suite, regenerate FLOW_HASH, and record change history.
Breaking changes to connective semantics require a major version change.

16. AI_CONSUMPTION
READ typed entities and semantic rules before inference.
DISTINGUISH syntactic equality from semantic equivalence.
RETURN explicit valuation-based counterexamples for invalid claims.
STATE assumptions: classical, two-valued, finite propositional variable set.
DO NOT infer empirical truth from propositional validity.

END FLOW ALGEBRA