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 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?
OriaG is offline  
 
October 29th, 2012, 04:03 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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 n-ary operator +:{0,1}^n->{0,1} can be written using just {!,v,^} by "translating" its truth table.
kiuhnm is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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





Copyright © 2017 My Math Forum. All rights reserved.