Question

The first stage of the method described to "push negations inward" was a method to climinate \(\rightarrow\) 's and \(\leftrightarrow\) 's. Prove that in the method to eliminate them, the process of substituting always stops, Consider, for example, the substitution in the formula $$ (p \leftrightarrow q) \leftrightarrow(r \leftrightarrow s) $$ If the substitution is first performed on the second \(\leftrightarrow\), the resultant formula is $$ ((p \leftrightarrow q) \rightarrow(r \leftrightarrow s)) \wedge((r \leftrightarrow s) \rightarrow(p \leftrightarrow q)) $$ which has more \(\leftrightarrow\) 's to replace than in the original formula! At first sight, one might expect that if the substitutions are made in the wrong order, the process might continue generating more \(\leftrightarrow\) 's at each stage, and the process might continue forever. (Hint: One method is to, instead of just counting the number of \(\leftrightarrow\) symbols, put a weight on each \(\leftrightarrow\) symbol, with the weight of the \(\leftrightarrow\) symbol in \(\psi \leftrightarrow x\) being dependent on the number of \(\leftrightarrow\) 's in \(\psi\) and \(\chi\). If the correct method of calculating weights is used, it can be shown that the total weight of the \(\leftrightarrow\) 's decreases with each substitution.

Short answer

The substitution process will stop as the total weight, which accounts for all equivalences, decreases with each replacement until reaching zero.

Step-by-step solution

Understand the Problem

The task is to show that replacing logical equivalences (\(\leftrightarrow\)) with implications (\(\rightarrow\)) and conjunctions (\(\wedge\)) during the process to "push negations inward" will eventually stop, even if initially additional equivalences appear, as in the example \((p \leftrightarrow q) \leftrightarrow (r \leftrightarrow s)\).

Identify the Substitution Rule

The substitution rule for an equivalence \(\alpha \leftrightarrow \beta\) is to replace it with \((\alpha \rightarrow \beta) \wedge (\beta \rightarrow \alpha)\). This means that each occurrence of an equivalence is replaced with operations that do not involve additional equivalences themselves.

Concept of Weights

Consider each \(\leftrightarrow\) in the expression to have a weight. A sensible method assigns a weight to \(\alpha \leftrightarrow \beta\), which depends on the number of \(\leftrightarrow\)'s in both \(\alpha\) and \(\beta\). Here, let's conceptualize this weight as the sum of total \(\leftrightarrow\) occurrences in \(\alpha\) and \(\beta\) individually before substitution.

Calculating Initial Total Weight

Calculate the initial weight of the original expression \((p \leftrightarrow q) \leftrightarrow (r \leftrightarrow s)\). The original weight before substitution is 3, as there are three \(\leftrightarrow\) relations in total when considered individually.

Effect of Substitution on Weight

After performing a substitution like \((\psi \leftrightarrow \chi)\) becomes \(((\psi \rightarrow \chi) \wedge (\chi \rightarrow \psi))\), the weight of the expression will decrease because each substitution does not introduce more \(\leftrightarrow\)'s, it replaces existing ones with \(\rightarrow\) and \(\wedge\), which are weightless. Therefore, the 'weight' always decreases or at least does not increase after each replacement.

Concluding the Substitution Process

The process of continuously replacing all \(\leftrightarrow\) by \(\rightarrow\) and \(\wedge\) will lead to a reduction in weight until it eventually reaches zero when no further \(\leftrightarrow\) exist in the expression. Hence, even though immediate substitutions might temporarily increase the explicit count of \(\leftrightarrow\), the calculated weight assures the process of substitutions has a definitive endpoint.

Key concepts

Implications

In logic, an implication is a logical operation used to express a relationship where if one statement, considered a premise, is true, then a second statement, the conclusion, also follows as true. This is written symbolically as \( p \rightarrow q \), which reads as "if \( p \) then \( q \)." Here are some important points to understand implications:

• Implications are directional; they do not naturally suggest that \( q \rightarrow p \).
• The only time an implication is false is when \( p \) is true but \( q \) is false.
• Implications are used in logical equivalences to transform complex expressions into simpler forms.

In the process of simplifying logical expressions, implications play a critical role in breaking down equivalences. For instance, an equivalence like \( p \leftrightarrow q \) can be expressed using implications as \( (p \rightarrow q) \wedge (q \rightarrow p) \). This helps in the logical conversion process, where equivalences are replaced with implications, ensuring that expressions become easier to interpret without losing their logical meaning.

Conjunctions

Conjunction is a fundamental operation in logic that combines two statements such that the resultant statement is true only when both individual statements are true. It is symbolized by \( \wedge \) and corresponds to the AND operation in logic. Here are some key aspects of conjunctions:

• Conjunctive expressions, written as \( p \wedge q \), mean "both \( p \) and \( q \) must be true" for the whole expression to be true.
• Conjunctions are used extensively to express conditions and constraints within logical expressions.
• They are crucial in the transformation of logical equivalences, especially when used alongside implications.

In logical equivalences, conjunctions often pair with implications to reform expressions. For example, replacing \( p \leftrightarrow q \) with \( (p \rightarrow q) \wedge (q \rightarrow p) \) uses conjunction to join the two implication statements together. This transformation maintains the logical equivalence of the original expression while allowing for further simplification or analysis within a logical framework.

Substitution Rules

Substitution rules in logic involve replacing parts of an expression with equivalent expressions to simplify or transform the original. This technique is particularly useful for eliminating logical equivalences and introducing implications and conjunctions instead. Here's how the substitution process generally works:

• An equivalence \( \alpha \leftrightarrow \beta \) is replaced by \( (\alpha \rightarrow \beta) \wedge (\beta \rightarrow \alpha) \).
• This new expression doesn't include any equivalence operators, effectively pushing the negations and simplifying the expression.
• Substitution ensures that the logical value of the expression stays intact while potentially rearranging its structure for ease of use or further operations.

By employing a weight concept, substitutions are guided to guarantee that each step effectively reduces complexity rather than increasing it. This is accomplished by ensuring the resulting expression's logical weight, based on the number of equivalences, decreases with every successful substitution. Thus, substitution rules are critical in logical problem solving, enabling a step-by-step reduction of expressions to their simplest form while maintaining correctness.