3NOT問題がよくわからないのでまずは理解する
要約
問題文が「わからない」のと、解き方が「わからない」のがごっちゃになって、問題文を理解していないまま複雑な解き方の考察をしてしまった事例 問題文を理解していないまま解き方の考察をする人を見て「ちゃんと勉強しろ」という人がいた事例
---
合っているか自信ないので補足ほしいです
x,y,zの3入力, x',y',z'の3出力を持つブラックボックスがある. 入出力の関係は
x' = not x
y' = not y
z' = not z
である. ブラックボックスには, andとorは好きなだけ使われているが, notは2つしかないことが分かっている. 内部はどうなっているか.
こういうことかしらsta.icon
https://gyazo.com/4f784c2706f2326817b89a028a6dfe72
？の中がどうなっているか（論理回路がどうなっているか）を考えよ
つまり入力としてx,y,zの三つを入れると、not x,not y, not zの三つが出てくる
これであってます 増井俊之.icon
普通に回路だと思って解いてください 増井俊之.icon
論理回路の知識が少しでもあれば問題の意味は明白です ゴチャゴチャ変な考察は不要なんですが
話を複雑にしてるだけだと思いますけどね
yuki_minoh.iconこれｗ
やっぱり考察の意義が乏しく感じられる
問題設定を理解する上で論理回路の知識が少し必要ってのは、まあ論理回路の言葉で書いてあるのでその通りnishio.icon
だけど、このパズルを解く上で「論理回路だと考えること」が有益かどうかっていうと微妙だなぁ
僕は論理回路とは異なるものに変換して解いたし。
何に変換しましたか？yuki_minoh.icon
今僕は線形代数と漸化式と微分を試してます
漸化式表示にできたのであとは最適化問題を解くという段階 なお問題の本質に比べると不必要に複雑なのは変わりない
質問に対する直接の回答はページ末にて
道は複製してもよい
普通にやると、2入力から1出力になる
https://gyazo.com/01b32ce5a2eb3e99bdb171c4cc81ebf7
NOTの場合は1入力1出力
一方、この問題では3出力必要である
よって
「一度でもandやorを使ったらもう解けない」となる
notだけでは当然解けない（3 notに対して2 notしかない）
パズルが成立していない
が、成立していないはずはないだろう
何か前提を見落としている
複製できる、と考えるのが自然だと思った
https://gyazo.com/af39aa8cd1c9e5b19df61efc79404fc4
https://gyazo.com/745995e420813f3ccf0b12fb12a3f8ca
↑ このようにしても良い
https://gyazo.com/0c24db9109817e48d5b4523f6e5b9ba4
↑ なんならこうしてもいい
正しいnishio.icon
複製なんて言葉は気持ち悪いですね 増井俊之.icon
コンセントに電化製品ふたつつないだとき「複製」なんて言わないでしょう
「道」も微妙かもしれませんsta.icon
回路の線のことを「道」なんて言いませんからね 増井俊之.icon
論理回路において普通のことを普通の言葉で表現してほしいです 増井俊之.icon
...また紛糾するかもしれないからこのページはもう見ないこにします 増井俊之.icon
言い換えるとこうか？takker.icon
以下の条件を満たす3変数命題函数$ \psiを求めよ
$ \psi(x,y,z)\iff\lnot x\land\lnot y\land\lnot z
$ \psiに陽に含まれる$ \lnotはちょうど2つである
この言い換えはおかしい
$ \psi(x,y,z):\iff\lnot x\land\lnot (y\lor z)とすぐに答えが求まってしまう
こんなに簡単なわけがない
言い換えで何かを間違えている
3出力を持つが何を意味しているのかがわからない
出力を1つにしないと命題として成立しないから、何かしらの方法で1つの出力にまとめているはずなんだが……
「1つの命題として成立しないといけない」が不要な思い込みnishio.icon
あえて命題として言うなら「3つの命題$ \psi_x(x,y,z)\iff\lnot x,\, \psi_y(x,y,z)\iff\lnot y,\, \psi_z(x,y,z)\iff\lnot zを作る問題」
なるほど。普通にvector函数$ \pmb{\psi}:(x,y,z)\mapsto(x',y',z')で考えればよかったんですねtakker.icon
$ \pmb{\psi}:(x,y,z)\mapsto(x',y',z')で考察する
もし制約条件を無視するなら、例えば$ \pmb{\psi}:(x,y,z)\mapsto(\lnot x, \lnot y,\lnot z)が当てはまる
制約条件は、$ \pmb{\psi}\ (=(\psi_x,\psi_y,\psi_z))に陽に含まれる$ \lnotの合計数がちょうど2になることを要求している
各論理式中ではなく、3つの論理式全体で使っている$ \lnotの総計
例：$ \pmb{\psi}:(x,y,z)\mapsto(\lnot x, \lnot y,\lnot z)
それぞれの論理式で$ \lnotを一回しか使っていないが、全体でみると計3回使っているので制約条件に合わない
いやまて。この制約条件の解釈はあっているのか？
反転操作と論理否定記号をごっちゃにするべきじゃないと思いますよ
+1nishio.icon
二重否定除去を考えればわかると思います
反転操作とはどれのことを示していますか？takker.icon
not回路による論理値の反転ですyuki_minoh.icon
通常の数理論理学的な式変形は十分条件の範囲内でしか変形できないので、論理回路の考察は数理論理学でない操作を考える必要があります
たとえばNot回路は論理否定を導入しますが、否定導入のために矛盾を導く必要がないのが数理論理学的な変形との違いです
そこは問題ではないと思いますtakker.icon
証明図を作成する際は推論規則に則った導入しかできませんが、論理式を作るだけなら、文法エラーでなければ何でも構築できます
例えば$ \lnot P\land Q\implies (\lnot\lnot H\implies Q)の真偽は特定できないが、妥当な論理式である
結局今回問われているのは「どう論理式を作るか」を制約して目的の論理式を構成する問題だと思うのですがどうですか？yuki_minoh.icon
「どう論理式を作るか」を制約して目的の論理式を構成する問題 +1nishio.icon
結局、今回の問題の考察で重要なのは「論理式の構成手順」と「解釈」の分離だと思います
この2つを同一視すると、下記のように問題の制約の解釈に困難が生じると思います
下記の例で示されているのは「解釈と構成手順は一致する」ことではなく、「同じ意味の式を2通りの方法で構成できる」ことなのだ、と考えるのが良い気がしています
多分この制約条件の解釈は間違っている
例えば以下の回路はNOTゲートを2個しか使っていないが、出力はどうやっても$ \lnotを3つ使わないと定式化できない
https://kakeru.app/24b6a93667fba99506a10f2db1e0b520 https://i.kakeru.app/24b6a93667fba99506a10f2db1e0b520.svg
論理ゲートの使用数は、対応する論理記号を一番外側に使っている全ての部分論理式を重複を除いて数えた数と一致する？
$ \lnot x2
$ \lnotを一番外で使っている部分論理式が$ \lnot(x\land y)と$ \lnot(y\land z)しかない
$ \land x2
$ x\land yと$ y\land zの2式のみ
$ \lor x1
$ \lnot(x\land y)\lor\lnot(y\land z)のみ
論理式を式変形すれば、論理ゲートの使用数も変化する
例
https://kakeru.app/d21acbb1598251c321717bce5515c293 https://i.kakeru.app/d21acbb1598251c321717bce5515c293.svg
$ \lorが1つ減って$ \landと$ \lnotが1つづつ増えた
論理式と論理回路を一対一対応させようとしているように見えるが、もともと一対一対応しないものを無理やり対応させようとして話がややこしくなってるように見えるnishio.icon
yuki_minoh.iconいやドモルガンの法則とか諸々使えるんで反転操作と論理否定記号をごっちゃにするべきじゃないと思いますよ
より直接的に言えば「論理回路と論理式をごっちゃにするべきじゃないと思いますよ」
$ \pmb{\psi}の各成分の命題函数は非対称なはず
命題函数の本数に対して、使用できる$ \lnotの数が少ないので、対称な命題函数を作成する事ができない
$ \pmb{f}:\Bbb{B}^3\rightarrow\Bbb{B}^2と$ \pmb{g}:\Bbb{B}^2\rightarrow\Bbb{B}^3との合成函数や、$ \pmb{h}:\Bbb{B}^3\rightarrow\Bbb{B}^4と$ \pmb{i}:\Bbb{B}^4\rightarrow\Bbb{B}^3との合成函数で$ \pmb{\psi}で表してもいい
($ \Bbb{B}:=\{\top,\bot\}とした)
+1nishio.icon
ところで減少することはあり得ると思う？
ただし、途中で次元を増減させたとしても、命題函数の最終的な本数は変わらず3である
yuki_minoh.icon
僕も少し考えていましたが、以下のように定式化するとうまくいくと思います
整理してみると回路による操作は論理学的操作と分けて考えるべきだと分かった
学びだ
多分これ木構造とかオートマトン考えたほうがいいな
ベクトル列$ X = (X_1, \cdots, X_i, \cdots, X_n)^\mathsf{T}と関数列$ \psi = (\psi_1, \cdots, \psi_{i-1})^{\mathsf{T}}を考える
$ X_iは論理式からなるベクトル
題意より以下の条件を得る
$ X_1 = \lbrack P,Q,R\rbrack ^ \mathsf{T}
$ X_n = \lbrack \lnot P, \lnot Q, \lnot R \rbrack ^ \mathsf{T}
考えるべき操作は以下のように漸化式で定式化できる
$ X_{i+i} = \psi_i(X_i), ~~ ( 1 \le i \le n-1)
$ \psi_iに許された操作は「回路的操作」と「論理学的操作」の二つがある
以下「回路的操作」をi毎に必ず一回だけ行う
「分岐」
入力の要素を複製し、新しい次元として加える
ex: $ \lbrack P, P, Q, R\rbrack ^ \mathsf{T} = \psi_i(\lbrack P, Q, R\rbrack ^ \mathsf{T})
回路の分岐に相当
「結合」
連言・選言によって二つの次元の論理式を結合すること
ex: $ \lbrack P \land Q, R\rbrack ^ \mathsf{T} = \psi_i(\lbrack P, Q, R\rbrack ^ \mathsf{T})
出力の次元数は入力の次元数-1
「反転」
一つの次元の論理値を反転させること
全体で2回まで
論理学的操作
単一次元の範囲内ならば無制限に行って良い
他の次元の結果を参照することはできない
参照のためには結合操作が必要になる
通常の数理論理学的式変形を自由に実行できる
次の回路的操作の前に完結するならば背理法などを利用してもよい
証明単位
上記を全て満たす関数列$ \psi = (\psi_1, \cdots, \psi_{i-1})^{\mathsf{T}}を求めよ
で、ここまで考えて「論理回路考えた方が早くねw」と思ったので放置してます
そもそも入出力の次元数が固定できない以上、上記の関数列を一部だけ取り出して抽象的に思考するというやり方ができず、問題の整理に役立たないように見える
とはいえ+1, 0, -1のいずれかなので
入出力の次元数が固定できない
-1nishio.icon
利用可能かどうかをベクトルに含まれるかどうかで表現しているから次元数が変わるのであって、定義域を適切なものにした0/1ベクトルにすれば次元は変わらないnishio.icon
でも逆演算を思考することはできる？
問題の解法を考えてみる
線形代数を利用したい
え、3つ入力するってokなん？
AND(x, y, z) = AND(x, AND(y, z))ですnishio.icon
なるほどですsta.icon
何に変換しましたか？yuki_minoh.icon
3ビットの入力を受け取り1ビットの値を返す(数学的な意味での)関数ですnishio.icon
関数の合成の問題と捉える
高々256個の関数しか登場しない
8ビット整数で表現できる