Appendix B
Glossary
Forgot what a countermodel is, or how a term differs from a formula? Here’s a quick reference to the concepts needed for chapters 1–4 and the notation appendix. The definitions follow our use of the terms; where a choice of logic matters, we’ve said which one we mean.
You can search the terms and their definitions below. For symbols, see the notation table . In the chapters, marked terms show a short definition on hover or keyboard focus; clicking opens the corresponding entry here in a new tab.
Abstract syntax tree (AST)
A tree representing the structure of an expression while omitting grammatical details such as brackets.
Abstraction
Leaving out features of a reasoning scenario that do not matter for the question we are studying.
Adder
A circuit that computes addition on numbers in binary representation.
Affirming a disjunct
The invalid pattern from inclusive A ∨ B and A to ¬B; both disjuncts may be true.
Affirming the consequent
The classically invalid pattern from A → B and B to A.
Algorithm
A precise, step-by-step procedure that takes an input and produces an output in finitely many steps.
Algorithm correctness
An algorithm produces the specified result on its intended inputs; total correctness also requires termination.
Algorithmic undecidability
The absence of an algorithm that terminates with the correct yes-or-no answer on every allowed input to a problem.
Alphabet
A set of symbols from which strings of a formal language are formed.
Ambiguity
An expression is ambiguous if it has more than one possible reading.
Ambiguous grammar
A grammar that generates at least one expression with more than one grammatical structure.
Auxiliary symbol
A symbol used to mark the grammatical structure of an expression, such as a bracket in propositional logic.
Backus–Naur Form (BNF)
Notation for grammar rules, using alternatives to specify how expressions can be built.
Base case
A case handled directly by a recursive definition or procedure, without another recursive call.
Belief revision
Changing the propositions we accept when we receive new information, including information that conflicts with earlier beliefs.
Biconditional
A connective written ↔ and read “if and only if”; in classical logic it is true when its two parts have the same truth-value.
Binary representation
Positional notation with digits 0 and 1, in which position n, counted from the right starting at 0, has place value 2 to the power n.
Bit
A binary digit: either 0 or 1.
Bivalence
The assumption that each formula has exactly one of the two truth-values, true and false.
Boolean evaluation
The extension of a Boolean valuation to all formulas of a propositional language: it keeps the assigned values of variables and interprets ¬, ∧ and ∨ using NOT, AND and OR, respectively.
Boolean function
A function that takes a fixed number of Boolean values, 0 and 1, as inputs and returns one Boolean value.
Boolean identity
An equation between Boolean expressions that holds for every assignment of Boolean values to its variables.
Boolean model
A Boolean valuation of the propositional variables of a language, used to represent a possible reasoning situation. It is a model of a formula when that formula has value 1 under the valuation.
Boolean valuation
A function assigning precisely one Boolean value to every propositional variable of a language.
Boolean value
One of the two values 0 and 1. In logic, they represent false and true, respectively. The Boolean value v(A) of a formula A under a valuation v is determined by the values of its variables and the Boolean functions interpreting its connectives.
Cardinality
The number of elements of a set.
Classical logic
The logical framework used in our Boolean and FOL chapters, with bivalent semantics and classical inference principles.
Complement
The complement W ∖ S contains the objects in a specified universe W that do not belong to S.
Conclusion
The statement being inferred from the premises of an inference.
Conclusion indicator
A word or phrase, such as “therefore”, that signals the conclusion of an inference.
Conditional
An if-then statement. In classical logic, A→B is false exactly when A is true and B is false.
Conditional probability
The probability of one claim given another. Formally, Pr(A given B)=Pr(A∧B)/Pr(B), provided Pr(B)>0.
Conjunction
An and-formula. Classical A∧B is true exactly when both conjuncts are true.
Consistency
A theory is consistent if it does not prove both a statement and its negation.
Contradiction
A formula that is false in every model of the logic under discussion.
Counterexample
A case that shows a claim is false. For an inference, it is a case where the premises are true but the conclusion is false.
Countermodel
A model in which all the premises of an inference are true and its conclusion is not true.
De Morgan laws
The identities NOT (X OR Y) = (NOT X) AND (NOT Y) and NOT (X AND Y) = (NOT X) OR (NOT Y).
Deductive closure
The set of all logical consequences of a set of formulas.
Deductive validity
The impossibility of the premises being true and the conclusion false in the reasoning situations under consideration.
Defeasible inference
An inference whose support can be overturned by additional evidence.
Denotation
The object or function assigned to a term symbol by an interpretation.
Denying the antecedent
The classically invalid pattern from A → B and ¬A to ¬B.
Derivability
The existence of a formal proof of a conclusion from given assumptions, written with ⊢.
Designated value
A truth value counted as acceptable in defining a consequence relation; in K3, only 1 is designated.
Disjunction
An or-formula. Classical A∨B is true exactly when at least one disjunct is true, including when both are.
Disjunctive syllogism
The inference from A ∨ B and ¬A to B, valid classically.
Domain
The nonempty set of objects over which an FOL model interprets names, predicates, functions, and quantifiers.
Effective axiomatization
Specifying the axioms of a theory so that an algorithm can list them all, though the list may be infinite.
Empty string
The string containing no symbols, often written ε.
Entailment
Another name for semantic consequence, written with ⊨.
Enumerative induction
Generalizing from observed instances to a universal claim about a population. The universal claim entails its instances, giving weak logical support; the degree of support and the probability of the conclusion depend on the probability function.
Event
A set of outcomes in a probability space. In our logical treatment, propositions are events.
Exclusive or
The Boolean truth-function XOR, which returns 1 exactly when its two inputs differ.
Existential quantifier
The symbol ∃, used to say that at least one object in the domain satisfies a condition.
Expansion
Adding a formula and all its consequences together with the old beliefs: KB+A=Cn(KB∪{A}).
Explainable AI
Research into making the behavior and results of AI systems understandable.
Extensional definition of a set
Specifying a set by listing its elements.
Read about Extensional definition of a set in Formal languages
Fallacy
An invalid pattern of reasoning that may appear correct.
Formal language
A set of finite strings of symbols from an alphabet.
Formalization
Representing an expression or inference in a formal language.
Formula
An expression formed according to the syntax of a logical language.
Free variable
An occurrence of a variable not governed by a quantifier for that variable.
Full adder
A circuit that adds two bits and an incoming carry, returning a sum bit and an outgoing carry.
Fuzzy predicate
A predicate whose extension assigns degrees in [0,1] rather than just membership or nonmembership.
Grammar
Rules for generating the expressions of a formal language.
Half adder
A circuit that adds two bits, returning a sum bit and a carry bit. The sum is XOR of the inputs and the carry is AND of the inputs.
Idealization
Representing a situation in a simplified form that need not reproduce all its real features.
Identity
Sameness of objects: a=b is true when the two terms denote the same object.
Indefeasible consequence
A consequence that cannot be defeated by adding premises while the semantics remains fixed.
Inductive definition
A definition by initial cases and rules for generating further cases, with nothing else included.
Inductive strength
How strongly the premises support a conclusion without guaranteeing it, given the relevant background information.
Inductive support
Support that premises give a conclusion without guaranteeing it. In probability models, evidence positively supports a conclusion when learning the evidence raises its probability.
Inductive validity
In our weak logical sense, conditioning on the premises never lowers the probability of the conclusion, for any distribution giving the premises positive probability.
Inductive validity (in context)
In the sense used in chapter 1, the premises supporting the conclusion strongly enough to justify accepting it, without making it certain.
Inference
A piece of reasoning from premises to a conclusion.
Inference engine
The part of a reasoning system that applies rules to information in a knowledge base to derive further conclusions.
Inference indicator
A word or phrase, such as “therefore” or “since”, that signals an inference and helps identify its premises or conclusion.
Inference line
A horizontal line separating the premises above it from the conclusion below it.
Inference schema
A pattern of premises and conclusion with placeholders for expressions of specified grammatical categories.
Intersection
The set of elements belonging to every one of the sets being intersected.
Kleene star
For an alphabet Σ, the set Σ* of all finite strings over Σ, including the empty string.
Knowledge base
A collection of represented information used as the starting point for further inference.
Knowledge Representation and Reasoning (KRR)
The study of how to represent information in a form that allows a system to draw conclusions and answer questions.
Read about Knowledge Representation and Reasoning (KRR) in Logic and AI
Likelihood ratio
The probability of the evidence if a conclusion is true, divided by its probability if the conclusion is false. Ratios above 1 favor the conclusion; ratios below 1 count against it.
Log-likelihood ratio
The logarithm of the ratio of the likelihood of the evidence under a hypothesis to its likelihood under the alternative. Positive values favor the first hypothesis.
Logic
The discipline that aims to define and understand valid inference.
Logical consequence
A conclusion is a logical consequence of premises if every model making the premises true also makes the conclusion true.
Logical equivalence
Two formulas are logically equivalent if they have the same truth-value in every model of the logic.
Logical form
The structure of an expression or inference that matters for logical validity, abstracting from its particular subject matter.
Logical inductive support
Support that holds across all probability functions on a fixed model space for which conditioning on the premises is defined, using a specified criterion of support.
Logical law
A general principle of valid inference in a logical system.
Logical operator
A symbol used to form compound expressions, such as negation or conjunction.
Logical proof
A chaining of inference rules applied to logical formulas, with assumptions tracked through the derivation.
Logical space
The collection of models considered by a semantics.
Logical system
A mathematical model of valid inference, typically comprising syntax, semantics, and proof theory.
Logical validity
Validity that depends on logical form, rather than the particular subject matter of the inference.
Material inductive support
Inductive support relative to a particular probability function and a chosen measure of support.
Material validity
Correctness that depends on domain-specific meanings, facts, or assumptions; in inductive reasoning, support relative to a particular probability measure.
Meaning postulate
A statement included among the background assumptions to capture a relationship between the meanings of expressions.
Metavariable
A variable in the language used to talk about another language; for example, A standing for any formula of propositional logic.
Model
A mathematical representation of a possible reasoning situation; a model of premises makes those premises true.
Model checking
Determining whether a formula is true in a specified model.
Modus ponens
The inference from A → B and A to B.
Modus tollens
The inference from A → B and ¬B to ¬A, valid classically.
Negation
A not-formula. Classical ¬A is true exactly when A is false.
Numeral
A written expression representing a number; for example, 120 represents the number one hundred and twenty.
Operator precedence
A convention specifying which operators bind more tightly when brackets are omitted.
Parsing
Reconstructing the grammatical structure of a string according to a grammar.
Premise
A statement from which an inference starts.
Premise indicator
A word or phrase, such as “given that”, that signals a premise of an inference.
Probability
A measure of the chance of an event, given by adding the masses of its outcomes in our finite models.
Probability function
A measure assigning events probabilities between 0 and 1. In a finite space, outcome masses sum to 1 and event probabilities sum the masses of their outcomes.
Probability-raising support
Support measured by the conditional probability of the conclusion given the premises minus its unconditional probability. A positive difference favors the conclusion; a negative difference counts against it.
Proof assistant
Software for constructing formal proofs and checking that their steps obey the rules of the proof system.
Proof theory
The study of formal proofs and the rules by which they are constructed; as a component of a logical system, it models stepwise inference.
Proposition
In this semantic approach, the set of models in which a formula is true.
Propositional variable
A basic symbol representing a proposition in a propositional language.
Pseudocode
A precise description of an algorithm written for readers, using programming-like notation without requiring a complete executable program.
Querying a database
Asking a database for information by specifying what to retrieve and which conditions it must meet.
Recursion
Defining or carrying out a procedure in terms of further calls to that same procedure.
Recursive case
A case handled by applying the same definition or procedure to smaller parts and combining their results.
Rewrite rule
An instruction specifying how one string of symbols may be replaced by another when generating expressions.
Rooted tree
A structure of nodes joined by edges, with a designated root and exactly one path from the root to each other node.
Sample space
The set of possible outcomes of an experiment, written Ω.
Semantics
The component of a logical system that specifies interpretations and truth conditions.
Set
A collection of objects, called its members or elements. Sets are equal when they have exactly the same members.
Set abstraction
Specifying a set by a condition its members satisfy, within an intended domain.
Set difference
The difference S ∖ T contains the members of S that do not belong to T.
Set membership
An object belongs to a set if it is one of its elements, written ∈.
Sound argument
A deductively valid argument with true premises, and therefore a true conclusion. Distinct from soundness of a proof system.
String
A finite sequence of symbols, where order and repetitions matter.
Subset
S is a subset of T when every member of S belongs to T. Equality is allowed.
Substitution
Replacing free occurrences of a variable by a term, while avoiding variable capture.
Syntax
The component of a logical system that specifies which expressions are well formed.
System 1 thinking
Fast, automatic, intuitive and associative thinking, usually requiring little conscious effort.
System 2 thinking
Slow, deliberate and conscious thinking, such as working through a calculation or checking an argument.
Tautology
A formula true in every valuation of the propositional logic under discussion.
Termination
The property that a procedure finishes after finitely many steps on its intended inputs.
Truth-functional completeness
A collection of truth-functions is truth-functionally complete if every Boolean truth-function of positive finite arity can be expressed using those functions.
Truth-value
A value assigned to a formula by a semantics, such as 0 or 1 in classical logic.
Undecidable statement (in a theory)
A statement that can neither be proved nor refuted in the theory under discussion.
Read about Undecidable statement (in a theory) in Logic and AI
Unification
Finding a substitution that makes two expressions syntactically identical.
Union
The union S ∪ T contains every object belonging to S or T, including objects belonging to both.
Unique readability
A property of a grammar: every expression it generates has exactly one grammatical structure.
Universal quantifier
The symbol ∀, used to say that every object in the domain satisfies a condition.
Validity
In the broad sense used in chapter 1, the premises supporting the conclusion in the way required by the kind of inference under discussion.
Verification
Checking that a proposed result meets a stated specification; for an argument, checking a proof or a countermodel in the chosen formal setting.