Bài viết này mình tổng hợp lại đề thi toán rời rạc 1 được chia sẻ tại Diễn Đàn Sinh Viên PTIT
Đề thi Đại Học D13CN:
Đề thi cao đẳng C13CN:
Đề thi kỳ hè 2014:
Ngoài các đề thi các năm trên, các bạn có thể xem thêm ngân hàng đề thi Toán rời rạc 1 để luyện tập thêm nhé 😀 Các đề thi trên do mình tổng hợp lại, nếu có sai sót gì các bạn có thể comment bên dưới cho mình biết và cập nhật lại nhé. Ngoài ra, nếu bạn có thêm đề thi khác của Toán rời rạc 1, hãy gửi email cho mình về địa chỉ [email protected] để chia sẻ cho mọi người nhé!
TRƯỜNG ĐẠI HỌC CẦN THƠ KHOA CTTT&TT
Đề thi môn TOÁN RỜI RẠC 1 - TH466 Lần 1 - Học kỳ 2 - Năm học 06-07 Lớp ĐT-TH K32 Thời gian làm bài 60 phút NỘI DUNG I- Tập hợp X cùng với quan hệ R là một tập hợp thứ tự. Trên X người ta định nghĩa thêm một quan hệ S như sau : ∀ x, y ∈ X : x S y ⇔ y R x S có phải là quan hệ thứ tự hay không ? . Chứng minh.
II- Chứng minh rằng trong một đại số bool mỗi phần tử có duy nhất một phần tử bù.
III- Hãy tìm tất cả các hàm bool 2 biến f thỏa tính chất sau : ]ba[f]ab[f:Bab 2 \=∈∀
IV- Cho hàm bool 4 biến f có sơ đồ Karnaugh như sau :
f3 = 0011 0.5 f5 = 0101 0.5 f10 = 1010 0.5 III 2.0đ f12 = 1100 0.5 Dạng tuyển chuẩn tắc. ]dcba,dcba,cdba,bcda,dbca,dcab,dcab,abcd,dabc,dcba,dcba,cdba[L = 1.0 Với biến a ]dcb,dcb,cdb,bcd,dbc,dcab,dcab[L = 0.5 Với biến b ]dca,dca,dcb,dcb,dbc,cd[L =
0.5 Với biến c ]dab,dca,dcb,dbc,ad,db,cd[L = 0.5 IV 3.0đ Với biến d ]ab,ca,cb,bc,ad,db,cd[L = Đây là danh sách các nguyên nhân nguyên tố 0.5
Toán rời rạc, Đề thi phần đại số
Posted by nguyenchiphuong ⋅ 02/01/2013 ⋅ Nhập mật khẩu để xem bình luận.
Filed Under Bài giảng, Cần Thơ, Nguyễn Hữu Khánh, Rời rạc, Đề thi, đại số
Đây là nội dung riêng tư. Cần phải nhập mật khẩu để xem tiếp:
Mật khẩu:
About nguyenchiphuong
Thạc sĩ Toán Khoa Học
View all posts by nguyenchiphuong »
« Đề thi môn Tôpô đại cương – Cao học Cần Thơ K18
Tài liệu lý thuyết môn Giải tích thực – Cao học Cần Thơ »
Bài viết này đã được bảo vệ bằng mật khẩu. Bạn vui lòng nhập mật khẩu để xem bài viết và lời bình.
TRƯỜNG ĐẠI HỌC CẦN THƠ KHOA CNTT & TRUYỀN THÔNG BỘ MÔN KHOA HỌC MÁY TÍNH
1
TOÁN RỜI RẠC [DISCRETE MATHEMATICS] 08/2013
GV: Trần Nguyễn Minh Thư []
2
CƠ SỞ LOGIC
3
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ
7/17/2016
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ
Định nghĩa: Mệnh đề là một câu khẳng định có giá trị chân lý xác định
đúng [True] hoặc sai [False]. Ví dụ:
True
2+3=5 Tam giác đều có 3 cạnh bằng nhau Toronto là thủ đô của Canada 3*4=10
True False False 4
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ 5
P, Q, R, S,… : các ký hiệu mệnh đề
Ký hiệu giá trị chân lý của mệnh đề: T: Đúng F: Sai
Bảng chân trị: biểu diễn mối quan hệ giữa những giá trị chân lý của các mệnh đề
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ Các phép tính mệnh đề
Phép phủ định: Cho P là một mệnh đề, câu “không phải là P” là một mệnh đề được gọi là phủ định của mệnh đề P. Kí hiệu: ¬P hay P Bảng chân trị
P
¬P
T F
F T 6
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ 7
Phép hội [conjunction]: Cho hai mệnh đề P, Q. “P và Q” là một mệnh đề được gọi là hội của 2 mệnh đề P và Q. Kí hiệu: PQ Bảng chân trị:
P T T F F
Q T F T F
PQ T T
F F F
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ 8
Phép tuyển [disjunction]: “P hay Q” là một mệnh đề được gọi là tuyển của 2 mệnh đề P và Q. Kí hiệu: P Q Bảng chân trị:
P T T F F
Q T F T F
PQ
T T T F
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ 9
Phép XOR: “loại trừ P hoặc loại trừ Q”, nghĩa là “hoặc là P đúng hoặc Q đúng”. Bảng chân trị
P T T F F
Q T F T F
PQ
F T T F
PQ = [P Q] ¬[P Q]
1.Mệnh đề 2.Vị từ
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ 10
Phép kéo theo: “Nếu P thì Q” là một mệnh đề kéo theo của hai mệnh đề P, Q. Bảng chân trị:
P T T F F
Q P®Q T
T F F T T F T
P ® Q = ¬P Q
1.Mệnh đề 2.Vị từ
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ
Mệnh đề đảo và mệnh đề phản đảo
Các mệnh đề kéo theo khác của mệnh đề P ® Q: Q ® P: mệnh đề đảo ¬Q ® ¬P: mệnh đề phản đảo
11
1.Mệnh đề 2.Vị từ
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ 12
Phép tương đương: “P nếu và chỉ nếu Q” là một mệnh đề được gọi là P tương đương Q.
Bảng chân trị:
P T T F F
Q T F T F
PQ T F F T
P Q = [P ® Q] [Q ® P]
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ
Cho P, Q, R,... là các mệnh đề. Nếu các mệnh đề này liên kết với nhau bằng các phép toán thì ta được một biểu thức mệnh đề.
Chú ý: -
Một mệnh đề cũng là một biểu thức mệnh đề.
-
Nếu P là một biểu thức mệnh đề thì ¬P cũng là biểu thức mệnh đề
-
Chân trị của biểu thức mệnh đề là kết quả nhận được từ sự kết hợp giữa các phép toán và chân trị của các biến mệnh đề. 13
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ 14
Hằng đúng: là một mệnh đề luôn có chân trị là đúng
Ví dụ: ¬P P P ¬P T F F T
¬P P T T
Hằng sai: là một mệnh đề luôn có chân trị là sai
Ví dụ: ¬P P
P ¬P T F
F T
¬P P F F
1.Mệnh đề 2.Vị từ
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ
Tiếp liên: là một mệnh đề không phải là hằng đúng và
không phải là hằng sai. Ví dụ: [P Q ] [¬Q] P Q ¬Q P Q [P Q ] [¬Q] T T F F
T F T F
F T F T
T F F F
T T F T 15
1.Mệnh đề 2.Vị từ
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ
Mệnh đề hệ quả: Cho F và G là 2 biểu thức mệnh đề. G là mệnh đề hệ quả của F hay G được suy ra từ F nếu F ® G là hằng đúng. Kí hiệu:
F G
Tương đương logic:
Định nghĩa 1: Mệnh đề P và Q được gọi là tương đương logic nếu phép tương đương của P và Q là hằng đúng.
Định nghĩa 2: Hai mệnh đề P và Q được gọi là tương đương logic nếu và chỉ nếu chúng có cùng chân trị. 16
1.Mệnh đề 2.Vị từ
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ
Các quy tắc tương đương logic:
Đặt T= hằng đúng, P T = T P F = F
Luật thống trị
P T = P P F = P
Luật trung hòa
P P = P P P = P
Luật lũy đẳng
P=P
F = hằng sai
Luật phủ định của phủ định 17
1.Mệnh đề 2.Vị từ
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ
Các quy tắc tương đương logic: Đặt T= hằng đúng, F = hằng sai P P = T P P = F P Q = Q P P Q = Q P
Luật về phần tử bù
Luật giao hoán
[P Q] R = P [Q R] [P Q] R = P [Q R]
Luật kết hợp
P [ Q R ] = [ P Q ] [ P R ] P [ Q R ] = [ P Q ] [ P R ]
Luật phân phối 18
1.Mệnh đề 2.Vị từ
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ
Các quy tắc tương đương logic:
Đặt T= hằng đúng,
F = hằng sai
P Q = P Q P Q = P Q
Luật De Morgan
P [P Q ] = P P [P Q ] = P
Luật hấp thụ
P ®Q = PQ
Luật về phép kéo theo 19
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ
Vị Từ Định nghĩa: Một vị từ là một khẳng định P[x,y,...] trong đó có chứa một số biến x, y,... lấy giá trị trong những tập hợp A, B,... cho trước, sao cho:
Bản thân P[x,y,...] không phải là mệnh đề. Nếu thay x, y,... bằng những giá trị cụ thể thuộc tập hợp A, B,... cho trước ta sẽ được một mệnh đề P[x, y,...]. Các biến x, y,... được gọi là
các biến tự do của vị từ.
Ví dụ: P[n] = {n là chẵn}
n = 2: {2 là chẵn}: True n = 5: {5 là chẵn}: False 20
1.Mệnh đề 2.Vị từ
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ
Không gian của vị từ: có thể xem vị từ như là một ánh xạ P, xE ta được một ảnh P[x]{0, 1}. Tập hợp E này được gọi là không gian của vị từ.
Trọng lượng của vị từ: số biến của vị từ
Ví dụ: P[a,b]
\= {cặp số nguyên tương ứng thỏa a + b = 5}
Không Trọng
gian của vị từ: Số nguyên
lượng: 2 21
1.Mệnh đề 2.Vị từ
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ
Cho trước các vị từ P[x], Q[x] theo một biến x A. Ta có các phép toán vị từ tương ứng như trên phép tính mệnh đề.
Phủ định ¬P[x]
Phép hội P[x] Q[x]
Phép tuyển P[x] Q[x]
Phép XOR P[x] Q[x]
Phép kéo theo P[x] ® Q[x]
Phép tương đương P[x] Q[x] 22
1.Mệnh đề 2.Vị từ
PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ
Định nghĩa: Cho P[x] là một vị từ có không gian là A. Các mệnh đề lượng tử hóa [quantified statement] của P[x] như sau: Mệnh
đề “Với mọi x thuộc A, P[x] ”, kí hiệu bởi “ x A, P[x]”,
là mệnh đề đúng P[a] luôn đúng với mọi giá trị a A. Mệnh
đề “Tồn tại một x thuộc A, P[x]]” kí hiệu bởi : “ x A, P[x]”,
là mệnh đề đúng khi và chỉ khi có một giá trị x = a nào đó sao cho mệnh đề P[a] đúng. 23
BÀI TẬP 24
Không lập bảng chân trị, sử dụng các tương đương logic để chứng minh rằng : [P Q] ® Q là hằng đúng.
[ P Q] ® Q = P Q Q \= [ P Q] Q \= P [Q Q ] \= PT \=T
BÀI TẬP 25
Bằng biến đổi tương đương, chứng minh các biểu thức mệnh đề sau là hằng đúng [PQ]®P
[PQ]®P = ¬ [PQ] v P \= [¬P v ¬Q] v P \= ¬P v P v ¬Q \= T v ¬Q = T P®[¬P®P]
P ® [PvP] = P ® P \= ¬P v P = T