# Is following propositional formula a tautology?

Whether following propositional formula a tautology?

$$(p\iff q) \space \lor \space (p\iff \lnot q)$$.

I think it is not. For contradiction I came up with following interpretation.

$$p(x): \text{x got A grade in math.}$$

$$q(x): \text{x got A grade in english.}$$

Now, in a class where there are students getting $$A$$ in both english and math as well as there are students getting $$A$$ in only one of them. Then above formula fails.

But answer given is that formula is a tautology.

They gives following reasoning for that.

As we know, $$\lnot(p\iff q) = (p\iff \lnot q)$$

and

$$X \lor \lnot X$$ is tautology.

So is $$(p\iff q) \lor \lnot (p\iff q)$$.

So, where I am getting wrong.

The formula in question does not contain quantifiers. It is a truth-functional statements, not a quantificational one. So, you cannot have one world where $$p$$ is true 'for some' but false 'for others' ... there are no 'some' or 'others' here. Instead, for any one world, $$p$$ will be one of true or false, period.

• Can you please elaborate a little more. Nov 14, 2019 at 3:59
• @VimalPatel I just did ... Nov 14, 2019 at 4:00

The point is that your example with grades is about the formula $$(\forall x, p(x) \iff q(x)) \lor (\forall x, p(x)\iff \lnot q(x))$$ but actually you should be looking at $$\forall x, \left( (p(x) \iff q(x)) \lor (p(x)\iff \lnot q(x))\right).$$

Reference for the method I apply here : Mendelson, Schaum's outline of boolean algebra and switching circuits.

In order an OR statement to be false, it is required each member of the disjunction to be false.

Supposse there is a truth value assignment such that your formula is false.

In this assignment, both members are false, so, in particular, the first is false. so we have : ( P <--> Q) is false.

This can happen in two cases : P true and Q false, P false and Q true.

Case 1 : P is true, Q is false; therefore ~ Q is true ; and finally ( P <--> ~Q) is true ( see the truth table of <--> ) ; hence a contradiction, since we initially assumed both members of the disjunction to ba false.

Case 2 : P false , Q true ; therefore ~ Q is false; and finally (P <--> ~Q) is true ; hence again a contradiction for the same reason.

Conclusion : there is no possible truth value assignment in which the formula is false; this formula is a tautology.