Deductive System

A Deductive System consists of

• One or more initial objects
• One or more deduction rules

Propositional Logic

doesn’t have quantifiers, or “First Order Logic”

• Propositional Variables: basic statements that can be either true or false, like $p, w, r, x_1, x_2, x_3$
• Connectives:
  • Not $\neg$
  • And $\wedge$
  • Or $\vee$
  • Implies $\rightarrow$
  • If and Only if $\leftrightarrow$

formula: Connectives and P.V.
well-formed formula:

• Initial: Any variable
• Deduction Rules: From $A$, can obtain $\neg A$. From $A, B$, can obtain $A\vee B$, $A\wedge B$, $A\rightarrow B$, $A\leftrightarrow B$.

A formula is a binary tree in which:

• 2-child nodes are labeled by binary ops
• 1-child nodes are labeled by unary ops
• 0-child nodes are labeled by variables

Truth Assignment V: setting of true and false for each variable
Given a formula $S$, its truth value $V[S]$ can be defined by structural induction

Satisfiability:

• $V$ satisfies $S$: $V[S] = T$
• $S$ is satisfiable: $\exists V$ such that $V[S] = T$
• $S$ is unsatisfiable: $\forall V, V[S] = F$
• $S$ is tautology: $\forall V, V[S] = T$

Equivalent: Formulas $R$ and $S$ are equivalent, $R \equiv S$ if $\forall V, V[R] = V[S]$.
Entailment: Formulas $A_1, …, A_m$ entail formula $S$, written $A_1, …, A_m \models S$ if every truth assignment which makes $A_i$ true makes $S$ true.
Truth table: It represents a Boolean function, $f: {0, 1}^n \rightarrow {0, 1}$.

• There are $2^{2^n}$ truth tables on n variables.
• Every truth table can be computed by some formula, only using $\neg, \vee, \wedge$

Circuits

• In circuits, nodes (gates) may have fan-out > 1.
• Formulas are trees: all nodes have fan-out 1.
• Circuits can reuse already-computed pieces. Formulas cannot; everything must be “rebuilt”.
• Deduction viewpoint: The circuit is the deduction. The formula is the last line.