真理値表

真理値表は、論理学、特にブール代数、ブール関数、命題計算で使用される数学的な表であり、論理式の関数値を、その関数の各引数、つまり論理変数が取る値の各組み合わせに対して設定します。^[1]特に、真理値表は、命題式がすべての正当な入力値に対して真であるかどうか、つまり論理的に有効であるかどうかを示すために使用できます。

真理値表には、入力変数ごとに 1 つの列 (たとえば、A と B) があり、最後の 1 つの列には、表が表す論理演算のすべての可能な結果 (たとえば、A XOR B) が表示されます。真理値表の各行には、入力変数の 1 つの可能な構成 (たとえば、A=true、B=false) と、それらの値に対する演算の結果が含まれます。

真理値表は、ブール関数の入力変数の真理値とそれに対応する出力値のすべての可能な組み合わせを表す構造化表現です。Aから F までの関数 fは特別な関係、つまり A×F のサブセットであり、これは単にf を入力と出力のペアのリストとしてリストできることを意味します。明らかに、ブール関数の場合、出力はバイナリ セット、つまり F = {0, 1} に属します。n 項ブール関数の場合、入力は、入力ブール変数に対応するバイナリ セットの直積であるドメインから取得されます。たとえば、バイナリ関数f (A, B) の場合、 fのドメインはA×B であり、次のようにリストできます。A×B = {(A = 0, B = 0), (A = 0, B = 1), (A = 1, B = 0), (A = 1, B = 1)}。定義域の各要素は、変数 A と B の入力値の組み合わせを表します。これらの組み合わせは、その組み合わせに対応する関数の出力と組み合わせることができ、A×F のサブセットである特別な関係としての入力-出力ペアのセットを形成できます。関係が関数であるための特別な要件は、関数の定義域の各要素が共域の 1 つのメンバーにのみマップされる必要があることです。したがって、関数 f 自体は次のようにリストできます。f = {((0, 0), f ₀ ), ((0, 1), f ₁ ), ((1, 0), f ₂ ), ((1, 1), f ₃ )}、ここでf ₀、f ₁、f ₂、およびf _{3 は}それぞれ共域 {0, 1} のメンバーとしてのブール値 0 または 1 であり、定義域のメンバーに対応する出力です。真理値表は、上記のリスト (セット) ではなく、これらの入力と出力のペアを表形式で表します。表の各行は、ドメインのメンバーと、それに対応する出力値 (0 または 1) のペアに対応します。もちろん、ブール関数の場合、ドメインのすべてのメンバーを共ドメインのイメージとともにリストする必要はありません。メンバーを "1" にマッピングするマッピングをリストするだけで済みます。他のすべてのメンバーは自動的に "0" にマッピングされる必要があるためです (これがmintermsのアイデアにつながります)。

ルートヴィヒ・ヴィトゲンシュタインは、1918年に完成し1921年に出版された『論理哲学論考』の中で真理表を発明し普及させたと一般に考えられている。 ^[2]このような体系は、1921年にエミール・レオン・ポストによっても独立して提案されている。^[3]

アーヴィング・アネリスの研究によると、CS・ピアースが真理値表行列を考案した最初の論理学者（1883年）であるようだ。^[4]

アネリスの論文の要約から：^[4]

1997 年、ジョン・ショスキーは、バートランド・ラッセルの 1912 年の講義「論理的原子論の哲学」のタイプされたトランスクリプトのページの裏に、真理値表の行列を発見した。否定の行列はラッセルのものであり、その横にはルートヴィヒ・ヴィトゲンシュタインの手書きの物質的含意の行列がある。1893 年にピアーズが書いたと特定された未発表の原稿に、ジョン・ショスキーが発見した物質的含意の行列と同等の真理値表の行列が含まれていることが示された。1885 年にアメリカ数学ジャーナルに掲載されたピアーズの「論理の代数について: 表記法の哲学への貢献」の執筆に関連して 1883 年から 1884 年に書かれたと特定されたピアーズの未発表の原稿には、条件文の間接真理値表の例が含まれている。

真理値表は、他の多くの論理的等価性を証明するために使用できます。たとえば、次の真理値表を考えてみましょう。

これは、がと論理的に同等であるという事実を示しています。 ${\displaystyle p\Rightarrow q}$${\displaystyle \lnot p\lor q}$

以下は、2 つのブール変数 P と Q の 16 個の可能な真理値関数のうち、最もよく使用される 7 個の定義を示す真理値表です。

二項演算子の場合、行見出しと列見出しでオペランドを指定し、表のセルで結果を指定する、簡略化された真理値表も使用されます。たとえば、ブール論理では、次の簡略化された真理値表表記が使用されます。

この表記法は、演算が可換である場合に特に便利ですが、行が最初のオペランドで列が 2 番目のオペランドであるとさらに指定することもできます。この簡略化された表記法は、必要な行数の組み合わせ爆発を大幅に削減するため、ロジックの多値拡張について議論する際に特に便利です。また、表内の値の分布の特徴的な「形状」をすぐに認識できるため、読者がルールをより迅速に把握するのに役立ちます。

真理値表は、デジタル ロジック回路のハードウェア ルックアップ テーブル (LUT)の機能を指定するためにも使用されます。n 入力の LUT の場合、真理値表には 2^ n個の値 (または上記の表形式の行) が含まれ、LUT のブール関数が完全に指定されます。各ブール値を2 進数のビットとして表すことで、真理値表の値を電子設計自動化 (EDA)ソフトウェアで整数値として効率的にエンコードできます。たとえば、32 ビットの整数で、最大 5 つの入力を持つ LUT の真理値表をエンコードできます。

真理値表の整数表現を使用する場合、LUT の出力値は、LUT の入力値に基づいてビット インデックスk を計算することによって取得できます。この場合、LUT の出力値は整数のk番目のビットになります。たとえば、n個のブール入力値の配列が与えられた LUT の出力値を評価するには、真理値表の出力値のビット インデックスを次のように計算できます。i 番目の入力が true の場合は、そうでない場合は とします。次に、真理値表のバイナリ表現のk番目のビットが LUT の出力値になります。 ここで です。${\displaystyle V_{i}=1}$${\displaystyle V_{i}=0}$${\displaystyle k=V_{0}\times 2^{0}+V_{1}\times 2^{1}+V_{2}\times 2^{2}+\dots +V_{n}\times 2^{n}}$

真理値表はブール関数をエンコードするシンプルで簡単な方法ですが、入力数が増えるとサイズが指数関数的に増加するため、入力数が多い関数には適していません。メモリ効率のよい他の表現としては、テキスト方程式と二分決定図があります。

デジタル エレクトロニクスとコンピューター サイエンス (応用論理工学と数学の分野) では、真理値表を使用して、論理ゲートやコードを使用せずに、基本的なブール演算を入力と出力の単純な相関関係に簡略化できます。たとえば、2 進加算は真理値表で表すことができます。

ここで、A は最初のオペランド、B は 2 番目のオペランド、C は繰り上がり桁、R は結果です。

この真理値表は左から右に読みます。

• 値のペア (A、B) は値のペア (C、R) と等しくなります。
• または、この例では、A と B を足すと結果 R になり、繰り上がりは C になります。

この表は、この操作を実装するために必要な論理操作を説明するものではなく、単に入力から出力値への機能を指定するものです。

結果に関して、この例は算術的には 2 を法とする 2 進加算とみなすことができ、論理的には排他的論理和 (排他的論理和) の 2 進論理演算と同等とみなすことができます。

この場合、1 と 0 などの非常に単純な入力と出力にのみ使用できます。ただし、入力に使用できる値の種類の数が増加すると、真理値表のサイズが増加します。

たとえば、加算演算では、2 つのオペランド A と B が必要です。それぞれのオペランドは、0 または 1 のいずれかの値を持ちます。これらの 2 つの値の組み合わせの数は 2×2、つまり 4 です。したがって、結果として、C と R の出力は 4 つになります。基数を 3 にすると、サイズは 3×3、つまり 9 つの出力に増えます。

上記の最初の「加算」の例は、半加算器と呼ばれます。全加算器は、前の演算からの繰り上がりが次の加算器への入力として提供される場合です。したがって、全加算器のロジックを記述するには、8 行の真理値表が必要になります。

ABC* | CR
0 0 0 | 0 0
0 1 0 | 0 1
1 0 0 | 0 1
1 1 0 | 1 0
0 0 1 | 0 1
0 1 1 | 1 0
1 0 1 | 1 0
1 1 1 | 1 1

前回と同じですが、
C* = 前の加算器からのキャリー

表の左側にある命題変数を表すガイド列^[5]については、著者によって記入方法が異なりますが、論理的な意味はありません。^[6]

ランダー大学の教授であるリー・アーチーは、出版されている真理値表でよく採用されているこの手順を推奨しています。

1. 変数の数（ステートメントの数に対応）をアルファベット順に書き出します。
2. 必要な行数は 2 ⁿです。ここで n は変数の数です。(たとえば、変数が 3 つの場合、2 ³ = 8)。
3. 右側の列から始めて、行がなくなるまでTとFを交互に書きます。
4. 次に、左の次の列に移動し、行がなくなるまでTとFのペアを交互に繰り返します。
5. 次に、次の左側の列に進み、TとFの数を2倍にして完成させます。^[5]

この方法により、スティーブン・コール・クリーネが作成した「 P⊃（Q∨R⊃（R⊃¬P）） 」の次の表のような真理値表が得られる。^[7]

一方、コリン・ハウソンは、次のことを実行することが「良い実践的なルールである」と考えています。

まずすべて T で始め、次にすべての方法 (3 つ) で 2 つの T を 1 つの F と組み合わせ、次にすべての方法 (3 つ) で 1 つの T を 2 つの F と組み合わせ、最後にすべて F で終了します。複合語が n 個の異なる文の文字から構築されている場合、その真理値表には 2 ⁿ行が含まれます。これは、最初の文字に T または F を割り当てる方法が 2 つあり、これらのそれぞれに対して 2 番目の文字に T または F を割り当てる方法が 2 つあり、これらのそれぞれに対して 3 番目の文字に T または F を割り当てる方法が 2 つあり、以下同様にして 2.2.2 が得られる。…、n 回、つまり 2 ⁿに等しい。^[6]

この結果、ハウソンが作成した表をモデルにした「(A→C)∧(B→C)と(A∨B)→Cは真理関数的に 同等であることを示す」次のような真理表が得られる。^[6]

入力変数がn 個ある場合、その真理値の組み合わせは 2 ^{n 通り}あります。与えられた関数はそれぞれの組み合わせに対して true または false を生成するため、n個の変数を持つ異なる関数の数は二重指数2 ^{2 n}です。

3 つ以上の変数を持つ関数の真理値表が与えられることはほとんどありません。

真理値表の出力を、単なる文字どおりの真偽値ではなく、いくつかの変数値の関数として表現すると便利な場合があります。これらは、より一般的な「真理値表」と区別するために「関数表」と呼ばれることがあります。^[8]たとえば、1 つの値 は、XOR ゲートを使用して、別の値 を条件付きで反転することができます。つまり、が偽の場合、出力は であり、が真の場合は、出力は です。この場合の関数表は次のようになります。 ${\displaystyle G}$${\displaystyle X}$${\displaystyle G}$${\displaystyle X}$${\displaystyle G}$${\displaystyle \lnot X}$

同様に、選択入力と、データ入力、、および、出力(図に表示) を持つ4 対 1マルチプレクサには、次の関数テーブルがあります。${\displaystyle S_{0}}$${\displaystyle S_{1}}$${\displaystyle A}$${\displaystyle B}$${\displaystyle C}$${\displaystyle D}$${\displaystyle Z}$

以下は、2つのブール変数pとqの16個の可能な真理関数の定義を示す拡張真理値表である。^{[注 1]}

どこ

T = 真。

F = 偽。

上付き文字⁰から^{15 は、 4 つの真理値を F = 0、T = 1 の}2 進数として読み取った結果の数値です。

Com行は、演算子op が可換であるかどうかを示します( P op Q = Q op P)。

Assoc行は、演算子op が結合的であるかどうかを示します- (P op Q) op R = P op (Q op R)。

Adj行には、 P op Q = Q op2 Pとなる演算子op2が表示されます。

Neg行は、P op Q = ¬(P op2 Q)となる演算子op2を示します。

Dual行は、Tと F、AND と OR を交換することによって得られるデュアル演算を示します。

L id行には、 I op Q = Qとなるような- 値Iがある場合、演算子の左側のアイデンティティが表示されます。

R id行は、 P op I = Pとなるような- 値Iを持つ演算子の右恒等式を示します。^{[注 2]}

ウィトゲンシュタインは『論理哲学論考』の命題5.101において、^[9] 上記の表を以下のように列挙している。

各行で表される真理値表は、真理値_行に与えられたシーケンスを表に追加することによって得られる^[注3]

例えば、表

物質的含意の真理値表を表します。論理演算子はベン図を使用して視覚化することもできます。

ヌル演算には 2 つの種類があります。

• 常に真実
• 決して真ではない、一項偽

この演算子にはオペランドがないので入力値もないので、出力値は常に真になります。

出力値は決して真ではありません。つまり、この演算子にはオペランドがないため、入力値もないため、常に偽です。

単項演算には 2 つあります。

• 一項同一性
• 一項否定

論理的同一性は、1 つの論理値pに対する演算であり、出力値は p のままです。

論理単位演算子の真理値表は次のとおりです。

論理否定は、1 つの論理値(通常は命題の値)に対する演算であり、オペランドが偽の場合はtrueの値を生成し、オペランドが真の場合は falseの値を生成します。

NOT p ( ¬p、Np、Fpq、または~pとも表記)の真理値表は次のとおりです。

2 つのバイナリ変数には16 個の可能な真理関数があり、各演算子には独自の名前があります。

論理積は、2 つの論理値(通常は 2 つの命題の値)に対する演算であり、両方のオペランドが true の場合に trueの値を生成します。

p AND q ( p ∧ q、Kpq、p & q、p qとも表記)の真理値表は次のとおりです。 ${\displaystyle \cdot }$

通常の言語で言えば、pとq の両方が真である場合、論理積p ∧ qは真です。その他のすべてのpとqへの論理値の割り当てでは、論理積p  ∧  qは偽です。

また、 pの場合、p ∧ qはqであり、それ以外の場合はp ∧ qはpであるとも言えます。

論理和は、2 つの論理値(通常は 2 つの命題の値)に対する演算であり、そのオペランドの少なくとも 1 つが true の場合に trueの値を生成します。

p OR q ( p ∨ q、Apq、p || q、p + qとも表記される)の真理値表は次のとおりです。

英語で言うと、pならばp ∨ q はpであり、それ以外の場合にはp ∨ qはqです。

論理含意と物質条件はどちらも、 2 つの論理値(通常は 2 つの命題の値) に対する演算に関連付けられており、最初のオペランドが true で 2 番目のオペランドが false の場合はfalseの値を生成し、それ以外の場合はtrueの値を生成しています。

論理的含意p は q を意味する( p ⇒ q、またはまれにCpqと表記される) に関連付けられた真理値表は次のとおりです。

物質的条件文「if p then q」 （ p → qと表記）に関連付けられた真理値表は次のとおりです。

p ⇒ qとp → q は¬p ∨ qと同等です。

論理等価性(双条件または排他的論理和とも呼ばれる) は、 2 つの論理値(通常は 2 つの命題の値)に対する演算であり、両方のオペランドが false の場合、または両方のオペランドが true の場合にtrueの値を生成します。

p XNOR q ( p ↔ q、Epq、p = q、p ≡ qとも表記される)の真理値表は次のとおりです。

したがって、p と q の真理値が同じ場合 (両方とも真または両方とも偽)、p EQ q は真となり、真理値が異なる場合は偽となります。

排他的論理和は、2 つの論理値(通常は 2 つの命題の値)に対する演算であり、そのオペランドの両方ではなく 1 つが true の場合に trueの値を生成します。

p XOR q ( Jpqまたはp ⊕ qとも表記)の真理値表は次のとおりです。

2 つの命題の場合、XOR は(p ∧ ¬q) ∨ (¬p ∧ q) と表記することもできます。

論理NANDは、2 つの論理値(通常は 2 つの命題の値)に対する演算であり、両方のオペランドが true の場合にfalseの値を生成します。言い換えると、少なくとも 1 つのオペランドが false の場合に trueの値を生成します。

p NAND q ( p ↑ q、Dpq、またはp | qとも表記)の真理値表は次のとおりです。

論理演算を複合演算、つまり他の演算から構築または合成された演算として表現すると便利な場合がよくあります。基本または「プリミティブ」とみなされる演算と、複合または「派生」とみなされる演算に応じて、このような合成は多数可能です。

論理 NAND の場合は、NOT と AND の複合として明確に表現できます。

連言の否定: ¬( p  ∧  q )、および否定の選言: (¬ p ) ∨ (¬ q ) は、次のように表すことができます。

論理NORは、2 つの論理値(通常は 2 つの命題の値)に対する演算で、両方のオペランドが偽の場合にtrueの値を生成します。言い換えると、少なくとも 1 つのオペランドが真の場合にfalseの値を生成します。↓ は、発明者であるCharles Sanders PeirceにちなんでPeirce 矢印とも呼ばれ、唯一十分な演算子です。

p NOR q ( p ↓ q、またはXpqとも表記)の真理値表は次のとおりです。

選言の否定 ¬( p  ∨  q ) と否定の連言 (¬ p ) ∧ (¬ q ) は次のように表すことができます。

関数引数pとqに論理値を割り当てるたびに、 NAND と NOR の表形式の導出を調べると、 ¬( p  ∧  q ) と (¬ p ) ∨ (¬ q ) および ¬( p  ∨  q ) と (¬ p ) ∧ (¬ q ) の関数値のパターンが同一であることがわかります。したがって、各ペアの最初の式と 2 番目の式は論理的に同等であり、論理値のみに関係するすべてのコンテキストで互いに置き換えることができます。

この同値性はド・モルガンの法則の 1 つです。

• ボチェンスキー、ユゼフ・マリア(1959)。数理論理学の精密書。バード、オットー訳。 D.レイデル。土井：10.1007/978-94-017-0592-9。ISBN 978-94-017-0592-9。
• エンダートン、H. (2001)。論理学への数学的入門（第2版）。ハーコート・アカデミック・プレス。ISBN 0-12-238452-0。
• クワイン、WV (1982)。論理の方法（第4版）。ハーバード大学出版局。ISBN 978-0-674-57175-4。

• 「真理値表」、数学百科事典、EMS Press、2001 [1994]
• 真理値表、トートロジー、論理的同値性
• Anellis, Irving H. (2011). 「Peirce の真理関数分析と真理値表の起源」. arXiv : 1108.2429 [math.HO].
• 真理値表をブール式に変換する