命題論理式

命題論理式（めいだいろんりしき、テンプレート:Lang-en-short）は、命題論理における整式（well-formed formula）の一種であり、構文的に適切に構成された論理式である。命題論理式のすべての変数に真理値が与えられると、一意の真理値が定まる。命題論理式は命題式（propositional expression）、文（sentence）、あるいは文論理式（sentential formula）とも呼ばれる。

命題論理式は、「5は3より大きい」のような単純な命題や、p・q といった命題変数から、NOT、AND、OR、IMPLIESなどの論理結合子（論理演算子）を用いて構成される。例えば:

(p AND NOT q) IMPLIES (p OR q)

数学において、命題論理式はしばしば単に「命題」と呼ばれるが、より正確には、命題論理式は命題そのものではなく、命題—議論の対象となる形式的対象—を表示する形式表現である。これはちょうど「テンプレート:Nowrap」という式が値そのものではなく値を表示するのと同様である。文脈によっては、この区別を保持することが重要になる。

命題

命題論理の目的のために、命題（発話、文、主張）は単純なものと複合なものに分けられる。 複合命題は文論理的結合子によって結び付けられたものとみなされる。最もよく使われる結合子としては、「AND」「OR」「IF ... THEN ...」「NEITHER ... NOR ...」「... IS EQUIVALENT TO ...」などがある。接続的なセミコロン「;」や「BUT（しかし）」は「AND」の表現とみなされる。一連の離散的な文は「AND」で結び付けられたものとみなされ、形式的な分析では単純命題の列に対して再帰的な「括弧規則」が適用される（整式についての詳細は後述参照）。

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

単純命題は宣言的な性質を持ち、特定の感覚的対象の状態や性質についての主張を行う。例:「この牛は青い」「コヨーテがいる！」（「そのコヨーテはあの岩の陰にいるのだ。」）。 したがって、単純な「原始的」主張は特定の対象または特定の心的状態についてのものでなければならない。少なくとも主語（思考または観察の直接の対象）、動詞（能動態・現在形が望ましい）、そして場合によっては形容詞や副詞を持つ必要がある。「犬！」は「犬が見える」を示唆するかもしれないが、曖昧すぎるとして棄却されるべきである。

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

命題論理においては、複合命題は通常、一連の単純文に言い換えることができるが、結果はぎこちなく聞こえることが多い。

命題論理式と述語論理式の関係

述語論理は命題論理よりも一歩進んで「命題の内部構造の分析」を行う。 単純文を (i) 主語（言説の対象、単数または複数）と (ii) 述語（対象の性質・属性を主張する動詞または動詞句）の二部分に分解する。述語論理はさらに「主語|述語」の形式（ここで | は記号の連結を表す）を「___|述語」という空白主語の構造に一般化し、述語はさらにその性質を持つすべてのものへと一般化される。

例: 「この青い豚には翼がある」は命題論理では「この豚には翼がある」AND「この豚は青い」という2文になり、その内部構造は考慮されない。一方、述語論理では最初の文は「この豚」を主語、「翼がある」を述語に分解する。したがって、対象「この豚」は「翼のあるもの」のクラス（集合）のメンバーであることを主張する。2番目の文は「この豚」が「青い」という属性を持ち、「青いもの」のクラスのメンバーであることを主張する。AND で結ばれた2文を次のように書くことができる:

p|W AND p|B

「この豚」を「翼のあるもの」と「青いもの」の2クラスの（潜在的）メンバーに一般化することは、それらのクラスとの真理関係を持つことを意味する。すなわち、「翼のあるもの」という言説の領域が与えられたとき、p がこの領域のメンバーであるかどうかを確認できる。したがって W（翼性）と p（豚）と { T, F } の間には関係があり、W(p) は { T, F } の値を取る。同様に B（青性）と p（豚）についても B(p) は { T, F } の値を取る。そこで「B(p) AND W(p)」という接続された主張全体の真理値を分析できる:

( B(p) AND W(p) ) → { T, F }

特に、「すべて」「いくつか」「少数」「一つの」などの論理量化子を用いる単純文は述語論理によって扱われる。新しい関数記法「F(x)」とともに2つの新しい記号が導入される: ∀（すべての）と ∃（…が存在する）。述語論理は命題論理とは異なり、次の命題の形式的妥当性を証明できる:

「すべての青い豚は翼を持つが、翼を持たない豚もいる。したがって、青くない豚もいる。」

同一性

タルスキは、同一性（IDENTITY）の概念（論理的同値とは区別される）は命題論理の外にあると主張するが、数学や諸科学に役立つ論理を構築するためには同一性の「理論」が含まれなければならないと述べる。 著者によっては「同一性を含む述語論理」と明示してこの拡張を強調する。詳細は後述参照。

命題の代数（命題論理）

テンプレート:Essay-like 代数（そこには様々な種類がある）とは、大まかに定義すれば、変数と呼ばれる記号の集まりを、括弧 (, ) や *, +, ~, &, ∨, =, ≡, ∧, ￢ などの記号のサブセットとともに、一定の規則体系の中で操作する方法である。これらの記号、およびそれらの整式な文字列は対象を表示するとされるが、特定の代数体系内ではこれらの対象に意味はない。したがって、代数の中での作業は、記号の構文論(記号形成)の特定の法則(規則)に従う演習となり、記号の意味論(意味)を扱うものではない。意味は代数の外部に求めなければならない。

代数において整式の記号列—論理式—が代数外でも有用であるためには、記号に意味が割り当てられ、最終的に変数に値が割り当てられる。そして一連の規則によって論理式が評価される。

値が2つだけに制限され、命題結合子によって結ばれた単純文（例: 発話や書かれた主張）の概念に適用される場合、この記号・規則・評価方法の代数体系全体は通常命題論理（センテンシャル計算）と呼ばれる。

算術代数のいくつかの馴染み深い規則は命題の代数でも成立するが（例: AND と OR の交換法則と結合法則）、成立しないものもある（例: AND, OR, NOT の分配法則）。

命題論理式の有用性

分析: 演繹的推論において、哲学者・修辞学者・数学者は議論を論理式に還元し、真理表を用いてその正しさ（健全性）を研究する。例えば、以下の議論は健全だろうか:

「意識が人工知能にとって十分条件であり、意識を持つ存在だけがチューリングテストに合格できるとすれば、ロボットが人工知能であると結論付ける前に、ロボットはチューリングテストに合格しなければならない。」

エンジニアは設計した論理回路を合成技法を用いて分析し、設計を簡略化するために様々な縮減・最小化技法を適用する。

合成: エンジニアは特に真理表から命題論理式（最終的には記号の回路になる）を合成する。例えば、変数「b」「a」と桁上げ入力「carry_in」「ci」、結果「carry_out」「co」と和 Σ が与えられた場合の2進加算の動作について真理表を書き下すことができる:

• 例: 行5では、( (b+a) + ci ) = ( (1+0) + 1 ) = 「2」という数になる。2進数で書くと 10₂ であり、右端の列に示されるように「co」=1、Σ=0 となる。

行	b	a	ci		(b+a)+ci	co	Σ
0	0	0	0		0	0	0
1	0	0	1		1	0	1
2	0	1	0		1	0	1
3	0	1	1		2	1	0
4	1	0	0		1	0	1
5	1	0	1		2	1	0
6	1	1	0		2	1	0
7	1	1	1		3	1	1

命題変数

命題論理式の最も単純な形は命題変数である。単純な（原子的な）命題を表す記号的表現は、しばしば p, q や P, Q などと命名された変数で表される。命題変数は「今日は土曜日だ」＝ p（ここで = は「…という変数名が割り当てられる」を意味する）や「私は月曜日だけ映画に行く」＝ q のような原子命題（主張）を表すことを意図している。

真理値の割当と論理式の評価

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

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

真理値は2つだけである: {真「T」, 偽「F」}。経験論者はすべての命題を2つの大きなクラスに分類する: 分析的—何があっても真（例: トートロジー）—と 総合的—経験から導出され、第三者による確認が可能（意味の検証理論）。 経験論者によれば、一般に総合命題の真理値に到達するには、まず言葉に意味（パターン照合テンプレート）を適用し、次にそれらを主張されていることと照合しなければならない。例えば、「あの牛はテンプレート:Blue！」という発言。これは真か? 確かに私はそう言った。そして私は青い牛を見ているかもしれない—嘘をついていない限り、私の（誤りがあるかもしれない）知覚の対象に相対的に、その発言は真である。しかし青い牛は「本当にそこにある」のか? 同じ窓から見えるものは何か? 確認のためには、「牛」と「テンプレート:Blue」両方の先行概念（テンプレート）と、感覚対象（もし存在するなら）にテンプレートを照合する能力が必要になる。テンプレート:Citation needed

工学における真理値

エンジニアは哲学者を悩ます真偽の概念を避けようとするが、最終的には測定器を信頼しなければならない。堅牢性を追求するエンジニアは、小さなライブラリから既知のオブジェクトを引き出すことを好む—大きな組み合わせでも動作が明確に予測可能なオブジェクトを（そのため「組み合わせ論理」という名称が付いた）。単一のオブジェクトの最小の動作数は2つであり（例: {OFF, ON}, {開, 閉}, {上, 下} など）、これらを {0, 1} に対応させる。そのような要素をデジタルと呼ぶ; 動作が連続する範囲を持つものはアナログと呼ぶ。アナログシステムで判断が必要な場合、エンジニアはしばしばコンパレータを使用してアナログ動作（ドアが45.32146%開いている）をデジタル（例: DOWN=0）に変換する。

したがって変数の意味と2値記号 {0, 1} の割当は、通常は複合的な対象の動作を表す論理式の「外部」から来る。例えば、2つの「リミットスイッチ」を持つガレージドアがある—UP 用に SW_U、DOWN 用に SW_D とラベルされたスイッチと、ドアの回路内にある他のもの。回路（回路図または実際のオブジェクト—ドア、スイッチ、ワイヤー、回路基板など）の検査から、スイッチ「SW_D」の接点が機械的に接触（「閉じた」）しているとき回路基板の「ノード22」が+0ボルトになり、ドアが95%「下げられた」位置にあること、そしてドアが95%上がっておりスイッチ SW_U の接点が機械的に接触（「閉じた」）しているとき「ノード29」が+0ボルトになることが判明するかもしれない。 エンジニアはこれらの電圧のすべての組み合わせ（全4通り）の意味を定義しなければならない。「悪い」組み合わせ（例: ノード22とノード29の両方が0ボルト—ドアが同時に開いており閉じていることを意味する）も含めて。回路はどんな電圧が加わっても、真・偽・正・誤・安全・危険の認識なしに盲目的に反応する。テンプレート:Citation needed

命題結合子

任意の命題論理式は、命題変数と他の命題論理式から命題結合子を用いて構成される。結合子の例として以下がある:

• 単項否定結合子: $\alpha$ が論理式なら、$\mathrm{\neg }\alpha$ も論理式である。
• 古典的な二項結合子 $\wedge ,\vee ,\to ,\leftrightarrow$: 例えば $\alpha$ と $\beta$ が論理式なら $(\alpha \to \beta )$ も論理式である。
• NAND、NOR、XOR などの他の二項結合子
• 三項結合子 IF ... THEN ... ELSE ...
• 定数の0項結合子 ⊤ と ⊥（あるいは定数 {T, F}, {1, 0} など）
• 「理論拡張」結合子 EQUALS（あるいは IDENTITY、または記号「=」—論理結合子 $\leftrightarrow$ とは区別される）

修辞学・哲学・数学の結合子

以下に、修辞学・哲学・数学に共通する結合子とその真理表を示す。使用される記号は著者や分野によって異なる。一般に「T」と「F」の略語は命題論理式の変数に適用される真・偽の評価を表す（例: 「あの牛は青い」という主張は「T」（真）または「F」（偽）の真理値を持つ）。

結合子には様々な言葉の用法がある。例えば「a IMPLIES b」は「IF a THEN b」とも言われる。これらのいくつかを表に示す。

						b only if a
						b IS SUFFICIENT FOR a	b PRECISELY WHEN a
						テンプレート:Not a typo IS NECESSARY FOR b	b IF AND ONLY IF a; b IFF a
					inclusive OR	IF b THEN a	b IS NECESSARY AND SUFFICIENT FOR a
		negation	negation	conjunction	disjunction	implication	biconditional
variables		NOT b	NOT a	b AND a	b OR a	b IMPLIES a	b IS logically equivalent TO a ***	f IS A tautology	NEITHER a NOR b	b stroke a	exclusive OR
b	a	¬(b)	¬(a)	(b ∧ a)	(b ∨ a)	(b → a)	(b ↔ a)	(f = formula)	(a NOR b)	(b|a)	various
F	F	T	T	F	F	T	T	T	T	T	F
F	T	T	F	F	T	T	F	T	F	T	T
T	F	F	T	F	T	F	F	T	F	T	T
T	T	F	F	T	T	T	T	T	F	F	F

工学的結合子

Engineering symbols have varied over the years, but these are commonplace. Sometimes they appear simply as boxes with symbols in them. "a" and "b" are called "the inputs" and "c" is called "the output".

一般に、工学的結合子は数学の結合子と同じであるが、「1」=「T」、「0」=「F」として評価する傾向がある。これは最小項とカルノー図（後述）の概念を用いた論理式の分析・最小化および合成のためである。エンジニアはまた、ブールの概念（a*a = a）に由来する論理積と、ジェボンズの概念（a+a = a）に由来する論理和という言葉を用いる。

					logical product	logical sum			half-adder (no carry)
									exclusive OR
row number	variables		NOT	NOT	AND	OR	NAND	NOR	XOR
b*21+a*20	b	a	~(b)	~(a)	(b & a)	(b ∨ a)	~(b & a)	~(b ∨ a)	⊕
0	0	0	1	1	0	0	1	1	0
1	0	1	1	0	0	1	1	0	1
2	1	0	0	1	0	1	1	0	1
3	1	1	0	0	1	1	0	0	0

CASEコネクティブ: IF ... THEN ... ELSE ...

IF ... THEN ... ELSE ... 結合子は、再帰理論と計算理論における CASE 演算子の最も単純な形として現れ、条件付きジャンプ（ゴートゥー、分岐）を担う結合子である。この1つの結合子から他のすべての結合子を構成できる（後述参照）。「IF c THEN b ELSE a」は含意のように聞こえるが、最も縮減された形では「a」または「b」の2つの代替のいずれかを決定して提供するスイッチである（C言語のswitch文という名称の由来）。

以下の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 に進む') OR ('カウンタがゼロでない' AND '命令 a に進む') )

したがって IF ... THEN ... ELSE は—含意とは異なり—最初の命題が偽（(c → b) の c = F）のときに曖昧な「真」に評価されることがない。例えば、多くの人が以下の複合命題を無意味なノン・セクイトゥルとして拒絶するだろう。2番目の文が最初の文と意味的につながっていないからである。

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

この問題を認識して、命題論理における形式的含意の記号 → は、日常的・直感的な含意と区別するために実質的含意と呼ばれる。テンプレート:Efn

IF ... THEN ... ELSE 構成を用いることで論争を避けられる。なぜなら2つの明示された代替間で完全に決定論的な選択を提供するからである; 2つの「オブジェクト」（代替 b と a）を提供し、それらの間を網羅的かつ明確に選択する。 以下の真理表において、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 演算子をマルチプレクサと呼ぶ。

											d1																		d2
row	c	b	a		(	(	c	→	b	)	&	(	~	(	c	)	→	a	)	)	=d1		(	(	c	&	b	)	∨	(	~	(	c	)	&	a	)	)	=d2
0	0	0	0				0	1	0		0		1		0		0	0			0				0	0	0		0		1		0		0	0			0
1	0	0	1				0	1	0		1		1		0		1	1			1				0	0	0		1		1		0		1	1			1
2	0	1	0				0	1	1		0		1		0		0	0			0				0	0	1		0		1		0		0	0			0
3	0	1	1				0	1	1		1		1		0		1	1			1				0	0	1		1		1		0		1	1			1
4	1	0	0				1	0	0		0		0		1		1	0			0				1	0	0		0		0		1		0	0			0
5	1	0	1				1	0	0		0		0		1		1	1			0				1	0	0		0		0		1		0	1			0
6	1	1	0				1	1	1		1		0		1		1	0			1				1	1	1		1		0		1		0	0			1
7	1	1	1				1	1	1		1		0		1		1	1			1				1	1	1		1		0		1		0	1			1

IDENTITY and evaluation

The first table of this section stars *** the entry logical equivalence to note the fact that "Logical equivalence" is not the same thing as "identity". For example, most would agree that the assertion "That cow is blue" is identical to the assertion "That cow is blue". On the other hand, logical equivalence sometimes appears in speech as in this example: " 'The sun is shining' means 'I'm biking' " Translated into a propositional formula the words become: "IF 'the sun is shining' THEN 'I'm biking', AND IF 'I'm biking' THEN 'the sun is shining'":

"IF 's' THEN 'b' AND IF 'b' THEN 's' " is written as ((s → b) & (b → s)) or in an abbreviated form as (s ↔ b). As the rightmost symbol string is a definition for a new symbol in terms of the symbols on the left, the use of the IDENTITY sign = is appropriate:

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

Different authors use different signs for logical equivalence: ↔ (e.g. Suppes, Goodstein, Hamilton), ≡ (e.g. Robbin), ⇔ (e.g. Bender and Williamson). Typically identity is written as the equals sign =. One exception to this rule is found in Principia Mathematica. For more about the philosophy of the notion of IDENTITY see Leibniz's law.

As noted above, Tarski considers IDENTITY to lie outside the propositional calculus, but he asserts that without the notion, "logic" is insufficient for mathematics and the deductive sciences. In fact the sign comes into the propositional calculus when a formula is to be evaluated.

In some systems there are no truth tables, but rather just formal axioms (e.g. strings of symbols from a set { ~, →, (, ), variables p₁, p₂, p₃, ... } and formula-formation rules (rules about how to make more symbol strings from previous strings by use of e.g. substitution and modus ponens). the result of such a calculus will be another formula (i.e. a well-formed symbol string). Eventually, however, if one wants to use the calculus to study notions of validity and truth, one must add axioms that define the behavior of the symbols called "the truth values" {T, F} ( or {1, 0}, etc.) relative to the other symbols.

For example, Hamilton uses two symbols = and ≠ when he defines the notion of a valuation v of any well-formed formulas (wffs) A and B in his "formal statement calculus" L. A valuation v is a function from the wffs of his system L to the range (output) { T, F }, given that each variable p₁, p₂, p₃ in a wff is assigned an arbitrary truth value { T, F }. テンプレート:NumBlk テンプレート:NumBlk

The two definitions (テンプレート:EquationNote) and (テンプレート:EquationNote) define the equivalent of the truth tables for the ~ (NOT) and → (IMPLICATION) connectives of his system. The first one derives F ≠ T and T ≠ F, in other words " v(A) does not mean v(~A)". Definition (テンプレート:EquationNote) specifies the third row in the truth table, and the other three rows then come from an application of definition (テンプレート:EquationNote). In particular (テンプレート:EquationNote) assigns the value F (or a meaning of "F") to the entire expression. The definitions also serve as formation rules that allow substitution of a value previously derived into a formula:

		v(A→B)
(	v(A)	→	v(B)	)
	F	T	F
	F	T	T
	T	F	F
	T	T	T

Some formal systems specify these valuation axioms at the outset in the form of certain formulas such as the law of contradiction or laws of identity and nullity. The choice of which ones to use, together with laws such as commutation and distribution, is up to the system's designer as long as the set of axioms is complete (i.e. sufficient to form and to evaluate any well-formed formula created in the system).

同一性と評価

このセクションの最初の表では、「論理的同値」は「同一性」と同じものではないことを注記するために「論理的同値」の項目に *** を付けている。例えば、「あの牛は青い」という主張は「あの牛は青い」という主張と同一であることにほとんどの人が同意するだろう。一方、論理的同値は会話で時に現れる。例えば「'太陽が輝いている'とは'私は自転車に乗っている'ということだ」と言う場合、命題論理式に翻訳すると「'太陽が輝いているなら自転車に乗っており、自転車に乗っているなら太陽が輝いている'」となる:

「'もし s ならば b、かつもし b ならば s'」は ((s → b) & (b → s)) と書かれ、略記法では (s ↔ b) となる。右端の記号列が左の記号を用いた新しい記号の定義であるため、IDENTITY 記号 = の使用が適切である:

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

著者によって論理的同値に異なる記号を用いる: ↔（例: Suppes, Goodstein, Hamilton）、≡（例: Robbin）、⇔（例: Bender and Williamson）。同一性は通常等号 = で書かれる。この規則の例外は『プリンキピア・マテマティカ』に見られる。同一性の概念の哲学についてはライプニッツの法則を参照。

上述のように、タルスキは IDENTITY が命題論理の外にあると考えるが、その概念なしでは「論理」は数学と演繹的諸科学に不十分であると主張する。実際この記号は、論理式が評価されるときに命題論理に入ってくる。

体系によっては真理表がなく、単に形式的公理（例えば {~, →, (, ), 変数 p₁, p₂, p₃, ...} からなる記号列）と論理式形成規則（例えば代入やモーダス・ポネンスを用いて以前の記号列からさらに記号列を作る規則）だけの場合がある。このような計算の結果もまた論理式（すなわち整式な記号列）になる。しかし最終的に、妥当性と真理の概念を研究するために計算を使用したい場合、「真理値」{T, F}（または{1, 0}など）と呼ばれる記号の動作を他の記号に対して定義する公理を追加しなければならない。

例えば、Hamiltonは「形式的命題計算」L における任意の整式（wff）A と B の付値 vの概念を定義する際に2つの記号 = と ≠ を使用する。付値 v は体系 L の wff から {T, F}（各変数 p₁, p₂, p₃ に任意の真理値 {T, F} が割り当てられる）への関数である。 テンプレート:NumBlk テンプレート:NumBlk

2つの定義（テンプレート:EquationNote）と（テンプレート:EquationNote）は体系の ~（NOT）と →（IMPLICATION）結合子の真理表に相当するものを定義する。最初の定義から F ≠ T と T ≠ F が導出される。つまり「v(A) は v(~A) を意味しない」。定義（テンプレート:EquationNote）は真理表の3行目を指定し、残りの3行は定義（テンプレート:EquationNote）の適用から導かれる。特に（テンプレート:EquationNote）は式全体に F の値（つまり「F」の意味）を割り当てる。定義はまた、以前に導出した値を論理式に代入することを可能にする代入規則としても機能する: | ) |- style="font-size:9pt" align="center" | Height="12" | | F |style="background-color:#E5E0EC" | T | F | |- style="font-size:9pt" align="center" | Height="12" | | F |style="background-color:#E5E0EC" | T | T | |- style="font-size:9pt" align="center" | Height="12" | | T |style="background-color:#CCC0DA" | F | F | |- style="font-size:9pt" align="center" | Height="12" | | T |style="background-color:#E5E0EC" | T | T | |}

Some formal systems specify these valuation axioms at the outset in the form of certain formulas such as the law of contradiction or laws of identity and nullity. The choice of which ones to use, together with laws such as commutation and distribution, is up to the system's designer as long as the set of axioms is complete (i.e. sufficient to form and to evaluate any well-formed formula created in the system).

より複雑な論理式

上述のように、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 の列から構成され、括弧なしの省略形で書かれる。これらや他の結合子もさらなる結合子の構成要素として使用できる。修辞学者・哲学者・数学者は真理表と様々な定理を使用して論理式を分析・簡略化する。

電気工学では描かれた記号を線で接続し、その線は代入と置換の数学的行為を表す。次に真理表で図面を検証し、以下に示すカルノー図や定理を使用して式を簡略化する。このようにして工学者は「デコーダ」「エンコーダ」「多機能ゲート」「多数決論理」「2進加算器」「算術論理装置」などの多数の「組み合わせ論理」（すなわちフィードバックのない結合子）を生み出してきた。

定義

定義は、しばしば省略の目的で、新しい記号とその動作を作り出す。定義が提示されると、等価な記号または論理式のどちらの形も使用できる。以下の記号 =Df は Reichenbach の慣例に従っている。 記号セット {~, &, (, )} と変数から引き出した便利な定義の例を示す。各定義は代入または置換に使用できる論理的に同値な論理式を生成する:

• 新しい変数の定義: (c & d) =Df s
• OR: ~(~a & ~b) =Df (a ∨ b)
• IMPLICATION: (~a ∨ b) =Df (a → b)
• XOR: (~a & b) ∨ (a & ~b) =Df (a ⊕ b)
• 論理的同値: ( (a → b) & (b → a) ) =Df ( a ≡ b )

公理スキーマと定義スキーマ

上記の OR、IMPLICATION、XOR、論理的同値の定義は実際にはスキーマ(または「schemata」)であり、一般的な論理式の形式のモデル（例示・実例）であるが、変数として具体的な文字 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. ( (a ∨ 0) ≡ a )
2. ( (a & ~a) ≡ 0 )
3. ( (~a ∨ b) =Df (a → b) )
6. ( ~(~a) ≡ a )

テンプレート:Ordered list

帰納的定義

命題論理の古典的な提示（Enderton 2002 参照）では結合子 $\mathrm{\neg },\wedge ,\vee ,\to ,\leftrightarrow$ を用いる。命題変数の集合に対する論理式の集合は、次の条件を満たす最小の式の集合として帰納的に定義される:

• 集合内の各命題変数は論理式である。
• $\alpha$ が論理式なら $(\mathrm{\neg }\alpha )$ も論理式である。
• $\alpha$ と $\beta$ が論理式であり $◻$ が二項結合子 $\wedge ,\vee ,\to ,\leftrightarrow$ の一つならば、$(\alpha ◻\beta )$ は論理式である。

この帰納的定義は追加の結合子をカバーするように容易に拡張できる。

帰納的定義は閉包演算の言葉で言い換えることもできる（Enderton 2002）。V を命題変数の集合とし、X_V を V 内の記号、左右の括弧、および考慮するすべての論理結合子を含むアルファベットからなるすべての文字列の集合とする。各論理結合子は論理式構成演算、すなわち XX_V から XX_V への関数に対応する:

• 文字列 z が与えられたとき、演算 ${ℰ}_{\mathrm{\neg }}(z)$ は $(\mathrm{\neg }z)$ を返す。
• 文字列 y と z が与えられたとき、演算 ${ℰ}_{\wedge }(y,z)$ は $(y\wedge z)$ を返す。他の二項結合子に対応する類似の演算 ${ℰ}_{\vee }$、${ℰ}_{\to }$、${ℰ}_{\leftrightarrow }$ も存在する。

V に対する論理式の集合は、V を含み、すべての論理式構成演算に対して閉じている XX_V の最小部分集合として定義される。

論理式の解析

命題論理の以下の「法則」は複雑な論理式を「縮減」するために使用される。「法則」は真理表で容易に検証できる。各法則において、主（最外）結合子は論理的同値 ≡ または同一性 = と対応している。その n 個の異なる変数に対するすべての 2ⁿ 個の真理値の組み合わせの完全な分析は、この結合子の下に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。したがって、どちらの論理式もより大きな論理式の中で互いに代入できる。

|style="background-color:#FFFF99" | 1 | |style="background-color:#EAF1DD" | 1 | | 0 | |style="background-color:#DBE5F1" | 1 |style="background-color:#EAF1DD" | 1 | | 0 | | | |- style="font-size:9pt" align="center" | Height="12" | 0 | 1 |style="background-color:#A5A5A5" | | |style="background-color:#D7E4BC" | 0 | | 0 |style="background-color:#FDE9D9" | 1 | 1 | |style="background-color:#FFFF99" | 1 | |style="background-color:#EAF1DD" | 1 | | 0 | |style="background-color:#DBE5F1" | 0 |style="background-color:#EAF1DD" | 0 | | 1 | | | |- style="font-size:9pt" align="center" | Height="12" | 1 | 0 |style="background-color:#A5A5A5" | | |style="background-color:#D7E4BC" | 0 | | 1 |style="background-color:#FDE9D9" | 1 | 0 | |style="background-color:#FFFF99" | 1 | |style="background-color:#EAF1DD" | 0 | | 1 | |style="background-color:#DBE5F1" | 0 |style="background-color:#EAF1DD" | 1 | | 0 | | | |- style="font-size:9pt" align="center" | Height="12" | 1 | 1 |style="background-color:#A5A5A5" | | |style="background-color:#D7E4BC" | 0 | | 1 |style="background-color:#FDE9D9" | 1 | 1 | |style="background-color:#FFFF99" | 1 | |style="background-color:#EAF1DD" | 0 | | 1 | |style="background-color:#DBE5F1" | 0 |style="background-color:#EAF1DD" | 0 | | 1 | | | |}

Enterprising readers might challenge themselves to invent an "axiomatic system" that uses the symbols { ∨, &, ~, (, ), variables a, b, c }, the formation rules specified above, and as few as possible of the laws listed below, and then derive as theorems the others as well as the truth-table valuations for ∨, &, and ~. One set attributed to Huntington (1904) (Suppes:204) uses eight of the laws defined below.

If used in an axiomatic system, the symbols 1 and 0 (or T and F) are considered to be well-formed formulas and thus obey all the same rules as the variables. Thus the laws listed below are actually axiom schemas, that is, they stand in place of an infinite number of instances. Thus ( x ∨ y ) ≡ ( y ∨ x ) might be used in one instance, ( p ∨ 0 ) ≡ ( 0 ∨ p ) and in another instance ( 1 ∨ q ) ≡ ( q ∨ 1 ), etc.

結合子の優先順位（記号の順位）

一般に、命題論理式の分析と評価における混乱を避けるために、括弧を自由に使用できる。しかし著者はしばしば括弧を省略する。複雑な論理式を解析するには、まず各結合子（* を除く）が他の結合子に対して持つ優先順位または順位を知る必要がある。論理式を「整式化」するには、最高順位の結合子から始めてその構成要素の周りに括弧を追加し、順位を下げながら（その結合子が作用する範囲に十分注意して）進む。最高から最低の順に、述語記号 ∀x と ∃x、IDENTITY =、算術記号を完全性のために追加すると:テンプレート:Efn

≡

（論理的同値）

→

（含意）

&

（AND）

∨

（OR）

~

（NOT）

∀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) ) )

交換法則と結合法則

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 が2つ以上の記号を持つ論理式にかかる場合は括弧が必須、例えば ~(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 ）; 他の体系では以下の真理表で導出されることもある: The sign " = " (as distinguished from logical equivalence ≡, alternately ↔ or ⇔) symbolizes the assignment of value or meaning. Thus the string (a & ~(a)) symbolizes "0", i.e. it means the same thing as symbol "0" ". In some "systems" this will be an axiom (definition) perhaps shown as ( (a & ~(a)) =_Df 0 ); in other systems, it may be derived in the truth table below:

					c						taut	c
a		(	(	a	&	~	(	a	)	)	≡	0	)
0				0	0	1		0			1	0
1				1	0	0		1			1	0

• Commutation of equality: (a = b) ≡ (b = a)
• Identity for OR: (a ∨ 0) = a or (a ∨ F) = a
• Identity for AND: (a & 1) = a or (a & T) = a
• Nullity for OR: (a ∨ 1) = 1 or (a ∨ T) = T
• Nullity for AND: (a & 0) = 0 or (a & F) = F
• Complement for OR: (a ∨ ~a) = 1 or (a ∨ ~a) = T, law of excluded middle
• Complement for AND: (a & ~a) = 0 or (a & ~a) = F, law of contradiction

• 等価の可換性: (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

整式（wff）

論理式の重要な性質は、論理式を命題変数と論理結合子の観点からその構造を一意に解析できることである。論理式が上記のように中置記法で書かれている場合、論理式の定義における括弧の適切な使用によって一意的な読解が確保される。あるいは論理式をポーランド記法や逆ポーランド記法で書くことで括弧を全く不要にすることができる。

前節の中置論理式の帰納的定義はバッカス・ナウア形式の形式文法に変換できる:

<formula> ::= <propositional variable>
| ( ¬ <formula> )
| ( <formula> ∧ <formula>)
| ( <formula> ∨ <formula> )
| ( <formula> → <formula> )
| ( <formula> ↔ <formula> )

この文法に一致する任意の式は左右の括弧の数が均衡しており、論理式の空でない任意の初期セグメントは右括弧より左括弧の方が多いことを示すことができる。 この事実を使って論理式を解析するアルゴリズムを与えることができる。例えば、式 x が $(\mathrm{\neg }$ から始まるとする。2番目の記号の後から始めて、括弧が均衡している x の最短部分式 y を一致させる。x が論理式なら、この式の後に残る記号はちょうど1つであり、それは閉じ括弧であり、y 自体が論理式である。この考え方を使って論理式の再帰下降構文解析器を生成できる。

括弧カウントの例:

この方法は、（しばしば省略される）最外の括弧の評価が起こる結合子である主結合子を「1」として特定する。 また、真理表を使わずに論理式を評価するときに開始する最内の結合子（例えば「レベル6」で）も特定する。 A key property of formulas is that they can be uniquely parsed to determine the structure of the formula in terms of its propositional variables and logical connectives. When formulas are written in infix notation, as above, unique readability is ensured through an appropriate use of parentheses in the definition of formulas. Alternatively, formulas can be written in Polish notation or reverse Polish notation, eliminating the need for parentheses altogether.

The inductive definition of infix formulas in the previous section can be converted to a formal grammar in Backus-Naur form:

<formula> ::= <propositional variable>
| ( ¬ <formula> )
| ( <formula> ∧ <formula>)
| ( <formula> ∨ <formula> )
| ( <formula> → <formula> )
| ( <formula> ↔ <formula> )

It can be shown that any expression matched by the grammar has a balanced number of left and right parentheses, and any nonempty initial segment of a formula has more left than right parentheses. This fact can be used to give an algorithm for parsing formulas. For example, suppose that an expression x begins with $(\mathrm{\neg }$. Starting after the second symbol, match the shortest subexpression y of x that has balanced parentheses. If x is a formula, there is exactly one symbol left after this expression, this symbol is a closing parenthesis, and y itself is a formula. This idea can be used to generate a recursive descent parser for formulas.

Example of parenthesis counting:

This method locates as "1" the principal connective テンプレート:-- the connective under which the overall evaluation of the formula occurs for the outer-most parentheses (which are often omitted). It also locates the inner-most connective where one would begin evaluatation of the formula without the use of a truth table, e.g. at "level 6".

	start	(	(	(	c	&	d	)	V	(	p	&	~	(	(	c	&	~	(	d	)	)	)	)	)	=	(	(	(	c	&	d	)	V	(	p	&	d	)	)	V	(	p	&	~	(	c	)	)	)	)
count	0	1	2	3	3	3	3	2	2	3	3	3	3	4	5	5	5	5	6	6	5	4	3	3	1	1	2	3	4	4	4	4	3	3	4	4	4	4	3	2	2	3	3	3	3	3	3	3	2	1	0

Well-formed formulas versus valid formulas in inferences

The notion of valid argument is usually applied to inferences in arguments, but arguments reduce to propositional formulas and can be evaluated the same as any other propositional formula. Here a valid inference means: "The formula that represents the inference evaluates to "truth" beneath its principal connective, no matter what truth-values are assigned to its variables", i.e. the formula is a tautology.

整式と有効な推論

有効な議論の概念は通常推論における議論に適用されるが、議論は命題論理式に還元され、他の命題論理式と同様に評価できる。ここで有効な推論とは「推論を表す論理式が、その変数にどんな真理値が割り当てられても、主結合子の下で真に評価される」ことを意味する、すなわち論理式はトートロジーである。 論理式が整式でも有効でもない場合がある。別の言い方をすると: 「整式であることは論理式が有効であるための必要条件であるが十分条件ではない。」整式かつ有効かどうかを知る唯一の方法は、真理表によって検証するか「法則」を使用することである:

Well-formed formulas versus valid formulas in inferences

The notion of valid argument is usually applied to inferences in arguments, but arguments reduce to propositional formulas and can be evaluated the same as any other propositional formula. Here a valid inference means: "The formula that represents the inference evaluates to "truth" beneath its principal connective, no matter what truth-values are assigned to its variables", i.e. the formula is a tautology. Quite possibly a formula will be well-formed but not valid. Another way of saying this is: "Being well-formed is necessary for a formula to be valid but it is not sufficient." The only way to find out if it is both well-formed and valid is to submit it to verification with a truth table or by use of the "laws":

• Example 1: What does one make of the following difficult-to-follow assertion? Is it valid? "If it's sunny, but if the frog is croaking then it's not sunny, then it's the same as saying that the frog isn't croaking." Convert this to a propositional formula as follows:

  " IF (a AND (IF b THEN NOT-a) THEN NOT-a" where " a " represents "its sunny" and " b " represents "the frog is croaking":

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

  This is well-formed, but is it valid? In other words, when evaluated will this yield a tautology (all T) beneath the logical-equivalence symbol ≡ ? The answer is NO, it is not valid. However, if reconstructed as an implication then the argument is valid.

  "Saying it's sunny, but if the frog is croaking then it's not sunny, implies that the frog isn't croaking."

  Other circumstances may be preventing the frog from croaking: perhaps a crane ate it.

• Example 2 (from Reichenbach via Bertrand Russell):

  "If pigs have wings, some winged animals are good to eat. Some winged animals are good to eat, so pigs have wings."

  ( ((a) → (b)) & (b) → (a) ) is well formed, but an invalid argument as shown by the red evaluation under the principal implication:

W	G												arg
a	b		(	(	(	a	->	b	)	&	b	)	->	a	)
0	0					0	1	0		0	0		1	0
0	1					0	1	1		1	1		0	0
1	0					1	0	0		0	0		1	1
1	1					1	1	1		1	1		1	1

縮減された結合子の集合

NAND 結合子（「ストローク」）の工学記号は任意の命題論理式を構成するために使用できる。真（1）と偽（0）がこの結合子の観点から定義できるという概念は左側の NAND の列に示されており、a NAND b の4通りの評価の導出は下部に示されている。より一般的な方法は NAND の定義を真理表から使用することである。

論理結合子の集合は、すべての命題論理式がその集合内の結合子だけを使った論理式とトートロジー的に同値である場合、完全と呼ばれる。完全な結合子の集合は多数あり、$\{\wedge ,\mathrm{\neg }\}$、$\{\vee ,\mathrm{\neg }\}$、$\{\to ,\mathrm{\neg }\}$ などが含まれる。単独で完全な二項結合子は2つあり、それぞれ NAND と NOR に対応する。 一部の対は完全でない、例えば $\{\wedge ,\vee \}$。

ストローク（NAND）

NAND に対応する二項結合子はシェファーストロークと呼ばれ、縦棒 | または上矢印 ↑ で書かれる。この結合子の完全性は『プリンキピア・マテマティカ』（1927:xvii）に記録されている。単独で完全であるため、他のすべての結合子はストロークのみを使って表現できる。例えば、記号「≡」が論理的同値を表す場合:

~p ≡ p|p

p → q ≡ p|~q

p ∨ q ≡ ~p|~q

p & q ≡ ~(p|q)

特に、0項結合子 $\mathrm{\top }$（真を表す）と $\mathrm{\perp }$（偽を表す）もストロークを使って表現できる:

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

$\mathrm{\perp }\equiv (\mathrm{\top }|\mathrm{\top })$

IF ... THEN ... ELSE

この結合子と {0, 1}（または {F, T} または {$\mathrm{\perp }$, $\mathrm{\top }$}）の組み合わせは完全な集合を形成する。以下において IF...THEN...ELSE 関係 (c, b, a) = d は ( (c → b) ∨ (~c → a) ) ≡ ( (c & b) ∨ (~c & a) ) = d を表す

(c, b, a):

(c, 0, 1) ≡ ~c

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

Normal forms

An arbitrary propositional formula may have a very complicated structure. It is often convenient to work with formulas that have simpler forms, known as normal forms. Some common normal forms include conjunctive normal form and disjunctive normal form. Any propositional formula can be reduced to its conjunctive or disjunctive normal form.

Reduction to normal form

A truth table will contain 2ⁿ rows, where n is the number of variables (e.g. three variables "p", "d", "c" produce 2³ rows). Each row represents a minterm. Each minterm can be found on the Hasse diagram, on the Veitch diagram, and on the Karnaugh map. (The evaluations of "p" shown in the truth table are not shown in the Hasse, Veitch and Karnaugh diagrams; these are shown in the Karnaugh map of the following section.)

Reduction to normal form is relatively simple once a truth table for the formula is prepared. But further attempts to minimize the number of literals (see below) requires some tools: reduction by De Morgan's laws and truth tables can be unwieldy, but Karnaugh maps are very suitable a small number of variables (5 or less). Some sophisticated tabular methods exist for more complex circuits with multiple outputs but these are beyond the scope of this article; for more see Quine–McCluskey algorithm.

Literal, term and alterm

In electrical engineering, a variable x or its negation ~(x) can be referred to as a literal. A string of literals connected by ANDs is called a term. A string of literals connected by OR is called an alterm. Typically the literal ~(x) is abbreviated ~x. Sometimes the &-symbol is omitted altogether in the manner of algebraic multiplication.

• Examples
  1. a, b, c, d are variables. ((( a & ~(b) ) & ~(c)) & d) is a term. This can be abbreviated as (a & ~b & ~c & d), or a~b~cd.
  2. p, q, r, s are variables. (((p ∨ ~(q) ) ∨ r) ∨ ~(s) ) is an alterm. This can be abbreviated as (p ∨ ~q ∨ r ∨ ~s).

Minterms

In the same way that a 2ⁿ-row truth table displays the evaluation of a propositional formula for all 2ⁿ possible values of its variables, n variables produces a 2ⁿ-square Karnaugh map (even though we cannot draw it in its full-dimensional realization). For example, 3 variables produces 2³ = 8 rows and 8 Karnaugh squares; 4 variables produces 16 truth-table rows and 16 squares and therefore 16 minterms. Each Karnaugh-map square and its corresponding truth-table evaluation represents one minterm.

Any propositional formula can be reduced to the "logical sum" (OR) of the active (i.e. "1"- or "T"-valued) minterms. When in this form the formula is said to be in disjunctive normal form. But even though it is in this form, it is not necessarily minimized with respect to either the number of terms or the number of literals.

In the following table, observe the peculiar numbering of the rows: (0, 1, 3, 2, 6, 7, 5, 4, 0). The first column is the decimal equivalent of the binary equivalent of the digits "cba", in other words:

• Example

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

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

This numbering comes about because as one moves down the table from row to row only one variable at a time changes its value. Gray code is derived from this notion. This notion can be extended to three and four-dimensional hypercubes called Hasse diagrams where each corner's variables change only one at a time as one moves around the edges of the cube. Hasse diagrams (hypercubes) flattened into two dimensions are either Veitch diagrams or Karnaugh maps (these are virtually the same thing).

When working with Karnaugh maps one must always keep in mind that the top edge "wrap arounds" to the bottom edge, and the left edge wraps around to the right edge—the Karnaugh diagram is really a three- or four- or n-dimensional flattened object.

decimal equivalent of (c, b, a)	c	b	a	minterm
0	0	0	0	(~c & ~b & ~a)
1	0	0	1	(~c & ~b & a)
3	0	1	1	(~c & b & a)
2	0	1	0	(~c & b & ~a)
6	1	1	0	(c & b & ~a)
7	1	1	1	(c & b & a)
5	1	0	1	(c & ~b & a)
4	1	0	0	(c & ~b & ~a)
0	0	0	0	(~a & ~b & ~c)

標準形

任意の命題論理式は非常に複雑な構造を持つ場合がある。標準形と呼ばれる単純な形の論理式を扱うことがしばしば便利である。一般的な標準形には連言標準形（conjunctive normal form）と選言標準形（disjunctive normal form）がある。任意の命題論理式はその連言標準形または選言標準形に縮減できる。

標準形への縮減

真理表は変数の数を n とすると 2ⁿ 行を含む（例: 3変数「p」「d」「c」は 2³ 行を生成する）。各行は最小項を表す。各最小項はハッセ図、ベイッチ図、カルノー図上に見つけることができる。

標準形への縮減は一旦論理式の真理表が準備されれば比較的簡単である。しかしリテラル数の最小化のためにはいくつかのツールが必要である: ド・モルガンの法則と真理表による縮減は扱いにくいが、カルノー図は少数の変数（5つ以下）に対して非常に適している。複数の出力を持つより複雑な回路に対しては洗練された表形式の方法が存在するが、それらはこの記事の範囲を超えている; 詳細についてはクワイン・マクラスキー法を参照。

リテラル・項・互換項

電気工学において、変数 x またはその否定 ~(x) をリテラルと呼ぶ。AND で結ばれたリテラルの列を項（term）と呼ぶ。OR で結ばれたリテラルの列を互換項（alterm）と呼ぶ。通常 ~(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ⁿ 行の真理表が n 変数の論理式のすべての 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次元の平坦化されたオブジェクトである。

Reduction by use of the map method (Veitch, Karnaugh)

Veitch improved the notion of Venn diagrams by converting the circles to abutting squares, and Karnaugh simplified the Veitch diagram by converting the minterms, written in their literal-form (e.g. ~abc~d) into numbers. The method proceeds as follows:

Produce the formula's truth table

Produce the formula's truth table. Number its rows using the binary-equivalents of the variables (usually just sequentially 0 through n-1) for n variables.

Technically, the propositional function has been reduced to its (unminimized) conjunctive normal form: each row has its minterm expression and these can be OR'd to produce the formula in its (unminimized) conjunctive normal form.

Example: ((c & d) ∨ (p & ~(c & (~d)))) = q in conjunctive normal form is:

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

However, this formula be reduced both in the number of terms (from 4 to 3) and in the total count of its literals (12 to 6).

row	Minterms	p	d	c	(	(	c	&	d	)	∨	(	p	&	~	(	(	c	&	~	(	d	)	)	)	)	)	テンプレート:Active minterms	Formula in conjunctive normal form
0	( ~p & ~d & ~c )	0	0	0			0	0	0		0		0	0	1			0	0	1		0
1	( ~p & ~d & c)	0	0	1			1	0	0		0		0	0	0			1	1	1		0
2	( ~p & d & ~c )	0	1	0			0	0	1		0		0	0	1			0	0	0		1
3	( ~p & d & c )	0	1	1			1	1	1		1		0	0	1			1	0	0		1						(~p & d & c)
4	( p & ~d & ~c )	1	0	0			0	0	0		1		1	1	1			0	0	1		0						(~p & d & c)
5	( p & ~d & c )	1	0	1			1	0	0		0		1	0	0			1	1	1		0
6	( p & d & ~c )	1	1	0			0	0	1		1		1	1	1			0	0	0		1						(p & d & ~c)
7	( p & d & c )	1	1	1			0	1	1		1		1	1	1			1	0	0		1						( p & d & c )
											q																		= (~p&d&c) ∨ (~p&d&c) ∨ (p&d&~c ) ∨ (p&d&c )

Create the formula's Karnaugh map

Steps in the reduction using a Karnaugh map. The final result is the OR (logical "sum") of the three reduced terms.

Use the values of the formula (e.g. "p") found by the truth-table method and place them in their into their respective (associated) Karnaugh squares (these are numbered per the Gray code convention). If values of "d" for "don't care" appear in the table, this adds flexibility during the reduction phase.

Reduce minterms

Minterms of adjacent (abutting) 1-squares (T-squares) can be reduced with respect to the number of their literals, and the number terms also will be reduced in the process. Two abutting squares (2 x 1 horizontal or 1 x 2 vertical, even the edges represent abutting squares) lose one literal, four squares in a 4 x 1 rectangle (horizontal or vertical) or 2 x 2 square (even the four corners represent abutting squares) lose two literals, eight squares in a rectangle lose 3 literals, etc. (One seeks out the largest square or rectangles and ignores the smaller squares or rectangles contained totally within it. ) This process continues until all abutting squares are accounted for, at which point the propositional formula is minimized.

For example, squares #3 and #7 abut. These two abutting squares can lose one literal (e.g. "p" from squares #3 and #7), four squares in a rectangle or square lose two literals, eight squares in a rectangle lose 3 literals, etc. (One seeks out the largest square or rectangles.) This process continues until all abutting squares are accounted for, at which point the propositional formula is said to be minimized.

Example: The map method usually is done by inspection. The following example expands the algebraic method to show the "trick" behind the combining of terms on a Karnaugh map:

Minterms #3 and #7 abut, #7 and #6 abut, and #4 and #6 abut (because the table's edges wrap around). So each of these pairs can be reduced.

Observe that by the Idempotency law (A ∨ A) = A, we can create more terms. Then by association and distributive laws the variables to disappear can be paired, and then "disappeared" with the Law of contradiction (x & ~x)=0. The following uses brackets [ and ] only to keep track of the terms; they have no special significance:

• Put the formula in conjunctive normal form with the formula to be reduced:

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

• Idempotency (absorption) [ A ∨ A) = A:

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

• Associative law (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) ].

• Distributive law ( x & (y ∨ z) ) = ( (x & y) ∨ (x & z) ) :

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

• Commutative law and law of contradiction (x & ~x) = (~x & x) = 0:

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

• Law of identity ( x ∨ 0 ) = x leading to the reduced form of the formula:

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

Verify reduction with a truth table

row	Minterms	p	d	c	(	(	d	&	c	)	∨	(	p	&	d	)	∨	(	p	&	~	(	c	)	)
0	( ~p & ~d & ~c )	0	0	0			0	0	0		0		0	0	0		0		0	0	1		0
1	( ~p & ~d & c)	0	0	1			0	0	1		0		0	0	0		0		0	0	0		1
2	( ~p & d & ~c )	0	1	0			1	0	0		0		0	0	1		0		0	0	1		0
3	( ~p & d & c )	0	1	1			1	1	1		1		0	0	1		1		0	0	0		1
4	( p & ~d & ~c )	1	0	0			0	0	0		0		1	0	0		1		1	1	1		0
5	( p & ~d & c )	1	0	1			0	0	1		0		1	0	0		0		1	0	0		1
6	( p & d & ~c )	1	1	0			1	0	0		1		1	1	1		1		1	1	1		0
7	( p & d & c )	1	1	1			1	1	1		1		1	1	1		1		1	0	0		1
																	q

非述語的命題

次の例を定義として与えたとき、以下の推論をどう考えるか:

(1) 「この文は単純だ。」(2) 「この文は複合的で、AND によって結合されている。」

そこで「この文は単純だ」という文の最左の文に変数「s」を割り当てる。「複合的」を c = 「単純でない」~s として定義し、「この文は複合的だ」に c = ~s を割り当て; 「AND によって結合されている」に「j」を割り当てる。2番目の文は次のように表現できる:

( NOT(s) AND j )

これらの文 c = ~s と j に真理値を置くなら、すべて明らかに偽である: 例えば「この文は複合的だ」は偽（定義上単純だ）。したがってその連言（AND）は偽。しかし組み立てられた形では、その文は真である。

これは非述語的定義から生じるパラドックスの例である—すなわち、対象 m が性質 P を持つが、対象 m は性質 P の観点から定義される場合。 修辞学者または演繹的分析に携わる者に対する最善のアドバイスは、非述語的定義を避けることであるが、同時にそれらに注意を払うことでもある。なぜならそれらは確かにパラドックスを生み出す可能性があるからだ。一方、エンジニアはフィードバックを持つ命題論理式の形でそれらを活用する。

フィードバックを持つ命題論理式

命題論理式が自身の変数の一つとして現れるという概念は、論理式を変数に割り当てることを可能にする形成規則を必要とする。一般に公理体系や真理表体系において、これが起こることを禁じる規定（公理的または真理表的）はない。

最も単純な場合は OR 論理式がその入力の一つ自身になる場合に起こる（例: p = q）。(p ∨ s) = q から始め、p = q とする。q の「定義」が自身「q」だけでなく「s」と OR 結合子にも依存することを観察する。したがってこの q の定義は非述語的である。 2つの条件のいずれかが起こりうる: 発振またはメモリ。

論理式をブラックボックスとして考えると理解しやすい。論理式「ボックス」の「内部」で何が起こっているかの知識なしに外部からは、出力が入力だけの関数でなくなっているように見える。すなわち時に q を見ると 0 であり、時に 1 である。この問題を避けるためにボックス内の「隠れた」変数 p の状態（すなわち p に割り当てられてフィードバックされる q の値）を知らなければならない。これが知られると見かけ上の矛盾は消える。

フィードバックを持つ論理式の動作を理解（予測）するには、順序回路のより高度な分析が必要となる。フィードバックを持つ命題論理式は、その最も単純な形で状態機械につながり、さらにチューリングテープやカウンタマシンのカウンタの形のメモリにもつながる。これらの要素の組み合わせから、任意の境界のある計算モデル（例: チューリング機械、カウンタマシン、レジスタマシン、マッキントッシュコンピュータなど）を構築できる。

発振

抽象的な（理想的な）場合、最も単純な発振論理式は NOT がそれ自身にフィードバックされるものである: ~(~(p=q)) = q。真理表における抽象的（理想的）命題論理式の分析は、p=1 と p=0 の両方のケースで矛盾を明らかにする: p=1 のとき q=0 となるが、p=q であるためこれは不可能; p=0 と q=1 でも同様。

		q
p		~	(	p	)	= q
0		1		0		1	q と p が矛盾
1		0		1		0	q と p が矛盾

遅延を伴う発振: 遅延（理想的または非理想的）が p と q の間の抽象論理式に挿入されると、p は 1 と 0 の間で発振する: 101010...101... ad infinitum（無限に）。遅延と NOT のいずれかが抽象的（すなわち理想的）でない場合、使用する分析の種類は発振器を構成するオブジェクトの正確な性質に依存する; そのようなことは数学の外、工学の範疇に入る。

分析には遅延を挿入し、その後遅延と入力「p」の間でループを切断する必要がある。遅延は「q」を入力として「qd」（q 遅延）を出力とする一種の命題として見なされなければならない。この新しい命題は真理表に別の列を追加する。矛盾は今や「qd」と「p」の間にあり、赤で示され; 2つの安定状態が生じる:

			q
qd	p	(	~	(	p	)	= q
0	0		1		0		1	state 1
0	1		0		1		0	qd と p が矛盾
1	0		1		0		1	qd と p が矛盾
1	1		0		1		0	state 0

メモリ

OR の出力がその入力の一つにフィードバックされると最も単純なメモリが生じる。この場合、出力「q」が「p」にフィードバックされる。次に単純なのが、1回フリップの下に示す「フリップフロップ」である。この種の論理式の分析は、フィードバックパスを切断するか、またはパスに（理想的な）遅延を挿入することで行われる。切断パスとどこにも遅延が発生しないという仮定により、全状態（入力と出力の組み合わせ、例: (p=0, s=1, r=1) は矛盾を生じる）の一部に矛盾が生じる。遅延が存在する場合、これらの矛盾は単なる過渡状態であり、遅延が終了すると消える。右の図は状態遷移図と呼ばれる。

「クロック付きフリップフロップ」メモリ（「c」は「クロック」、「d」は「データ」）。データはクロック c=0 の間はいつでも変化できる; クロック c=1 のとき、出力 q はデータ d の値を「追従」する。c が 1 から 0 になると d = q の値が「トラップ」され、d が何をしても（c が 0 のままである限り）q に現れ続ける。

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

真理表は入力の p = q_遅延 と出力の q の間に矛盾が生じる行を明らかにする。フィードバックを「切断」した後、 真理表の構築は通常の方法で進む。しかしその後、すべての行で出力 q が今や独立した入力 p と比較され、p と q の間の矛盾（すなわち p=0 で q=1、または p=1 で q=0）が記録される（「線」が「再接続」されると矛盾律 ~(p & ~p) によって両方が不可能となる）。矛盾を明らかにする行は過渡状態として考えられるか、矛盾していて「不可能」として除外される。

1回フリップメモリ

OR の出力がその入力の一つにフィードバックされると最も単純なメモリが生じる。この場合、出力「q」が「p」にフィードバックされる。論理式が最初に p=0 & q=0 で評価（初期化）されると仮定すると、s=1 で「セット」されると1回「フリップ」する。その後、出力「q」は「フリップされた」状態（状態 q=1）で「q」を維持する。この時間依存の動作は1回フリップの右の状態遷移図に示される。

				q
p	s	(	s	∨	p	)	= q
0	0		0	0	0		0	状態0、s=0
0	1		1	1	0			q と p が矛盾
1	0		0	1	1		1	s=0 での状態1
1	1		1	1	1		1	s=1 での状態1

フリップフロップメモリ

次に単純なケースは1回フリップの下に示す「セットリセット」フリップフロップである。r=0 & s=0 で q=0 から始まると、1回フリップと同様に「セット」（s=1）される。しかしリセット「r」=1 のとき q=0 に「リセット」する規定がある。追加の複雑さはセット=1 とリセット=1 が同時に起こる場合に生じる。この論理式では、セット=1 は出力 q=1 を強制するので、(s=0 & r=1) のとき、フリップフロップはリセットされる。または (s=1 & r=0) のとき、フリップフロップはセットされる。s=1 ⇒ s=0 & r=1 ⇒ r=0 が同時に起こるという抽象（理想）的な場合、論理式 q は不定（決定不能）となる。「実際の」OR、AND、NOT の遅延により、最初は結果が不明だが、その後は予測可能となる。

					q
p	s	r	(	s	∨	(	p	&	~	(	r	)	)	)	= q
0	0	0		0	0		0	0	1		0				0	（s=0 & r=0）での状態0
0	0	1		0	0		0	0	0		1				0	（s=0 & r=1）での状態0
0	1	0		1	1		0	0	1		0					q と p が矛盾
0	1	1		1	1		0	0	0		1					q と p が矛盾
1	0	0		0	1		1	1	1		0				1	（s=0 & r=0）での状態1
1	0	1		0	0		1	0	0		1					q と p が矛盾
1	1	0		1	1		1	1	1		0				1	（s=1 & r=0）での状態1
1	1	1		1	1		1	0	0		1				1	s と r が同時に1の場合の状態1

クロック付きフリップフロップメモリ

「クロック付きフリップフロップ」メモリ（「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

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

							s			q			w	v				r	u
row	q	d	c	(	(	c	&	d	)	∨	(	q	&	~	(	(	c	&	~	(	d	)	)	)	)	)	=q	説明
0	0	0	0			0	0	0		0		0	0	1			0	0	1		0						0	（s=0 & r=0）での状態0、0が保持
1	0	0	1			1	0	0		0		0	0	0			1	1	1		0						0	（d=0 & c=1）での状態0: q=0 は d=0 を追従
2	0	1	0			0	0	1		0		0	0	1			0	0	0		1						0	（d=1 & r=0）での状態0、0が保持
3	0	1	1			1	1	1		1		0	0	1			1	0	0		1							q と p が矛盾
4	1	0	0			0	0	0		1		1	1	1			0	0	1		0						1	（d=0 & c=0）での状態1、1が保持
5	1	0	1			1	0	0		0		1	0	0			1	1	1		0							q と p が矛盾
6	1	1	0			0	0	1		1		1	1	1			0	0	0		1						1	（d=1 & c=0）での状態1、1が保持
7	1	1	1			1	1	1		1		1	1	1			1	0	0		1						1	（d=1 & c=1）での状態1: q=1 は d=1 を追従

歴史的発展

バートランド・ラッセル（1912:74）はアリストテレスに由来する3つの思考の法則を挙げている: (1) 同一律: 「あるものはあるものである。」(2) 矛盾律: 「何ものもあることと同時にないことはできない。」(3) 排中律: 「すべてのものはあるかないかのいずれかでなければならない。」

• 例: ここで O はある対象の存在または性質についての表現とする:
  1. 同一律: O = O
  2. 矛盾律: ~(O & ~(O))
  3. 排中律: (O ∨ ~(O))

排中律における「すべてのもの」という言葉の使用は、ラッセルによるこの法則の表現を議論の余地があるものにする。有限の対象の集まり（有限の「言説の領域」）—そのメンバーを一つずつ調べて主張の有無を確認できる—についての存在または性質に関する表現に限定されるなら、この法則は直観主義的に適切とみなされる。したがって「この対象は（集合の中に）存在するかしないかのいずれかでなければならない」または「この対象はこの性質を（集合の中の対象に相対的に）持つか持たないかのいずれかでなければならない」という主張は受け入れられる。ベン図で詳細を参照。

命題論理の起源はアリストテレスに遡るが、命題に適用される代数の概念は19世紀初頭まで待たなければならなかった。アリストテレスの三段論法の2000年の伝統への（逆）反応として、ジョン・ロックの『人間悟性論』（1690年）は記号論（記号の使用理論）という言葉を用いた。1826年までにリチャード・ウェイトリーはロックの記号論への共感を持ちながら三段論法の論理を批判的に分析した。ジョージ・ベンサムの研究（1827年）は「述語の量化」（今日では ∀ ≡ 「すべてについて」と記号化される）の概念をもたらした。ウィリアム・ハミルトンとオーガスタス・ド・モルガンの優先権争いによる「騒動」が「ジョージ・ブールに論理についての考えを書き上げ、1847年にMAL（数学的論理分析）として出版する意欲を与えた」（Grattan-Guinness and Bornet 1997:xxviii）。

彼らの貢献についてGrattan-GuinnessとBornetは次のようにコメントする:

「ブールの主要な単独革新は論理のための法則 [ xⁿ = x ] であった: それは性質 x を選ぶ心的行為と x を何度も選ぶ行為は x を一度選ぶことと同じであることを述べた... その帰結として彼は x•(1-x)=0 と x+(1-x)=1 という方程式を形成し、それぞれが彼にとって矛盾律と排中律を表していた」（p. xxviiff）。ブールにとって「1」は言説の領域であり「0」は無であった。

ゴットロープ・フレーゲの大規模な研究（1879年）は命題の形式的計算をもたらしたが、その記号体系はあまりにも難解なため、ある一人の人物—バートランド・ラッセル—を除いてほとんど影響を与えなかった。アルフレッド・ノース・ホワイトヘッドの学生として彼はフレーゲの研究を研究し、フレーゲが扱った二律背反—ラッセルのパラドックス—を巡って著名な（そして悪名高い）修正を提案した（1904年）。ラッセルの研究はホワイトヘッドとの共同作業につながり、1912年に『プリンキピア・マテマティカ』（PM）の第1巻を生み出した。ここで我々が「現代的」と考える命題論理が初めて現れた。特にPMは NOT と OR と主張記号 ⊦ を原始として導入する。これらの概念を用いて IMPLICATION → を定義し（def. *1.01: ~p ∨ q）、次に AND（def. *3.01: ~(~p ∨ ~q)）、次に EQUIVALENCE p ←→ q（*4.01: (p → q) & (q → p)）を定義する。

• ヘンリー・M・シェファー（1921年）とジャン・ニコは「ストローク」| という1つの結合子だけですべての命題論理式を表現するのに十分であることを実証した。
• エミール・ポスト（1921年）は「初等命題の一般理論への入門」において真理表による分析方法を発展させた。彼はニコのストローク | に言及している。
• ホワイトヘッドとラッセルは1927年のPM再版に序文を追加し、一部として「ストローク」の好意的な取り扱いを加えた。

計算とスイッチング論理:

• ウィリアム・エクルズとF・W・ジョーダン（1919年）は真空管で作られた「トリガーリレー」を記述した。
• ジョージ・スティビッツ（1937年）は機械式リレーを用いて2進加算器を発明した。彼はこれを自宅のキッチンテーブル上で製作した。

例: 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年代初頭に登場した。
• ウィラード・クワイン（1952年・1955年）、E・W・ベイッチ（1952年）、M・カルノー（1953年）は命題関数を簡略化するマップ法を開発した。
• ジョージ・H・ミーリー（1955年）とエドワード・F・ムーア（1956年）は順序（スイッチング回路）「機械」の理論を論じた。
• E・J・マクラスキーと H・ショアは命題（スイッチング）回路を簡略化する方法を開発した（1962年）。

参考文献

• テンプレート:Cite book
• テンプレート:Cite book
• テンプレート:Aut and テンプレート:Aut, 2005, A Short Course in Discrete Mathematics, Dover Publications, Mineola NY, テンプレート:ISBN.
• テンプレート:Aut, 2002, A Mathematical Introduction to Logic. Harcourt/Academic Press. テンプレート:ISBN
• テンプレート:Aut, (Pergamon Press 1963), 1966, (Dover edition 2007), Boolean Algebra, Dover Publications, Inc. Minola, New York, テンプレート:ISBN.
• テンプレート:Aut and Gérard Bornet 1997, George Boole: Selected Manuscripts on Logic and its Philosophy, Birkhäuser Verlag, Basil, テンプレート:ISBN (Boston).
• テンプレート:Aut 1978, Logic for Mathematicians, Cambridge University Press, Cambridge UK, テンプレート:ISBN.
• テンプレート:Aut 1965, Introduction to the Theory of Switching Circuits, McGraw-Hill Book Company, New York.
• テンプレート:Aut 1967, Computation: Finite and Infinite Machines, Prentice-Hall, Inc, Englewood Cliffs, N.J.
• テンプレート:Aut 1969, 1997, Mathematical Logic: A First Course, Dover Publications, Inc., Mineola, New York, テンプレート:ISBN (pbk.).
• テンプレート:Aut 1957 (1999 Dover edition), Introduction to Logic, Dover Publications, Inc., Mineola, New York. テンプレート:ISBN (pbk.).
• テンプレート:Aut 1941 (1995 Dover edition), Introduction to Logic and to the Methodology of Deductive Sciences, Dover Publications, Inc., Mineola, New York. テンプレート:ISBN (pbk.).
• テンプレート:Aut 1967, 3rd printing with emendations 1976, From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931, Harvard University Press, Cambridge, Massachusetts. テンプレート:ISBN (pbk.)
• テンプレート:Aut and テンプレート:Aut 1927 2nd edition, paperback edition to *53 1962, Principia Mathematica, Cambridge University Press.
• テンプレート:Aut 1968, Logic Design with Integrated Circuits, John Wiley & Sons, Inc., New York.

外部リンク

• テンプレート:Commonscatinline