Are parentheses/connectives always necessary in representing expressions built with a single sole sufficient operator

boolean-algebrafoundationslogicnotationpropositional-calculus

The Wikipedia page on the Sheffer stroke provides two ways of simplifying expressions consisting only of the Sheffer stroke:

  1. Removing all occurrences of the logical connective '$\mid$' in the expression so that the concatenation of expressions is taken to be their joint denial, where parentheses are doing the work of grouping (since '$\mid$' is not an associative operation).
  2. Using prefix (or postfix) notation to remove parentheses, but leaving the connective '$\mid$' in the expression.

There is then a sentence describing a way in which both parentheses and connectives can be removed to allow the order of the arguments determine the structure:

  • $p_{1}p_{2}p_{3} \equiv (p_{1} \mid(p_{2} \mid p_{3}))$
  • $p_{1}p_{2}p_{3}p_{4} \equiv (p_{1} \mid (p_{2} \mid (p_{3} \mid p_{4})))$
  • etc.

I can't imagine that any expression in propositional logic can be represented by some concatenation of the propositional variables, but I am not exactly sure how to verify that for any expression in propositional logic there is not an equivalent expression represented by $p_{1}p_{2}…p_{n}$ following the scheme above. This is my initial question.

My question more generally is: how 'economical' can we possibly be with symbols/notation. We know we can reduce a set of connectives down to a sole sufficient operator, and from there we have options like (1) and (2) above. Does it end there? If so, when was this originally discovered?

Thanks for any insight!

Best Answer

First, let's recap:

Consider $$p|(q|r)$$

Since all operators are Sheffer strokes, they can be eliminated, and thus this can be simplified to $$p(qr)$$

On the other hand, using Polish notation, we can eliminate parentheses, and write it as:

$$|p|qr$$

And, using a combination of these two methods, we can get rid of both operators and parentheses, and simply write

$$pqr$$

Now, your (initial) question is: can we, using a combination of these two methods, get rid of all operators and parentheses for any expression?

Your suspicion is No:

I can't imagine that any expression in propositional logic can be represented by some concatenation of the propositional variables, but I am not exactly sure how to verify that for any expression in propositional logic there is not an equivalent expression represented by $p_{1}p_{2}...p_{n}$ following the scheme above. This is my initial question.

Well, you are correct. The answer is indeed No, and here is why:

Consider:

$$(p|q)|(r|s)$$

Sure, we can eliminate all Sheffer strokes, and get: $$(pq)(rs)$$

And, using Polish notation, we can eliminate parentheses, and write it as $$||pq|rs$$

But there is no way to get rid of both parentheses and operators for this expression.

Here is why.

Note that with $p=q=r=s=F$, we have that:

$$(p|q)|(r|s)=(F|F)|(F|F)=T|T=F$$

However, any linear string consisting of any number of of $p$'s, $q$'s, $r$'s, and $s$'s, that represents a Sheffer stroke expression using the 'combination method' as described above will evaluate to $T$ for $p=q=r=s=F$, for the very simple reason that the first variable in that expression is False, and hence this expression always evaluates to

$$F|....=T$$

Related Question