変更要約: 初版
1.2論理とオートマトン
AND/OR/NOT等の論理演算とド・モルガンの法則、それらを物理的に実現する論理回路、プログラミング言語や通信プロトコルの構文を厳密に定義するBNFと文字列パターンを表す正規表現、そして状態遷移でシステムの振る舞いを表す有限オートマトンを学びます。
前節では数値そのものの表現を扱いました。この節では、その数値（特に真偽値）をどう組み合わせて判断を下すかという論理の世界に踏み込みます。条件分岐（if文）の裏側にある論理演算から、コンパイラが構文をチェックする仕組み（BNF・オートマトン）まで、擬似言語やプログラミング全般の土台となる考え方です。
1.2.1論理演算とド・モルガンの法則
- 論理演算＝真（true）・偽（false）の2値を対象とする演算。基本はAND（論理積）・OR（論理和）・NOT（否定）の3種で、擬似言語の
かつ/または/でない（英語ではand/or/not）に対応する。 - ド・モルガンの法則＝否定と論理積・論理和の関係を示す法則。
NOT (A AND B) = (NOT A) OR (NOT B)、NOT (A OR B) = (NOT A) AND (NOT B)。複雑な否定条件を分解して読みやすくする際に使う。 - 実務での使いどころ＝
if (在庫あり かつ 決済成功) でないという条件は、ド・モルガンの法則で在庫なし または 決済失敗と書き換えられ、条件分岐の意図が読み取りやすくなる。
1.2.2論理回路
- 論理回路＝論理演算を電子回路として物理的に実現したもの。AND回路・OR回路・NOT回路を基本ゲートとし、これらを組み合わせて加算器など複雑な演算回路を構成する。
- XOR（排他的論理和）＝2つの入力が異なるときのみ真になる演算。単純なAND/OR/NOTの組み合わせでも構成できるが、加算器の桁上げなしの和を求める箇所などで頻繁に使われる。
1.2.3BNFと正規表現
- BNF（Backus-Naur Form）＝プログラミング言語や通信プロトコルの構文（文法）を厳密に定義する記法。
<構文要素> ::= 定義の形で再帰的にルールを積み上げる。コンパイラの構文解析の基礎となる。 - 正規表現＝文字列のパターンを記述する表記法。
*（0回以上の繰り返し）・+（1回以上）・|（選択）などのメタ文字を使い、入力検証（メールアドレス形式のチェック等）や文字列検索に使われる。 - BNFとオートマトンは文法（構文の正しさ）を検証するという共通の目的を持つが、BNFは階層的な構文構造の記述に、有限オートマトンは状態遷移による単純なパターン（正規表現相当）の受理判定に向く。
「ド・モルガンの法則の変形（AND⇔ORの入れ替え＋各項の否定）」「BNF=構文の再帰的定義」「正規表現=パターンの記述、*/+/|の意味」が最頻出です。BNFと正規表現・有限オートマトンはどれも「文字列や構文の妥当性を判定する」道具であるという共通軸で整理すると混同しにくくなります。
1.2.4有限オートマトン
- 有限オートマトン（有限状態機械）＝有限個の状態と、入力に応じた状態遷移の規則で構成される計算モデル。ある状態から始まり、入力記号列を1つずつ読みながら状態を遷移し、最終的に受理状態にたどり着けば入力を「受理」する。
- 身近な例＝自動販売機（投入金額に応じた状態遷移）、信号機の制御、正規表現エンジンの内部実装。状態数が有限であることが「有限」オートマトンの名の由来。
あるECサイトの注文確定処理で、擬似言語の条件式 if (在庫あり かつ 決済成功) でない ならば エラー表示 を実装したところ、レビューで「否定とかつの組み合わせが読みにくい」と指摘されたとします。ここでド・モルガンの法則を適用すると、NOT (在庫あり AND 決済成功) は (NOT 在庫あり) OR (NOT 決済成功) と等価なので、条件式を if (在庫なし または 決済失敗) ならば エラー表示 と書き換えられます。両者は論理的に完全に同じ結果を返しますが、後者の方が「在庫切れか決済失敗のどちらかが起きたらエラー」という意図をひと目で読み取れます。次に、このシステムの注文状態（未確定→確定→発送済→完了、およびキャンセル）を管理する仕組みを設計する場面を考えます。状態と、注文確定イベント・発送イベント・キャンセルイベントによる遷移規則をあらかじめ列挙しておけば、これはそのまま有限オートマトンとしてモデル化でき、「キャンセル済みの注文に対して発送イベントを受け付けない」といった不正な遷移を機械的に検出できます。さらに、注文番号の入力欄で「英字2文字＋数字6桁」という形式を検証したい場合は、正規表現 ^[A-Z]{2}[0-9]{6}$ のようなパターンで表現でき、この正規表現自体も内部的には有限オートマトンとして実装されています。このように、論理演算・ド・モルガンの法則・オートマトン・正規表現は、いずれも「入力や条件を正しく判定する」という一貫した目的でつながっています。
| 道具 | 得意な対象 | 代表的な用途 |
|---|---|---|
| BNF | 階層的な構文構造 | 言語文法の厳密な定義 |
| 正規表現 | 文字列の単純なパターン | 入力検証・文字列検索 |
| 有限オートマトン | 状態遷移で表せる振る舞い | 状態管理・正規表現の内部実装 |
ひっかけ： 「NOT (A OR B) は (NOT A) OR (NOT B) と等しい」は誤りです。ド・モルガンの法則では NOT (A OR B) = (NOT A) AND (NOT B)——ORの否定はANDに変わる点を取り違えないこと。また「有限オートマトンは無限個の状態を扱える」も誤り＝状態数は必ず有限であることが定義の中核です。
1.2.5この節のまとめ
- ド・モルガンの法則＝
NOT(A AND B)=(NOT A)OR(NOT B)、NOT(A OR B)=(NOT A)AND(NOT B)（否定でAND/ORが入れ替わる） - BNF＝構文の再帰的定義、正規表現＝文字列パターンの記述、両者とも構文/入力の妥当性判定に使う
- 有限オートマトン＝有限個の状態＋遷移規則で振る舞いをモデル化。状態管理や正規表現の内部実装に使われる
進捗の記録にはログインが必要です。
理解度チェック
（軽い確認用）Q1. 条件式 `NOT (在庫あり AND 決済成功)` をド・モルガンの法則で書き換えた場合、論理的に等価なものはどれか。
Q2. 注文番号の形式（英大文字2文字＋数字6桁）を検証するために最も適した道具はどれか。
Q3. 注文の状態（未確定→確定→発送済→完了、キャンセル）と、イベントによる遷移規則をあらかじめ列挙してモデル化したい。最も適した考え方はどれか。