論理演算
論理記号
論理和(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 |
---|---|---|---|---|---|---|
A∩B=A∪B 積の否定は、それぞれの否定の和
A∪B=A∩B 和の否定は、それぞれの否定の積
論理式の基本公理
交換法則: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 イ:A・B+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