Summaries¶

First-order Logic¶

Language \( \mathcal{L}=(\Gamma,\Omega,\Pi, X) \)
- Constant symbols, Function symbols, Predicate symbols, variable symbols
- Is only syntax
Building blocks of languages: Terms
- Interpreting terms leads to an entity in an universe of discourse
Formulas are the combination of predicates and terms
- Can be quantified and connected
Interpretation \( I=(U,I_C,I_F,I_P) \)
- Universe of discourse
- Constant symbol mapping
- Function symbol mapping
- Predicate symbol mapping
Interpretation is required to evaluate and interpret the individual components of a language
Variable assignment \( \rho \)

Models¶

Set of formulae \( W \)
Model:
- Interpretation \( I \) such that all formulae in \( W \) evaluate to true w.r.t. \( I \)
- If \( W \) has a model, it is called satisfiable
- If \( W \) has no model, it is called unsatisfiable/inconsistent
Semantically equivalent:
- If two formulae always evaluate to the same truth value for any interpretation \( I \), they are called semantically equivalent
Tautology:
- If every interpretation is a model of \( W \), the formulae in \( W \) are called tautologies
- Also called valid
- Notation: \( \models W \)
- Tautologies can be used as transformation rules
Semantic conclusion:
- A formula \( F \) is a semantic conclusion of \( W \) if and only if every model of \( W \) is also a model of \( W \)
- \( W\models F \)
- Test \( W\models F \): Show that \( W\cup\{F\} \) is unsatisfiable
- Testing unsatisfiability is hard due to the unlimited number of possible interpretations
Idea: Herbrand Interpretations
- Only for closed formulae
- Interpret each constant as itself
- Purely symbolic interpretation (worst case scenario)
Clause:
- Disjunction of positive/negative literals
- Horn clauses contain at most one positive literal
- Lemma:
  - Given a set of clauses \( W \)
  - \( W \) has model if and only if \( W \) has a Herbrand Model
  - \( W \) is unsatisfiable if and only if \( W \) has no Herbrand model

Complexity¶

SAT in Boolean logic: Decidable
- For any set of Boolean formulae there is an algorithm testing for satisfiability
- NP-complete
- Algorithm: Davis-Putnam algorithm
- Restricting SAT to Horn clauses is P-complete
SAT in first-order logic: Undecidable
- No algorithm can check satisfiability for any first-order logic formula in finite time
- Semi-decidable algorithms:
  - Algorithm finds out if a formula is unsatisfiable
- Restrict FOL to decidable subset:
  - Schönfinkel-Barnays class
  - NEXP-complete

Datalog¶

Implementation of a logical programming language
Restricted to Horn clauses
- Fact horn clauses: Extensional DB
- Definite horn clauses: Rule
- Goal horn clauses: Query
Datalog classification:
- Datalog
- Datalog-neg
- Datalog-f
- Datalog-f-neg
Problem: Programs with cyclic negations
- Program must be rejected (program will not end)
- Detection: Stratification
Semantics:
- Least, minimal, perfect Herbrand model
- Herbrand interpretation
  - Herbrand interpretation satisfying the Datalog program is a model
  - Problem: it is not easy to compute a model
  - Multiple models exist: Which is the intended semantics?
Datalog-f:
- Computationally complete
- Intended semantic: Least Herbrand Model
- Least Herbrand model is the intersection of all Herbrand models
- It does not contain superfluous statements
- Operational semantics:
  - Computation of the LHM, use fixpoint iteration
  - Start with empty set of ground atoms
  - Iteratively, refine the set
  - Monotonous process (only expanded)
  - Method is finite for Datalog-f
  - Result: Least Herbrand Model
- Iteration step: Elementary production rule
  - Apply given rules with premises contained in the set of the previous step
Datalog-neg:
- Provide natural modeling
- Datalog-neg is potentially unsafe (infinite large models)
- Datalog-neg is potentially ambiguous (multiple distinctive models possible)
- Multiple minimal models
- Address ambiguity:
  - Assume negation as failure
  - Non-provided fact is false
  - ==Is this the same as the Closed World Assumption?==
- Address Safety:
  - Positive grounding
  - Each variable appearing in a negative clause must appear in a positive clause
  - This restricts the evaluation to known facts
- Deterministic choice of models:
  - Perfect model w.r.t. to preference relation
  - Perfect model is the intended semantics
- Operative semantics:
  - Iterated fixpoint iteration
  - Apply fixpoint iteration on every stratum
Fixpoint iteration and iterative fixpoint iteration are very inefficient
Datalog to RelAlg:
- Merge Datalog-style reasoning with techniques of relational databases
- Elementary production rule can be implemented in relational algebra
- Bottom-up approach:
- Top-down approach:
  - Start with query, construct a proof tree down to the facts
  - Construct search trees by their depth
  - Search tree: Parameterized proof tree
  - Backwards-chaining
  - Stopping? Maximal chain
Magic Sets:
- Logical rewriting
- Query is part of program
- Determine the reachable adorned system
  - Observe which terms are distinguished and propagate the resulting adornments
  - Contains adorned predicate occurrences
- Determine the magic set
  - using magic rules and magic predicates
  - Restricted/modified rules use only the constants from their respective magic set

RDF¶

Markup language to encode knowledge
Knowledge in triples
URI represents entity or concept
RDF document represents graphs of labeled nodes and edges
RDF has not restriction of the used labels
RDF-S defines valid resources
- Define vocabulary for RDF graphs
- Define classes and properties
- Contains pre-defined relationships (e.g., sub-classes, sub-properties, ranges, domains)