NOR Gate Ontology

FLOW_ALGEBRA NORGateOntology v1.0

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

BEGIN_FLOW

ENTITY NORGate {
    TYPE := LogicGate
    LOGICAL_ROLE := NegatedDisjunction
    MIN_ARITY := 2
    INPUT_DOMAIN := {0,1} ≡ {FALSE,TRUE}
    OUTPUT_DOMAIN := {0,1} ≡ {FALSE,TRUE}
    DEFINITION := "A logic gate whose output is true exactly when all Boolean inputs are false; otherwise its output is false."
}

RELATIONSHIP NORGate --is_a--> LogicGate
RELATIONSHIP NORGate --implements--> NegatedBooleanDisjunction
RELATIONSHIP NORGate --implements--> BooleanFunction
RELATIONSHIP NORGate --corresponds_to--> NOROperator
RELATIONSHIP NORGate --is_composition_of--> ORGate
RELATIONSHIP NORGate --is_composition_of--> NOTGate
RELATIONSHIP NORGate --can_be_represented_by--> BooleanExpression
RELATIONSHIP NORGate --can_be_specified_by--> TruthTable
RELATIONSHIP NORGate --is_a--> UniversalGate
RELATIONSHIP NORGate --can_generate--> AllBooleanFunctions

ENTITY NOROperator {
    TYPE := BooleanOperator
    SYMBOLS := {"NOR","↓","⊽"}
}

BOOLEAN_FUNCTION {
    BINARY :=
        NOR(x,y) := ¬(x ∨ y)

    NARY :=
        NOR(x1,...,xn) :=
            ¬(x1 ∨ x2 ∨ ... ∨ xn)

    CONDITION :=
        OUTPUT=1 IFF FOR_ALL xi: xi=0
}

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

NARY_SEMANTICS {
    INPUTS := x1,...,xn
    n >= 2

    IF FOR_ALL i IN {1,...,n}:
        xi=0
    THEN
        OUTPUT := 1
    ELSE
        OUTPUT := 0
}

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

    IF FOR_ALL x IN X: x=0
        RETURN 1

    RETURN 0
}

ALGEBRAIC_FORM {
    FOR BooleanValues xi IN {0,1}:
        NOR(x1,...,xn) =
            PRODUCT(i=1..n, (1-xi))
}

PROPOSITIONAL_LOGIC_MAPPING {
    INPUT_A := proposition_P
    INPUT_B := proposition_Q
    OUTPUT := ¬(P ∨ Q)

    SEMANTICS :=
        output is true only when P and Q are both false
}

OR_NOT_DECOMPOSITION {
    G1 := ORGate(A,B)
    G2 := NOTGate(output(G1))

    RESULT :=
        NOR(A,B)
}

DEMORGAN_EQUIVALENCE {
    ¬(A ∨ B) ≡
        ¬A ∧ ¬B

    NOR(A,B) ≡
        AND(
            NOT(A),
            NOT(B)
        )
}

UNIVERSALITY {
    PROPERTY := functionally_complete_single_gate_basis

    STATEMENT :=
        "Every Boolean function can be expressed using NOR gates alone."
}

NOR_ONLY_NOT {
    NOT(A) :=
        NOR(A,A)

    VERIFY {
        A=0 -> NOR(0,0)=1
        A=1 -> NOR(1,1)=0
    }
}

NOR_ONLY_OR {
    T := NOR(A,B)

    OR(A,B) :=
        NOR(T,T)

    EXPANDED :=
        NOR(
            NOR(A,B),
            NOR(A,B)
        )
}

NOR_ONLY_AND {
    NA := NOR(A,A)
    NB := NOR(B,B)

    AND(A,B) :=
        NOR(NA,NB)

    EXPANDED :=
        NOR(
            NOR(A,A),
            NOR(B,B)
        )
}

NOR_ONLY_NAND {
    T :=
        NOR(
            NOR(A,A),
            NOR(B,B)
        )

    NAND(A,B) :=
        NOR(T,T)
}

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

    XNOR(A,B) :=
        NOR(T2,T3)
}

NOR_ONLY_XOR {
    XN := NOR_ONLY_XNOR(A,B)

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

FUNCTIONAL_COMPLETENESS_DERIVATION {
    NOR -> NOT
    NOR -> OR
    {NOT,OR} -> AllBooleanFunctions

    THEREFORE:
        {NOR} -> AllBooleanFunctions
}

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

    LOGICAL_EQUATION :=
        Y = ¬(A ∨ B)
        FOR binary_gate
}

EXPRESSION_TRANSLATION {
    BooleanExpression:
        ¬(A ∨ B)

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

REVERSE_TRANSLATION {
    NORGate(A,B)->Y

    MAP_TO BooleanExpression:
        Y := ¬(A ∨ B)
}

TRUTH_TABLE_GENERATION(Arity n) {
    REQUIRE n >= 2

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

    PROPERTY :=
        exactly_one_input_vector_has_output_1
        NAMELY (0,0,...,0)
}

LOGICAL_PROPERTIES {
    COMMUTATIVE_BINARY := TRUE
    ASSOCIATIVE_AS_BINARY_OPERATOR := FALSE
    IDEMPOTENT := FALSE
    MONOTONE := FALSE
    ANTITONE_IN_EACH_ARGUMENT := TRUE
    ZERO_PRESERVING := FALSE
    ONE_PRESERVING := FALSE
    FUNCTIONALLY_COMPLETE := TRUE
}

COMMUTATIVITY {
    NOR(A,B) ≡ NOR(B,A)
}

NON_ASSOCIATIVITY {
    IN_GENERAL:
        NOR(NOR(A,B),C)
        !=
        NOR(A,NOR(B,C))

    CONSEQUENCE :=
        parentheses and circuit topology matter
}

SELF_INPUT_BEHAVIOUR {
    NOR(A,A) ≡ ¬A

    CONSEQUENCE :=
        tied-input NOR gate implements NOT
}

CONTROLLING_VALUE {
    FOR a given input:
        input 1 forces NOR output 0

    CONTROLLING_INPUT_VALUE := 1
}

ALL_FALSE_CONDITION {
    OUTPUT=1
    IFF every_input=0
}

DUAL_GATE {
    NORGate --dual_of--> NANDGate

    DUALITY_TRANSFORMATION {
        OR <-> AND
        0 <-> 1
        NOR <-> NAND
    }
}

NOR_VS_OR {
    NOR(A,B) :=
        NOT(OR(A,B))

    OR(A,B) :=
        NOT(NOR(A,B))
}

NOR_VS_NAND {
    NOR :=
        negated_disjunction

    NAND :=
        negated_conjunction

    BOTH :=
        universal_single_gate_bases
}

COMPOSITION_EXAMPLE {
    TARGET_EXPRESSION :=
        (A ∨ B) ∧ C

    NOR_ONLY_NETWORK {
        T1 := NOR(A,B)
        T2 := NOR(C,C)
        OUTPUT := NOR(T1,T2)
    }

    DERIVATION :=
        NOR(
            ¬(A∨B),
            ¬C
        )
        =
        ¬(
            ¬(A∨B) ∨ ¬C
        )
        =
        (A∨B) ∧ C
}

NOR_NETWORK_EVALUATION(Network N, Assignment A) {
    TOPOLOGICALLY_ORDER gates(N)

    FOR_EACH gate G IN order {
        INPUT_VALUES :=
            resolve_primary_or_previous_outputs(G,A)

        OUTPUT(G) :=
            EVALUATE_NOR(INPUT_VALUES)
    }

    RETURN primary_outputs(N)
}

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

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

        IF yE != yN
            RETURN FALSE
    }

    RETURN TRUE
}

NOR_SYNTHESIS(Expression E) {
    CONVERT E TO operators {NOT,OR}
    REPLACE NOT(A) WITH NOR(A,A)
    REPLACE OR(A,B) WITH
        NOR(
            NOR(A,B),
            NOR(A,B)
        )

    RECURSIVELY simplify_shared_subexpressions
    VERIFY truth_table_equivalence

    RETURN NOROnlyNetwork
}

APPLICATION_RELATIONSHIPS {
    NORGate --used_in--> UniversalLogicSynthesis
    NORGate --used_in--> CombinationalLogic
    NORGate --used_in--> ArithmeticCircuits
    NORGate --used_in--> ControlLogic
    NORGate --used_in--> DataSelectionLogic
    NORGate --used_in--> MemoryCircuitConstruction
    NORGate --used_in--> BooleanFunctionImplementation
    NORGate --used_in--> DigitalSystemDesign
}

ABSTRACT_MEMORY_RELATIONSHIP {
    CROSS_COUPLED_NOR_STRUCTURE
        --can_form-->
        SRLatchAbstraction

    NOTE :=
        sequential behaviour requires state/time semantics beyond the pure combinational NOR truth function
}

NORMAL_FORM_SYNTHESIS_ROLE {
    CNF_EXPRESSION
        -> OR_AND_NETWORK
        -> NOR_NOR_NETWORK

    REQUIRE :=
        Boolean_equivalence_preserved
}

ONTOLOGY_LINKS {
    PARENT := LogicGateOntology

    ANCESTORS := {
        BooleanLogicOntology,
        MathematicalLogicOntology,
        MathematicalOntology
    }

    RELATED := {
        ANDGateOntology,
        ORGateOntology,
        NOTGateOntology,
        NANDGateOntology,
        XORGateOntology,
        XNORGateOntology,
        BooleanFunctionOntology,
        BooleanExpressionOntology,
        BooleanAlgebraOntology,
        TruthTableOntology,
        DigitalLogicOntology
    }
}

SEMANTIC_EQUIVALENCE {
    NORGate ≈ NegatedORGate
    NORGate ≈ NOT-ORGate
    NOR(A,B) ≈ ¬(A ∨ B)
    NOR(A,B) ≈ ¬A ∧ ¬B
    TRUE ≈ 1
    FALSE ≈ 0
}

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

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

    C3 :=
        output MUST equal 1 exactly when all inputs equal 0

    C4 :=
        binary NORGate MUST match the canonical four-row truth table

    C5 :=
        NOR-only constructions MUST preserve target Boolean semantics

    C6 :=
        binary NOR MUST NOT be treated as associative

    C7 :=
        claims of functional completeness MUST refer to arbitrary finite Boolean functions

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

REASONING_CHAIN Query Q {
    IDENTIFY NORGate concept
    IDENTIFY requested representation
    DETERMINE arity
    RESOLVE Boolean aliases
    RESOLVE input_values

    IF evaluation_requested
        THEN EVALUATE_NOR

    IF truth_table_requested
        THEN TRUTH_TABLE_GENERATION

    IF expression_requested
        THEN RETURN negated_disjunction_expression

    IF NOR_only_synthesis_requested
        THEN NOR_SYNTHESIS

    IF target_gate_requested {
        IF target=NOT THEN NOR_ONLY_NOT
        IF target=OR THEN NOR_ONLY_OR
        IF target=AND THEN NOR_ONLY_AND
        IF target=NAND THEN NOR_ONLY_NAND
        IF target=XNOR THEN NOR_ONLY_XNOR
        IF target=XOR THEN NOR_ONLY_XOR
    }

    IF network_evaluation_requested
        THEN NOR_NETWORK_EVALUATION

    IF equivalence_requested
        THEN EQUIVALENCE_TEST

    VALIDATE canonical_NOR_semantics
    VALIDATE functional_equivalence
    RETURN result WITH derivation
}

CONFIDENCE {
    CANONICAL_NOR_DEFINITION := 1.00
    BINARY_TRUTH_TABLE := 1.00
    NARY_BOOLEAN_SEMANTICS := 1.00
    UNIVERSALITY := 1.00
    NOR_ONLY_STANDARD_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,
        NegatedDisjunctionTruthFunction,
        CanonicalBinaryTruthTable,
        FunctionalCompleteness
    }

    EXTENSIBLE := {
        NOROnlySynthesisMethods,
        CircuitApplications,
        OptimisationMethods,
        SequentialStructures,
        HardwareRealisation,
        RelatedOntologies
    }

    ON_NEW_KNOWLEDGE {
        VALIDATE against NORTruthFunction
        VALIDATE arity
        VALIDATE BooleanDomain
        CHECK semantic_consistency
        CHECK truth_table_equivalence
        CHECK universal_construction_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
    TRUTH_TABLE_REASONING := TRUE
    NOR_ONLY_SYNTHESIS := TRUE
    CIRCUIT_TRANSLATION := TRUE
    EQUIVALENCE_VALIDATION := TRUE
}

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

OUTPUT {
    PRIMARY_ENTITY := NORGate

    INTERPRETATION :=
        "A NOR gate implements negated Boolean disjunction, producing true only when every input is false. Because NOR alone can construct NOT, OR, AND and therefore arbitrary finite Boolean functions, it forms a functionally complete basis for Boolean logic and digital circuit synthesis."
}

END_FLOW