4
$\begingroup$

I have two homework questions that I've been struggling with. For the first I need to prove that

$((p \lor q) \land (\lnot p \lor r)) \to (q \lor r)$

is a tautology.

I've tried two approaches. First I tried substituting other logically equivalent statements for the propositions on the LHS. Once that failed, I tried assuming that the LHS is true and I tried to show the RHS must also be true. I wasn't able to do that either. There is nothing saying I can't use a truth table, but I'd prefer not to. Any help would be appreciated.

The second question is to decide whether

$\forall x \exists y(P(x) \to P(y)) \to \exists y \forall x(P(x) \to P(y))$

is logically valid or not. Does logically valid mean tautology? If so, I don't even know where to start.

EDIT: This question originally asked to prove the second expression as true, which was incorrect.

  • 1
    The reading order of the first proposition is unclear, could you add parenthesis to clarify what is connected by the implication?2012-01-16
  • 0
    I've added the parenthesis, although it should have been clear simply from precedence.2012-01-16
  • 0
    Do you have any sort of proof system at hand here? If you do, you could show the first proposition a theorem, and then invoke soundness.2012-01-17
  • 0
    @gsingh2011: Unfortunately there is no universally observed convention for what the precedence rules for logical connectives are. Unless one is working within a particular context where specific rules have explicitly been adopted, it is recommended to err on the side of too many parentheses.2012-01-17
  • 0
    @HenningMakholm I don't see how you can err on the side of too many parentheses to begin with. After all, if you fully parenthesize a statement, you end up writing the actual wff instead of a shorthand for one.2012-01-17

4 Answers 4