Computational Logic Cheat Sheet

The core ideas of Computational Logic distilled into a single, scannable reference — perfect for review or quick lookup.

PiqCue — piqcue.com/computational-logic/cheatsheet

Quick Reference

Propositional Logic

A branch of logic that deals with propositions (statements that are either true or false) and logical connectives such as AND, OR, NOT, and IMPLIES. It forms the basis for Boolean algebra and digital circuit design.

Predicate Logic (First-Order Logic)

An extension of propositional logic that introduces quantifiers (for all, there exists) and predicates that express properties of objects and relations between them, providing far greater expressive power.

SAT and SMT Solving

SAT (Boolean Satisfiability) solving determines whether a propositional formula can be made true by some assignment of truth values. SMT (Satisfiability Modulo Theories) extends this to richer theories including integers, arrays, and bit-vectors.

Automated Theorem Proving

The use of algorithms and software to prove or disprove mathematical and logical theorems without human intervention. Key techniques include resolution, tableau methods, and superposition calculus.

Logic Programming

A programming paradigm in which computation is expressed as logical inference over a set of facts and rules. Programs are declarative specifications of what should be computed rather than how to compute it.

Curry-Howard Correspondence

A deep isomorphism between formal proofs in logic and programs in typed lambda calculus. Under this correspondence, propositions correspond to types, proofs correspond to programs, and proof normalization corresponds to computation.

Model Checking

An automated verification technique that systematically explores all possible states of a system to check whether a specification expressed in temporal logic holds. It is widely used for verifying hardware and concurrent software.

Type Theory

A formal system in which every term has a type, serving as both a foundation for mathematics and a mechanism for ensuring program correctness. Dependent type theories like the Calculus of Inductive Constructions unify proofs and programs.

Temporal Logic

A family of logics that introduce operators for reasoning about time, such as 'always,' 'eventually,' 'until,' and 'next.' Linear Temporal Logic (LTL) and Computation Tree Logic (CTL) are widely used in verification.

Resolution Principle

A single inference rule for first-order logic introduced by J. A. Robinson in 1965 that is both sound and refutation-complete. It works by deriving the empty clause from a set of clauses to prove unsatisfiability.

Key Terms at a Glance

Automated Theorem Proving:The use of computer programs to prove mathematical or logical theorems without human guidance.

Boolean Algebra:An algebraic structure with operations AND, OR, and NOT over truth values, forming the basis of digital logic and propositional calculus.

Clause:A disjunction of literals used in conjunctive normal form (CNF) representations of logical formulas.

Completeness:A property of a logical system guaranteeing that every valid formula can be derived through the proof rules.

Conjunctive Normal Form (CNF):A standard form for propositional formulas expressed as a conjunction (AND) of clauses, where each clause is a disjunction (OR) of literals.

Decidability:The property of a problem for which an algorithm exists that always terminates with a correct yes or no answer.

Dependent Type:A type whose definition depends on a value, enabling types to express precise program specifications.

Description Logic:A family of knowledge representation formalisms providing the logical foundation for ontology languages like OWL.

Entailment:A semantic relationship where a set of premises logically guarantees the truth of a conclusion in every model.

Epistemic Logic:A modal logic dealing with knowledge and belief operators for reasoning about what agents know or believe.

First-Order Logic:A formal logical system using quantifiers and predicates to express statements about objects and their relationships.

Formal Verification:The process of mathematically proving that a system conforms to its specification.

Horn Clause:A logical clause with at most one positive literal, forming the basis of logic programming languages like Prolog.

Inference Rule:A syntactic transformation that derives new formulas from existing ones while preserving validity.

Lambda Calculus:A formal system for expressing computation based on function abstraction and application, developed by Alonzo Church.

Get study tips in your inbox

We'll send you evidence-based study strategies and new cheat sheets as they're published.

We'll notify you about updates. No spam, unsubscribe anytime.