My Math Forum Are there any other methods to prove logical equivalence?

 Applied Math Applied Math Forum

 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?
 October 3rd, 2013, 04:08 PM #2 Global Moderator     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.
 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!
 October 3rd, 2013, 07:00 PM #4 Global Moderator     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.)
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.

October 7th, 2013, 02:57 PM   #6
Global Moderator

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.

 Tags equivalence, logical, methods, prove

 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top