Notes - Logic and Proof MT24, Boolean circuits
Flashcards
Can you @define a boolean circuit/straight-line program over a set of propositional variables $p _ 1, p _ 2, \ldots, p _ n$.
A finite sequence of definitions $\alpha _ 1 := E _ 1$, …, $\alpha _ m := E _ m$ where each $E _ i$ is an expression of the form:
- $\mathbf{true}$
- $\mathbf{false}$
- $F \land G$
- $F \lor G$
- $\lnot F$
and where $F$ and $G$ are drawn from the set of input variables or preceding program variables $\alpha _ 1, \ldots, \alpha _ {i-1}$.
Can you @define what it means for a boolean circuit/straight-line program to be monotone?
It does not use negation.