• Support PF! Buy your school textbooks, materials and every day products Here!

Problem with Propositional Logic

  • Thread starter TheShoink
  • Start date
  • #1
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 :)
 
Last edited:

Answers and Replies

  • #2
326
3

Related Threads for: Problem with Propositional Logic

  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
5
Views
5K
  • Last Post
Replies
9
Views
6K
  • Last Post
Replies
8
Views
1K
Replies
3
Views
1K
  • Last Post
Replies
19
Views
7K
Replies
4
Views
768
Top