- #1
TheShoink
- 1
- 0
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 :)
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: