Fabian M. Suchanek First Order Logic
Running Example 2 “Hermione married Ron” -> why??? married loves
propositional formula  over a set of atoms   is any of the following •  •  •  •  •  • any element of  •  •  ... where   and   are propositional formulae. Example:  ={smart, heroic, childish, dumb} Def: Propositional Logic 3 (called  conjunction ) (called  disjunction ) (called  implication ) (called  negation ) (called  equivalence ) (We usually omit outer brackets.) NAND>53
propositional formula  over a set of atoms   is either • an element of  • or a formula of the form  This is NAND. It is “true” if at least one of the arguments is “false”. Also known as the “Sheffer Stroke”, and written as “|” We define:  for any  (We usually omit outer brackets.) Digression: Alternative definition 4
Example:    KB={smart, rich} A (propositional)  knowledge base (KB)  over a set of atoms   is a subset  . An  interpretation/valuation/denotation/possible world for a set of atoms A is a function  . Often, the interpretation is given as a KB, with   . (Here, we first talk about only one candidate for Hermione. We will later generalize the definition to the previously known definition of a KB.) (In most of the following, we will see a KB and an interpretation as the same.) Def: Prop. Knowledge Base, Interpretation 5
Example:    KB={smart, rich} Often, the interpretation is given as a KB, with   . (Here, we first talk about only one candidate for Hermione. We will later generalize the definition to the previously known definition of a KB.) (In most of the following, we will see a KB and an interpretation as the same.) Def: Prop. Knowledge Base, Interpretation 6 In the example: A (propositional)  knowledge base (KB)  over a set of atoms   is a subset  . An  interpretation/valuation/denotation/possible world for a set of atoms A is a function  .
We extend the interpretation to propositional formulae by defining Extending Interpretations 7
We extend the interpretation to propositional formulae by defining Extending Interpretations 8
Example:    KB={smart, rich} We extend the interpretation to propositional formulae by defining Extending Interpretations 9 ? ? ?
We extend the interpretation to propositional formulae by defining Extending Interpretations 10 Example:    KB={smart, rich}
Example:    KB={smart, rich} We say: The formula is  true/satisfied  in the KB. We extend the interpretation to propositional formulae by defining Extending Interpretations 11 NAND>61 eqv>62
The usual truth tables follow from this. We extend the interpretation to propositional formulae by defining Digression: Interpretations and NAND 12
A formula   is a  tautology , if for all  . We write  . Examples: Two formulas   and   are  equivalent , if     . Def: Tautology, Equivalence 13
An implication  is equivalent to  . Example:    KB={smart, rich} There is only one case where an implication  is false: if   is true and   is false. Implications 14 ? ? ?
Example:    KB={smart, rich} There is only one case where an implication  is false: if   is true and   is false. Implications 15 An implication  is equivalent to  . details>69
Example: The  law of contraposition  says that an implication can be “turned around”: Implications 16 details>69
Here are some well-known tautological equivalences: • Identity • Domination • Idempotence • Double negation • Commutation • Associativity • Distribution • De Morgan • Absorption • Negation