Which one of the following is a tautology?
We want to know which of the given compound statements is a tautology, that is, which statement is always true no matter which truth-values (T or F) we assign to the simple propositions and . The straightforward way is to construct truth-tables for every option, but often we can save time by using well-known logical equivalences. Nevertheless, for absolute clarity we shall give every algebraic step and also exhibit at least one counter-example for all the non-tautological options.
First recall some standard logical facts that we shall need:
1. Implication equivalence (Because an implication is false only when is true and is false.)
2. Distributive, associative, commutative and absorption laws for (OR) and (AND) behave exactly like their algebraic counterparts, but with the understanding that TRUE behaves like 1 and FALSE like 0.
3. The absorption laws that we shall use twice are These tell us that mixing a statement with itself inside an OR or an AND does not add any new logical content: already captures the whole truth of the compound.
Now we treat every option one by one.
Option A :
We start by rewriting the implication inside the antecedent () using fact 1.
So,
Substituting this inside the main expression gives
Next we simplify the bracket by distributing over the parentheses:
But is always FALSE (a contradiction), hence
because OR with FALSE leaves the other term unchanged.
So up to now we have reduced the whole statement to
Once again we use fact 1 on the outer implication, i.e.
We apply De Morgan to the negation:
so the expression becomes
OR is associative and commutative, therefore we can rearrange freely. We now gather the two clauses that contain :
because is always TRUE. And of course simplifies to TRUE (OR with TRUE is TRUE).
Thus the entire compound statement has simplified to the constant truth-value TRUE for every truth assignment to and . Therefore option A is a tautology.
Option B :
Again write as and substitute:
As in option A we know that So we obtain
This implication is equivalent to Now choose a valuation with and Then and , so the whole expression evaluates to FALSE. Hence option B is not a tautology.
Option C :
Using the absorption law stated earlier, we get directly
The value of obviously depends on our choice of truth-values; it is TRUE for and FALSE for . Therefore this compound statement sometimes becomes FALSE, so it is not a tautology.
Option D :
This is the other absorption law:
Again the truth of the whole expression varies with the truth of , so option D is not a tautology.
After examining every choice we see that only option A is always TRUE, i.e. is a tautology.
Hence, the correct answer is Option A.
Tagged Logical connectives, truth tables and tautologies. Machine-assigned, so read it as a strong shortlist rather than a verdict.