My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
May 12th, 2016, 04:16 PM   #1
Newbie
 
Joined: May 2016
From: London

Posts: 7
Thanks: 0

Laws Of Logic

Use the laws of logic to prove that ¬(p∧ q) ∨ (¬p∧ q)== ¬p V ¬q

Any Help would really be appreciated. Thanks
AJizzle is offline  
 
May 12th, 2016, 05:26 PM   #2
Math Team
 
Joined: Nov 2014
From: Australia

Posts: 688
Thanks: 243

What laws of logic do you know? Do you know De Morgan's Laws?
Azzajazz is offline  
May 12th, 2016, 05:37 PM   #3
Newbie
 
Joined: May 2016
From: London

Posts: 7
Thanks: 0

yes de morgans is easy =
not(p and q) == not p or not q
not(p or q) == not p and not q
AJizzle is offline  
May 12th, 2016, 07:15 PM   #4
Senior Member
 
Monox D. I-Fly's Avatar
 
Joined: Nov 2010
From: Indonesia

Posts: 2,000
Thanks: 132

Math Focus: Trigonometry
$\displaystyle \neg(p\wedge q)\vee(\neg p\wedge q)$
$\displaystyle \equiv(\neg p\vee\neg q)\vee(\neg p\wedge q)$
$\displaystyle \equiv(\neg p\vee\neg q\vee\neg p)\wedge(\neg p\vee\neg q\vee q)$
$\displaystyle \equiv(\neg q\vee\neg p)\wedge(\neg p\vee1)$
$\displaystyle \equiv(\neg q\vee\neg p)\wedge1$
$\displaystyle \equiv(\neg q\vee\neg p)$
$\displaystyle \equiv(\neg p\vee\neg q)$
Monox D. I-Fly is offline  
May 13th, 2016, 02:39 AM   #5
Newbie
 
Joined: May 2016
From: London

Posts: 7
Thanks: 0

Thanks Man! That has really helped me to understand. Do you know about this one.
Given two statements, p and q, prove that (¬p ∧ q) → ¬ (q →p) is tautology. [Hint: p→q == (¬p ∨ q)] and verify your answer using a truth table.
AJizzle is offline  
May 13th, 2016, 04:20 AM   #6
Newbie
 
Joined: May 2016
From: London

Posts: 7
Thanks: 0

(¬P∧ Q) → ¬ (Q → P)
¬ (¬P∧ Q) V ¬ (Q → P) (Implication Law)
(¬¬ P V ¬Q) V ¬ (Q → P) (De Morgan’s Law)
(P V ¬Q) V ¬ (Q → P) (Double Negation Law)
(P V ¬Q) V ¬ (¬ Q V P) (Implication Law)
(P V ¬Q) V (¬¬ Q ∧ ¬P) (De Morgan’s Law)
(P V ¬Q) V (Q ∧ ¬P) = T (Double Negation Law)
¬ (¬P ∧ Q) V (Q ∧ ¬P) (Reversing De Morgan’s Law)
¬ (¬P ∧ Q) V (¬P ∧ Q) = T
(Commutative Law)
This Expression Reduces To True!
P Q (¬P∧ Q) ¬ (Q → P) (¬P ∧ Q) → ¬ (Q →P) ¬ (¬P ∧ Q) V (¬P ∧ Q)
F F F F T T
F T T T T T
T F F F T T
T T F F T T



This is what i have, but i am being told its wrong, help would be appreciated, thanks
AJizzle is offline  
May 13th, 2016, 05:07 AM   #7
Senior Member
 
Joined: Dec 2012
From: Hong Kong

Posts: 853
Thanks: 311

Math Focus: Stochastic processes, statistical inference, data mining, computational linguistics
P

Quote:
Originally Posted by Monox D. I-Fly View Post
$\displaystyle \neg(p\wedge q)\vee(\neg p\wedge q)$
$\displaystyle \equiv(\neg p\vee\neg q)\vee(\neg p\wedge q)$
$\displaystyle \equiv(\neg p\vee\neg q\vee\neg p)\wedge(\neg p\vee\neg q\vee q)$
$\displaystyle \equiv(\neg q\vee\neg p)\wedge(\neg p\vee1)$
$\displaystyle \equiv(\neg q\vee\neg p)\wedge1$
$\displaystyle \equiv(\neg q\vee\neg p)$
$\displaystyle \equiv(\neg p\vee\neg q)$
You can see that the connective with the greatest scope is a material conditional. Whenever that happens, it's likely that you need to start from the expression on the left and derive the one on the right, then wrap up the proof with a conditional introduction.

Next, you see that the expression on the right is a negation. Then there's a pretty good chance you'll need to assume the opposite at first, then prove that it's wrong by reductio.

Now, (Q → P) is another conditional, so we can use the same strategy. Q is true according to (¬P∧ Q). If Q is true, we can derive P. But, according to (¬P∧ Q), we know that ~P is true as well. That contradicts what we've derived. Thus, (Q → P) is false. Then we go back and establish the validity of the whole thing, without dependencies.

So here's the whole proof (left column shows the dependencies of each statement, and we've proved our tautology when we eliminate all the dependencies):

1 1. $\displaystyle (\neg P \wedge Q)$ (Assumption)
2 2. $\displaystyle (Q \rightarrow P)$ (Assumption)
1 3. $\displaystyle Q$ (1 - Conjunction elimination)
1, 2 4. $\displaystyle P$ (2, 3 - Conditional elimination)
1 5. $\displaystyle \neg P$ (1 - Conjunction elimination)
1, 2 6. $\displaystyle (P \wedge \neg P)$ (4, 5 - Conjunction introduction)
1 7. $\displaystyle \neg (Q \rightarrow P)$ (2, 6 - Negation introduction)
8. $\displaystyle ((\neg P \wedge Q) \rightarrow \neg (Q \rightarrow P))$ (1, 7 - Conditional introduction)
123qwerty is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

Tags
laws, logic



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
prove logic equation, logic algebra dmnte Computer Science 0 April 23rd, 2015 10:45 PM
Laws of Logic FloorPlay Applied Math 2 December 4th, 2012 12:11 PM
Laws of Exponents KingATG Algebra 2 December 26th, 2011 06:33 PM
absorption laws: pappi Applied Math 2 March 25th, 2011 12:03 AM
Help Please - Index Laws mikel03 Algebra 1 April 1st, 2009 05:30 AM





Copyright © 2018 My Math Forum. All rights reserved.