Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Hello I need to proove that $\{\not\to$, ¬} is functional complete concerning {not, or, and}. The definition: x $\not\to$ y : x and not y. My attempt is to show that {not, or, and} can be also replaced by $\not\to$. not x = already given; LOGIC OR: x or y = not(not(x or y)) = not(not x and not y) = not(not x $\not\to$ y); LOGIC AND: x and y = x $\not\to$ not y Is this correct? -Freddy {}{}{}{}

share|improve this question
1  
Your expressions appear sound and correct. –  Lord_Farin Oct 24 '12 at 21:10
add comment

1 Answer

Yes, correct.

Note also, that

  1. $\lnot$ can also be obtained assuming instead the constant $1$ (alias 'true').
  2. Every function on a Boolean algebra $B$ can be expressed by using constants and the boolean connectives.
share|improve this answer
    
Mind giving an example for 1.? (You don't have to) –  Freddy Oct 24 '12 at 21:18
    
I meant $\lnot x =1\not\to x$. –  Berci Oct 24 '12 at 21:23
    
Oh I see, thanks. –  Freddy Oct 24 '12 at 21:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.