Math Help Forum: 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 . But I couldnt figure out the forms for or .

Any help is appreciated. Thanks.

Originally Posted by tukeywilliams

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 . But I couldnt figure out the forms for or .

Any help is appreciated. Thanks.

can we use notP and notQ in the definitions? if so, P or Q = notP notand notQ

Originally Posted by Jhevon

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

Originally Posted by tukeywilliams

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 . But I couldnt figure out the forms for or .

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?

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.


I think that using the truth-table is easy to see what JakeD found to be true.