We closed module 5 with an uncomfortable observation: neural networks and large language models are subsymbolic and opaque; nobody can read their weights or hold them to account for a decision. And NovaMarket has decisions that must be readable and justifiable: whether or not a refund applies (case 8) or what the probable cause of an incident is (case 9). This lesson opens the other half of artificial intelligence, the symbolic AI of the first decades of 01-01, starting from its foundation: logic, the formal language for representing knowledge explicitly and reasoning with it in a verifiable way. We will cover propositional logic (propositions, connectives and truth tables, equivalences, inference rules, knowledge bases and the notion of logical entailment), first-order logic (objects, predicates, quantifiers), which lets us write NovaMarket's returns policies precisely, and the working mechanism of almost every rule-based system: forward and backward chaining with Horn clauses. All of it with pure Python code that you can run and read, line by line. It matters because logic is the vocabulary shared by the next three lessons: expert systems (06-02) are logic plus engineering, Bayesian networks (06-03) are the answer to what logic cannot do, and the applications of 06-04 are logic in production.

1. Why logic: explicit, verifiable knowledge
2. Propositional logic: propositions and connectives
3. Tautologies, contradictions, satisfiability and useful equivalences
4. Inference rules: modus ponens, modus tollens and resolution
5. Knowledge base and query: KB ⊨ α by model enumeration
6. First-order logic: objects, predicates, functions and quantifiers
7. Horn clauses: forward and backward chaining
8. Prolog, the language of logic
9. Limitations: closed world, monotonicity and uncertainty
10. Common Mistakes and Tips
11. Exercises
12. Conclusion

In 02-02 we distinguished symbolic AI (symbols and rules a human can read) from subsymbolic AI (numbers and weights that nobody reads). Modules 4 and 5 were subsymbolic: the logistic regression of 04-04 and the MLP of 05-03 learn weights from orders.csv, and the LLM of 05-05 generates text without being able to explain why. For many tasks that is the right approach. But consider what Diego needs for returns:

• The rule exists before the data. The 14-day withdrawal period or the 3-year legal guarantee are not learned from a history: they are set by the regulations and by NovaMarket's commercial policy. A model that "learned" 13 or 16 days would simply be wrong.
• The decision must be justifiable to the customer, to an auditor and, as we saw in 02-04, under the AI Act and the GDPR (automated decisions with significant effects). "The model gave 0.71" is not a justification; "no refund applies because the product is used and 20 days have passed, rule R3" is.
• It must be verifiable: Diego has to be able to read the rules, spot that two of them contradict each other and correct them, without retraining anything.
• There is little data and there are many edge cases (an opened hygiene product, an extended warranty), exactly where ML performs worst.

Logic offers exactly that: a formal language with a precise syntax (which sentences are well formed), a precise semantics (what it means for a sentence to be true) and inference rules that derive new conclusions mechanically and correctly. It is the tool Aristotle sketched, Boole and Frege formalised, and the Logic Theorist of 1956 brought to the computer (01-01). We start with the simplest version.

A proposition is a statement that is either true or false, with no middle ground: "the product is used", "more than 14 days have passed since delivery", "a refund applies". We represent them with letters (P, Q, R) or with readable names (used, over14, refund). A model (or interpretation) is an assignment of true/false to every proposition: it describes a "possible world". With 3 propositions there are 2³ = 8 possible worlds.

Connectives combine propositions into compound formulas. Their meaning is defined by truth tables, which give the value of the formula for every combination of values of its parts:

Two important observations for beginners:

• The logical or is inclusive: "P ∨ Q" is also true when both are true. "Product damaged or wrong" allows it to be both.
• The implication P → Q is false only when P is true and Q is false. If P is false, the implication is true whatever Q is: the rule "if it is used and 14 days have passed, no refund applies" says nothing about unused products; they do not violate it. This is surprising at first, but it is exactly what we want from a rule: the only case that violates it is one that meets the condition and contradicts the conclusion.

Diego's rule, the one that closed module 5, is written (used ∧ over14) → ¬refund. Its truth table has 8 rows and only one is false: the world in which the product is used, more than 14 days have passed and it is refunded anyway. That world is the one the rule forbids. Let us generate tables like this in code.

We represent a formula as a variable name (a string) or a tuple whose first element is the operator: ("and", "P", "Q"), ("not", "R"), ("->", ("and", "P", "Q"), ("not", "R")). A recursive evaluator walks down the tuple and applies each connective's truth table; itertools.product generates all the T/F combinations.

Output:

Explanation: evaluate is a recursive function: if the formula is a string it returns its value in the model; if it is a tuple, it evaluates the operands and combines the results with the connective's table. Note the "->" line: we implement the implication as (not P) or Q, which is its definition. product([True, False], repeat=3) generates the 8 rows. The only false row is the first (used, more than 14 days, and refunded), as we had reasoned.

Depending on how a formula behaves across all models, we classify it:

Two formulas are equivalent (≡) if they have the same truth table, that is, if their biconditional is a tautology. Equivalences let you rewrite rules without changing their meaning, something the engine of 06-02 will do and that you will do when debugging Diego's rules:

Beware of the converse: P → Q is not equivalent to Q → P. "If it is defective, a refund applies" does not mean "if a refund applies, it is defective" (it may apply because of withdrawal). It is the most frequent logical error in badly written business rules.

We check De Morgan and a contradiction with the code above:

Output (abridged):

Truth tables settle any question, but with n propositions they have 2ⁿ rows: with the 40 propositions a real returns system may handle, that is a trillion rows. Inference rules avoid enumeration: they are patterns that, applied to true formulas, produce true formulas (they are sound).

Modus ponens is the star rule of expert systems: given "if conditions then conclusion" and the conditions, add the conclusion. It is literally what the engine of section 7 will do.

Resolution deserves an intuition: if we know that "the package arrived damaged or the product was the wrong one" (P ∨ Q) and also that "it did not arrive damaged or the cause is transport" (¬P ∨ R), then, whatever the value of P, something survives: if P is true, the second clause forces R; if it is false, the first forces Q. Hence Q ∨ R. Resolution is a single rule that, applied to formulas converted to a clausal normal form, is complete: if something follows logically, resolution finds it (often by showing that the negation leads to the empty clause, a contradiction). It is the internal engine of Prolog (section 8) and of automated theorem provers; here the idea is enough.

A knowledge base (KB) is a set of formulas we take to be true: general rules plus the facts of the case. A query α is a formula we ask about. We say the KB logically entails α, written KB ⊨ α, when α is true in every model in which the KB is true. It is the precise definition of "follows from what we know": there is no world compatible with what we know in which α is false.

The most direct way to check it is model enumeration: go through every assignment, keep those that satisfy the KB and check whether α is true in all of them. It is exponential, but for small bases it is perfect and, above all, it is the definition turned into code.

Output:

Explanation, line by line of the result:

• KB ⊨ ¬refund: with used and over14 as facts, Diego's rule forces ¬refund in the only compatible model. Modus ponens done by brute force.
• KB ⊨ ¬defective: we never wrote this, and yet it follows: if it were defective there would be a refund (rule 2), but there is none (rule 1); therefore it is not defective. That is modus tollens, and it is a useful alarm: the KB as written asserts that a used product returned after 20 days cannot be defective, which is absurd. Logic has detected that the two rules, together, are incompatible with a real case (used, late and defective: the KB would be inconsistent, with no model at all, and from an inconsistent KB anything follows). In 06-02 we will resolve it with priorities between rules; here it is enough to notice that formal verification has found a design error that an opaque model would never reveal.
• KB ⊨ refund is false, with an explicit counterexample: the world in which it is not defective and there is no refund is compatible with the KB.
• KB2: once the fact over14 is removed, ¬refund can no longer be concluded; the counterexample shows a world where over14 is false, defective and refunded. The query is undecided: more information is needed. That "missing question" will be the engine behind the question interface of 06-02.

Propositional logic treats "the product is used" as an indivisible atom. But NovaMarket has 12,000 products and 3,000 orders a day: we are not going to write a proposition used_order_48377, used_order_48378... First-order logic (FOL) adds internal structure to statements:

• Objects: things in the world: order 48377, the NovaClean vacuum cleaner, the customer Ana López, the Getafe warehouse. They are named with constants (o48377, getafe).
• Predicates: properties of objects and relations between them, true or false: Product(x), Sealed(x), Defective(x), DeliveredFrom(p, warehouse), Customer(c, p).
• Functions: return an object from other objects: DaysSinceDelivery(p) returns a number, Warehouse(p) returns a warehouse.
• Variables and quantifiers: ∀x ("for all x") and ∃x ("there exists some x").
• The same connectives ¬, ∧, ∨, →, ↔ as before.

Now NovaMarket's returns policy can be written once for every product (the business data we fix here and that will reappear throughout the module: 14-day withdrawal, 3-year legal guarantee for new products, sealed/hygiene products not returnable once opened, original label, free return shipping if defective; the specific consumer regulations must always be reviewed by a legal professional, this is a teaching example):

The first rule is the one announced in this lesson's outline: Returnable(p) ← Product(p) ∧ ¬Sealed(p) ∧ DaysSinceDelivery(p) ≤ 14, written with the arrow pointing left ("Returnable if..."), the usual notation for rules. Two reading notes:

• ∀ goes with →: "for all p, if p is an unsealed product within the period, then it is returnable". Writing ∀p (Product(p) ∧ Returnable(p)) would say that every object is a returnable product: false.
• ∃ goes with ∧: "there exists p such that p is a product and defective and from Getafe". Writing ∃p (Product(p) → Defective(p)) would be trivially true as soon as anything that is not a product exists (an implication with a false antecedent is true).

The two statements are related by quantified De Morgan: ¬∀x P(x) ≡ ∃x ¬P(x) ("not every package arrives in good condition" = "some package does not arrive in good condition").

To apply modus ponens to a rule with variables, it has to be matched against concrete facts: unify Product(p) with Product(o48377) by substituting p = o48377, check ¬Sealed(o48377), OriginalLabel(o48377) and DaysSinceDelivery(o48377) ≤ 14 with the same substitution, and conclude Returnable(o48377). Unification is the algorithm that finds the variable substitution that makes two expressions equal (Customer(c, o48377) unifies with Customer(ana, o48377) with c = ana; Customer(ana, p) does not unify with Customer(luis, o48377)). It is the piece that lets one general rule apply to thousands of cases, and the heart of Prolog. In our code we will spare ourselves unification with a trick that is common in practice: instantiate the rules for a specific order, that is, turn the predicates about the order into propositions (within_period, unused), which takes us back to propositional logic, where modus ponens is a simple all(...).

General inference in FOL is expensive (even undecidable in general). Rule-based systems restrict formulas to Horn clauses: implications with a conjunction of positive premises and a single positive conclusion, P₁ ∧ P₂ ∧ ... ∧ Pₙ → Q (a fact is the case n = 0). With that restriction there are two efficient, sound algorithms:

• Forward chaining (data-driven): you start from the known facts, apply modus ponens to every rule whose premises are already satisfied, add the conclusion and repeat until nothing new appears. It derives everything derivable. Suitable when data arrives and you want all its consequences (an order comes back and the system works out refund, free shipping, supplier notice...).
• Backward chaining (goal-driven): you start from the question ("does a refund apply?"), look for rules whose conclusion is that goal, and turn their premises into new subgoals, recursively, until you reach facts. It explores only what is relevant to the question and, if a fact is missing, it can ask the user for it: that is how the interactive diagnostic systems of 06-02 work.

NovaMarket's return rules as Horn clauses (small version, with no conflicts between rules; conflicts are handled in 06-02):

Forward trace for order 48213 (NovaBrew coffee maker delivered 9 days ago, with its label, unused, not defective). Initial facts: days_le_14, days_le_1095, original_label, unused.

Backward trace for order 47102 (NovaClean vacuum cleaner, 40 days, used, no label, defective), goal refund_applies:

Notice how backward chaining backtracks when a branch fails and tries the next rule with the same conclusion.

Output:

Explanation:

• RULES is a list of tuples: name, list of premises and conclusion. It is the whole "knowledge base" of rules; the facts of each order are produced by facts_of, which instantiates the first-order predicates (DaysSinceDelivery(p) ≤ 14) as propositions (days_le_14) for that specific order, as announced in 6.1.
• forward_chain is an "until nothing changes" loop: on each pass it goes through the rules and fires (modus ponens) those that have all their premises in the fact set and whose conclusion is not there yet. It returns the final facts and the list of rules applied, which is already a rudimentary explanation ("refund applies because of R1, R3, R5"). In 06-02 we will enrich it.
• Compare the three orders: the coffee maker is refunded under withdrawal; the used, late headphones do not derive refund_applies (nothing proves it, and under the closed world that means "no"); the defective vacuum cleaner at 40 days is refunded under warranty and also gets free shipping (R7), even though it has no label and is not unused: the warranty is a separate route from withdrawal, exactly as in the real policy.
• prove is backward chaining in ten lines: if the goal is a fact, done; otherwise, try each rule that concludes it and prove its premises recursively; all(...) stops at the first premise that fails (backtracking). The printed trace reproduces the table of section 7 and shows that only what is relevant to the question has been explored.

Everything above is so regular that there is a programming language whose interpreter is a backward-chaining engine with unification and resolution over Horn clauses: Prolog (1972). The same rules are written almost exactly as in the table, and the query is a question:

We will not run it here (it is not part of the course environment); we mention it because it is the pure example of declarative programming: you describe what is true and the interpreter works out how to prove it. In 07-01 we will compare Prolog with Python and Lisp, and in 06-02 and 06-04 we will see the modern tools (CLIPS, Drools, experta) that inherit these ideas.

Logic is precise, but that precision comes at a price. It is worth knowing its three main limits before building a system with it:

• Closed-world assumption: in our engine, whatever is not among the facts is treated as false. For order 48377 we concluded "no refund applies" because we could not prove that one applied, not because we proved the opposite. In databases and business rules the assumption is convenient (if a product is not recorded as defective, it is not), but it can be dangerous: "there is no record that it is defective" and "we know it is not defective" are different things. Pure logic (sections 2-5) is open-world: if something is not known, nothing is concluded; remember KB2 in section 5.
• Monotonicity: in classical logic, adding knowledge never removes conclusions. But common sense does not work like that: "electronic products have a 3-year warranty" and then "except refurbished ones (1 year)" forces us to withdraw a conclusion once we know more. Expert systems solve it pragmatically with exceptions and priorities between rules (06-02); research on non-monotonic logics is extensive and outside the scope of this course.
• Uncertainty: logic is binary. "The package arrives dented" does not imply with certainty "transport damage": it could also be a picking error with poor packaging. The symptoms of an incident are ambiguous, and forcing them into true/false loses information. The incident diagnosis of case 9 needs precisely degrees of belief, and that is the topic of 06-03: probability, Bayes' theorem and Bayesian networks.

And a practical limitation that belongs not to logic but to the process: someone has to write the rules correctly, maintain them and validate them against cases. That work is called knowledge engineering and it is the heart of the next lesson.

• Confusing the implication with its converse. "If defective then refund" does not license deducing "defective" from "refund". When you write a rule, read its converse out loud too and check that you are not assuming it.
• Thinking that P → Q is false when P is false. A rule is not violated by the cases that do not meet its condition. The only false row of the implication is T → F.
• Writing ∀ with ∧ or ∃ with →. It is the most common syntax error in first-order logic: "for all p, if Product(p) then..." and "there exists p such that Product(p) and...".
• Using truth tables for everything. They are perfect for understanding and for verifying small bases (our entails), but they grow as 2ⁿ. For real bases, Horn chaining or resolution.
• Forgetting the closed-world assumption. If your engine returns "does not apply", ask yourself whether that is "proved not to" or "not proved". For decisions with effects on people (02-04), the latter should lead to "ask more" or to human review, not to a denial.
• Not checking consistency. Our KB of section 5 entailed ¬defective, a sign that two rules clashed on a real case. Run "absurd" queries (does the KB entail that no product is defective?) to catch these clashes before a customer does.
• Ambiguous proposition names. period does not say whether it means "within" or "outside". Use names that are complete, positive statements (within_period, unused): Horn clauses do not allow negations in the premises and you will be grateful for the clarity.

Exercise 1. With truth_table, check whether the following are tautologies: (a) the contrapositive (P → Q) ↔ (¬Q → ¬P); (b) the converse (P → Q) ↔ (Q → P); (c) the hypothetical syllogism ((P → Q) ∧ (Q → R)) → (P → R). Interpret each result with NovaMarket propositions (P: defective, Q: refund applies, R: free shipping).

Exercise 2. Extend the KB of section 5 with the warranty rule as it should be: if it is defective and under warranty, a refund applies (instead of "if it is defective, a refund applies"), and add the fact under_warranty. With entails, check again whether KB ⊨ ¬defective. Has anything changed? What does that tell you about the incompatibility we detected, and what would it take to really resolve it? (No need to program the solution; reasoning it through is enough: it will be done in 06-02.)

Exercise 3. Add to the RULES of section 7 the hygiene products policy: R8 hygiene ∧ opened → not_returnable, and make facts_of generate hygiene and opened from two new keys of the order. Run forward chaining with a NovaSmile electric toothbrush that was opened and returned after 5 days with its label. What does the engine derive? Is it coherent? Explain why this lesson's engine cannot resolve what you see and which mechanism will be needed.

Solution 1. (a) Tautology: all 4 rows are T; "if it is defective a refund applies" is equivalent to "if no refund applies, it was not defective". (b) Not a tautology (satisfiable: it fails when P and Q differ): that a refund applies does not imply that it is defective (it may be withdrawal). (c) Tautology (8 rows, all T): rules chain together; it is the basis for forward chaining being sound: if defective → refund and refund → notice, then defective → notice.

Solution 2. With ("->", ("and", "defective", "under_warranty"), "refund") and the fact under_warranty, entails(KB, ("not", "defective")) still returns True (a single KB model, in which defective is false). Nothing has changed, because the underlying conflict was not the wording of the warranty but that the two rules conclude opposite things (¬refund and refund) about the same used, late, under-warranty, defective order; classical logic cannot hold both and "sacrifices" the possibility of it being defective. Really resolving it requires that one rule prevail over the other (the warranty over withdrawal) or rewriting Diego's rule with an exception (used ∧ over14 ∧ ¬defective → ¬refund), which cannot be expressed directly in Horn clauses (a negated premise). Expert systems do it with priorities and conflict resolution, the topic of 06-02.

Solution 3. With ("R8", ["hygiene", "opened"], "not_returnable") and the order dict(days_since_delivery=5, original_label=True, used=False, defective=False, hygiene=True, opened=True) (and facts_of adding hygiene/opened when those keys are true), the engine derives both refund_applies (via R1, R3, R5: within the period, with its label and "unused") and not_returnable (via R8). It is incoherent: an opened hygiene product must not be refunded under withdrawal. This lesson's engine only adds facts and has no way of saying that R8 blocks R3/R5: Horn clauses have no negation in the premises and no notion of priority. We will need an engine with conflict resolution (priority or specificity: R8 is more specific than R3) and a working memory that records a single decision, which is what we will build in 06-02.

In this lesson we opened the symbolic half of AI with its fundamental tool. We saw why NovaMarket needs explicit, verifiable knowledge for returns (the rules precede the data, and they must be justified and audited); propositional logic with its five connectives and its truth tables, generated with itertools.product; the notions of tautology, contradiction and satisfiability, and the equivalences (De Morgan, contrapositive) that let you rewrite rules without changing their meaning; the inference rules (modus ponens, modus tollens, resolution) that avoid enumeration; logical entailment KB ⊨ α, checked by model enumeration, which also uncovered a clash between Diego's rule and the warranty rule; first-order logic, with which the returns policy is written once for all 12,000 products, and the unification that applies it to each order; and the two working algorithms over Horn clauses, forward chaining (data-driven, forward_chain) and backward chaining (goal-driven, prove), which decided the refund for the NovaBrew coffee maker, the NovaSound headphones and the NovaClean vacuum cleaner with a readable trace. We closed with Prolog and with the limits of logic: closed world, monotonicity and uncertainty.

We now have the minimal engine. What is missing is everything that turns an engine into a system Diego can use: rules with priorities that resolve the conflicts we have left open (warranty versus withdrawal, the opened hygiene product), a working memory, a module that explains "why" and "how", an interface that asks the user for the missing facts and a process to extract the rules from the expert's head and validate them. That is an expert system, the technology that took AI out of the laboratories in the 1980s (MYCIN, XCON, 01-01), and we will build one in pure Python for NovaMarket's returns and warranties in the next lesson, 06-02.