Bài giảng môn học Toán học rời rạc
Bài giảng môn học Toán học rời rạc cung cấp cho các bạn những kiến thức chính về: Tập hợp và logic mệnh đề, giải thuật và các phương pháp đếm, lý thuyết đồ thị và cây. Để hiểu rõ hơn về bài giảng mời các bạn cùng tham khảo tài liệu. » Xem thêm
Tóm tắt nội dung tài liệu
- TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN KHOA HỌC MÁY TÍNH
-------------o0o------------
BÀI GIẢNG MÔN HỌC
TOÁN HỌC RỜI RẠC
HỆ ĐẠI HỌC
Số tín chỉ: 3TC
Hệ đào tạo: ĐHCQ
Ngành: CNTT, HTTTQL, TMĐT.
Bộ môn giảng dạy: Bộ môn KHMT – Khoa CNTT.
Thái Nguyên, năm 2015
0
- MỤC LỤC
Mục Trang
Chương 1: TẬP HỢP VÀ LOGIC MỆNH ĐỀ……………………………… 2
1.1 Tập hợp và các phép toán trên tập hợp………………………………….. 2
1.2. Quan hệ…………………………………..……………………………... 5
1.3. Logic mệnh đề………………………………….. …………………….. 8
1.4. Suy luận toán học và các phương pháp chứng minh…………………… 16
Chương 2: GIẢI THUẬT VÀ CÁC PHƯƠNG PHÁP ĐẾM………………. 22
2.1. Thuật toán và các đặc trưng cơ bản của thuật toán……………………… 22
2.2. Thuật toán đệ quy…………………………………..……………………. 28
2.3. Thuật toán quay lui………………………………….. …………………. 33
2.4. Các nguyên lý đếm cơ bản………………………………….. ………… 37
2.5. Hoán vị và tổ hợp…………………………………..…………………… 40
Chương 3: LÝ THUYẾT ĐỒ THỊ VÀ CÂY………………………………… 50
3.1. Đồ thị và các khái niệm cơ bản trong đồ thị ……………………………. 50
3.2. Bậc, đường đi, chu trình và tính liên thông của đồ thị………………….. 54
3.3. Các phương pháp duyệt đồ thị…………………………………………... 57
3.4. Một số đơn đồ thị đặc biệt………………………………….. …………. 59
3.5. Đồ thị Euler…………………………………..…………………………. 63
3.6. Đồ thị Hamilton………………………………………………………… 68
3.7. Thuật toán tìm đường đi ngắn nhất. ………………………………….. 73
3.8. Cây và cây khung của đồ thị……………………………………………. 80
TÀI LIỆU THAM KHẢO…………………………………………………… 90
1
- CHƯƠNG 1
TẬP HỢP & LOGIC MỆNH ĐỀ
1.1.Tập hợp
1.1.1 Khái niệm chung về tập hợp
Tập hợp là một trong những khái niệm quan trọng nhất của toán học, nó là gốc rễ
của các ngành toán học khác nhau. Vào nửa đầu thế kỷ 19, nhà toán học người Đức
Geory Cautar (1845 – 1918) đã nghiên cứu các tập hợp và ứng dụng của chúng như là
nền tảng của các ngành toán học (các công trình được công bố vào những năm từ 1871
– 1883) . Lý thuyết tập hợp sau khi xuất hiện đã thống nhất được nhiều quan niệm toán
học và đã xây dựng nên các cơ sở logic của nhiều ngành toán học khác nhau.
Tập hợp được coi là 1 cấu trúc rời rạc bao gồm nhiều đối tượng được nhóm lại
với nhau, thông thường các đối tượng trong một tập hợp có một vài tính chất tương tự
nhau.
Các đối tượng trong tập hợp được gọi là các phần tử của tập hợp đó. Trật tự của
các các phần tử trong tập hợp là không quan trọng, quan trọng là phần tử đó có mặt
trong tập hợp hay không.
Ví dụ:
Tập hợp các số tự nhiên N.
Tập N+ các số tự nhiên khác 0
Tập các số nguyên Z
Tập các số hữu tỷ Q
Tập các số thực R
Ký hiệu:
Phần tử tập hợp dùng chữ in thường.
Tập hợp dùng chữ in hoa.
Để ký hiệu x là phần tử của tập A, ta viết: xA (x thuộc A hay x là phần tử của A).
Nếu x không là phần tử của tập A thì ta viết: xA (x không thuộc A).
1.1.2.Một số tập hợp đặc biệt
a.Tập con
Cho 2 tập hợp A và B. Nếu mọi phần tử của A đều là phần tử của B thì ta viết:
AB hoặc BA và gọi là A là tập con của B (A được chứa trong B; A được bao hàm
trong B; A là bộ phận của B; B bao hàm A…).
Ví dụ: N*NZQR
Hai tập A và B được gọi là bằng nhau nếu AB và BA. Ký hiệu là A=B
Nếu AB và AB thì ta nói A là tập con thực sự của B, ký hiệu A B. Nếu A không
là tập con thực sự của B thì ta viết AB
b.Tập hợp rỗng:Tập hợp không chứa phần tử nào gọi là tập rỗng. Tập rỗng được ký
hiệu là .Với mọi tập A ta có A.Tập rỗng là duy nhất.
c.Tập hợp các tập con của một tập hợp: Cho X là một tập hợp. Tập hợp các tập con
của tập X ký hiệu là P(X) hay 2X. P(X) = {A | AX}
Ví dụ: X = thì P(X) = {}
X = {a, b} thì P(X) = {, {a}, {b}, {a,b}}
d. Tập hợp bù: Với mỗi AX đặt AC = X\A hay X X \ A gọi là phần bù của A trong
X. Ta có: AAC = X hay A A X ; AAC = hay A A
2
- Theo tính chất ta có:
(AB)C = ACBC
(AB)C = ACBC
1.1.3 Cách xác định tập hợp
a. Liệt kê các phần tử của tập hợp trong cặp ngoặc {…}
Một tập hợp có thể được xác định bằng cách liệt kê tất cả các phần tử của nó:
A = {a, e, o, i, u}: tập tất cả các nguyên âm (của bảng chữ cái Aab)
A = {1, 2, 3, 5, 7}
Khi không liệt kê hết ta dùng dấu …
A = {0, 1, 2, …, 99}: Tập tất cả các số tự nhiên từ 0 đến 99.
B = {0, 2, 4, 6, …}: Tập tất cả các số tự nhiên chẵn.
b. Chỉ ra thuộc tính đặc trưng của các phần tử trong tập hợp bằng một mệnh đề
(x) nào đó.
Nếu A là tập gồm các phần tử x của tập X có tính chất P(x) thì ta viết:
A = {xX | P(x)}
Ví dụ : A = {xR | x2 – 4x + 3 = 0}
B = {nN | n là ước của 20}
C = {nN* | xn + yn = zn có nghiệm nguyên dương}
c. Dùng giản đồ Venn
Qui ước:
Tập hợp vũ trụ U: tập chứa tất cả các phần tử đang xét, được biểu diễn bằng
một hình chữ nhật.
Bên trong hình chữ nhật, dùng hình tròn, hình elip để biểu diễn cho các tập hợp.
Các điểm được dùng để biểu diễn cho các phần tử của tập hợp.
Ví dụ : U = N
A = {2, 4, 6, 8, 10}
N
A .2 .10
.8
.4 .6
1.1.4 Phép toán trên tập hợp
a. Phép hợp: Cho hai tập hợp A, B. Ta gọi A hợp B là tập gồm các phần tử thuộc A
hoặc thuộc B. Ký hiệu là AB, như vậy AB = {a | aA hoặc aB}.
b. Phép giao:
Cho hai tập hợp A, B. Ta gọi A giao B là tập gồm các phần tử vừa thuộc A vừa
thuộc B. Ký hiệu là AB, như vậy AB = {a | aA và aB}.
Nếu không có phần tử nào vừa thuộc A vừa thuộc B thì AB = . Trong trường
hơp này ta nói A và B rời nhau hoặc không giao nhau.
c. Phép hiệu:
Cho hai tập hợp A, B. Ta gọi A trừ B (hay hiệu của A và B) là tập gồm các phần tử
thuộc A nhưng không thuộc B. Ký hiệu là A\B.
3
- A\B = {a | aA và aB}.
Lưu ý: A\B khác B\A.
d. Phép hiệu đối xứng:
Cho hai tập hợp A, B. Ta gọi hiệu đối xứng của A và B là tập gồm các phần tử chỉ
thuộc A hoặc chỉ thuộc B, không đồng thời thuộc cả A và B. Ký hiệu là AB.
A B = {(A\B) (B\A)}.
Ví dụ 1: Cho A ={0, 1, 2, 4, 6} B = {1, 3, 5, 6}
AB = {0, 1, 2, 3, 4, 5, 6} AB = {0,6}
A\B = {1, 2, 4} B\A = {3, 5} AB = {1, 2, 4, 3, 5}
Ví dụ 2: A = {xN | x chia hết cho 2}; B = {xN | x chia hết cho 3}
AB = {xN | x chia hết cho 2 và chia hết cho 3}
1.1.4 Các tính chất trên tập hợp
Với A, B, C là các tập hợp bất kỳ ta có:
1.Tính chất giao hoán: AB = BA và AB = BA
2.Tính chất kết hợp: (AB)C = A(BC)
(AB)C = A(BC)
3.Tính chất phân phối: A(BC) = (AB)(AC)
A(BC) = (AB)(AC)
4.Luật đối ngẫu Demorgan: A B A B
A B A B
5.Luật nuốt: nếu AB thì AB = B, AB = A
Chứng minh:
Các tính chất 1, 2, 5 là hiển nhiên. Các tính chất còn lại được chứng minh tương tự nhau.
Chứng minh tính chất 3: A(BC) = (AB)(AC)
Thật vậy với aA(BC)
aA hoặc aBC
aA hoặc aB và aC
aA hoặc aB và aA hoặc aC
aAB và aAC
a (AB)(AC)
Tức là có tính chất 3.
Lưu ý:
Vì A và AA với A nên: A = A, A = , AA = A, AA = A
1.1.5 Mở rộng các phép toán tập hợp
a. Mở rộng tính chất 2
Với các tập A1, A2,…, An ta có:
A1A2 A3 = (A1A2)A3
n
Ai A1 A2 ... An = ( A1 A2 ... An1 ) An
i 1
A1A2 A3 = (A1A2)A3
n
Ai A1 A2 ... An = ( A1 A2 ... An1 ) An
i 1
b.Mở rộng tính chất 3
Cho các tập hợp X, A1, A2,…, An ta có:
2
- X Ai X Ai
n n
i 1 i 1
X Ai X Ai
n n
i 1 i 1
c.Mở rộng tính chất 4
Cho các tập hợp X, A1, A2,…, An ta có:
n n
Ai Ai
i 1 i 1
n n
Ai Ai
i 1 i 1
1.1.7 Tích đề các
a. Tích đề các của 2 tập hợp
Cho A, B là 2 tập hợp. Với mỗi aA, bB. Ta gọi (a, b) là một cặp. Hai cặp (a, b)
và (c, d) gọi là bằng nhau nếu a = c và b = d.
Ta gọi tích đề các của A và B là tập AB gồm các cặp (a, b) với aA, bB
AB = {(a,b) | aA, bB}
Tích đề các AA ký hiệu là A2 (Bình phương đề các)
Ví dụ: = {1, 2, 3}; B = {a, b} thì:
AB = {(1, a); (1, b); (2, a); (2, b); (3, a); (3, b)}
BA = {(a, 1); (a, 2); (a, 3); (b, 1); (b, 2); (b, 3)}
AA = A2 = {(1, 1); (1, 2); (1, 3); (2, 1); (2, 2); (2, 3); (3, 1); (3, 2); (3, 3)}
BB = B2 = {(a,a); (a,b); (b,a); (b,b)}
b.Tích đề các của n tập hợp
Cho n tập hợp A1, A2,…, An. Khi đó tích đề các của n tập hợp này ký hiệu là
A1 A2 … An = Ai a1 ,, a n / a1 A1 ,, a n An
n
i 1
Hai bộ (a1, a2, …, an) và (b1,b2, …, bn) gọi là bằng nhau nếu: a1 = b1; a2 = b2 ; …; an = bn
n
Nếu A1 = A2 = … = An thì ký hiệu Ai A n và gọi là luỹ thừa đề các bậc n của tập hợp
i 1
A.
1.1.8 Tập hợp hữu hạn
a. Bản số của tập hữu hạn
Tập A được gọi là hữu hạn nếu nó là tập hoặc liệt kê được tất cả các phần tử của
tập A, như vậy tập A là hữu hạn nếu:
A=
A = {a1, a2, …, an) với các ai là khác nhau ( i = 1,..,n).
Trong trường hợp 1 ta nói A có bản số 0. Trong trường hợp 2 ta nói A có bản số n.
Kí hiệu: A=0; hay N(A)=0; A=n; hay N(A)=n
Nhận xét:
Bản số của một tập hữu hạn chính là số phần tử của tập đó.
Hai tập hữu hạn cùng bản số có cùng số phần tử.
b.Tính chất của bản số hữu hạn
Định lý 1: Cho A, B là hai tập hữu hạn, khi đó:
1. |AB| = |A| + |B| – |AB|
2. |A\B| = |A| – |AB|
3
- 3. |AB| = |A| + |B| – 2|AB|
Chứng minh:
1.Giả sử |A| = m; |B| = n. A = {a1, a2, …, am} và B = {b1, b2, …, bn}
Xét trường hợp AB = :
AB = {a1, a2, …, am, b1, b2, …, bn} do đó |AB| = m + n = |A| + |B|
Trường hợp AB có k phần tử. Đặt AB = {a1, a2, …, ak}. Khi đó:
A = {a1, a2, …, ak, ak+1, …, am}; B = {b1, b2, …, bk, bk+1,…, bn}
Vì AB = {a1, a2, …, ak, ak+1, …, am, bk+1,…, bn} nên:
|AB| = m + (n – k) = m + n – k = |A| + |B| – |AB|
1.Do A = (A\B) (AB) mà (A\B) (AB) = nên theo (1) ta có:
|A| = |A\B| + |AB| |A\B| = |A| – |AB|
2.Vì (A\B)(B\A) = nên áp dụng (1) và sau đó áp dụng (2) ta có:
|AB| = |(A\B)(B\A)| = |A\B| + |B\A|
= |A| – |AB| + |B| – |BA|
= |A| + |B| – 2|AB|
Lưu ý theo tính chất (2) nếu BA thì |A\B| = |A| – |B|
Các tập hợp A1, A2,…, An gọi là đôi một rời nhau nếu 2 tập bất kỳ trong chúng đều
rời nhau, tức là AiAj = . Với ij.
Theo định lý 1, nếu A1A2 = thì |A1A2|= |A1| + |A2|
Áp dụng tính chất (1) (n-1) lần, ta có:
Định lý 2: Cho A1, A2,…, An là các tập đôi một rời nhau. Khi đó,
|A1A2… An| = |A1| + |A2| + …+ |An|
Định lý 3: Với tập hợp A, B ta có: |AB| = |A|.|B|
Chứng minh:
Giả sử A = {a1, a2, …, am} |A| = m B = {b1, b2, …, bn} |B| = n Với ai, ta có:
m
| {ai} B| = n vì AB = ({ai } B) và các tập {a1} B; {a2} B; …; {am} B
i 1
đôi một rời nhau nên theo định lý 2 ta có:
|AB| = |{a1} B| + |{a2} B| + … + |{am}B | = m n = |A|.|B|
Định lý 4: Cho A1, A2,…, An là các tập hợp bất kỳ. Khi đó
|A1A2… An| = |A1| |A2| … |An|
1.2.Quan Hệ
1.2.1 Khái niệm về quan hệ
Trong thực tế, ta thường gặp mối quan hệ giữa các phần tử của tập hợp này với các
phần tử của tập hợp khác, hoặc ngay trong cùng một tập hợp.
Nếu gọi A là tập các đối tượng (phần tử) mà ta đang xét thì mỗi nhóm gồm m phần
tử có quan hệ với nhau là một phần tử của Am A
A
A . Các nhóm gồm m phần tử
m
như vậy tạo thành một tập con của Am. Ta có các định nghĩa:
a. Quan hệ 2 ngôi: Một quan hệ 2-ngôi từ tập A đến tập B là tập con của tích đề các A
x B. Nếu R là một quan hệ 2-ngôi từ A đến B thì R {(a,b) a A, b B } .
Nếu (a, b) R hay aRb thì ta nói a,b có R-quan hệ với nhau. Nếu (a, b) R thì ta
nói a,b không có R-quan hệ với nhau. Trong trường hợp A=B thì quan hệ R được gọi là
quan hệ 2 ngôi trên chính tập A. Quan hệ 2-ngôi được gọi tắt là quan hệ.
4
- b. Tương tự ta có khái niệm về quan hệ m-ngôi: Một quan hệ m-ngôi trên tập hợp A là
tập con của tích đề các Am. Nếu R là một quan hệ m-ngôi trên A thì khi (a1, a2, …, am)
R ta nói a1, a2, …, am có R-quan hệ với nhau.
Ví dụ: Cho A: Tập các nước; B: Tập các thủ đô
R A B = {(a, b) | nếu a có thủ đô là b}
Ta có: (Việt Nam, Hà nội) R; (Lào, Viêng chăn) R
(Thái Lan, Băng cốc) R; (Singapo, Hà nội) R
Ví dụ 2: A: Tập các cán bộ trong khoa CNTT
R = {(a, b) | a, b A và a, b có cùng tuổi} A A
R là một quan hệ trên A.
1.2.2 Tính chất của quan hệ
Cho quan hệ R trên A. Nếu (x,y)R thì ta nói x có R quan hệ với y (x có quan hệ với y)
viết là : xRy hay (x, y) R.
Nếu (x, y) R thì hiểu là x không có quan hệ với y. Quan hệ R trên tập A có các tính chất
sau:
i.Tính chất phản xạ nếu với xA ta có xRx
ii.Tính chất đối xứng nếu: vớix, yA: xRy thì yRx.
iii.Tính chất phản đối xứng nếu : vớix, yA: xRy yRx thì x=y.
iv.Tính chất bắc cầu nếu: vớix, y, zA: xRy yRx thì xRz.
Ví dụ 1 : + Xét trong tập số tự nhiên N: Quan hệ xRy nếu x y là quan hệ có tính chất
phản xạ, phản đối xứng, bắc cầu.
+ Xét tập các tam giác, quan hệ R: đồng dạng, có tính chất phản xạ, đối xứng,
bắc cầu.
Ví dụ 2: Cho tập A={1, 2, 3, 4} Quan hệ R trên tập hợp A được định nghĩa
a, bA :aRb a+b =2k kZ, khi đó:
1. R có tính chất phản xạ: aA ta có a+a=2a aRa hay (a,a)R
2. R có tính chất đối xứng: a, bA và a+b=2k thì cũng có b+a=2k hay nếu có aRb thì
cũng có bRa
3. R có tính chất bắc cầu : a, b,c A nếu a+b=2k, b+c=2k’
thì a+c=(2k-b)+(2k’-b)= 2k+2k’-2b=2k’’ hay (a,c)R
1.2.3 Quan hệ tương đương
a.Định nghĩa
Một quan hệ R trên tập A gọi là quan hệ tương đương nếu R có các tính chất phản
xạ, đối xứng, và bắc cầu.
Nếu R là quan hệ tương đương thì thay cho cách viết xRy ta viết xy (x tương
đương y). Vậy là một quan hệ tương đương trên A nếu với x, y, zA ta có:
xx (tính phản xạ)
xy yx (tính đối xứng)
xy yz xz (tính bắc cầu)
b. Ví dụ : Cho tập A={1, 2, 3, 4, 5, 6, 7} Quan hệ R trên tập hợp A được định nghĩa
a, bA :aRb a-b =3k kZ, khi đó R là quan hệ tương đương, thực vậy:
1. R có tính chất phản xạ: aA ta có a-a=0=3.0 aRa hay (a,a)R
2. R có tính chất đối xứng: a, bA và a-b=3k b-a=3(-k)=3k’ bRa
5
- 3. R có tính chất bắc cầu : a, b,c A nếu a-b=3k, b-c=3k’
thì a-c= 3k+b+3k’-b=3(k+k’)=3k’’ hay (a,c)R
c.Lớp tương đương
Cho A là một tập và R là một quan hệ tương đương trên A. Với xA, tập
xR x y x | yRx gọi là lớp tương đương chứa x.
Định lý 1: Các lớp tương đương là , hoặc bằng nhau, hoặc rời nhau.
Chứng minh: Xét lớp tương đương bất kỳ [x]:
Vì xRx nên x [x] [x] .
Để chứng minh phần còn lại ta giả sử 2 lớp x và y có
x y = ta chỉ cần chứng minh x = y .
Chọn z x y vì z x nên xRz, vì z y nên zRy.
t x tRx tRy t y . Vậy x = y .
Từ định lý ta có:
y x x y và xRy x y
Các lớp tương đương chia A thành các tập con rời nhau (các phân hoạch tập A).
Tập hợp mà mỗi phần tử là 1 lớp tương đương của tập A theo quan hệ tương đương R
() gọi là tập thương của A theo quan hệ R (). Ký hiệu là X/R X/.
Vậy X/R = {[x] | x X}.
Ví dụ:
Trên tập Z các số nguyên xét quan hệ aRb nếu a – b 3. Ta có R là một quan hệ tương
đương trên Z. Thật vậy: x, y, z Z:
a/x – x = 0 3 aRa suy ra R có tính chất phản xạ.
b/xRy x – y 3 –(y – x) 3 hay yRx suy ra R có tính chất đối xứng.
c/ xRy x – y 3 và yRz x – y 3 (x – z) 3 suy ra R có tính chất bắc cầu.
Ta xét các lớp tương đương theo quan hệ này ta có xRy x – y 3 x và y chia
cho 3 có cùng số dư. Khi chia cho 3 số dư có thể là 0, 1, 2. Do đó ta có các lớp tương
đương đúng là:
0R 3k | k Z các số chia hết cho 3
1R 3k 1 | k Z các số chia cho 3 dư 1
2R 3k 2 | k Z các số chia cho 3 dư 2
Vậy Z = 0R , 1R , 2R
Quan hệ tương đương trên gọi là quan hệ đồng dư theo modul 3, ký hiệu là ab (mod 3).
1.2.4 Quan hệ thứ tự
a. Định nghĩa quan hệ thứ tự
Một quan hệ R trên tập A gọi là quan hệ thứ tự nếu R có các tính chất phản xạ, phản
đối xứng và bắc cầu.
Nếu R là quan hệ thứ tự trên A thì thay cho cách viết xRy ta viết xy (x nhỏ hơn
hay bằng y). Vậy là một quan hệ thứ tự trên A nếu với x, y, z A, ta có:
1.x x (tính phản xạ)
2.x y y x thì x = y (tính phản đối xứng)
3.x y y z thì x z (tính bắc cầu)
Ký hiệu x < y có nghĩa là x y và x y: đọc là x nhỏ hơn y.
Tập A cùng với một quan hệ thứ tự trên nó gọi là tập được sắp thứ tự, khi đó ký
hiệu là (A, ).
6
- Ví dụ 1: Trong N, Z, Q, R quan hệ thông thường là quan hệ thứ tự.
Ví dụ 2: Quan hệ bao hàm ( ) trong tập P(A) = 2A ( tập các tập con của tập A) là quan
hệ thứ tự.
Thật vậy:
1. X P(A): A A có tính chất phản xạ.
2. X, Y P(A): A B B A A = B nên có tính chất phản đối xứng.
3. X, Y, Z P(A): A B B C A C nên có tính chất bắc cầu.
b. Quan hệ thứ tự toàn phần và bộ phận
Cho A là một tập hợp được sắp thứ tự. Nếu với x, y A ta có x y hoặc y x thì
ta nói x và y so sánh được với nhau. Nếu mọi x, y A đều so sánh được với nhau thì ta
nói A là tập sắp thứ tự toàn phần (sắp thứ tự tuyến tính). Trong trường hợp ngược lại, nói
rằng A là tập sắp thứ tự bộ phận.
Ví dụ :
Quan hệ thông thường trên N, Z, Q, R là quan hệ thứ tự toàn phần.
Quan hệ “chia hết” trong N* là quan hệ thứ tự bộ phận (2 và 3 không so sánh được với
nhau).
c.Phần tử lớn nhất, nhỏ nhất, tối đại và tối thiểu
Cho A là một tập được sắp thứ tự:
Phần tử a A gọi là phần tử lớn nhất (nhỏ nhất) nếu với x A đều có x a (a x).
Phần tử a A gọi là phần tử tối đại (tối thiểu) nếu với x A đều có a x a = x ( x
a kéo theo x = a).
Ví dụ : Trong tập N với quan hệ ta có 0 là phần tử nhỏ nhất; 0 là phần tử tối thiểu.
Không có phần tử lớn nhất, phần tử tối đại.
Trong tập P(A) với quan hệ có là phần tử nhỏ nhất, A là phần tử lớn nhất.
1.3.Logic mệnh đề
1.3.1.Khái niệm mệnh đề và giá trị chân lý
Một mệnh đề là một câu đúng hoặc sai, không thể vừa đúng vừa sai. Giá trị đúng
hoặc sai của một mệnh đề được gọi là giá trị chân lý của mệnh đề.
Về ký hiệu, ta thường dùng các chữ cái như p, q, r… để ký hiệu cho các biến nhận
giá trị đúng hoặc sai. Giá trị chân lý “đúng – true” thường được viết là 1 hoặc T và giá trị
chân lý “sai – false” được viết là 0 hoặc F.
Ví dụ 1: Các phát biểu sau đây là các mệnh đề
1. 6 là một số nguyên tố
2. 5 là số lẻ
3. 4
- Mệnh đề có hai loại:
(1)Mệnh đề sơ cấp (elementary): mệnh đề sơ cấp là các “nguyên tử” theo nghĩa là
nó không thể phân tích được thành một hay nhiều (từ 2 trở lên) mệnh đề thành phần đơn
giản hơn.
(2) Mệnh đề phức hợp (compound): mệnh đề phức hợp là mệnh đề được tạo thành
từ một hay nhiều mệnh đề khác bằng cách sử dụng các liên kết logic như từ “không”
dùng trong việc phủ định một mệnh đề, các từ nối: “và”, “hay”, “hoặc”, “suy ra”, vv …
Ví dụ : xét các mệnh đề sau:
p: “15 chia hết cho 3” ; q: “2 là một số nguyên tố và là một số lẻ”
Ta có: p là mệnh đề sơ cấp, q là mệnh đề phức hợp, vì q được tạo thành từ 2 mệnh đề:
p1 : “2 là một số nguyên tố” ; P2: “2 là một số lẻ” nhờ vào liên kết logic “và”.
1.3.2.Các phép toán mệnh đề
Khi có các mệnh đề phức hợp theo các mệnh đề sơ cấp thì việc tính toán giá trị chân
lý sẽ được thực hiện như thế nào? Để trả lời được cần có các phép toán logic, các phép
toán logic ở đây là các ký hiệu được dùng thay cho các từ liên kết logic như từ “không”,
“và”, “hay”, “hoặc”, “suy ra”, “nếu … thì …”, “nếu và chỉ nếu…”
Các phép toán logic được định nghĩa bằng bảng giá trị chân lý (truth table).
a.Phép phủ định
Ký hiệu là:
Giả sử p là một mệnh đề, phủ định của p được ký hiệu là p hay p . Bảng giá trị
chân lý của phép phủ định được cho bởi bảng:
p p
0 1
1 0
Ví dụ 1: Cho mệnh đề p: 5
- Ví dụ 1: Cho các mệnh đề
p: “5>2” ; q: “6 là số nguyên tố”
r: “Một tam giác đều cũng là tam giác cân”
Giá trị chân lý của p, q, r là 1, 0, 1. Khi đó ta có:
pq = 0; pr = 1
qr = 0;
Ví dụ 2: Bằng cách lập bảng giá trị chân lý ta có:
1.Các mệnh đề p và pp luôn có cùng giá trị chân lý.
2.Mệnh đề p p luôn có giá trị chân lý bằng 0 (tức là một mệnh đề luôn sai)
c.Phép tuyển
Cho p, q là 2 mệnh đề. Ta ký hiệu mệnh đề p hoặc q (p hay q) là pq. Phép tuyển
hay phép hoặc được định nghĩa bởi bảng chân lý sau:
p q pq
0 0 0
0 1 1
1 0 1
1 1 1
Ví dụ 1: Với các mệnh đề p, q, r đã cho ta có:
pq = 1; pr = 1
Ví dụ 2: Lập bảng giá trị chân lý ta luôn có mệnh đề p p là luôn đúng.
Nhận xét:
Một mệnh đề phức hợp mà luôn đúng bất kể các giá trị chân lý của các mệnh dề thành
phần của nó được gọi là hằng đúng.
Một mệnh đề mà luôn luôn sai được gọi là mâu thuẫn.
Một mệnh đề không phải hằng đúng, cũng không phải mâu thuẫn được gọi là tiếp liên
Ví dụ 3 : p p là luôn đúng nó là hằng đúng.
p p là luôn luôn sai nó là mâu thuẫn.
Phép loại trừ ký hiệu là XOR. p XOR q được định nghĩa bởi bảng chân lý sau:
p q p XOR q
0 0 0
0 1 1
1 0 1
1 1 0
p XOR q đúng khi trong 2 mệnh đề p và q có một mệnh đề đúng, một mệnh đề sai.
d.Phép kéo theo, ký hiệu là
Cho p và q là 2 mệnh đề. Mệnh đề p kéo theo q ký hiệu là p q dùng để diễn đạt
phát biểu: nếu p thì q và được định nghĩa bởi bảng chân lý sau:
p q pq
0 0 1
0 1 1
1 0 0
1 1 1
9
- Ví dụ : với nN, ta xét mệnhđề:
p: n chia hết cho 5
q: n chia hết cho 9
Lúc đó mệnh đề p q có giá trị xác định cụ thể:
n = 45 p: 1 q: 1 p q: 1
n = 15 p: 1 q: 0 p q: 0
n = 16 p: 0 q: 0 p q: 1
Xét mệnh đề p q (1). Khi đó các mệnh đề sau đây gọi là các mệnh đề liên kết với (1)
q p (2)
p q (3)
q p (4)
Mệnh đề (1) được gọi là mệnh đề thuận
Mệnh đề (2) được gọi là mệnh đề đảo
Mệnh đề (3) được gọi là mệnh đề phản
Mệnh đề (4) được gọi là mệnh đề phản đảo
Các mệnh đề liên kết chia thành 2 cặp tương đương:
i/ p q q p
ii/ q p p q
với mệnh đề (1): Nếu có p thì có q do đó còn nói: p là điều kiện đủ để có q.
Mệnh đề (1) tương đương mệnh đề (4) nghĩa là không q thì không p, do đó có thể
nói: q là điều kiện cần để có p.
e.Phép kéo theo hai chiều (phép tương đương). Ký hiệu là
Cho p, q là 2 mệnhđề. Mệnh đề p tương đương q dùng để diễn đạt phát biểu: p nếu
và chỉ nếu q và được định nghĩa bởi bảng giá trị chân lý sau:
P q pq
0 0 1
0 1 0
1 0 0
1 1 1
Mệnh đề p q được đọc là: p nếu và chỉ nếu q hay còn được phát biểu dưới các
dạng khác:
p khi và chỉ khi q
p là điều kiện cần và đủ cho q
Độ ưu tiên của các toán tử logic
1.
2. ,
3. ,
Trong đó các toán tử liệt kê trên cùng dòng có cùng độ ưu tiên.
Ví dụ :
1. x y có nghĩa là x y
2. x y p q có nghĩa x y p q
1.3.3.Biểu thức logic (công thức logic)
Trong đại số ta có các biểu thức số học được xây dựng từ các hằng số, các biến số
và các phép toán số học. Khi thay thế các biến trong một biểu thức số học bởi các hằng số
10
- thì kết quả thực hiện các phép toán trong biểu thức là một hằng số. Trong đại số mệnh đề
ta có biểu thức logic cũng được xây dựng như sau:
a.Định nghĩa: Các mệnh đề chưa xác định p, q, r… gọi là các biến mệnh đề.
1.Các biến mệnh đề là các biểu thức
2.Nếu P, Q là các (công thức) biểu thức logic thì P , P Q , P Q , P Q , P Q là
các (công thức) biểu thức.
3.Mọi ký hiệu khác không được xác định theo 2 qui tắc 1, 2 đều không là các biểu thức.
Ví dụ: p(x, y, z) = x p q r là một biểu thức logic với các biến mệnh đề x, p, q, r.
b.Sự tương đương logic
Hai biểu thức logic E và F theo bộ biến mệnh đề nào đó được gọi là tương đương
logic khi E và F luôn có cùng giá trị chân lý trong mọi trường hợp giá trị chân lý của bộ
biến mệnh đề.
Khi đó ta viết E F hay E F và đọc là “E tương đương với F”. Như vậy, để
chứng minh 2 biểu thức logic là tương đương logic thì có thể lập bảng giá trị chân lý.
Ví dụ: Chứng minh p q r p r q r
Giải: ta lập bảng giá trị chân lý như sau:
p q r pq pr qr pq r p r q r
0 0 0 0 1 1 1 1
0 0 1 0 1 1 1 1
0 1 0 1 1 0 0 0
0 1 1 1 1 1 1 1
1 0 0 1 0 1 0 0
1 0 1 1 1 1 1 1
1 1 0 1 0 0 0 0
1 1 1 1 1 1 1 1
Nhìn vào giá trị chân lý trên 2 cột cuối ta thấy:
p q r p r q r
c.Phép biến đổi công thức (biểu thức):
Để biến đổi biểu thức một cách thuận tiện, ta qui ước các điều sau:
1.Không viết dấu ngoặc ngoài cùng đối với mỗi công thức (biểu thức).
2.Thay ký hiện bởi dấu . hoặc bỏ đi.
3.Các phép toán được thực hiện theo thứ tự: , , ,
4.Nếu có dấu phủ định trên một biểu thức thì bỏ dấu ngoặc hai đầu biểu thức đó.
Ví dụ :
( p q r ) được viết là p q r
p q r được viết là p q r
d.Các luật của logic mệnh đề
Biểu thức logic A gọi là hằng đúng nếu A nhận giá trị 1 với mọi hệ giá trị chân lý của bộ
biến mệnh đề có mặt trong A.
Biểu thức logic A gọi là hằng sai nếu A nhận giá trị 0 với mọi hệ giá trị chân lý của bộ
biến mệnh đề có mặt trong A.
Khi A là hằng đúng thì ta gọi A là một luật, ký hiện là = A. Khi A là hằng sai thì ta gọi
A là một mâu thuẫn.
Ví dụ : p p 1 nên ta có một luật = p p . Luật = p p gọi là luật bài trung: Trong
hai mệnh đề phủ định lẫn nhau, có ít nhất một mệnh đề đúng.
11
- Các luật logic cơ bản
1. Luật phủ định kép: p p
2. Luật giao hoán: p q q p , p q q p
3. Luật kết hợp: p (q r ) p q r , p (q r ) p q r
4. Luật phân phối:
p (q r ) p q q r , p (q r ) p q q r
5. Luật Demorgan: p q p q , p q p q
6. Luật về mối liên hệ giữa p với chính nó, với p , với 0 và 1:
p p p p p p
p0 0 p0 p
p 1 p p 1 1
p p 0 p p 1
7. Luật kéo theo: p q p q
8. Luật tương đương: p q p q q p
Nhận xét: Có thể dùng các luật logic để biến đổi tương đương các biểu thức logic, hay
nói cách khác, để chứng minh 2 biểu thức logic tương đương ta có thể dùng phương pháp
biến đổi logic.
Ví dụ: Chứng minh p q r p r q r
Ta biến đổi vế trái về vế phải như sau:
Vế trái p q r ( p q) r ( p r ) (q r ) ( p r ) (q r ) Vế phải
1.3.4.Các dạng chính tắc
a.Dạng chính tắc tuyển
Giả sử p1, p2, …, pn là các biến mệnh đề. Một biểu thức logic F theo các biến mệnh
đề p1, p2, …, pn được gọi là một biểu thức hội cơ bản nếu nó có dạng sau:
F = q1 q2 … qn với qi = pi hoặc qi pi (i = 1… n).
Ví dụ: Biểu thức xyz hoặc x y z hoặc x y z là các biểu thức hội cơ bản theo 3
biến mệnh đề x, y, z.
Biểu thức E (p1, p2, …, pn) theo các biến mệnh đề p1, p2, …, pn được gọi là có dạng
chính tắc tuyển khi E có dạng: E = E1 E2 … Em. Trong đó mỗi biểu thức Ei đều có
dạng là một biểu thức hội cơ bản theo các biến mệnh đề p1, p2, …, pn.
Ví dụ : Các biểu thức sau đây có dạnh chính tắc tuyển.
Ex, y, z x y z x y z x y z
F p1 , p 2 , p3 , p 4 p1 p 2 p3 p 4 p1 p 2 p3 p 4 p1 p 2 p3 p 4
Định lý: Mọi biểu thức logic F(p1, p2, …, pn) đều có thể viết dưới dạng chính tắc tuyển
duy nhất (không kể sự sai khác về thứ tự trước sau của các biểu thức hội cơ bản trong
phép tuyển).
Nói cách khác, ta có duy nhất một tập hợp các biểu thức hội cơ bản {E1, E2, …, Em}
sao cho biểu thức E (p1, p2, …, pm) E1 E2 … Em.
Ví dụ : Tìm dạng chính tắc tuyển của biểu thức:
E x, y , z x z x y
Ex, y, z x z x y x z x x z y
x z x y z
12
-
x y y z x yz
x y z x y z x y z
x y z x y z
b. Dạng chính tắc hội
Giả sử p1, p2, …, pn là các biến mệnh đề. Một biểu thức logic F theo các biến mệnh
đề p1, p2, …, pn được gọi là một biểu thức tuyển cơ bản nếu nó có dạng sau:
F = q1 q2 … qn với qi = pi hoặc qi pi (i = 1… n).
Ví dụ: Biểu thức x y z hoặc x y z hoặc x y z là các biểu thức tuyển cơ bản theo
3 biến mệnh đề x, y, z.
Biểu thức E (p1, p2, …, pn) theo các biến mệnh đề p1, p2, …, pn được gọi là có dạng
chính tắc hội khi E có dạng: E = E1 E2 … Em. Trong đó mỗi biểu thức Ei đều có
dạng là một biểu thức tuyển cơ bản theo các biến mệnh đề p1, p2, …, pn.
Ví dụ : Các biểu thức sau đây có dạng chính tắc hội.
Ex, y, z x y z x y z x y z
F p1 , p 2 , p3 , p 4 p1 p 2 p3 p 4 p1 p 2 p3 p 4 p1 p 2 p3 p 4
Định lý: Mọi biểu thức logic F(p1, p2, …, pn) đều có thể viết dưới dạng chính tắc hội duy
nhất (không kể sự sai khác về thứ tự trước sau của các biểu thức tuyển cơ bản trong phép
hội).
Nói cách khác, ta có duy nhất một tập hợp các biểu thức tuyển cơ bản {E1, E2, …,
Em} sao cho biểu thức E (p1, p2, …, pm) E1 E2 … Em.
Ví dụ 1: Tìm chính tắc hội của biểu thức sau:
E x, y, z , t x y y z z t
Ex, y, z, t x y z z t t x x y z t t x x y y z t
x y z t x y z t x y z t x y z t x y z t x y z t
x y z t x y z t x y z t x y z t x y z t x y z t
x y z t x y z t x y z t x y z t x y z t x y z t
x y z t x y z t
Ví dụ 2: Tìm chính tắc tuyển của biểu thức:
x y z y
x y z y
x y z x y y
x z y z xy y y
x z y z xy
x y y z x x y z xy z z
xy z x y z x y z x y z xyz xy z
x y z x y z x y z x yz
1.3.5.Vị từ, lượng từ
a.Vị từ (Hàm mệnh đề)
P(x) là một hàm mệnh đề (một biến) xác định trên tập X nếu với mỗi xX thì P(x)
là một mệnh đề. Hàm mệnh đề một biến còn được gọi là vị từ 1-ngôi.
13
- Nếu P(x) là một hàm mệnh đề xác định trên X thì x được gọi là biến tử, một phần
tử cụ thể aX gọi là hằng tử, P(a) là một hàm mệnh đề hoàn toàn xác định.
Tương tự ta có hàm mệnh đề m biến, hay vị từ m-ngôi với mN*
b.Miền đúng của hàm mệnh đề
Giả sử P(x) là một hàm mệnh đề trên X, khi đó miền đúng của P(x) là tập
EP(x)={ aX P(a) là mệnh đề đúng}
Ví dụ:
1. P(x): x2-6x+5=0 với x R có EP(x)={ 1,5}
2. P(x): x2-6x+50 với x R có EP(x)= (,1) (5,)
Hàm mệnh đề P(x) xác định trên X gọi là hằng đúng nếu EP(x)=X, gọi là hằng sai
nếu EP(x)=, gọi là thực hiện được nếu EP(x)
Ví dụ:
1. P(x): x2+1>0 là hằng đúng trên R
2. P(x): x2+1=0 là hằng sai trên R
3. P(x): 3x-4=0 là thực hiện được trên R nhưng không thực hiện được trên N
Hai hàm mệnh đề P(x) và Q(x) cùng xác định trên tập X được gọi là tương đương
logic, kí hiệu là P( x) Q( x) hoặc P( x) Q( x) khi và chỉ khi EP(x)= EQ(x)
c.Phép toán trên các hàm mệnh đề
Phép phủ định
Cho P(x) là một hàm mệnh đề xác định trên X, ta gọi phủ định của P(x) là
hàm mệnh đề P( x) xác định trên X, nhận giá trị 1 trên tập các phần tử
a X , P(a) 0 , nhận giá trị 0 trên miền đúng của P(x)
Ta có: E P ( x ) X \ E P ( x )
EP( x)
EP(x)
Phép hội
Cho 2 hàm mệnh đề P(x), Q(x) cùng xác định trên X, hội của P(x) và Q(x) là hàm
mệnh đề P(x) Q(x) xác định trên X, nhận giá trị 1 trên tập các phần tử aX sao cho
P(a) 1 Q(a) 1 , nhận giá trị 0 trong các trường hợp còn lại.
Ta có: EP ( x )Q( x ) EP( x ) EQ( x)
14
- Phép tuyển
Cho 2 hàm mệnh đề P(x), Q(x) cùng xác định trên X, tuyển của P(x) và Q(x) là
hàm mệnh đề P(x) Q(x) xác định trên X, nhận giá trị 0 trên tập các phần tử aX sao
cho P(a) 0 Q(a) 0 , nhận giá trị 1 trong các trường hợp còn lại.
Ta có: EP ( x )Q( x) EP ( x ) EQ( x)
Phép kéo theo
Cho 2 hàm mệnh đề P(x), Q(x) cùng xác định trên X, ta gọi P(x) kéo theo Q(x) là hàm
mệnh đề P(x) Q(x) xác định trên X, nhận giá trị 0 trên tập các phần tử aX sao cho
P(a) 1 Q(a) 0 , nhận giá trị 1 trong các trường hợp còn lại.
Ta có: EP( x)Q( x) ( X \ EP( x) ) EQ( x)
Phép tương đương
Cho 2 hàm mệnh đề P(x), Q(x) cùng xác định trên X, ta gọi P(x) tương đương Q(x) là
hàm mệnh đề P(x) Q(x) xác định trên X, nhận giá trị 1 trên tập các phần tử aX
sao cho P(a) Q(a) , nhận giá trị 0 trong các trường hợp còn lại.
Ta có: EP( x)Q( x) ( X \ ( EP( x) EQ( x) )) ( EP( x) EQ( x) )
d. Lượng từ
Cho P(x) là hàm mệnh đề xác định trên X.
Ta gọi xX P(x) hiểu là Với mọi xX, P(x) là mệnh đề đúng nếu EP(x)=X, sai trong
các trường hợp khác.
Ta gọi xX P(x) hiểu là tồn tại xX, P(x) là mệnh đề đúng nếu EP(x), sai trong
các trường hợp khác.
Ký hiệu gọi là lượng từ phổ dụng (với mọi), ký hiệu gọi là lượng từ tồn tại
Như vậy: xX P(x) đúng P(x) hằng đúng trên X
xX P(x) đúng P(x) thực hiện được trên X
Ví dụ: 1. x R ( x 2 1 0) là mệnh đề đúng
2. x R (3x 1 0) là mệnh đề sai
3. x R (3x 1 0) là mệnh đề đúng
4. x N (3x 1 0) là mệnh đề sai
e. Lượng từ trên các hàm mệnh đề nhiều biến
Cho hàm mệnh đề 2 biến Px,y) xác định trên X x Y. Khi đó với mỗi y cố định
xX P(x,y), xX P(x,y) là các mệnh đề, do đó ta được các hàm mệnh đề
xX P(x,y), xX P(x,y) xác định theo yY. Ta có thể áp dụng các lượng từ
với mọi và tồn tại lên các hàm mệnh đề này để được các mệnh đề xác định:
xX yY P(x,y), xX yY P(x,y) , xX yY P(x,y) , xX yY
P(x,y)
f. Mối liên hệ giữa 2 mệnh đề phổ dụng và tồn tại
Cho P(x) là hàm mệnh đề xác định trên X, khi đó ta có:
1. x XP(x) x X P( x) ; 2. x XP(x) x X P( x)
1.4 Suy luận toán học & các phương pháp chứng minh
1.4.1 Qui tắc suy luận
Giả sử A1, A2, ..., An, B là các biểu thức logic. Ta nói B là hệ quả logic của
A1, A2, ..., An nếu với mọi bộ giá trị chân lý có thể nhận của bộ biến mệnh đề có mặt trong
trong các biểu thức đó mà A1, A2, ..., An đồng thời nhận giá trị 1 đều có B nhận giá trị 1.
15
- Khi B là hệ quả logic của A1, A2, ..., An thì nói rằng có một qui tắc suy luận từ các tiên
đề A1, A2, ..., An tới hệ quả logic B.
A1 , A2 ,..., An
Qui tắc suy luận trên được kí hiệu là: hay A1, A2, ..., An = B
B
Ta có A1, A2, ..., An đồng thời nhận giá trị 1 khi và chỉ khi A1 A2 ... An nhận giá trị 1
Khi đó A1 A2 ... An B đúng A1 A2 ... An nhận giá 1 thì B cũng nhận giá trị 1
A1 , A2 ,..., An
Hay có qui tắc suy luận có luật A1 A2 ... An B
B
A , A ,..., An
Như vậy để chứng minh qui tắc suy luận 1 2 ta có thể dùng một trong 2 phương
B
pháp sau:
1. Lập bảng giá trị chân lý, xét theo đúng định nghĩa
2. Chỉ ra mệnh đề A1 A2 ... An B là hằng đúng.
p, p q
Ví dụ 1: Chứng minh qui tắc suy luận
q
Cách 1: Lập bảng giá trị chân lý
p q pq
0 0 1
0 1 1
1 0 0
1 1 1
Nhìn vào bảng giá trị chân lý ta thấy có một bộ giá trị của p,q làm cho p,q nhận giá trị 1
p, p q
thì p q cũng nhận giá trị 1, do đó theo định nghĩa ta có qui tắc suy luận
q
p, p q
Cách 2: Để chứng minh qui tắc suy luận ta cần chứng minh
q
( p ( p q)) q 1( hằng đúng)
Thực vậy: ( p ( p q)) q p ( p q) q ( p p) ( p q) q
p q q p q q 1 (ĐPCM)
p q, q r
Ví dụ 2: Chứng minh qui tắc suy luận
pr
Cách 1: Lập bảng giá trị chân lý
p q r pq qr pr
0 0 0 1 1 1
0 0 1 1 1 1
0 1 0 1 0 1
0 1 1 1 1 1
1 0 0 0 1 0
1 0 1 0 1 1
16
- 1 1 0 1 0 0
1 1 1 1 1 1
Nhìn vào bảng giá trị chân lý ta thấy có 4 bộ giá trị của p,q, r làm cho pq và qr đồng
thời nhận giá trị 1 thì p r cũng nhận giá trị 1, do đó theo định nghĩa ta có qui tắc suy
p q, q r
luận
pr
p q, q r
Cách 2: Để chứng minh qui tắc suy luận ta cần chứng minh
pr
(( p q) (q r )) ( p r ) 1 ( hằng đúng)
Thực vậy:
(( p q) (q r )) ( p r ) ( p q) (q r ) p r ( p q) p (q r ) r
q q p r 1 p r 1 (ĐPCM)
1.4.2 Các qui tắc suy luận cơ bản
Trong suy luận toán học người ta thường dùng 28 qui tắc suy luận cơ bản sau, các qui tắc
này đã được chứng minh theo 2 phương pháp trên. 2 ví dụ vừa xét là qui tắc suy luận số1
và qui tắc số 3.
p q, p p q, q
1. 2.
q p
p q, q r p q, q r
3. 4.
pr pr
p q, q p p q, p
5. 6.
pq q
p r, q r p q, p r
7. 8.
pq r pqr
p q, r s p q, r s
9. 10.
pr qs pr qs
p q, r s p q, r s
11. 12.
pr qs pr qs
p, q pq
13. 14.
pq p
p p p
15. 16. ;
pq p p
pq q p pq
17. ; 18.
q p pq pq
pqr p q r pqr
19. 20.
p q r pqr pr
17
