■
Linear Congruences
m: integer > 0, a and b: integers, x: variable
ax ≡ b (mod m)
となるような
をa mod mの逆元(inverse of a modulo m)という。
aとmがそれぞれ互いに素（最大公約数が１）の時、はただ１つ存在する。
例:
Find an inverse of 101 modulo 4620.
Use Euclidean algorithm to see if 101 and 4620 are prime (gcd for the numbers = 1).
By Euclidean algorithm, gcd(101, 4620) is
4620 = 45・101 + 75
101 = 1・75 + 26
75 = 2・26 + 23
26 = 1・23 + 3
23 = 7・3 + 2
3 = 1・2 + 1
2 = 2・1
Because the last nonzero remainder is 1, gcd(101, 4620) = 1.
Now find the Bezout coefficients for 101 and 4620 by working backwards.
The Bezout coefficients are -35 and 1601, and 1601 is an inverse of 101 modulo 4620.
What are the solutions of the linear congruence 3x ≡ 4 (mod 7)?
3と7はそれぞれ互いに素なので、gcd(3, 7) = 1.
3x ≡ 4 (mod 7)より、3x÷7=4になるxは、3・6÷7=4 ∴ x ＝ 6
x = 6 (mod 7), namely, 6, 13, 20, ... and -1, -8, -15, ...
中国剰余定理 The Chinese Remainder Theorem
例:
以下の連立方程式を解け。
x ≡ 2 mod 3
x ≡ 4 mod 5
解は０≦ x < 3(5)=15 の間にある。
3X + 5Y = 1を満たすX, Yをユークリッドの互除法で求める。
5 = 1・3 + 2
3 = 1・2 + 1
2 = 2・1
1 = 3 - 1(2)
= 3 - 1(5 - 1(3)) = -1(5) + 2(3)
∴ X = 2, Y = -1
= (2)(5)(-1) + (4)(3)(2) = 14
Use the method of back substitution to find all integers x such that x ≡ 1 (mod 5),
x ≡ 2 (mod 6), and x ≡ 3 (mod 7).
Use the theorem "let m be a positive integer. The integers a and b are congruent modulo m if and only if there is an integer k such that a = b + km."
By the theorem, the first congruence can be written as x = 1 + 5t, where t is an integer.
Substituting this expression for x into the second congruence, 1 + 5t ≡ 2 (mod 6).
∴ 5t ≡ 1 (mod 6)
5t (mod 6) ≡ 1 になるのは、5(5t) ≡ 5(1) (mod 6) (25 mod 6 = 1)
∴ t ≡ 5 (mod 6)
Using the theorem again, t = 5 + 6u, where u is an integer.
Substituting this expression for t back into the equation x = 1 + 5t.
x = 1 + 5t = 1 + 5(5 + 6u) = 26 + 30u.
Insert this equation into the third equation to obtain 26 + 30u ≡ 3 (mod 7).
∴ 30u ≡ -23 (mod 7) ≡ 5 (mod 7)
7 = 1(5) + 2
5 = 2(2) + 1
2 = 2(1)
gcd(5, 7) = 1, they are coprime.
1 = 5 - 2(2) = 5 - 2(7 - 1(5)) = -2(7) + 3(5)
3(30u) ≡ 3(5) (mod 7) ≡ 1 ∴ 90u ≡ 1 (mod 7)
6(90u) ≡ 6(1) (mod 7) ∴ u ≡ 6 (mod 7)
∴ u = 7v + 6, where v is an integer.
Substitutiong this expression into x = 26 + 30u = 210u +206.
∴ x ≡ 206 (mod 210)
フェルマーの小定理 Fermat's Little Theorem
例:
Find 
.
7 and 11 are coprime ⇨ 
So 
for every positive integer k.
DIvide the exponent 222 by 10, 222 = 22(10) + 2
擬素数 Pseudoprime
nを合成数、aを整数とする。合同式 
が成り立つとき、nは底aに関する擬素数(psedoprime)であるという。
例:
The integer 341 is a psedoprime to the base 2 because it is composite (341 = 11・31) and 
.
カーマイケル数 Carmichael Number
nを合成数とする。任意の整数aに対して、gcd(a, n) = 1ならば、合同式が成り立つ。この時のnをcarmichael数という。
例:
The integer 561 is a Carmichael number. To see this, first note that 561 is composite because 561 = 3(11)(17).
Next, note that if gcd(b, 561) = 1, then gcd(b, 3) = gcd(b, 11) = gcd(b, 17) = 1.
Using Fermat's little theorem we find that
擬素数かどうかはフェルマーの小定理を使って底ごとに定まるが、ある底で擬素数であっても別の底では擬素数であるとは限らないので複数の底でフェルマーの小定理を試して素数である確率を高める。
が、どんな底でも擬素数であると判定される数が存在する。これをカーマイケル数という。絶対擬素数(absolute psedoprimes)とも呼ばれる。
カーマイケル数は小さい方から561, 1105, 1729, 2465, 2821, ...で無限に存在する。
Primitive Roots and Discrete Logarithms
A primitive root modulo a prime p is an integer r in Zp such that every nonzero element of Zp is a power of r.
例:
Determine whether 2 and 3 are primitive roots modulo 11.
n進数とアルゴリズム Integer and Algorithms
１０進数…decimal (base 10)
２進数…binary (base 2)
８進数…octal (base 8)
１６進数…hexadecimal (base 16)
０から１５までの変換表
b: integer > 1, n: integer > 0, それぞれの進数は、次のようにして１０進数で表せる。
例：
The decimal expansion (base 10) of the integer that has 
as its binary expansion is
101011111は９桁あるので最初のkはk＝9-1＝8、そして徐々に減っていき0に近づく。
その10のk乗に、それぞれの桁の数字をかける。９桁目なら1、８桁目なら0。
The decimal expansion of the number with dexadecimal expansion 
is
2AE0Bは５桁なのでk＝4から始まる。
５桁目は2なので、2・10の４乗。
１６進数のそれぞれの桁は４ビットを表している（ビット…binary digitの略。１桁の２進数＝１ビット。４ビット＝４桁の２進数）。そして８ビットを１バイトといい、これが２桁の１６進数に相当する。
次に、１０進数からそれぞれの基数へ変換する場合。
１０進数の数字を基数で割っていく。そしてその余りを最後から順番に並べたものがその基数での数字になる。
例：
To find the octal expansion of 
、
Hence, 
To find the hexadecimal expansion of 
,
10進数以外での基数同士の変換。
例：
Find the octal and hexadecimal expansions of 
and the binary expansions of 
and 
.
８は２の３乗なので右から３桁ずつ。１６は２の４乗なので４桁ずつ取る。
表を使うと簡単。
2進数の加法。
右端から順に足していき、係数×基数＋余りの形に直していく。
余りを最後から順に組み合わせたものが加法の答えになる。
例：
Add a = 
, b = 
.
一番右端同士の足し算は、a0＋b0＝０＋１＝０・２＋１
上記よりc0＝０、s0＝１
次の位がa1＋b1＋c0＝１＋１＋０＝１・２＋０
上記よりc1=1, s1=0
次の位がa2+b2+c1＝１＋０＋１＝１・２＋０
c2=1, s2=0
a3+b3+c2＝１＋１＋１＝１・２＋１
c3=1, s3=1→s4=c3=1
∴ s = a + b = 
＝
2進数同士の掛け算。
2の累乗分だけ０を右側に付け足す。
例：
Find the product of 
.
Modular Exponentiation
2進数を使って大きな数の余りを求める事が出来る。
b: integer, 
, m: positive integers
x := 1
power := b mod m
for i := 0 to k-1
if ai = 1 then x := (x・power) mod m
power := (power・power) mod m
return x{x equals 
}
例:
Use that algorithm to find 
.
辞書 Dictionaries
リストを使えば、インデックスと要素の内容を覚えておけば要素を取り出せるものであった。
>>> list = [1, 2, 'python', 'yeah']
>>> list[0]
1
>>>
逆に言えば、インデックスと要素の内容を覚えていないと面倒だという事。
そこで、要素ごとに情報の性質や種類が異なっているデータは、インデックスで管理するより見出しで管理する方が便利なので、要素にラベルをつける方法がある。これをディクショナリ機能という。書き方は、{キー１: 値１, キー２: 値２, ...}といった具合。このキーがラベルにあたる。
>>> dictionary = {'name': 0, 'name1': 1, 'name2': 2}
>>> dictionary['name1']
1
>>> dictionary['name2']
2
>>>
要素の変更、追加、削除はリストとほぼ同じなので省略。
違うのはインデックスの部分がキーになる事くらい。
リストのようにこのようにしてディクショナリを作ることもできる。
>>> {x: x*x for x in range(3,6)}
{3: 9, 4: 16, 5: 25}
リストだとこうなる。基本的にラベルがあるかないかの違い。リストはキー（ラベル）の代わりにインデックス。
>>> [x*x for x in range(3,6)]
[9, 16, 25]
以下のようにすると、一番小さいキー（ラベル）を取り出す。
>>> min({-1: 6, 0: 5, 1: 4})
-1
まずキーをそれぞれ２乗し、最小値を取る。
>>> min({-1: 6, 0: 5, 1: 4}, key=lambda x: x*x)
0
ちなみにリストの時はこんな感じ。
まずkey=lambda x: x[1]でインデックス1番目の３、２、１を取り出す。
次にその３つの数値のうち最小値を取る（１）。
この最小値が含まれているリストは[2, 1]である。
>>> min([[0, 3], [1, 2], [2, 1]], key=lambda x: x[1])
[2, 1]
>>>
以上はキー（：の左側）を比較した場合。
次に、キーの値（：の右側）の比較をする場合。
get()を使うことで、ディクショナリのキーの値を渡すことができる。
具体的にコードに書くとこんな感じ。
def key_of_min_value(d):
"""Returns the key in a dict d that corresponds to the minimum value of d.
>>> letters = {'a': 6, 'b': 5, 'c': 4, 'd': 5}
>>> min(letters)
'a'
>>> key_of_min_value(letters)
'c'
"""
return min(d, key=d.get)
データ抽象 Data Abstraction
<データのタイプについて>
データの種類のことを型(type)という。
１、２、３…などの数値は数値型、'hello'などの文字は文字列型などのようにそれぞれ分類されている。
違う型同士での計算はPythonでは出来ない（JavaScript、PHPなど他の言語では可能）ので、型を揃えて操作する必要がある。
そのデータの型が何なのかを知るのに、type()が使える。
>>> type(3)
<class 'int'>
>>> type(sum)
<class 'builtin_function_or_method'>
>>> type(0.5)
<class 'float'>
>>>
数値型で気をつけておきたいのが、整数型(int)と浮動小数型(float)では微妙に異なる点がある。それは整数型は誤差なしの値であるのに対して、浮動小数型は曖昧な（誤差ありの）値になるということ。
>>> 1/3 == 0.33 # 誤差が大きいのでFalseになる
False
>>> 1/3 == 0.3333333333333333333333 # 誤差が小さいのでTrueになる
True
>>> 1/3
0.3333333333333333
>>>
<データ抽象>
データ抽象とは実装に依存せずにデータ構造を抽象的に定義すること。
データの具体的な表現を示さず、関数だけを示している。これを抽象データ型(Abstract Data Type, ADT)という。
例として、分数を表すプログラムを考える。
通常では分数表現を書いた場合、Pythonは先に計算をしてしまうので分数を表示することが出来ない。なので、これを表示するために３つの関数を考える。
- rational(n, d) 分子n、分母dの分数を返す.
- numer(x) 分数xの分子を返す.
- denom(x) 分数xの分母を返す.
これらの定義を用いて、分数の足し算、掛け算を定義すると、
>>> def add_rationals(x, y):
nx, dx = numer(x), denom(x)
ny, dy = numer(y), denom(y)
return rational(nx * dy + ny * dx, dx * dy)
>>> def mul_rationals(x, y):
return rational(numer(x) * numer(y), denom(x) * denom(y))
また、分数を表示する関数は、
>>> def print_rational(x):
print(numer(x), '/', denom(x))
と書くことができる。
ここで、リストを用いてrational, numer, denomを定義することができる。
def rational(n, d):
return [n, d]
def numer(x):
return x[0]
def denom(x):
return x[1]
これで分数を表示できるようになった。
>>> half = rational(1, 2)
>>> print_rational(half)
1 / 2
>>> third = rational(1, 3)
>>> print_rational(mul_rationals(half, third))
1 / 6
>>> print_rational(add_rationals(third, third))
6 / 9
しかし、6 / 9は本当は2 / 3と表示されるべきである。
そこで、Pythonにもともと組み込まれているgcd（greatest common denominator、分子と分母の最大公約数）をimportしてrational関数を少し変える必要がある。
>>> from fractions import gcd
>>> def rational(n, d):
g = gcd(n, d)
return (n//g, d//g) ＃ 分子と分母をそれぞれ最大公約数で割る
>>> print_rational(add_rationals(third, third)) 2 / 3
このデータ抽象の概念を使えば、関数の特徴をいじることなく色々な表現をすることができる。その状態を保つために、abstraction barrierという概念がある。
コードを書くとき、一般化されたコードを書くことで、他の関数の実装に関係なく求めたいものを求められるように定義する必要があるという事。
先ほどの分数の例でいうと、例えば分数の２乗を計算するプログラムを書くとする。
>>> def square_rational(x):
return mul_rational(x, x)
これなら分数がどのように実装されていても関係なく求めたい結果を求められる。
しかし、次の例はabstraction barrierに違反している。
>>> def square_rational_violating_once(x): return rational(numer(x) * numer(x), denom(x) * denom(x))
こうしてしまうと、もしnumerやdenomの実装方法が変わってしまった場合、分数の２乗を正しく計算できなくなる可能性がある。
次の例も同様で、
>>> def square_rational_violating_twice(x): return [x[0] * x[0], x[1] * x[1]]
他の関数の実装方法に依存した書き方のため、リストの中身が変わってしまったりすると正しく計算できなくなる。
Abstraction barrierとは、こういった他の実装方法に依存されない方法で関数を書きましょうといったルールのようなものである。
そこで、一般化されたプログラムを書くには、コンストラクタとセレクタを使って書く必要がある。
コンストラクタ、セレクタの説明の前に、オブジェクトとクラスについて。
オブジェクトとは、変数と関数が一緒になっているもの。
例：
x = 2 （変数）
def square(x):
return x * x （処理をする関数）
これらを一まとめにしたものがオブジェクト。
オブジェクトにまとめられている関数をメソッドと呼ぶ。
オブジェクトのメリットとして、変数をどの関数で処理するかが明確になるのでバグが出にくいこと、再利用や分類がしやすいことなどが挙げられる。
クラスとは、オブジェクトの設計図でのことで、オブジェクトがどのような性質を持っていて、どのような振る舞いをするのか、ということをコードに書いてクラスという形にまとめることで様々なオブジェクトを生み出すことができる。
今回の分数の例の場合、rationalがコンストラクタ、numer、denomがセレクタとなる。
詳しくはまた別の記事で。
ラムダ式 Lambda Expression
通常defを使った関数の定義はdefの直後に名前をつける必要がある。
しかし、lambdaを使えば名前をつける必要がなくなる。無名関数とも呼ばれる。
lambda式のメリットとして、関数を式(expression)として扱うため、変数に代入できるようになり、プログラムを簡潔にできる。
書式は、lambda 引数のリスト: 引数を使った式（戻り値）
例：
>>> def add(a, b):
return a + b
この関数をlambdaを使うと１行で表せる。
>>> add = lambda a, b: a + b
連続して使うこともできる。ただし、分かりづらいのでなるべく避けること。
あくまでlambdaを使うときはシンプルな表現として、引数として渡したいときか戻り値として渡したいときが多い。
>>> compose = lambda f: lambda g: lambda x: f(g(x)) # これは避けた方が良い
特にpythonではあまりlambdaは好まれないので、defをよく用いる。
また、lambda式ではstatementは使えないので、while文などは使えない。
また引数なしでも使える。
>>> say_hello = lambda: 'hello'
>>> say_hello
<function <lambda> at 0x10f803488>
>>> say_hello()
'hello'
>>>
練習問題
空欄を埋めよ。
x = lambda x, y: lambda x- y
result = (lambda ________, question: one(________)(x, 4)
# 以下解答
x = lambda x, y: lambda x- y
result = (lambda one, question: one(46, question)())(x, 4)
高階関数 Higher Order Functions
高階関数とは、別の関数を引数として渡して処理をしたり、戻り値として別の関数を返したりする関数のこと。
通常は引数や戻り値には数値などを入れたりして単純な結果を返していただけだったが、この概念を使うことでより複雑な処理もできるようになる。
そもそもなぜ関数を定義するか、それは関数を定義することで、値を渡すだけで一々手計算をしなくて済むからである。
このような考え方から、同じような事をする関数があったとき、それを一般化する関数を書くことができれば、詳細の機能を自由に変更できる。
例として、次の３つのプログラムを考える。
① ０からnまでの和を計算する関数
>>> def sum_naturals(n):
total, k = 0, 1
while k <= n:
total, k = total + k, k + 1
return total
>>> sum_naturals(100)
5050
② ０からnまでの２乗の和を計算する関数
>>> def sum_cubes(n):
total, k = 0, 1
while k <= n:
total, k = total + k*k*k, k + 1
return total
>>> sum_cubes(100)
25502500
③ nが増えるにつれて円周率πにだんだん収束していく数列の和を計算する関数
>>> def pi_sum(n):
total, k = 0, 1
while k <= n:
total, k = total + 8 / ((4*k-3) * (4*k-1)), k + 1
return total
>>> pi_sum(100)
3.1365926848388144
この３つの関数の作りはよく似ている。
違いは足していくものが整数なのか、整数を２乗したものなのか、そして分数なのかという事のみ。
この共通した部分だけを抜き出して一般化した関数を作る事で、別に整数を渡す関数、整数の２乗を渡す関数、そして分数を渡す関数を作ってそれを引数として渡す事で、一々関数を定義し直さなくても良くなる。
その共通部分を抜き出して一般化した関数がこちら。
def summation(n, term):
total, k = 0, 1
while k <= n:
total, k = total + <term>(k), k + 1
return total
変わった部分は引数にtermが増えてることと、totalに足されるものが<term>(k)となっている事。この<term>の部分に別の整数を渡す関数、整数の２乗を渡す関数、または分数を渡す関数を渡す事でそれぞれの和が計算できる。
整数を渡す関数
def identity(x):
return x
整数の２乗を渡す関数
def square(x):
return x * x
πに収束していく分数を渡す関数
def pi_term(x):
return 8 / ((4*x-3) * (4*x-1))
これで準備が整った。
１０までの自然数の和を求めたい場合、
>>> summation(10, identity)
55
または何の和なのか分かりやすくするため新たに定義しても良い。
>>> def sum_natural(n):
return summation(n, identity)
>>> sum_natural(10)
55
同様に、２乗の和は、
>>> def sum_square(n):
return summation(n, square)
>>> sum_square(10)
385
πに収束していく分数の和は、
>>> def sum_pi(n):
return summation(n, pi_term)
>>> sum_pi(10)
3.091623806667838
>>> sum_pi(100)
3.1365926848388144
これが基本的な高階関数の使い方の１つである。
別の例として、図形の面積を求める関数も高階関数にする事で簡単に求められる。
一辺の長さがrの正方形、正六角形、または半径の長さがrの円の面積の求め方は、
正方形＝r * r
正六角形＝(3√3)/2 * r * r
円＝π * r * r
この３つの共通点はrの２乗に係数をかけているという事。
なので、このrの２乗を共通点として一般化した関数を書き、新たに正方形の係数をかける関数、正六角形の係数をかける関数、そして円の係数をかける関数を書くことができる。
>>> from math import pi, sqrt # 正六角形で√、円でπが必要なため
>>>
>>> def area(r, shape_constant):
assert r > 0, 'A length must be positive'
return r * r * shape_constant
>>> def area_square(r):
return area(r, 1)
>>> def area_hexagon(r):
return area(r, 3*sqrt(3)/2)
>>> def area_circle(r):
return area(r, pi)
これで面積を計算する準備ができたので早速実行してみる。
>>> area_square(10)
100
>>> area_hexagon(10)
259.8076211353316
>>> area_circle(10)
314.1592653589793
>>>
ここまでが関数を引数として渡した場合の例。
次に、関数の中に別の関数を定義した場合と、返り値に関数を渡した場合。
この場合のメリットとしては、関数内で定義された関数は、親の変数を使える事。デメリット？としては、親の関数の変数を書き換えることは出来ないので、入れ子の関数の中で変数に代入すると、親の関数の変数は隠されてしまう。また、定義された関数の中でのみ有効で、他の関数から呼び出すことは出来ない。
例として、ある条件を満たしているnまでの整数をプリントアウトする関数を考える。
>>> def keep_ints(n):
"""Returns a function which takes one parameter cond and
prints out all integers 1..i..n where calling cond(i)
returns True.
>>> def is_even(x):
return x % 2 == 0
>>> keep_ints(5)(is_even)
2
4
"""
def do_keep(cond):
i = 1
while i <= n:
if cond(i):
print(i)
i += 1
return do_keep
テストケースの>>> keep_ints(5)(is_even)に注目。
先にkeep_ints(5)を実行して、関数が返り、その関数にis_evenを渡していることが分かる。なので、keep_intsのreturn値は関数である。
関数do_keep内では、condに渡された関数が条件を満たすかどうかを判定（今回の場合is_even、偶数かどうかを判定）して満たしているならプリントアウトする。
なぜdo_keepをkeep_ints中に定義する必要があるのか、それはもしこのdo_keepをkeep_intsの外側、要は全く別の関数として定義した場合、keep_intsに渡したnの値がdo_keepの中では一切使えなくなってしまうためである（もしこのdo_keepが定義されたところと同じスコープ内でnが定義されているなら、そのnの値を使えるが、keep_intsのnとは異なるため、２つの関数は全く紐づいていないことになる）。
ちなみに、keep_ints(5)(is_even)のように、引数を１つ１つ渡していく関数をカリー化という。
他にも、カリー化のわかりやすい例として以下のようなものがある。
>>> def make_adder(n):
def adder(k):
return n + k
return adder
>>> make_adder(2)(3)
5
>>> make_adder(2)
<function make_adder.<locals>.adder at 0x10f7cbd90>
このように、make_adder(2)だけでは関数adderを返しているだけにすぎなく、次の引数(3)を渡して初めて計算がされて数値が返ってくる。
練習問題１
２つの関数f、gを引数とし、f(g(x))を計算する高階関数を書きなさい。
>>> def compose(f, g):
"""
>>> def square(x):
return x * x
>>> comppose(square, square)(2)
16
""" # 以下解答
def h(x):
return f(g(x))
return h
練習問題２
先ほどのcomposeを改良して、f(f(f...f(x)...)をn回繰り返す関数を書きなさい。
>>> def n_compose(n, f):
"""
>>> n_compose(3, square)(2) # ((2**2)**2)**2
256
""" # 以下解答
def compose_helper(x):
i, result = 0, x
while i < n:
result = f(result)
i += 1
return result
return compose_helper
集合 Sets
対象としているものの集まりのうち、対象物が属しているか属していないかが、明確に判定できるあつまりを集合(set)という。集合を表す記号は通常英大文字を用いる。
集合を構成しているものを要素または元(element/member)といい、英小文字を用いる。
例：
aが集合Aの要素である時、a∈Aと表し、aはAに属すという。
bが集合Aの要素でない時、bAと表し、bはAに属さないという。
A
集合を示す主な方法は、
- 要素を列挙する方法(roster method)
V＝{a, i, u, e, o}
- 要素の条件を書く方法(set builder)
V＝{x｜x is an odd positive integer less than 10}
数の集合には世界共通で特別に記号が決まっている。
N＝自然数全体の集合＝{0, 1, 2, 3, ...}
Z＝整数全体の集合＝{..., -1, 0, 1, 2, ...}
Q＝有理数全体の集合＝{p/q｜p、q∈Z、q≠０}
R＝実数全体の集合
C＝複素数全体の集合
要素を１つも持たない集合を空集合(empty set/null set)といい、φで表す。
要素が１つのみの集合をsingleton setという。
要素の数が有限である集合を有限集合(finite set)、無限である集合を無限集合(infinite set)という。またAが有限集合の場合、要素の数(cardinality)をn(A)、｜A｜などで表す。
例：
A＝{x｜x is an odd positive integers less than 10}＝{1, 3, 5, 7, 9}
∴｜A｜＝５
｜φ｜＝０
集合Aの要素が集合Bの要素でもある時、AはBの部分集合であるといい、A⊆Bで表す。
A⊆BかつB⊆Aが成立する時、AとBは等しいといい、A＝Bと表す（要素が完璧に一致する）。またA⊆BかつA≠Bのとき、AはBの真部分集合であるといい、A⊂Bと書く。
集合Aの全ての部分集合からなる集合をAのベキ集合(power set)といい、P(A)または２^Aと表す。空集合φは全ての集合のベキ集合である。ベキ集合の要素数は、２^nである。
例：
A＝{a, b}のベキ集合は、要素の数が２なので、要素の数が０、１、２の部分集合が考えられる。要素が０の部分集合…φ、要素の数が１の部分集合…{a}、{b}、要素の数が２の部分集合…{a, b}、よってP(A)＝{φ、{a}、{b}、{a, b}}
B＝{φ}のベキ集合は、B＝空集合を要素としてもつ集合より、Bの要素の数は空集合１つなので、要素の数が０と１の場合が考えられる。要素が０…φ、要素が１…{φ}、よってP(B)＝{φ、{φ}}
C＝{0, 1, 2}のベキ集合は、要素が０…φ、要素が１…{0}, {1}, {2}、要素が２…{0, 1}, {0, 2}, {1, 2}、要素が３…{0, 1, 2}、よってP(C)＝{φ, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}
２つの集合A、Bに対して、A×B＝{(a, b)｜a∈A、b∈B}をAとBの直積集合、または単に直積(Cartesian product)という。直積集合A×Bとは、Aの要素aとBの要素bの組(a, b)を全部集めた集合のこと。組(a, b)は順序対(ordered pair)と呼ばれ、並んでいる順番に意味がある組であり、aを第１成分、bを第２成分という。
AとBが有限集合であれば、A×Bの要素の数＝Aの要素数×Bの要素数が成立する。
例：
A＝{1, 2}、B＝{a, b, c}の直積集合は、A×B＝{(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}
B＝{b1, b2}とした時、直積集合B^2＝{(b1, b1), (b1, b2), (b2, b1), (b2, b2)}
集合AとBの和集合(union)はA∪Bと表し、要素はA、またはB、または両方に属する。
例：
{1, 3, 5}と{1, 2, 3}の和集合は、{1, 3, 5}∪{1, 2, 3}＝{1, 2, 3, 5}
集合AとBの積集合(intersection)はA∩Bと表し、要素はAとBの両方に属する。積集合がφの場合、AとBはdisjointという。
例：
{1, 3, 5}∩{1, 2, 3}＝{1, 3}
{1, 3, 5}∩{2, 4, 6}＝φ
<ベン図(Venn Diagram)>
Uを全体集合(universal set)といい、Uに対しての集合Aの補集合(complement)を/Aと表し（Aの上にバー）、UーAで求められる。/A＝{x∈U｜xA}
ド・モルガンの法則/(A∩B)＝/A∪/Bを証明する。
/(A∩B)＝{x｜xA∩B}＝{x｜¬(x∈(A∩B))}＝{x｜¬(x∈A∧x∈B)}＝{x｜¬(x∈A)∨¬(x∈B)}
＝{x｜xA∨xB}＝{x｜x∈/A∪x∈/B}＝/A∪/B
