Checking Functional Completeness in Propositional Logic

When working with propositional logic, it is essential to determine whether a given set of logical operators is functionally complete. This article explores how to check if a specific set of operators is functionally complete, along with a detailed example. Let's dive into the concept and steps involved.

Understanding Functional Completeness

A set of logical operators is considered functionally complete if it can be used to express all possible truth functions. In other words, any logical operation can be constructed using these operators. The three fundamental operators for functional completeness are:

Negation (#92;): The ability to reverse the truth value of a proposition. Conjunction (#8743;): The logical AND operator, which outputs true only if both propositions are true. Disjunction (#8744;): The logical OR operator, which outputs true if at least one proposition is true.

Checking a Specific Set of Operators

Let's consider the set of logical operators:

{ #8743;, #8596;, #8744; }

These operators represent:

AND (#8743;): Logical AND Biconditional (#8596;): Logical Biconditional (if and only if) OR (#8744;): Logical OR

To determine if this set is functionally complete, we must follow a systematic approach:

Step 1: Understand Functional Completeness

We need to verify if the given set of operators can express the following:

Negation (#92;) Conjunction (#8743;) Disjunction (#8744;)

Step 2: Check Basic Operators

Negation

First, we need to check if negation can be expressed using the given operators. The biconditional operator (#8596;) can be used to create negation:

eg A equiv A leftrightarrow text{False}

However, since we cannot express #92; without an external constant like text{False}, this step is incomplete.

Conjunction and Disjunction

Both #8743; and #8744; are already present in the given set, so no further action is needed for these.

Step 3: Evaluate Combinations

Even though #8743;, #8596;, and #8744; are present, we still need to check if we can express all possible combinations and truth tables. As mentioned, the biconditional operator alone cannot create negation without a constant. Therefore:

We cannot construct negation using only #8743;, #8596;, and #8744;. Without negation, it is impossible to create any other operator, which is crucial for functional completeness.

Making a Known Functionally Complete Set

A simple test for functional completeness involves checking if a known functionally complete set of connectives can be derived from the given ones. Let's use the NOR operator, which is a known functionally complete set:

NOR (A, B) equiv (A land B) leftrightarrow text{False}

However, as shown in the first row of the truth table, all of the given connectives output T but we require an F. Since we don't have any negation connective, any combination of the three given connectives will result in a T when both schemas p and q are T. Therefore, the NOR operation cannot be realized using the given set.

This kind of 'disproving' test does not need a singleton functionally complete set like NOR. If we substitute any proposition in the final column that has an F in the first row, the fact still remains that it cannot be realized for the same reasons mentioned above.

Hence, the given set is not functionally complete.

Final Conclusion

To summarize, the set:

{ #8743;, #8596;, #8744; }

is not functionally complete because we cannot express negation or create constants like #92; using only these operators.

We encourage anyone working with logic to understand the concept of functional completeness and apply these steps to verify the completeness of any given set of operators. If you have any further questions or need clarification, feel free to ask!