跳到主要内容

東北大学 工学研究科 電気・情報系 2015年8月実施 基礎科目 問題3 情報基礎1

标签：

Author​

祭音Myyura (co-authored with GPT 5.6 SOL)

Description​

日本語版​

x1,x2,⋯ ,xn∈{0,1}x_1,x_2,\cdots,x_n\in\{0,1\} とし，xˉ\bar{\phantom x} を否定演算とする。このとき nn 変数論理関数 f(x1,x2,⋯ ,xn)f(x_1,x_2,\cdots,x_n) に関して，

f∗(x1,x2,⋯ ,xn)=f(xˉ1,xˉ2,⋯ ,xˉn)‾f^*(x_1,x_2,\cdots,x_n)=\overline{f(\bar x_1,\bar x_2,\cdots,\bar x_n)}

で定義される f∗f^* を論理関数 ff の双対関数という。また，f∗(x1,x2,⋯ ,xn)=f(x1,x2,⋯ ,xn)f^*(x_1,x_2,\cdots,x_n)=f(x_1,x_2,\cdots,x_n) が成り立つとき ff は自己双対であるといい，f∗(x1,x2,⋯ ,xn)=f(x1,x2,⋯ ,xn)‾f^*(x_1,x_2,\cdots,x_n)=\overline{f(x_1,x_2,\cdots,x_n)} が成り立つときには，ff は自己反双対であるという。双対関数に関して，以下の問に答えよ。

(1) F(x,y)F(x,y) を x=yx=y のときに 00，x≠yx\ne y のときに 11 となる 22 変数論理関数とする。このとき，F(x,y)F(x,y) は自己反双対であることを示せ。

(2) 33 変数の論理関数 M(x,y,z)M(x,y,z) は，x,y,zx,y,z のうち，11 の個数が 22 以上のときに 11 となり，それ以外の場合には 00 とする。このとき，M(x,y,z)M(x,y,z) は自己双対であることを示せ。

(3) 自己双対である 22 変数論理関数をすべて挙げよ。

(4) nn 変数論理関数 f1,f2f_1,f_2 が，自己反双対であるとき，f1⊕f2f_1\oplus f_2 は，自己反双対であることを示せ。ただし，⊕\oplus は排他的論理和演算を表す。

题目描述​

令 xi∈{0,1}x_i\in\{0,1\}，xˉ\bar x 表示非。nn 元逻辑函数 ff 的对偶定义为

f∗(x1,…,xn)=f(xˉ1,…,xˉn)‾.f^*(x_1,\ldots,x_n)=\overline{f(\bar x_1,\ldots,\bar x_n)}.

若 f∗=ff^*=f，称 ff 自对偶；若 f∗=fˉf^*=\bar f，称其自反对偶。

  1. 令 F(x,y)=x⊕yF(x,y)=x\oplus y，证明 FF 自反对偶。
  2. M(x,y,z)M(x,y,z) 在至少两个输入为 11 时取 11，否则取 00。证明 MM 自对偶。
  3. 列出全部二元自对偶逻辑函数。
  4. 若 f1,f2f_1,f_2 均为 nn 元自反对偶函数，证明 f1⊕f2f_1\oplus f_2 也自反对偶。

Kai​

(1)​

同时反转两个输入不改变异或值，故

F∗(x,y)=xˉ⊕yˉ‾=x⊕y‾=Fˉ(x,y).F^*(x,y)=\overline{\bar x\oplus\bar y}=\overline{x\oplus y}=\bar F(x,y).

(2)​

设三个输入中有 kk 个 11，取反后有 3−k3-k 个 11。k≥2k\ge2 与 3−k≥23-k\ge2 恰有一个成立，故 M(xˉ,yˉ,zˉ)=Mˉ(x,y,z)M(\bar x,\bar y,\bar z)=\bar M(x,y,z)，即 M∗=MM^*=M。

(3)​

自对偶要求 f(11)=f(00)‾f(11)=\overline{f(00)}、f(10)=f(01)‾f(10)=\overline{f(01)}，前两项可任取，共四个：

x,y,xˉ,yˉ.\boxed{x,\quad y,\quad\bar x,\quad\bar y.}

(4)​

自反对偶等价于 fi(xˉ)=fi(x)f_i(\bar{\boldsymbol x})=f_i(\boldsymbol x)。因此

(f1⊕f2)(xˉ)=f1(x)⊕f2(x),(f_1\oplus f_2)(\bar{\boldsymbol x})=f_1(\boldsymbol x)\oplus f_2(\boldsymbol x),

所以 f1⊕f2f_1\oplus f_2 自反对偶。

本页目录