私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「”嘘つきのパラドックス”はコードで解ける？」（CodeIQ）を参照してください。
突然ですが、
「私はいつも嘘つきである」
という一文について、考えてみてください。
もし、この文を書いた人が"正直"なら、「私はいつも嘘つきである」という文が嘘になり、矛盾します。
逆に、この人が"嘘つき"だとしたら、「私はいつも嘘つきである」という文が嘘をついていないことになり、やはり矛盾します。
この"嘘つきのパラドックス"はなんと紀元前600年ごろの哲学者であるエウブリデスによって考案されたとのことですが、
派生した概念に"自己言及のパラドックス"というものがあります。
同様に、
「この文は偽(False)である」
という一文について、考えてみましょう。
先程の例と同じで、この文が真(True)でも偽(False)でも矛盾していることになりますね。
以下、「自己言及のパラドックス」（2017年4月26日 (水) 02:18 UTCの版）『ウィキペディア日本語版』 より詳細を抜粋します。
嘘つきのパラドックスの問題は、真理と虚偽に関する一般通念を適用すると矛盾が導かれる点である。文法や意味論の上では規則を守りつつ、真理値を割り当てられない文を構築することができる。
このパラドックスの最も単純な文は次の通りである。
この文は偽である。(A)
(A) が真だとすると、そこで表明されていることは全て真でなければならない。しかし、(A) はそれ自身が間違っている（偽である）と表明しているので、それは偽のはずである。これを真とする仮説を立てると、それが偽だという矛盾が生じる。同様に偽とする仮説を立てても矛盾を生じる。この文を偽だとすると、そこで言っている内容は真ではないということになる。すると、それは真だということになる。どちらの仮説を採用しても、(A) は真でありかつ偽であるという結論に至る。
しかし、この文を真とすると偽だということになり、偽とすると真だということになることから、「真でも偽でもない」と結論することもある。このようにこのパラドックスに反応することは、真理と虚偽についての一般通念である「全ての文は二値原理に従う」を否定することであり、それは排中律とも関連する概念である。
この文が真でも偽でもないという場合、次の強化されたパラドックスではどうだろうか。
この文は真ではない。(B)
(B)を真でも偽でもないとするなら、真でも偽でもない中間があるということになり、(B) は真ではないということになる。するとそれはまさしく (B) が主張している内容であり、(B) は真だということになり、結局パラドックスが生じる。
(A) のパラドックスに対するもう一つの反応として、グラハム・プリーストのように矛盾許容論理を仮定し、真であり同時に偽であるとする考え方もある。しかし、次のように変形すると矛盾許容論理を仮定してもパラドックスから逃れられない。
この文は偽のみである（つまり、同時に真ということはない）。(C)
(C) を真であり同時に偽であるとすると、それは偽でなければならなくなる。つまり (C) は偽のみであると表明しているが、それは真ではありえないということであり、結局パラドックスを生じる。
複数の文で構成した版もあり、単純な論証形式となっている。次は2つの文で構成した版である。
次の文は真である。(D1)
前の文は偽である。(D2)
(D1) を真だとすると、(D2) が真だということになる。すると (D1) は偽ということになり、結果として (D2) も偽となる。すると今度は (D1) が真だということになり……というように無限に続き、パラドックスを生じる。
このような形式は相互に言及しあう複数の文を円環状に配することで（つまり、最後の文は最初の文の真偽を述べる）いくらでもバリエーションを生み出せる。次の例は奇数個の文を使ったもので、それぞれ次の文が偽だと表明する。
D2 は偽である。(D1)
D3 は偽である。(D2)
D1 は偽である。(D3)
(D1) が真だとすると、(D2) は偽ということになる。すると (D3) は真となり、結果として (D1) は偽となって、矛盾が生じる。逆に (D1) を偽だとすると、(D2) は真ということになり、(D3) は偽となって、結局 (D1) は真となって、やはり矛盾が生じる。つまり、パラドックスである。
本設問のミッションは、ずばり前述の引用における赤文字の文章が与えられたときに、それが矛盾しているかどうかを判定することです。
まさに歴代の哲学者の思考過程を、コンピュータが解釈できるアルゴリズムに落とせるのか？という挑戦になります。
求められるプログラムの前提条件は、以下の通りとなります。
標準入力から、以下の2パターンの構造の文が複数行送られる
Y is true (X)
Y is false (X)
それぞれのパターンの意味は、以下の通りとなる
(Y)は真である (X)
(Y)は偽である (X)
ここでXおよびYは、1以上N以下の自然数が入る
Xは1から始まり1ずつ増える行番号に必ず一致するものとする
Nは最大で10とする、つまり入力から与えられる行数は最大で10である
これらの入力文からなる文章に自己矛盾がないか判定し、矛盾があれば-1を、なければ0を標準出力に返すこと
以下が、入力と出力例になります。
No. 入力例 出力例 1 1 is true (1) 0 2 1 is false (1) -1 3 1 is true (1)
2 is true (2)
0 4 2 is true (1)
1 is false (2)
-1 5 2 is false (1)
1 is false (2)0 6 2 is false (1)
3 is false (2)
1 is false (3)
-1
たとえば、No. 5の場合、(1)と(2)がお互いに偽であると記述されていますが、もし(1)が真で(2)が偽、あるいはその逆としていても矛盾はしていません。
そのため、出力結果は0となります。
それでは、この問題を解く上のヒントを示しましょう。
それは、"文を集合またはグラフ構造として考える"というものです。
このとき集合の要素（グラフの頂点）は、2N個あることに注意してください。
なぜ2N個なのか？それは、"それぞれの文には真か偽、２通りの可能性がある"ためです。
さらに言うと"１つの入力文は、最大で２つの集合を作る（最大で２本の辺を張れる）"ことができます。
何をもって集合の要素（グラフの頂点）とみなすか、よく考えてみてくださいね。
最後に、今「人工知能」というキーワードが流行していますが、これまでに人工知能と称された技術の歴史を紐解くと、こうした真か否かを問う論理式をどう扱うが重要なテーマだったことがわかるでしょう。
そして、終わったとされる過去のどんな技術が再び脚光を浴びるのか？予想がつかないのが、この分野の面白いところでもあります。
たまには歴代の哲学者の悩みを分かち合いながら、人工知能の未来を想像してみてはいかがでしょうか？
難問ですが、ぜひ挑戦してみてくださいね！
【問題】
標準入力から、「Yは真or偽である（X)」という構造の文が複数送られます(X, Yには自然数が入る）。
これらの文からなる文章に自己矛盾がないか判定し、その結果を標準出力に返してください。
Rubyで解答しています。
#!/usr/bin/ruby
def check(inputs, n, is, results)
# printf("%s, %d, %s, %s\n", inputs.to_s, n, is.to_s, results.to_s)
if results[n] != nil then
if is == results[n] then return 0
else return -1
end
end
results[n] = is
nxt_n = inputs[n]["no"]
nxt_is = (is == inputs[n]["is"])
return check(inputs, nxt_n, nxt_is, results)
end
def solve(inputs)
for n in 1...inputs.size
rt = Array.new(inputs.size+1)
ret = check(inputs, n, true, rt)
return -1 if ret == -1
rf = Array.new(inputs.size+1)
ret = check(inputs, n, false, rf)
return -1 if ret == -1
end
return 0
end
# main
inputs = [nil]
while line = gets
line.strip!
words = line.split
is = false
is = true if words[2] == "true"
inputs << {"no"=>words[0].to_i, "is"=>is}
end
p solve(inputs)
★★★の問題で、問題文にも難問とありますが、そこまで難しいわけではありません。簡単というほどでもありませんが。
多分、普通の考え方でできます。
つまり、任意の文をtureもしくはfalseと仮定し、結果を得ます。
その文が他の文を参照しているならその結果を新たな仮定として同じように次の結果を得ます。
これを繰り返してすでに結果を得ている文に戻ってきた時、その結果が仮定と一致しているかをチェックすれば良い、というのが基本的な考え方になります。
例えば、例6の場合でやってみます。
1行目をtrueと仮定すると、「2 is false」なので2はfalseであると仮定できます。
2行目は「3 is false」で仮定がfalseなので3はtrueであると仮定できます。
3行目は「1 is false」で仮定がtrueなので1はfalseとなります。
ここで最初、1はtrueと仮定したのにfalseとなったので矛盾しているため答えは-1になる、という具合です。
これを全ての行から開始し、それぞれ仮定がtrue, falseのパターンをチェックします。その全てが正しければ0、1つでもおかしいものがあれば-1を答えとします。
入力値を取得し各行を{"no"=>対象行番号, "is"=>true | false}の連想配列として配列に保持します。入力値の要素番号が1始まりなのでinputs[0]はnilでパディングして番号を一致させています。
これをsolve()に渡し、結果を印字します。
引数全ての行について、その行から始め、trueもしくはfalseと仮定した場合の結果を得ます。
途中、1件でも矛盾したものがあれば-1を返却します。
全て正しければ0を返却します。
任意の行から開始した時、矛盾しているかどうかをcheck()で判定します。
inputsのn行目をtrue|falseと仮定した場合、矛盾を生じるかどうかを判定します。
引数inputsは入力値をmainで変換したものです。
nは何行目かを示すインデックス番号です。
isはその行がtrueかfalseかの仮定（連鎖する場合は最初の行から連鎖的に導かれた値）です。
resultsはinputsと要素番号が一致する形で最初の仮定から導かれた値を保持します。
5行目の処理はチェックの終了条件で、すでに結論が得られている行に戻ってきた時の処理になります。過去に得られている仮定とisに渡された値が同じなら矛盾していないので0、異なれば矛盾しているので-1を返します。
11行目で仮定（連鎖の2つ目以降は最初の仮定から導かれた結論）をその行の真偽として記録します。
12行目は次にチェックする行番号を取得しています。
13行目はisの値（仮定の真偽値）からその行の真偽値を求めています。
例えばn行目がtrueと仮定される場合、「m is true」ならm行目はtrueと仮定できますし、「m is false」ならm行目はfalseと仮定できます。逆にn行目がfalseと仮定される場合、「m is true」ならm行目はfalseと仮定できますし、「m is false」ならm行目はtrueと仮定できます。
つまり、引数isとinputs[n]["is"]が同じなら次の行はtrue、異なるならfalseと仮定できるわけです。
15行目で次の行を再帰的にチェックし、終了条件に達して戻ってきた値を返却します。
問題文が長い(^^;;
とばして「求められるプログラムの前提条件は、以下の通りとなります。」以降だけを読んで解きました。
ヒントに「このとき集合の要素（グラフの頂点）は、2N個あることに注意してください。」とありますが、Nで十分な気がしています。trueと仮定した場合に矛盾するならfalseと仮定しても矛盾するし、trueと仮定して無矛盾ならfalseと仮定しても無矛盾なんじゃないかなぁ。いや、ヒントにある通り両方チェックしましたけど（何も考えずに）。