命題式

命題論理において、命題式は、適切に形成された構文式の一種です。命題式内のすべての変数の値が与えられた場合、一意の真理値が決まります。命題式は、命題表現、文、文式とも呼ばれます。

命題式は、「5 は 3 より大きい」などの単純な命題、またはpやqなどの命題変数から、NOT、AND、OR、IMPLIES などの接続詞または論理演算子を使用して構築されます。次に例を示します。

( p AND NOT q ) は ( p OR q ) を意味します。

数学では、命題式はしばしば「命題」と略されるが、より正確には、命題式は命題ではなく、命題、つまり議論中の形式的なオブジェクトを表す形式的な表現である。これは、「x + y」などの表現が値ではなく、値を表すのと同じである。文脈によっては、この区別を維持することが重要になることがある。

命題論理学の目的上、命題（発話、文、主張）は単純か複合かのいずれかであると考えられる。^[1]複合命題は文接続詞によって結合されていると考えられ、最も一般的なものは「AND」、「OR」、「IF ... THEN ...」、「NEITHER ... NOR ...」、「... IS EQUIVALENT TO ...」などである。接続セミコロン「;」および接続詞「BUT」は「AND」の表現であると考えられる。離散文のシーケンスは「AND」によって結合されていると考えられ、形式分析は単純命題のシーケンスに関して再帰的な「括弧ルール」を適用する（整形式の式については以下を参照）。

たとえば、「この牛は青い。あの馬はオレンジ色だが、この馬は紫色だ」という主張は、実際には「AND」で結び付けられた複合命題です: ( (「この牛は青い」AND「あの馬はオレンジ色だ」) AND「この馬は紫色だ」) 。

単純な命題は、本質的に宣言的である。つまり、感覚の特定の対象の状態や性質について断言する。たとえば、「この牛は青い」、「コヨーテがいる！」（「あのコヨーテは岩の後ろにいる」）。 ^[2]したがって、単純な「原始的な」断言は、特定の対象または特定の心の状態に関するものでなければならない。それぞれに、少なくとも主語（思考または観察の直接の対象）、動詞（能動態と現在時制が望ましい）、そしておそらく形容詞または副詞が含まれている必要がある。「犬！」はおそらく「犬が見える」という意味だが、曖昧すぎるため拒否されるべきである。

例: 「あの紫色の犬は走っています」「この牛は青いです」「スイッチ M31 は閉じています」「このキャップは外れています」「明日は金曜日です」。

命題論理の目的上、複合命題は通常、一連の単純な文に言い換えることができますが、その結果はおそらく堅苦しく聞こえるでしょう。

述語計算は命題計算よりも一歩進んで「命題の内部構造の分析」を行います^[3]。これは単純な文を (i) 主語 (談話の目的語 (単数または複数)) と (ii) 述語(目的語の性質または属性を主張する動詞または動詞節) の 2 つの部分に分解します。次に、述語計算は「主語|述語」形式 (| は記号の連結(連続) を表す) を次の空白主語構造「___|述語」に一般化し、次に述語をその特性を持つすべてのものに一般化します。

例: 「この青いブタには翼がある」は、命題論理では 2 つの文になります。「このブタには翼がある」AND「このブタは青い」ですが、その内部構造は考慮されません。対照的に、述語論理では、最初の文は主語として「このブタ」、述語として「翼がある」に分かれます。したがって、オブジェクト「このブタ」は「翼のあるもの」のクラス (集合、コレクション) のメンバーであると主張します。2 番目の文は、オブジェクト「このブタ」に「青」という属性があり、したがって「青いもの」のクラスのメンバーであると主張します。AND で接続された 2 つの文を次のように記述することもできます。

p|W かつ p|B

「この豚」を「羽のあるもの」と「青いもの」という 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)」の全体的な真理値を分析できます。つまり、次のようになります。

( B(p) AND W(p) ) は { T, F } と評価される。

特に、論理量指定子と呼ばれる「すべて」、「いくつか」、「いくつか」、「1 つ」などの概念を使用する簡単な文は、述語計算によって処理されます。新しい関数記号「F(x)」とともに、2 つの新しい記号が導入されました。 ∀ (すべてに対して)、および ∃ (... が存在する、... の少なくとも 1 つが存在するなど)。述語計算は、命題計算とは異なり、次のステートメントの形式的な妥当性を確立できます。

「青い豚はすべて翼を持っていますが、翼のない豚もいます。そのため、青くない豚もいます」。

タルスキは、同一性の概念（論理的同値性とは区別される）は命題論理の範囲外であると主張する。しかし、論理が数学や科学に有用であるためには、同一性の「理論」を含まなければならないと指摘している。^[4]一部の著者は、この拡張を強調するために「同一性を伴う述語論理」に言及している。これについては以下で詳しく説明する。

代数（さまざまな代数があります）は、大まかに定義すると、変数と呼ばれる記号のコレクションと、括弧（、）などの他の記号、および *、+、~、&、∨、=、≡、∧、￢ などの記号のサブセットを規則のシステム内で操作する方法です。これらの記号、およびそれらの整形式の文字列はオブジェクトを表すと言われていますが、特定の代数システムでは、これらのオブジェクトには意味がありません。したがって、代数の内部での作業は、記号の意味論（意味）ではなく、代数の構文（記号形成）の特定の法則（規則）に従う演習になります。意味は代数の外部にあります。

代数における整形式の記号列、つまり式が代数の外部で何らかの有用性を持つためには、記号に意味が割り当てられ、最終的に変数に値が割り当てられ、その後一連の規則によって式が評価されます。

値が 2 つだけに制限され、命題接続詞で結び付けられた単純な文 (たとえば、口頭の発話や書面の主張) の概念に適用される場合、この記号と規則および評価方法の代数システム全体は、通常、命題計算または文計算と呼ばれます。

算術代数のよく知られた規則のいくつかは命題代数でも引き続き有効ですが (たとえば、AND と OR の交換法則と結合法則)、いくつかは有効ではありません (たとえば、AND、OR、NOT の 分配法則)。

分析:演繹的推論では、哲学者、修辞学者、数学者は議論を公式にまとめ、その正しさ (妥当性) を (通常は真理値表を使用して) 検証します。たとえば、次の議論は妥当でしょうか?

「人工知能には意識が十分であり、意識を持つ存在だけがチューリングテストに合格できることを考えると、ロボットが人工知能であると結論付ける前に、ロボットはチューリングテストに合格する必要があります。」

エンジニアは、合成技術を使用して設計した論理回路を分析し、さまざまな削減および最小化技術を適用して設計を簡素化します。

合成: 特にエンジニアは、真理値表から命題式 (最終的には記号の回路になる) を合成します。たとえば、変数「b」と「a」および「carry_in」「ci」の加算と、結果「carry_out」「co」「sum」Σ が与えられた場合、 2 進加算がどのように動作するかを示す真理値表を記述できます。

• 例: 5 行目では、( (b+a) + ci ) = ( (1+0) + 1 ) = 数値「2」です。これを 2 進数で表すと 10 ₂となり、右端の列に示すように「co」=1、Σ=0 となります。

最も単純な命題式は命題変数です。単純な (アトミックな) 記号表現である命題は、多くの場合、 p、q、またはP、Qなどの名前の変数で表されます。命題変数は、アトミック命題 (主張) を表すためのもので、たとえば、「今日は土曜日です」 = p (ここで、記号 = は「... に ... という名前の変数が割り当てられている」という意味です) や、「私は月曜日にだけ映画を見に行きます」 = qなどです。

命題式の評価は、各変数に真理値を割り当てることから始まります。各変数は単純な文を表すため、真理値はこれらの単純な文の「真」または「偽」に適用されます。

修辞学、哲学、数学における真理値

真理値は 2 つしかありません: { 真理 "T", 偽り "F" }。経験主義者は、すべての命題を 2 つの広いクラスに分類します:分析的- 何があろうとも真 (例:トートロジー)、および合成的- 経験から導き出されたもので、第三者による確認を受けやすい (意味の検証理論)。 ^{[5]経験主義者は、一般に、}合成命題の真理値に到達するには、意味 (パターン マッチング テンプレート) を最初に単語に適用し、次にこれらの意味テンプレートを主張されている内容と照合する必要があると考えています。たとえば、私の発言「あの牛は青い!」は真実でしょうか? 本当にそう言いました。そして、青い牛を見ているのかもしれません。私が嘘をついていない限り、私の発言は私の (おそらく欠陥のある) 知覚の対象に対して真実です。しかし、青い牛は「本当にそこに」いるのでしょうか? 同じ窓から外を見ると何が見えますか?検証を進めるには、「牛」と「青」の両方の事前の概念（テンプレート）と、そのテンプレートを感覚の対象（実際に存在する場合）と照合する能力が必要になります。^{[引用が必要]}

工学における真理値

エンジニアは哲学者を悩ませる真偽の概念を避けようとしますが、最終的には計測機器を信頼しなければなりません。エンジニアは堅牢性を求めて、小さなライブラリから既知のオブジェクト、つまり大きな組み合わせでも明確に定義され、予測可能な動作を持つオブジェクトを好みます (これが命題計算の「組み合わせ論理」と呼ばれる理由です)。単一のオブジェクトの最小の動作は 2 つ (例: { OFF、ON }、{ open、shut }、{ UP、DOWN } など) であり、これらは { 0、1 } に対応付けられます。このような要素はデジタルと呼ばれ、動作の範囲が連続している要素はアナログと呼ばれます。アナログ システムで決定を下す必要があるときはいつでも、エンジニアはコンパレータを使用してアナログ動作 (ドアは 45.32146% UP) をデジタル動作 (例: DOWN=0) に変換することがよくあります。^[6]

したがって、変数と 2 つの値シンボル { 0, 1 } の意味の割り当ては、(通常は) 複合オブジェクトの動作を表す式の「外部」から行われます。例として、ガレージ ドアがあります。このドアには、2 つの「リミット スイッチ」があり、1 つは UP 用でラベルは SW_U、もう 1 つは DOWN 用でラベルは SW_D です。ドアの回路には他にもさまざまなものがあります。回路 (図または実際のオブジェクト自体、つまりドア、スイッチ、配線、回路基板など) を調べると、回路基板の「ノード 22」は、スイッチ「SW_D」の接点が機械的に接触 (「閉じている」) し、ドアが「下」の位置 (95% 下) にあるときに +0 ボルトになり、「ノード 29」は、ドアが 95% UP でスイッチ SW_U の接点が機械的に接触 (「閉じている」) しているときに +0 ボルトになることがわかります。^[7]エンジニアは、これらの電圧の意味と、すべての可能な組み合わせ（4つすべて）を定義する必要があります。これには「悪い」もの（たとえば、ノード22と29の両方が0ボルトの場合、ドアが同時に開いていて閉じていることを意味します）も含まれます。回路は、真実か虚偽か、正しいか間違っているか、安全か危険かといったことを意識することなく、経験する電圧に無意識に反応します。^{[引用が必要]}

任意の命題式は、命題変数と命題接続詞を使用した他の命題式から構築されます。接続詞の例には次のものがあります。

• 単項否定接続詞。 が式であれば、 は式です。${\displaystyle \alpha }$${\displaystyle \lnot \alpha }$
• 古典的な二項接続詞。したがって、たとえば、と が式である場合、 も式です。${\displaystyle \land ,\lor ,\to ,\leftrightarrow }$${\displaystyle \alpha }$${\displaystyle \beta }$${\displaystyle (\alpha \to \beta )}$
• NAND、NOR、XORなどの他のバイナリ接続子
• 三項接続詞 IF ... THEN ... ELSE ...
• 定数 0 項接続子 ⊤ と ⊥ (または、定数 { T, F }、{ 1, 0 } など)
• 「理論拡張」接続子 EQUALS（または、IDENTITY、または「論理接続子」と区別される記号「 = 」）${\displaystyle \leftrightarrow }$

以下は修辞学、哲学、数学に共通する接続詞とその真理値表です。使用される記号は著者や研究分野によって異なります。一般に、略語「T」と「F」は命題式の変数に適用される評価「真」と「偽」を表します (たとえば、「その牛は青い」という主張は、状況に応じて真理値「T」が真実、「F」が偽となります)。

接続詞にはさまざまな語法があり、たとえば「a IMPLIES b」は「IF a THEN b」とも言います。これらのいくつかを表に示します。

一般的に、工学接続詞は数学接続詞とまったく同じですが、評価が「1」=「T」および「0」=「F」となる傾向があります。これは、最小項とカルノー図の概念を使用して、式の分析/最小化と合成を目的として行われます(以下を参照)。エンジニアは、ブールの概念から論理積(a*a = a)、ジェヴォンズの概念から論理和(a+a = a) という単語も使用します。^[8]

IF ... THEN ... ELSE ... 結合子は、再帰理論と計算理論の CASE 演算子の最も単純な形式として現れ、条件付き goto (ジャンプ、分岐) を担う結合子です。この 1 つの結合子から、他のすべての結合子を構築できます (詳細は以下を参照)。「IF c THEN b ELSE a」は含意のように聞こえますが、最も簡略化された形式では、決定を下し、結果として 2 つの選択肢「a」または「b」のいずれか 1 つだけを提供するスイッチです (そのため、Cプログラミング言語ではswitch 文と呼ばれます)。^[9]

次の3つの命題は同等です（論理等価記号 ≡ で示されます）。

1. ( IF 'カウンタがゼロ' THEN '命令bへ進む' ELSE '命令aへ進む') ≡
2. ( (c → b) & (~c → a) ) ≡ ( ( IF 'カウンターがゼロ' THEN '命令bへ進む' ) AND ( IF 'カウンターがゼロではない' THEN '命令aへ進む) " ≡
3. ( (c & b) ∨ (~c & a) ) ≡ " ( 'カウンタはゼロ' AND '命令bに進む ) または ( 'カウンタはゼロ' AND '命令aに進む ) ではない"

したがって、IF ... THEN ... ELSE は、含意とは異なり、最初の命題が偽である場合、つまり c = F in (c → b) の場合、あいまいな「真実」に評価されません。たとえば、ほとんどの人は、次の複合命題を無意味な非論理的命題として拒否します。なぜなら、 2 番目の文は最初の文と意味的につながっていないからです。 ^[10]

例: 「『ウィンストン・チャーチルは中国人だった』ならば『太陽は東から昇る』」という命題は、「ウィンストン・チャーチルは中国人だった」が虚偽で、「太陽は東から昇る」が真実であると評価されるため、真実であると評価されます。

この問題を認識して、命題論理における形式的含意の記号→は、日常的な直観的含意と区別するために、質的含意と呼ばれます。 ^[a]

IF ... THEN ... ELSE 構文を使用すると、2 つの明示された選択肢の間で完全に決定論的な選択が提供されるため、論争を回避できます。つまり、2 つの「オブジェクト」(2 つの選択肢 b と a) が提供され、それらの間で網羅的かつ明確に選択されます。 ^[12]以下の真理値表で、d1 は式: ( (IF c THEN b) AND (IF NOT-c THEN a) ) です。その完全に簡約された形式 d2 は式: ( (c AND b) OR (NOT-c AND a) ) です。2 つの式は、列 "=d1" と "=d2" で示されるように同等です。電気技師は、完全に簡約された式を AND-OR-SELECT 演算子と呼びます。CASE (または SWITCH) 演算子は、同じアイデアをn 個の可能なが相互に排他的な結果に拡張したものです。電気技師は CASE 演算子をマルチプレクサと呼びます。

このセクションの最初の表では、論理的等価性の項目に星印を付けて、「論理的等価性」は「同一性」と同じではないことを指摘しています。たとえば、「あの牛は青い」という主張は、「あの牛は青い」という主張と同一であることにほとんどの人が同意するでしょう。一方、論理的等価性は、次の例のように会話の中に現れることがあります。「「太陽が輝いている」は「私は自転車に乗っている」という意味です」この単語を命題式に翻訳すると、「IF '太陽が輝いている' THEN '私は自転車に乗っている'、そして IF '私は自転車に乗っている' THEN '太陽が輝いている'」となります。^[13]

「IF 's' THEN 'b' AND IF 'b' THEN 's'」は、((s → b) & (b → s)) と書かれるか、省略形では (s ↔ b) と書かれます。右端のシンボル文字列は、左側のシンボルに関する新しいシンボルの定義であるため、IDENTITY 記号 = の使用が適切です。

((s → b) & (b → s)) = (s ↔ b)

論理的等価性を表す記号は著者によって異なり、↔ (例: Suppes、Goodstein、Hamilton)、≡ (例: Robbin)、≡ (例: Bender と Williamson) などがあります。通常、同一性は等号 = で表されます。この規則の例外がPrincipia Mathematicaにあります。同一性の概念の哲学については、ライプニッツの法則を参照してください。

上で述べたように、タルスキは同一性は命題論理の範囲外にあると考えているが、その概念がなければ「論理」は数学や演繹科学には不十分であると主張している。実際、記号は式を評価するときに命題論理に登場してくる。^[14]

いくつかのシステムでは真理値表は存在せず、形式的な公理 (例えば、集合 { ~, →, (, )、変数 p ₁、 p ₂、 p _{3 、... } からの記号の文字列) と式形成規則 (例えば、置換や}可能性法を使用して、以前の文字列からさらに記号文字列を作成する方法に関する規則) のみが存在する。このような計算の結果は、別の式 (つまり、整形式の記号文字列) となる。ただし、最終的に、計算を使用して妥当性と真実性の概念を研究する場合は、「真理値」{T、F} (または {1、0} など) と呼ばれる記号の振る舞いを他の記号と比較して定義する公理を追加する必要がある。

たとえば、ハミルトンは、彼の「形式ステートメント計算」L で任意の整形式式(wff) AとBの評価値 vの概念を定義するときに、2 つの記号 = と ≠ を使用します。評価値vは、 wff 内の各変数 p ₁、 p ₂、 p ₃に任意の真理値 { T、 F } が割り当てられていることを前提として、彼のシステム L の wff から範囲 (出力) { T 、 F } への関数です。

2 つの定義 ( i ) と ( ii ) は、彼のシステムの ~ (NOT) および → (IMPLICATION) 接続詞の真理値表と同等のものを定義します。最初の定義は、 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は、ライヘンバッハの慣例に従っています。^[15]記号セット { ~、&、(、) } と変数から引き出された便利な定義の例。各定義は、置換または置き換えに使用できる論理的に同等の式を生成します。

• 新しい変数の定義: (c & d) = _Df s
• または: ~(~a & ~b) = _Df (a ∨ b)
• 意味: (~a ∨ b) = _Df (a → b)
• XOR: (~a & b) ∨ (a & ~b) = _Df (a ⊕ b)
• 論理的同値性: ( (a → b) & (b → a) ) = _Df ( a ≡ b )

上記の OR、IMPLICATION、XOR、および論理的等価性の定義は、実際にはスキーマ(または「スキーマ」) です。つまり、これらは一般的な数式形式のモデル(デモンストレーション、例) ですが、(説明目的で) 変数に特定の文字 a、b、c を使用して示されています。ただし、文字の置換が以下の置換規則に従っている限り、任意の変数文字をその場所に配置できます。

例: 定義 (~a ∨ b) = _Df (a → b) では、「SW2」や「CON1」などの他の変数記号が使用される場合があります。つまり、正式には次のようになります。

a = _Df SW2、b = _Df CON1なので、定義スキーマのインスタンスとして(~SW2 ∨ CON1) = _Df (SW2 → CON1)となります。

置換: 別の変数、定数、またはサブ式に置換される変数またはサブ式は、全体の式全体のすべてのインスタンスで置換される必要があります。

例: (c & d) ∨ (p & ~(c & ~d)) ですが、(q1 & ~q2) ≡ d です。変数 "d" が現れる箇所には、必ず (q ₁ & ~q ₂ ) を代入します。

(c & (q ₁ & ~q ₂ )) ∨ (p & ~(c & ~(q ₁ & ~q ₂ )))

置換: (i) 置換される式はトートロジー内にある必要があります。つまり、置換する式と論理的に同等(≡または↔で接続)でなければなりません。また、(ii) 置換とは異なり、置換は 1 か所(つまり、1 つの式) でのみ実行できます。

例: 次の数式スキーマ/同等性のセットを使用します。

1. ( (a ∨ 0) ≡ a )。
2. ( (a & ~a) ≡ 0 )。
3. ( (~a ∨ b) = _Df (a → b) )。
6. ( ~(~a) ≡ a )

1. 「a」で始まる: a
2. 1 を使用して「a」を (a ∨ 0) に置き換えます: (a ∨ 0)
3. 「スキーマ」の概念を使用して、2のaをbに置き換えます：((a & ~a)≡0)
4. 2を使用して0を(b & ~b)に置き換えます: ( a ∨ (b & ~b) )
5. （「a ∨」を（b & ~b）などに分配する方法については以下を参照してください。）

命題論理の古典的な表現（Enderton 2002 を参照）では、接続詞を使用します。与えられた命題変数の集合に対する式の集合は、次のような式の最小の集合として帰納的に定義されます。 ${\displaystyle \lnot ,\land ,\lor ,\to ,\leftrightarrow }$

• 集合内の各命題変数は式であり、
• ${\displaystyle (\lnot \alpha )}$は、が常に式であり、${\displaystyle \alpha }$
• ${\displaystyle (\alpha \,\Box \,\beta )}$は、と が式である場合は常に式であり、は二項接続詞の 1 つです。${\displaystyle \alpha }$${\displaystyle \beta }$${\displaystyle \Box }$${\displaystyle \land ,\lor ,\to ,\leftrightarrow }$

この帰納的定義は、追加の接続詞をカバーするように簡単に拡張できます。

帰納的定義は、閉包操作という観点から言い換えることもできます(Enderton 2002)。V は命題変数の集合を表し、X _{V は}V内の記号、左括弧と右括弧、および検討中のすべての論理接続子を含むアルファベットのすべての文字列の集合を表します。各論理接続子は、 XX _VからXX _Vへの関数である式構築操作に対応します。

• 文字列zが与えられると、この操作はを返します。${\displaystyle {\mathcal {E}}_{\lnot }(z)}$${\displaystyle (\lnot z)}$
• 文字列yとz が与えられると、この演算はを返します。他の二項接続詞に対応する同様の演算、、があります。${\displaystyle {\mathcal {E}}_{\land }(y,z)}$${\displaystyle (y\land z)}$${\displaystyle {\mathcal {E}}_{\lor }}$${\displaystyle {\mathcal {E}}_{\to }}$${\displaystyle {\mathcal {E}}_{\leftrightarrow }}$

V上の式の集合は、V を含み、すべての式構築操作に対して閉じている XX _Vの最小の部分集合として定義されます。

命題計算の次の「法則」は、複雑な式を「簡約」するために使用されます。これらの「法則」は、真理値表で簡単に検証できます。各法則について、主要な (最も外側の) 接続詞は、論理的同値 ≡ または同一性 = に関連付けられています。n個の異なる変数の真理値のすべての 2 ^{n の}組み合わせを完全に分析すると、この接続詞の下に 1 (T) の列が表示されます。この結果から、各法則は定義上トートロジーになります。また、特定の法則について、左側と右側の式が同等 (または同一) であるため、互いに置き換えることができます。

• 例: 次の真理値表は、OR に対する NOT の動作に関するド・モルガンの法則です: ~(a ∨ b) ≡ (~a & ~b)。主接続子 ≡ (「taut」というラベルの付いた黄色の列) の左側では、式 ~(b ∨ a) はラベル「P」の下で (1, 0, 0, 0) と評価されます。「taut」の右側では、式 (~(b) ∨ ~(a)) もラベル「Q」の下で (1, 0, 0, 0) と評価されます。2 つの列の評価は同等であるため、「taut」の下の論理的等価性 ≡ は (1, 1, 1, 1) と評価されます (つまり、P ≡ Q)。したがって、どちらかの式がより大きな式に現れる場合は、もう一方の式を置き換えることができます。

意欲的な読者は、記号 { ∨、&、~、(、)、変数 a、b、c }、上記の形成規則、および以下に列挙する法則をできるだけ少なく使用した「公理系」を考案し、残りの法則と ∨、&、および ~ の真理値表値を定理として導出することに挑戦するかもしれません。Huntington (1904) (Suppes:204) による 1 つのセットでは、以下に定義される法則のうち 8 つが使用されています。

公理系で使用される場合、記号 1 と 0 (または T と F) は整形式の式であると見なされ、変数と同じ規則に従います。したがって、以下にリストされている法則は実際には公理スキーマであり、つまり、無限の数のインスタンスの代わりになります。したがって、あるインスタンスでは ( x ∨ y ) ≡ ( y ∨ x ) が使用され、別のインスタンスでは ( p ∨ 0 ) ≡ ( 0 ∨ p ) が使用され、別のインスタンスでは ( 1 ∨ q ) ≡ ( q ∨ 1 ) などが使用されます。

一般に、命題式の分析と評価の際の混乱を避けるために、括弧を多用することができます。しかし、著者が括弧を省略するケースも少なくありません。複雑な式を解析するには、まず、各接続子（* を除く）が他の接続子に対して持つ優先順位、つまりランクを知る必要があります。式を「適切に形成」するには、最高ランクの接続子から始めて、その構成要素を括弧で囲み、次にランクを下げていきます（接続子が機能する範囲に細心の注意を払います）。最も優先順位の高いものから最も優先順位の低いものまで、述語記号 ∀x と ∃x、IDENTITY =、および完全性のために算術記号を追加します。^[b]

≡

（論理的等価性）

→

（含意）

＆

（そして）

∨

（または）

〜

（ない）

∀x

（全員 x）

∃x

(x が存在します)

=

（身元）

+

（算術和）

*

（算術乗算）

'

(s、算術後継者)。

したがって、式は解析できますが、NOT は分配法則に従わないため、内部の式 (~c & ~d) を囲む括弧は必須です。

例: 「 d & c ∨ w 」を書き直すと ( (d & c) ∨ w ) となります。

例: 「 a & a → b ≡ a & ~a ∨ b 」を書き直すと（厳密には）

• ≡ は先順位である: ( ( a & a → b ) ≡ ( a & ~a ∨ b ) )
• → は先順位である: ( ( a & (a → b) ) ≡ ( a & ~a ∨ b ) )
• & は両辺とも上位関係にあります: ( ( ( (a) & (a → b) ) ) ≡ ( ( (a) & (~a ∨ b) ) )
• ~ は先順位である: ( ( ( (a) & (a → b) ) ) ≡ ( ( (a) & (~(a) ∨ b) ) )
• 9 ( -括弧と9 ) -括弧を確認してください: ( ( ( (a) & (a → b) ) ) ≡ ( ( (a) & (~(a) ∨ b) ) )

例：

d & c ∨ p & ~(c & ~d) ≡ c & d ∨ p & c ∨ p & ~d を書き直すと ( ( (d & c) ∨ ( p & ~((c & ~(d)) ) ) ) ≡ ( (c & d) ∨ (p & c) ∨ (p & ~(d)) ) )

AND と OR はどちらも交換法則と結合法則に従います。

• OR の交換法則: ( a ∨ b ) ≡ ( b ∨ a )
• AND の交換法則: ( a & b ) ≡ ( b & a )
• OR の結合法則: (( a ∨ b ) ∨ c ) ≡ ( a ∨ (b ∨ c) )
• AND の結合法則: (( a & b ) & c ) ≡ ( a & (b & c) )

AND および OR の文字列で括弧を省略する: 接続子は単項 (1 つの変数、例: NOT) および二項 (つまり、2 つの変数 AND、OR、IMPLIES) とみなされます。例:

上記の ( (c & d) ∨ (p & c) ∨ (p & ~d) ) は、 ( ((c & d) ∨ (p & c)) ∨ (p & ~(d) ) ) または ( (c & d) ∨ ( (p & c) ∨ (p & ~(d)) ) ) と書く必要があります。

しかし、真理値表のデモンストレーションでは、余分な括弧のない形式が完全に適切であることが示されています。

単一変数 NOT に関する括弧の省略: a が単一変数である場合、~(a) は完全に明らかですが、~a で十分であり、このリテラルは通常このように表示されます。NOT が複数の記号を含む式上にある場合、括弧は必須です (例: ~(a ∨ b))。

OR は AND に分配され、AND は OR に分配されます。NOT は AND または OR に分配されません。ド・モルガンの法則については以下を参照してください。

• OR の分配法則: ( c ∨ ( a & b) ) ≡ ( (c ∨ a) & (c ∨ b) )
• AND の分配法則: ( c & ( a ∨ b) ) ≡ ( (c & a) ∨ (c & b) )

NOT は、OR または AND に分散されると、特異な動作をします (これも真理値表で確認できます)。

• OR に関するド・モルガンの法則: ¬(a ∨ b) ≡ (¬a ^ ¬b)
• AND に関するド・モルガンの法則: ¬(a ^ b) ≡ (¬a ∨ ¬b)

吸収、特に最初の吸収により、論理の「法則」が算術の「法則」と異なるようになります。

• OR の吸収（べき等性）: (a ∨ a) ≡ a
• AND の吸収（べき等性）: (a & a) ≡ a

記号「 = 」（論理的等価性 ≡、交互に ↔ または ≡ と区別）は、値または意味の割り当てを表します。したがって、文字列 (a & ~(a)) は「0」を表します。つまり、記号「0」と同じ意味になります。一部の「システム」では、これはおそらく ( (a & ~(a)) = _Df 0 ) として示される公理（定義）になります。他のシステムでは、以下の真理値表で導出される場合があります。

• 等式の交換: (a = b) ≡ (b = a)
• OR の恒等式: (a ∨ 0) = a または (a ∨ F) = a
• AND の恒等式: (a & 1) = a または (a & T) = a
• OR の無効性: (a ∨ 1) = 1 または (a ∨ T) = T
• AND の無効性: (a & 0) = 0 または (a & F) = F
• OR の補語: (a ∨ ~a) = 1 または (a ∨ ~a) = T、排中律
• AND の補数: (a & ~a) = 0 または (a & ~a) = F、背理法則

• ¬(¬a) ≡ a

数式の重要な特性は、命題変数と論理接続子の観点から数式の構造を決定するために一意に解析できることです。上記のように、数式が中置記法で記述されている場合、数式の定義で括弧を適切に使用することで、一意の可読性が保証されます。あるいは、数式をポーランド記法または逆ポーランド記法で記述して、括弧をまったく必要としないようにすることもできます。

前のセクションの挿入式の帰納的定義は、バッカスナウア形式の形式文法に変換できます。

<式>  ::=  <命題変数> 
| ( ¬ <式> )
| ( <式> ∧ <式> )
| ( <式> ∨ <式> )
| ( <式> → <式> )
| ( <式> ↔ <式> )

文法に一致する任意の式は左括弧と右括弧の数のバランスが取れていること、および式の空でない最初のセグメントは右括弧より左括弧の数が多いことが示されています。^[17]この事実は、式を解析するためのアルゴリズムを与えるために使用できます。たとえば、式xが で始まるとします。2 番目の記号の後から始めて、バランスの取れた括弧を持つxの最短の部分式yに一致します。 xが式の場合、この式の後にはちょうど 1 つの記号が残り、この記号は閉じ括弧であり、y自体が式です。このアイデアを使用して、式の 再帰下降パーサーを生成することができます。${\displaystyle (\lnot }$

括弧カウントの例:

この方法では、主接続詞を「1」として特定します。主接続詞とは、最も外側の括弧（省略されることが多い）の式全体の評価が行われる接続詞です。^[18]また、真理値表を使用せずに式の評価を開始する最も内側の接続詞（たとえば「レベル6」）も特定します。

有効な議論という概念は、通常、議論における推論に適用されるが、議論は命題式に還元され、他の命題式と同様に評価することができる。ここで有効な推論とは、「推論を表す式は、その変数にどのような真理値が割り当てられていても、その主接続子の下で「真理」と評価される」、つまり式がトートロジーであることを意味する。^[19] 式は整形式であっても有効ではない可能性は十分にある。別の言い方をすると、「式が有効であるためには整形式であることが必要であるが、それだけでは十分ではない」ということである。式が整形式かつ有効であるかどうかを調べる唯一の方法は、真理値表または「法則」を使用して検証することである。

• 例 1: 次のわかりにくい主張をどう解釈しますか? 有効ですか? 「晴れていても、カエルが鳴いている場合は晴れていないということです。これは、カエルが鳴いていないと言うことと同じです。」 これを次のように命題式に変換します。

  「IF (a AND (IF b THEN NOT-a) THEN NOT-a」、ここで「a」は「晴れている」を表し、「b」は「カエルが鳴いている」を表します。

  ( ( (a) & ( (b) → ~(a) ) ≡ ~(b) )

  これは整形式ですが、有効でしょうか? 言い換えると、評価すると、論理等価記号 ≡ の下にトートロジー (すべて T) が生成されますか? 答えは「いいえ」です。有効ではありません。ただし、含意として再構築すると、議論は有効になります。

  「晴れていると言っても、カエルが鳴いていれば晴れていないということは、カエルは鳴いていないということを意味します。」

  カエルが鳴かないのは他の状況によるものかもしれません。鶴がカエルを食べたのかもしれません。

• 例 2 (ライヘンバッハからバートランド・ラッセル経由):

  「豚に翼があるなら、翼のある動物の中には食べるのに良いものがある。翼のある動物の中には食べるのに良いものがある、だから豚には翼がある。」

  ( ((a) → (b)) & (b) → (a) ) は正しく形成されていますが、主含意の下の赤い評価で示されているように無効な議論です。

論理接続詞の集合は、すべての命題式がその集合内の接続詞だけを含む式とトートロジー的に同値であるとき完全であると言われる。接続詞の完全な集合は多数存在し、これには、、、が含まれる。NANDとNORにそれぞれ対応する、それ自体で完全な2つの二項接続詞が存在する。^[20]など、一部のペアは完全ではない。 ${\displaystyle \{\land ,\lnot \}}$${\displaystyle \{\lor ,\lnot \}}$${\displaystyle \{\to ,\lnot \}}$${\displaystyle \{\land ,\lor \}}$

NAND に対応する 2 項接続子は、シェファー ストロークと呼ばれ、縦棒 | または縦矢印 ↑ で表されます。この接続子の完全性は、プリンキピア・マテマティカ(1927:xvii) で指摘されています。この接続子はそれ自体で完全であるため、他のすべての接続子はストロークのみを使用して表現できます。たとえば、記号 " ≡ " は論理的等価性を表します。

~p ≡ p|p

p → q ≡ p|~q

p ∨ q ≡ ~p|~q

p & q ≡ ~(p|q)

特に、ゼロ項接続詞(真実を表す) と(偽を表す) は、ストロークを使用して表現できます。 ${\displaystyle \top }$${\displaystyle \bot }$

${\displaystyle \top \equiv (a|(a|a))}$

${\displaystyle \bot \equiv (\top |\top )}$

この接続詞は、{0,1}、(または{F,T}、{ 、})とともに完全なセットを形成します。以下では、IF...THEN...ELSE関係(c, b, a) = dは、((c → b)∨(~c → a))≡((c & b)∨(~c & a))=dを表します。 ${\displaystyle \bot }$${\displaystyle \top }$

（c、b、a）：

(c, 0, 1) ≡ ~c

(c, b, 1) ≡ (c → b)

(c, c, a) ≡ (c ∨ a)

(c, b, c) ≡ (c & b)

例: 以下は、「(c, b, 1) ≡ (c → b)」の定理に基づく証明がどのように進むかを示しています。証明の下には真理値表による検証があります。(注: (c → b) は(~c ∨ b) と定義されます):

• 簡約された形式から始めましょう: ( (c & b) ∨ (~c & a) )
• a に「1」を代入します: ( (c & b) ∨ (~c & 1) )
• 恒等式 (~c & 1) = ~c: ( (c & b) ∨ (~c) )
• V の交換法則: ( (~c) ∨ (c & b) )
• 「~c V」を (c & b) に分配します: ( ((~c) ∨ c ) & ((~c) ∨ b )
• 排中律 (((~c) ∨ c ) = 1 ): ( (1) & ((~c) ∨ b ) )
• 「(1) &」を((~c) ∨ b)に分配する: ( ((1) & (~c)) ∨ ((1) & b )) )
• 交換性と恒等性 (( 1 & ~c) = (~c & 1) = ~c、かつ (( 1 & b) ≡ (b & 1) ≡ b: ( ~c ∨ b )
• ( ~c ∨ b ) はc → b QEDと定義される

次の真理値表では、トートロジーを表す「taut」というラベルの付いた列は、d というラベルの付いた 2 つの列間の論理的等価性 (ここでは ≡ で表されます) を評価します。「taut」の下の 4 つの行はすべて 1 であるため、等価性は確かにトートロジーを表します。

任意の命題式は非常に複雑な構造を持つ場合があります。より単純な形式 (正規形と呼ばれる) を持つ式を使用すると便利な場合がよくあります。一般的な正規形には、連言正規形と選言正規形があります。任意の命題式は、連言正規形または選言正規形に簡約できます。

式の真理値表が用意できれば、正規形への簡約は比較的簡単です。しかし、リテラルの数をさらに最小限に抑えるには (下記参照)、いくつかのツールが必要です。ド・モルガンの法則と真理値表による簡約は扱いにくい場合がありますが、カルノー図は変数の数が少ない (5 以下) 場合に非常に適しています。複数の出力を持つより複雑な回路には、洗練された表形式の方法がいくつかありますが、この記事の範囲を超えています。詳細については、クワイン・マクラスキー アルゴリズムを参照してください。

電気工学では、変数 x またはその否定 ~(x) はリテラルと呼ばれることがあります。AND で接続されたリテラルの文字列は項と呼ばれます。OR で接続されたリテラルの文字列は項と呼ばれます。通常、リテラル ~(x) は ~x と省略されます。代数乗算のように & 記号が完全に省略されることもあります。

• 例
  1. a、b、c、d は変数です。((( a & ~(b) ) & ~(c)) & d) は項です。これは (a & ~b & ~c & d)、または a~b~cd と省略できます。
  2. p、q、r、sは変数です。(((p ∨ ~(q) ) ∨ r) ∨ ~(s) )は代名詞です。これは(p ∨ ~q ∨ r ∨ ~s)と省略できます。

2 ⁿ行の真理値表が、変数の2 ⁿ通りの値すべてに対する命題式の評価を表示するのと同じように、 n 変数は 2 ⁿ平方のカルノー図を生成します（ただし、これを完全な次元で実現することはできません）。たとえば、3 つの変数は 2 ³ = 8 行と 8 つのカルノー平方を生成します。4 つの変数は 16 の真理値表の行と 16 の平方、つまり 16 個の最小項を生成します。カルノー図の各平方とそれに対応する真理値表の評価は、1 つの最小項を表します。

任意の命題式は、アクティブな（つまり「1」または「T」の値を持つ）最小項の「論理和」（OR）に簡約できます。この形式の式は、選言標準形であると言われます。ただし、この形式であっても、項の数またはリテラルの数に関して必ずしも最小化されるわけではありません。

次の表では、行の番号付けが独特であることに注意してください: (0、1、3、2、6、7、5、4、0)。最初の列は、数字「cba」の 2 進数に相当する 10 進数です。言い換えると、次のようになります。

• 例

  cba ₂ = c*2 ² + b*2 ¹ + a*2 ⁰ :

  cba = (c=1, b=0, a=1) = 101 ₂ = 1*2 ² + 0*2 ¹ + 1*2 ⁰ = 5 ₁₀

この番号付けは、表を行から行へと下に移動すると、一度に 1 つの変数の値のみが変化することから生じます。グレイ コードはこの概念から派生したものです。この概念は、ハッセ図と呼ばれる3 次元および 4 次元の超立方体に拡張できます。ハッセ図では、立方体の端を移動すると、各コーナーの変数が一度に 1 つだけ変化します。2 次元に平坦化されたハッセ図 (超立方体) は、ヴィーチ図またはカルノー図のいずれかです(これらは実質的に同じものです)。

カルノー図を扱うときは、上端が下端に「折り返され」、左端が右端に「折り返される」ことを常に念頭に置く必要があります。カルノー図は、実際には 3 次元、4 次元、または n 次元の平坦化されたオブジェクトです。

ヴィーチは円を隣接する四角形に変換することでベン図の概念を改良し、カルノーはリテラル形式で書かれた最小項（例：〜abc〜d）を数値に変換することでヴィーチ図を簡略化した。^[21]この方法は次のように進行する。

式の真理値表を作成します。n 個の変数に対して、変数の 2 進数相当値 (通常は 0 から n-1 まで順番に) を使用して行に番号を付けます。

技術的には、命題関数は（最小化されていない）連言正規形に縮小されています。各行には最小項式があり、これらを OR 演算して（最小化されていない）連言正規形の式を生成できます。

例: ((c & d) ∨ (p & ~(c & (~d)))) = q の連言標準形は次のようになります。

( (~p & d & c ) ∨ (p & d & c) ∨ (p & d & ~c) ∨ (p & ~d & ~c) ) = q

ただし、この式では項の数 (4 から 3) とリテラルの総数 (12 から 6) の両方が削減されます。

真理値表法で見つかった式の値 (例: "p") を使用して、それぞれの (関連付けられた) カルノー方陣に配置します (これらはグレイ コード規則に従って番号が付けられます)。表に "don't care" を表す "d" の値が表示されると、削減フェーズ中に柔軟性が増します。

隣接する（隣接する）1 マス（T マス）の最小項は、そのリテラルの数に応じて削減することができ、その過程で数項も削減されます。隣接する 2 つのマス（水平方向の 2 x 1 または垂直方向の 1 x 2、端も隣接するマスを表す）はリテラルを 1 つ失い、4 x 1 の長方形（水平方向または垂直方向）または 2 x 2 の正方形（4 つの角も隣接するマスを表す）内の 4 つのマスはリテラルを 2 つ失い、長方形内の 8 つのマスはリテラルを 3 つ失う、などとなります（最大のマスまたは長方形を探し、その中に完全に含まれる小さなマスまたは長方形は無視します）。このプロセスは、隣接するマスがすべて考慮されるまで続けられ、その時点で命題式が最小化されます。

たとえば、正方形 #3 と #7 は隣接しています。これらの隣接する正方形は 1 つのリテラル (たとえば、正方形 #3 と #7 の "p") を失い、長方形または正方形内の 4 つの正方形は 2 つのリテラルを失い、長方形内の 8 つの正方形は 3 つのリテラルを失います (最大の正方形または長方形を探します)。このプロセスは、隣接する正方形がすべて考慮されるまで続けられ、その時点で命題式は最小化されたと言われます。

例: マップ法は通常、検査によって行われます。次の例では、代数的方法を拡張して、カルノー図上の項の結合の背後にある「トリック」を示します。

最小項 #3 と #7 は隣接し、#7 と #6 は隣接し、#4 と #6 は隣接します (テーブルの端が折り返されているため)。したがって、これらの各ペアは縮小できます。

冪等性法則 (A ∨ A) = A により、より多くの項を作成できることに注目してください。次に、結合法則と分配法則により、消える変数をペアにすることができ、その後、背理法則 (x & ~x)=0 により「消える」ことができます。以下では、項を追跡するためだけに括弧 [ と ] を使用しています。これらには特別な意味はありません。

• 簡約する式と連言正規形に式を置きます。

q = ( (~p & d & c ) ∨ (p & d & c) ∨ (p & d & ~c) ∨ (p & ~d & ~c) ) = ( #3 ∨ #7 ∨ #6 ∨ #4 )

• 冪等性（吸収）[A∨A) = A:

( #3 ∨ [ #7 ∨ #7 ] ∨ [ #6 ∨ #6 ] ∨ #4 )

• 結合法則 (x ∨ (y ∨ z)) = ( (x ∨ y) ∨ z )

( [ #3 ∨ #7 ] ∨ [ #7 ∨ #6 ] ∨ [ #6 ∨ #4] )

[ (~p & d & c ) ∨ (p & d & c) ] ∨ [ (p & d & c) ∨ (p & d & ~c) ] ∨ [ (p & d & ~c) ∨ (p & ~d & ~c) ] .

• 分配法則 ( x & (y ∨ z) ) = ( (x & y) ∨ (x & z) ) :

( [ (d & c) ∨ (~p & p) ] ∨ [ (p & d) ∨ (~c & c) ] ∨ [ (p & ~c) ∨ (c & ~c) ] )

• 交換法則と背理法則 (x & ~x) = (~x & x) = 0:

( [ (d & c) ∨ (0) ] ∨ [ (p & d) ∨ (0) ] ∨ [ (p & ~c) ∨ (0) ] )

• 同一性の法則 ( x ∨ 0 ) = x により、次の式の簡約形が得られます。

q = ( (d & c) ∨ (p & d) ∨ (p & ~c) )

次の定義としての例を考えると、その後の推論はどうなるでしょうか。

(1)「この文は単純です。」 (2)「この文は複雑で、ANDで結合されています。」

次に、変数「s」を一番左の文「この文は単純です」に割り当てます。「複合」c = 「単純ではない」~s と定義し、c = ~s を「この文は複合です」に割り当てます。「j」を「[この文] は AND で結合されています」に割り当てます。2 番目の文は次のように表現できます。

( NOT(s) AND j )

文 c = ~s と j に真理値を置くと、すべてが明らかに虚偽になります。たとえば、「この文は複雑です」は虚偽です (定義により単純です)。したがって、それらの接続詞 (AND) は虚偽です。しかし、組み立てられた形式では、文は真実です。

これは、非述語的定義から生じるパラドックスの一例です。つまり、オブジェクト m がプロパティ P を持っているが、オブジェクト m がプロパティ P によって定義されている場合です。^[22]修辞学者や演繹分析に携わる人への最善のアドバイスは、非述語的定義を避けることですが、同時に、パラドックスを生み出す可能性があるため、注意が必要です。一方、エンジニアは、フィードバック付きの命題式の形で非述語的定義を活用します。

命題式が自身の変数の1つとして現れるという概念は、式を変数に割り当てることを可能にする形成規則を必要とする。一般に、これが起こることを禁じる規定（オブジェクトと関係の公理的または真理値表システム）はない。^[23]

最も単純なケースは、OR 式がそれ自身の入力になる場合です (例: p = q)。(p ∨ s) = q から始めて、p = q とします。q の「定義」は、それ自身「q」だけでなく、「s」と OR 接続詞にも依存していることに注意してください。したがって、この q の定義は非叙述的です。結果として、^[24]振動またはメモリのいずれかの状態が発生します。

数式をブラック ボックスとして考えると役に立ちます。数式「ボックス」の「内部」で何が起こっているかを外部から知らなければ、出力はもはや入力のみの関数ではないように見えます。つまり、q を見ると 0 が表示されることもあれば、1 が表示されることもあります。この問題を回避するには、ボックス内の「隠れた」変数 p の状態 (条件) (つまり、フィードバックされて p に割り当てられる q の値) を知る必要があります。これがわかると、見かけ上の矛盾はなくなります。

フィードバックを持つ式の動作を理解する [予測する] には、順序回路のより高度な分析が必要です。フィードバックを持つ命題式は、最も単純な形では状態マシンにつながります。また、チューリング テープやカウンター マシン カウンターの形のメモリにもつながります。これらの要素の組み合わせから、あらゆる種類の境界付き計算モデルを構築できます (例: チューリングマシン、カウンター マシン、レジスタ マシン、Macintosh コンピューターなど)。

抽象的 (理想的な) ケースでは、最も単純な振動式は、それ自体にフィードバックされる NOT です: ~(~(p=q)) = q。真理値表で抽象的 (理想的な) 命題式を分析すると、p=1 と p=0 の両方のケースで矛盾が明らかになります: p=1、q=0 のとき、これは p=q なのであり得ません。p=0、q=1 のときも同様です。

遅延を伴う振動: 抽象式のpとqの間に遅延^[25]（理想的または非理想的）が挿入されると、pは1と0の間を101010...101...と無限に振動します。遅延とNOTのいずれかが抽象的でない場合（つまり理想的でない場合）、使用する分析の種類は、振動子を構成するオブジェクトの正確な性質に依存します。このようなことは数学の範囲外であり、工学の範疇に入ります。

分析では、遅延を挿入し、遅延と入力「p」の間のループを切断する必要があります。遅延は、入力「q」に対して出力として「qd」(q 遅延) を持つ一種の命題として見なす必要があります。この新しい命題により、真理値表に別の列が追加されます。赤で示されているように、矛盾は「qd」と「p」の間に発生し、2 つの安定した状態が生じます。

遅延がなければ、真理値表分析から矛盾を排除する必要があります。「遅延」の概念では、この状態は、フィードバックされた出力変数 q と p = q _delayedの間の瞬間的な矛盾として現れます。

_{真理値表は、入力で遅延された}p = q と出力の q の間に矛盾が生じる行を明らかにする。フィードバックを「破壊」した後、^[26]真理値表の構築は従来の方法で進む。しかしその後、すべての行で出力 q が独立入力 p と比較され、p と q の間の矛盾が記​​録される (つまり、p=0 と q=1 が一緒に、または p=1 と q=0)。「行」が「作り直される」と、両方とも矛盾の法則 ~(p & ~p) によって不可能になる。矛盾を示す行は、一時的な状態と見なされるか、単に矛盾して「不可能」であるとして排除される。

最も単純なメモリの結果は、OR の出力がその入力の 1 つにフィードバックされるときに発生します。この場合、出力 "q" が "p" にフィードバックされます。式が最初に p=0 および q=0 で評価 (初期化) されると、s=1 によって "設定" されたときに 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 は d の値に「追従」します。c が 1 から 0 に変わると、データの最後の値は出力「q」で「トラップ」されたままになります。c=0 である限り、d は q を変更することなく値を変更することができます。

• 例
  1. ( ( c & d ) ∨ ( p & ( ~( c & ~( d ) ) ) ) = qですが、ここで p = q とします。
  2. ( ( c & d ) ∨ ( q & ( ~( c & ~( d ) ) ) ) = q

状態図はフリップフロップの状態図と形は似ていますが、遷移のラベルが異なります。

バートランド・ラッセル（1912:74）は、アリストテレスから派生した思考の3つの法則を挙げている：（1）同一性の法則：「何であれ、存在する。」、（2）矛盾律：「存在と非存在の両方はあり得ない。」、（3）排中律：「すべてのものは、存在するか、存在しないかのどちらかである。」

• 例: ここで O はオブジェクトの存在または品質に関する表現です。
  1. 同一性の法則: O = O
  2. 矛盾の法則: ~(O & ~(O))
  3. 排中律: (O ∨ ~(O))

排中律で「すべて」という言葉が使われているため、ラッセルのこの法則の表現は議論の余地があります。有限のオブジェクトの集合 (有限の「論議領域」) を参照する存在または品質に関する表現に限定される場合 (そのメンバーを 1 つずつ調べて、主張の有無を調べることができます)、この法則は直観的に適切であると考えられます。したがって、「このオブジェクトは (集合内で) 存在するか存在しないかのいずれかである」、または「このオブジェクトは (集合内のオブジェクトに対して) この品質を持っているか持っていないかのいずれかである」などの主張は受け入れられます。詳細については、ベン図を参照してください。

命題計算はアリストテレスに由来するが、命題に適用される代数の概念は19 世紀初頭まで待たなければならなかった。アリストテレスの三段論法の 2000 年の伝統に対する (反対の) 反応として、ジョン ロックの『人間理解に関するエッセイ』(1690 年)では、記号論(記号の使用理論) という言葉が使用された。1826 年までに、リチャード ウェイトリーはロックの記号論に共感しながら三段論法を批判的に分析した。ジョージ ベンサムの研究 (1827 年) は、「述語の量化」の概念 (1827 年) (現在では ∀ ≡ 「すべての」と記号化される) につながった。ウィリアム・ハミルトンがオーガスタス・ド・モルガンとの優先権をめぐって起こした「騒動」がきっかけとなり、 「ジョージ・ブールは論理学に関する自身の考えを書き上げ、1847 年に MAL [論理の数学的分析] として出版した」(Grattin-Guinness および Bornet 1997:xxviii)。

彼の貢献について、グラッタン＝ギネスとボルネットは次のようにコメントしている。

^{「ブールの唯一の主要な革新は、論理における [ x n} = x ] の法則でした。これは、特性 x を選択し、それを何度も選択するという精神的行為は、x を一度選択することと同じであると述べています...その結果、彼は x•(1-x)=0 と x+(1-x)=1 という方程式を作成しました。これは、彼にとってそれぞれ、背理法則と排中律を表現していました」(p. xxviiff)。ブールにとって、「1」は議論の宇宙であり、「0」は何もなかったのです。

ゴットロープ・フレーゲの大事業 (1879) は命題の正式な計算をもたらしたが、彼の記号化は非常に難解であったため、バートランド・ラッセル以外にはほとんど影響を与えなかった。彼は最初、アルフレッド・ノース・ホワイトヘッドの弟子としてフレーゲの研究を研究し、フレーゲの扱い方で発見した二律背反の問題(ラッセルのパラドックスを参照) に関する (有名かつ悪名高い) 修正案 (1904) を提案した。ラッセルの研究はホワイトヘッドとの共同作業につながり、1912 年に『プリンキピア・マテマティカ』 (PM) の第 1 巻が出版された。ここで、いわゆる「現代」命題論理が登場した。特に、PM では NOT と OR およびアサーション記号 ⊦ がプリミティブとして導入されている。これらの概念に基づいて、IMPLICATION → ( 定義 *1.01: ~p ∨ q )、AND ( 定義 *3.01: ~(~p ∨ ~q) )、EQUIVALENCE p ←→ q (*4.01: (p → q) & ( q → p ) ) を定義します。

• Henry M. Sheffer (1921) とJean Nicod は、1 つの接続詞「ストローク」| だけですべての命題式を表現できることを示しています。
• エミール・ポスト(1921) は、著書『基本命題の一般理論入門』の中で、真理値表分析法を展開しています。彼はニコドのストロークに注目しています。
• ホワイトヘッドとラッセルは、1927 年に再出版した PM に序文を追加し、部分的に「脳卒中」に対する好意的な扱いを加えました。

計算とスイッチングロジック:

• ウィリアム・エクルズとFWジョーダン（1919）は、真空管で作られた「トリガーリレー」について説明しています。
• ジョージ・スティビッツ(1937) は、機械式リレーを使用した 2 進加算器を発明しました。彼はこれを自宅の台所で作りました。

例: バイナリビットa _iと b _iおよびキャリーイン ( c_in _i ) が与えられた場合、それらの合計 Σ _iとキャリーアウト (c_out _i ) は次のようになります。

• ( ( a _i XOR b _i ) XOR c_in _i )= Σ _i
• ( a _i & b _i ) ∨ c_in _i ) = c_out _i ;

• アラン・チューリングはリレーを使った乗算器を製作しました (1937 ～ 1938 年)。これを実現するために、彼はリレーコイルを自分で手で巻く必要がありました。
• 「スイッチング回路」に関する教科書は 1950 年代初頭に登場しました。
• Willard Quine (1952 年と 1955 年)、EW Veitch (1952 年)、およびM. Karnaugh (1953 年) は、命題関数を簡略化するためのマップ法を開発しました。
• George H. Mealy (1955) とEdward F. Moore (1956) は、シーケンシャル (つまりスイッチング回路)「マシン」の理論を論じています。
• EJ McCluskey と H. Shorr は命題 (スイッチング) 回路を簡素化する方法を開発しました (1962)。

• ローゼンブルーム、ポール(1950)。『数学論理の要素』。ニューヨーク州ミネオラ：ドーバー出版。ISBN 0-486-44617-4。
• クリーネ、スティーブン（1952）。メタ数学入門。アムステルダム：ノースホランド出版社。
• Bender, Edward A.およびWilliamson, S. Gill、2005、「A Short Course in Discrete Mathematics」、Dover Publications、Mineola NY、ISBN 0-486-43946-1。このテキストは、カリフォルニア大学サンディエゴ校の「下級学部 2 学期 [コンピュータ サイエンス] コース」で使用されています。 
• エンダートン、HB、2002年、「論理への数学的入門」、ハーコート/アカデミック出版。ISBN 0-12-238452-0 
• Goodstein, RL、(Pergamon Press 1963)、1966、(Dover edition 2007)、Boolean Algebra、Dover Publications、Inc. Minola、ニューヨーク、ISBN 0-486-45894-6。集合論的記号である ∩、∪、' (NOT)、⊂ (IMPLIES) などを用いた「クラスの代数」の概念を強調。後に Goldstein は「Sentence Logic」pp. 76–93 の扱いの中で、これらをそれぞれ &、∨、￢、→ に置き換えている。 
• Ivor Grattan-Guinnessと Gérard Bornet 1997、「George Boole: Selected Manuscripts on Logic and its Philosophy 」、Birkhäuser Verlag、Basil、 ISBN 978-0-8176-5456-6 (ボストン)。 
• AG Hamilton 1978、「Logic for Mathematicians」、Cambridge University Press、Cambridge UK、ISBN 0-521-21838-1。 
• EJ McCluskey 1965、「スイッチング回路理論入門」、McGraw-Hill Book Company、ニューヨーク。ISBN なし。米国議会図書館カタログカード番号 65-17394。McCluskey はWillard Quineの弟子であり、Quine と共同で、また独自に、いくつかの注目すべき定理を開発しました。歴史に興味のある方のために、この本には豊富な参考文献が掲載されています。
• Marvin L. Minsky 1967、「Computation: Finite and Infinite Machines」、Prentice-Hall, Inc、Englewood Cliffs、NJ。ISBN なし。米国議会図書館カタログ カード番号 67-12342。特に計算可能性に役立ち、優れた情報源です。
• Joel W. Robbin 1969、1997、「Mathematical Logic: A First Course」、Dover Publications、Inc.、Mineola、New York、ISBN 0-486-45018-X (pbk.)。 
• Patrick Suppes 1957 (1999 Dover 版)、『Introduction to Logic 』、Dover Publications, Inc.、ニューヨーク州ミネオラ。ISBN 0-486-40687-3 (pbk.)。この本は印刷されており、すぐに入手できます。 
• 204 ページの脚注で、彼は自身の公理の集合を、EV Huntingtonの「Sets of Independent Postulates for the Algebra of Logic」( Transactions of the American Mathematical Society、第 5 巻、91904) pp. 288-309 に引用しています。
• アルフレッド・タルスキ1941 (1995 Dover 版)、『論理学と演繹科学の方法論入門』、Dover Publications, Inc.、ニューヨーク州ミネオラ。ISBN 0-486-28462 -X (pbk.)。この本は印刷されており、すぐに入手できます。 
• Jean van Heijenoort 1967、1976 年に改訂された第 3 刷、「 From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931」、Harvard University Press、マサチューセッツ州ケンブリッジ。ISBN 0-674-32449-8 (pbk) 。Frege (1879)、Russell's letter to Frege (1902)、Frege's letter to Russell (1902)、Richard's paradox (1905)、Post (1921) の翻訳/再版は、こちらでご覧いただけます。 
• アルフレッド・ノース・ホワイトヘッドとバートランド・ラッセル1927 年第 2 版、ペーパーバック版から 1962 年まで、プリンキピア・マテマティカ、ケンブリッジ大学出版局、ISBN なし。1912 年の第 1 版から 1927 年の第 2 版までの間に、HMシェファー1921 と M. ジャン・ニコ(年は記載なし) が、ラッセルとホワイトヘッドに、彼らが基本命題 (接続詞) と考えていたものが、今日では「ストローク」または NAND (NOT-AND、NEITHER ... NOR...) として知られる単一の | に簡約できることを指摘しました。ラッセルとホワイトヘッドは「第 2 版の序論」でこれについて論じ、上記の定義を行っています。
• William E. Wickes 1968、「Logic Design with Integrated Circuits」、John Wiley & Sons, Inc.、ニューヨーク。ISBN なし。米国議会図書館カタログカード番号: 68-21185。エンジニアリングの分析および合成方法を厳密に提示。McCluskey 1965 を参照。Suppes とは異なり、Wickes の「ブール代数」の提示は、真理値表の性質を持つ一連の公理から始まり、それらの一般的な定理を導出する (p. 18ff)。

• ウィキメディア・コモンズの命題公式に関連するメディア