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
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.
 

Related Threads on 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
7K
  • Last Post
Replies
5
Views
243
  • Last Post
Replies
8
Views
1K
Replies
3
Views
2K
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
19
Views
7K
Replies
4
Views
931
Top