Expressive completeness of a logical language
Some collections of logical connectives are able to express all the others—they are expressively complete.
We say that a collection of logical connectives in propositional logic is expressively complete (also known as expressively adequate), if those connectives are able to express all logical truth functions of any positive arity.
Let us explore various complete and incomplete sets of connectives, and the various reasons a language may be incomplete: it may be T-preserving, F-preserving, monotone, affine, or self-dual. Eventually, we shall organize the various sublanguages of propositional logic into a hierarchy of expressivity.
Keep reading with a 7-day free trial
Subscribe to Infinitely More to keep reading this post and get 7 days of free access to the full post archives.