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!

Problem with Propositional Logic

  1. Sep 8, 2012 #1

    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 Threads - Problem Propositional Logic Date
Integration problem using u substitution Monday at 1:02 PM
Set problems(Of which one includes propositional logic) Oct 17, 2012
Propositional Logic Problem Jun 24, 2010
Propositional logic problem Oct 18, 2009
Propositional Logic problem Jan 27, 2008