Question

Show that the Sheffer stroke, I, forms a functionally complete set (hint: \(\models \neg \varphi \leftrightarrow \varphi \mid \varphi\) ).

Short answer

The Sheffer stroke is functionally complete as it can express NOT, AND, and OR.

Step-by-step solution

Understanding the Sheffer Stroke

The Sheffer stroke, denoted as \( P \mid Q \), represents the operation of NAND in boolean logic. It equals true in all cases except when both \( P \) and \( Q \) are true. A functionally complete set means any logical expression can be constructed using only this operation.

Expressing NOT using the Sheffer Stroke

We aim to express logical NOT using only the Sheffer stroke. According to the hint, \( \models eg \varphi \leftrightarrow \varphi \mid \varphi \). This means \( eg \varphi \) can be represented by applying the Sheffer stroke to \( \varphi \) with itself: \( eg P \equiv P \mid P \).

Expressing AND using the Sheffer Stroke

The logical AND operation \( P \land Q \) needs to be expressed using only the Sheffer stroke. We can achieve this by using \( (P \mid P) \mid (Q \mid Q) \). This expression first gets the NOT of both \( P \) and \( Q \) and then takes the Sheffer stroke of those: \( eg P \mid eg Q \equiv P \land Q \).

Expressing OR using the Sheffer Stroke

To derive OR, we use \( (P \mid P) \mid Q \). It applies the NOT operation to \( P \) and then uses the Sheffer stroke with \( Q \): essentially \( eg (eg P \land eg Q) \equiv P \lor Q \) derived by De Morgan's laws. Alternatively, \( (P \mid Q) \mid (P \mid Q) \equiv P \lor Q \) using self-application of the Sheffer stroke.

Conclusion on Functional Completeness

Since we can express NOT, AND, and OR using only the Sheffer stroke, it is functionally complete. Any logical operation required in boolean logic can be constructed using the Sheffer operation alone.

Key concepts

Sheffer Stroke

The Sheffer stroke, represented as \( P \mid Q \), is an intriguing logical operation in boolean logic. At its core, the Sheffer stroke is synonymous with the NAND operation. It is a binary operation that yields true unless both operands, \( P \) and \( Q \), are true simultaneously. By capturing this duality, the Sheffer stroke acts as a powerful tool in constructing various logical statements.

• When both inputs are true, the result is false.
• For all other combinations of \( P \) and \( Q \), the result is true.

This characteristic makes the Sheffer stroke a fundamental component in demonstrating the notion of functional completeness.

Boolean Logic

Boolean logic is at the heart of digital systems and computational logic. It employs a mathematical model to represent and manipulate boolean values—true and false. At its core, boolean logic is built on a succinct set of basic operations:

• NOT (negation)
• AND (conjunction)
• OR (disjunction)

To meet the needs of complex computations, any boolean expression can be constructed using these operations, or their equivalent ones, like NAND. This simplicity and flexibility are foundational in computer science, enabling the creation of complex networks and algorithms using basic concepts.

Logical Operators

Logical operators are symbols or words used to connect propositions in boolean logic, creating new propositions with specific logical meanings. Operators serve as the building blocks that allow for the construction of complex boolean expressions. The primary logical operators include:

• AND (\( \land \)): Results in true only if both operands are true.
• OR (\( \lor \)): Results in true if at least one operand is true.
• NOT (\( eg \)): Inverts the truth value of its operand.
• NAND (\( \mid \)): Results in true unless both operands are true.

These operators can be combined and transformed using equivalences and identities in boolean logic, which allows for innovative expressions and optimizations, such as those seen with the Sheffer stroke, underscoring their indispensability in logic and computation.

NAND Operation

The NAND operation is a non-standard yet extremely important logical operation in boolean algebra. Standing for "Not AND" (hence NAND), it is the opposite of the AND operator. Significantly, the NAND operation is functionally complete.

• The output is true unless all inputs are true.
• It can simulate all primary logical operations like NOT, AND, and OR.

To visualize, consider the property \( P \mid P \equiv eg P \), which means you can achieve the NOT operation through a self-combination of the NAND.
Through systems of layered NANDs, one can create robust logical frameworks, making NAND not only fundamental in theoretical computer science, but also vital in practical applications such as the construction of digital circuitry.