The simplest logic

Here is a very simple logic. It has two ingredients. Propositional variables and the Sheffer stroke (which, following Peirce, we could call the amphecore). The logic uses Polish notation to express formulae, which is just to say that the syntax rules require the sentences to be ordered (although there isn't a unique ordering because | commutes).

The syntax looks like this. Any propositional variable is well-formed and if p and q are well-formed then |pq is well formed. We can quickly confirm that all well-formed formulae have n propositional variables and n-1 strokes.

The valuation function is likewise simple. V(|pq)=0 iff V(p)=1 and V(q)=1.

Finally, what are some interesting deductive systems for this logic? A simple modus ponens-style inference rule is the following:

|pq,p ⇒ |qq

Nicod gives the following as his single NAND rule of inference.[^1]

||rqp,p ⇒ r

We could use either of these to construct a Hilbert-style axiom system.


Pretty quickly we might get tired of this logic if we're used to thinking in the less sparse language of classical logic. What parts of this logic are equivalent to classical logic?

  • ~p = |pp
  • p∧q = ||pq|pq
  • p∨q = ||pp|qq
  • p→q = ||qqp

Some Tautologies

  • ||ppp
  • |||pr|pq|pr
  • ||||ppq||ppqp

I suspect that there are some interesting relationships between the length of an axiom in this system and the number and arrangement of unique propositional variables. I mess around with this when I'm doodling, but I don't have much else to say about it.

Some speculation:

  • All tautologies have at least one sentence letter that occurs an even number of times. Maybe an odd number of such sentence letters? Maybe exactly one?
  • No tautology exists for ranks |,|||,|||| but one occurs for every other rank.
  • There is an arrangement where the number of | is weakly decreasing and the number of p is weakly increasing.
  • Probably other stuff too!

[^1]: J.G. Nicod, A reduction in the number of primitive propositions of logic, Proc. Camb. Phil. Soc. 19 (1917), 32-41.

researchAdam Edwardslogic