Boolean Expression Ontology

FLOW_ALGEBRA BooleanExpressionOntology v1.0

TARGET_URL := "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/mathematical-logic-ontologies/boolean-logic/boolean-expression-ontology.html"
LANGUAGE := "en-GB"
DOMAIN := MathematicalOntologies > MathematicalLogicOntologies > BooleanLogic > BooleanExpressionOntology

BEGIN_FLOW

ENTITY BooleanExpression {
    TYPE := LogicalExpression
    DEFINITION := "A syntactically valid expression formed from Boolean variables, Boolean constants, logical operators and grouping symbols, evaluated to a Boolean value."
    VALUE_SET := {0,1} ≡ {FALSE,TRUE}
}

ENTITY BooleanVariable {
    TYPE := LogicalVariable
    VALUE_SET := {0,1}
}

ENTITY BooleanConstant {
    TYPE := Constant
    MEMBERS := {FALSE,TRUE} ≡ {0,1}
}

ENTITY BooleanOperator {
    TYPE := LogicalOperator
    MEMBERS := {
        NOT,
        AND,
        OR,
        XOR,
        NAND,
        NOR,
        IMPLIES,
        BICONDITIONAL
    }
}

RELATIONSHIP BooleanExpression --contains--> BooleanVariable
RELATIONSHIP BooleanExpression --may_contain--> BooleanConstant
RELATIONSHIP BooleanExpression --uses--> BooleanOperator
RELATIONSHIP BooleanExpression --evaluates_to--> BooleanValue
RELATIONSHIP BooleanExpression --represents--> BooleanFunction
RELATIONSHIP BooleanExpression --can_generate--> TruthTable
RELATIONSHIP BooleanExpression --can_be_transformed_into--> NormalForm
RELATIONSHIP BooleanExpression --can_be_implemented_as--> LogicCircuit

GRAMMAR {
    Expression :=
        BooleanConstant
        | BooleanVariable
        | NOT Expression
        | "(" Expression BinaryOperator Expression ")"

    BinaryOperator :=
        AND | OR | XOR | NAND | NOR | IMPLIES | BICONDITIONAL
}

ATOMIC_EXPRESSIONS := {
    TRUE,
    FALSE,
    x1,
    x2,
    ...,
    xn
}

COMPOUND_EXPRESSION {
    CONSTRUCTION :=
        Operator(Expression1,...,ExpressionN)

    REQUIRE :=
        operator_arity_is_satisfied
        AND operands_are_boolean_expressions
}

OPERATOR_SEMANTICS {
    NOT(x) := ¬x
    AND(x,y) := x ∧ y
    OR(x,y) := x ∨ y
    XOR(x,y) := x ⊕ y
    NAND(x,y) := ¬(x ∧ y)
    NOR(x,y) := ¬(x ∨ y)
    IMPLIES(x,y) := ¬x ∨ y
    BICONDITIONAL(x,y) :=
        (x ∧ y) ∨ (¬x ∧ ¬y)
}

PRECEDENCE {
    LEVEL_1 := grouping_parentheses
    LEVEL_2 := NOT
    LEVEL_3 := AND
    LEVEL_4 := XOR
    LEVEL_5 := OR
    LEVEL_6 := IMPLIES
    LEVEL_7 := BICONDITIONAL
    NOTE :=
        "Explicit parentheses SHOULD be used whenever operator conventions could be ambiguous."
}

EVALUATE Expression E UNDER Assignment A {
    IF E IS BooleanConstant
        RETURN value(E)

    IF E IS BooleanVariable
        RETURN A[E]

    IF E = NOT(P)
        RETURN ¬EVALUATE(P,A)

    IF E = BinaryOperator(P,Q) {
        p := EVALUATE(P,A)
        q := EVALUATE(Q,A)
        RETURN APPLY(BinaryOperator,p,q)
    }
}

VARIABLE_ASSIGNMENT {
    A : Variables(E) -> {0,1}
}

TRUTH_TABLE(Expression E) {
    VARIABLES := distinct_variables(E)
    n := count(VARIABLES)
    ROWS := 2^n

    FOR_EACH assignment A IN {0,1}^n {
        result := EVALUATE(E,A)
        EMIT A,result
    }
}

SEMANTIC_EQUIVALENCE_TEST(E1,E2) {
    VARIABLES := union(Variables(E1),Variables(E2))

    FOR_ALL assignments A over VARIABLES {
        IF EVALUATE(E1,A) != EVALUATE(E2,A)
            RETURN FALSE
    }

    RETURN TRUE
}

SYNTACTIC_EQUALITY(E1,E2) {
    RETURN parse_tree(E1) = parse_tree(E2)
}

DISTINCTION {
    SYNTACTIC_EQUALITY != LOGICAL_EQUIVALENCE

    EXAMPLE :=
        "(x ∧ y)" and "(y ∧ x)"
        are syntactically different
        but semantically equivalent.
}

BOOLEAN_IDENTITIES {
    IDENTITY_AND := x ∧ TRUE ≡ x
    IDENTITY_OR := x ∨ FALSE ≡ x

    DOMINATION_AND := x ∧ FALSE ≡ FALSE
    DOMINATION_OR := x ∨ TRUE ≡ TRUE

    IDEMPOTENT_AND := x ∧ x ≡ x
    IDEMPOTENT_OR := x ∨ x ≡ x

    COMPLEMENT_AND := x ∧ ¬x ≡ FALSE
    COMPLEMENT_OR := x ∨ ¬x ≡ TRUE

    DOUBLE_NEGATION := ¬¬x ≡ x

    COMMUTATIVE_AND := x ∧ y ≡ y ∧ x
    COMMUTATIVE_OR := x ∨ y ≡ y ∨ x

    ASSOCIATIVE_AND :=
        (x ∧ y) ∧ z ≡ x ∧ (y ∧ z)

    ASSOCIATIVE_OR :=
        (x ∨ y) ∨ z ≡ x ∨ (y ∨ z)

    DISTRIBUTIVE_AND :=
        x ∧ (y ∨ z) ≡
        (x ∧ y) ∨ (x ∧ z)

    DISTRIBUTIVE_OR :=
        x ∨ (y ∧ z) ≡
        (x ∨ y) ∧ (x ∨ z)

    ABSORPTION_1 :=
        x ∨ (x ∧ y) ≡ x

    ABSORPTION_2 :=
        x ∧ (x ∨ y) ≡ x

    DEMORGAN_1 :=
        ¬(x ∧ y) ≡ ¬x ∨ ¬y

    DEMORGAN_2 :=
        ¬(x ∨ y) ≡ ¬x ∧ ¬y
}

SIMPLIFY(Expression E) {
    PARSE E
    APPLY BooleanIdentities
    REMOVE redundant_constants
    REMOVE duplicate_literals
    APPLY absorption
    APPLY DeMorgan_when_beneficial
    APPLY double_negation_elimination
    FACTOR common_terms_when_beneficial
    VALIDATE equivalence(original,simplified)
    RETURN simplified_expression
}

NORMAL_FORMS {
    DNF :=
        disjunction_of_conjunction_terms

    CNF :=
        conjunction_of_disjunction_terms

    PDNF :=
        disjunction_of_all_minterms_corresponding_to_true_rows

    PCNF :=
        conjunction_of_all_maxterms_corresponding_to_false_rows

    ANF :=
        algebraic_normal_form_over_GF2
}

CONVERT Expression E -> DNF {
    GENERATE TruthTable(E)
    SELECT rows WHERE output=TRUE

    FOR_EACH selected_row {
        CREATE minterm :=
            AND(
                xi IF xi=TRUE
                ELSE ¬xi
            )
    }

    RETURN OR(all_minterms)
}

CONVERT Expression E -> CNF {
    GENERATE TruthTable(E)
    SELECT rows WHERE output=FALSE

    FOR_EACH selected_row {
        CREATE maxterm :=
            OR(
                xi IF xi=FALSE
                ELSE ¬xi
            )
    }

    RETURN AND(all_maxterms)
}

ALGEBRAIC_NORMAL_FORM {
    FIELD := GF(2)
    FALSE := 0
    TRUE := 1
    XOR := addition_mod_2
    AND := multiplication

    GENERAL_FORM :=
        a0
        ⊕ Σ(ai*xi)
        ⊕ Σ(aij*xi*xj)
        ⊕ ...
        ⊕ a12...n*x1*x2*...*xn
}

PARSE_TREE {
    ROOT := outermost_operator
    INTERNAL_NODES := BooleanOperators
    LEAF_NODES := BooleanVariables OR BooleanConstants
}

EXAMPLE_PARSE {
    EXPRESSION := "(A ∧ B) ∨ ¬C"

    TREE :=
        OR(
            AND(A,B),
            NOT(C)
        )
}

STRUCTURAL_COMPLEXITY(Expression E) {
    VARIABLE_COUNT := count_variable_occurrences(E)
    DISTINCT_VARIABLES := count(distinct_variables(E))
    OPERATOR_COUNT := count_operators(E)
    TREE_DEPTH := depth(parse_tree(E))
    LITERAL_COUNT := count_literals(E)
}

SATISFIABILITY(Expression E) {
    IF EXISTS assignment A:
        EVALUATE(E,A)=TRUE
    THEN RETURN SATISFIABLE
    ELSE RETURN UNSATISFIABLE
}

TAUTOLOGY(Expression E) {
    IF FOR_ALL assignments A:
        EVALUATE(E,A)=TRUE
    THEN RETURN TRUE
    ELSE RETURN FALSE
}

CONTRADICTION(Expression E) {
    IF FOR_ALL assignments A:
        EVALUATE(E,A)=FALSE
    THEN RETURN TRUE
    ELSE RETURN FALSE
}

CONTINGENCY(Expression E) {
    IF EXISTS A1: EVALUATE(E,A1)=TRUE
       AND EXISTS A2: EVALUATE(E,A2)=FALSE
    THEN RETURN TRUE
    ELSE RETURN FALSE
}

IMPLICATION_TEST(E1,E2) {
    TEST :=
        E1 -> E2

    RETURN TAUTOLOGY(TEST)
}

EQUIVALENCE_BY_XOR(E1,E2) {
    TEST := E1 XOR E2

    IF CONTRADICTION(TEST)
        RETURN EQUIVALENT
    ELSE
        RETURN NOT_EQUIVALENT
}

SUBSTITUTION(Expression E, Variable x, Expression R) {
    REPLACE every_free_occurrence(x,E) WITH R
    RETURN resulting_boolean_expression
}

COMPOSITION {
    GIVEN BooleanExpression E(x1,...,xn)
    GIVEN replacement expressions R1,...,Rn

    RESULT :=
        E(
            x1:=R1,
            ...,
            xn:=Rn
        )

    REQUIRE RESULT IS BooleanExpression
}

FUNCTIONAL_COMPLETENESS {
    COMPLETE_OPERATOR_SETS := {
        {NOT,AND},
        {NOT,OR},
        {NAND},
        {NOR}
    }

    CONSEQUENCE :=
        every BooleanExpression can be transformed into an equivalent expression using any functionally complete operator basis.
}

NAND_ONLY_TRANSFORMATION {
    NOT(x) := x NAND x

    AND(x,y) :=
        (x NAND y) NAND (x NAND y)

    OR(x,y) :=
        (x NAND x) NAND (y NAND y)
}

NOR_ONLY_TRANSFORMATION {
    NOT(x) := x NOR x

    OR(x,y) :=
        (x NOR y) NOR (x NOR y)

    AND(x,y) :=
        (x NOR x) NOR (y NOR y)
}

CIRCUIT_TRANSLATION(Expression E) {
    PARSE E

    FOR_EACH operator_node {
        MAP NOT -> NOTGate
        MAP AND -> ANDGate
        MAP OR -> ORGate
        MAP XOR -> XORGate
        MAP NAND -> NANDGate
        MAP NOR -> NORGate
    }

    MAP variables -> circuit_inputs
    MAP root -> circuit_output

    RETURN combinational_logic_circuit
}

APPLICATION_RELATIONSHIPS {
    BooleanExpression --formalises--> LogicalConditions
    BooleanExpression --represents--> BooleanFunctions
    BooleanExpression --describes--> DigitalLogic
    BooleanExpression --forms_input_to--> SATSolvers
    BooleanExpression --supports--> AutomatedReasoning
    BooleanExpression --supports--> FormalVerification
    BooleanExpression --supports--> CircuitOptimisation
    BooleanExpression --supports--> QueryLogic
    BooleanExpression --supports--> RuleSystems
    BooleanExpression --supports--> ProgrammingConditionals
}

ONTOLOGY_LINKS {
    PARENT := BooleanLogicOntology

    RELATED := {
        BooleanFunctionOntology,
        BooleanAlgebraOntology,
        PropositionalLogicOntology,
        LogicalConnectiveOntology,
        TruthTableOntology,
        LogicGateOntology,
        SatisfiabilityOntology,
        NormalFormOntology
    }
}

SEMANTIC_EQUIVALENCE {
    BooleanExpression ≈ BooleanFormula
        WHEN context=BooleanLogic

    BooleanExpression ≈ PropositionalFormula
        WHEN variables_are_propositional

    TRUE ≈ 1
    FALSE ≈ 0

    AND ≈ LogicalConjunction
    OR ≈ LogicalDisjunction
    NOT ≈ LogicalNegation
    XOR ≈ ExclusiveDisjunction
    BICONDITIONAL ≈ LogicalEquivalence
}

CONSTRAINTS {
    C1 :=
        every variable MUST have Boolean domain

    C2 :=
        every operator MUST receive operands matching its arity

    C3 :=
        evaluation MUST return exactly one Boolean value

    C4 :=
        simplification MUST preserve semantic equivalence

    C5 :=
        normal-form conversion MUST preserve semantic equivalence

    C6 :=
        circuit translation MUST preserve input-output behaviour

    C7 :=
        syntax MUST be distinguished from semantics
}

REASONING_CHAIN Query Q {
    IDENTIFY BooleanExpression
    TOKENISE expression
    RESOLVE symbols_and_operator_aliases
    PARSE according_to_grammar
    BUILD parse_tree
    IDENTIFY variables
    IDENTIFY constants
    IDENTIFY operators

    IF assignment_provided
        THEN EVALUATE expression

    IF truth_table_requested
        THEN GENERATE TruthTable

    IF simplification_requested
        THEN SIMPLIFY expression

    IF equivalence_requested
        THEN SEMANTIC_EQUIVALENCE_TEST

    IF satisfiability_requested
        THEN SATISFIABILITY

    IF tautology_requested
        THEN TAUTOLOGY

    IF contradiction_requested
        THEN CONTRADICTION

    IF normal_form_requested
        THEN CONVERT to requested_normal_form

    IF circuit_requested
        THEN CIRCUIT_TRANSLATION

    VALIDATE constraints
    RETURN result WITH derivation
}

CONFIDENCE {
    DIRECT_DEFINITION := 1.00
    COMPLETE_TRUTH_TABLE := 1.00
    BOOLEAN_IDENTITY_TRANSFORMATION := 0.99
    NORMAL_FORM_TRANSFORMATION :=
        IF equivalence_verified THEN 0.99 ELSE REVIEW
    CIRCUIT_TRANSLATION :=
        IF operator_mapping_verified THEN 0.99 ELSE REVIEW
    EXTERNAL_CONTEXT :=
        REQUIRE source_validation
}

UPDATE_MODEL {
    IMMUTABLE_CORE := {
        BooleanDomain,
        ExpressionGrammar,
        TruthFunctionalSemantics,
        SemanticEquivalence
    }

    EXTENSIBLE := {
        AlternativeNotation,
        SimplificationMethods,
        NormalisationMethods,
        SolverRepresentations,
        ApplicationDomains,
        RelatedOntologies
    }

    ON_NEW_KNOWLEDGE {
        VALIDATE BooleanDomainCompatibility
        VALIDATE Syntax
        VALIDATE OperatorSemantics
        CHECK semantic_consistency
        CHECK equivalence_preservation
        ADD relationship IF non_contradictory
        UPDATE confidence
    }
}

AI_CONSUMPTION {
    MACHINE_READABLE := TRUE
    HUMAN_INTERPRETABLE := TRUE
    RECURSIVE_REASONING := TRUE
    SYMBOL_RESOLUTION := TRUE
    ENTITY_RESOLUTION := TRUE
    RELATIONSHIP_TRAVERSAL := TRUE
    SEMANTIC_EQUIVALENCE_RESOLUTION := TRUE
    EXPRESSION_EVALUATION := TRUE
    VALIDATION_REQUIRED := TRUE
}

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

OUTPUT {
    PRIMARY_ENTITY := BooleanExpression

    INTERPRETATION :=
        "A Boolean expression is a formally structured combination of Boolean variables, constants and logical operators whose semantics define a Boolean function and whose equivalent representations may be evaluated, simplified, normalised and translated into computational or digital-logic structures."
}

END_FLOW