論理回路
2n変数論理関数
fn(x1,x2,...,xn,y1,y2,...,yn)={ 1 N(x1,x2,...,xn)>N(y1,y2,...,yn)の時
0 その以外
について、以下の問に答えよ。ここで、Nは入力を2進数とみなしたときの数を値として持つ関数であり、N(x1,x2,...,xn)=Σ(i=1～n)xi2^n-iと表すことができる。
問 任意のn>=2に対して
fn(x1,x2,...,xn,y1,y2,...,yn)=
x1・y1(bar) + (x1+y1(bar))・fn-1(x2,...,xn,y2,...yn)
が成り立つことを示せ。ただし、(bar)が論理否定、・が論理積、＋は論理和を表す
という問なのですが、どのように証明をすればよいのでしょうか？
お願いします。
