Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
sav08:propositional_logic_informally [2008/03/04 21:02] david |
sav08:propositional_logic_informally [2010/02/22 13:59] vkuncak |
||
---|---|---|---|
Line 6: | Line 6: | ||
* learn how to write programs that build, transform, and prove validity of such formulas (SAT solvers) | * learn how to write programs that build, transform, and prove validity of such formulas (SAT solvers) | ||
* use these techniques to build verification tools | * use these techniques to build verification tools | ||
+ | |||
+ | ===== Importance of Propositional Logic ===== | ||
+ | |||
+ | * Many search problems can be encoded using propositional formulas | ||
+ | * Checking equivalence of logical combinatorial circuits in hardware directly reduces to SAT | ||
+ | * Can encode integer arithmetic with fixed bitwidth (e.g. operations on 16-bit integers) | ||
+ | * An important class of logics can be obtained by giving meaning to propositional variables | ||
===== Propositional Formulas ===== | ===== Propositional Formulas ===== | ||
Line 127: | Line 134: | ||
Suggest another tautology. | Suggest another tautology. | ||
- | ===== Importance of Propositional Logic ===== | + | ===== More information ===== |
- | * Many search problems can be encoded using propositional formulas | ||
- | * Checking equivalence of logical combinatorial circuits in hardware directly reduces to SAT | ||
- | * Can encode integer arithmetic with fixed bitwidth (e.g. operations on 16-bit integers) | ||
- | * An important class of logics can be obtained by giving meaning to propositional variables | ||
- | |||
- | ===== More information ===== | ||
- | * forthcoming lectures | ||
* [[Calculus of Computation Textbook]], Chapter 1 (for now especially Sections 1.1, 1.2, 1.3) | * [[Calculus of Computation Textbook]], Chapter 1 (for now especially Sections 1.1, 1.2, 1.3) | ||
* [[:Gallier Logic Book]], Sections 3.1, 3.2, 3.3 | * [[:Gallier Logic Book]], Sections 3.1, 3.2, 3.3 | ||
+ |