Logic Gate Ontology

FLOW_ALGEBRA LogicGateOntology v1.0

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

BEGIN_FLOW

ENTITY LogicGate {
    TYPE := BooleanComputationalElement
    DEFINITION := "An abstract logical element that implements a Boolean function by mapping one or more Boolean-valued inputs to a Boolean-valued output."
    INPUT_DOMAIN := {0,1} ≡ {FALSE,TRUE}
    OUTPUT_DOMAIN := {0,1} ≡ {FALSE,TRUE}
}

ENTITY InputSignal {
    TYPE := BooleanValue
    VALUE_SET := {0,1}
}

ENTITY OutputSignal {
    TYPE := BooleanValue
    VALUE_SET := {0,1}
}

RELATIONSHIP LogicGate --implements--> BooleanFunction
RELATIONSHIP LogicGate --corresponds_to--> BooleanOperator
RELATIONSHIP LogicGate --accepts--> InputSignal
RELATIONSHIP LogicGate --produces--> OutputSignal
RELATIONSHIP LogicGate --can_be_composed_into--> LogicCircuit
RELATIONSHIP LogicGate --can_be_described_by--> BooleanExpression
RELATIONSHIP LogicGate --can_be_specified_by--> TruthTable

GATE_TYPES := {
    NOTGate,
    ANDGate,
    ORGate,
    XORGate,
    NANDGate,
    NORGate,
    XNORGate,
    BufferGate
}

ENTITY NOTGate {
    TYPE := UnaryLogicGate
    ARITY := 1
    FUNCTION := y = ¬x
    TRUTH_TABLE := {
        0 -> 1,
        1 -> 0
    }
}

ENTITY BufferGate {
    TYPE := UnaryLogicGate
    ARITY := 1
    FUNCTION := y = x
    TRUTH_TABLE := {
        0 -> 0,
        1 -> 1
    }
}

ENTITY ANDGate {
    TYPE := NaryLogicGate
    MIN_ARITY := 2
    FUNCTION := y = x1 ∧ x2 ∧ ... ∧ xn
    TWO_INPUT_TRUTH_TABLE := {
        (0,0)->0,
        (0,1)->0,
        (1,0)->0,
        (1,1)->1
    }
}

ENTITY ORGate {
    TYPE := NaryLogicGate
    MIN_ARITY := 2
    FUNCTION := y = x1 ∨ x2 ∨ ... ∨ xn
    TWO_INPUT_TRUTH_TABLE := {
        (0,0)->0,
        (0,1)->1,
        (1,0)->1,
        (1,1)->1
    }
}

ENTITY XORGate {
    TYPE := NaryLogicGate
    MIN_ARITY := 2
    FUNCTION := y = x1 ⊕ x2 ⊕ ... ⊕ xn
    INTERPRETATION := "For n inputs, output is 1 when an odd number of inputs are 1."
    TWO_INPUT_TRUTH_TABLE := {
        (0,0)->0,
        (0,1)->1,
        (1,0)->1,
        (1,1)->0
    }
}

ENTITY NANDGate {
    TYPE := NaryLogicGate
    MIN_ARITY := 2
    FUNCTION := y = ¬(x1 ∧ x2 ∧ ... ∧ xn)
    TWO_INPUT_TRUTH_TABLE := {
        (0,0)->1,
        (0,1)->1,
        (1,0)->1,
        (1,1)->0
    }
}

ENTITY NORGate {
    TYPE := NaryLogicGate
    MIN_ARITY := 2
    FUNCTION := y = ¬(x1 ∨ x2 ∨ ... ∨ xn)
    TWO_INPUT_TRUTH_TABLE := {
        (0,0)->1,
        (0,1)->0,
        (1,0)->0,
        (1,1)->0
    }
}

ENTITY XNORGate {
    TYPE := BooleanLogicGate
    FUNCTION := y = ¬(x1 ⊕ x2 ⊕ ... ⊕ xn)
    TWO_INPUT_INTERPRETATION := "Output is 1 when the two inputs are equal."
    TWO_INPUT_TRUTH_TABLE := {
        (0,0)->1,
        (0,1)->0,
        (1,0)->0,
        (1,1)->1
    }
}

BOOLEAN_OPERATOR_MAPPING {
    NOTGate -> NOT
    ANDGate -> AND
    ORGate -> OR
    XORGate -> XOR
    NANDGate -> NAND
    NORGate -> NOR
    XNORGate -> BICONDITIONAL WHEN arity=2
    BufferGate -> IDENTITY
}

EVALUATE_GATE(Gate G, Inputs X) {
    VALIDATE length(X) satisfies arity(G)
    VALIDATE FOR_ALL x IN X: x IN {0,1}
    APPLY BooleanFunction(G) TO X
    RETURN BooleanOutput
}

TRUTH_TABLE_GENERATION(Gate G) {
    n := arity(G)
    FOR_EACH input_vector X IN {0,1}^n {
        y := EVALUATE_GATE(G,X)
        EMIT ROW(X,y)
    }
}

FUNCTIONAL_COMPLETENESS {
    DEFINITION :=
        "A gate set is functionally complete when arbitrary Boolean functions can be constructed using gates from that set."

    COMPLETE_GATE_BASES := {
        {NOTGate,ANDGate},
        {NOTGate,ORGate},
        {NANDGate},
        {NORGate}
    }

    NANDGate --is--> UniversalGate
    NORGate --is--> UniversalGate
}

NAND_CONSTRUCTIONS {
    NOT(x) :=
        NAND(x,x)

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

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

NOR_CONSTRUCTIONS {
    NOT(x) :=
        NOR(x,x)

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

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

ENTITY LogicCircuit {
    TYPE := DirectedAcyclicBooleanNetwork
    COMPONENTS := LogicGate*
    INPUTS := PrimaryInput*
    OUTPUTS := PrimaryOutput*
}

RELATIONSHIP LogicCircuit --contains--> LogicGate
RELATIONSHIP LogicCircuit --implements--> BooleanFunction
RELATIONSHIP LogicCircuit --is_described_by--> BooleanExpression
RELATIONSHIP LogicCircuit --has_semantics--> TruthTable

CIRCUIT_COMPOSITION {
    GIVEN gates G1,...,Gm

    CONNECT output(Gi) -> input(Gj)
        WHERE connection_is_valid

    REQUIRE {
        BooleanSignalCompatibility,
        DefinedInputSources,
        DefinedOutputTargets
    }

    RESULT := LogicCircuit
}

EXPRESSION_TO_GATE_NETWORK(Expression E) {
    PARSE E INTO SyntaxTree

    FOR_EACH node N {
        IF N=NOT THEN CREATE NOTGate
        IF N=AND THEN CREATE ANDGate
        IF N=OR THEN CREATE ORGate
        IF N=XOR THEN CREATE XORGate
        IF N=NAND THEN CREATE NANDGate
        IF N=NOR THEN CREATE NORGate
        IF N=XNOR THEN CREATE XNORGate
    }

    CONNECT gates according_to SyntaxTreeEdges
    MAP leaves -> PrimaryInputs
    MAP root -> PrimaryOutput

    RETURN LogicCircuit
}

GATE_NETWORK_TO_EXPRESSION(Circuit C) {
    TRACE FROM PrimaryOutputs BACK_TO PrimaryInputs
    SUBSTITUTE each_gate WITH corresponding_boolean_operator
    PRESERVE connectivity_and_precedence
    RETURN BooleanExpression
}

COMBINATIONAL_SEMANTICS {
    OUTPUT_AT_TIME_t :=
        BooleanFunction(CurrentInputsAtTime_t)

    MEMORY := NONE
}

STRUCTURAL_PROPERTIES(Gate G) {
    ARITY := number_of_inputs(G)
    FAN_OUT := number_of_destinations_driven_by_output(G)
    LOGICAL_FUNCTION := BooleanFunction(G)
}

CIRCUIT_PROPERTIES(Circuit C) {
    GATE_COUNT := count(gates(C))
    INPUT_COUNT := count(primary_inputs(C))
    OUTPUT_COUNT := count(primary_outputs(C))
    LOGIC_DEPTH := maximum_gate_levels_from_input_to_output(C)
}

PROPAGATION_MODEL {
    ABSTRACT_BOOLEAN_MODEL :=
        output changes according_to BooleanFunction

    PHYSICAL_IMPLEMENTATION_NOTE :=
        real electronic gates may have propagation delay and electrical constraints,
        but these are implementation properties beyond the pure Boolean gate abstraction.
}

SIMPLIFY_GATE_NETWORK(Circuit C) {
    DERIVE BooleanExpression(C)
    SIMPLIFY expression USING BooleanAlgebra
    RECONSTRUCT equivalent_gate_network
    VERIFY equivalent_truth_table
    RETURN optimised_network
}

EQUIVALENCE_TEST(Circuit C1, Circuit C2) {
    REQUIRE compatible_primary_inputs_and_outputs

    FOR_ALL input_vectors X {
        Y1 := EVALUATE(C1,X)
        Y2 := EVALUATE(C2,X)

        IF Y1 != Y2
            RETURN FALSE
    }

    RETURN TRUE
}

COMMON_COMPOSITE_STRUCTURES := {
    HalfAdder,
    FullAdder,
    Multiplexer,
    Demultiplexer,
    Encoder,
    Decoder,
    Comparator,
    ParityGenerator,
    ParityChecker
}

ENTITY HalfAdder {
    INPUTS := {A,B}
    OUTPUTS := {SUM,CARRY}
    SUM := A XOR B
    CARRY := A AND B
}

ENTITY FullAdder {
    INPUTS := {A,B,Cin}
    OUTPUTS := {SUM,Cout}
    SUM := A XOR B XOR Cin
    Cout := (A AND B) OR (Cin AND (A XOR B))
}

ENTITY Multiplexer {
    TYPE := CombinationalLogicCircuit
    PURPOSE := "Select one input from multiple data inputs according to selector inputs."
}

ENTITY Decoder {
    TYPE := CombinationalLogicCircuit
    PURPOSE := "Map an encoded Boolean input pattern to one or more corresponding output lines."
}

ENTITY Comparator {
    TYPE := CombinationalLogicCircuit
    PURPOSE := "Compare Boolean vectors and produce relational result signals."
}

BOOLEAN_DUALITY {
    ANDGate <-> ORGate
    NANDGate <-> NORGate
    TRUE <-> FALSE
}

DEMORGAN_GATE_TRANSFORMATIONS {
    NOT(AND(x,y)) ≡ OR(NOT(x),NOT(y))
    NOT(OR(x,y)) ≡ AND(NOT(x),NOT(y))

    NAND(x,y) ≡ OR(NOT(x),NOT(y))
    NOR(x,y) ≡ AND(NOT(x),NOT(y))
}

APPLICATION_RELATIONSHIPS {
    LogicGate --underlies--> DigitalLogic
    LogicGate --constructs--> CombinationalCircuits
    LogicGate --contributes_to--> SequentialCircuits
    LogicGate --implements--> ArithmeticCircuits
    LogicGate --implements--> ControlLogic
    LogicGate --supports--> ComputerArchitecture
    LogicGate --supports--> EmbeddedSystems
    LogicGate --supports--> DigitalSignalProcessing
    LogicGate --supports--> HardwareVerification
    LogicGate --supports--> BooleanComputation
}

ONTOLOGY_LINKS {
    PARENT := BooleanLogicOntology

    RELATED := {
        BooleanFunctionOntology,
        BooleanExpressionOntology,
        BooleanAlgebraOntology,
        TruthTableOntology,
        PropositionalLogicOntology,
        DigitalLogicOntology,
        CircuitOntology,
        CombinationalLogicOntology
    }
}

SEMANTIC_EQUIVALENCE {
    LogicGate ≈ BooleanGate
    ANDGate ≈ ConjunctionGate
    ORGate ≈ DisjunctionGate
    NOTGate ≈ Inverter
    XORGate ≈ ExclusiveORGate
    XNORGate ≈ EquivalenceGate WHEN arity=2
    NANDGate ≈ NegatedANDGate
    NORGate ≈ NegatedORGate
    TRUE ≈ Logic1
    FALSE ≈ Logic0
}

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

    C2 :=
        every abstract gate output MUST belong_to {0,1}

    C3 :=
        gate evaluation MUST match its Boolean function

    C4 :=
        gate-network transformations MUST preserve Boolean semantics

    C5 :=
        universal-gate constructions MUST reproduce target truth tables

    C6 :=
        circuit equivalence MUST be assessed over all relevant input combinations

    C7 :=
        abstract Boolean semantics MUST be distinguished from physical electronic implementation details
}

REASONING_CHAIN Query Q {
    IDENTIFY requested_gate_or_circuit
    RESOLVE gate_aliases
    IDENTIFY gate_type
    DETERMINE arity
    IDENTIFY input_vector

    IF evaluation_requested
        THEN EVALUATE_GATE

    IF truth_table_requested
        THEN TRUTH_TABLE_GENERATION

    IF BooleanExpression_provided
        THEN EXPRESSION_TO_GATE_NETWORK

    IF circuit_provided AND expression_requested
        THEN GATE_NETWORK_TO_EXPRESSION

    IF NAND_only_requested
        THEN APPLY NAND_CONSTRUCTIONS recursively

    IF NOR_only_requested
        THEN APPLY NOR_CONSTRUCTIONS recursively

    IF simplification_requested
        THEN SIMPLIFY_GATE_NETWORK

    IF equivalence_requested
        THEN EQUIVALENCE_TEST

    VALIDATE BooleanSemantics
    RETURN result WITH derivation
}

CONFIDENCE {
    STANDARD_GATE_DEFINITION := 1.00
    COMPLETE_TRUTH_TABLE := 1.00
    BOOLEAN_EXPRESSION_MAPPING := 0.99
    UNIVERSAL_GATE_TRANSFORMATION := 0.99
    CIRCUIT_EQUIVALENCE :=
        IF exhaustive_boolean_inputs_checked THEN 1.00
        ELSE REQUIRE validation
    PHYSICAL_IMPLEMENTATION_CLAIM :=
        REQUIRE implementation_specific_source
}

UPDATE_MODEL {
    IMMUTABLE_CORE := {
        BooleanDomain,
        StandardGateTruthFunctions,
        GateFunctionMapping,
        TruthFunctionalSemantics
    }

    EXTENSIBLE := {
        CompositeCircuits,
        AlternativeGateRepresentations,
        OptimisationMethods,
        PhysicalImplementations,
        ApplicationDomains,
        RelatedOntologies
    }

    ON_NEW_KNOWLEDGE {
        VALIDATE BooleanFunction
        VALIDATE gate_arity
        VALIDATE truth_table
        CHECK semantic_consistency
        CHECK transformation_equivalence
        ADD relationship IF non_contradictory
        UPDATE confidence
    }
}

AI_CONSUMPTION {
    MACHINE_READABLE := TRUE
    HUMAN_INTERPRETABLE := TRUE
    RECURSIVE_REASONING := TRUE
    ENTITY_RESOLUTION := TRUE
    GATE_ALIAS_RESOLUTION := TRUE
    RELATIONSHIP_TRAVERSAL := TRUE
    BOOLEAN_EVALUATION := TRUE
    CIRCUIT_TRANSLATION := TRUE
    EQUIVALENCE_VALIDATION := TRUE
}

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

OUTPUT {
    PRIMARY_ENTITY := LogicGate

    INTERPRETATION :=
        "A logic gate is an abstract Boolean computational element whose truth-functional behaviour implements a Boolean function. Gates may be composed into networks that are semantically equivalent to Boolean expressions, truth tables and combinational logic functions."
}

END_FLOW