5.1 Propositions

5.1.1 Syntax of the Propositional Calculus

A proposition is a sentence, written in a language, that has a truth value (i.e., it is true or false) in a world. A proposition is built from atomic propositions and logical connectives.

An atomic proposition, or just an atom, is a symbol. Atoms are written as sequences of letters, digits, and the underscore (_) and start with a lower-case letter. For example, a, ai_is_fun, lit_l1, live_outside, mimsy, and sunny are all atoms.

Propositions can be built from simpler propositions using logical connectives. A proposition or logical formula is either

  • an atomic proposition or

  • a compound proposition of the form

    ¬p “not p negation of p
    pq p and q conjunction of p and q
    pq p or q disjunction of p and q
    pq p implies q implication of q from p
    pq p if q implication of p from q
    pq p if and only if q equivalence of p and q
    pq p XOR q exclusive-or of p and q

    where p and q are propositions.

The operators ¬, , , , , , and are logical connectives.

Parentheses can be used to make logical formulas unambiguous. When parentheses are omitted, the precedence of the operators is in the order they are given above. Thus, a compound proposition can be disambiguated by adding parentheses to the subexpressions in the order the operations are defined above. For example, ¬abcd¬ef is an abbreviation for ((¬a)(bc))((d(¬e))f).

5.1.2 Semantics of the Propositional Calculus

Semantics defines the meaning of the sentences of a language. The semantics of propositional calculus is defined below. Intuitively, propositions have meaning to someone who specifies propositions they claim are true, and then queries about what else must also be true. An interpretation is a way that the world could be. All that the system knows about the world is that the propositions specified are true, so the world must correspond to an interpretation in which those propositions hold.

An interpretation consists of a function π that maps atoms to {true, false}. If π(a)=true, atom a is true in the interpretation. If π(a)=false, atom a is false in the interpretation. Sometimes it is useful to think of π as the set of the atoms that map to true, and the rest of the atoms map to false.

Whether a compound proposition is true in an interpretation is inferred using the truth table of Figure 5.1 from the truth values of the components of the proposition.

Truth values are only defined with respect to interpretations; propositions may have different truth values in different interpretations.

p q ¬p pq pq pq pq pq pq
true true false true true true true true false
true false false false true false true false true
false true true false true true false false true
false false true false false true true true false
Figure 5.1: Truth table defining ¬, , , , , , and
Example 5.1.

Suppose there are three atoms: ai_is_fun, happy, and light_on.

Suppose interpretation I1 assigns true to ai_is_fun, false to happy, and true to light_on. That is, I1 is defined by the function π1:



  • ai_is_fun is true in I1

  • ¬ai_is_fun is false in I1

  • happy is false in I1

  • ¬happy is true in I1

  • ai_is_funhappy is true in I1

  • ai_is_funhappy is true in I1

  • happyai_is_fun is false in I1

  • ai_is_funhappylight_on is true in I1.

Suppose interpretation I2 assigns false to ai_is_fun, true to happy, and false to light_on:

  • ai_is_fun is false in I2

  • ¬ai_is_fun is true in I2

  • happy is true in I2

  • ¬happy is false in I2

  • ai_is_funhappy is true in I2

  • ai_is_funhappy is false in I2

  • ai_is_funlight_on is true in I2

  • ai_is_funhappylight_on is true in I2.

A knowledge base is a set of propositions that are stated to be true. An element of the knowledge base is an axiom. The elements of a knowledge base are implicitly conjoined, so that a knowledge base is true when all of the axioms in it are true.

A model of knowledge base KB is an interpretation in which all the propositions in KB are true.

If KB is a knowledge base and g is a proposition, g is a logical consequence of KB, or g logically follows from KB, or KB entails g, written


if g is true in every model of KB. Thus, g is not a logical consequence of KB, written KB⊧̸g, when there is a model of KB in which g is false.

Example 5.2.

Suppose KB is the following knowledge base:


Given this knowledge base:


KB does not entail switch_1_is_up as there is a model of the knowledge base where switch_1_is_up is false. The atom someone_is_in_room must be false in that interpretation.

The Human’s View of Semantics

The description of semantics does not tell us why semantics is interesting or how it can be used as a basis to build intelligent systems. The basic idea behind the use of logic is that, when a knowledge base designer has a particular world to characterize, the designer can choose that world as an intended interpretation, choose meanings for the symbols with respect to that world, and write propositions about what is true in that world. When the system computes a logical consequence of a knowledge base, the designer can interpret this answer with respect to the intended interpretation.

The methodology used by a knowledge base designer to represent a world can be expressed as follows:

Step 1

A knowledge base designer chooses a task domain or world to represent, which is the intended interpretation. This could be some aspect of the real world (for example, the structure of courses and students at a university, or a laboratory environment at a particular point in time), some imaginary world (such as the world of Alice in Wonderland, or the state of the electrical environment if a switch breaks), or an abstract world (for example, the world of numbers and sets).

Step 2

The knowledge base designer selects atoms to represent propositions of interest. Each atom has a precise meaning to the designer with respect to the intended interpretation. This meaning of the symbols forms an intended interpretation or conceptualization.

Step 3

The knowledge base designer tells the system propositions that are true in the intended interpretation. This is often called axiomatizing the domain, where the given propositions are the axioms of the domain.

Step 4

A user can now ask questions about the intended interpretation. The system can answer these questions. A user who knows the intended interpretation is able to interpret the answers using the meaning assigned to the symbols.

Within this methodology, the designer does not actually tell the computer anything until step 3.

The Computer’s View of Semantics

A computer does not have access to the intended interpretation. All the computer knows about the intended interpretation is the knowledge base KB. If KBg, then g must be true in the intended interpretation, because it is true in all models of the knowledge base. If KB⊧̸g, meaning g is not a logical consequence of KB, there is a model of KB in which g is false. As far as the computer is concerned, the intended interpretation may be the model of KB in which g is false, and so it does not know whether g is true in the intended interpretation.

Given a knowledge base, the models of the knowledge base correspond to all of the ways that the world could be, given that the knowledge base is true.

Example 5.3.

Consider the knowledge base of Example 5.2. The user could interpret these symbols as having some meaning. The computer does not know the meaning of the symbols, but it can still draw conclusions based on what it has been told. It can conclude that apple_is_eaten is true in the intended interpretation. It cannot conclude switch_1_is_up because it does not know if someone_is_in_room is true or false in the intended interpretation.

If the knowledge base designer tells lies – some axioms are false in the intended interpretation – the computer’s answers are not guaranteed to be true in the intended interpretation.