論理方程式系。 ロジック。 ロジック機能。 方程式を解く

サービスの目的。 オンライン計算機は以下のために設計されています 論理式の真理値表を構築する.
真理値表 – 入力変数とそれに対応する出力値の可能なすべての組み合わせを含む表。
真理値表には 2n 行が含まれます。n は入力変数の数、n+m は列、m は出力変数です。

説明書。 キーボードから入力する場合は、次の規則に従ってください。

ブール式:

真理値表の中間表の導出
SKNFの構築
SDNFの構築
Zhegalkin 多項式の構築
Veitch-Karnaugh マップの構築
ブール関数の最小化

たとえば、論理式 abc+ab~c+a~bc は次のように入力する必要があります: a*b*c+a*b=c+a=b*c
論理図の形式でデータを入力するには、このサービスを使用します。

論理関数の入力規則

1. v (論理和、OR) 記号の代わりに、+ 記号を使用します。
2. 論理関数の前に関数指定を指定する必要はありません。 たとえば、 F(x,y)=(x|y)=(x^y) の代わりに、単に (x|y)=(x^y) と入力する必要があります。
3. 上限額変数は 10 に等しい。

コンピュータ論理回路の設計と解析は、数学の特別な分野である論理代数を使用して実行されます。 論理代数では、「NOT」(否定)、「AND」(論理積)、「OR」(論理和)という 3 つの主要な論理関数を区別できます。
論理デバイスを作成するには、既存の入力変数に対する各出力変数の依存関係を決定する必要があります。この依存関係は、スイッチング関数または論理代数関数と呼ばれます。
論理代数関数は、その値の 2n 個がすべて与えられた場合、完全に定義されていると呼ばれます。ここで、n は出力変数の数です。
すべての値が定義されていない場合、関数は部分的に定義されていると呼ばれます。
デバイスの状態が論理代数関数を使用して記述される場合、デバイスは論理的と呼ばれます。
論理代数関数を表すには、次の方法が使用されます。
代数形式では、論理要素を使用して論理デバイスの回路を構築できます。


図 1 - ロジックデバイスの図

論理代数のすべての演算が定義されている 真理値表価値観。 真理値表は、次の演算の結果を決定します。 誰でも可能です元のステートメントの x 個の論理値。 適用した操作の結果を反映するオプションの数は、論理式内のステートメントの数によって異なります。 論理式内のステートメントの数が N の場合、可能な引数値には 2 N 通りの異なる組み合わせがあるため、真理値表には 2 N 行が含まれます。

演算 NOT - 論理否定 (反転)

論理演算は、単純な論理式または複雑な論理式である単一の引数には適用されません。 操作の結果は次のとおりではありません。

• 元の式が true の場合、その否定の結果は false になります。
• 元の式が false の場合、その否定の結果は true になります。

次の規則は否定演算では受け入れられません。
A ではありません、Ā、A ではありません、œA、!A
否定演算の結果は、次の真理値表によって決まりません。

あ	Aではありません
0	1
1	0

否定演算の結果は、元のステートメントが false の場合は true となり、その逆の場合も同様です。

OR演算 - 論理和（論理和、和集合）

論理 OR 演算は、単純な論理式または複雑な論理式のいずれかである 2 つのステートメントを結合する機能を実行します。 論理演算の開始点となるステートメントは引数と呼ばれます。 OR 演算の結果は、元の式の少なくとも 1 つが true である場合にのみ true となる式です。
使用される名称: A または B、A V B、A または B、A||B。
OR 演算の結果は、次の真理値表によって決まります。
OR 演算の結果は、A が true、B が true、または A と B の両方が true の場合は true となり、引数 A と B が false の場合は false になります。

演算 AND - 論理積 (結合)

論理演算 AND は、単純な論理式または複雑な論理式のいずれかである 2 つのステートメント (引数) の共通部分の機能を実行します。 AND 演算の結果は、元の式が両方とも true の場合にのみ true となる式です。
使用される名称: A と B、A Λ B、A と B、A と B。
AND 演算の結果は、次の真理値表によって決まります。

あ	B	AとB
0	0	0
0	1	0
1	0	0
1	1	1

AND 演算の結果は、ステートメント A と B が両方とも true の場合にのみ true となり、それ以外の場合はすべて false になります。

操作「IF-THEN」 - 論理的結果 (含意)

この演算は 2 つの単純な論理式を接続します。最初の論理式は条件であり、2 番目の論理式はこの条件の結果です。
使用される名称:
A の場合は B。 A には B が伴います。 A の場合は B; A→B。
真理値表:

あ	B	A → B
0	0	1
0	1	1
1	0	0
1	1	1

含意操作の結果は、前提 A が真で、結論 B (結果) が偽の場合にのみ偽となります。

操作「B の場合にのみ A」（等価、等価）

使用される名称: A ↔ B、A ~ B。
真理値表:

あ	B	A↔B
0	0	1
0	1	0
1	0	0
1	1	1

演算「加算モジュロ 2」（XOR、排他的論理和、厳密論理和）

使用される表記: A XOR B、A ⊕ B。
真理値表:

あ	B	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

等価演算の結果は、A と B の両方が同時に true または false である場合にのみ true になります。

論理演算の優先順位

• 括弧内のアクション
• 反転
• 接続詞 (&)
• 論理和 (V)、排他的論理和 (XOR)、和法 2
• 含意 (→)
• 等価性 (↔)

完全選言正規形

式の完全選言正規形(SDNF) は、基本接続詞の論理和である同等の式であり、次の特性があります。

1. 式の各論理項には、関数 F(x 1,x 2,...x n) に含まれるすべての変数が含まれます。
2. 式の論理項はすべて異なります。
3. 変数とその否定を含む論理用語は 1 つもありません。
4. 数式内の論理項に同じ変数が 2 回含まれることはありません。

SDNF は、真理値表を使用するか、同等の変換を使用して取得できます。
関数ごとに、SDNF と SCNF は順列に至るまで一意に定義されます。

完全接続正規形

数式の完全結合正規形 (SCNF)これは、基本的な論理和の結合であり、次の特性を満たす、これと同等の式です。

1. すべての基本的な論理和には、関数 F(x 1 ,x 2 ,...x n) に含まれるすべての変数が含まれます。
2. 基本的な論理和はすべて異なります。
3. 各基本論理和には変数が 1 回含まれます。
4. 単一の基本論理和には、変数とその否定が含まれません。

コンピューター サイエンス試験のセクション A と B の問題を解く方法

レッスンその3。 ロジック。 ロジック機能。 方程式を解く

統一州試験の問題の多くは命題論理に特化しています。 それらのほとんどを解決するには、命題論理の基本法則、1 つまたは 2 つの変数の論理関数の真理値表の知識を知るだけで十分です。 命題論理の基本法則を説明します。

1. 論理和と論理積の可換性:
   a ˅ b ≡ b ˅ a
   a^b ≡ b^a
2. 選言と結合に関する分配法則:
   a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. 否定の否定:
   ￣(￣a) ≡ a
4. 一貫性：
   a ^ за ≡ false
5. 排他的な 3 番目:
   a ˅ за ≡ true
6. ド・モルガンの法則:
   Д(a ˅ b) ≡ 診a ˄ 診b
   Д(a ˄ b) ≡ 診a ˅ 診b
7. 簡略化:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ 真 ≡ a
   a ˄ false ≡ false
8. 吸収：
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. 含意の置き換え
   a → b ≡ åa ˅ b
10. アイデンティティの置き換え
    a ≡ b ≡(a ˄ b) ˅ (зa ˄ зb)

論理関数の表現

n 個の変数の論理関数 - F(x 1, x 2, ... x n) は、真理値表によって指定できます。 このようなテーブルには 2n 個の変数セットが含まれており、それぞれにこのセットの関数の値が指定されています。 この方法は、変数の数が比較的少ない場合に適しています。 すでに n > 5 の場合、表現はほとんど見えなくなります。

もう 1 つの方法は、既知の非常に単純な関数を使用して、何らかの式によって関数を定義することです。 関数 f i のみを含む式で論理関数を表現できる場合、関数系 (f 1、f 2、... f k) は完全であると呼ばれます。

関数系 ( 、 、 、 ) が完成しました。 法則 9 と 10 は、含意と同一性が否定、論理積、論理和によってどのように表現されるかを示す例です。

実際、否定と論理積、または否定と論理和という 2 つの関数のシステムも完成します。 ド・モルガンの法則からは、否定と論理積によって論理積を表現し、それに応じて否定と論理積によって論理積を表現できるというアイデアに従います。

(a ˅ b) ≡ з(зa ˄ зb)
(a ˄ b) ≡ з(зa ˅ зb)

逆説的に言えば、たった 1 つの機能からなるシステムが完成します。 パース アローとシェファー ストロークと呼ばれる逆結合と逆分離という 2 つの二項関数があり、中空システムを表します。

プログラミング言語の基本機能には通常、恒等、否定、論理積、論理和が含まれます。 統一国家試験の問題では、これらの機能に加えて、しばしば含意が見られます。

論理関数に関連するいくつかの簡単な問題を見てみましょう。

問題 15:

真理値表の断片が示されています。 指定された 3 つの関数のうち、このフラグメントに対応するのはどれですか?

×1	×2	×3	×4	F
1	1	0	0	1
0	1	1	1	1
1	0	0	1	0

1. (X 1 → X 2) ˄ з X 3 ˅ X 4
2. (￣ X 1 ˄ X 2) ˅ (￣ X 3 ˄ X 4)
3. ￣ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

機能番号3。

この問題を解決するには、基本的な関数の真理値表を知り、演算の優先順位を覚えておく必要があります。 論理積 (論理積) の方が優先度が高く、論理積 (論理和) よりも先に実行されることに注意してください。 計算中に、3 番目のセットの番号 1 と 2 を持つ関数の値が 1 であるため、フラグメントに対応していないことが容易にわかります。

問題 16:

指定された数値のうち、次の条件を満たすものはどれですか。

（桁は最上位桁から降順）→（数値－偶数）˄（下位桁－偶数）˄（上位桁－奇数）

このような数値が複数ある場合は、最大のものを示します。

1. 13579
2. 97531
3. 24678
4. 15386

条件は4番で満たされます。

最初の 2 つの数値は、最下位の桁が奇数であるため、条件を満たしていません。 条件の結合は、結合の項の 1 つが false の場合、false になります。 3 番目の数値については、最上位桁の条件が満たされていません。 4 番目の数値については、数値の下位桁と上位桁に課せられた条件が満たされます。 接続詞の最初の項も真です。なぜなら、その前提が偽である場合に含意が真であるためです。ここではこれが当てはまります。

問題 17: 2 人の証人は次の証言をしました。

第一証人: A が有罪であれば、B はさらに有罪であり、C は無罪です。

二人目の証人: 二人は有罪です。 そして、残りの1人は間違いなく有罪で有罪ですが、誰が正確に言うことはできません。

A、B、C の有罪について証言からどのような結論を導き出すことができますか?

回答: 証言から、A と B は有罪、C は無罪であることがわかります。

解決策: もちろん、答えは以下に基づいて与えることができます。 常識。 しかし、これを厳密かつ正式に行う方法を見てみましょう。

最初に行うことは、ステートメントを形式化することです。 3 つの論理変数 A、B、C を導入しましょう。対応する容疑者が有罪の場合、それぞれの値は true (1) になります。 次に、最初の証人の証言は次の式で与えられます。

A→(B˄C)

2 人目の証人の証言は次の式で与えられます。

A ˄ ((B ˄ зC) ˅ (зB ˄ C))

両方の証人の証言は真実であると仮定され、対応する式の結合を表します。

これらの測定値の真理値表を作成してみましょう。

あ	B	C	F1	F2	F1～F2
0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	1	1	1
1	1	1	0	0	0

要約証拠は 1 件のみで真実であり、A と B は有罪、C は無罪という明確な答えが得られます。

この表の分析から、2 人目の証人の証言がより有益であることもわかります。 彼の証言の真実から分かることは 2 つだけです。 可能なオプション- A と B は有罪、C は無罪、または A と C は有罪、B は無罪。 最初の証人の証言はあまり有益ではありません - 5 人です さまざまなオプション、彼の証言に一致します。 両方の証人の証言を総合すると、容疑者の有罪について明確な答えが得られます。

論理方程式と連立方程式

F(x 1, x 2, …x n) を n 個の変数の論理関数としましょう。 論理式は次のようになります。

F(x 1, x 2, …x n) = C,

定数 C の値は 1 または 0 です。

論理方程式には 0 ～ 2 n 個の異なる解が存在します。 C が 1 に等しい場合、解は、関数 F が値 true (1) をとる真理値表の変数のセットすべてになります。 残りのセットは、C がゼロに等しい方程式の解です。 常に次の形式の方程式のみを考慮できます。

F(x 1 , x 2 , …x n) = 1

実際に、次の方程式を与えてみましょう。

F(x 1, x 2, …x n) = 0

この場合、次の等価式に進むことができます。

δF(x 1 , x 2 , …x n) = 1

k 個の論理方程式からなる系を考えてみましょう。

F 1 (x 1、x 2、…x n) = 1

F 2 (x 1、x 2、…x n) = 1

F k (x 1 , x 2 , …x n) = 1

システムの解は、システムのすべての方程式が満たされる一連の変数です。 論理関数に関して言えば、論理方程式系の解を得るには、元の関数 F の結合を表す論理関数 Ф が真となる集合を見つける必要があります。

Ф = F 1 ˄ F 2 ˄ … F k

変数の数が少ない場合、たとえば 5 未満の場合、関数 Ф の真理値表を構築するのは難しくありません。これにより、システムに解がいくつあるか、解を提供する集合は何かを知ることができます。

論理方程式系の解を見つける一部の USE 問題では、変数の数が 10 に達します。その場合、真理値表を構築することはほぼ不可能な作業になります。 問題を解決するには、別のアプローチが必要です。 任意の連立方程式の場合、そのような問題を解決できる一般的な方法は列挙以外にありません。

試験で提示される問題では、通常、方程式系の詳細を考慮した解法が求められます。 繰り返しますが、変数セットのすべてのオプションを試す以外に、問題を解決する一般的な方法はありません。 ソリューションは、システムの詳細に基づいて構築する必要があります。 多くの場合、既知の論理法則を使用して方程式系の予備的な単純化を実行すると便利です。 この問題を解決するためのもう 1 つの有効な手法は次のとおりです。 すべての集合には興味がありませんが、関数 Ф の値が 1 である集合のみに興味があります。完全な真理値表を構築する代わりに、その類似物である二分決定木を構築します。 このツリーの各ブランチは 1 つの解に対応し、関数 Ф が値 1 を持つセットを指定します。デシジョン ツリーのブランチの数は、連立方程式の解の数と一致します。

二分決定木とは何か、そしてそれがどのように構築されるかを、いくつかの問題の例を使って説明します。

問題18

2 つの連立方程式を満たす、論理変数 x1、x2、x3、x4、x5、y1、y2、y3、y4、y5 の異なる値のセットはいくつありますか?

回答: このシステムには 36 の異なるソリューションがあります。

解決策: 連立方程式には 2 つの方程式が含まれています。 5 つの変数 (x 1、x 2、...x 5) に応じて、最初の方程式の解の数を見つけてみましょう。 最初の方程式は、5 つの方程式からなるシステムと考えることができます。 これまでに示したように、方程式系は実際には論理関数の結合を表します。 逆も同様です。条件の結合は方程式系と考えることができます。

含意 (x1→ x2) の決定木を構築しましょう。これは接続詞の最初の項であり、最初の方程式とみなすことができます。 このツリーをグラフィカルに表現すると次のようになります。

ツリーは番号に応じて 2 つのレベルで構成されます 方程式変数。 最初のレベルは、最初の変数 X 1 を記述します。 このレベルの 2 つの分岐は、この変数の可能な値、1 と 0 を反映します。2 番目のレベルでは、ツリーの分岐は、方程式が真である変数 X 2 の可能な値のみを反映します。 方程式は含意を指定しているため、X 1 が値 1 を持つ分岐は、その分岐上で X 2 が値 1 を持つ必要があります。X 1 が値 0 を持つ分岐は、X 2 の値を持つ 2 つの分岐を生成します。 0 と 1 に等しい 構築されたツリーは 3 つの解を定義し、その含意 X 1 → X 2 は値 1 をとります。各分岐で、対応する変数値のセットが書き出され、方程式の解が得られます。

これらのセットは次のとおりです: ((1, 1)、(0, 1)、(0, 0))

次の方程式、次の含意 X 2 → X 3 を追加して、決定木の構築を続けましょう。 私たちの方程式系の特徴は、系の新しい各方程式が前の方程式の 1 つの変数を使用し、新しい変数を 1 つ追加することです。 変数 X 2 はツリー内にすでに値を持っているため、変数 X 2 の値が 1 であるすべての分岐では、変数 X 3 の値も 1 になります。そのような分岐の場合、ツリーの構築は次のレベルに進みますが、新しい分岐は表示されません。 変数 X 2 が値 0 を持つ 1 つの分岐は、変数 X 3 が値 0 と 1 を受け取る 2 つの分岐に分岐します。 したがって、その詳細を考慮して、新しい方程式を追加するたびに、1 つの解が追加されます。 元の最初の方程式:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
には6つの解決策があります。 この方程式の完全な決定木は次のようになります。

私たちのシステムの 2 番目の方程式は最初のものと似ています。

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

唯一の違いは、方程式が Y 変数を使用していることです。この方程式にも 6 つの解があります。 変数 X i のすべての解は変数 Y j のすべての解と組み合わせることができるため、次のようになります。 総数解決策は 36 通りあります。

構築されたデシジョン ツリーでは、(分岐の数に応じた) 解決策の数だけでなく、ツリーの各分岐に書かれた解決策自体も提供されることに注意してください。

問題 19

以下の条件をすべて満たす、論理変数 x1、x2、x3、x4、x5、y1、y2、y3、y4、y5 の異なる値のセットはいくつ存在しますか?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
(x1→ y1) = 1

このタスクは前のタスクを変更したものです。 違いは、変数 X と Y を関連付ける別の方程式が追加されることです。

方程式 X 1 → Y 1 から、X 1 が値 1 を持つとき (そのような解が 1 つ存在します)、Y 1 も値 1 を持つことがわかります。 したがって、X 1 と Y 1 が次の値を持つ 1 つのセットが存在します。 1. X 1 が 0 に等しい場合、Y 1 は 0 と 1 の両方の任意の値を取ることができます。したがって、X 1 が 0 に等しい各セットは 5 つあり、Y 変数を持つ 6 つのセットすべてに対応します。したがって、解の総数は 31 です。

問題20

(￣X 1 ˅ X 2) ˄ (￣X 2 ˅ X 3) ˄ (￣X 3 ˅ X 4) ˄ (￣X 4 ˅ X 5) ˄ (￣X 5 ˅ X 1) = 1

解決策: 基本的な等価関係を思い出して、方程式を次のように書きます。

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1

循環的な影響の連鎖は、変数が同一であることを意味するため、方程式は次の方程式と等価です。

X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1

すべての X i が 1 または 0 の場合、この方程式には 2 つの解があります。

問題21

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1

解決策: 問題 20 と同様に、循環含意から恒等式に移行し、方程式を次の形式に書き換えます。

(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1

この方程式の決定木を構築しましょう。

問題22

次の方程式系には解がいくつありますか?

((×1 ≡×2)˄(×3 ≡X 4)) ˅( Д(×1 ≡X 2) ˄ з(×3 ≡X 4)) = 0

((×3 ≡× 4) ˄ (×5 ≡X 6)) ˅( Д(×3 ≡X 4) ˄ з(×5 ≡X 6)) = 0

((×5 ≡×6)˄(× 7 ≡X 8)) ˅( Д(×5 ≡X 6) ˄ з(× 7 ≡X 8)) = 0

((× 7 ≡×8)˄(×9 ≡X 10)) ˅(￣(× 7 ≡X 8) ˄ з(×9 ≡X 10)) = 0

答え: 64

解決策: 次の変数変更を導入して、10 個の変数から 5 個の変数に移行してみましょう。

Y 1 = (X 1 ≡ X 2); Y 2 = (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 = (X 7 ≡ X 8); Y 5 = (X 9 ≡ X 10);

最初の方程式は次の形式になります。

(Y 1 ˄ Y 2) ˅ (зY 1 ˄ зY 2) = 0

方程式は次のように書くことで簡略化できます。

(Y 1 ≡ Y 2) = 0

従来の形式に移り、次の形式で単純化した後にシステムを記述します。

ε(Y 1 ≡ Y 2) = 1

ε(Y 2 ≡ Y 3) = 1

ε(Y 3 ≡ Y 4) = 1

ε(Y 4 ≡ Y 5) = 1

このシステムのデシジョン ツリーはシンプルで、変数値が交互に切り替わる 2 つの分岐で構成されます。

元の X 変数に戻ると、Y 変数の各値に対して X 変数には 2 つの値があるため、Y 変数の各解は X 変数に 2 5 の解を生成します。2 つの分岐は 2 * 2 を生成します。解は 5 つあるため、解の総数は 64 になります。

ご覧のとおり、連立方程式を解く各問題には独自のアプローチが必要です。 一般的な手法は、等価な変換を実行して方程式を単純化することです。 一般的な手法は、決定ツリーを構築することです。 使用されるアプローチは、変数の可能な値のすべてのセットが構築されるわけではなく、関数が値 1 (true) を取るセットのみが構築されるという特徴を持つ真理値表の構築を部分的に思い出させます。 多くの場合、提案された問題では、完全な決定木を構築する必要はありません。これは、たとえば問題 18 で行われたように、初期段階で後続の各レベルでの新しい分岐の出現パターンを確立することが可能であるためです。 。

一般に、論理方程式系の解を見つける問題は、優れた数学の演習となります。

問題を手動で解決することが難しい場合は、方程式や連立方程式を解くための適切なプログラムを作成することで、コンピューターに解決を委ねることができます。

このようなプログラムを書くのは難しくありません。 このようなプログラムは、統一州試験で提供されるすべてのタスクに簡単に対処できます。

奇妙なことに、論理方程式系の解を見つける作業はコンピュータにとって困難であり、コンピュータには限界があることが判明しました。 コンピュータは、変数の数が 20 ～ 30 個の問題には非常に簡単に対処できますが、より大きなサイズの問題については長時間考えるようになります。 実際、セットの数を指定する関数 2 n は、n が増加するにつれて急速に増加する指数関数です。 あまりに速いので、通常のパソコンでは 1 日に 40 個の変数を含むタスクを処理できません。

論理方程式を解くためのC#言語プログラム

論理方程式を解くためのプログラムを作成することは、統一州試験のテスト問題に対する自分の解答の正しさを確認するために使用できるという理由だけでも、さまざまな理由で役立ちます。 もう 1 つの理由は、このようなプログラムが、統一州試験のカテゴリ C タスクの要件を満たすプログラミング タスクの優れた例であるためです。

プログラムを構築するという考え方は単純です。それは、考えられるすべての変数値のセットの完全な検索に基づいています。 与えられた論理方程式または方程式系では、変数の数 n がわかっているため、並べ替える必要があるセットの数 (2 n ) もわかります。 C# 言語の基本関数 (否定、論理和、結合、恒等) を使用すると、与えられた一連の変数に対して、論理方程式または方程式系に対応する論理関数の値を計算するプログラムを作成するのは難しくありません。 。

このようなプログラムでは、ループの本体内で、セットの数を使用してセットの数に基づいてループを構築し、セット自体を形成し、このセットの関数の値を計算し、これが値が 1 の場合、セットは方程式の解を与えます。

プログラムを実装するときに発生する唯一の困難は、セット番号に基づいて変数値のセット自体を生成するタスクに関連するものです。 この問題の利点は、この一見難しそうなタスクが、実際にはすでに何度も発生している単純な問題に帰着することです。 実際、数値 i に対応する 0 と 1 からなる変数値のセットが数値 i のバイナリ表現を表すことを理解すれば十分です。 それで 難しい仕事セット番号によって変数値のセットを取得することは、数値を 2 進法に変換するというよく知られた問題に帰着します。

私たちの問題を解決する C# の関数は次のようになります。

///

/// 解の数を数えるプログラム

/// 論理方程式 (方程式系)

///

///

/// 論理関数 - メソッド、

/// 署名は DF デリゲートによって指定されます

///

/// 変数の数

/// 解の数

static int SolveEquations(DF fun, int n)

bool セット = 新しい bool[n];

int m = (int)Math.Pow(2, n); //セット数

int p = 0、q = 0、k = 0;

//セット数による完全検索

for (int i = 0; i< m; i++)

//次のセットの形成 - セット、

//数値 i のバイナリ表現で指定

for (int j = 0; j< n; j++)

k = (int)Math.Pow(2, j);

//セット上の関数の値を計算します

プログラムを理解するには、プログラムの考え方の説明とテキスト内のコメントで十分だと思います。 ここでは、指定された関数のタイトルについてのみ説明します。 SolveEquations 関数には 2 つの入力パラメーターがあります。 fun パラメータは、解く方程式または連立方程式に対応する論理関数を指定します。 n パラメータは fun 変数の数を指定します。 その結果、SolveEquations 関数は論理関数の解の数、つまり関数が true と評価するセットの数を返します。

関数 F(x) の入力パラメータ x が算術、文字列、または論理型の変数であることは、学童にとってよくあることです。 私たちの場合は、さらに多くのものを使用します 力強いデザイン。 SolveEquations 関数は高次関数、つまり F(f) 型の関数を指します。そのパラメーターは単純な変数だけでなく関数も可能です。

SolveEquations 関数にパラメーターとして渡すことができる関数のクラスは、次のように指定されます。

デリゲート bool DF(bool vars);

このクラスは、vars 配列で指定された論理変数の値のセットをパラメーターとして渡すすべての関数を所有します。 結果は、このセットの関数の値を表すブール値です。

最後に、SolveEquations 関数を使用して複数の論理方程式系を解くプログラムを示します。 SolveEquations 関数は、以下の ProgramCommon クラスの一部です。

クラスプログラム共通

デリゲート bool DF(bool vars);

static void Main(文字列引数)

Console.WriteLine("および関数 - " +

SolveEquations(FunAnd, 2));

Console.WriteLine("この関数には 51 個のソリューションがあります - " +

SolveEquations(Fun51, 5));

Console.WriteLine("関数には 53 個のソリューションがあります - " +

SolveEquations(Fun53, 10));

静的 bool FunAnd(bool vars)

vars && vars; を返します。

静的 bool Fun51(bool vars)

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

静的 bool Fun53(bool vars)

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && (!((vars == vars) || (vars == vars)));

このプログラムのソリューション結果は次のようになります。

独立した仕事のための 10 のタスク

1. 3 つの関数のうち同等のものはどれですか。
   1. (X → Y) ˅ зY
   2. ʼ(X ˅ ʼY) ˄ (X → ʼY)
   3. �X ˄Y
2. 真理値表の一部を次に示します。

×1	×2	×3	×4	F
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

このフラグメントは 3 つの関数のうちどれに対応しますか?

1. (X 1 ˅ æX 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
4. 陪審員は3名で構成されます。 決定は、陪審員の少なくとも 1 人の支持を得て、陪審員長が賛成票を投じた場合に行われます。 それ以外の場合は、決定は行われません。 意思決定プロセスを形式化する論理関数を構築します。
5. 4 回のコイントスで 3 回表が出た場合、X は Y に勝ちます。 X の利得を記述する論理関数を定義します。
6. 文内の単語には 1 から始まる番号が付けられます。 次のルールが満たされる場合、文は正しく構成されているとみなされます。
   1. 偶数番号の単語が母音で終わる場合、次の単語が存在する場合、その単語は母音で始まらなければなりません。
   2. 奇数番号の単語が子音で終わる場合、次の単語が存在する場合は、子音で始まり母音で終わる必要があります。
      次の文のうち、正しく構成されているものはどれですか:
   3. お母さんはマーシャを石鹸で洗いました。
   4. リーダーは常に模範となるものです。
   5. 真実も良いですが、幸福はもっと良いです。
7. 方程式には解がいくつありますか:
   (a ˄ ʼ b) ˅ (ʼa ˄ b) → (c ˄ d) = 1
8. 方程式のすべての解をリストします。
   (a → b) → c = 0
9. 次の方程式系には解がいくつありますか。
   X 0 → X 1 ˄ X 1 → X 2 = 1
   X 2 → X 3 ˄ X 3 → X 4 = 1
   X 5 → X 6 ˄ X 6 → X 7 = 1
   X 7 → X 8 ˄ X 8 → X 9 = 1
   X 0 → X 5 = 1
10. 方程式には解がいくつありますか:
    ((((X 0 → X 1) → X 2) → X 3) →X 4) →X 5 = 1

問題への答え:

1. 関数 b と関数 c は同等です。
2. このフラグメントは関数 b に対応します。
3. 陪審員長が決定に「賛成」票を投じた場合、論理変数 P の値が 1 になるとします。 変数 M 1 および M 2 は、陪審員の意見を表します。 肯定的な決定を行うことを指定する論理関数は、次のように記述できます。
   P ˄ (M 1 ˅ M 2)
4. 論理変数 Pi が次の場合に値 1 を取るものとします。 i 番目のスローコインが表に出てきます。 ペイオフ X を指定する論理関数は次のように記述できます。
   ￣((￣P 1 ˄ (￣P 2 ˅ ￣P 3 ˅ ￣P 4)) ˅
   (￣P 2 ˄ (￣P 3 ˅ ￣P 4)) ˅
   (￣P3￣￣P4))
5. 文b.
6. 方程式には 3 つの解があります: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

この資料には、コンピューター サイエンスの統一州試験のタスク B15 (No. 23、2015) の論理方程式および論理方程式系を解く方法を示すプレゼンテーションが含まれています。 この課題は、統一国家試験の課題の中で最も難しいものの 1 つであることが知られています。 このプレゼンテーションは、専門クラスで「論理」というテーマの授業を行う場合や、統一国家試験の準備をする場合に役立ちます。

ダウンロード：

プレビュー:

プレゼンテーションのプレビューを使用するには、Google アカウントを作成してログインします: https://accounts.google.com

スライドのキャプション:

タスク B15 (論理方程式系) の解決法 MAOU ヴィシュネフスカヤ M.P. 「第 3 体育館」 2013 年 11 月 18 日、サラトフ

タスク B15 は、コンピューター サイエンスの統一国家試験の中で最も難しいものの 1 つです。 次のスキルがテストされます: 論理変数を含む式を変換する。 与えられた論理変数のセットが真となる論理変数の値のセットを自然言語で記述します。 与えられた条件を満たすバイナリ セットの数を数えます。 最も難しいのは、なぜなら... これを行う方法については正式な規則はなく、推測が必要です。

これなしではいられないもの！

これなしではいられないもの！

結合記号: A /\ B 、 A  B 、 AB 、 A &B、 A および B 論理和: A \ / B 、 A + B 、 A | B 、A または B の否定:  A 、A、not A の等価性: A  B、A  B、A  B 排他的「論理和」: A  B 、A xor B

変数置換方法 以下の条件をすべて満たす論理変数 x1, x2, ..., x9, x10 の値の組はいくつ存在します: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ ((x1 ≡ x2) \/ з(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (з(x3 ≡ x4) \/ з(x5) ≡ x6)) = 1 ((x5 ≡ x6 ) \/ (x7 ≡ x8)) /\ (з(x5 ≡ x7) \/ з(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (з(x7 ≡ x8) \/ з(x9 ≡ x10)) = 1 答えは、異なるセット x1、x2、…、x9、x10 をすべてリストする必要はありません。この平等体系は成り立ちます。 答えとして、そのようなセットの数を指定する必要があります (デモ バージョン 2012)

解決策のステップ 1. 変数を変更して簡略化します。 t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 簡略化後: (t1 \/ t2) /\ (зt1 \/ з t2) =1 (t2 \/ t3) /\ (зt2 \/ зt3) =1 (t3 \/ t4) /\ (зt3 \/ зt4) =1 (t4 \/ t5) /\ ( з t4 \/ ¬ t5) =1 次の方程式の 1 つを考えてみましょう: (t1 \/ t2) /\ (зt1 \/ ¬ t2) =1 明らかに、変数の 1 つが 0 で、もう 1 つが 1 の場合にのみ =1 になります。論理積と論理和による XOR 演算を式を使って表現しましょう: (t1 \/ t2) /\ (зt1 \/ ⁄ t2) = t1  t2 = з(t1 ≡ t2) =1 з(t1 ≡ t2) =1 ε( t2 ≡ t3) =1 ε(t3 ≡ t4) =1 ε(t4 ≡ t5) =1

ステップ2。 システム分析 δ(t1 ≡ t2) =1 δ(t2 ≡ t3) =1 δ(t3 ≡ t4) =1 δ(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1 Т 。に。 tk = x2k-1 ≡ x2k (t1 = x1  x2 ,….) の場合、tk の各値は値 x2k-1 と x2k の 2 つのペアに対応します。たとえば、 tk =0 は 2 つのペアに対応します - (0 ,1) と (1, 0) 、および tk =1 – (0,0) と (1,1) のペア。

ステップ3. 解の数を数えます。 各 t には 2 つの解があり、t の数は 5 です。 変数 t の場合、解は 2 5 = 32 通りあります。 しかし、各 t に対して、解 x のペアが対応します。つまり、 元のシステムには 2*32 = 64 の解があります。 答え: 64

解の一部を削除する方法 以下の条件をすべて満たす、論理変数 x1, x2, ..., x5, y1,y2,..., y5 の異なる値の集合はいくつ存在します: (x1→ x2 )∧(x2→ x3)∧(x3→ x4 )∧(x4→ x5) =1; (y1→y2)∧(y2→y3)∧(y3→y4)∧(y4→y5)=1; y5→x5=1。 答えは、この等式系が成立するさまざまな集合 x1、x2、...、x5、y 1 、y2、...、y5 をすべてリストする必要はありません。 答えはそのようなセットの数を示す必要があります。

解決。 ステップ1。 逐次解決策方程式 x1 1 0 x2 1 0 1 x3 1 0 1 1 x4 1 0 1 1 1 x5 1 0 1 1 1 1 最初の方程式は、1 に等しい複数の含意演算の積です。 それぞれの意味は真実です。 この含意は、1 ➞ 0 の場合のみ false であり、他のすべての場合 (0 ➞ 0、0 ➞ 1、1 ➞ 1) では、演算は 1 を返します。これを表形式で書いてみましょう。

ステップ1。 方程式の逐次解 T.o. x1、x2、x3、x4、x5 に対して 6 セットの解が得られました: (00000)、(00001)、(00011)、(00111)、(01111)、(11111)。 同様に推論すると、y1、y2、y3、y4、y5 についても同じ一連の解が存在するという結論に達します。 なぜなら これらの方程式は独立しています。つまり、 それらに共通の変数がない場合、この方程式系の解 (3 番目の方程式を考慮しない場合) は、6 * 6 = 36 組の「X」と「Y」になります。 3 番目の方程式を考えてみましょう: y5→ x5 =1 解はペアです: 0 0 0 1 1 1 このペアは解ではありません: 1 0

得られた解を比較してみますが、y5=1、x5=0の場合は不適切です。 このようなペアは 5 つあり、システムの解の数: 36-5= 31。 答え: 31 個の組み合わせ論が必要でした。

動的計画法 x 1, x 2, …, x 6 を論理変数としたとき、論理方程式 x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1 には何種類の解がありますか? 答えは、この等式が成り立つ変数値のさまざまなセットをすべてリストする必要はありません。 答えとして、そのようなセットの数量を示す必要があります。

解決策 ステップ1. 条件の分析 方程式の左側には含意の操作が順番に書かれており、優先順位は同じです。 書き直してみましょう: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 注意! 後続の各変数は、前の変数に依存するのではなく、前の含意の結果に依存します。

ステップ2。 パターンを明らかにする 最初の含意 X 1 → X 2 を考えてみましょう。 真理値表: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 1 つの 0 から 2 単位が得られ、1 からは 2 単位が得られます。 0 が 1 つと 1 が 1 つあります。0 は 1 つと 1 が 3 つだけあり、これは最初の演算の結果です。

ステップ2。 パターンを明らかにする x 3 を最初の演算の結果に接続すると、次のようになります: F(x 1 ,x 2) x 3 F(x 1 ,x 2)  x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 2 つの 0 – 2 つの 1、各 1 (3 つあります) から 1 つの 0 と 1 つの 1 (3+3)

ステップ 3. 式 T.o. の導出 i 個の変数を含む方程式のゼロの数 N i と 1 の数 E i を計算する式を作成できます。

ステップ 4. 表に記入する i = 6 として表を左から右に記入し、上記の式を使用して 0 と 1 の数を計算します。 この表は、次の列が前の列からどのように構築されるかを示しています。 変数の数 1 2 3 4 5 6 ゼロの数 N i 1 1 3 5 11 21 1 の数 E i 1 2*1+1= 3 2*1 +3= 5 11 21 43 答え: 43

論理式の簡略化を利用した方法 この方程式には何種類の解があるか ((J → K) → (M  N  L))  ((M  N  L) → (з J  K))  (M → J) = 1 ここで、J、K、L、M、N は論理変数ですか? 答えは、この等式が成り立つ J、K、L、M、N のさまざまな値のセットをすべてリストする必要はありません。 答えとしては、そのようなセットの数を示す必要があります。

解決策 J → K =  J  K であることに注意してください。変数の変化を導入しましょう: J → K=A, M  N  L =B 変化を考慮して方程式を書き直しましょう: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. 明らかに、A と B の同じ値に対して A  B 6. 最後の含意を考慮する M → J =1 これは次の場合に可能です: M= J=0 M=0、J=1 M=J=1

解決策 A  B の場合、M=J=0 のとき、1 + K=0 が得られます。 解決策はありません。 M=0、J=1 の場合、0 + K=0、K=0 が得られ、N と L は任意の 4 つの解になります: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 1

解 10. M=J=1 の場合、0+K=1 *N * L、または K=N*L、4 つの解が得られます。 11. 合計は 4+4=8 つの解になります 答え: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

情報源: O.B. ボゴモロバ、D.Yu. ウセンコフ。 B15: 新しいタスクと新しいソリューション // インフォマティクス、第 6 号、2012 年、p. 35 – 39. K.Yu. ポリアコフ。 論理方程式 // インフォマティクス、第 14 号、2011 年、p. 30～35。 http://ege-go.ru/zadania/grb/b15/、[電子リソース]。 http://kpolyakov.narod.ru/school/ege.htm、[電子リソース]。

を n 個の変数の論理関数としましょう。 論理式は次のようになります。

定数 C の値は 1 または 0 です。

論理方程式には 0 からさまざまな解が含まれます。 C が 1 に等しい場合、解は、関数 F が値 true (1) をとる真理値表の変数のセットすべてになります。 残りのセットは、C がゼロに等しい方程式の解です。 常に次の形式の方程式のみを考慮できます。

実際に、次の方程式を与えてみましょう。

この場合、次の等価式に進むことができます。

k 個の論理方程式からなる系を考えてみましょう。

システムの解は、システムのすべての方程式が満たされる一連の変数です。 論理関数に関して言えば、論理方程式系の解を得るには、元の関数の結合を表す論理関数 Ф が真となる集合を見つける必要があります。

変数の数が少ない場合 (たとえば、5 未満)、関数の真理値表を構築するのは難しくありません。これにより、システムに解がいくつあるか、解を提供するセットは何かを知ることができます。

論理方程式系の解を見つける一部の USE 問題では、変数の数が 10 に達します。その場合、真理値表を構築することはほぼ不可能な作業になります。 問題を解決するには、別のアプローチが必要です。 任意の連立方程式の場合、そのような問題を解決できる一般的な方法は列挙以外にありません。

試験で提示される問題では、通常、方程式系の詳細を考慮した解法が求められます。 繰り返しますが、変数セットのすべてのオプションを試す以外に、問題を解決する一般的な方法はありません。 ソリューションは、システムの詳細に基づいて構築する必要があります。 多くの場合、既知の論理法則を使用して方程式系の予備的な単純化を実行すると便利です。 この問題を解決するためのもう 1 つの有効な手法は次のとおりです。 すべての集合には興味がありませんが、関数の値が 1 である集合のみに興味があります。完全な真理値表を構築する代わりに、その類似物であるバイナリ決定木を構築します。 このツリーの各ブランチは 1 つの解に対応し、関数の値が 1 であるセットを指定します。デシジョン ツリーのブランチの数は、連立方程式の解の数と一致します。

二分決定木とは何か、そしてそれがどのように構築されるかを、いくつかの問題の例を使って説明します。

問題18

2 つの連立方程式を満たす、論理変数 x1、x2、x3、x4、x5、y1、y2、y3、y4、y5 の異なる値のセットはいくつありますか?

回答: このシステムには 36 の異なるソリューションがあります。

解決策: 連立方程式には 2 つの方程式が含まれています。 5 つの変数に応じて、最初の方程式の解の数を見つけてみましょう - 。 最初の方程式は、5 つの方程式からなるシステムと考えることができます。 これまでに示したように、方程式系は実際には論理関数の結合を表します。 逆のステートメントも真であり、条件の結合は方程式系と考えることができます。

implication () の決定木を構築してみましょう。これは接続詞の最初の項であり、最初の方程式とみなすことができます。 このツリーをグラフィカルに表現すると次のようになります。

ツリーは、方程式内の変数の数に応じて 2 つのレベルで構成されます。 最初のレベルでは、最初の変数が説明されます。 このレベルの 2 つの分岐は、この変数の可能な値 (1 と 0) を反映します。2 番目のレベルでは、ツリーの分岐は、方程式が true と評価される変数の可能な値のみを反映します。 方程式は含意を指定しているため、値 1 を持つ分岐は、この分岐の値が 1 である必要があります。値 0 を持つ分岐は、0 と 1 に等しい値を持つ 2 つの分岐を生成します。ツリーは 3 つの解を指定し、その含意は値 1 をとります。各分岐で、対応する変数値のセットが書き出され、方程式の解が得られます。

これらのセットは次のとおりです: ((1, 1)、(0, 1)、(0, 0))

次の方程式と次の含意を追加して、決定木の構築を続けましょう。 私たちの方程式系の特徴は、系の新しい各方程式が前の方程式の 1 つの変数を使用し、新しい変数を 1 つ追加することです。 変数はツリー内にすでに値を持っているため、変数の値が 1 であるすべての分岐では、変数の値も 1 になります。そのような分岐では、ツリーの構築は次のレベルに続きます。しかし、新しい枝は現れません。 変数の値が 0 である 1 つの分岐は、変数が 0 と 1 の値を受け取る 2 つの分岐に分岐します。したがって、新しい方程式を追加するたびに、その特異性を考慮すると、1 つの解が追加されます。 元の最初の方程式:

には6つの解決策があります。 この方程式の完全な決定木は次のようになります。

私たちのシステムの 2 番目の方程式は最初のものと似ています。

唯一の違いは、方程式が Y 変数を使用していることです。この方程式にも 6 つの解があります。 各変数解は各変数解と組み合わせることができるため、解の総数は 36 になります。

構築されたデシジョン ツリーでは、(分岐の数に応じた) 解決策の数だけでなく、ツリーの各分岐に書かれた解決策自体も提供されることに注意してください。

問題 19

以下の条件をすべて満たす、論理変数 x1、x2、x3、x4、x5、y1、y2、y3、y4、y5 の異なる値のセットはいくつ存在しますか?

このタスクは前のタスクを変更したものです。 違いは、変数 X と Y を関連付ける別の方程式が追加されることです。

方程式から、 の値が 1 (そのような解が 1 つ存在する) の場合、値は 1 になることがわかります。 したがって、値が 1 になるセットが 1 つあります。 0 に等しい場合は、次のことができます。は、0 と 1 の両方の任意の値を持ちます。したがって、 が 0 に等しい各セットは 5 つあり、変数 Y を持つ 6 つのセットすべてに対応します。したがって、解の総数は 31 です。

問題20

解決策: 基本的な等価関係を思い出して、方程式を次のように書きます。

循環的な影響の連鎖は、変数が同一であることを意味するため、方程式は次の方程式と等価です。

すべてが 1 または 0 の場合、この方程式には 2 つの解があります。

問題21

方程式には解がいくつありますか:

解決策: 問題 20 と同様に、循環含意から恒等式に移行し、方程式を次の形式に書き換えます。

この方程式の決定木を構築しましょう。

問題22

次の方程式系には解がいくつありますか?

レッスンのトピック: 論理方程式を解く

教育 – 論理方程式を解く方法を学び、論理方程式を解くスキルを開発し、真理値表を使用して論理式を構築する。

発達 - 生徒の認知的興味を発展させるための条件を作り、記憶力、注意力、注意力の発達を促進します。 論理的思考;

教育的 : 他人の意見を聞く能力を促進します。最終的な結果を達成するための意志と忍耐力を養います。

レッスンタイプ: 複合レッスン

装置： コンピュータ、マルチメディア プロジェクター、プレゼンテーション 6.

授業中

基礎知識の反復と更新。 検査 宿題（10分）

これまでのレッスンでは、論理代数の基本法則を理解し、これらの法則を使用して論理式を簡略化する方法を学びました。

論理式の簡略化に関する宿題を確認してみましょう。

1. 次の単語のうち、論理条件を満たすものはどれですか。

(1文字目子音→2文字目子音)٨ (最後の文字の母音→最後から2番目の文字の母音)? そのような単語が複数ある場合は、そのうちの最小のものを示します。

1) アンナ 2) マリア 3) オレグ 4) ステパン

次の表記法を導入しましょう。

A – 最初の文字の子音

B – 2 番目の文字の子音

S – 最後の文字の母音

D – 最後から 2 番目の母音文字

式を作ってみましょう:

表を作ってみましょう:

2. どの論理式がその式と同等であるかを示します

元の式と提案されたオプションの記録を単純化してみましょう。

3. 式 F の真理値表の一部が与えられると、次のようになります。

F に一致する式はどれですか?

指定された引数の値に対するこれらの式の値を決定してみましょう。

レッスンのトピックの紹介、新しい教材のプレゼンテーション (30分)

私たちは引き続き論理の基礎を勉強します。今日のレッスンのテーマは「論理方程式を解く」です。 このトピックを学習すると、論理方程式を解く基本的な方法を学び、論理代数の言語を使用してこれらの方程式を解くスキルと、真理値表を使用して論理式を構成する能力を獲得します。

1. 論理方程式を解く

(￣K M) → (￣L M N) =0

答えを 4 文字の文字列として書きます: 変数 K、L、M、N の値 (この順序)。 したがって、たとえば、行 1101 は、K=1、L=1、M=0、N=1 に対応します。

解決：

表現を変えてみましょう(￣K  M) → (￣L  M  N)

両方の項が false の場合、式は false になります。 M =0、N =0、L =1 の場合、第 2 項は 0 に等しくなります。 最初の項では、M = 0 であるため、K = 0、および
.

答え: 0100

2. 方程式には解がいくつありますか (答えには数字のみを示してください)。

解決策: 式を変換します。

(A +B )*(C +D )=1

A +B =1 および C +D =1

方法 2: 真理値表を作成する

3ウェイ: SDNF の構築 - 関数の完全な選言正規形 - 完全な規則的な基本接続詞の選言。

元の式を変換して、接続詞の論理和を取得するために括弧を開けてみましょう。

(A+B)*(C+D)=A*C+B*C+A*D+B*D=

接続詞を補足して接続詞 (すべての引数の積) を完成させましょう。括弧を開けてください。

同じ接続詞を考慮してみましょう。

その結果、9 個の接続詞を含む SDNF が得られます。 したがって、この関数の真理値表は、2 4 =16 セットの変数値の 9 行の値 1 を持ちます。

3. 方程式には解がいくつありますか (答えには数字のみを示してください)。

式を単純化してみましょう:

,

3ウェイ: SDNFの構築

同じ接続詞を考慮してみましょう。

その結果、5 つの接続詞を含む SDNF が得られます。 したがって、この関数の真理値表は、2 4 =16 セットの変数値の 5 行に値 1 を持ちます。

真理値表を使用して論理式を構築します。

1 を含む真理値表の各行に対して引数の積を構成します。0 に等しい変数は否定されて積に含まれ、1 に等しい変数は否定なしで含まれます。 目的の式 F は、結果として得られる積の合計で構成されます。 そして、可能であれば、この式を簡略化する必要があります。

例: 式の真理値表が与えられます。 論理式を構築します。

解決：

3. 宿題（5分）

方程式を解きます。

方程式には解がいくつありますか (答えには数字のみを示してください)。

与えられた真理値表を使用して論理式を構築し、

それを単純化します。