1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Problem with Propositional Logic

  1. Sep 8, 2012 #1
    Hi,

    I've been set an assignment, part of which is to come up with a formal proof for (p [itex]\wedge[/itex] q) [itex]\Rightarrow[/itex] p. I have to show that the formula is either a tautology or contradiction, or contingent. If it is contingent, I have to show the smallest possible equivalent expression that uses only conjunction, disjunction and negation.

    I'm also only allowed to use the following tautologies:

    (p [itex]\wedge[/itex] p) [itex]\Leftrightarrow[/itex] p
    (p [itex]\vee[/itex] p) [itex]\Leftrightarrow[/itex] p
    (p [itex]\vee \neg[/itex]p) [itex]\Leftrightarrow[/itex] T
    ((p [itex]\vee[/itex] q) [itex]\vee[/itex] r) [itex]\Leftrightarrow[/itex] (p [itex]\vee[/itex] (q [itex]\vee[/itex] r))
    ((p [itex]\wedge[/itex] q) [itex]\wedge[/itex] r) [itex]\Leftrightarrow[/itex] (p [itex]\wedge[/itex] (q [itex]\wedge[/itex] r))
    (p [itex]\vee[/itex] r) [itex]\Leftrightarrow[/itex] (r [itex]\vee[/itex] p)
    (p [itex]\wedge[/itex] r) [itex]\Leftrightarrow[/itex] (r [itex]\wedge[/itex] p)
    (p [itex]\vee[/itex] T) [itex]\Leftrightarrow[/itex] T
    (p [itex]\Leftrightarrow[/itex] p) [itex]\Leftrightarrow[/itex] T
    [itex]\neg[/itex][itex]\neg[/itex]p [itex]\Leftrightarrow[/itex] p
    [itex]\neg[/itex](p [itex]\wedge[/itex] r) [itex]\Leftrightarrow[/itex] ([itex]\neg[/itex]p [itex]\vee[/itex] [itex]\neg[/itex]r)
    [itex]\neg[/itex](p [itex]\vee[/itex] r) [itex]\Leftrightarrow[/itex] ([itex]\neg[/itex]p [itex]\wedge[/itex] [itex]\neg[/itex]r)
    (p [itex]\Rightarrow[/itex] q) [itex]\Leftrightarrow[/itex] ([itex]\neg[/itex]p [itex]\vee[/itex] r)

    My first thought was to use the last tautology in this way:
    (p [itex]\wedge[/itex] q) [itex]\Rightarrow[/itex] p [itex]\Leftrightarrow[/itex] [itex]\neg[/itex](p [itex]\wedge[/itex] q) [itex]\vee[/itex] p
    Firstly, I'm not entirely sure I can even use it in that way, and even if I can, I'm not sure what to do next. I can see that [itex]\neg[/itex](p [itex]\wedge[/itex] q) [itex]\vee[/itex] p always evaluates to true, but I've spend a good few hours on this and still can't see how I can use the above tautologies to prove it.

    Any help with this would be greatly appreciated :)

    EDIT: Nevermind, finally got it :)
     
    Last edited: Sep 8, 2012
  2. jcsd
  3. Sep 17, 2012 #2
    For this kind of problem, you will need to consider setting up the truth assignments. Set up the truth table for each statement and see if both wffs are satisfied on both sides.

    Remember that in order for the statement to be the tautology, both sides must have the same truth assignments, either T or F.

    Also see: http://en.wikipedia.org/wiki/Propos...ves_of_rhetoric.2C_philosophy_and_mathematics

    Hope this helps.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook