1. Not finding help here? Sign up for a free 30min 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!

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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Problem with Propositional Logic
  1. Propositional Logic (Replies: 5)

  2. Propositional Logic (Replies: 9)

Loading...