Logic and proofs: the rules AI reasons by

Propositions, connectives and truth tables, the implication trap, quantifiers and kinds of proof — and why XOR stopped the first neural networks.

14 minutes Matěj Žalmánek 2026-10-15

Series AI basics Part 7 of 52

1. Map of artificial intelligence: what is what and how it all fits together
2. A brief history of artificial intelligence: from Turing to language models
3. Data, model, training, inference: the basic terms on a single example
4. How to read mathematical notation: symbols, indices, sums and quantifiers
5. Sets and relations: the building blocks of definitions in AI
6. Functions and mappings: why every AI model is a function
7. Logic and proofs: the rules AI reasons by
8. Graphs and trees: the structure that both search and neural networks stand on
9. Linear algebra for machine learning: vectors, matrices and why AI mostly multiplies
10. Derivatives, the gradient and the chain rule: how a model finds out which way to learn
11. Gradient descent: how a model learns
12. What probability is: from rolling dice to the Kolmogorov axioms
13. Conditional probability and Bayes’ theorem: how to update your estimate when you learn something new
14. Random variables and the cumulative distribution function: one function that tells you everything about a distribution
15. Probability density and probability mass functions: why a continuous variable has zero probability at a point
16. Expected value, variance and covariance: where a distribution lies, how wide it is and what goes with what
17. Overview of probability distributions: Bernoulli, binomial, Poisson, uniform, normal and exponential
18. Law of large numbers and central limit theorem: why averages behave so predictably
19. Statistics and parameter estimation: maximum likelihood, MAP and confidence intervals
20. Information theory: entropy, cross-entropy and KL divergence — where loss functions come from
21. State-space search: BFS, DFS, UCS and A* with animations
22. Games and adversaries: minimax, alpha-beta pruning and Monte Carlo tree search
23. Constraint satisfaction: backtracking, constraint propagation and AC-3 on sudoku and a map of Czech regions
24. Logic and knowledge systems: forward and backward chaining, resolution and expert systems
25. Planning: STRIPS, the blocks world, heuristics from relaxation and planning in AI agents
26. Local search and simulated annealing: a travelling salesman through the Czech regional capitals
27. Genetic algorithms: population, crossover, mutation and selection on a backpack for a hike
28. Evolution strategies and genetic programming: from the one-fifth rule to Kepler’s law
29. Ant colony optimization: how a pheromone trail finds a short path
30. Particle swarm optimisation: inertia, personal experience and the swarm’s experience
31. Neuroevolution: evolving the weights and shape of neural networks, and the NEAT algorithm
32. Fuzzy sets and membership functions: how to write down “somewhat warm”
33. Fuzzy logic and probability: why “somewhat warm” does not mean “probably warm”
34. Fuzzy logic: t-norms, implications and IF–THEN rules
35. Fuzzy control: Mamdani and Sugeno from a fan to a pole on a cart
36. Fuzzy clustering: the fuzzy c-means algorithm and points between clusters
37. Neuro-fuzzy systems (ANFIS): fuzzy rules that learn from data
38. Markov chains: the transition matrix, the stationary distribution and PageRank
39. Hidden Markov models: the Viterbi algorithm and the dishonest casino
40. Bayesian networks: why the grass is wet and what it means for the sprinkler
41. The Kalman filter: how to estimate where a car is and how fast it goes from imprecise measurements
42. Types of machine learning: supervised, unsupervised, semi-supervised and more
43. Prompts, context and RAG: how to give a model the right information
44. Variational autoencoders (VAE): new images from a continuous latent space
45. Generative adversarial networks (GAN): the forger versus the detective
46. Diffusion models: how pure noise becomes an image
47. Markov decision processes: states, actions, rewards and the Bellman equations
48. Q-learning and DQN: learning the value of actions, from a table to a neural network
49. Policy gradient and PPO: learning the policy directly
50. How an AI agent works: a language model in a loop with tools
51. Programming with AI agents: the task, tests and review
52. Evaluating and securing AI systems: how to measure and how to keep watch

Full series syllabus 52 of 83 topics published

Every definition in this series is a logical statement, and every “therefore” after it is a piece of a proof. Logic is the rules of the game: it tells you when a statement is true and how to correctly derive new statements from true ones. And in artificial intelligence it shows up twice — as the language in which we talk about algorithms, and as a field of its own from which the first “thinking” programs grew.

We first met the symbols ¬, ∧, ∨, ⇒, ∀ and ∃ in the part on mathematical notation. Here you will find out exactly how they work, where people most often go wrong with them and how a proof is built out of them.

1. Propositions and truth values

Definition — proposition

A proposition is a statement (a declarative sentence or a mathematical expression) about which it makes sense to say whether it is true or false, and exactly one of these two possibilities holds. It is a basic notion that logic does not break down any further. The truth value of a proposition A is the number

v(A) ∈ {0, 1},   v(A) = 1 ⇔ A is true,   v(A) = 0 ⇔ A is false.

Let P₁, …, P_n (also P, Q, R, …) be propositional variables — simple propositions whose value we leave open. Compound propositions (formulas) are exactly those that arise by applying the following rules finitely many times:

1. every propositional variable is a compound proposition;
2. if A is a compound proposition, then so is ¬A;
3. if A, B are compound propositions, then so are (A ∧ B), (A ∨ B), (A ⇒ B), (A ⇔ B) and (A ⊕ B).

An assignment of the variables is a function v : {P₁, …, P_n} → {0, 1}. The value of a compound proposition under an assignment v is uniquely determined by the values of its parts according to the truth tables of the logical connectives ¬, ∧, ∨, ⇒, ⇔, ⊕ (next section) — so the truth of a compound proposition depends only on the truth of its parts.

2. Connectives and truth tables

The best way to show how a connective works is a truth table: one row for each combination of the values of P and Q. Two variables have 2 · 2 = 4 combinations, n variables have 2ⁿ.

• Negation ¬P flips the value.
• Conjunction P ∧ Q (“and”) holds only when both parts hold.
• Disjunction P ∨ Q (“or”) holds when at least one holds — or both.
• Implication P ⇒ Q (“if…, then”) fails in only one case: P holds and Q does not.
• Equivalence P ⇔ Q holds when both parts have the same value.
• Exclusive or P ⊕ Q (XOR) holds when exactly one of them holds.

Definition — a connective as a function

Let n ∈ ℕ, n ≥ 1, and let {0, 1}ⁿ = {(p₁, …, p_n) : p_i ∈ {0, 1} for i = 1, …, n} be the set of all n-tuples of zeros and ones. An n-ary logical connective (Boolean function) is a function

f : {0, 1}ⁿ → {0, 1}.

The truth table is its complete definition: one value for each of the 2ⁿ inputs. The connective ¬ is unary, the connectives ∧, ∨, ⇒, ⇔, ⊕ are binary (n = 2, 4 inputs).

Each of the 4 rows can turn out in two ways, so there are exactly 2⁴ = 16 binary connectives — and in general 2²ⁿ n-ary ones (the number of functions from a 2ⁿ-element set to a two-element set, see the part Functions and mappings). The six in the table above are just the ones that have a name of their own.

The values 0 and 1 can be calculated with like numbers: for all p, q ∈ {0, 1}

1. ¬p = 1 − p,
2. p ∧ q = p · q,
3. p ∨ q = p + q − pq,
4. p ⇒ q = 1 − p + pq,
5. p ⇔ q = 1 − p − q + 2pq,
6. p ⊕ q = p + q − 2pq.

Each equality can be checked by substituting all four pairs (p, q) and comparing with the table.

The arithmetic form of “or” is worth breaking down, because it explains why “or” in logic includes both:

p ∨ q = p + q − p · q

p

when P holds, it contributes a one — enough for the whole to be true

q

the same for Q; “or” is happy with either part

p · q

is 1 only when both hold; without subtracting it we would get 1 + 1 = 2, which is not a truth value — we subtract the case counted twice

3. Implication: the most common trap

Definition — converse and contrapositive

Let P, Q be propositions. For the implication P ⇒ Q we define

1. the converse Q ⇒ P,
2. the contrapositive ¬Q ⇒ ¬P.

Theorem. Let P, Q be propositional variables. Then (P ⇒ Q) ≡ (¬Q ⇒ ¬P), but (P ⇒ Q) ≡ (Q ⇒ P) does not hold: under every assignment an implication has the same value as its contrapositive, but there is an assignment under which it differs from its converse (we define logical equivalence ≡ in the section on tautologies).

The table settles it beyond argument: the columns of the implication and the contrapositive are identical, while the converse differs in two rows.

The second trap is the first row, with P = 0: when the premise does not hold, the implication is true whatever Q is. “If 7 is even, I am the Pope” is a true proposition. It sounds odd, but it makes sense — an implication only promises something about the situation where P holds, and that promise cannot be broken when P does not hold.

Both traps disappear when we rewrite the implication using “not” and “or”:

P ⇒ Q ≡ ¬P ∨ Q

P ⇒ Q

the promise “if P, then Q” — we want to know when it is kept

¬P

when the premise does not hold, the promise does not concern the situation, and so it is kept by itself — hence the rows with P = 0

Q

when the premise holds, the promise is kept only if Q really happens

Theorem — an implication is equivalent to its contrapositive (proof without a table)

Theorem. Let P, Q be propositional variables. Then (¬Q ⇒ ¬P) ≡ (P ⇒ Q) and (Q ⇒ P) ≢ (P ⇒ Q).

Proof. By the rewriting A ⇒ B ≡ ¬A ∨ B (breakdown above):

¬Q ⇒ ¬P ≡ ¬(¬Q) ∨ ¬P ≡ Q ∨ ¬P ≡ ¬P ∨ Q ≡ P ⇒ Q.

We used only the rewriting of the implication (twice), double negation ¬¬Q ≡ Q and the fact that the order does not matter for “or”. The converse Q ⇒ P ≡ ¬Q ∨ P is a different expression — for P = 0, Q = 1 it gives 0, whereas P ⇒ Q gives 1. ∎

4. Tautologies and equivalent propositions

Definition — tautology, contradiction, equivalence

Let A, B be compound propositions in the propositional variables P₁, …, P_n, and for an assignment v : {P₁, …, P_n} → {0, 1} let v(A) ∈ {0, 1} denote the value of A under this assignment.

1. A is a tautology (e.g. P ∨ ¬P) if and only if v(A) = 1 for every assignment v;
2. A is a contradiction (e.g. P ∧ ¬P) if and only if v(A) = 0 for every assignment v;
3. A and B are logically equivalent, written A ≡ B, if and only if v(A) = v(B) for every assignment v, i.e. if and only if A ⇔ B is a tautology.

So equivalent propositions have the same column in the truth table. We write A ≢ B when they are not equivalent.

This is how you can check De Morgan’s laws from the part on sets: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q. The columns are identical:

Checking with a table is a simple algorithm — go through all assignments and look for the one that brings the proposition down:

from itertools import product

def je_tautologie(vyrok, n):
    for hodnoty in product([True, False], repeat=n):   # 2**n assignments
        if not vyrok(*hodnoty):
            return False                               # we found a counterexample
    return True

je_tautologie(lambda p, q: (not (p and q)) == ((not p) or (not q)), 2)   # True: De Morgan

Checking a tautology with a table is reliable, but for n variables it means 2ⁿ rows. For 20 variables that is 2²⁰ = 1,048,576 rows, which takes a computer a fraction of a second. For 300 variables it is 2³⁰⁰ ≈ 2.04 · 10⁹⁰ rows — more than there are atoms in the universe (about 10⁸⁰). Even at a billion rows per second it would take 2 · 10⁸¹ s, while the universe is about 4 · 10¹⁷ s old. The question of whether a proposition can be satisfied at all (the SAT problem) is one of the most famous hard problems in computer science.

5. Why XOR stopped the first neural networks

Let us draw the four combinations of P and Q as points in the plane and colour them by the result. For “and” as well as “or”, the green points can be separated from the orange ones by a single line. For XOR it cannot be done — the green points lie on one diagonal and the orange ones on the other:

P ∧ Q

P ∨ Q

P ⊕ Q

The perceptron, the simplest neural network, can only separate points with a line. In 1969 Minsky and Papert showed that this is why it cannot handle even a function as simple as XOR, and interest in neural networks faded for years. The solution is to add a layer: XOR can be composed of simpler functions, (P ∨ Q) ∧ ¬(P ∧ Q), and a two-layer network can do that. This is where the story of deep learning begins.

Definition — perceptron with two inputs

Let w₁, w₂ ∈ ℝ be the weights and b ∈ ℝ the threshold (bias). The perceptron with two inputs and parameters w₁, w₂, b is the function f_{w1, w2, b} : {0, 1}² → {0, 1},

f_{w1, w2, b}(p, q) = 1 if and only if w₁p + w₂q + b > 0; otherwise f_{w1, w2, b}(p, q) = 0.

For (w₁, w₂) ≠ (0, 0) the set {(p, q) ∈ ℝ² : w₁p + w₂q + b = 0} is a line — it divides the plane into a “1” part and a “0” part.

A function g : {0, 1}² → {0, 1} is linearly separable if and only if some perceptron can compute it:

∃w₁, w₂, b ∈ ℝ ∀(p, q) ∈ {0, 1}² : g(p, q) = f_{w1, w2, b}(p, q).

y = [ w₁p + w₂q + b > 0 ]

y

the output 0 or 1 — the perceptron should give the same value as the logical connective

w₁p + w₂q

the weighted sum of the inputs: a weight says how strongly an input “votes” for one

b

the threshold shifts the line — it determines how many votes are needed; without it the line would have to pass through the origin

> 0

the yes/no decision: which side of the line the point lies on

Theorem — XOR is not linearly separable (proof by contradiction)

Theorem. Let XOR : {0, 1}² → {0, 1}, XOR(p, q) = p ⊕ q. Then XOR is not linearly separable, i.e. there are no w₁, w₂, b ∈ ℝ for which f_{w1, w2, b} = XOR.

Proof. Assume, for contradiction, that a perceptron with w₁, w₂, b computes XOR. The four rows of the table give four inequalities:

(0, 0) ↦ 0: b ≤ 0;   (1, 0) ↦ 1: w₁ + b > 0;   (0, 1) ↦ 1: w₂ + b > 0;   (1, 1) ↦ 0: w₁ + w₂ + b ≤ 0.

Adding the middle two: w₁ + w₂ + 2b > 0, so w₁ + w₂ + b > −b ≥ 0. This contradicts the fourth inequality. Contradiction — no such perceptron exists. ∎

A second layer gets around the contradiction. The hidden neuron h₁ computes OR (weights 1, 1, threshold −0.5), h₂ computes AND (weights 1, 1, threshold −1.5) and the output y = [h₁ − h₂ − 0.5 > 0] says “OR, but not AND”. Each of the three neurons is a perceptron; the colours in the table header match the terms of its formula above:

6. Predicates and quantifiers

Definition — predicate and quantifiers

Let M be a non-empty set (the domain of the variable). A predicate (propositional form) on M is a rule P that assigns to every x ∈ M a proposition P(x) — a proposition with a variable that becomes a proposition once an element of M is substituted (e.g. on M = ℤ: P(x) = “x is even”). Equivalently, it is a function P : M → {0, 1}, x ↦ v(P(x)).

1. Universal quantifier: the proposition ∀x ∈ M : P(x) is true if and only if P(x) is true for every x ∈ M, i.e. if and only if {x ∈ M : P(x)} = M.
2. Existential quantifier: the proposition ∃x ∈ M : P(x) is true if and only if P(x) is true for at least one x ∈ M, i.e. if and only if {x ∈ M : P(x)} ≠ ∅.

The order of different quantifiers matters: let M, N be non-empty sets and P(x, y) a predicate on M × N. Then it always holds that

(∃y ∈ N ∀x ∈ M : P(x, y)) ⇒ (∀x ∈ M ∃y ∈ N : P(x, y)),

but the converse implication does not hold in general (counterexample in the box below).

Definitions in AI are full of quantifiers. The admissible heuristic from the part on search is “∀n : h(n) ≤ h*(n)” — and a single state where the estimate overshoots is enough to refute it.

Why a single state is enough is explained by the rule for negating a quantifier — De Morgan’s law for “all” and “exists”:

¬∀x : P(x)  ≡  ∃x : ¬P(x)

¬

the negation “passes” inside — denying the whole statement becomes denying the property for one element

∀x / ∃x

as the negation passes through, the quantifier flips: “not for all” means “for at least one, not” — that is the counterexample

P(x)

the property itself stays the same; only how many elements it concerns changes

On a finite set, quantifiers are just long connectives: for M = {1, 2, 3}, ∀x : P(x) is the same as P(1) ∧ P(2) ∧ P(3) and ∃x : P(x) the same as P(1) ∨ P(2) ∨ P(3). The rule above is then the ordinary De Morgan’s law, just for three terms instead of two.

7. What a proof is

Definition — proof and modus ponens

Let Γ be a set of propositions — assumptions (axioms, previously proven theorems, hypotheses of the statement) — and T a proposition. A proof of the statement T from Γ is a finite sequence of propositions V₁, V₂, …, V_k (k ≥ 1) such that

1. V_k = T (the sequence ends with the statement being proven);
2. for every i = 1, …, k, either V_i ∈ Γ, or V_i arises from some propositions V_j with j < i by applying an inference rule.

The basic inference rule is modus ponens: for any propositions A, B

from A and A ⇒ B one may derive B.

The rule is sound (from true propositions it derives only a true proposition), because (A ∧ (A ⇒ B)) ⇒ B is a tautology.

Example — a proof as a sequence of lines

Assumptions: P (“it is raining”), P ⇒ Q (“if it is raining, it is wet”), Q ⇒ R (“if it is wet, it is slippery”). Statement: R.

1. P — assumption
2. P ⇒ Q — assumption
3. Q — modus ponens from 1 and 2
4. Q ⇒ R — assumption
5. R — modus ponens from 3 and 4 ∎

Every line has a justification that can be checked mechanically: either it is in the list of assumptions, or it refers to two earlier lines of the form A and A ⇒ B.

8. Kinds of proof

Direct proof

From the assumptions we reach the statement step by step. Statement: the sum of two even numbers is even (an integer m is even if and only if ∃a ∈ ℤ : m = 2a). Proof: the even numbers are 2a and 2b for integers a, b. Their sum is 2a + 2b = 2(a + b), that is, twice an integer — an even number. ∎

Proof by contrapositive and by contradiction

Instead of P ⇒ Q we prove the equivalent ¬Q ⇒ ¬P — or we assume the statement does not hold and arrive at nonsense. Statement: there are infinitely many primes. Proof by contradiction (Euclid): if there were only finitely many, p₁, …, p_k, take N = p₁ · … · p_k + 1. No p_i divides N — there is always a remainder of 1. So N has a prime divisor that is missing from the list. Contradiction. ∎

Example — Euclid’s number with concrete primes

For the list 2, 3, 5, 7: N = 2 · 3 · 5 · 7 + 1 = 211. Dividing by 2, 3, 5 and 7 leaves a remainder of 1, and 211 is itself a prime that was not in the list.

For the list 2, 3, 5, 7, 11, 13: N = 30,030 + 1 = 30,031 = 59 · 509. Here N is not a prime — but its prime divisors 59 and 509 are missing from the list. The proof does not claim that N is prime, only that it has a new prime divisor.

Counterexample

A “for all” statement is refuted by a single example. “Every odd number greater than 1 is prime” holds for 3, 5 and 7 — and falls on 9 = 3 · 3. Three examples prove nothing, one counterexample refutes.

Mathematical induction

Definition — principle of mathematical induction

Let ℕ = {1, 2, 3, …} and let P(n) be a predicate on ℕ. If

1. P(1)   (the base case) and
2. ∀n ∈ ℕ : P(n) ⇒ P(n + 1)   (the inductive step)

hold, then

∀n ∈ ℕ : P(n).

The principle is one of the basic properties of the natural numbers (an axiom in Peano arithmetic). It works the same way with a base case at any n₀ ∈ ℤ: from P(n₀) and ∀n ≥ n₀ : P(n) ⇒ P(n + 1) it follows that P(n) for all integers n ≥ n₀.

[ P(1) ∧ ∀n ≥ 1 : (P(n) ⇒ P(n + 1)) ] ⇒ ∀n ∈ ℕ : P(n)

P(1)

the base case — the first domino really falls; without it the step would have nowhere to start

∀n : P(n) ⇒ P(n + 1)

the inductive step — a single implication, proven for a general n, replaces infinitely many individual checks; it is a “chain of modus ponens” 1 → 2 → 3 → …

∀n : P(n)

what we want: the statement for all natural numbers at once

Statement: for all n ∈ ℕ, 1 + 2 + … + n = n(n + 1)/2. The colours match the parts of the induction principle above. Base case P(1): for n = 1 the left side is 1 and the right side is 1 · 2/2 = 1. Step P(n) ⇒ P(n + 1): if the formula holds for n, then 1 + … + n + (n + 1) = n(n + 1)/2 + (n + 1) = n(n + 1) + 2(n + 1)/2 = (n + 1)(n + 2)/2, which is the formula for n + 1. So by the principle of induction ∀n ∈ ℕ : P(n). ∎ The picture shows the same result: two staircases of dots together make an n × (n + 1) rectangle.

For n = 100 the formula gives 100 · 101/2 = 5050 — the result that, according to legend, young Gauss computed by adding up the pairs 1 + 100, 2 + 99, …, 50 + 51: fifty pairs of 101 each.

Definition — loop invariant

Let a loop in a program run k ≥ 0 times, and for j = 0, 1, …, k let I(j) be a statement about the values of the program’s variables after j iterations (I(0) talks about the state before the first iteration). I is a loop invariant if and only if

1. I(0) holds (the invariant holds before the first iteration) and
2. ∀j ∈ {0, 1, …, k − 1} : I(j) ⇒ I(j + 1) (every iteration preserves it).

By induction on the number of iterations j (with base case j = 0), I(j) then holds for all j = 0, …, k, in particular I(k) after the loop ends — and from it we read off the result.

def soucet(n):
    s = 0
    for i in range(1, n + 1):
        s = s + i
        # invariant: s == 1 + 2 + … + i == i * (i + 1) // 2
    return s          # after the last iteration i == n: s == n * (n + 1) // 2

In computer science, induction is used to prove algorithms correct: “after k iterations of the loop…”. This is how you prove, for example, that UCS expands states in non-decreasing order of cost — and therefore finds the cheapest path.

9. Logic in artificial intelligence

• Symbolic AI — the first artificial intelligence systems were logical: knowledge written as “if–then” rules and inference by modus ponens. The expert systems of the 1980s were built on this.
• SAT solvers solve the task “can this proposition be satisfied?” for millions of variables — they plan, verify hardware and find bugs in programs.
• Verifying AI — logic is used to prove properties of systems: that an autopilot never issues two contradictory commands, or that a neural network does not change its decision because of invisible noise.
• Language models and proofs — today’s models can write proofs, which are then checked by formal tools that verify every step mechanically.

Inference in an expert system is modus ponens repeated as long as new facts keep coming — forward chaining. A rule is a pair (premises, conclusion), that is, the implication A₁ ∧ … ∧ A_k ⇒ B:

def dopredne_retezeni(fakta, pravidla):
    fakta = set(fakta)
    zmena = True
    while zmena:                                    # as long as something was added
        zmena = False
        for predpoklady, zaver in pravidla:
            if zaver not in fakta and all(a in fakta for a in predpoklady):
                fakta.add(zaver)                    # modus ponens
                zmena = True
    return fakta

pravidla = [({"rain"}, "wet"), ({"wet"}, "slippery"), ({"slippery", "in a hurry"}, "careful")]
dopredne_retezeni({"rain", "in a hurry"}, pravidla)  # {rain, in a hurry, wet, slippery, careful}

The loop always ends: every iteration with a change adds at least one conclusion, and there are only as many conclusions as there are rules. In the example all three new facts are added already in the first iteration, because the rules are ordered the way they build on each other; the second iteration only checks that nothing was added. With the rules in reverse order there would be three iterations with a change.

10. Summary

• A proposition is either true or false; the connectives ¬ ∧ ∨ ⇒ ⇔ ⊕ are precisely defined by a truth table.
• An implication is equivalent to its contrapositive, not to its converse — and with a false premise it is always true.
• XOR cannot be separated by a single line, and that is why a neural network needs more layers.
• The order of quantifiers matters; a single counterexample refutes a “for all” statement.
• A proof is a chain of verifiable steps: direct, by contrapositive, by contradiction or by induction.

Do you see it differently? Write to support@coden-app.com.