The thesis is dedicated to Post's theorem on functional completeness, which falls within the field of mathematical logic. First, we present Post’s classes of logical functions, namely being closed under each of the logical constants, being a counting function, being monotone, and being self-dual. A set of logical functions is complete if every logical function can be expressed using that set. Post's theorem, which we present and prove in this thesis, states that a set $X$ of truth functions is functionally complete if and only if for each of Post's classes, there is a member of $X$ which does not belong to that class.
|
