Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
sav08:propositional_logic_informally [2010/02/22 01:09] vkuncak |
sav08:propositional_logic_informally [2012/02/21 15:09] vkuncak |
||
---|---|---|---|
Line 1: | Line 1: | ||
====== Propositional Logic ====== | ====== Propositional Logic ====== | ||
- | Propositional logic is the core part of most logical formalisms (such as first-order and higher-order logic). It also describes well digital circuits that are the basis of most modern computing devices. In this course we will | + | Propositional logic is the core part of most logical formalisms (such as first-order and higher-order logic). It also describes well digital circuits that are the basis of most modern computing devices. |
- | * review propositional logic informally to make sure everyone is comfortable with it (today) | + | |
- | * define propositional logic formula syntax and semantics formally | + | ===== Importance of Propositional Logic ===== |
- | * learn how to write programs that build, transform, and prove validity of such formulas (SAT solvers) | + | |
- | * use these techniques to build verification tools | + | * 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 126: | Line 129: | ||
Suggest another tautology. | Suggest another tautology. | ||
- | |||
- | ===== 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 | ||
===== More information ===== | ===== More information ===== |