3.1 Logic, Ontologies, and Semantic Networks

1. Propositional Logic: The Simplest Formal Language

"Aspirin inhibits cyclooxygenase-2 (COX-2)": true or false, no maybes allowed. That uncompromising binary crispness is the starting point of propositional logic, the simplest formal language for encoding scientific knowledge. A proposition is any declarative statement that must be one or the other ("the sample contains graphene," "pH exceeds 7"), and propositional logic gives us five connectives to build compound statements from these atoms:

• Negation (\(\neg p\)): "aspirin does not inhibit COX-2."
• Conjunction (\(p \land q\)): "the sample contains graphene and it is electrically conductive."
• Disjunction (\(p \lor q\)): "the compound is synthesized via route A or route B."
• Implication (\(p \to q\)): "if pH is below 3, then the protein denatures."
• Biconditional (\(p \leftrightarrow q\)): "the reaction is exothermic if and only if \(\Delta H < 0\)."

A knowledge base in propositional logic is a set of such formulas. Reasoning reduces to checking whether a query formula is a logical consequence of the knowledge base, written \(\text{KB} \models q\). For propositional logic this is decidable: truth tables or the Davis-Putnam-Logemann-Loveland (DPLL) algorithm (the ancestor of every Boolean satisfiability (SAT) solver) can answer the question in finite time, although worst-case complexity is NP-complete.

A knowledge base collects every formula the system accepts as true. It is the central data structure in any logic-based AI system, the single source of ground truth against which every query is evaluated. Knowledge bases matter because they separate what the system knows from how it reasons. The same inference engine works across different domains when you swap the stored formulas. The mechanism is straightforward: you add formulas (the "tell" operation) and then ask whether a new formula follows logically from what has been stored (the "ask" operation, implemented via satisfiability checking or resolution). Use a knowledge base when your domain has clear, categorical rules that can be stated as logical sentences; prefer statistical or learned models when the relationships are probabilistic, noisy, or too numerous to enumerate by hand. In short: logic gives a machine the ability to say not just what it knows, but what necessarily follows from what it knows.

Entailment in Practice

Let us build a tiny propositional knowledge base and check entailment using SymPy, which provides a clean symbolic logic engine.

from sympy.logic.boolalg import And, Or, Implies, Not
from sympy.logic.inference import satisfiable
from sympy import symbols

# Define atomic propositions
inhibits_cox2, reduces_inflammation, is_nsaid, has_gi_risk = symbols(
    'inhibits_cox2 reduces_inflammation is_nsaid has_gi_risk'
)

# Knowledge base: three rules about NSAIDs
kb = And(
    Implies(is_nsaid, inhibits_cox2),          # NSAIDs inhibit COX-2
    Implies(inhibits_cox2, reduces_inflammation),  # COX-2 inhibition reduces inflammation
    Implies(is_nsaid, has_gi_risk),            # NSAIDs carry GI risk
    is_nsaid                                    # Aspirin is an NSAID (ground fact)
)

# Query: does aspirin reduce inflammation?
# Check if KB ∧ ¬query is unsatisfiable (refutation)
query = reduces_inflammation
refutation = And(kb, Not(query))
result = satisfiable(refutation)
print(f"KB entails 'reduces_inflammation': {result == False}")
# Output: KB entails 'reduces_inflammation': True

# Query: does aspirin carry GI risk?
refutation2 = And(kb, Not(has_gi_risk))
result2 = satisfiable(refutation2)
print(f"KB entails 'has_gi_risk': {result2 == False}")
# Output: KB entails 'has_gi_risk': True

The limitation of propositional logic for scientific knowledge is immediately apparent: we cannot say "for all NSAIDs" or "there exists a compound that." Every fact about every individual must be stated separately. To talk about classes, instances, and relationships, we need quantifiers.

2. First-Order Logic: Variables, Quantifiers, and Predicates

First-order logic (FOL) extends propositional logic with three ingredients: variables that range over individuals in a domain, predicates that express properties and relationships, and quantifiers (\(\forall\) and \(\exists\)) that bind variables. The NSAID rules from above become a single universally quantified statement:

This one formula replaces the need to enumerate every NSAID individually. We can also express relational facts: \(\text{Inhibits}(\text{aspirin}, \text{COX\text{-}2})\) is a binary predicate linking a drug to a target. Functions let us build complex terms: \(\text{MolWeight}(\text{aspirin}) = 180.16\) uses a function symbol that maps a compound to its molecular weight.

FOL is the lingua franca of mathematical reasoning, and its influence pervades every knowledge representation formalism in this book. The Prolog programming language, for example, restricts FOL to Horn clauses (formulas of the form "if \(A_1\) and \(A_2\) and \(\ldots\) then \(B\)," where each \(A_i\) and \(B\) are positive atomic statements) and uses SLD resolution, a goal-directed proof strategy that works backward from the query to the known facts, for backward chaining. The reasoning engines in Chapter 4 build directly on FOL inference.

Here is a compact FOL knowledge base about drug targets, encoded in Python using a dictionary-based representation and a simple forward-chaining reasoner:

from dataclasses import dataclass
from typing import Set, Tuple

@dataclass(frozen=True)
class Fact:
    predicate: str
    args: tuple

    def __repr__(self):
        return f"{self.predicate}({', '.join(str(a) for a in self.args)})"

class FOLKnowledgeBase:
    """A toy first-order knowledge base with forward chaining."""

    def __init__(self):
        self.facts: Set[Fact] = set()
        self.rules = []  # list of (condition_fn, consequent_fn)

    def tell(self, predicate: str, *args):
        self.facts.add(Fact(predicate, args))

    def add_rule(self, condition_fn, consequent_fn):
        """condition_fn(fact) -> bool; consequent_fn(fact) -> list of new Facts."""
        self.rules.append((condition_fn, consequent_fn))

    def forward_chain(self, max_iterations=100):
        """Apply rules until no new facts are derived."""
        for _ in range(max_iterations):
            new_facts = set()
            for fact in self.facts:
                for cond, conseq in self.rules:
                    if cond(fact):
                        for new_fact in conseq(fact):
                            if new_fact not in self.facts:
                                new_facts.add(new_fact)
            if not new_facts:
                break
            self.facts |= new_facts
        return self.facts

    def ask(self, predicate: str, *args) -> bool:
        return Fact(predicate, args) in self.facts

# Build KB
kb = FOLKnowledgeBase()
kb.tell("NSAID", "aspirin")
kb.tell("NSAID", "ibuprofen")
kb.tell("Target", "COX-2")

# Rule: for all x, NSAID(x) -> InhibitsCOX2(x)
kb.add_rule(
    lambda f: f.predicate == "NSAID",
    lambda f: [Fact("InhibitsCOX2", (f.args[0],)),
               Fact("HasGIRisk", (f.args[0],))]
)

# Rule: InhibitsCOX2(x) -> ReducesInflammation(x)
kb.add_rule(
    lambda f: f.predicate == "InhibitsCOX2",
    lambda f: [Fact("ReducesInflammation", (f.args[0],))]
)

derived = kb.forward_chain()
print(f"Derived {len(derived)} facts:")
for f in sorted(derived, key=str):
    print(f"  {f}")
print(f"\nDoes ibuprofen reduce inflammation? {kb.ask('ReducesInflammation', 'ibuprofen')}")
# Output:
# Derived 9 facts:
#   HasGIRisk(aspirin)
#   HasGIRisk(ibuprofen)
#   InhibitsCOX2(aspirin)
#   InhibitsCOX2(ibuprofen)
#   NSAID(aspirin)
#   NSAID(ibuprofen)
#   ReducesInflammation(aspirin)
#   ReducesInflammation(ibuprofen)
#   Target(COX-2)
#
# Does ibuprofen reduce inflammation? True

3. Description Logics: The Decidable Core of Ontology Languages

When a hospital's clinical decision system misclassifies a drug interaction because its reasoning engine cannot finish computing in time, patients are at risk. That failure mode is exactly what drove the design of description logics: formalisms where every query is guaranteed to terminate, so that safety-critical systems can rely on them.

FOL's expressive power comes at a steep computational price, so researchers carved out restricted fragments that guarantee termination while retaining enough structure to model real scientific domains.

Description logics (DLs) sit between propositional logic and full FOL. They are carefully calibrated: expressive enough for real-world ontologies, yet decidable for key reasoning tasks. The basic building blocks are:

• Concepts (unary predicates): classes of individuals, such as Drug, Protein, Disease.
• Roles (binary predicates): relationships between individuals, such as inhibits, treats, causedBy.
• Individuals (constants): named entities, such as aspirin, COX-2, rheumatoid_arthritis.

Concepts can be combined using constructors. In the widely-used \(\mathcal{ALC}\) (Attributive Language with Complements) description logic, the constructors are:

where \(A\) is an atomic concept, \(R\) is a role, \(\top\) is the universal concept (everything), and \(\bot\) is the empty concept (nothing). The expression \(\exists \text{inhibits}.\text{Enzyme}\) denotes "the class of things that inhibit at least one enzyme." The expression \(\text{Drug} \sqcap \exists \text{treats}.\text{Cancer}\) denotes "drugs that treat some cancer."

A TBox (terminological box, the component of a DL knowledge base that stores concept definitions and axioms about classes) contains concept definitions and axioms:

This says: every NSAID is a Drug that inhibits some COX enzyme. An ABox (assertional box, the component that stores facts about specific named individuals) contains facts about individuals:

The four standard reasoning tasks for description logics are: satisfiability (can concept \(C\) have any instances?), subsumption (is every instance of \(C\) also an instance of \(D\)?), instance checking (is individual \(a\) an instance of concept \(C\)?), and retrieval (find all individuals that are instances of \(C\)). For \(\mathcal{ALC}\), all four are decidable in EXPTIME (exponential time in the size of the input, meaning the algorithm terminates but may take time that grows exponentially with the number of axioms). Figure 3.1.1 illustrates Description Logic TBox and ABox architecture.

4. OWL and RDF: Standards for the Semantic Web

Description logics supply the theoretical foundations, but to share ontologies across labs, hospitals, and databases, those foundations need a concrete file format and query protocol that every tool can agree on.

The W3C's Resource Description Framework (RDF) provides a concrete syntax for expressing knowledge as triples: (subject, predicate, object). Every entity and relationship is identified by a Uniform Resource Identifier (URI), making knowledge globally addressable. The triple \((\text{ex:aspirin}, \text{ex:inhibits}, \text{ex:COX-2})\) is an RDF statement. Collections of triples form an RDF graph.

RDF Schema (RDFS) adds vocabulary for class hierarchies (rdfs:subClassOf), property domains and ranges, and labels. OWL goes further, providing the full expressiveness of description logics: cardinality restrictions, disjointness, equivalence, property characteristics (transitivity, symmetry, functionality), and more. OWL comes in three profiles that trade expressiveness for computational complexity (see also Figure 3.1):

• OWL EL: polynomial-time reasoning, suitable for large biomedical ontologies (SNOMED CT, Gene Ontology).
• OWL QL: designed for query answering over large ABoxes, reducible to SQL.
• OWL DL: corresponds to the description logic \(\mathcal{SROIQ}\), decidable but 2NEXPTIME-complete.

Let us build a small scientific ontology using RDFLib and query it with SPARQL (SPARQL Protocol and RDF Query Language):

from rdflib import Graph, Namespace, Literal, RDF, RDFS, OWL

# Create namespaces
EX = Namespace("http://example.org/discovery/")
g = Graph()
g.bind("ex", EX)

# TBox: define classes
g.add((EX.Drug, RDF.type, OWL.Class))
g.add((EX.Protein, RDF.type, OWL.Class))
g.add((EX.Disease, RDF.type, OWL.Class))
g.add((EX.NSAID, RDF.type, OWL.Class))
g.add((EX.NSAID, RDFS.subClassOf, EX.Drug))

# Define properties
g.add((EX.inhibits, RDF.type, OWL.ObjectProperty))
g.add((EX.inhibits, RDFS.domain, EX.Drug))
g.add((EX.inhibits, RDFS.range, EX.Protein))
g.add((EX.treats, RDF.type, OWL.ObjectProperty))
g.add((EX.treats, RDFS.domain, EX.Drug))
g.add((EX.treats, RDFS.range, EX.Disease))

# ABox: individuals
for drug, cls in [("aspirin", EX.NSAID), ("ibuprofen", EX.NSAID)]:
    g.add((EX[drug], RDF.type, cls))
    g.add((EX[drug], RDFS.label, Literal(drug)))

g.add((EX.aspirin, EX.inhibits, EX.COX2))
g.add((EX.ibuprofen, EX.inhibits, EX.COX2))
g.add((EX.COX2, RDF.type, EX.Protein))
g.add((EX.COX2, RDFS.label, Literal("Cyclooxygenase-2")))

# SPARQL query: find all drugs that inhibit a protein
query = """
SELECT ?drug ?target WHERE {
    ?drug ex:inhibits ?target .
    ?drug a/rdfs:subClassOf* ex:Drug .
    ?target a ex:Protein .
}
"""
print("Drugs and their protein targets:")
for row in g.query(query, initNs={"ex": EX}):
    print(f"  {row.drug.split('/')[-1]} inhibits {row.target.split('/')[-1]}")
# Output:
# Drugs and their protein targets:
#   aspirin inhibits COX2
#   ibuprofen inhibits COX2

print(f"\nTotal triples in graph: {len(g)}")
# Output: Total triples in graph: 16

from owlready2 import get_ontology, Thing, ObjectProperty

onto = get_ontology("http://example.org/discovery.owl")
with onto:
    class Drug(Thing): pass
    class NSAID(Drug): pass
    class Protein(Thing): pass
    class inhibits(Drug >> Protein): pass

    aspirin = NSAID("aspirin")
    cox2 = Protein("COX2")
    aspirin.inhibits.append(cox2)

# Run the HermiT reasoner
from owlready2 import sync_reasoner
sync_reasoner()
print(list(onto.search(type=Drug)))
# [discovery.aspirin]  (classified via NSAID ⊑ Drug)

5. Semantic Networks and Frames

Before the Semantic Web standardized ontology languages, AI researchers used two related formalisms: semantic networks and frames. A semantic network is a labeled directed graph: nodes are concepts, edges carry typed relationships (IS-A, HAS-PART, CAUSES). Quillian (1968) introduced them for modeling associative memory; Collins and Loftus (1975) added spreading activation, a process in which triggering one node sends a signal along weighted edges to neighboring nodes, with signal strength decaying over distance, where triggering a node propagates signal to its neighbors through weighted edges.

Frames (Minsky, 1975) organize knowledge into structured records: a frame for "Enzyme" might have slots for substrate, product, optimal_pH, cofactor, each with type constraints, default values, and inheritance from parent frames. Frames are the precursor to object-oriented programming and to the slot-and-filler representations used in modern knowledge graphs.

In modern practice, semantic networks are typically implemented using the same graph infrastructure that powers knowledge graphs: property graph databases such as Neo4j or RDF triple stores. The conceptual vocabulary of semantic networks (typed nodes, labeled edges, inheritance via IS-A links) maps directly onto these tools, so rather than building a bespoke semantic network library, practitioners today encode network-style knowledge in RDF (as shown in Section 4 above) or in a property graph (as Section 3.2 demonstrates). What the historical formalisms contribute is the design intuition: knowledge is not a flat collection of facts but a structured network where meaning emerges from connections.

6. Choosing a Representation for Scientific Discovery

The formalisms in this section form a spectrum of expressiveness and tractability. The table below summarizes the trade-offs:

In practice, a discovery AI system rarely uses a single formalism. The Discovery Workbench architecture (introduced in Chapter 6) combines an OWL ontology for the domain schema, a property graph for instance-level knowledge, and dense embeddings for similarity search. The next section shows how to build the graph layer.