Results 1 to 5 of 5

Math Help - Basic Connectives

  1. #1
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307

    Basic Connectives

    Prove that the three basic connectives 'or', 'and' and 'not' can all be written in terms of the single connective 'notand' where 'P notand Q' is interpreted as 'not(P and Q)'.

    So I made truth tables for ( P or Q) and (P and Q). I am not sure what the basic connective 'not' is. Is it (not P) / not(Q), or the negation of the individual statements? I figured out that  P \text{and} \; Q = \text{not}\; (P\text{notand} \; Q) . But I couldnt figure out the forms for  P \text{or} Q or  \text{not} P, \; \text{not} Q .

    Any help is appreciated. Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by tukeywilliams View Post
    Prove that the three basic connectives 'or', 'and' and 'not' can all be written in terms of the single connective 'notand' where 'P notand Q' is interpreted as 'not(P and Q)'.

    So I made truth tables for ( P or Q) and (P and Q). I am not sure what the basic connective 'not' is. Is it (not P) / not(Q), or the negation of the individual statements? I figured out that  P \text{and} \; Q = \text{not}\; (P\text{notand} \; Q) . But I couldnt figure out the forms for  P \text{or} Q or  \text{not} P, \; \text{not} Q .

    Any help is appreciated. Thanks.
    can we use notP and notQ in the definitions? if so, P or Q = notP notand notQ
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Jhevon View Post
    can we use notP and notQ in the definitions? if so, P or Q = notP notand notQ
    No (see the possible get out clause latter) as not is one of the things you have to
    show can be written in terms of notand, but if you can do not first without using
    and or or then you can use it for the others.

    RonL
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Apr 2006
    Posts
    399
    Awards
    1
    Quote Originally Posted by tukeywilliams View Post
    Prove that the three basic connectives 'or', 'and' and 'not' can all be written in terms of the single connective 'notand' where 'P notand Q' is interpreted as 'not(P and Q)'.

    So I made truth tables for ( P or Q) and (P and Q). I am not sure what the basic connective 'not' is. Is it (not P) / not(Q), or the negation of the individual statements? I figured out that  P \text{and} \; Q = \text{not}\; (P\text{notand} \; Q) . But I couldnt figure out the forms for  P \text{or} Q or  \text{not} P, \; \text{not} Q .

    Any help is appreciated. Thanks.
    How about this?

    not P = not(P and P) = P notand P.

    P and Q = (P and Q) or (P and Q)
    = not(not(P and Q) and not(P and Q)) (De Morgan's laws)
    = not((P notand Q) and (P notand Q)) (Definition of notand)
    = (P notand Q) notand (P notand Q). (Definition of notand)

    P or Q = not(not P and not Q) (De Morgan's Laws)
    = not((P notand P) and (Q notand Q)) (Using not P = P notand P)
    = (P notand P) notand (Q notand Q). (Definition of notand)

    Is there something simpler?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,712
    Thanks
    1641
    Awards
    1
    This function has as interesting history. If is known as Sheffer’s stroke function after H.M.Sheffer who named it. Although, CS Peirce actually discovered it and its properties and Quine called it the alternate denial function..

    It is most often defined as in the truth-table below.
    \begin{array}{cccc}<br />
   P & Q &\vline &  {P | Q}  \\<br />
\hline<br />
   T & T &\vline &  F  \\<br />
   T & F &\vline &  T  \\<br />
   F & T &\vline &  T  \\<br />
   F & F &\vline &  T  \\<br />
\end{array}

    I think that using the truth-table is easy to see what JakeD found to be true.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] set of connectives
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 14th 2011, 11:39 AM
  2. Not functionally complete set of connectives
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 17th 2010, 04:15 AM
  3. functionally complete set of connectives
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 15th 2010, 11:50 AM
  4. Logic Connectives
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 29th 2009, 09:57 PM
  5. Disproving the completeness of a set of connectives
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 18th 2008, 12:09 PM

Search Tags


/mathhelpforum @mathhelpforum