0

Section 1.3 - Adequate Sets of Connectives

The adequacy of connectives is novel, but I feel it distracts from the potential of variable truth functions. I suffered the section, but I with the exception of naming joint and alternative denail, I can't say I got much from it.

Concepts and Vocabulary

  • Joint Denial: A binary truth function that only returns one when both inputs are zero. $$\begin{array}{c|c|c|c} A & B & A\downarrow B & (A,B)_\mathtt{0x1} \\ \hline 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \end{array}$$
  • Alternative Denial: A binary function that returns one for all input conditions except when both inputs are one. $$\begin{array}{c|c|c|c} A & B & A\big| B & (A,B)_\mathtt{0x7} \\ \hline 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{array}$$
  • Literal: A variable or its negation.
  • Disjunctive Normal Form (dnf): A disjunction of conjunctions.
  • Conjunctive Normal Form (cnf): A conjunction of disjunctions.
  • (Degenerate) Conjunction: A literal.
  • (Degenerate) Disjunction: A literal.
  • Full dnf or cnf: A disjunction of conjunctions where each conjunction contains all the same variables, or a conjunction of disjunctions where each disjunction contains all the same variables.
  • Satisfiable: Not contradictory.
  • Resolution: A complete and total mess.
  • $Res(\mathscr{B})$: A continuation of the pain above.
  • Blatant Contradiction: A variable and its negation in a conjunction.
  • Craig's Interpolation Theorem: If $\mathscr{B}\Rightarrow\mathscr{D}$ and $\mathscr{B}$ and $\mathscr{D}$ have some variables in common, then there exists a $\mathscr{C}$ such that $\mathscr{B}\Rightarrow\mathscr{C}$ and $\mathscr{C}\Rightarrow\mathscr{D}$

Propositions

Proposition 1.5

Every truth function is generated by a statement form involving the connectives $\neg$, $\land$, and $\vee$.

Proposition 1.6

Every truth function can be generated by a statement form containing as connectives only $\land$ and $\neg$, or only $\vee$ and $\neg$, or only $\Rightarrow$ and $\neg$.

Proposition 1.7

The only binary connectives that alone are adequate for the construction of all truth functions are $\downarrow$ and $\big|$.

< Previous