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

Question

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!

Answer 1

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$$