Saltar al contenido ForoHackers

Logic in computer science: start here

Lógica en informática
#899 · Ophuscado · · Denunciar

Logic gives computing a precise language for statements and proofs. Programs, specifications, type systems, databases and circuits can all be described in it, and checked by machine. It is the basis of SAT and SMT solvers, proof assistants, query languages and the verification of software and hardware.

Key concepts

  • Propositional logic: statements joined by and, or, not and implies; truth tables and normal forms decide them.
  • First-order logic: adds variables, predicates and quantifiers to talk about objects and their properties.
  • Proof systems: natural deduction and resolution give rules that derive conclusions step by step.
  • Soundness and completeness: what a proof system proves is true, and everything true is provable, for the right logics.
  • Satisfiability: finding an assignment that makes a formula true; it is NP-complete, yet modern solvers handle huge instances.

Vocabulary

  • Model: an interpretation in which a formula is true or false.
  • Validity and satisfiability: true in every model, or true in at least one.
  • Unification: finding a substitution that makes two terms equal, the heart of Prolog.
  • Temporal logic: logic with operators such as always and eventually, used to specify system behaviour.

What to study, in order

  1. Truth tables, equivalences and conjunctive normal form by hand.
  2. Write a small SAT solver with unit propagation and backtracking.
  3. Prove simple theorems by natural deduction and by resolution.
  4. First-order logic: translate English statements, then try a SMT solver on a puzzle.
  5. Learn temporal logic and use it to state a property of a protocol.

Related tags

#formal-methods #type-theory #databases #knowledge-representation

Inicia sesión o únete para responder.