SEMANTICS
Semantics
 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
Interpretations

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) ?
Solution:
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
Equivalence

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

Solution:
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
Validity

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
Theory

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) .