Editing Propositional formula (section)

== Historical development ==
[[Bertrand Russell]] (1912:74) lists three laws of thought that derive from [[Aristotle]]: (1) The [[law of identity]]: "Whatever is, is.", (2) The [[law of noncontradiction]]: "Nothing can both be and not be", and (3) The [[law of excluded middle]]: "Everything must be or not be."
* Example: Here O is an expression about an object's BEING or QUALITY:
*# Law of Identity: O = O
*# Law of contradiction: ~(O & ~(O))
*# Law of excluded middle: (O &or; ~(O))

The use of the word "everything" in the law of excluded middle renders Russell's expression of this law open to debate. If restricted to an expression about BEING or QUALITY with reference to a finite collection of objects (a finite "universe of discourse") -- the members of which can be investigated one after another for the presence or absence of the assertion—then the law is considered intuitionistically appropriate. Thus an assertion such as: "This object must either BE or NOT BE (in the collection)", or "This object must either have this QUALITY or NOT have this QUALITY (relative to the objects in the collection)" is acceptable. See more at [[Venn diagram]].

Although a propositional calculus originated with Aristotle, the notion of an ''algebra'' applied to propositions had to wait until the early 19th century. In an (adverse) reaction to the 2000 year tradition of Aristotle's [[syllogism]]s, [[John Locke]]'s ''Essay concerning human understanding (1690)'' used the word [[semiotics]] (theory of the use of symbols). By 1826 [[Richard Whately]] had critically analyzed the syllogistic logic with a sympathy toward Locke's semiotics. [[George Bentham]]'s work (1827) resulted in the notion of "quantification of the predicate" (1827) (nowadays symbolized as ∀ ≡ "for all"). A "row" instigated by [[Sir William Hamilton, 9th Baronet|William Hamilton]] over a priority dispute with [[Augustus De Morgan]] "inspired [[George Boole]] to write up his ideas on logic, and to publish them as MAL [Mathematical Analysis of Logic] in 1847" (Grattin-Guinness and Bornet 1997:xxviii).

About his contribution Grattin-Guinness and Bornet comment:
: "Boole's principal single innovation was [the] law [ x<sup>n</sup> = x ] for logic: it stated that the mental acts of choosing the property x and choosing x again and again is the same as choosing x once... As consequence of it he formed the equations x•(1-x)=0 and x+(1-x)=1 which for him expressed respectively the law of contradiction and the law of excluded middle" (p. xxviiff). For Boole "1" was the [[universe of discourse]] and "0" was nothing.

[[Gottlob Frege]]'s massive undertaking (1879) resulted in a formal calculus of propositions, but his symbolism is so daunting that it had little influence excepting on one person: [[Bertrand Russell]]. First as the student of [[Alfred North Whitehead]] he studied Frege's work and suggested a (famous and notorious) emendation with respect to it (1904) around the problem of an [[antinomy]] that he discovered in Frege's treatment ( cf [[Russell's paradox]] ). Russell's work led to a collaboration with Whitehead that, in the year 1912, produced the first volume of ''Principia Mathematica'' (PM). It is here that what we consider "modern" propositional logic first appeared. In particular, PM introduces NOT and OR and the assertion symbol ⊦ as primitives. In terms of these notions they define IMPLICATION → ( def. *1.01: ~p &or; q ), then AND (def. *3.01: ~(~p &or; ~q) ), then EQUIVALENCE p ←→ q (*4.01: (p → q) & ( q → p ) ).

* [[Henry M. Sheffer]] (1921) and [[Jean Nicod]] demonstrate that only one connective, the "stroke" | is sufficient to express all propositional formulas.
* [[Emil Post]] (1921) develops the truth-table method of analysis in his "Introduction to a general theory of elementary propositions". He notes Nicod's stroke | .
* Whitehead and Russell add an introduction to their 1927 re-publication of PM adding, in part, a favorable treatment of the "stroke".

'''Computation and switching logic''':
* [[William Eccles (physicist)|William Eccles]] and [[F. W. Jordan]] (1919) describe a "trigger relay" made from a vacuum tube.
* [[George Stibitz]] (1937) invents the binary adder using mechanical relays. He builds this on his kitchen table.
: Example: Given binary [[bit]]s a<sub>i</sub> and b<sub>i</sub> and carry-in ( c_in<sub>i</sub>), their summation Σ<sub>i</sub> and carry-out (c_out<sub>i</sub>) are:
:* ( ( a<sub>i</sub> XOR b<sub>i</sub> ) XOR c_in<sub>i</sub> )= Σ<sub>i</sub>
:* ( a<sub>i</sub> & b<sub>i</sub> ) &or; c_in<sub>i</sub> ) = c_out<sub>i</sub>;
* [[Alan Turing]] builds a multiplier using relays (1937–1938). He has to hand-wind his own relay coils to do this.
* Textbooks about "switching circuits" appear in the early 1950s.
* [[Willard Quine]] 1952 and 1955, [[Edward W. Veitch|E. W. Veitch]] 1952, and [[Maurice Karnaugh|M. Karnaugh]] (1953) develop map-methods for simplifying propositional functions.
* [[George H. Mealy]] (1955) and [[Edward F. Moore]] (1956) address the theory of sequential (i.e. switching-circuit) "machines".
* E. J. McCluskey and H. Shorr develop a method for simplifying propositional (switching) circuits (1962).