Understanding how to prove either/or type statements in logic

Question

I've been working my way through a logic textbook and I recently came across this problem:

B and D are statement forms such that B → D is a tautology. Now, if b and d have no statement letters in common, show that either b is contradictory or d is a tautology.

This threw me off completely and I am not exactly sure how exactly to go about approach this. Any hints/help would go a long way.

Answer 1

HINT:

Do this by Contraposition: Show that if $B$ is not a contradiction, and $D$ is not a tautology, then $B \to D$ is not a tautology.

The basic idea is this: If $B$ is not contradiction, then it can possibly be True. More precisely: there is an assignment $v_1$ of truth-values to the variables involved in $B$ that will end upo making $B$ true. Also, if $D$ is not a tautology, then it is possible for it to be False: there is an assignment $v_2$ of truth-values to the variables involved in $D$ that will end up making $D$ False. But, since $B$ and $D$ share no variables, we can combine $v_1$ and $v_2$ into one big truth-value assignment $v$, and since $v$ will set $B$ to True and $D$ to false, this assignment will set $B \to D$ to False, and hence $B \to D$ is not a tautology.

Answer 2

Let $F(w)$ refer to the set of free variables in the wff $w$ . Let $\varepsilon$ refer to the empty set.

You can prove this by borrowing some notation from Łukasiewicz notation. Namely $\Sigma$, the existential quantifier over truth values, and $\Pi$ the universal quantifier over truth values.

For instance.

$ \Sigma a \mathop. a $ is true, since the assigning $a$ the truth value $\top$ produces a true statement. Therefore at least one truth value results in $a$ being true and the whole is expression is true.

$ \Pi a \mathop. a $ is false, since assigning $a$ the truth value $\bot$ produces a false statement. Therefore it is not the case that all of the truth values when applied to $a$ result in a true statement. Therefore $(\Pi a \mathop. a)$ is false.

Our premises are

• $B \to D$ is a tautology
• $F(B) \cap F(D) = \varepsilon$

Let $\{x_1, \cdots, x_n\}$ be equal to $F(B\to D)$ , then our first premise is equivalent to claiming (101). Note that the order in which we quantify over the free variables inside the new wff does not matter.

$$ \Pi x_1 \cdots \Pi x_n \mathop. B \to D \tag{101} $$

Replace the interior expression with an equivalent one.

$$ \Pi x_1 \cdots \Pi x_n \mathop. \lnot B \lor D \tag{102} $$

Let $\{y_1, \cdots, y_m\}$ be equal to $F(B)$ . Similarly, let $\{z_1, \cdots, z_k\}$ be equal to $F(D)$ . Since $F(B)$ and $F(D)$ are disjoint, we can quantify over the $y$ variables first, then the $z$ variables.

$$ \Pi y_1 \cdots \Pi y_m \mathop. \Pi z_1 \cdots \Pi z_k \mathop. \lnot B \lor D \tag{103} $$

None of the $z$ variables appear in $B$, therefore the following transformation is valid.

$$ \Pi y_1 \cdots \Pi y_m \mathop. \lnot B \lor (\Pi z_1 \cdots \Pi z_k \mathop. D) \tag{104} $$

We can rewrite the formula.

$$ \Pi y_1 \cdots \Pi y_m \mathop. (\Pi z_1 \cdots \Pi z_k \mathop. D) \lor \lnot B \tag{105} $$

$ \Pi z_1 \cdots \Pi z_k \mathop. D $ is a constant, therefore the following transformation is valid.

$$ (\Pi z_1 \cdots \Pi z_k \mathop. D) \lor (\Pi y_1 \cdots \Pi y_m \mathop. \lnot B) \tag{106} $$

We can replace the second disjunct with an equivalent expression.

$$ (\Pi z_1 \cdots \Pi z_k \mathop. D) \lor \lnot (\Sigma y_1 \cdots \Sigma y_m \mathop. B) \tag{107} $$

As is desired, either $D$ is a tautology or $B$ is unsatisfiable.