Understanding how to prove either/or type statements in logic 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.
 A: 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.
A: 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.
