For each ternary propositional connective, we determine the minimum number of binary connectives needed to construct a logically equivalent formula. In order to reduce this problem to a computably feasible one, we prove a number of lemmas showing that every element of a large set of formulas is logically equivalent to a formula in a much smaller associated set.

Author Bio

William Bradley is a statistics major with acomputer science minor at Appalachian State University. He startedworking in the Academy of Science in the spring of 2009 and iscontinuing research in the STEP program until 2011 with Dr. WilliamCook, but with a focus on deblurring images using matrices. His planis to attend graduate school for statistics after graduating in 2012.When not studying, he is active in the ASU Math Club and enjoysrelaxing with friends. He would like to thank Dr. Jeff Hirst and Dr.Rahman Tashakkori for this great experience.

Steve Harenberg is currently a mathematics major at UNC-Chapel Hill with a minor in computer science. He will be graduating in December of 2011 and plans on attending graduate school in math. Under the guidance of Dr. Hirst, he worked on this project during the 2008-2009 school year at Appalachian State University as part of the Academy of Science (NSF STEP-0756928). In his free time he enjoys juggling and riding his bike.

Matthew Owen is an undergraduate at Appalachian State University majoring in mathematics. He hopes to become a mechanical engineer after graduation. Matthew joined the Academy of Science in spring semester of 2009 and with the financial assistance of the grant NSF STEP-0756928 the student group along with Jeff Hirst Ph.D. was able to make several presentations on their research.

Matthew Roberts is an undergraduate mathematics major at the North Carolina State University with a minor in cognitive science. He plans to graduate by May 2012. Matthew worked with Dr. Hirst on this research project at the Appalachian State University as a part of the Academy of Science program (NSF STEP-075692) during the 2008-2009 school year. Matthew has plans to attend graduate school in either math or theoretical computer science with a focus in mathematical logic. In his free time he likes nature and simple living.