- #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: