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

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

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは、夫に会ったとき、典型的な交際のアドバイスに逆らいました。

マイケルシーンが非営利の俳優である理由

マイケルシーンが非営利の俳優である理由

マイケルシーンは非営利の俳優ですが、それは正確にはどういう意味ですか?

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

特徴的なスターのコリン・エッグレスフィールドは、RomaDrama Liveでのスリル満点のファンとの出会いについて料理しました!加えて、大会での彼のINSPIREプログラム。

「たどりつけば」をオンラインでストリーミングできない理由

「たどりつけば」をオンラインでストリーミングできない理由

ノーザンエクスポージャーが90年代の最も人気のある番組の1つになった理由を確認するには、Blu-rayまたはDVDプレーヤーをほこりで払う必要があります。

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

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

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

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖は、世界で2番目に大きいボイリング湖です。そこにたどり着くまでのトレッキングは大変で長いですが、努力する価値は十分にあります。

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

サロンからのヘアトリミングや個人的な寄付は、油流出を吸収して環境を保護するのに役立つマットとして再利用できます。

ホワイトハウスの最も記憶に残る結婚式を見てください

ホワイトハウスの最も記憶に残る結婚式を見てください

過去200年以上の間にホワイトハウスで結婚したのはほんの数人です。彼らは誰でしたか、そしてそこで結婚式を獲得するために何が必要ですか?

驚くほど素晴らしいDropMixミュージックミキシングカードゲームは30ドルで驚くべき取引です

驚くほど素晴らしいDropMixミュージックミキシングカードゲームは30ドルで驚くべき取引です

DropMixはNFC対応のカードゲームで、基本的にはリミックスアーティストになります。現在、Amazonでは$ 30まで下がっており、これまでで最高の価格に匹敵します。ロックバンドで有名なHarmonixによって開発されたDropMixは、おそらく少し野心的すぎるように思われます。結局のところ、ほとんどの人は素晴らしいリズムを持っていませんが、ゲームは驚くほどうまく実行されます。

メアリーJ.ブライジがついにハリウッドウォークオブフェイムスターを獲得

メアリーJ.ブライジがついにハリウッドウォークオブフェイムスターを獲得

写真:APメアリーJ.ブライジは、間もなくハリウッドウォークオブフェイムのスターを獲得します。これは、メアリーJよりもハリウッドウォークオブフェイムのほうが正直なところ恩恵です。

MeltdownとSpectreの脆弱性についてこれまでに知っていることはすべて、簡単な方法で説明されています

MeltdownとSpectreの脆弱性についてこれまでに知っていることはすべて、簡単な方法で説明されています

画像:グラズ工科大学/ NataschaEiblがデザインしたロゴ。MeltdownとSpectreは、攻撃者がシステムメモリに保存されているあらゆる種類の情報にアクセスできるようにする2つの脆弱性に付けられた名前です。

彼のニューヨークの家から追い出されようとしている97歳の第二次世界大戦の獣医。メリーエフィングクリスマス

彼のニューヨークの家から追い出されようとしている97歳の第二次世界大戦の獣医。メリーエフィングクリスマス

日本人に襲われたときに真珠湾にいた97歳の第二次世界大戦のベテランが、ニューヨークのブルックリンから追い出されています。

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya shared a sweet photo in honor of boyfriend Tom Holland's 26th birthday Wednesday

小さな女性:脳卒中を患った後に病院から解放されたアトランタのジューシーな赤ちゃん:「まだ癒し」

小さな女性:脳卒中を患った後に病院から解放されたアトランタのジューシーな赤ちゃん:「まだ癒し」

シーレン「Ms.JuicyBaby」ピアソンは、先月脳卒中で入院した後、「もう一度たくさんのことをする方法を学ばなければならない」ため、言語療法を受けていることを明らかにしました。

エマストーンは彼女のクリフサイドマリブビーチハウスを420万ドルでリストアップしています—中を見てください!

エマストーンは彼女のクリフサイドマリブビーチハウスを420万ドルでリストアップしています—中を見てください!

オスカー受賞者の世紀半ばの家には、3つのベッドルーム、2つのバス、オーシャンフロントの景色があります。

ジーニー・メイ・ジェンキンスは、母乳育児の経験の中で、彼女は「本当に、本当に落ち込んでいる」と言います

ジーニー・メイ・ジェンキンスは、母乳育児の経験の中で、彼女は「本当に、本当に落ち込んでいる」と言います

ジーニー・メイ・ジェンキンスは、生後4か月の娘、モナコに母乳育児をしていると語った。

投資ノート:Bioscout AU$300万シード

投資ノート:Bioscout AU$300万シード

Bioscoutは、農家を運転席に置くという使命を負っています。Artesian(GrainInnovate)やUniseedと並んで、最新のシードラウンドでチームを支援できることをうれしく思います。問題真菌症による重大な作物の損失は、農民にとって試練であることが証明されています。

リトルマーケットリサーチ1| 2022年のクイックグリンプス遠隔医療市場

リトルマーケットリサーチ1| 2022年のクイックグリンプス遠隔医療市場

遠隔医療は、パンデミック後の時代では新しいものではなく、時代遅れの分野でもありません。しかし、業界を詳しく見ると、需要と供給の強力な持続可能性と、米国で絶え間ない革命となる強力な潜在的成長曲線を示しています。

スタートアップ資金調達環境:タイのスタートアップエコシステムの次は何ですか?

スタートアップ資金調達環境:タイのスタートアップエコシステムの次は何ですか?

2021年は、世界的なベンチャーキャピタル(VC)の資金調達にとって記録的な年でした。DealStreetAsiaによると、東南アジアも例外ではなく、この地域では年間で記録的な25の新しいユニコーンが採掘されました。

ムーアの法則を超えて

ムーアの法則を超えて

計算に対する私たちの欲求とムーアの法則が提供できるものとの間には、指数関数的に増大するギャップがあります。私たちの文明は計算に基づいています—建築と想像力の現在の限界を超える技術を見つけなければなりません。

Language