Skip to the content ForoHackers
Log inJoin

Logic in computer science: start here

Logic in computer science
#3405 · · Quote · Report

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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply