# Math Help - logic related question ...

1. ## logic related question ...

Below is the proof for the following proposition:

(p q) (¬q ¬p)

For each step in the proof indicate which law is used.

p q

Step 1: ¬p q
Step 2: q ¬p
Step 3: ¬(¬q) ¬p
Step 4: ¬
q¬p

What law belongs to what step?
Law 1: (a
b) (b a) (commutativity of )
Law 2: ¬(¬a) a(law of negation)
Law 3:
(a⇒ b) (¬a b) (law of implication)
Law 4:
(a b) ((a b) ∧ (b a))(law of equivalence)

I really have no clue where to start here ... so maybe someone can give me a hand ...

2. ## Re: logic related question ...

I found this explanation ... can someone confirm this is correct?

CNF = Conjunctive Normal Form
wff = Well Formed Formula

The following is the procedure to transform any wff into a logically equivalent wff that is in CNF.

Step 1. Eliminate ⇔’s (using the Law of Equivalence)

Step 2. Eliminate ⇒’s (using the Law of Implication)

Step 3. Move ¬’s inwards (using De Morgan’s Laws), eliminating any double negations (using the Law of Negation).

Step 4. Use the Distribute Law (∨ over ∧) to move the ∧’s up and the ∨’s down; use commutativity and associativity of ∧ and ∨ to reorder subformulas so that this law may be used.

3. ## Re: logic related question ...

p ⇒ q

Step 1: ¬p ∨ q
Hmm, let's see, which of the following four laws is responsible for this step:
Law 1: (a ∨ b) ⇔ (b∨ a) (commutativity of ∨)
Law 2: ¬(¬a) ⇔ a(law of negation)
Law 3: (a⇒ b) ⇔ (¬a∨ b) (law of implication)
Law 4: (a⇔ b) ⇔ ((a⇒ b) ∧ (b ⇒ a))(law of equivalence)
I really have no clue where to start here
To be honest, if you don't see which of the four laws is responsible for converting p ⇒ q into ¬p ∨ q, I am also at a loss concerning how to explain it.

I found this explanation ... can someone confirm this is correct?
Yes, but if this is an unrelated question, please post it in a different thread.

4. ## Re: logic related question ...

Yes, but if this is an unrelated question, please post it in a different thread.
I think this is related but I am not sure...

To be honest, if you don't see which of the four laws is responsible for converting p ⇒ q into ¬p ∨ q, I am also at a loss concerning how to explain it.
We need the 4 laws in a specific order right?
But isn't there a trick to see this? Or is this just information that is by rule?

5. ## Re: logic related question ...

I think this is related but I am not sure...
I don't think so.

We need the 4 laws in a specific order right?
No, to convert p ⇒ q into ¬p ∨ q we need only law 3.

But isn't there a trick to see this?
I am not sure which trick.

Or is this just information that is by rule?
I don't know by which rule and what you mean by "information is by rule."

6. ## Re: logic related question ...

I just want to understand what I should do in order to understand/solve the question...

7. ## Re: logic related question ...

In order to understand what you need to do, you need to realize that each step is a transformation of the previous step by some instance of the provided laws. Which law do you use? That is for you to figure out by simple pattern matching. As already pointed out to you, the first step is a direct application (instance) of Law 3. Do you not see why? If you replace the generic "a" and "b" in Law 3 by the specifics given in the problem "p" and "q", you get exactly the transformation we see from our assumption to step 1.

Now think about step 2. What has changed between step 1 and step 2? Which of the provided laws represent that change?

8. ## Re: logic related question ...

I think that Step 2 belongs to Law 2 ... am I correct?

Now think about step 2. What has changed between step 1 and step 2? Which of the provided laws represent that change?
The change is that NOT p swapped places with q ... And the law of negation represents this change right?

9. ## Re: logic related question ...

You are right, the commutative law of disjunction allows us to transpose positions of each disjunct. The point of the law is to generalize a schema of something that is true for every similar instance. While in your case you are dealing with "¬p v q" it would also work for complex statements like "(p & r) v q" (i.e., it is equivalent to "q v (p & r)"). The point of these exercises is to become familiar with what the laws entail. The name of the law helps explain that. Commutitive laws allow you to commute (transpose, switch positions, etc.) terms around the connective. The law of (double) negation allows you to add a double negative or take it away. The law of implication gives you an equivalent form that is useful for conjunctive or disjunctive normal forms. The law of equivalence lets you break up a biconditional into conjunctions (and from the conjunct of implication with law 3 you can have a conjunction of disjunctions).

Now do you see how the laws justify each transformation at each step? More importantly, do you see why each step is performed due to the provided law?

10. ## Re: logic related question ...

Commutitive laws allow you to commute (transpose, switch positions, etc.) terms around the connective
The law of (double) negation allows you to add a double negative or take it away
The law of implication gives you an equivalent form that is useful for conjunctive or disjunctive normal forms
The law of equivalence lets you break up a biconditional into conjunctions (and from the conjunct of implication with law 3 you can have a conjunction of disjunctions)
Now do you see how the laws justify each transformation at each step? More importantly, do you see why each step is performed due to the provided law?
I can see a pattern indeed ...

SO with this information given I think Step3 = Law 1
And Step 4 = Law 4

Am I correct?

Thanks,

11. ## Re: logic related question ...

Why do you think that? Does it fit the pattern of behavior I described each of the laws to have as you quoted above? Note, you're not using every law in that proof. Some of them are used more than once. Often a pattern of reasoning is like that: you put the statement in other terms that make it easier to put into another form that can then be put into other terms that are desired. That is what is going on here. Remember, your end goal of the proof is to show that ¬q → ¬p. Just as before, what has changed between steps 2 and 3? What is changed between 3 and 4? That change is indicative of some law, otherwise you would not be able to make that sort of transformation. If you can understand that pattern of change, you can answer my original question as to why the law is used at that step. If you cannot answer the 'why' question, you have not grasped the exercise. The point of it is to obtain that pattern recognition skill and relate it to your knowledge of the logical operations involved.

12. ## Re: logic related question ...

Step 1: ¬p ∨ q = Law 3
Step 2: q ∨¬p = Law 2
Step 3: ¬(¬q) ∨¬p = Law 4
Step 4: ¬q⇒ ¬p = Law 1

So if I understand correctly they want you to start with the first step (¬p ∨ q) where you see almost immediately that this belons to Law 3 ... only the characters are different.
And the end result should be ¬q ⇒ ¬p
ANd we get there with using the different laws in the correct order right?

13. ## Re: logic related question ...

Here is a quote from the thread's first post, to remind the law numbers.

Originally Posted by iwan1981
Law 1: (a ∨ b) ⇔ (b∨ a) (commutativity of ∨)
Law 2: ¬(¬a) ⇔ a(law of negation)
Law 3: (a⇒ b) ⇔ (¬a∨ b) (law of implication)
Law 4: (a⇔ b) ⇔ ((a⇒ b) ∧ (b ⇒ a))(law of equivalence)
So, in step 2, we go from ¬p ∨ q to q ∨¬p. Why do you think that this is described by law 2: ¬(¬a) ⇔ a rather than by law 1: (a ∨ b) ⇔ (b ∨ a)? Does the starting formula, i.e., ¬p ∨ q, look more like ¬(¬a) or like a ∨ b?

14. ## Re: logic related question ...

Does the starting formula, i.e., ¬p ∨ q, look more like ¬(¬a) or like a ∨ b?
It looks more like "a ∨ b" right?

15. ## Re: logic related question ...

Yes. But before we go further, could you explain this line:
Originally Posted by iwan1981
Step 3: ¬(¬q) ∨¬p = Law 4
I really want to understand you reasoning. We are converting

q ∨ ¬p (*)

into

¬(¬q) ∨ ¬p (**).

You are saying this is done by law 4:

(a ⇔ b) ⇔ ((a ⇒ b) ∧ (b ⇒ a))

Yet, this law does not mention either ∨ or ¬, which are the only connectives (operations) in the formulas (*) and (**) above. Why do you think law 4 applies?

Page 1 of 3 123 Last