Loading article…
命題論理では、命題式は整形式な構文式の一種です。命題式内のすべての変数の値が与えられると、一意の真理値が決定されます。命題式は、命題表現、文、[ 1 ]または文式とも呼ばれます。
命題論理式は、「5は3より大きい」などの単純な命題、またはpやqなどの命題変数から、NOT、AND、OR、IMPLIESなどの論理演算子や接続詞を用いて構築されます。例：
数学において、命題式はしばしば「命題」と簡潔に呼ばれるが、より正確には、命題式は命題そのものではなく、命題、すなわち議論の対象となる形式的な対象を表す形式的な表現である。ちょうど「x + y」のような表現が値そのものではなく、値を表すのと同様である。場合によっては、この区別を維持することが重要となることもある。
命題論理の目的上、命題（発話、文、主張）は単純命題または複合命題のいずれかであると考えられています。[ 2 ]複合命題は文接続詞によって連結されていると考えられており、最も一般的なものとしては「AND」、「OR」、「IF ... THEN ...」、「NEITHER ... NOR ...」、「... IS EQUIVALENT TO ...」などがあります。連結セミコロン「;」と接続詞「BUT」は「AND」の表現であると考えられています。離散文のシーケンスは「AND」によって連結されていると考えられており、形式分析では単純命題のシーケンスに関して再帰的な「括弧規則」が適用されます（整形式式については後述を参照）。
単純な命題は宣言的な性質を持ち、特定の感覚対象の状態や性質について断言します。例えば、「この牛は青い」、「コヨーテがいる！」（「あのコヨーテは岩の後ろにいる」）。[ 3 ]したがって、単純な「原始的な」断言は、特定の対象または特定の心の状態に関するものでなければなりません。それぞれに少なくとも主語（思考または観察の直接の対象）、動詞（能動態で現在形が望ましい）、そしておそらく形容詞または副詞が必要です。「犬！」はおそらく「私は犬を見る」という意味ですが、曖昧すぎるため却下されるべきです。
命題論理においては、複合命題は通常、一連の単純な文に言い換えることができるが、その結果は恐らく不自然に聞こえるだろう。
述語論理は命題論理よりもさらに一歩進んで「命題の内部構造の分析」を行う[ 4 ]。単純な文を(i)主語(談話の目的語(単数または複数))と(ii)述語(目的語の性質や属性を主張する動詞または動詞節)の2つの部分に分解する。次に、述語論理は「主語|述語」形式(|は記号の連結(紐付け)を表す)を次の空白主語構造「___|述語」を持つ形式に一般化し、述語は今度はその性質を持つすべてのものに一般化される。
「この豚」を「翼のあるもの」と「青いもの」という2つのクラスの（潜在的な）メンバーに一般化するということは、この豚がこれら両方のクラスと真理関係を持つことを意味します。言い換えれば、 「翼のあるもの」という議論領域が与えられた場合、p はこの領域のメンバーであるか、そうでないかのどちらかです。したがって、p（豚）と { T, F } の間には関係 W（翼性）があり、W(p) は { T, F } と評価されます。ここで、{ T, F } はブール値「真」と「偽」の集合です。同様に、B（青さ）と p（豚）と { T, F } についても、B(p) は { T, F } と評価されます。したがって、関連する主張「B(p) AND W(p)」の全体的な真理値を分析することができます。
特に、「すべて」、「いくつか」、「少数」、「1つ」などの論理量化子を用いる単純な文は、述語論理によって扱われます。新しい関数記号「F(x)」とともに、2つの新しい記号、∀（すべてについて）、および∃（…が存在する、…のうち少なくとも1つが存在するなど）が導入されます。述語論理は、命題論理とは異なり、次の文の形式的妥当性を確立できます。
タルスキは、同一性の概念（論理的同値性とは区別される）は命題論理の外にあると主張しているが、論理が数学や科学に役立つためには、同一性の「理論」を含まなければならないと指摘している。[ 5 ]この拡張を強調するために、「同一性を持つ述語論理」という表現を用いる著者もいる。これについては後述を参照のこと。
代数（様々な種類がある）とは、大まかに言えば、変数と呼ばれる記号の集合と、括弧（, ）などの記号、そして*、+、~、&、∨、=、≡、∧、￢などの記号のサブセットを、規則体系の中で操作する方法である。これらの記号、およびそれらの整列した文字列は、対象を表すとされるが、特定の代数体系においては、これらの対象には意味がない。したがって、代数内部での作業は、記号の意味論（意味）ではなく、代数の構文（記号形成）の特定の法則（規則）に従う作業となる。意味は代数の外部で見出される。
代数における整然とした記号の列（数式）が、代数以外の分野で何らかの有用性を持つためには、記号に意味が割り当てられ、最終的に変数に値が割り当てられます。そして、一連の規則によって数式が評価されます。
値が2つだけに限定され、命題結合子によって連結された単純な文（例えば、話し言葉や書き言葉）の概念に適用される場合、この記号、規則、評価方法からなる代数システム全体は、通常、命題論理または文論理と呼ばれます。
算術代数の馴染みのある規則の中には、命題代数においても引き続き成り立つもの（例えば、ANDとORの交換法則と結合法則）がある一方で、成り立たないもの（例えば、 AND、OR、NOTの分配法則）もある。
分析：演繹的推論では、哲学者、修辞学者、数学者は議論を数式に還元し、その後、（通常は真理値表を用いて）その正しさ（健全性）を検証します。例えば、次の議論は健全でしょうか？
エンジニアは、合成技術を用いて設計した論理回路を解析し、その後、さまざまな削減・最小化技術を適用して設計を簡素化する。
合成: 特にエンジニアは、真理値表から命題論理式（最終的には記号の回路となる）を合成します。たとえば、変数「b」と「a」、および「carry_in」、「ci」、結果「carry_out」、「co」、および「sum」Σが与えられた場合の二項加算の動作に関する真理値表を作成することができます。
最も単純な命題式は命題変数です。単純な（原子的な）記号表現の命題は、 p、q、またはP、Qなどの名前の変数で表されることがよくあります。命題変数は、「今日は土曜日です」= p （ここで記号=は「...に...という名前の変数が割り当てられます」を意味します）や「私は月曜日にしか映画に行きません」= qのような原子命題（主張）を表すことを目的としています。
命題論理式の評価は、各変数に真偽値を割り当てることから始まります。各変数は単純な文を表すため、これらの単純な文の「真」または「偽」に対して真偽値が適用されることになります。
修辞学、哲学、数学における真理値
真理値は { 真理 "T", 虚偽 "F" } の 2 つだけです。経験論者は、すべての命題を 2 つの大きなクラスに分類します。分析命題— 何があっても真である命題 (例:トートロジー) と、総合命題— 経験から導き出され、第三者による確認が可能な命題 (意味の検証理論) です。[ 6 ]経験論者は、一般的に、総合命題の真理値に到達するには、まず意味 (パターン マッチング テンプレート) を単語に適用し、次にこれらの意味テンプレートを主張されているものと照合する必要があると主張します。たとえば、私の発言「あの牛は青い！」は真理でしょうか? 確かに私はそう言いました。そして、私は青い牛を見ているのかもしれません。私が嘘をついていない限り、私の発言は私の (おそらく欠陥のある) 知覚の対象に関して真理です。しかし、青い牛は「本当にそこに」いるのでしょうか? 同じ窓から外を見ると、何が見えますか?検証を進めるには、「牛」と「青」の両方に関する事前概念（テンプレート）と、それらのテンプレートを感覚の対象（もし存在するならば）と照合する能力が必要です。
工学における真理値
エンジニアは哲学者を悩ませる真偽の概念を避けようとしますが、最終的には測定機器を信頼しなければなりません。堅牢性を追求する中で、エンジニアは、大規模な組み合わせでも明確に定義され予測可能な動作を持つ、小さなライブラリから既知のオブジェクトを取り出すことを好みます（そのため、命題論理を「組み合わせ論理」と呼びます）。単一のオブジェクトの最小の動作は 2 つ（例：{ OFF、ON }、{ open、shut }、{ UP、DOWN } など）であり、これらは { 0、1 } に対応付けられます。このような要素はデジタルと呼ばれ、連続的な動作範囲を持つものはアナログと呼ばれます。アナログ システムで決定を下す必要がある場合、多くの場合、エンジニアは比較器を使用してアナログ動作（ドアは 45.32146% UP ）をデジタル（例：DOWN=0）に変換します。[ 7 ]
したがって、変数と 2 つの値記号 { 0, 1 } の意味の割り当ては、（通常は）複合オブジェクトの挙動を表す式の「外部」から行われます。例として、2 つの「リミットスイッチ」を備えたガレージドアが挙げられます。1 つは上昇用で SW_U とラベル付けされ、もう 1 つは下降用で SW_D とラベル付けされています。その他、ドアの回路にはさまざまな部品があります。回路（図または実際のオブジェクト自体 - ドア、スイッチ、配線、回路基板など）を調べると、回路基板上で、スイッチ「SW_D」の接点が機械的に接触（「閉じている」）し、ドアが「下降」位置（95% 下降）にあるときに「ノード 22」が +0 ボルトになり、ドアが 95% 上昇し、スイッチ SW_U の接点が機械的に接触（「閉じている」）しているときに「ノード 29」が +0 ボルトになることがわかります。[ 8 ]エンジニアは、これらの電圧の意味と、考えられるすべての組み合わせ（4つすべて）を定義しなければなりません。これには、「悪い」組み合わせ（たとえば、ノード22と29の両方が0ボルトの場合、ドアが開いていると同時に閉じていることを意味します）も含まれます。回路は、真実か虚偽か、正しいか間違っているか、安全か危険かといったことを一切認識せずに、経験する電圧に無意識に反応します。
任意の命題式は、命題変数と他の命題式を命題結合子を用いて組み合わせることで構築されます。結合子の例としては、以下のようなものがあります。
以下は、修辞学、哲学、数学に共通する論理結合子と、それらの真理値表です。使用される記号は、著者や分野によって異なります。一般的に、「T」と「F」は、命題式の変数に適用される真偽の評価を表します（例えば、「その牛は青い」という主張は、真であれば「T」、偽であれば「F」という真理値を持ちます）。
接続詞には様々な言い回しがあり、例えば「a IMPLIES b」は「IF a THEN b」とも言われます。これらの例の一部を表に示します。
一般的に、工学の論理結合子は数学の論理結合子とほぼ同じですが、「1」=「T」、「0」=「F」で評価される傾向があります。これは、最小項とカルノー図の概念を使用して、分析/最小化と式の合成を行う目的で行われます（下記参照）。エンジニアはまた、ブールの概念（a*a = a）の論理積とジェボンズの概念（a+a = a）の論理和という言葉も使用します。[ 9 ]
IF ... THEN ... ELSE ... という接続詞は、再帰理論と計算理論の CASE 演算子の最も単純な形式として現れ、条件付き goto (ジャンプ、分岐) を担当する接続詞です。この 1 つの接続詞から他のすべての接続詞を構築できます (詳細は後述)。「IF c THEN b ELSE a」は含意のように聞こえますが、最も簡略化された形式では、決定を下し、結果として「a」または「b」の 2 つの選択肢のうちの 1 つだけを提供する switch です (そのため、C言語ではswitch 文という名前が付けられています)。 [ 10 ]
以下の３つの命題は同値である（論理同値記号≡で示される）。
したがって、IF ... THEN ... ELSE は、含意とは異なり、最初の命題が偽の場合、つまり (c → b) において c = F の場合には、曖昧な「真」に評価されません。たとえば、ほとんどの人は、 2 番目の文が最初の文と意味的に関連していないため、次の複合命題を意味のない論理的飛躍として拒否するでしょう。 [ 11 ]
この問題を認識して、命題論理における形式的含意の記号 → は、日常的な直観的含意と区別するために、実質的含意と呼ばれる。 [ a ]
IF ... THEN ... ELSE 構造の使用は、明示された 2 つの選択肢の間で完全に決定論的な選択を提供するので論争を回避します。2 つの「オブジェクト (2 つの選択肢 b と a) を提供し、それらを網羅的かつ明確に選択します。 [ 13 ]下の真理値表では、d1 は式 ( (IF c THEN b) AND (IF NOT-c THEN a) ) です。その完全に簡略化された形式 d2 は式 ( (c AND b) OR (NOT-c AND a) ) です。列 "=d1" と "=d2" で示されているように、2 つの式は同等です。電気技師は、完全に簡略化された式を AND-OR-SELECT 演算子と呼びます。CASE (または SWITCH) 演算子は、同じアイデアをn個の可能なが相互に排他的な結果に拡張したものです。電気技師は、CASE 演算子をマルチプレクサと呼びます。
このセクションの最初の表では、「論理的同値性」が「同一性」と同じではないことを注意するために、項目「論理的同値性」に星印***を付けています。たとえば、「その牛は青い」という主張は、「その牛は青い」という主張と同一であるとほとんどの人が同意するでしょう。一方、論理的同値は、次の例のように、会話の中で現れることがあります。「『太陽が輝いている』は『私は自転車に乗っている』を意味する」命題論理式に翻訳すると、次のようになります。「『太陽が輝いている』ならば『私は自転車に乗っている』、そして『私は自転車に乗っている』ならば『太陽が輝いている』」[ 14 ]
論理的同値を表す記号は著者によって異なり、↔（例：サップス、グッドスタイン、ハミルトン）、≡（例：ロビン）、⇔（例：ベンダーとウィリアムソン）などがあります。通常、同一性は等号 = で表されます。この規則の例外は『プリンキピア・マテマティカ』に見られます。同一性の概念の哲学については、ライプニッツの法則を参照してください。
前述のように、タルスキは同一性を命題論理の外にあると考えているが、その概念がなければ「論理」は数学や演繹科学には不十分であると主張している。実際、記号は数式を評価する際に命題論理に現れる。[ 15 ]
システムによっては真理値表がなく、形式的な公理（例えば、集合 { ~, →, (, ) からの記号列、変数 p 1 , p 2 , p 3 , ... }）と式形成規則（例えば、置換やモーダス・ポネンスを用いて、以前の記号列からさらに記号列を作成する方法に関する規則）のみが存在する。このような計算の結果は、別の式（つまり、整形式の記号列）となる。しかし、最終的に、妥当性や真理の概念を研究するために計算を使用したい場合は、「真理値」と呼ばれる記号 {T, F}（または {1, 0} など）の振る舞いを他の記号との関係で定義する公理を追加する必要がある。
例えば、ハミルトンは、自身の「形式的命題計算」Lにおいて、任意の整形式論理式（wff）AおよびBの評価値vの概念を定義する際に、=と≠という2つの記号を使用しています。評価値vは、wff内の各変数p1、p2 、p3に任意の真理値{T、F}が割り当てられている場合、彼のシステムLのwffから範囲（出力）{T 、F}への関数です。
定義（i）と（ii）は、彼のシステムの~（否定）および→（含意）結合子の真理値表に相当するものを定義する。最初の定義はF≠TおよびT≠Fを導出する。言い換えれば、「v（A ）はv（~ A ）を意味 しない」。定義（ii）は真理値表の3行目を指定し、残りの3行は定義（i）の適用から得られる。特に、（ii）は式全体に値F（または「F」の意味）を割り当てる。これらの定義は、以前に導出された値を式に代入することを可能にする形成規則としても機能する。
一部の形式体系では、矛盾法則や同一性・無効性といった特定の公式の形で、これらの評価公理を最初に規定します。交換法則や分配法則などとともに、どの公式を使用するかは、公理の集合が完全である限り（つまり、体系内で作成されたあらゆる整形式公式を形成し、評価するのに十分である限り）、体系の設計者に委ねられます。
上記のように、CASE (IF c THEN b ELSE a) という接続詞は、2 引数の接続詞 IF ... THEN ... と AND から、または OR と AND と 1 引数 NOT から構成されます。n 引数の AND (a & b & c & ... & n)、OR (a ∨ b ∨ c ∨ ... ∨ n) などの接続詞は、2 引数の AND と OR の文字列から構成され、括弧なしで省略形で記述されます。これらの接続詞やその他の接続詞は、さらに別の接続詞の構成要素として使用できます。修辞学者、哲学者、数学者は、真理値表とさまざまな定理を使用して、数式を分析して簡略化します。
電気工学では、描かれた記号を線で結び、数学的な置換や置き換えを表します。そして、真理値表を用いて図を検証し、カルノー図や定理を用いて式を簡略化します。このようにして、エンジニアは「デコーダ」、「エンコーダ」、「多機能ゲート」、「多数決論理」、「バイナリ加算器」、「算術論理演算装置」など、フィードバックのない「組み合わせ論理」（つまり、フィードバックのない接続器）を数多く生み出してきました。
定義は、多くの場合省略の目的で、新しい記号とその動作を作成します。定義が提示されると、同等の記号または式のどちらの形式も使用できます。次の記号体系 = Dfは、ライヘンバッハの慣例に従っています。[ 16 ]記号セット { ~、&、(、) } と変数から抽出された便利な定義の例をいくつか示します。各定義は、置換または置き換えに使用できる論理的に同等の式を生成します。
上記のOR、含意、XOR、および論理等価性の定義は、実際にはスキーマ（または「スキーマタ」）であり、一般的な数式形式のモデル（デモンストレーション、例）ですが、（説明のために）変数に特定の文字a、b、cを使用して示されています。ただし、文字の置換が以下の置換規則に従う限り、任意の変数文字をその場所に配置できます。
置換：別の変数、定数、または部分式に置換される変数または部分式は、全体の式全体を通してすべての箇所で置き換えられなければなりません。
置換: (i) 置換される式は同義反復、つまり置換される式と論理的に同等（≡ または ↔ で接続）でなければならず、(ii) 置換とは異なり、置換は 1 箇所 (つまり 1 つの式) でのみ発生することが許容されます。
命題論理の古典的な表現（Enderton 2002を参照）では、結合子を使用します。与えられた命題変数集合上の論理式の集合は、帰納的に、以下の条件を満たす最小の式の集合として定義される。
この帰納的な定義は、他の接続詞にも容易に拡張できる。
帰納的定義は、閉包演算の観点からも言い換えることができる（Enderton 2002）。Vを命題変数の集合とし、X V をVに含まれる記号、左括弧と右括弧、および検討対象のすべての論理結合子を含むアルファベットからのすべての文字列の集合とする。各論理結合子は、 XX VからXX Vへの関数である式構築演算に対応する。
V上の式の集合は、Vを含み、すべての式構築操作に関して閉じているXX Vの最小の部分集合として定義される。
命題論理の以下の「法則」は、複雑な論理式を「簡約化」するために用いられます。これらの「法則」は真理値表を用いて容易に検証できます。各法則において、主（最外側）の論理結合子は、論理的同値性≡または同一性=に対応します。n個の異なる変数に対する2ⁿ通りの真理値の組み合わせをすべて分析すると、この結合子の下に1（T）の列が現れます。この結果から、各法則は定義上、恒真式となります。また、与えられた法則については、左辺と右辺の論理式が等価（または同一）であるため、互いに置き換えることができます。
意欲的な読者は、記号 { ∨ 、 &、 ~、 (、 )、変数 a、 b、 c }、上記で指定した形成規則、および以下に列挙した法則のうちできるだけ少ないものを使用して「公理系」を考案し、残りの法則と∨ 、 &、および ~の真理値表の評価を定理として導出するという課題に挑戦するかもしれない。ハンティントン (1904) (Suppes:204) に帰属するあるセットは、以下に定義された 8 つの法則を使用している。
公理系で使用される場合、記号 1 と 0 (または T と F) は整形式式とみなされ、変数と同じ規則をすべて満たします。したがって、以下に列挙する法則は実際には公理図式であり、無限の数のインスタンスの代わりとなります。したがって、あるインスタンスでは ( x ∨ y ) ≡ ( y ∨ x )、別のインスタンスでは ( p ∨ 0 ) ≡ ( 0 ∨ p )、また別のインスタンスでは ( 1 ∨ q ) ≡ ( q ∨ 1 ) などが使用される可能性があります。
一般的に、命題式の分析や評価の際に混乱を避けるために、括弧を多用することができます。しかし、著者は括弧を省略することが非常に多いです。複雑な式を解析するには、まず各接続詞（* を除く）が他の接続詞に対して持つ優先順位、つまりランクを知る必要があります。式を「整形式」にするには、最もランクの高い接続詞から始めて、その構成要素を括弧で囲み、次にランクを下げていきます（接続詞が作用する範囲に細心の注意を払います）。最も優先順位の高いものから最も低いものへ、述語記号 ∀x と ∃x、IDENTITY =、および算術記号を完全性のために追加します。[ b ]
したがって、この式は解析できますが、NOT は分配法則に従わないため、内部の式 (~c & ~d) を囲む括弧は必須です。
AND および OR の文字列で括弧を省略する場合: これらの接続詞は、単項 (1 変数、例: NOT) および二項 (2 変数 AND、OR、IMPLIES) とみなされます。例:
しかし、真理値表による証明によれば、余分な括弧のない形式でも全く問題ないことがわかる。
単一変数の NOT に関して括弧を省略する場合: a が単一変数の場合 ~(a) は完全に明確ですが、~a で十分であり、このリテラルは通常このように表示されます。 NOT が複数の記号を含む式に対して行われる場合は、括弧が必須です。例: ~(a ∨ b)。
ORはANDに対して分配法則を満たし、ANDはORに対して分配法則を満たします。NOTはANDまたはORに対して分配法則を満たしません。ド・モルガンの法則については下記を参照してください。
NOT を OR または AND に分散させると、奇妙な動作をします (これも真理値表で確認できます)。
吸収、特に最初の吸収は、論理の「法則」を算術の「法則」と異なるものにする。
記号「 = " （論理等価性≡、または↔や⇔とは区別される）は、値または意味の割り当てを象徴します。したがって、文字列(a & ~(a))は「0」を象徴します。つまり、記号「0」と同じ意味です。一部の「システム」では、これは公理（定義）として( (a & ~(a)) = Df 0 )のように示されます。他のシステムでは、以下の真理値表で導出される場合があります。
式の重要な特性の一つは、命題変数と論理結合子の観点から式の構造を一意に解析できることです。上記のように中置記法で式を記述する場合、式の定義において括弧を適切に使用することで、一意の可読性が確保されます。あるいは、括弧を全く必要としないポーランド記法または逆ポーランド記法で式を記述することもできます。
前節で述べた中置構文の帰納的定義は、バッカス・ナウア記法の形式文法に変換することができる。
<式> ::= <命題変数> | ( ¬ <式> ) | ( <数式> ∧ <数式> ) | ( <数式> ∨ <数式> ) | ( <数式> → <数式> ) | ( <数式> ↔ <数式> ) 文法に一致する式は、左括弧と右括弧の数が均衡しており、式の空でない先頭部分は右括弧よりも左括弧が多いことが示せる。[ 18 ]この事実は、式を解析するアルゴリズムを与えるために使用できる。たとえば、式x が次のように始まると仮定する。2番目の記号の後に、括弧のバランスが取れているxの最短部分式yを照合します。xが式の場合、この式の後にはちょうど1つの記号が残ります。この記号は閉じ括弧であり、y自体が式です。この考え方は、式の再帰下降構文解析器を生成するために使用できます。
括弧の数え方の例：
この方法は、最も外側の括弧（省略されることが多い）について式の全体的な評価が行われる結合子である主結合子を「 1」として特定します。 [ 19 ]また、真理値表を使用せずに式の評価を開始する最も内側の結合子、たとえば「レベル6」を特定します。
妥当な議論という概念は通常、議論における推論に適用されますが、議論は命題論理式に還元され、他の命題論理式と同様に評価できます。ここで妥当な推論とは、「推論を表す論理式は、その主結合子の下で、変数にどのような真理値が割り当てられても「真理」と評価される」、つまり論理式がトートロジーであることを意味します。[ 20 ] 論理式は整形式であっても妥当でない場合があります。別の言い方をすれば、「論理式が妥当であるためには整形式であることは必要条件ですが、十分条件ではありません」。論理式が整形式かつ妥当であるかどうかを調べる唯一の方法は、真理値表または「法則」を用いて検証することです。
論理結合子の集合は、すべての命題式がその集合に含まれる結合子のみを含む式と同値である場合に完全であると呼ばれる。結合子の完全な集合は多数あり、、、 そして2つの二項結合子は、それぞれNANDとNORに対応し、それ自体で完結している。[ 21 ]一部のペアは完結していない。例えば。
NANDに対応する二項結合子はシェファーストロークと呼ばれ、縦棒|または縦矢印↑で表されます。この結合子の完全性は『プリンキピア・マテマティカ』（1927年：xvii）で指摘されています。それ自体で完全であるため、他のすべての結合子は、このストロークのみを使用して表現できます。たとえば、記号「≡」が論理的同値性を表す場合：
特に、ゼロ項結合子（真実を表す）そして（虚偽を表す）は、以下のストロークで表現できます。
この結合子は { 0, 1 }、(または { F, T }または {、} ) は完全な集合を形成します。以下では、IF...THEN...ELSE関係(c, b, a) = d は ( (c → b) ∨ (~c → a) ) ≡ ( (c & b) ∨ (~c & a) ) = d を表します。
例：以下は、「(c, b, 1) ≡ (c → b)」の定理に基づく証明の進め方を示しており、証明の下に真理値表による検証結果が示されています。（注：(c → b) は(~c ∨ b)と定義されます）
以下の真理値表において、「taut」とラベル付けされた列は、dとラベル付けされた2つの列間の論理的同値性（ここでは≡で表される）を評価します。「taut」の下の4つの行すべてが1であるため、この同値性は確かに同値性を表しています。
任意の命題論理式は非常に複雑な構造を持つ場合があります。そのため、より単純な形式、すなわち正規形と呼ばれる形式を用いる方が便利な場合が多くあります。一般的な正規形には、連言正規形と選言正規形があります。どの命題論理式も、連言正規形または選言正規形に簡約することができます。
式の真理値表が準備できれば、正規形への還元は比較的簡単です。しかし、リテラルの数を最小限に抑えるためのさらなる試み（下記参照）には、いくつかのツールが必要です。ド・モルガンの法則と真理値表による還元は扱いにくい場合がありますが、カルノー図は少数の変数（5以下）に非常に適しています。複数の出力を持つより複雑な回路には、洗練された表形式の方法が存在しますが、これらはこの記事の範囲外です。詳細については、クワイン・マクラスキーアルゴリズムを参照してください。
電気工学では、変数 x またはその否定 ~(x) はリテラルと呼ばれます。AND で接続されたリテラルの列は項と呼ばれ、OR で接続されたリテラルの列はオルタムと呼ばれます。通常、リテラル ~(x) は ~x と略記されます。代数乗算のように、& 記号が完全に省略される場合もあります。
2 n行の真理値表が、変数の2 n 個の可能な値すべてに対する命題論理式の評価を表示するのと同様に、n 個の変数は 2 n個の正方形のカルノー図を生成します (完全な次元で描画することはできません)。たとえば、3 つの変数は 2 3 = 8 行と 8 つのカルノー図正方形を生成します。4 つの変数は 16 行の真理値表と 16 個の正方形、したがって 16 個の最小項を生成します。各カルノー図正方形とそれに対応する真理値表の評価は、1 つの最小項を表します。
任意の命題論理式は、有効な（つまり「1」または「T」の値をとる）最小項の「論理和」（OR）に還元できる。この形式の場合、論理式は選言標準形であると言われる。しかし、この形式であっても、項数またはリテラル数に関して必ずしも最小化されているとは限らない。
次の表では、行の番号付けが独特であることに注目してください。(0, 1, 3, 2, 6, 7, 5, 4, 0)。最初の列は、数字「cba」の2進数表現の10進数表現です。つまり、次のようになります。
この番号付けは、表を1行ずつ下に移動していくと、一度に1つの変数の値しか変化しないという事実に基づいています。グレイコードはこの概念から派生したものです。この概念は、ハッセ図と呼ばれる3次元および4次元の超立方体にも拡張できます。ハッセ図では、立方体の辺を一周すると、各角の変数が一度に1つずつ変化します。ハッセ図（超立方体）を2次元に平面化すると、ヴェイチ図またはカルノー図になります（これらは実質的に同じものです）。
カルノー図を扱う際には、常に上端が下端に「回り込み」、左端が右端に回り込むことを念頭に置いておく必要があります。つまり、カルノー図は実際には3次元、4次元、あるいはn次元の平面化されたオブジェクトなのです。
Veitchは円を隣接する正方形に変換することでベン図の概念を改良し、Karnaughは最小項を文字形式（例：~abc~d）で記述して数値に変換することでVeitch図を簡略化した。[ 22 ]この方法は次のように進む。
式の真理値表を作成します。n個の変数については、各変数の2進数表現（通常は0からn-1まで）を用いて行番号を付けます。
例：((c & d) ∨ (p & ~(c & (~d)))) = q の連言標準形は次のようになります。
しかし、この式は項の数（4から3へ）とリテラルの総数（12から6へ）の両方において削減できる。
真理値表法で求めた式の値（例：「p」）を、それぞれの（関連する）カルノー図（グレイコード規則に従って番号が付けられている）に配置します。表に「気にしない」を表す「d」の値が含まれている場合、削減段階での柔軟性が高まります。
隣接する（接する）1-正方形（T-正方形）の最小項は、そのリテラルの数に関して削減することができ、その過程で項の数も削減されます。2つの隣接する正方形（2 x 1の水平方向または1 x 2の垂直方向、辺も隣接する正方形を表す）は1つのリテラルを失い、4 x 1の長方形（水平方向または垂直方向）または2 x 2の正方形（4つの角も隣接する正方形を表す）の4つの正方形は2つのリテラルを失い、長方形の8つの正方形は3つのリテラルを失う、など。（最大の正方形または長方形を探し出し、その中に完全に含まれるより小さな正方形または長方形は無視します。）このプロセスは、すべての隣接する正方形が考慮されるまで続き、その時点で命題式が最小化されます。
例えば、正方形3と7が隣接しているとします。この隣接する2つの正方形は、それぞれ1つのリテラル（例えば、正方形3と7から「p」）を削除できます。長方形または正方形内の4つの正方形は2つのリテラルを削除し、長方形内の8つの正方形は3つのリテラルを削除します。（最大の正方形または長方形を探します。）このプロセスは、隣接するすべての正方形が考慮されるまで続き、その時点で命題論理式が最小化されたと言われます。
例：マップ法は通常、目視で行われます。次の例では、代数的方法を拡張して、カルノー図上で項を組み合わせる際の「コツ」を示します。
冪等法則 (A ∨ A) = A により、さらに多くの項を作成できることに注意してください。次に、結合法則と分配法則により、消去する変数をペアにし、矛盾法則 (x & ~x)=0 で「消去」することができます。以下では、角括弧 [ と ] は項を追跡するためだけに使用されており、特別な意味はありません。
以下の例を定義として挙げた場合、その後の推論をどのように解釈すべきでしょうか？
次に、左端の文「この文は単純です」に変数「s」を代入します。「複合」c = 「単純ではない」~s と定義し、「この文は複合です」に c = ~s を代入します。「この文は AND で結合されています」に「j」を代入します。2 番目の文は次のように表現できます。
文 c = ~s と j に真偽値を割り当てると、明らかにすべて偽となります。例えば、「この文は複雑である」は偽です（定義上、単純です）。したがって、それらの論理積（AND）は偽となります。しかし、組み立てられた形で考えると、この文は真となります。
これは、非述語的定義から生じるパラドックスの一例です。つまり、対象 m が特性 P を持つが、対象 m が特性 P によって定義されている場合です。[ 23 ]修辞学者や演繹分析に携わる人にとって最善のアドバイスは、非述語的定義を避けることですが、同時に、それらが実際にパラドックスを生み出す可能性があるため、注意を払う必要があります。一方、エンジニアは、フィードバック付きの命題式という形でそれらを活用します。
命題式が自身の変数の1つとして現れるという概念は、その式を変数に割り当てることを可能にする形成規則を必要とする。一般に、これが起こることを禁じる規定（公理系または真理値表の対象と関係の体系）はない。[ 24 ]
最も単純なケースは、OR 式が自身の入力の 1 つになる場合です。たとえば、p = q です。 (p ∨ s) = q から始めて、p = q とします。q の「定義」は、s と OR 結合子だけでなく、q 自身にも依存していることに注意してください。したがって、q のこの定義は非述語的です。次の 2 つの条件のいずれかが結果として発生する可能性があります。[ 25 ]振動または記憶。
数式をブラックボックスとして考えると理解しやすくなります。数式という「箱」の「内部」で何が起こっているのかを外部から知らなければ、出力は入力のみの関数ではないように見えます。つまり、qを見ると0になることもあれば、1になることもあるのです。この問題を回避するには、箱の中にある「隠れた」変数pの状態（つまり、qの値がフィードバックされてpに割り当てられる値）を知る必要があります。これが分かれば、見かけ上の矛盾は解消されます。
フィードバックを持つ論理式の挙動を理解（予測）するには、より高度な順序回路の解析が必要となる。フィードバックを持つ命題論理式は、最も単純な形では状態機械につながり、またチューリングテープやカウンタマシンのカウンタといったメモリにもつながる。これらの要素を組み合わせることで、あらゆる種類の限定された計算モデル（例えば、チューリングマシン、カウンタマシン、レジスタマシン、マッキントッシュコンピュータなど）を構築することができる。
抽象的（理想的）な場合、最も単純な振動式は、自身にフィードバックされる NOT です。~(~(p=q)) = q。真理値表で抽象的（理想的）命題式を分析すると、p=1 と p=0 の両方の場合で矛盾が明らかになります。p=1 の場合、q=0 ですが、これは p=q であるからではありません。p=0 で q=1 の場合も同様です。
遅延を伴う振動：抽象式に遅延[ 26 ]（理想的または非理想的）がpとqの間に挿入されると、pは1と0の間で振動します：101010...101...無限に。遅延とNOTのいずれかが抽象的でない場合（つまり理想的でない場合）、使用する分析の種類は、発振器を構成するオブジェクトの正確な性質に依存します。このようなことは数学の範囲外であり、工学の領域になります。
解析には遅延を挿入し、その遅延と入力「p」の間のループを切断する必要があります。遅延は、入力「q」に対して出力「qd」（q遅延）を持つ一種の命題とみなす必要があります。この新しい命題は真理値表に別の列を追加します。矛盾は赤色で示されているように「qd」と「p」の間に生じ、結果として2つの安定状態が生じます。
真理値表分析から矛盾を速やかに排除しなければならない。「遅延」という概念では、この条件はフィードバック出力変数 q と p = q delayedの間の瞬間的な矛盾として現れる。
真理値表は、入力で遅延されたp = q と出力で q の間に矛盾が生じる行を明らかにします。フィードバックを「破壊」した後、[ 27 ]真理値表の構築は従来の方法で進められます。しかしその後、各行で出力 q が独立入力 p と比較され、p と q の間の矛盾が記録されます (つまり、p=0 と q=1、または p=1 と q=0 です)。「ライン」が「再構築」されると、矛盾法則 ~(p & ~p)) により両方とも不可能になります。矛盾を示す行は、一時的な状態とみなされるか、矛盾しているため「不可能」として単に排除されます。
最も単純なメモリの例としては、OR演算の出力が入力の1つにフィードバックされる場合が挙げられます。この場合、出力「q」が「p」にフィードバックされます。式が最初に評価（初期化）され、p=0、q=0となると、s=1で「設定」されたときに一度「反転」します。その後、出力「q」は「反転」状態（状態q=1）で「q」を維持します。この動作は時間依存となり、1回反転した状態の右側にある状態図に示されています。
次に単純なケースは、ワンスフリップの下に示した「セットリセット」フリップフロップです。初期状態でr=0、s=0、q=0の場合、ワンスフリップと同様の方法で「セット」（s=1）されます。ただし、「r」=1のときにq=0を「リセット」する機能があります。さらに、set=1とreset=1の両方の場合、複雑な問題が発生します。この式では、set=1によって出力q=1が強制されるため、(s=0 & r=1)の場合にフリップフロップはリセットされます。または、(s=1 & r=0)の場合にフリップフロップはセットされます。s=1 ⇒ s=0 & r=1 ⇒ r=0が同時に成り立つ抽象的な（理想的な）ケースでは、式qは不確定（決定不能）になります。実際のOR、AND、NOTの遅延により、結果は最初は不明ですが、その後は予測可能になります。
「クロック付きフリップフロップ」メモリ（「c」は「クロック」、「d」は「データ」）と呼ばれる式を以下に示します。動作原理は次のとおりです。c = 0 の場合、データ d（0 または 1）は出力 q に影響を与えることができません。c = 1 の場合、データ d は出力 q に影響を与え、出力 q は d の値に追従します。c が 1 から 0 に変化すると、データの最後の値は出力 q に「捕捉」されたままになります。c = 0 である限り、d の値は q を変化させることなく変更できます。
状態図はフリップフロップの状態図と形状は似ているが、遷移のラベル付けが異なっている。
バートランド・ラッセル（1912:74）は、アリストテレスに由来する思考の3つの法則を挙げている。（1）同一性の法則：「存在するものはすべて存在する」、（2）矛盾律：「何物も存在し、かつ存在しないということはあり得ない」、（3）排中律：「すべては存在するか、存在しないかのどちらかである」。
排中律において「すべて」という言葉が使われているため、ラッセルのこの法則の表現は議論の余地がある。有限個の対象（有限の「議論の宇宙」）に関する存在または性質についての表現に限定し、その対象を一つずつ調べて主張の有無を確認できる場合、この法則は直観主義的に適切であると考えられる。したがって、「この対象は（その集合において）存在するか存在しないかのどちらかである」または「この対象はこの性質を持つか持たないかのどちらかである（その集合内の対象に関して）」といった主張は受け入れられる。詳しくはベン図を参照。
命題論理はアリストテレスに端を発するものの、命題に代数の概念を適用するという考え方は19世紀初頭まで待たなければならなかった。アリストテレスの三段論法の2000年にわたる伝統に対する（否定的な）反動として、ジョン・ロックは『人間知性論』（1690年）の中で記号論（記号の使用に関する理論）という言葉を用いた。1826年までに、リチャード・ホワットリーはロックの記号論に共感しながら三段論法を批判的に分析した。ジョージ・ベンサムの研究（1827年）は「述語の量化」（1827年）（今日では∀≡「すべての」と表記される）という概念をもたらした。ウィリアム・ハミルトンがオーガスタス・ド・モーガンとの優先権争いをめぐって引き起こした「論争」が、ジョージ・ブールに論理学に関する自身の考えをまとめさせ、1847年に『MAL（Mathematical Analysis of Logic）』として出版するきっかけとなった（Grattin-Guinness and Bornet 1997:xxviii）。
彼の貢献について、グラッタン＝ギネスとボルネは次のように述べている。
ゴットロープ・フレーゲの膨大な研究（1879年）は、命題の形式的計算体系を生み出したが、その記号体系はあまりにも難解であったため、バートランド・ラッセルを除いてほとんど影響を与えなかった。ラッセルは、アルフレッド・ノース・ホワイトヘッドの弟子としてフレーゲの研究に取り組み、フレーゲの理論に見られる矛盾（ラッセルのパラドックス参照）の問題をめぐって、（有名かつ悪名高い）修正案（1904年）を提示した。ラッセルの研究はホワイトヘッドとの共同研究につながり、1912年に『プリンキピア・マテマティカ』（PM）の第1巻が刊行された。ここで、私たちが「現代」命題論理と考えるものが初めて登場した。特に、PMではNOTとOR、そして主張記号⊦が基本概念として導入されている。これらの概念に関して、彼らは含意を次のように定義します → (定義 *1.01: ~p ∨ q )、次に AND (定義 *3.01: ~(~p ∨ ~q) )、次に等価性 p ←→ q (*4.01: (p → q) & ( q → p ) )。
計算およびスイッチングロジック：
{{cite book}}ISBN /日付の不一致（ヘルプ）
ウィキメディア・コモンズにある命題論理式に関連するメディア