Mind Map of knowledge representation and reasoning with logic [coggle]

  1. Propositional Logic (also Propositional Calculus)
  • The simplest logical system, both with respect to syntax as well as semantics
  • Limited to use of propositions – finite declarative sentences (statements), being either true or false   
  • The alphabet consists of a set of propositional symbols; a set of logical connectives; parentheses used if necessary; and possibly two special symbols denoting a formula is always true (tautology) or always false (contradiction)
  • Respecting a Syntax, we get a well-formed formulae (wff) which makes it possible to interpret (Semantics), based on evaluation of all used symbols. 
  • Propositional formulae can be transformed from the initial form to another one using various transformation rules. Specific forms of well-formed formulae are Conjunctive Normal Form (CNF) and Disjunctive Normal Form (DNF).  
  • One formula can be a logical consequence of another formula (or a set of formulae).  The concept of logical consequence is of primary importance in the whole logic. 
  • Having a knowledge base, there are various modes of reasoning. The classical modes of logical inference are: deduction, abduction, induction. Reasoning becomes  inference if it is performed according to a specific scheme. Deduction is the best known method of logical inference here (e.g., modus-ponens scheme). One of the most attractive rules is a resolution rule. 
  • PL can be used for several generic tasks: theorem proving, tautology or completeness verification, minimization of propositional formulae [ligeza].    

Mind Map of Logic [coggle]

An example: The PL-based knowledge representation [cs3793] 

  1. First-Order Logic (FOL): also Predicate Calculus 
  • The most popular logical system, an extension of the propositional logic
  • Unlike PL, it has sufficient expressive power (admission of individual variables, terms and quantifiers, predicates – properties or relations among some objects which are the arguments of them)
  • The alphabet consists of symbols denoting objects, functions and relations, logical connectives, quantifiers, and auxiliary elements, like parentheses and comma
  • Variables may be used to denote unknown but specific objects; any functional and predicate symbol have assigned a constant number of argument they operate on (arity).
  • The notion of term is introduced, to make representation of various complex data structures possible; formulae are constructed in an analogous way to propositional logic, including analogical definitions of CNF a DNF
  • Formulae can be consistent (satisfiable), inconsistent (unsatisfiable) or valid in all their interpretations (tautologies)
  • The key concepts used during the inference process are substitution, unification (unification algorithm), transformation of the original set of formulae into the so-called clausal form. As in propositional logic, the resolution rule is very attractive, constituting a single and powerful inference rule

An example: The FOL-based knowledge representation [russel]

Literature

  1. [coggle] The Coggle Gallery – the mind maps gallery https://coggle.it/gallery 
  2. [ligeza] Ligęsa, A., Logical foundations for rule-based systems. Studies in Computational Intelligence (2nd ed.), vol. 11, Springer, 2006
  3. [cs3793] Logical Inference. CS 3793/5233 Artificial Intelligence http://www.cs.utsa.edu/~bylander/cs3793/notes/logic.pdf
  4. [russel] Russell, S.J. and Norvig, P., 2002. Artificial Intelligence-A Modern Approach, Second International Edition.