User Name Remember Me? Password

 Applied Math Applied Math Forum

 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 May 12th, 2016, 05:26 PM #2 Math Team   Joined: Nov 2014 From: Australia Posts: 689 Thanks: 244 What laws of logic do you know? Do you know De Morgan's Laws? 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 May 12th, 2016, 07:15 PM #4 Senior Member   Joined: Nov 2010 From: Indonesia Posts: 2,001 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)$ 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. 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 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 $\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) Tags laws, logic Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post dmnte Computer Science 0 April 23rd, 2015 10:45 PM FloorPlay Applied Math 2 December 4th, 2012 12:11 PM KingATG Algebra 2 December 26th, 2011 06:33 PM pappi Applied Math 2 March 25th, 2011 12:03 AM mikel03 Algebra 1 April 1st, 2009 05:30 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top      