0
$\begingroup$

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.

$\endgroup$

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Can you please elaborate a little more. $\endgroup$ Nov 14, 2019 at 3:59
  • $\begingroup$ @VimalPatel I just did ... $\endgroup$
    – Bram28
    Nov 14, 2019 at 4:00
2
$\begingroup$

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).$$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.