Discrete Math question on creating a logically equivalent compound proposition

In summary, to find a compound proposition that is logically equivalent to p → q using only the logical operator ↓, we can use the following steps:1. Start with the logical equivalence: p → q is equivalent to ¬p ∨ q2. Use the definition of ↓ to replace ¬p with (p ↓ p): (p ↓ p) ∨ q3. Use the definition of ↓ again to replace (p ↓ p) with ((p ↓ p) ↓ p) and (p ↓ q) with ((p ↓ p) ↓ q)4. Simplify the first part of the statement to just (p ↓ p) since it is always true.5. Use the definition of ↓ again to replace (
  • #1
nicnicman
136
0

Homework Statement



Find a compound proposition logically equivalent to p → q using only the logical operator ↓.

Homework Equations


The Attempt at a Solution


My book does not go into much detail about solving this problem other than providing the answer. I really want to know how to get the answer, step by step. If it helps, here is the answer: ((p ↓ p) ↓ p) ↓ ((p ↓ p) ↓ p)

I've tried constructing truth tables, but that's not really helping.
How in the world would I derive the above answer?
 
Physics news on Phys.org
  • #2


To derive the above answer, you can use the following logical equivalences:

1. p → q is equivalent to ¬p ∨ q (implication equivalence)
2. ¬p ∨ q is equivalent to (p ↓ p) ∨ q (definition of ↓)
3. (p ↓ p) ∨ q is equivalent to ((p ↓ p) ↓ p) ↓ ((p ↓ p) ↓ q) (definition of ↓)

So, ((p ↓ p) ↓ p) ↓ ((p ↓ p) ↓ q) is a compound proposition that is logically equivalent to p → q, using only the logical operator ↓.

Here is a step-by-step explanation of how to derive this answer:

1. Start with the logical equivalence: p → q is equivalent to ¬p ∨ q
2. Replace the ¬p with (p ↓ p) using the definition of ↓: (p ↓ p) ∨ q
3. Use the definition of ↓ again to replace (p ↓ p) with ((p ↓ p) ↓ p) and (p ↓ q) with ((p ↓ p) ↓ q): ((p ↓ p) ↓ p) ∨ ((p ↓ p) ↓ q)
4. Since (p ↓ p) is always true, we can simplify the first part of the statement to just (p ↓ p): (p ↓ p) ∨ ((p ↓ p) ↓ q)
5. Again, using the definition of ↓, replace (p ↓ p) with ((p ↓ p) ↓ p) and (p ↓ q) with ((p ↓ p) ↓ q): ((p ↓ p) ↓ p) ↓ ((p ↓ p) ↓ q)
6. This final statement is logically equivalent to p → q using only the logical operator ↓.
 

What is discrete math?

Discrete math is a branch of mathematics that deals with discrete objects and structures, rather than continuous ones. It is used in various fields, including computer science, engineering, and physics.

What is a compound proposition?

A compound proposition is a logical statement that is made up of two or more simpler propositions, connected by logical operators such as "and" or "or".

What does it mean for two compound propositions to be logically equivalent?

Two compound propositions are said to be logically equivalent if they have the same truth value for every possible combination of truth values of their component propositions. In other words, they are always either both true or both false.

How can I create a logically equivalent compound proposition?

To create a logically equivalent compound proposition, you can use logical equivalences, also known as logical laws or rules, to transform the original proposition into an equivalent one. These laws include the commutative, associative, and distributive laws, among others.

Why is creating logically equivalent compound propositions important?

Creating logically equivalent compound propositions is important because it allows us to simplify complex statements and make logical deductions. It is also useful in various fields such as computer science, where it is used to optimize code and improve efficiency.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
822
  • Programming and Computer Science
Replies
7
Views
4K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
2K
Replies
2
Views
1K
Replies
7
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
3K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
1
Views
3K
Back
Top