HOME > 情報理論1 情報理論2

論理演算

論理記号

論理和(OR演算)
論理和AまたはBのどちらか一方が真(1)の時に真(1)を出力する演算
記号は”+”や”∨”で表します。



論理積(AND演算)
論理積AとBの両方真(1)であった時に真(1)を出力する演算
記号は”・”や”∧”で表します。

 

否定(NOT演算)
否定真(1)ならば偽(0)、偽(0)ならば真(1)を出力する演算
記号は” ̄”や”¬”で表します。




排他的論理和(EXOR演算)
排他的論理和AとBが一致しない時に真(1)、一致した時に偽(0)を出力する演算



否定論理積(NAND演算)
否定論理積AとBが両方真(1)の時に偽(0)を出力する演算

 


否定論理和(NOR演算)
否定論理和AかBが真(1)の時に偽(0)を出力する演算

 

 

含意
含意AならばB(A→B)を表す演算
記号は”⊃”で表します。

(*解りにくければ、A≦B と覚えればOK!)

A B 論理積
A and B
論理和
A or B
排他的論理和
A exor B
否定論理積
A nand B
否定論理和
A nor B
0 0 0 0 0 1 1
0 1 0 1 1 1 0
1 0 0 1 1 1 0
1 1 1 1 0 0 0

A∩B=AB 積の否定は、それぞれの否定の和
A∪B=AB 和の否定は、それぞれの否定の積

論理式の基本公理

交換法則:A∧B=B∧A
     A∨B=B∨A
結合法則:A∧(B∧C)=(A∧B)∧C
     A∨(B∨C)=(A∨B)∨C
分配法則:A∧(B∨C)=(A∧B)∨(B∧C)
     A∨(B∧C)=(A∨B)∧(B∨C)
吸収法則:A∧(A∨B)=A
     A∨(A∧B)=A
     A∧((¬A)∨B)=A∧B
     A∨((¬A)∧B)=A∨B
矛盾法則:P∧(¬P)=0
     P∨(¬P)=1
二重否定:¬(¬P)=P
ド・モルガン:¬(A∧B)=(¬A)∨(¬B)
       ¬(A∨B)=(¬A)∧(¬B)

問題

論理式(A+B)・(A+B)と等価な式はどれか?

ア:A・B+A・B イ:AB+A・B ウ:A+B エ:A+B

答えを表示

問題

XとYの否定論理積X NAND Yは、NOT(X AND Y)と定義される。X OR YをNANDだけを使って表した論理式はどれか?

ア:((X NAND Y) NAND X) NAND Y イ:(X NAND X) NAND (Y NAND Y)
ウ:(X NAND Y) NAND (X NAND Y) エ:X NAND (Y NAND (X NAND Y))

答えを表示




ページの先頭へ

加算器

半加算器
1桁目の2進数を加算する回路。
Cを求める計算は、AND演算、Yを求める計算は、EXOR演算の組合せによって実現されます。

半加算器

全加算器
下位桁を考慮した1桁の2進数の加算を行う回路。
2つの半加算器とOR回路の組合せによって実現されます。

全加算器

シフト演算

ビットを右・または左にずらす演算もよく行われます。これをシフト演算といいます。左にずらす演算を左シフト演算、右にずらす演算を右シフト演算といいます。シフト演算には、論理シフトと算術シフトがあります。
論理シフトは、単純にビットを右または左にずらす演算のことをいいます。空いた位置には0が入ります。
算術シフトは、右シフトする場合に、シフト前の符号が保たれるようにします。つまり、正負の符号を考慮した演算のことをいいます。左シフトの時は空いた位置には0が入り、右シフトの時は、空いた位置に符号ビットが入ります。

問題

数値を2進数で表すレジスタがある。このレジスタに格納されている正の整数xを10倍する方法はどれか。ここで、シフトによるあふれ(オーバーフロー)は起こらないものとする。

ア:xを2ビット左にシフトした値にxを加算し、さらに1ビット左にシフトする。
イ:xを2ビット左にシフトした値にxを加算し、さらに2ビット左にシフトする。
ウ:xを3ビット左にシフトした値と、xを2ビット左にシフトした値を加算する。
エ:xを3ビット左にシフトした値にxを加算し、さらに1ビット左にシフトする。

答えを表示




ページの先頭へ

形式言語

正規表現
正規表現とは、パターンを表現する規則を示したものです。 例えば、 [A-Z]+[0-9]*は、A~Zの英字1文字を表し、0~9の数字0文字以上を表します。
[A-Z]:英字1文字
[0-9]:数字1文字
*:直前の正規表現の0回以上の繰り返し
+:直前の正規表現の1回以上の繰り返しをあらわす

BNF記法(バッカス・ナウア記法)
BNF記法では、<数字>::=0|1|2|3|4|5|6|7|8|9という形で生成規則を表します。複数の置き換えが可能な方法がある場合は、|で表します。

逆ポーランド記法(後置法)
演算子を演算の対象である演算数(オペランド)の右側(後)に記述します。通常の記法は中記法といいます。
X=(A+B)×(C-D)を逆ポーランド記法で表すと、XAB+CD-×=となります。

問題

次のBNFで定義される<DNA>に合致するものはどれか。
<DNA>::=<コドン>|<DNA><コドン>
<コドン>::=<塩基><塩基><塩基>
<塩基> ::=A|T|G|C

ア:AC イ:ACGCG ウ:AGC エ:ATGC

答えを表示




ページの先頭へ
inserted by FC2 system