0

Let $F$ and $G$ be formulas of propositional logic having no atomic proposition in common.

Show: If $F \vee G$ is a tautology, then $F$ is a tautology or $G$ is a tautology.

I have come across this question and am struggling to understand what is needed

If $F \vee G$ is a tautology then \begin{align*} [[F \vee G]] \alpha &= [[F]]\alpha \vee [[G]]\alpha \\ &= 1 \vee 1 \\ &= 1. \end{align*}

I'm not really understanding what to include.

Christoph
  • 24,912
bodwm15
  • 9
  • 4
    The key-point is the fact "having no atomic proposition in common". Consider the tautology $p \lor \lnot p$: neither $p$ nor $\lnot p$ are tautologies – Mauro ALLEGRANZA Jan 19 '21 at 14:38
  • What does "[[F]] alpha" mean? – coffeemath Jan 19 '21 at 14:38
  • 5
    Assume by contradiction that neither $F$ nor $G$ are tautologies. This means that there are valuations $v_1$ and $v_2$ such that $v_1(F)=0$ and $v_2(G)=0$ – Mauro ALLEGRANZA Jan 19 '21 at 14:39
  • The last paragraph of your question is essentially a proof that if $F$ and $G$ are tautologies then so is $F\lor G$. In comparison to what you're supposed to show, you've reversed the direction of the implication and you've changed "or" to "and". – Andreas Blass Jan 19 '21 at 18:34
  • @AndreasBlass Okay I'm not sure how i'd show that – bodwm15 Jan 20 '21 at 16:48
  • @bodwm15 Does $[[F]]_{\alpha}$ mean the value of $F$ in the valuation $\alpha$? – GVT Feb 14 '21 at 14:57

1 Answers1

0

I never seen this notation, but I assume $[[A]]_{\alpha}$ stands for the value of the formula $A$ in the valuation $\alpha$, am I correct?

Since $F$ and $G$ have no atomic propositions in common, assume $p_{1}, ... , p_{n}$ are the atomic propositions in $F$ and $q_{1}, ... , q_{m}$ the atomic propositions in $G$, which satisfy $\{p_{1}, ... , p_{n}\}\cap\{q_{1}, ... , q_{m}\}=\emptyset$.

Now, if $F$ and $G$ are both non-tautologies, as Mauro ALLEGRANZA suggests, take valuations $\alpha$ and $\beta$ such that $[[F]]_{\alpha}=0$ and $[[G]]_{\beta}=0$. And now comes the important part: define the valuation $\nu$ such that $$[[p_{1}]]_{\nu}=[[p_{1}]]_{\alpha}, ... , [[p_{n}]]_{\nu}=[[p_{n}]]_{\alpha}\quad\text{and}\quad [[q_{1}]]_{\nu}=q_{1}]]_{\beta}, ... , [[q_{m}]]_{\nu}=[[q_{m}]]_{\beta},$$ what can be done since all $p_{i}$ and $q_{j}$ are atomic propositions. Since $p_{1}$ through $p_{n}$ are the atomic propositions in $F$, and $\nu$ and $\alpha$ agree in these statements, $[[F]]_{\nu}=[[F]]_{\alpha}=0$; analogously, $[[G]]_{\nu}=[[G]]_{\beta}=0$, meaning that $$[[F\vee G]]_{\nu}=[[F]]_{\nu}\vee[[G]]_{\nu}=0\vee 0=0,$$ what would imply that $F\vee G$ is NOT a tautology, against our hypothesis. By reduction to absurd, we must derive that either $F$ or $G$ is a tautology.

GVT
  • 518