真理値表を使用せずに、このステートメントがトートロジーであることを証明するにはどうすればよいですか?

2
jackkkk 2020-04-13 05:46.

ステートメントです

[(P→(Q∧¬R))∧(¬S→(P∨¬V))∧R∧V]→S

トートロジー?もしそうなら、それが真理値表を使用せずにあるという正式な証明を与えてください。この問題を解決する方法がわかりません。誰か助けてもらえますか?

(P→(Q∧¬R))∧(¬S→(P∨¬V))∧R∧V

(¬P∨(Q∧¬R))∧((¬S∧¬P)→¬V)∧R∧V

((¬P∨Q)∧(¬P∨¬R))∧(¬(S∨P)→¬V)∧R∧V

((¬P∨Q)∧(¬P∨¬R))∧(V→(S∨P))∧R∧V

(¬P∨Q)∧(¬P∨¬R))∧(¬V∨(S∨P))∧R∧V

前もって感謝します。

4 answers

2
Noname 2020-04-13 18:28.

(1)(反論のために)式が偽であるようなケース/真理の割り当てが考えられると仮定します。

(2)それは、(その想定された割り当てにおいて)前件が真であり、結果として偽であることを意味します。

そう $S$ は偽であり、先行詞のすべての結合は真です。

(3)それで、特に、 $R$ 真実であり、 $(P \rightarrow (Q\land\neg R))$ も真実です。

以来 $R$ 本当です、 $(Q\land\neg R)$は誤りです。だから、のための唯一の方法$(P \rightarrow (Q\land\neg R))$真実であるということ、その前例が$P$は誤りです。 (真の条件と偽の結果の場合、真の前件を持つことはできません)。

(4)問題は $S$仮説では誤りです。そう : $\neg S\rightarrow (P\lor\neg V))$は、真の前件を持つ真の条件です。したがって、それは真の結果をもたらす必要があります。

したがって、結果として $(P\lor\neg V))$真実でなければなりません。この論理和にはすでに誤った論理和があります(Vは割り当てで真であるため、段階的に$(2)$)。つまり、最初の分離、つまり$P$、真でなければなりません。

(5)しかし、真でなければならないこの分離は偽です(ステップ(3)による)。したがって、矛盾

結論:式が偽である一貫した/可能な真実の割り当てはありません。

注:この方法の詳細については、メンデルソン、ブール代数の概要およびスイッチング回路を参照してください

注意 :

ここで使用する原則は次のとおりです。

(1)条件付きは、その先行詞がtrueであり、その結果がfalseである場合、falseです。

(2)接続詞がすべて真である場合、その接続詞は真です。

(3)論理和の少なくとも1つが真である場合、論理和は真です。

(4)命題が真と偽を同時に持つことはできません。

2
Bram28 2020-04-13 22:14.

完全な真理値表の代わりに、いわゆる「短い真理値表」メソッドを実行できます。基本は、興味のあるものに応じて1つ以上のステートメントをtrueまたはfalseに設定し、そこから何が偽造されているかを確認することです。したがって、この場合、単一のステートメントがあり、それがトートロジーであるかどうかに関心があるので、関心のある真実の価値はそれが偽であることにあります。これは直感に反しているように見えますが、ステートメントがFalseである可能性がある場合はトートロジーではなく、Falseである可能性がない場合はトートロジーであることに注意してください。だから、可能性、それは虚偽であることの答えを提供します重要な可能性があります。

それでは、ステートメントをFalseに設定して、何が起こるかを見てみましょう。

\ begin {array} {cccccccccccccccccccc} [(&P&\ rightarrow&(Q&\ land&\ neg&R&))&\ land&(\ neg&S&\ rightarrow&(P&\ lor&\ neg&V& ))&\ land&R∧&\ land&V]&\ rightarrow&S \\ &&&&&&&&&&&&&&&&&&&&&& F&\ end {array}

まあ、条件付きから偽への唯一の方法があり、それは先行詞が真であり、結果として偽であるということです。

\ begin {array} {cccccccccccccccccccc} [(&P&\ rightarrow&(Q&\ land&\ neg&R&))&\ land&(\ neg&S&\ rightarrow&(P&\ lor&\ neg&V& ))&\ land&R&\ land&V]&\ rightarrow&S \\ &&&&&&&& T &&&&&&&&& T && T && F&F \ end {array}

もちろん、これはすべての個々の結合が真でなければならないことを意味します。

\ begin {array} {cccccccccccccccccccc} [(&P&\ rightarrow&(Q&\ land&\ neg&R&))&\ land&(\ neg&S&\ rightarrow&(P&\ lor&\ neg&V& ))&\ land&R&\ land&V]&\ rightarrow&S \\ && T &&&&&& T &&& T &&&&&& T&T&T&T&F&F \ end {array}

それでは、すでに強制されているアトミック命題の値のいくつかをコピーしましょう。 $R$$V$、および $S$

\ begin {array} {cccccccccccccccccccc} [(&P&\ rightarrow&(Q&\ land&\ neg&R&))&\ land&(\ neg&S&\ rightarrow&(P&\ lor&\ neg&V& ))&\ land&R&\ land&V]&\ rightarrow&S \\ && T &&&& T && T && F&T &&&& T && T&T&T&T&F&F \ end {array}

否定を解決する:

\ begin {array} {cccccccccccccccccccc} [(&P&\ rightarrow&(Q&\ land&\ neg&R&))&\ land&(\ neg&S&\ rightarrow&(P&\ lor&\ neg&V& ))&\ land&R&\ land&V]&\ rightarrow&S \\ && T &&& F&T && T&T&F&T &&& F&T && T&T&T&T&F&F \ end {array}

焦点を当てましょう $\neg S \rightarrow (P \lor \neg V)$。これを真にしようとしているので、$\neg S$ すでに真になることを余儀なくされている、つまり $P \lor \neg V$ 同様に真である必要があります:

\ begin {array} {cccccccccccccccccccc} [(&P&\ rightarrow&(Q&\ land&\ neg&R&))&\ land&(\ neg&S&\ rightarrow&(P&\ lor&\ neg&V& ))&\ land&R&\ land&V]&\ rightarrow&S \\ && T &&& F&T && T&T&F&T && T&F&T && T&T&T&T&F&F \ end {array}

どの力 $P$ 真であります:

\ begin {array} {cccccccccccccccccccc} [(&P&\ rightarrow&(Q&\ land&\ neg&R&))&\ land&(\ neg&S&\ rightarrow&(P&\ lor&\ neg&V& ))&\ land&R&\ land&V]&\ rightarrow&S \\ && T &&& F&T && T&T&F&T&T&T&F&T && T&T&T&T&F&F \ end {array}

のコピー値 $P$

\ begin {array} {cccccccccccccccccccc} [(&P&\ rightarrow&(Q&\ land&\ neg&R&))&\ land&(\ neg&S&\ rightarrow&(P&\ lor&\ neg&V& ))&\ land&R&\ land&V]&\ rightarrow&S \\&T&T &&& F&T && T&T&F&T&T&T&F&T && T&T&T&T&F&F \ end {array}

以来 $\neg R$ Falseの場合、次のようになります $Q \land \neg R$ また誤りです:

\ begin {array} {cccccccccccccccccccc} [(&P&\ rightarrow&(Q&\ land&\ neg&R&))&\ land&(\ neg&S&\ rightarrow&(P&\ lor&\ neg&V& ))&\ land&R&\ land&V]&\ rightarrow&S \\&T&T && F&F&T && T&T&F&T&T&T&F&T && T&T&T&T&F&F \ end {array}

しかし今、私たちは問題を抱えています(矛盾!): $P \rightarrow (Q \land \neg R$ 真であるはずですが $P$ 真実であり、 $Q \land \neg R$ False:

\ begin {array} {cccccccccccccccccccc} [(&P&\ rightarrow&(Q&\ land&\ neg&R&))&\ land&(\ neg&S&\ rightarrow&(P&\ lor&\ neg&V& ))&\ land&R&\ land&V]&\ rightarrow&S \\&\ color {red} T&\ color {red} T && \ color {red} F&F&T && T&T&F&T&T&T&F&T && T&T&T&T&F&F \ end {array}

これは、私たちの仮定に反して、元の状態全体が偽になることできないことを意味します...それトートロジーであることを意味します。

さて、これは大変な作業のように思えますが、これが1行に形式化されたプロセス全体です。ここでは、インデックスを使用して、真理値を配置する順序を示しています。

\ begin {array} {cccccccccccccccccccc} [(&P&\ rightarrow&(Q&\ land&\ neg&R&))&\ land&(\ neg&S&\ rightarrow&(P&\ lor&\ neg&V& ))&\ land&R&\ land&V]&\ rightarrow&S \\&\ color {red} T_ {17}&\ color {red} T_6 && \ color {red} F_ {18}&F_ {12} &T_ {11} && T&T_ {13}&F_ {10}&T_5&T_ {16}&T_ {15}&F_ {14}&T_9 && T_4&T_7&T_3&T_8&F_1&F_2 \ end {array}

以上です!したがって、この単一の行は、他の行の全体と一緒に完全な真理値表に表示されることに注意してください。しかし、この方法では、元の質問への回答を示す行に直接「ホームイン」するのが効果的です。この方法に慣れると、実際にはかなり高速であり、実際、経験豊富な論理学者にとっては非常に迅速な方法であることがよくあります。また、これは事実上、Ray Littlerockによって提供された回答で説明されている方法であることに注意してください...これをうまく形式化する方法がわかるようになりました。

残念ながら、この方法には欠点があります。それは、「移動」が強制されない場合があるため、いくつかのオプションを検討し始めない限り、答えが得られないことです。そうですね、そのような選択を体系的に追跡する1つの方法は、user400188によって提供された回答に示されている「ツリーメソッド」または「タブローメソッド」です。

そうです、完全な真理値表を回避する方法はたくさんあります!

1
user400188 2020-04-13 13:52.

[(P→(Q∧¬R))∧(¬S→(P∨¬V))∧R∧V]→S(0)

(0)が真理値表やカルノー図を使用せずにトートロジーであることを示す最も簡単な方法は、 https://en.wikipedia.org/wiki/Method_of_analytic_tableaux

この方法を使用するには、最初に(0)が偽であると仮定し、その仮定から矛盾を導き出します。私たちの仮定は矛盾につながったので、それは間違っていたに違いありません。したがって、(0)は偽であってはなりません。つまり、(0)はトートロジーです。

次の証明ツリーでは、矛盾が発生すると、ブランチにXのマークが付けられます。目的は、すべての支店を閉鎖することです。そのため、前提が真実である方法はありません。

質問に対するあなたの試みは別の証明方法に従っているように思われるので、私はこの質問に以下の別の方法で答えました。ここでは、(0)を(0)に簡略化するまで、さまざまな方法で書き直します。$\lnot S)\lor S$、あなたがしているように見えたように。

1
Anton Sherwood 2020-05-06 00:57.

[(P→(Q∧¬R))∧(¬S→(P∨¬V))∧R∧V]→S

まず、「暗黙の」演算子をより基本的な演算子に変換します。

¬[(¬P∨(Q∧¬R))∧(S∨(P∨¬V))∧R∧V]∨S

そしてそれはすべて代数です。

[¬(¬P∨(Q∧¬R))∨¬(S∨(P∨¬V))∨¬R∨¬V]∨S

(P∧¬(Q∧¬R))∨(¬S∧¬(P∨¬V))∨¬R∨¬V∨S

(P∧(¬Q∨R))∨(¬S∧¬P∧V)∨¬R∨¬V∨S

(P∧¬Q)∨(P∧R)∨(¬S∧¬P∧V)∨¬R∨¬V∨S

(P∧¬Q)∨P∨(¬S∧¬P)∨¬R∨¬V∨S

(P∧¬Q)∨P∨¬S∨¬R∨¬V∨S

P∨¬S∨¬R∨¬V∨S

P∨¬R∨¬V∨¬S∨S

P∨¬R∨¬V∨1

1

Related questions

MORE COOL STUFF

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire が息子の Shelby Blackstock と共有しているクリスマスの伝統について学びましょう。

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルとマライア・キャリーが自然な髪の上でどのように結合したかについて、メーガンの「アーキタイプ」ポッドキャストのエピソードで学びましょう.

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子が家族、特にチャールズ王とウィリアム王子との関係について望んでいると主張したある情報源を発見してください。

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドが、母親のナオミ・ジャッドが亡くなってから初めての感謝祭のお祝いを主催しているときに、彼女が今では家長であることをどのように認識したかを学びましょう.

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

オーケーグッド770HPランボルギーニセンテナリオは十分に正気ではない

オーケーグッド770HPランボルギーニセンテナリオは十分に正気ではない

ランボルギーニの創設者であるフェルッチオランボルギーニが100歳になるのは毎日ではありません(そうです、彼は死んでいて、まだ死んでいると思います。

彼らが買った1台の車からAppleの車の計画について私たちが推測できること

彼らが買った1台の車からAppleの車の計画について私たちが推測できること

Appleが自動車分野に参入するという噂はかなり前から渦巻いており、AppleウォッチャーがSixtyEight Researchという会社がAppleの自動車研究開発のシェル会社である可能性が高いと判断したとき、その渦巻きは本当に渦巻いた。また、会社が購入した車は1台だけであることが知られており、その車はAppleが何を考えているかについての手がかりでいっぱいになる可能性があることも伝えています。

天文学者は太陽系の9番目の惑星の新しい証拠を見つけます

天文学者は太陽系の9番目の惑星の新しい証拠を見つけます

太陽系の外側にある架空の大きな物体である惑星Xの探索は、何十年にもわたって人間を魅了してきました。その検索の最新の章は、地球の10倍の大きさで、公転周期が15であるほど遠くにある惑星を指しています。

キャムニュートン、ゴッドダム

キャムニュートン、ゴッドダム

カムニュートンは昨日、簡単な265ヤードと3回のタッチダウンでファルコンズを引き裂き、別の素晴らしいゲームをしました。その日のハイライトは、上のタッチダウンスローでした。これは、視聴するたびにばかげているだけです。

米国のフィギュア スケートは、チーム イベントでの最終決定の欠如に「苛立ち」、公正な裁定を求める

米国のフィギュア スケートは、チーム イベントでの最終決定の欠如に「苛立ち」、公正な裁定を求める

ロシアのフィギュアスケーター、カミラ・バリエバが関与したドーピング事件が整理されているため、チームは2022年北京冬季オリンピックで獲得したメダルを待っています。

Amazonの買い物客は、わずか10ドルのシルクの枕カバーのおかげで、「甘やかされた赤ちゃんのように」眠れると言っています

Amazonの買い物客は、わずか10ドルのシルクの枕カバーのおかげで、「甘やかされた赤ちゃんのように」眠れると言っています

何千人ものAmazonの買い物客がMulberry Silk Pillowcaseを推奨しており、現在販売中. シルクの枕カバーにはいくつかの色があり、髪を柔らかく肌を透明に保ちます。Amazonで最大46%オフになっている間にシルクの枕カバーを購入してください

パデュー大学の教授が覚醒剤を扱った疑いで逮捕され、女性に性的好意を抱かせる

パデュー大学の教授が覚醒剤を扱った疑いで逮捕され、女性に性的好意を抱かせる

ラファイエット警察署は、「不審な男性が女性に近づいた」という複数の苦情を受けて、12 月にパデュー大学の教授の捜査を開始しました。

コンセプト ドリフト: AI にとって世界の変化は速すぎる

コンセプト ドリフト: AI にとって世界の変化は速すぎる

私たちの周りの世界と同じように、言語は常に変化しています。以前の時代では、言語の変化は数年または数十年にわたって発生していましたが、現在では数日または数時間で変化する可能性があります。

SF攻撃で91歳のアジア人女性が殴られ、コンクリートに叩きつけられた

犯罪擁護派のオークランドが暴力犯罪者のロミオ・ロレンゾ・パーハムを釈放

SF攻撃で91歳のアジア人女性が殴られ、コンクリートに叩きつけられた

認知症を患っている 91 歳のアジア人女性が最近、47 番街のアウター サンセット地区でロメオ ロレンゾ パーハムに襲われました。伝えられるところによると、被害者はサンフランシスコの通りを歩いていたところ、容疑者に近づき、攻撃を受け、暴行を受けました。

ℝ

“And a river went out of Eden to water the garden, and from thence it was parted and became into four heads” Genesis 2:10. ? The heart is located in the middle of the thoracic cavity, pointing eastward.

メリック・ガーランドはアメリカに失敗しましたか?

バイデン大統領の任期の半分以上です。メリック・ガーランドは何を待っていますか?

メリック・ガーランドはアメリカに失敗しましたか?

人々にチャンスを与えることは、人生で少し遅すぎると私は信じています。寛大に。

Language