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/02/19 18:46] vkuncak |
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 83: | Line 90: | ||
| for all values of its parameters. Let us draw formula as a tree. We introduce a column for each tree node. We obtain the value of a tree node by looking at the value of its children and applying the truth table for the operation in the node. The root gives the truth value of the formula. | for all values of its parameters. Let us draw formula as a tree. We introduce a column for each tree node. We obtain the value of a tree node by looking at the value of its children and applying the truth table for the operation in the node. The root gives the truth value of the formula. | ||
| - | ===== Validity, Satisfiability ===== | + | ===== Validity, Satisfiability of Logical Formulas ===== |
| Formula is //valid// if it evaluates to //true// for //all// values of its variables (all columns for formula say //true//). | Formula is //valid// if it evaluates to //true// for //all// values of its variables (all columns for formula say //true//). | ||
| Line 98: | Line 105: | ||
| **SAT** is a well-known NP-complete problem. | **SAT** is a well-known NP-complete problem. | ||
| + | |||
| ===== Propositional Tautologies ===== | ===== Propositional Tautologies ===== | ||
| Line 106: | Line 114: | ||
| \[\begin{array}{l} | \[\begin{array}{l} | ||
| - | (p \rightarrow q) \leftrightarrow (p \lor (\lnot q)) \\ | + | (p \rightarrow q) \leftrightarrow ((\lnot p) \lor q) \\ |
| - | (p \leftrightarrow q) \leftrightarrow ((p \rightarrow q) \land (r \rightarrow p)) \\ | + | (p \leftrightarrow q) \leftrightarrow ((p \rightarrow q) \land (q \rightarrow p)) \\ |
| (p \land q) \leftrightarrow (q \land p) \\ | (p \land q) \leftrightarrow (q \land p) \\ | ||
| (p \land (q \land r)) \leftrightarrow ((p \land q) \land r)) \\ | (p \land (q \land r)) \leftrightarrow ((p \land q) \land r)) \\ | ||
| Line 126: | 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 | ||
| + | |||