Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The question I'm stuck on is:

Let $p$ and $q$ be propositions. A compound proposition $f(p,q)$ is given by $(p\vee \neg q) \Rightarrow (p \Leftrightarrow q)$. Find two non-equivalent propositions $h_1(q)$ and $h_2(q)$ which depend only on $q$, such that both propositions $f(p,q)\vee h_1(q)$ and $f(p,q)\vee h_2(q)$ are tautologies.

I have completed the truth table for the original proposition and have ended up with (T F T T) with both $p$ and $q$; but I'm unsure how to find a proposition where only $q$ is a variable (from what I know there are $4$ nonequivalent propositions for a single variable, I'm just not sure how to combine this information, or whether its right).


share|cite|improve this question

Let us first analyze $f(p,q)$. It says that if $p$ is true or if $q$ is false, then $p$ and $q$ are equivalent. Namely, if $p$ is true then $q$ is true, and if $q$ is false then $p$ is false.

When does that fail? It fails when $p$ is true but $q$ is false. So we need to find two propositions depending only on $q$ such that whenever $q$ is false, they are true.

We can take $h_1(q)=q\lor\lnot q$, which is a tautology, so $f(p,q)\lor h_1(q)$ is also a tautology; and we can take $h_2(q)=\lnot q$, which is true whenever $q$ is false, so again we have that $f(p,q)\lor h_2(q)$ is a tautology. it is clear that the two propositions are non-equivalent because one is always true, and the other can be false.

My general advice for these sort of questions is to understand what does the proposition (in this case $f(p,q)$) mean semantically, and identify when it is false. Then it is not hard to come up with inequivalent propositions which complement it.

share|cite|improve this answer
+1 For finding my brain. I could not read properly and thought $f$ was a free variable. :) – AD. Oct 17 '12 at 11:52
@AD.: It was right under the bouncy castle, I saw it by luck! – Asaf Karagila Oct 17 '12 at 11:52
Thanks! $\,\,\,$ – AD. Oct 17 '12 at 11:59
thanks for your help! i think i was over-complicating it – Z Oj Oct 17 '12 at 12:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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