My Math Forum  

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

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
October 3rd, 2013, 02:32 PM   #1
Member
 
Joined: Sep 2013

Posts: 43
Thanks: 0

Are there any other methods to prove logical equivalence?

I can do that by using a truth table. But are there any other shorter ways of doing that?
danoc93 is offline  
 
October 3rd, 2013, 04:08 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Are there any other methods to prove logical equivalence

Sure, you could transform the two by tautologies until they are (symbolically) equal.
CRGreathouse is offline  
October 3rd, 2013, 06:51 PM   #3
Member
 
Joined: Sep 2013

Posts: 43
Thanks: 0

Re: Are there any other methods to prove logical equivalence

Well, how do you know when to stop trying to transform them? I mean, when can you say 'NO, they aren't equivalent'. Because for long expressions it could take a while before you are out of transformation possibilities... and sometimes you will never be.

Because I have this
P ? (Q ? R)
(P ? Q) ? (P ? R)

by using a truth table they are not!
danoc93 is offline  
October 3rd, 2013, 07:00 PM   #4
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Are there any other methods to prove logical equivalence

You can prove that they are inequivalent by finding an assignment which makes one true and the other false. (Essentially, you only need one row of the truth table as long as it's the right row.)
CRGreathouse is offline  
October 7th, 2013, 06:27 AM   #5
Newbie
 
Joined: Mar 2012

Posts: 25
Thanks: 0

Re: Are there any other methods to prove logical equivalence

Quote:
Originally Posted by danoc93
Well, how do you know when to stop trying to transform them?
Truth table is just another way of saying that you're transforming an expression to the form of:

A&B + A&C + B&D ... etc.

So transform both expressions into that form and then compare the two.
jomagam is offline  
October 7th, 2013, 02:57 PM   #6
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Are there any other methods to prove logical equivalence

Quote:
Originally Posted by jomagam
Quote:
Originally Posted by danoc93
Well, how do you know when to stop trying to transform them?
Truth table is just another way of saying that you're transforming an expression to the form of:

A&B + A&C + B&D ... etc.

So transform both expressions into that form and then compare the two.
More generally, this is an example of a canonical form (see, e.g., A = B). There are other canonical forms and their proofs work similarly.
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

Tags
equivalence, logical, methods, prove



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
LOGICAL EQUIVALENCE maths4computing Applied Math 15 July 20th, 2013 08:31 AM
Logical equivalence!! eChung00 Applied Math 3 September 30th, 2012 04:17 PM
Show this Logical Equivalence Jack Spicer Applied Math 8 February 3rd, 2012 05:23 AM
Logical Equivalence problem Frenchie. Applied Math 4 January 24th, 2012 09:12 AM
Logical Equivalence problem Frenchie. Number Theory 3 December 31st, 1969 04:00 PM





Copyright © 2019 My Math Forum. All rights reserved.