logical.md

論理演算と関数

コンピュータ計算のベースになっているのは論理演算，基本的な論理演算と関数型のプログラミングの考え方を知る。

演算の種類

1 入力(単項演算)

入力がなんであれ，常に False を出力する(恒偽)

(lambda P : False)
(lambda P : P and False)
(lambda P : P and not P)

入力がなんであれ，常に True を出力する(恒真)

(lambda P: True)
(lambda P : P or True)
(lambda P : P or not P)

入力がなんであれ，入力と同じ値をそのまま出力する(identity)

(lambda P: P)

入力が False であれば True を，入力が True であれば False を出力する(否定)

(lambda P: not P)
(lambda P: P ^ True)

2 入力(2 項演算)

論理和（OR 演算）は、入力された P, Q のうちいずれかが True なら答えも True となる論理演算

(lambda P, Q: P or Q)

論理積(AND 演算)は，入力された P，Q の両方が True なら答えも True となる論理演算

(lambda P, Q: P  and Q)

否定論理和(NOR 演算)は、入力された P，Q のうちいずれかが True なら答えが False となる論理演算

(lambda P, Q: not (P or Q))
(lambda P, Q: not P and not Q)

否定論理積(NAND 演算)は、入力された P，Q のうち両方が True なら答えが False となる論理演算

(lambda P, Q: not (P and Q))
(lambda P, Q: not P or not Q)

排他的論理和(XOR 演算)は、入力された P，Q が異なる場合に答えが True となり、同じ時に False となる論理演算

(lambda P, Q : P ^ Q)
(lambda P, Q : (not P and Q) or (P and not Q))

参考

_not = lambda p: not p
_and = lambda p, q: p and q
_or  = lambda p, q: p or q
_xor = lambda p, q: not(p and q) and (p or q)
comparator = lambda fn: lambda list: fn(*list)
bit = [True, False]
twobit = [[False, False], [False, True], [True, False], [True, True]]
print('not', list(map(_not, bit)))
print('and', list(map(comparator(_and), twobit)))
print('or' , list(map(comparator(_or), twobit)))
print('xor', list(map(comparator(_xor), twobit)))

加算回路

論理演算をつかうと足し算を行うことができる，足し算ができれば掛け算やべき乗算が可能になる

半加算回路

半加算回路（ハーフアダー）とは、2 進数の加算（足し算）を行う論理回路（加算器）の一種で、下位桁からの繰り上がりを考慮しない回路 足された結果を Sum 繰り上がりを Carry と呼ぶ

half adder sum

0 + 0 => 0
0 + 1  => 1
1 + 0  => 1
1 + 1   => 1

half adder carry

0 + 0 => 0
0 + 1  => 0
1 + 0  => 0
1 + 1   => 1

Python Program

_not = lambda p:  ~p  & 1
_or = lambda p, q: p | q
_and = lambda p, q: p & q
_xor = lambda p, q: p ^ q
_nor =lambda p, q: _not(_or(p, q))
_nand =lambda p, q: _not(_and(p, q))

# Carry と Sumを返す関数を作ってみよ
half_adder = lambda p, q: []

half adder

全加算回路

full adder sum

0 + 0 + 0 => 0
0 + 0 + 1 => 1
0 + 1 + 0 => 1
0 + 1 + 1 => 0
1 + 0 + 0 => 1
1 + 0 + 1 => 0
1 + 1 + 0 => 0
1 + 1 + 1 => 1

full adder carry

0 + 0 + 0 => 0
0 + 0 + 1 => 0
0 + 1 + 0 => 0
0 + 1 + 1 => 1
1 + 0 + 0 => 0
1 + 0 + 1 => 1
1 + 1 + 0 => 0
1 + 1 + 1 => 1

_not  = lambda p:  ~p  & 1
_or   = lambda p, q: p | q
_and  = lambda p, q: p & q
_xor  = lambda p, q: p ^ q
_nor  = lambda p, q: _not(_or(p, q))
_nand = lambda p, q: _not(_and(p, q))

# Carry と Sumを返す関数を作ってみよ
half_adder = lambda p, q:[]

# Carry と Sumを返す関数を作ってみよ
full_adder = lambda p, q, co: []

[full adder](https://eng.kice.tokyo/logic/adder/

抽象関数で実装してみる

 # 抽象関数のみで実装  
T = lambda t: lambda f: t
F = lambda t: lambda f: f
N = lambda p: p(F)(T)

OR  = lambda p: lambda q: p()()
AND = lambda p: lambda q: p()()
NOR = lambda p: lambda q: p()()
NAND= lambda p: lambda q: p()()
XOR = lambda p: lambda q: p()()

OR

# p => F
# - q => F => F => F()(F)
#  - q => T => T => F()(T)
# p => T
#  - q => F => T => T(T)()
#  - q => T => T => T(T)()

OR = lambda p: lambda q: p(T)(q)

AND

# p => F
#  q => F =>  F => F()(F)
#  q => T => F => F()(F)
# p => T
#  q => F => F => T(F)()
#  q => T => T => T(T)()

AND = lambda p: lambda  q: p(q)(F)

NOR