XOR Gate Ontology

FLOW_ALGEBRA XORGateOntology v1.0

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

BEGIN_FLOW

ENTITY XORGate {
    TYPE := LogicGate
    LOGICAL_ROLE := ExclusiveDisjunction
    MIN_ARITY := 2
    INPUT_DOMAIN := {0,1} ≡ {FALSE,TRUE}
    OUTPUT_DOMAIN := {0,1} ≡ {FALSE,TRUE}
    DEFINITION := "A logic gate implementing exclusive disjunction. For two inputs its output is true exactly when the inputs differ; for an n-input parity interpretation its output is true when an odd number of inputs are true."
}

RELATIONSHIP XORGate --is_a--> LogicGate
RELATIONSHIP XORGate --implements--> ExclusiveDisjunction
RELATIONSHIP XORGate --implements--> BooleanFunction
RELATIONSHIP XORGate --corresponds_to--> XOROperator
RELATIONSHIP XORGate --can_be_represented_by--> BooleanExpression
RELATIONSHIP XORGate --can_be_specified_by--> TruthTable
RELATIONSHIP XORGate --can_be_composed_into--> LogicCircuit
RELATIONSHIP XORGate --computes--> Parity

ENTITY XOROperator {
    TYPE := BooleanOperator
    SYMBOLS := {"XOR","⊕"}
}

BOOLEAN_FUNCTION {
    BINARY :=
        XOR(x,y) := x ⊕ y

    BINARY_EQUIVALENCE :=
        (x ∧ ¬y) ∨ (¬x ∧ y)

    NARY_PARITY :=
        XOR(x1,...,xn) :=
            x1 ⊕ x2 ⊕ ... ⊕ xn

    NARY_CONDITION :=
        OUTPUT=1 IFF count_true_inputs IS ODD
}

BINARY_TRUTH_TABLE {
    (A=0,B=0) -> Y=0
    (A=0,B=1) -> Y=1
    (A=1,B=0) -> Y=1
    (A=1,B=1) -> Y=0
}

EVALUATE_XOR(InputVector X) {
    REQUIRE length(X) >= 2
    REQUIRE FOR_ALL x IN X: x IN {0,1}

    true_count := SUM(X)

    RETURN true_count MOD 2
}

ALGEBRAIC_FORM_GF2 {
    FIELD := GF(2)
    XOR(x1,...,xn) :=
        (x1 + x2 + ... + xn) mod 2

    XOR := addition_over_GF2
}

PROPOSITIONAL_LOGIC_MAPPING {
    INPUT_A := proposition_P
    INPUT_B := proposition_Q
    OUTPUT := P ⊕ Q

    SEMANTICS :=
        P ⊕ Q IS TRUE
        IFF exactly one of P,Q is true
}

STANDARD_BOOLEAN_EXPANSION {
    A XOR B ≡
        (A ∧ ¬B) ∨
        (¬A ∧ B)
}

ALTERNATIVE_EXPANSION {
    A XOR B ≡
        (A ∨ B) ∧
        ¬(A ∧ B)
}

XNOR_RELATIONSHIP {
    XNOR(A,B) :=
        ¬(A XOR B)

    XOR(A,B) :=
        ¬XNOR(A,B)

    FOR binary_inputs:
        XOR -> inequality_test
        XNOR -> equality_test
}

BOOLEAN_IDENTITIES {
    IDENTITY :=
        A ⊕ 0 ≡ A

    COMPLEMENT_WITH_ONE :=
        A ⊕ 1 ≡ ¬A

    SELF_CANCELLATION :=
        A ⊕ A ≡ 0

    COMPLEMENT_PAIR :=
        A ⊕ ¬A ≡ 1

    COMMUTATIVITY :=
        A ⊕ B ≡ B ⊕ A

    ASSOCIATIVITY :=
        (A ⊕ B) ⊕ C ≡
        A ⊕ (B ⊕ C)

    DOUBLE_OCCURRENCE_CANCELLATION :=
        A ⊕ A ⊕ B ≡ B
}

PARITY_PROPERTIES {
    EVEN_NUMBER_OF_TRUE_INPUTS -> OUTPUT=0
    ODD_NUMBER_OF_TRUE_INPUTS -> OUTPUT=1
}

TRUTH_TABLE_GENERATION(Arity n) {
    REQUIRE n >= 2

    FOR_EACH X IN {0,1}^n {
        Y := EVALUATE_XOR(X)
        EMIT ROW(X,Y)
    }

    IF n >= 1:
        TRUE_ROWS := 2^(n-1)
        FALSE_ROWS := 2^(n-1)
}

LOGICAL_PROPERTIES {
    COMMUTATIVE := TRUE
    ASSOCIATIVE := TRUE
    IDEMPOTENT := FALSE
    MONOTONE := FALSE
    ZERO_PRESERVING := TRUE
    ONE_PRESERVING :=
        IF arity_is_odd THEN TRUE
        ELSE FALSE
    AFFINE_OVER_GF2 := TRUE
}

CIRCUIT_SYMBOL_SEMANTICS {
    INPUT_PORTS := {A,B,...}
    OUTPUT_PORT := Y

    BINARY_EQUATION :=
        Y = A ⊕ B
}

EXPRESSION_TRANSLATION {
    BooleanExpression:
        A ⊕ B

    MAP_TO:
        XORGate(
            input1=A,
            input2=B,
            output=Y
        )
}

REVERSE_TRANSLATION {
    XORGate(A,B)->Y

    MAP_TO BooleanExpression:
        Y := A ⊕ B
}

CASCADE_XOR_GATES {
    GIVEN inputs x1,...,xn

    y1 := XOR(x1,x2)
    y2 := XOR(y1,x3)
    ...
    y_final := XOR(y_previous,xn)

    BY_ASSOCIATIVITY:
        y_final ≡ XOR(x1,...,xn)
}

COMPOSITION_EXAMPLE {
    EXPRESSION :=
        A ⊕ B ⊕ C

    NETWORK :=
        G1 := XORGate(A,B)
        G2 := XORGate(output(G1),C)

    OUTPUT :=
        A ⊕ B ⊕ C

    INTERPRETATION :=
        three-input odd parity
}

AND_OR_NOT_IMPLEMENTATION {
    NA := NOT(A)
    NB := NOT(B)

    T1 := AND(A,NB)
    T2 := AND(NA,B)

    XOR(A,B) :=
        OR(T1,T2)
}

NAND_ONLY_IMPLEMENTATION {
    T1 := NAND(A,B)
    T2 := NAND(A,T1)
    T3 := NAND(B,T1)

    XOR(A,B) :=
        NAND(T2,T3)
}

NOR_ONLY_IMPLEMENTATION {
    T1 := NOR(A,B)
    T2 := NOR(A,T1)
    T3 := NOR(B,T1)
    XNOR := NOR(T2,T3)

    XOR(A,B) :=
        NOR(XNOR,XNOR)
}

HALF_ADDER_RELATIONSHIP {
    INPUTS := {A,B}

    SUM :=
        A XOR B

    CARRY :=
        A AND B

    RELATIONSHIP XORGate --implements--> HalfAdderSum
}

FULL_ADDER_RELATIONSHIP {
    INPUTS := {A,B,Cin}

    SUM :=
        A XOR B XOR Cin

    CARRY :=
        (A AND B) OR
        (Cin AND (A XOR B))

    RELATIONSHIP XORGate --contributes_to--> FullAdderSum
}

PARITY_GENERATOR {
    INPUTS := x1,...,xn

    PARITY_BIT :=
        XOR(x1,...,xn)

    PURPOSE :=
        derive parity information from Boolean data vector
}

PARITY_CHECKER {
    INPUTS := data_bits + parity_bit

    RESULT :=
        XOR(all_inputs)

    INTERPRETATION :=
        result depends on the parity convention used
}

INEQUALITY_DETECTOR {
    INPUTS := {A,B}

    OUTPUT :=
        XOR(A,B)

    OUTPUT=1 IFF A != B
}

CONTROLLED_INVERSION {
    DATA := A
    CONTROL := C

    OUTPUT :=
        A XOR C

    IF C=0:
        OUTPUT=A

    IF C=1:
        OUTPUT=NOT(A)
}

RELATIONSHIP XORGate --can_implement--> ControlledInversion

LINEAR_ALGEBRA_GF2_RELATIONSHIP {
    XOR --corresponds_to--> VectorAdditionOverGF2

    BOOLEAN_VECTOR_ADDITION {
        X ⊕ Y :=
            componentwise_addition_mod_2
    }
}

ALGEBRAIC_NORMAL_FORM_ROLE {
    ANF :=
        XOR of Boolean monomials

    XORGate --implements--> GF2Addition
}

CRYPTOGRAPHIC_RELATIONSHIP {
    XOR --used_as--> ReversibleBitwiseCombination

    PROPERTY {
        A XOR B XOR B = A
    }

    NOTE :=
        cryptographic security depends on the complete construction and assumptions,
        not on XOR alone
}

REVERSIBILITY_IDENTITIES {
    C := A XOR B

    THEN:
        C XOR B = A
        C XOR A = B
}

EQUIVALENCE_TEST(Expression E, XORNetwork N) {
    VARIABLES := union(inputs(E),inputs(N))

    FOR_ALL assignments A {
        yE := EVALUATE(E,A)
        yN := EVALUATE_NETWORK(N,A)

        IF yE != yN
            RETURN FALSE
    }

    RETURN TRUE
}

SIMPLIFICATION_RULES {
    XOR(A,0) -> A
    XOR(A,1) -> NOT(A)
    XOR(A,A) -> 0
    XOR(A,NOT(A)) -> 1

    XOR(A,A,B) -> B

    XOR(A,B,A) -> B
        BY commutativity_and_associativity
}

APPLICATION_RELATIONSHIPS {
    XORGate --used_in--> BinaryAddition
    XORGate --used_in--> HalfAdders
    XORGate --used_in--> FullAdders
    XORGate --used_in--> ParityGeneration
    XORGate --used_in--> ParityChecking
    XORGate --used_in--> InequalityDetection
    XORGate --used_in--> ControlledInversion
    XORGate --used_in--> ErrorDetection
    XORGate --used_in--> GF2Arithmetic
    XORGate --used_in--> DigitalLogic
}

ONTOLOGY_LINKS {
    PARENT := LogicGateOntology

    ANCESTORS := {
        BooleanLogicOntology,
        MathematicalLogicOntology,
        MathematicalOntology
    }

    RELATED := {
        ANDGateOntology,
        ORGateOntology,
        NOTGateOntology,
        NANDGateOntology,
        NORGateOntology,
        XNORGateOntology,
        BooleanFunctionOntology,
        BooleanExpressionOntology,
        BooleanAlgebraOntology,
        TruthTableOntology,
        ParityOntology,
        AlgebraicNormalFormOntology
    }
}

SEMANTIC_EQUIVALENCE {
    XORGate ≈ ExclusiveORGate
    XOROperator ≈ ExclusiveDisjunction
    XOR(A,B) ≈ A ⊕ B
    XOR(A,B) ≈ (A ∧ ¬B) ∨ (¬A ∧ B)
    XOR(A,B) ≈ inequality(A,B)
        WHEN inputs_are_single_boolean_values
    XOR_n ≈ odd_parity
        WHEN nary_XOR_uses_associative_parity_semantics
    TRUE ≈ 1
    FALSE ≈ 0
}

CONSTRAINTS {
    C1 :=
        every abstract XORGate input MUST belong_to {0,1}

    C2 :=
        XORGate output MUST belong_to {0,1}

    C3 :=
        binary XOR output MUST equal 1 exactly when its two inputs differ

    C4 :=
        n-ary XOR MUST use explicitly stated parity semantics

    C5 :=
        binary XORGate MUST match the canonical four-row truth table

    C6 :=
        gate-network transformations MUST preserve complete Boolean semantics

    C7 :=
        XOR MUST NOT be confused with inclusive OR

    C8 :=
        abstract Boolean semantics MUST remain distinct from implementation-specific electronic behaviour
}

REASONING_CHAIN Query Q {
    IDENTIFY XORGate concept
    IDENTIFY requested representation
    DETERMINE arity
    RESOLVE exclusive_disjunction_aliases
    RESOLVE input_values

    IF evaluation_requested
        THEN EVALUATE_XOR

    IF truth_table_requested
        THEN TRUTH_TABLE_GENERATION

    IF expression_requested
        THEN RETURN exclusive_disjunction_expression

    IF parity_requested
        THEN count_true_inputs MOD 2

    IF AND_OR_NOT_requested
        THEN APPLY AND_OR_NOT_IMPLEMENTATION

    IF NAND_only_requested
        THEN APPLY NAND_ONLY_IMPLEMENTATION

    IF NOR_only_requested
        THEN APPLY NOR_ONLY_IMPLEMENTATION

    IF arithmetic_context
        THEN RESOLVE GF2_addition_semantics

    IF simplification_requested
        THEN APPLY SIMPLIFICATION_RULES

    IF equivalence_requested
        THEN EQUIVALENCE_TEST

    VALIDATE canonical_XOR_semantics
    VALIDATE parity_semantics
    RETURN result WITH derivation
}

CONFIDENCE {
    CANONICAL_BINARY_XOR_DEFINITION := 1.00
    BINARY_TRUTH_TABLE := 1.00
    NARY_PARITY_SEMANTICS := 1.00
    GF2_ADDITION_MAPPING := 1.00
    STANDARD_GATE_TRANSFORMATIONS := 0.99
    NETWORK_EQUIVALENCE :=
        IF exhaustive_truth_table_verified THEN 1.00
        ELSE REQUIRE validation
    PHYSICAL_IMPLEMENTATION_CLAIM :=
        REQUIRE implementation_specific_source
}

UPDATE_MODEL {
    IMMUTABLE_CORE := {
        BooleanDomain,
        ExclusiveDisjunctionTruthFunction,
        CanonicalBinaryTruthTable,
        ParitySemantics,
        GF2AdditionRelationship
    }

    EXTENSIBLE := {
        CircuitApplications,
        AlternativeImplementations,
        ParityStructures,
        ArithmeticStructures,
        OptimisationMethods,
        HardwareRealisation,
        RelatedOntologies
    }

    ON_NEW_KNOWLEDGE {
        VALIDATE against XORTruthFunction
        VALIDATE arity
        VALIDATE BooleanDomain
        CHECK parity_interpretation
        CHECK semantic_consistency
        CHECK truth_table_equivalence
        ADD relationship IF non_contradictory
        UPDATE confidence
    }
}

AI_CONSUMPTION {
    MACHINE_READABLE := TRUE
    HUMAN_INTERPRETABLE := TRUE
    RECURSIVE_REASONING := TRUE
    ENTITY_RESOLUTION := TRUE
    SYMBOL_RESOLUTION := TRUE
    RELATIONSHIP_TRAVERSAL := TRUE
    BOOLEAN_EVALUATION := TRUE
    PARITY_REASONING := TRUE
    GF2_REASONING := TRUE
    TRUTH_TABLE_REASONING := TRUE
    CIRCUIT_TRANSLATION := TRUE
    EQUIVALENCE_VALIDATION := TRUE
}

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

OUTPUT {
    PRIMARY_ENTITY := XORGate

    INTERPRETATION :=
        "An XOR gate implements exclusive disjunction. For two Boolean inputs it is true exactly when the inputs differ; under n-input parity semantics it is true when an odd number of inputs are true. XOR also corresponds to addition modulo two, linking Boolean logic with parity computation and arithmetic over GF(2)."
}

END_FLOW