October 29th, 2012, 03:16 PM  #1 
Senior Member Joined: Jul 2012 Posts: 225 Thanks: 0  Discrete Mathematics  logic
Hi, another basic question here regarding logic, but one a bit harder to explain. I am asked to prove that the group {¬,>} (IE the operators NOT and implication) form a whole group of operators. That any logic phrase can be written down with these 2 operators. If i understood the question correctly :P The exact words are "prove that {¬,>} form a whole group of operators" Anyone has any idea what this means or how to solve it? 
October 29th, 2012, 04:03 PM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 933 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Discrete Mathematics  logic
One way would be to build the 16 binary operations from those two. Easier would be to reduce to a set of known complete operators, if you know such a set.

October 29th, 2012, 04:44 PM  #3 
Member Joined: Oct 2012 Posts: 45 Thanks: 0  Re: Discrete Mathematics  logic
Yes. a v b <> !a>b a ^ b <> !(a>!b) Any nary operator +:{0,1}^n>{0,1} can be written using just {!,v,^} by "translating" its truth table. 

Tags 
discrete, logic, mathematics 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Discrete Mathematics.  Shruthi318  Applied Math  0  November 9th, 2013 09:42 PM 
Discrete Mathematics  Set Theory  OriaG  Applied Math  2  February 16th, 2013 06:19 AM 
discrete mathematics  conradtsmith  Abstract Algebra  1  April 19th, 2010 07:02 AM 
discrete mathematics  conradtsmith  Number Theory  1  April 19th, 2010 06:11 AM 
Discrete Mathematics.  Shruthi318  Complex Analysis  0  December 31st, 1969 04:00 PM 