Problem with Propositional Logic

In summary, the speaker is seeking help with a formal proof for (p \wedge q) \Rightarrow p in an assignment, where they are only allowed to use certain tautologies. They have considered using the last tautology but are unsure of how to proceed. They are advised to set up truth assignments and check if both sides are satisfied. A resource link is provided for further assistance.
  • #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 :)
 
Last edited:
Physics news on Phys.org
  • #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.
 

Related to Problem with Propositional Logic

What is propositional logic?

Propositional logic, also known as sentential logic, is a type of deductive reasoning that uses statements (or propositions) to represent and evaluate arguments. It is a fundamental part of mathematical logic and is used in many fields such as computer science, philosophy, and linguistics.

What are the common problems with propositional logic?

One common problem with propositional logic is that it is limited in its ability to represent complex arguments involving multiple premises and conclusions. It also does not account for the meaning or truth value of statements, only their logical structure. Additionally, it does not account for the context or background knowledge that may affect the interpretation of statements.

How do you solve problems with propositional logic?

To solve problems with propositional logic, one can use truth tables or logical equivalences to determine the validity of an argument. It is also important to carefully consider the meaning and context of the statements being used. In some cases, converting propositional logic into a different form, such as predicate logic, may also help to solve problems.

What are some real-world applications of propositional logic?

Propositional logic has many practical applications, such as in computer programming, where it is used to represent and evaluate logical expressions. It is also used in artificial intelligence to represent knowledge and make inferences. In linguistics, propositional logic can be used to analyze the logical structure of sentences and arguments.

What are the differences between propositional logic and predicate logic?

Propositional logic deals with simple statements and their logical connectives (such as AND, OR, NOT), while predicate logic allows for the use of variables and quantifiers (such as FOR ALL, THERE EXISTS) to represent more complex arguments. Predicate logic is also better suited for representing the meaning and truth value of statements, rather than just their logical structure.

Similar threads

  • Calculus and Beyond Homework Help
Replies
8
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
988
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
Replies
10
Views
2K
  • Calculus and Beyond Homework Help
Replies
20
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
24
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
11K
  • Set Theory, Logic, Probability, Statistics
Replies
27
Views
3K
  • Calculus and Beyond Homework Help
Replies
4
Views
2K
Back
Top