論理回路

質問

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)が論理否定、・が論理積、＋は論理和を表す

という問なのですが、どのように証明をすればよいのでしょうか？
お願いします。

回答No.1

a-saitoh

問題を写し間違ってませんか？
x1・y1(bar) + (x1+y1(bar))・fn-1(x2,...,xn,y2,...yn)
=x1・y1(bar) （TRUE　＋ fn-1(x2,...,xn,y2,...yn)）
=x1・y1(bar)　になっちゃいますが。

n(x1,x2,...,xn,y1,y2,...,yn)=
x1・y1(bar) + (x1・y1+　x1(bar)・y1(bar))・fn-1(x2,...,xn,y2,...yn)
とはでは？

与えられた位取り記数法の定義、「N(x1,x2,...,xn)=Σ(i=1～n)xi2^n-i」を使えばすぐ証明できるでしょう。

補足

問題を確認してみたところ、特に間違いはありませんでした。
ですが少し式が分かりづらかったかもしれません。申し訳ないです。論理否定は最初の論理積、論理和ともにy1にしかかかっていません。

どのように使うのでしょうか…？考えてみましたが見当もつきませんでした。お手数ですがもしよろしければご教示願いたいです。