NAND Gate Ontology

FLOW_ALGEBRA NANDGateOntology v1.0

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

BEGIN_FLOW

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

RELATIONSHIP NANDGate --is_a--> LogicGate
RELATIONSHIP NANDGate --implements--> NegatedBooleanConjunction
RELATIONSHIP NANDGate --implements--> BooleanFunction
RELATIONSHIP NANDGate --corresponds_to--> NANDOperator
RELATIONSHIP NANDGate --is_composition_of--> ANDGate
RELATIONSHIP NANDGate --is_composition_of--> NOTGate
RELATIONSHIP NANDGate --can_be_represented_by--> BooleanExpression
RELATIONSHIP NANDGate --can_be_specified_by--> TruthTable
RELATIONSHIP NANDGate --is_a--> UniversalGate
RELATIONSHIP NANDGate --can_generate--> AllBooleanFunctions

ENTITY NANDOperator {
    TYPE := BooleanOperator
    SYMBOLS := {"NAND","↑","⊼"}
}

BOOLEAN_FUNCTION {
    BINARY :=
        NAND(x,y) := ¬(x ∧ y)

    NARY :=
        NAND(x1,...,xn) :=
            ¬(x1 ∧ x2 ∧ ... ∧ xn)

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

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

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

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

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

    IF FOR_ALL x IN X: x=1
        RETURN 0

    RETURN 1
}

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

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

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

AND_NOT_DECOMPOSITION {
    G1 := ANDGate(A,B)
    G2 := NOTGate(output(G1))

    RESULT :=
        NAND(A,B)
}

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

    NAND(A,B) ≡
        OR(
            NOT(A),
            NOT(B)
        )
}

UNIVERSALITY {
    PROPERTY := functionally_complete_single_gate_basis

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

NAND_ONLY_NOT {
    NOT(A) :=
        NAND(A,A)

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

NAND_ONLY_AND {
    T := NAND(A,B)

    AND(A,B) :=
        NAND(T,T)

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

NAND_ONLY_OR {
    NA := NAND(A,A)
    NB := NAND(B,B)

    OR(A,B) :=
        NAND(NA,NB)

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

NAND_ONLY_NOR {
    T :=
        NAND(
            NAND(A,A),
            NAND(B,B)
        )

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

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

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

NAND_ONLY_XNOR {
    X := NAND_ONLY_XOR(A,B)

    XNOR(A,B) :=
        NAND(X,X)
}

FUNCTIONAL_COMPLETENESS_DERIVATION {
    NAND -> NOT
    NAND -> AND
    {NOT,AND} -> AllBooleanFunctions

    THEREFORE:
        {NAND} -> 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:
        NANDGate(
            input1=A,
            input2=B,
            output=Y
        )
}

REVERSE_TRANSLATION {
    NANDGate(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_NAND(X)
        EMIT ROW(X,Y)
    }

    PROPERTY :=
        exactly_one_input_vector_has_output_0
        NAMELY (1,1,...,1)
}

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 {
    NAND(A,B) ≡ NAND(B,A)
}

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

    CONSEQUENCE :=
        parentheses and circuit topology matter
}

SELF_INPUT_BEHAVIOUR {
    NAND(A,A) ≡ ¬A

    CONSEQUENCE :=
        tied-input NAND gate implements NOT
}

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

    CONTROLLING_INPUT_VALUE := 0
}

ALL_TRUE_CONDITION {
    OUTPUT=0
    IFF every_input=1
}

DUAL_GATE {
    NANDGate --dual_of--> NORGate

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

NAND_VS_AND {
    NAND(A,B) :=
        NOT(AND(A,B))

    AND(A,B) :=
        NOT(NAND(A,B))
}

NAND_VS_NOR {
    NAND :=
        negated_conjunction

    NOR :=
        negated_disjunction

    BOTH :=
        universal_single_gate_bases
}

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

    NAND_ONLY_NETWORK {
        T1 := NAND(A,B)
        T2 := NAND(C,C)
        OUTPUT := NAND(T1,T2)
    }

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

NAND_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_NAND(INPUT_VALUES)
    }

    RETURN primary_outputs(N)
}

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

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

        IF yE != yN
            RETURN FALSE
    }

    RETURN TRUE
}

NAND_SYNTHESIS(Expression E) {
    CONVERT E TO operators {NOT,AND}
    REPLACE NOT(A) WITH NAND(A,A)
    REPLACE AND(A,B) WITH
        NAND(
            NAND(A,B),
            NAND(A,B)
        )

    RECURSIVELY simplify_shared_subexpressions
    VERIFY truth_table_equivalence

    RETURN NANDOnlyNetwork
}

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

ABSTRACT_MEMORY_RELATIONSHIP {
    CROSS_COUPLED_NAND_STRUCTURE
        --can_form-->
        SRLatchAbstraction

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

NORMAL_FORM_SYNTHESIS_ROLE {
    DNF_EXPRESSION
        -> AND_OR_NETWORK
        -> NAND_NAND_NETWORK

    REQUIRE :=
        Boolean_equivalence_preserved
}

ONTOLOGY_LINKS {
    PARENT := LogicGateOntology

    ANCESTORS := {
        BooleanLogicOntology,
        MathematicalLogicOntology,
        MathematicalOntology
    }

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

SEMANTIC_EQUIVALENCE {
    NANDGate ≈ NegatedANDGate
    NANDGate ≈ NOT-ANDGate
    NAND(A,B) ≈ ¬(A ∧ B)
    NAND(A,B) ≈ ¬A ∨ ¬B
    TRUE ≈ 1
    FALSE ≈ 0
}

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

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

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

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

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

    C6 :=
        binary NAND 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 NANDGate concept
    IDENTIFY requested representation
    DETERMINE arity
    RESOLVE Boolean aliases
    RESOLVE input_values

    IF evaluation_requested
        THEN EVALUATE_NAND

    IF truth_table_requested
        THEN TRUTH_TABLE_GENERATION

    IF expression_requested
        THEN RETURN negated_conjunction_expression

    IF NAND_only_synthesis_requested
        THEN NAND_SYNTHESIS

    IF target_gate_requested {
        IF target=NOT THEN NAND_ONLY_NOT
        IF target=AND THEN NAND_ONLY_AND
        IF target=OR THEN NAND_ONLY_OR
        IF target=NOR THEN NAND_ONLY_NOR
        IF target=XOR THEN NAND_ONLY_XOR
        IF target=XNOR THEN NAND_ONLY_XNOR
    }

    IF network_evaluation_requested
        THEN NAND_NETWORK_EVALUATION

    IF equivalence_requested
        THEN EQUIVALENCE_TEST

    VALIDATE canonical_NAND_semantics
    VALIDATE functional_equivalence
    RETURN result WITH derivation
}

CONFIDENCE {
    CANONICAL_NAND_DEFINITION := 1.00
    BINARY_TRUTH_TABLE := 1.00
    NARY_BOOLEAN_SEMANTICS := 1.00
    UNIVERSALITY := 1.00
    NAND_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,
        NegatedConjunctionTruthFunction,
        CanonicalBinaryTruthTable,
        FunctionalCompleteness
    }

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

    ON_NEW_KNOWLEDGE {
        VALIDATE against NANDTruthFunction
        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
    NAND_ONLY_SYNTHESIS := TRUE
    CIRCUIT_TRANSLATION := TRUE
    EQUIVALENCE_VALIDATION := TRUE
}

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

OUTPUT {
    PRIMARY_ENTITY := NANDGate

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

END_FLOW