カテゴリ:3.コンピュータの基礎理論 > 3.4 集合と論理演算

こちらも参考にしてください。
http://sm.seeeko.com/archives/15876986.html

小学校ではこんな問題があったと思います。
30人の生徒がいます。野球を好きな人が15人、サッカーが好きな人が10人、両方好きな人が4人いました。では、両方嫌いな人は何人でしょう。  
これをベン図で表すと、以下のようになります。
1
応用情報技術者試験を勉強する成子 

なぜベン図というのですか?
イギリスのベン(Venn)さんが考案したからです。レントゲンを発明したのがレントゲンさんであるのと同様です。
さて、論理和(OR)、論理積(AND)、排他的論理和(XOR)を覚えましょう。

これ以外には、否定も覚えておきましょう。ベン図では、補集合と言います。

論理和(OR)
上でいう、野球とサッカーのどちらかが好きな人です。
合計20人です
情報処理技術者試験では、A∪B、A∨B、A+B、などの表現が使われます。「AまたはB」と読みましょう。
ベン図と真理値表は、以下です。
ベン図 真理値表
OR2 OR

論理積(AND)
上でいう、野球とサッカーの両方が好きな人です。
4人います。
ベン図真理値表
AND2AND  

情報処理技術者試験では、A∩B、A∧B、A・B、などの表現が使われます。「AかつB」と読みましょう。
応用情報技術者試験を勉強する成子 

子供の頃に、AかつBだから、「つ」と「∩」を関連して覚えるといいと言われました。
試験では、問題文に表記の解説がなされますが、覚えておくのはいいと思います。

否定(NOT)
「じゃない」という意味です。
ベン図真理値表
後日記載NOT  

排他的論理和(XOR)
上でいう、どちらか一方だけが好きな人です。
16人います。
ベン図真理値表
haita2haita  

否定的論理積(NAND)
ANDの反対
以下も参照ください。
http://sm.seeeko.com/archives/15876986.html

では、ベン図に関して、過去問(H25年秋FE午前問1)を見てみましょう。
ベン図

正解はウです。
面倒ですが、一つ一つ丁寧に書いていくのが近道です。

論理演算において、いくつかの公式があります。それは、結合法則や分配法則、ド・モルガンの法則です。
応用情報技術者試験を勉強する成子 

結合法則と分配法則は、中学校の数学か何かで習った記憶があります。

はい、それとほぼ同じです。
実際に見てみましょう。

 

1.結合法則

これは、過去問(H29年春AP午前問1)でズバリ問われています。
(A∪B)∪C=A∪(B∪C)
(A∩B)∩C=A∩(B∩C)

これは、数学における足し算や掛け算の以下の公式が成り立つのと同じです。
(A+B)+C=A+(B+C)
(A×B)×C=A×(B×C)

2.分配法則

A∩(B∪C)=(A∩B)∪(A∩C)
A∪(B∩C)=(A∪B)∩(A∪C)

こちらも1つめは数学と同様です。
A×(B+C)=(A×B)+(A×C)

2つ目は、数学の公式とは違いますね。以下の式は成り立ちません。
A+(B×C)=(A×B)+(A∪C)

3.ド・モルガンの法則

aaa









分かりにくいですね。
ベン図を描いてみると、たしかに一致します。
aaaa
言葉で考えてみましょう。小学生にて、Aが野球が好き、Bがサッカーが好きと仮定します。
上の公式で考えます。
左辺:野球とサッカーの両方が好きではない人
右辺:野球が嫌い、または、サッカーが嫌いのどちらかの人
言葉で表現するとわかりにくいのですが、左辺も右辺も同じ人が対象になります。(以下の○の人が対象)
ben2

 

4.論理演算の公式の過去問を解いてみよう

(1)平成29年春期 午前問1

ben






順番にベン図を描くのが近道かも知れませんね。
すべて成立します。
【正解】エ

(2)H25春AP午前問2

問2
1-3H25h-2





【正解】ア

(3)H28春AP午前問1

問1 nビットの値L1,L2がある。次の操作によって得られる値L3は,L1とL2に対するどの論理演算の結果と同じか。
〔操作〕
(1)L1とL2のビットごとの論理和をとって,変数Xに記憶する。
(2)L1とL2のビットごとの論理積をとって更に否定をとり,変数Yに記憶する。
(3)XとYのビットごとの論理積をとって,結果をL3とする。
ア 排他的論理和   イ 排他的論理和の否定
ウ 論理積の否定   エ 論理和の否定






【正解】ア

(4)H27秋AP午前問1

問1 0以上255以下の整数nに対して,
1-3H27a-1
と定義する。 next (n)と等しい式はどれか。ここで,x AND y 及び x OR yは,それぞれxとyを2進数表現にして,桁ごとの論理積及び論理和をとったものとする。
ア (n +1)AND 255   イ (n +1)OR 256
ウ (n +1)OR 255    エ (n +1)AND 256






【正解】ア

(5)H27秋AP午前問2

問2 集合A,B,Cに対してA∪B∪Cでが空集合であるとき,包含関係として適切なものはどれか。ここで,∪は和集合を,∩は積集合を,XはXの補集合を,また, X⊆YはXがYの部分集合であることを表す。
ア (A∩B)⊆C   イ A∩B)⊆C   
ウ ((span style="text-decoration: overline;">A∩B)⊆C   エ ((span style="text-decoration: overline;">A∩B)⊆C






【正解】エ

(6)H26秋AP午前問2

問2 4nビットを用いて整数を表現するとき,符号なし固定小数点表示法で表現できる最大値をaとし, BCD (2進化10進符号)で表現できる最大値をbとする。nが大きくなるとa/bはどれに近づくか。
ア (15/9)×n
イ (15/9)n
ウ (16/10)×n
エ (16/10)n






【正解】エ

(7)H25秋AP午前問4

問4 論理式P,Qがいずれも真であるとき,論理式Rの真偽にかかわらず真になる式はどれか。ここで,“ ̄”は否定,“V”は論理和,“∧”は論理積,“→”は含意(“真→偽”となるときに限り偽となる演算)を表す。
1-3H25a-4






【正解】エ

(8)H28秋AP午前問1

問1 8ビットのデータX及びyの値をそれぞれ16進表現で0F,F0とするとき,  8ビットのデータAの下位4ビットを反転させ,上位4ビットを0にする論理式はどれか。
1






【正解】ウ
まず、XとYが2進数でどんな値なのでしょうか。慣れている人は、0FとF0を見て、00001111、11110000とすぐに分かったことでしょう。

念のため、一つずつ変換してみます。
X:0F(16進数)⇒15(10進数)⇒00001111(2進数(8ビット))
Y:F0(16進数)⇒240(10進数)⇒11110000(2進数)
たとえばAを11010111とすると、「8ビットのデータAの下位4ビットを反転させ,上位4ビットをOにする」と、
00001000 になります。
選択肢のなかでどれが正しいのかは、実際にやってみましょう。
たとえば、アです。わかりやすいように表にしましたが、このような図を書かなくても、A・Xを求めて、その否定を求めることはそう難しくないと思います。
2 
ウは以下のようになります。よって、正解選択肢です。
3

過去問にカルノー図の例がありますが、ちょっとだけ複雑です。

カルノー図
【正解】エ

↑このページのトップヘ