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

Creator: OlliG

Contributors:
soeren (TIB)

Licensed under the Creative Commons
Attribution ShareAlike CC-BY-SA license

This deck was created using SlideWiki. 