• Interpretations
  • Equivalence
  • Substitution
  • Models and Satisfiability
  • Validity
  • Logical Consequence (Entailment)
  • Theory

Semantics – Some Informal Definitions

  • Given the truth values of all symbols in a sentence, it can be “evaluated” to determine its truth value (True or False)

  • A model for a KB is a “possible world” (assignment of truth values to propositional symbols) in which each sentence in the KB is True

  • A valid sentence or tautology is a sentence that is True under all interpretations, no matter what the world is actually like or how the semantics are defined (example: “It’s raining or it’s not raining”)

  • An inconsistent sentence or contradictio n is a sentence that is False under all interpretations (the world is never like what it describes, as in “It’s raining and it’s not raining”)

  • P entails Q , written P ⊧ Q, means that whenever P is True, so is Q; in other words, all models of P are also models of Q


  • In propositional logic, truth values are assigned to the atoms of a formula in order to evaluate the truth value of the formula

  • An assignment is a function

    v : P → {T,F}

    v assigns a truth value to any atom in a given formula ( P is the set of all propositional letters, i.e. atoms)
    Suppose F denotes the set of all propositional formulas. We can extend an assignment v to a function

    v : F → {T,F}

    which assigns the truth value v(A) to any formula A in F. v is called an interpretation.

Interpretations (cont’)

  • Example:
    • Suppose v is an assignment for which

    v(p) = F,           v(q) = T.

    • If A = (¬p → q) ↔ (p V q) , what is v(A) ?


      v(A) = v ((¬ p q ) ( p V q ))

              = v p q ) v ( p V q )

              = ( v p ) v ( q )) ( v ( p ) V v ( q ))

              = (¬ v ( p ) v ( q )) ( v ( p ) V v ( q ))

              = (¬F T) (F V T)

              = (T T) (F V T)

              = T T

              = T


  • If A,B are formulas are such that

    v ( A ) = v ( B )

    for all interpretations v , A is (logically) equivalent to B:

    A ≡ B

  • Example: ¬p V q ≡ p → q since both formulas are true in all interpretations except when v ( p ) = T, v ( q ) = F and are false for that particular interpretation

  • Caution : ≡ does not mean the same thing as :

    • A ↔ B is a formula (syntax)

    • A ≡ B is a relation between two formula (semantics)

    • Theorem : A ≡ B if and only if A ↔ B is true in every interpretation; i.e. A ↔ B is a tautology .

Equivalence and Substitution – Examples

  • Examples of logically equivalent formulas

  • Example: Simplify

Models and Satisfiability

  • A propositional formula A is satisfiable iff v ( A ) = T in some interpretation v; s uch an interpretation is called a model for A .

    • A is unsatisfiable (or, contradictory) if it is false in every interpretation

  • A set of formulas U = { A 1 ,A 2 ,…,A n } is satisfiable iff there exists an interpretation v such that v ( A 1 ) = v ( A 2 ) = = v ( A n ) = T; such an interpretation is called a model of U.

    • U is unsatisfiable if no such interpretation exists

  • Relevant properties:

    • If U is satisfiable, then so is U − {Ai} for any i = 1, 2,…, n

    • If U is satisfiable and B is valid, then U U { B } is also satisfiable

    • If U is unsatisfiable and B is any formula, U U { B } is also unsatisfiable

    • If U is unsatisfiable and some A i is valid, then U − {Ai} is also unsatisfiable


  • A is valid (or, a tautology), denoted ⊧ A , iff v ( A ) = T , for all i nterpretations v

  • A is not valid (or, falsifiable), denoted ⊭ A if we can find some interpretation v , such that v(A) = F

  • Relationship between validity, satisfiability, falsifiability, and unsatisfiability:

Validity (cont’)

  • Examples:

    • Valid (tautology):

    • Not valid, but satisfiable:

    • False (contradiction):

  • Theorem:

  • (a) A is valid if and only if ¬A is unsatisfiable

  • (b) A is satisfiable if and only if ¬A is falsifiable

Logical Consequence (i.e. Entailment)

  • Let U be a set of formulas and A a formula. A is a (logical) consequence of U , if any interpretation v which is a model of U is also a model for A :

  • U A

  • Example:

      If some interpretation v is a model for the set

      it must satisfy but in this interpretation, we also have


  • A set of formulas T is a theory if it is closed under logical consequence. This means that, for every formula A , if T A , then A is in T

  • Let U be a set of formulas. Then, the set of all consequences of U

    T ( U ) = { A | U A }

    is called the theory of U . The formulas in U are called the axioms for the theory T(U) .