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



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.

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

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.