<a href="https://colab.research.google.com/github/kalz2q/mycolabnotebooks/blob/master/math_discrete_ishimurasonoko.ipynb" target="_parent"></a>

# メモ
やさしく学べる離散数学  
石村園子

を読む。
&nbsp;


# このノートの読み方
1. colab で開く
1. 上の方のメニューでドライブにコピーを押す
1. セルを実行しながら読む

&nbsp;

目次
1. 集合と論理
1. 関係と写像 => 有向グラフ、関係行列
1. 代数系 => 2項演算、半群と群、環と体
1. 重所集合と束
1. グラフ => ツリー、オイラーグラフ、ハミルトングラフ、有限オートマトン





# 集合
set

要素 element または元と言う。

$a \in A$ または $A \owns a$


$a \notin A$ または $A \not \owns a$

メモ $\quad$ latex の `\not \owns` で $\not \owns$ になった。 $\not \in$ は `\not \in`  $\neq$ は `\neq` と $\not =$ `\not =` のどちらでもオッケー。

&nbsp; 

集合は普通 `{}` 波括弧で表す。 latex の中では波括弧は `\` でエスケープすれば使える。

$A=\{1,2,3,4,5\}$

$A=\{n \ |\  1 \leq n \leq5,\  n は自然数\}$

$n$ は自然数は、$n \in \mathbb N$ とか $n \in \boldsymbol N$ と書く。


&nbsp;  

数の集合の表記 $\boldsymbol N$ 自然数、$\boldsymbol Z$ 整数、$\boldsymbol Q$ 有理数、$\boldsymbol R$ 実数、$\boldsymbol C$ 複素数。

黒板ボールドという書体もある。 $\mathbb N$ 自然数、$\mathbb Z$ 整数、$\mathbb Q$ 有理数、$\mathbb R$ 実数、$\mathbb C$ 複素数。

&nbsp;


**全体集合** $\quad U$

**空集合** $\quad \emptyset$ $\phi$ $\varnothing \quad$ `\emptyset$ $\phi$ $\varnothing`

集合 $A$ の要素が $B$ の要素であるとき、$A$ は $B$ の部分集合である、と言い、

$A \subseteq B$ または $B \supseteq A$ 

で表す。

$\quad \subseteq \quad$ `\subseteq`

$\quad \supseteq \quad$ `\supseteq`


$A \subseteq B \overset{\text{def}}{\Longleftrightarrow}$ $[x \in A \implies x \in B]$

$A \subseteq B \overset{\text{def}}{\iff}$ $[x \in A \implies x \in B]$

&nbsp;

メモ $\quad$ $\subset$ は $\subseteq$ を含まない真部分集合とする、というのが教育上の建前のようだが、数学的に無理があると思う。 実際いくつかのテキストは、$A\subset B \land  A\neq B$ のとき真部分集合と言う定義をしている。
教育上は日本もアメリカも Subset はそれ自身を含まない。含む場合は $\subseteq$ で明確にする、というルールのようである。

&nbsp;


集合はある全体集合 $U$ の部分集合として考え、特に $U \subseteq U$ である。

空集合 $\phi$ はすべての集合の部分集合と定めておく。

&nbsp;


**定義** $\quad A \subseteq B \land B \subseteq A$ が成立するとき、$A$ と $B$ は等しいと言い、$A=B$ と書く。

**定義** $\quad A \subseteq B \land A \neq B$ のとき $A$ は $B$ の真部分集合であると言い、 $A \subset B$と書く。

メモ $\quad$ これは別の流儀もあるとのことなので注意して使う。

この本では記号 $A \subseteq B$ を次の意味で使う。

$\quad \quad A \subseteq B \Longleftrightarrow [A \subset B \lor A=B]$

&nbsp;

**数の集合**

$\quad\quad \boldsymbol N \subset \boldsymbol Z \subset \boldsymbol Q \subset \boldsymbol R \subset \boldsymbol C$

&nbsp;


定義 $\quad$ 冪集合 べき集合

集合 $A$ のすべての部分集合からなる集合を $A$ の冪集合と言い、 $\mathcal P(A)$ または $2^A$ などで表す。

&nbsp;

例題 2 p.7 

(1) 次の集合の冪集合を集める。

1. $A=\{a,b\}\quad$  #=> $\mathcal P (A) = \{\phi,\{a\},\{b\},\{a,b\}\}$
2. $B=\{\phi\}\quad$ #=> $\mathcal P (B) = \{\phi,\{\phi\}\}$

(2) $A$ の部分集合の中で $\{a\} \subseteq X$ となる集合 $X$ をすべて求める。

=>  $\mathcal P (A)$ の要素の中で $\{a\} \subseteq X$ となる集合は $\{a\},\{a,b\}$

&nbsp;

# いまここ

練習問題 2 p.7 

(1) 次の集合の冪集合を求める。

1. $C=\{a,b,c\}\quad$ #=> $\mathcal P (C) = \{\phi,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$

2. $D=\{\phi,\{\phi\}\}\quad$ #=> $\mathcal P (D) = \{\phi,\{\phi\},\{\{\phi\}\},\{\phi,\{\phi\}\}\}$

(2) $C$ の部分集合のなkで $\{a\}\subseteq X$ となる集合 $X$ をすべて求める。

=> $\{a\},\{a,b\},\{a,c\},\{a,b,c\}$


```python
# べき集合のことを power set と言うらしい
from itertools import *
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

list(powerset(['a','b','c']))
```




    [(),
     ('a',),
     ('b',),
     ('c',),
     ('a', 'b'),
     ('a', 'c'),
     ('b', 'c'),
     ('a', 'b', 'c')]



全称記号 $\forall$ と 存在記号 $\exists$ の使い方

$\forall x \in \mathbf Z, \ x \in \mathbf R$ 

日本語訳 $\quad \mathbf Z$ に属するすべての (任意の) 要素 $x$ は $\mathbf R$ に属する。 整数はすべて実数である。

&nbsp;

$\exists x \in \mathbf Q, \ x \in \mathbf Z$

日本語訳 $\quad \mathbf Q$ には $\mathbf Z$ に属する要素 $x$ が存在する。有理数の中には整数であるものが存在する。

&nbsp;

$\forall$ と $\exists$ の順番で意味が変わる。

$\forall x \in \mathbf Z, \ \exists y \in \mathbf Z, \ x+y=1$ 

日本語訳 $\quad \mathbf Z$ の任意の要素 $x$ に対し、$\mathbf Z$ のある要素 $y$ が存在して、$x+y=1$ が成立する。
$\mathbf Z$ の任意の要素 $x$ に対し、$x+y=1$ となるような要素 $y$ が $\mathbf Z$ に存在する。

&nbsp;

$\exists x \in \mathbf R,\ \forall y \in \mathbf R, xy=y$ 

日本語訳 $\quad \mathbf R$
にある要素 $x$ が存在して、$\mathbf R$ の任意の要素 $y$ に対して $xy=y$ が成立する。
$\mathbf R$ の中には、$\mathbf R$ の任意の要素 $y$ に対して $xy=y$ が成立するような要素 $x$ が存在する。 (この $x$ は 1 のことである。)

&nbsp;



例題 3 p.8 日本語訳、論理記号訳を作る。

(1) $\forall x \in \mathbf R, \ x^2 \geq 0 \quad$ 

日本語訳: すべての実数 $x$ の 2乗は 0 以上である。

(2) $\exists x \in \mathbf R, \ x^2+x \leq 0 \quad$ 

日本語訳: $x^2+x \leq 0$ を満たす $x$ が $\mathbf R$ に存在する。

(3) $\forall n \in \mathbf Z,\ \exists m \in \mathbf Z,\ n+m=0 \quad$ 

日本語訳: $\mathbf Z$ の任意の $n$ について、$\mathbf Z$ に $n+m=0$ を満足させる $m$ が存在する。

(4) $\exists a \in \mathbf Z,\ \forall x \in \mathbf R,\ x^2-2x \geq a \quad $ 

日本語訳: すべての実数 $x$ について $x^2-2x \geq a$ が成立する整数 $a$ が存在する。

(5) 複素数の中には、2 乗すると実数になる数が存在する。

論理記号訳: $\exists z \in \mathbf C,\ z^2 \in \mathbf R$

(6) すべての実数 $x$ について、$x^2-2x+2 \geq 0$ が成立する。

論理記号訳: $\forall x \in \mathbf R,\ x^2-2x+2 \geq 0$

(7) 0 と異なる任意の実数 $x$ に対して、$xy=1$ となる実数 $y$ が存在する。

論理記号訳: $\forall x \in \mathbf R^*,\ \exists y \in \mathbf R,\ xy = 1 \quad$ ただし、$\mathbf R^* = \{x \ |\ x \in \mathbf R,\ x \neq 0\}$

(8) 任意の整数 $n$ に対し、 $n+a=n$ となる定数 $a$ が整数の中に存在する。 

論理記号訳: $\forall n \in \mathbf Z,\ \exists a \in \mathbf Z,\ n+a=n$ ($a$ は 0 のこと)

&nbsp;






メモ

$\mathrm R ^* = \mathrm R\backslash \{0\}$

$\mathrm R ^* = \{x \ |\ x \in \mathbf R,\ x \neq 0\}$

練習問題 3 p.9

(1) $\exists n \in \mathbf N,\ \sqrt n \in \mathbf N$

日本語訳: その平方根をとると自然数であるような自然数が存在する。

(2) $\forall x \in \mathbf R^*, \frac1x \in \mathbf R$

日本語訳: 0 を除く任意の実数を分母とし、分子を 1 とする分数は実数である。

(3) $\forall a \in \mathbf R^*,\ \forall x \in \mathbf R,\ \exists x \in \mathbf R,\ ax+b=0$

日本語訳: 実数 $a,b$ ただし $a \neg 0$ について、$ax+b=0$ となる実数 $x$ が存在する。

(4) $\exists a \in \mathbf R,\ \forall x \in \mathbf R,\ |\sin x| \leq a$

日本語訳: 任意の実数 $x$ について $\sin x$ の絶対値が $a$ 以下であるような実数 $a$ が存在する。

(5) 複素数の中には絶対値が 1 となる数が存在する。

論理記号訳: $\exists z \in \mathbf C,\ |z| = 1$

(6)  任意の実数 $a$ に対し、$x^2+x+2 \gt a$ となる有理数 $x$ が存在する。

論理記号訳: $\forall a \in \mathbf R ,\ \exists x \in \mathbf Q ,\ x^2+x+2 \gt a$

&nbsp;


集合の演算

定義

和集合

$A \cup B \overset{\text{def}}{\Longleftrightarrow} \{x \ |\ x \in \lor \ x \in  B\}$

積集合

$A \cap B \overset{\text{def}}{\Longleftrightarrow} \{x \ |\ x \in \land \ x \in  B\}$

補集合

$\overline A \overset{\text{def}}{\Longleftrightarrow} \{x \ |\ x \not \in A \}$

&nbsp;


# ベン図 Venn diagram 


```python
# ベン図 venn diagram
from matplotlib_venn import venn2
import matplotlib.pyplot as plt
from sympy import *

A = FiniteSet(1, 2)
B = FiniteSet(2, 3, 4)

venn2(subsets=(A,B))
plt.show()
print()
venn2(subsets=(15,10,5), set_labels=('X','Y'))
plt.show()
```

定理 1.1

冪等律

$A \cup A = A, \quad A \cap A = A$

交換律

$A \cup B = B\cup A,\quad A\cap B=B\cap A$

結合律

$(A \cup B)\cup C = A \cup (B \cup C)$

$(A \cap B)\cap C = A \cap (B \cap C)$

分配律

$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

吸収律

$A \cup (A \cap B) = A$

$A \cap (A \cup B) = A$

&nbsp;



定理 1.2 p.11

1. $A \cup \phi = A,\quad A\cap \phi = \phi$
1. $A \cup U = U,\quad A \cap U = A$
1. $A \cup \overline A = U,\quad A \cap \overline A = \phi$
1. $\overline{\overline A} = A$

&nbsp;

定理 1.3 p. 11

ド・モルガンの法則

1. $\overline{A \cup B}= \overline A \cap \overline B$

1. $\overline{A \cap B}= \overline A \cup \overline B$

&nbsp;

例題 4 p.11

次の性質をベン図で確認する。

1. $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

1. $\overline{A \cup B}= \overline A \cap \overline B$

&nbsp;


```python
# ベン図 venn diagram
from matplotlib_venn import venn3
import matplotlib.pyplot as plt
venn3(subsets = (4, 4, 2, 4, 2, 2, 1), set_labels = ('A', 'B', 'C'))
plt.show()
```


```python
# ベン図 venn diagram
from matplotlib_venn import venn2
import matplotlib.pyplot as plt
venn2(subsets = (4, 4, 2), set_labels = ('A', 'B'))
plt.show()
```

練習問題 4 p.11 次の性質をベン図で確かめる。
1. $A\cap(B \cup C) = (A\cap B) \cup (A\cap C)$

1. $\overline{(A \cap B)}=\overline A \cup \overline B$

&nbsp;

例題 5 p.12

$U=\{n \ |\ 1 \leq n \leq 15,\ n \in \mathbf Z\}$

を全体集合として、部分集合

$A = \{a \ |\ a は素数\}$

$B = \{b \ |\ b は奇数\}$

$C = \{c \ |\ c は 3 の倍数\}$

を考える。

1. $A,B,C$ の要素を列挙して、ベン図に表す。

2. $B \cup C, B \cap C, \overline{A \cup C}, \overline B \cap C$ を求めてみる。

&nbsp;



```python
# ベン図 venn diagram
from matplotlib_venn import venn3
import matplotlib.pyplot as plt

A = set([2,3,5,7,11,13])
B = set([1,3,5,7,9,11,13,15])
C = set([3,6,9,12,15])
U = set([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15])

venn3(subsets=(A,B,C))
plt.show()
```

$A \cup B \overset{\text{def}}{\Longleftrightarrow} \{x \ |\ x \in A \lor x \in B\}$

$A \cap B \overset{\text{def}}{\Longleftrightarrow} \{x \ |\ x \in A \land x \in B\}$

$\overline A \overset{\text{def}}{\Longleftrightarrow} \{x \ |\ x \not \in A \}$


練習問題 5 p.12

$U = \{ n \ |\ n は90の正の約数\}$ を全体集合とし、$U$ の部分集合を

$A=\{a \ |\ a は 2 の倍数\}$、$B=\{b \ |\ b は 3 の倍数\}$、$C=\{c \ |\ c は 5 の倍数\}$ 

とするとき、次の集合の要素を求める。

1. $U,A,B,C$
1. $A\cup B, A\cap C,\overline B, B\cup \overline C, A \cup (\overline B \cap \overline C)$

&nbsp;


```python
# 問題おかしくないか?
from matplotlib_venn import venn3
import matplotlib.pyplot as plt

A = set([2,6,10,18,30,90])
B = set([3,6,9,15,18,30,45,90])
C = set([5,10,15,30,45,90])
U = set([1,2,3,5,6,9,10,15,18,30,45,90])

print(A.union(B))
print(A.intersection(C))
print(U.difference(B))
print(C.union(U.difference(C)))
print(A.union((U.difference(B)).intersection(C)))
print(sorted(A.union((U.difference(B)).intersection(C))))
venn3(subsets=(A,B,C))
plt.show()
```

要素の個数 p.13

定義

要素の数が有限である集合を有限集合と言う。

有限集合でない集合を無限集合と言う。

&nbsp;

説明 p.13

$A_1=\{2,4,6,\cdots,98,100\}$

$B_1=\{1,3,5,\cdots,99\}$

などは有限集合であるが、

$A_2=\{2,4,6,\cdots\} = \{m \ |\ m = 2k, \ k \in \mathbf N\}$

$B_2=\{1,3,5,\cdots\} = \{m \ |\ m = 2k-1, \ k \in \mathbf N\}$

や、$\mathbf{N,Z,Q,R,C}$ はすべて無限集合である。


これらの数の集合の中で $\mathbf Z$ と $\mathbf Q$ の要素はともに $\mathbf N$ の要素と 1 対 1 に対応をつけることができるが、$\mathbf R$ と $\mathbf C$ の要素は $\mathbf N$ の要素と 1 対 1 に対応をつけることができない。

有限集合および $\mathbf {N,Z,Q}$ は離散集合、可算集合、可付番集合などと呼ばれる。

$A$ が有限集合の場合、要素の数を

$n(A), |A|, \#(A)$

などで表す。

有限集合の要素の数については次の定理が成立する。

&nbsp;




定理 1.4 p.13

$U$ を有限な全体集合とする。

$A,B$ を $U$ の部分集合とするとき、次の式が成立する。

1. $n(A\cup B) = n(A)+n(B)-n(A\cap B)$

1. $n(\overline A) =n(U) - n(A)$

&nbsp;




例題 6 p.14

$U=\{m\ |\ 1 \leq m \leq 100, \ m \in \mathbf N\}$ を全体集合とし

$A=\{m\ |\ m=5k,\ k\in \mathbf N\}$、$B=\{m\ |\ m=7k,\ k\in \mathbf N\}$

とするとき、次の値を求める。

1. $n(A),\ n(B),\ n(A \cap B)$
2. $n(A\cup B),\ n(\overline A),\ n(B)$
3. $n(\overline A \cup \overline B),\ n(\overline A \cap \overline B)$

ド・モルガンの法則をつかってもよい。

&nbsp;


# 命題

定義

真か偽か 真か偽か 真か偽かどちらか一方に明確に定まる主張を命題と言う。

&nbsp;


```python
# python では 真偽は True , False
0 == 0
```




    True



命題を $p,q,r,\cdots$ などの英小文字で表し、その中身は

$p=$ 犬は動物である

$p=[5+3=8]$

などと書く。

命題の真偽を真理値と言い、$\mathrm{T, F}$ の記号を使う。

命題 $p$ が真のときは、$\quad p = \mathrm T$ 

などと書く。

&nbsp;

定義

変数にある特定の要素を代入すると真偽が定まる主張を命題関数または述語 predicate と言う。

&nbsp;

命題関数は $x$ を変数として $p(x)$ などで表す。

&nbsp;


例題 7 p.16 命題かどうか。命題ならば真理値を求める。

1. 100 は自然数である。
1. 100 は大きい数である。
1. 人間は優れた生物である。
1. 地球は平らである。


1. $p(x)=x$ は動物である $\quad$ について、$x=$ 石、$x=$ 馬
1. $q(x)=[x^2-1=0]$ $\quad$ について $q(0),\ q(1)$

&nbsp;

練習問題 7 p.16 命題かどうか。命題ならば真理値を求める。

1. $\sqrt 2$ は有理数である。
1. $\sqrt 2$ は実数である。
1. 数学は美しい学問である。
1. スイカは果物である。


1. $p(x)=x$ は植物である $\quad$ について $x=$ ウサギ、$x=$ ユリ
1. $q(x)=[x^2-x-2=0]$ $\quad$ について $q(0),\ q(-1)$

&nbsp;

命題論理と述語論理
p. 17

わかりません。

命題論理はただの真偽で、述語論理は関係を表す。

命題論理は $P(x)$ で、述語論理は $Q(x,y)$ 。

述語論理は $\forall, \exists$ を含む。

&nbsp;



# いまここ

論理演算

p.18

定義

命題 $p,q$ の真偽 $\mathrm{T,F}$ により右表の真理値をもつ命題 $p\lor q, p\land q$ について

$p$ $\ $ $q$ | $p$ $\lor$ $q$ | $p$ $\land$ $q$ 
--- | :-: | :-: 
$\mathrm{T}$ $\ \ $ $\mathrm{T}$ | $\mathrm{T}$ | $\mathrm{T}$
$\mathrm{T}$ $\ \ $ $\mathrm{F}$ | $\mathrm{T}$ | $\mathrm{F}$
$\mathrm{F}$ $\ \ $ $\mathrm{T}$ | $\mathrm{T}$ | $\mathrm{F}$
$\mathrm{F}$ $\ \ $ $\mathrm{F}$ | $\mathrm{F}$ | $\mathrm{F}$



# 命題と真理値

真偽が明確に定まる式や文を命題 proposition と言う。

$x+1=2$ のように変数 $x$ が含まれている場合、命題にはならない。 $x$ に要素を代入したときに真理値が定まるものを, $x$ についての述語 predicate あるいは条件 condition と言い、$c(x),p(x)$ などと表す。



**合成命題**

compound proposition

George Bool 1815-1864 イギリスの数学者

**構成規則**

でない、かつ、または、ならば =>  論理結合子 logical connective =>  
$\lnot , \land, \lor, \Rightarrow $

これらの文字や記号が構成規則に従って組合されてできた記号列を論理式 well-formed formula と言う。

1. 命題を表す文字は論理式である。
1. $p$ と $q$ が論旨式ならば、$(\lnot p), (p \land q), (p \lor q), (p \Rightarrow q), (p \Leftrightarrow q)$ は論理式である。

$r,s$ を命題とするとき、構成規則により、次の論理式が得られる。

$\quad r, (\lnot r), (r \land s), ((\lnot r) \land s), ((r \land s) \lor (\lnot r)), (s \Rightarrow (\lnot r)) $


# sympy の logic

https://docs.sympy.org/latest/modules/logic.html

論理式を表示してくれる部分しかわからないが、とりあえず colab 上で動くことを確認してみる。


```python
from sympy.abc import *
from sympy import *
display( y | (x & y))
display(x | y)
display(~x)
```


$\displaystyle y \vee \left(x \wedge y\right)$



$\displaystyle x \vee y$



$\displaystyle \neg x$



```python
from sympy.abc import *
from sympy import *
display(x  >> y)
display(Implies(x, y))
display(x << y)
display(Implies(y,x))
```


$\displaystyle x \Rightarrow y$



$\displaystyle x \Rightarrow y$



$\displaystyle y \Rightarrow x$



$\displaystyle y \Rightarrow x$



```python
(y & x).subs({x: True, y: True})
```




$\displaystyle \text{True}$




```python
(x | y).atoms()
```




    {x, y}




```python
# SOPform
minterms = [[0, 0, 0, 1], [0, 0, 1, 1],
            [0, 1, 1, 1], [1, 0, 1, 1], [1, 1, 1, 1]]
dontcares = [[0, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 1]]
SOPform([w, x, y, z], minterms, dontcares)
```




$\displaystyle \left(y \wedge z\right) \vee \left(z \wedge \neg w\right)$




```python
# 整数で示すことができる
minterms = [1,3,7,11,15]
dontcares = {0,2,5}
SOPform([w, x, y, z], minterms, dontcares)
```


```python
# 辞書で示すことができる
minterms = [{w:0,x:1},{y:1,z:1,x:0}]
SOPform([w, x, y, z], minterms)
```


```python
# 混ぜて使うこともできる
minterms = [4,7,11,[1,1,1,1]]
dontcares =[{w:0,x:0,y:0},5]
SOPform([w,x,y,z],minterms,dontcares)
```


```python
# POSform
minterms = [[0, 0, 0, 1], [0, 0, 1, 1],
            [0, 1, 1, 1], [1, 0, 1, 1], [1, 1, 1, 1]]
dontcares = [[0, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 1]]
POSform([w, x, y, z], minterms, dontcares)
```




$\displaystyle z \wedge \left(y \vee \neg w\right)$




```python
# 整数で示すことができる
minterms = [1,3,7,11,15]
dontcares = {0,2,5}
POSform([w, x, y, z], minterms, dontcares)
```




$\displaystyle z \wedge \left(y \vee \neg w\right)$




```python
# 辞書で示すことができる
minterms = [{w:0,x:1},{y:1,z:1,x:0}]
POSform([w, x, y, z], minterms)
```




$\displaystyle \left(x \vee y\right) \wedge \left(x \vee z\right) \wedge \left(\neg w \vee \neg x\right)$




```python
# 混ぜて使うこともできる
minterms = [4,7,11,[1,1,1,1]]
dontcares =[{w:0,x:0,y:0},5]
POSform([w,x,y,z],minterms,dontcares)
```




$\displaystyle \left(w \vee x\right) \wedge \left(y \vee \neg w\right) \wedge \left(z \vee \neg y\right)$




```python
from sympy import sympify, true, false, Or
display(sympify(True))
display((_ is True, _ is true))
display(Or(true,false))
display(_ is true)
display((true >> true, True >> True))
```


$\displaystyle \text{True}$



    (False, False)



$\displaystyle \text{True}$



    False



    (True, 0)



```python
display(true.as_set()) #=> U, UniversalSet
```


$\displaystyle \mathbb{U}$



```python
from sympy import sympify, true, false, Or
display(sympify(False))
display((_ is False, _ is false))
display(Or(true,false))
display(_ is true)
display((~false, ~False))
display((false >> false, False >> False))
```


$\displaystyle \text{False}$



    (False, False)



$\displaystyle \text{True}$



    False



    (True, -1)



    (True, 0)



```python
false.as_set() #=> EmptySet
```




$\displaystyle \emptyset$




```python
display(x & y)
display(And(x,y).subs(x,1))
display(x | y)
display(Or(x,y).subs(x,0))
display(Not(True))
display(Not(False))
display(And(True,False))
display(Or(True,False))
display(Not(And(And(True,x), Or(x,False))))
display(Not(And(Or(A,B), Or(Not(A), Not(B)))))


```


$\displaystyle x \wedge y$



$\displaystyle y$



$\displaystyle x \vee y$



$\displaystyle y$



$\displaystyle \text{False}$



$\displaystyle \text{True}$



$\displaystyle \text{False}$



$\displaystyle \text{True}$



$\displaystyle \neg x$



$\displaystyle \neg \left(\left(A \vee B\right) \wedge \left(\neg A \vee \neg B\right)\right)$



```python
display(~True)
display(~true)
```


    -2



$\displaystyle \text{False}$



```python
display(Xor(True,False))
display(Xor(True,True))
display(Xor(True,False,True,True,False)) #=> True の数が奇数だと Truelay(Xor(True,False))
display(Xor(True,True))
display(Xor(True,False,True,True,False)) #=> True の数が奇数だと True
display(Xor(True,False,True,False))
display(x ^ y)
```


$\displaystyle \text{True}$



$\displaystyle \text{False}$



$\displaystyle \text{True}$



$\displaystyle \text{False}$



$\displaystyle x \veebar y$



```python
Xor(x,y).subs(y,0)
```




$\displaystyle x$




```python
# Nand は頭から評価していって、False があれば即座に True、最後までFalseがなければ False
# その結果、False がひとつでもあれば True, なければ False になる
display(Nand(False,True))
display(Nand(True,True))
display(Nand(x,y))
```


$\displaystyle \text{True}$



$\displaystyle \text{False}$



$\displaystyle \neg \left(x \wedge y\right)$



```python
# Nor は頭から評価していって、True があれば即座に False、最後までTrueなければ True
# その結果、True がひとつでもあれば Fale, なければ True になる
display(Nor(False,True))
display(Nor(True,True))
display(Nor(False,False))
display(Nor(x,y))
```


$\displaystyle \text{False}$



$\displaystyle \text{False}$



$\displaystyle \text{True}$



$\displaystyle \neg \left(x \vee y\right)$



```python
# Implies は A が True で B が False のときのみ False を返し、それ以外では True である
from sympy.abc import *
from sympy import *
display(Implies(True, False))
display(Implies(False, False))
display(Implies(True, True))
display(Implies(False, True))
display(x >> y)
display(y << x)

```


$\displaystyle \text{False}$



$\displaystyle \text{True}$



$\displaystyle \text{True}$



$\displaystyle \text{True}$



$\displaystyle x \Rightarrow y$



$\displaystyle x \Rightarrow y$



```python
display(True >> False)
display(true >> false)

```


    1



$\displaystyle \text{False}$



```python
# Equivalent は A と B の両方が True または False のときに True
# Equivalent is True iff A and B are both True or both False
from sympy.abc import *
from sympy import *
Equivalent (False, False, False)
Equivalent (True, False, False)
Equivalent (x, And(x, True)) #=> なるほど!!!!
```




$\displaystyle \text{True}$




```python
# ITE if then else clause
# A が真なら B の結果、偽なら C の結果を返す
display(ITE(True, False, True))
display(ITE(Or(True,False),And(True,True),Xor(True,True)))
display(ITE(x,y,z))
display(ITE(True, x, y))
display(ITE(False, x, y))
display(ITE(x,y,y))

```


$\displaystyle \text{False}$



$\displaystyle \text{True}$



$\displaystyle ITE\left(x, y, z\right)$



$\displaystyle x$



$\displaystyle y$



$\displaystyle y$



```python
# ITE は if then else と言っても引数に bool 値以外はエラー
# display(ITE(True, [],())) #=> TypeError
```


```python
# to_cnf(expr, simplify=False, force=False)
# Convert a propositional logical sentence s to 
# conjunctive normal form: ((A | ~B | …) & (B | C | …) & …). 
from sympy.abc import *
from sympy import *
display(to_cnf(~(A|B)|D))
display(to_cnf((A|B)&(A|~A)))
display(to_cnf((A|B)&(A|~A),True))

```


$\displaystyle \left(D \vee \neg A\right) \wedge \left(D \vee \neg B\right)$



$\displaystyle \left(A \vee B\right) \wedge \left(A \vee \neg A\right)$



$\displaystyle A \vee B$



```python
# to_dnf(expr, simplify=False, force=False)
# Convert a propositional logical sentence s to 
# disjunctive normal form: ((A & ~B & …) | (B & C & …) | …).
from sympy.abc import *
from sympy import *
from sympy.abc import C
display(to_dnf(B & (A | C)))
display(to_dnf((A&B)|(A&~B)|(B&C)|(~B&C)))
display(to_dnf((A&B)|(A&~B)|(B&C)|(~B&C),True))
```


$\displaystyle \left(A \wedge B\right) \vee \left(B \wedge C\right)$



$\displaystyle \left(A \wedge B\right) \vee \left(A \wedge \neg B\right) \vee \left(B \wedge C\right) \vee \left(C \wedge \neg B\right)$



$\displaystyle A \vee C$



```python
from sympy.abc import *
from sympy import *
from sympy.abc import C
from sympy.logic.boolalg import is_cnf
display(is_cnf(A|B|C))
display(is_cnf(A&B&C))
display(is_cnf((A&B)|C))
```


    True



    True



    False



```python
from sympy.abc import *
from sympy import *
from sympy.abc import C
from sympy.logic.boolalg import is_dnf
display(is_dnf(A|B|C))
display(is_dnf(A&B&C))
display(is_dnf((A&B)|C))
display(is_dnf(A&(B|C)))
```


    True



    True



    True



    False



```python
# simplify_logic(expr,form=None,deep=True,force=False)
from sympy.abc import *
from sympy import *
b=(~x&~y&~z) | (~x&~y& z)
display(b)
display(simplify_logic(b))
display(S(b)) #=> SingletonRegistry
display(simplify_logic(S(b)))
```


$\displaystyle \left(z \wedge \neg x \wedge \neg y\right) \vee \left(\neg x \wedge \neg y \wedge \neg z\right)$



$\displaystyle \neg x \wedge \neg y$



$\displaystyle \left(z \wedge \neg x \wedge \neg y\right) \vee \left(\neg x \wedge \neg y \wedge \neg z\right)$



$\displaystyle \neg x \wedge \neg y$



$\displaystyle B \wedge \left(A \vee C\right)$



```python
# bool_map(bool1, bool2)
from sympy.abc import *
from sympy import *
function1 = SOPform([x, z, y],[[1, 0, 1], [0, 0, 1]])
function2 = SOPform([a, b, c],[[1, 0, 1], [1, 0, 0]])
display(bool_map(function1, function2))
```


    (y & ~z, {y: a, z: b})



```python
eq =  Or(And(Not(y), w), And(Not(y), z), And(x, y))
eq2 = Or(And(Not(c), a), And(Not(c), d), And(b, c))
display(bool_map(eq, eq2))
eq = And(Xor(a, b), c, And(c,d))
display(bool_map(eq, eq.subs(c, x)))
```


    ((x & y) | (w & ~y) | (z & ~y), {w: a, x: b, y: c, z: d})



    (c & d & (a | b) & (~a | ~b), {a: a, b: b, c: d, d: x})



```python
# inference, satisfiable
from sympy.abc import *
from sympy import *
display(satisfiable(x & ~x))
display(satisfiable((x|y)&(x|~y)&(~x|y)))
display(satisfiable(x))
```


    False



    {x: True, y: True}



    {x: True}



```python
display(satisfiable(True))
```


    {True: True}



```python
display(next(satisfiable(A & ~A, all_models=True)))
models=satisfiable((A >> B)&B, all_models=True)
display(next(models))
def use_models(models):
    for model in models:
        if model:
            # do something with the model
            print(model)
        else:
            # Given expr is unsatisfiable
            print("UNSAT")
use_models(satisfiable(A>>~A,all_models=True))
use_models(satisfiable(A^A,all_models=True))
```


    False



    {A: False, B: True}


    {A: False}
    UNSAT


# 逆


```python

```

論理式 $p \Rightarrow q$ において、$p$ を仮定 hypothesis または前提 antecedent, premise 、 $q$ を結論 conclusion, consequent と言う。

仮定と結論を入れ替えた $q \Rightarrow p$ を $p \Rightarrow q$ の逆 converse と言う。

反例 counter example



# 必要十分条件

論理式 $p \Rightarrow q$ が成り立つとき

$q$ を $p$ (が成り立つため) の必要条件 necessary condition と言う。

$p$ を $q$ (が成り立つため) の十分条件 sufficient condition と言う。

$p \Longleftrightarrow q$ が成り立つとき

$p$ を $q$ (が成り立つため) の必要十分条件と言う。このとき $p$ と $q$ は同値であると言う。

恒真 トートロジー tautology

恒偽 contradiction


# 充足可能性問題 satisfiable problem SAT

ある論理式が真となるための各命題への真理値の割り当て方(組合せ)が少なくとも 1通りあるとき、すなわち恒真でない論理式を充足可能 sastifiable と言う。


ipynb
22f04a9a396384dcfbbf48cf0d4d702fbdb1a311
Jupyter Notebook
ba37ac7822543b830fe8602b3f611bb617943463
MIT
kalz2q/-yjupyternotebooks
math_discrete_ishimurasonoko.ipynb
ba37ac7822543b830fe8602b3f611bb617943463
MIT
kalz2q/-yjupyternotebooks
math_discrete_ishimurasonoko.ipynb
ba37ac7822543b830fe8602b3f611bb617943463
MIT
kalz2q/-yjupyternotebooks
math_discrete_ishimurasonoko.ipynb
2021-09-16T03:45:19.000Z
2021-09-16T03:45:19.000Z