Cách lập bảng chân trị trong toán rời rạc

     

Mục tiêu

Học ngừng chương này, sv phải nắm bắt được những vấn đề sau:

- Thế làm sao là mệnh đề, chân trị của mệnh đề, những phép toán mệnh đề.

Bạn đang xem: Cách lập bảng chân trị trong toán rời rạc

- Thực hiện được những phép toán mệnh đề.

- Hiểu được những ứng dụng của phép toán ngắn gọn xúc tích trong lập trình và trong đời sống hàng ngày.


Kiến thức cơ bản cần thiết

Các kiến thức cơ bản trong chương này bao gồm:

- Kiến thức về phép toán đại số, phép toán hình học cơ bản.

- có khả năng suy luận.

- Biết lập trình bằng ngôn ngữ Pascal, C


Tài liệu tham khảo

Phạm văn Thiều, Đặng Hữu Thịnh. Toán rời rạc ứng dụng vào tin học. Bên xuất bản Khoa học và Kỹ thuật, Hà Nội - 1997 (chương 1, trang 6 - 28).


Nội dung cốt lõi

- Định nghĩa mệnh đề, biểu thức mệnh đề.

- những phép toán

- Ví dụ ứng dụng

- Giới thiệu một số thuật ngữ chăm dùng

- Tương đương xúc tích và ngắn gọn và bí quyết chứng minh.


Định nghĩa mệnh đề

Mổi câu phát biểu là đúng xuất xắc là không đúng được gọi là một mệnh đề.

(Definition proposition: Any statement that is either true or false is called a proposition.)

Ví dụ 1: những câu xác định dưới đây là một mệnh đề

. 2 + 3 = 5

. 3*4 = 10 .

. Tam giác đều gồm 3 cạnh bằng nhau

. Washington D.C. Là thủ đô của Hoa Kỳ

. Toronto là thủ đô của Canada

Câu xác định "2 + 3 = 5", "Tam giác đều có 3 cạnh bằng nhau" cùng "Washington D.C. Là thủ đô của Hoa Kỳ" là các mệnh đề đúng. Còn những câu xác định "3*4 = 10" cùng "Toronto là thủ đô của Canada" là những mệnh đề sai.

Như vậy, một mệnh đề gồm thể là mệnh đề đúng hoặc mệnh đề sai. Hay nói phương pháp khác, một mệnh đề chỉ gồm thể lựa chọn 1 trong những 2 giá trị là đúng hoặc là sai.

Một mệnh đề ko thể vừa đúng vừa sai.

Ví dụ 2: Xét các câu phân phát biểu sau

. Từ bây giờ là thứ mấy ?

. Một số thực âm không phải là số bao gồm phương

. Hãy đọc kỹ đọan này

. X + 1 = 2

. X + y = z

Câu "Hôm nay là thứ mấy ? " không là mệnh đề bởi vì nó chỉ là một câu hỏi không có giá trị đúng, sai. Câu "Một số âm không phải là số chính phương" gồm chân trị là đúng nếu xét bên trên tập họp số thực R nhưng lại bao gồm chân trị sai khi xét bên trên tập họp số phức. Câu "x+1=2" và câu "x+y=z" không phải là mệnh đề do chúng chẳng đúng cũng chẳng không đúng bởi các biến trong những câu đó chưa được gán đến một giá bán trị cụ thể nào.

giá trị đúng, không nên của một mệnh đề được gọi là chân trị của mệnh đề đó. Chân trị của mệnh đề đúng ký kết hiệu là T (true), chân trị của mệnh đề sai ký kết hiệu là F (false).

Bảng chân trị của mệnh đề bao gồm những trường hợp đúng, sai bao gồm thể xảy ra của mệnh đề đó.

Mục đích của những họat động khoa học là phân biệt các mệnh đề để xác định chân trị của nó. Sự xác định chân trị này dựa vào thực nghiệm và lý luận. Lý luận ở đây là xác định chân trị của mệnh đề bằng biện pháp kết hợp những mệnh đề mà lại ta đã biết chân trị. Các luật lệ chế ngự phương pháp kết hợp sở hữu tính đúng chuẩn của phép toán đại số. Vày thế, họ cần nói đến "Đại số mệnh đề".


Các phép tính mệnh đề

vào phép tính mệnh đề, người ta không thân thiện đến ý nghĩa của câu phạt biểu mà chỉ chú ý đến chân trị của những mệnh đề. Vị đó, khi thực hiện những phép toán mệnh đề thông thường người ta không ghi rõ những câu vạc biểu nhưng chỉ ghi ký hiệu. Những chữ loại sẽ được cần sử dụng để ký hiệu các mệnh đề. Những chữ loại thường dùng là P, Q, R,.....

Mệnh đề chỉ gồm một giá trị đơn (luôn đúng hoặc sai) được gọi là mệnh đề nguyên từ ( atomic proposition ). Các mệnh đề ko phải là mệnh đề nguyên từ được gọi là mệng đề phức hợp (compound propositions). Thông thường, tất cả mệnh đề phức hợp là mệnh đề liên kết (có chứa phép tính mệnh đề).

những phép tính mệnh đề được sử dụng nhằm mục đích kết nối các mệnh đề lại với nhau tạo ra một mệnh đề mới. Những phép toán mệnh đề được trình diễn trong chương này bao gồm : phép phủ định, phép hội, phép tuyển, phép XOR, phép kéo theo, phép tương đương.


Phép phủ định (NEGATION)

Cho p. Là một mệnh đề, câu "không phải là P" là một mệnh đề khác được gọi là phủ định của mệnh đề p. Kí hiệu : ¬ kích cỡ 12 neg p. (P¯ kích cỡ 12 overline P ).

Ví dụ : p = " 2 > 0 "

¬ kích cỡ 12 neg p = " 2 ≤ 0 "

Bảng chân trị (truth table)

p ¬ form size 12 neg p
T F
F T
Qui tắc: Nếu p. Có giá trị là T thì phủ định phường có giá trị là F.


Phép hội (CONJUNCTION)

mang lại hai mệnh đề P, Q. Câu xác định "P cùng Q" là một mệnh đề mới được gọi là hội của 2 mệnh đề p. Và Q. Kí hiệu phường ^ Q.

Ví dụ : mang đến 2 mệnh đề p và Q như sau

phường = " 2 > 0 " là mệnh đề đúng

Q = " 2 = 0 " là mệnh đề sai

p ^ Q = " 2> 0 cùng 2 = 0 " là mệnh đề sai.

Bảng chân trị

p q p^q
T T T
T F F
F T F
F F F

Qui tắc : Hội của 2 mệnh đề chỉ đúng khi cả hai mệnh đề là đúng. Các trường hợp còn lại là sai.


Phép tuyển (DISJUNCTION)

đến hai mệnh đề P, Q. Câu xác định "P tốt (hoặc) Q" là một mệnh đề mới được gọi là tuyển của 2 mệnh đề p và Q. Kí hiệu phường V Q.

Ví dụ : cho 2 mệnh đề p. Và Q như sau

phường = " 2 > 0 " là mệnh đề đúng

Q = " 2 = 0 " là mệnh đề sai

phường V Q = " 2 ≥ 0 " là mệnh đề đúng.

pqpvq
TTT
TFT
FTT
FFF
Bảng chân trị

Qui tắc : Tuyển của 2 mệnh đề chỉ sai lúc cả hai mệnh đề là sai. Các trường hợp còn lại là đúng.


Phép XOR

đến hai mệnh đề phường và Q. Câu xác định "loại trừ p. Hoặc lọai trừ Q", nghĩa là "hoặc là phường đúng hoặc Q đúng nhưng không đồng thời cả hai là đúng" là một mệnh đề mới được gọi là phường xor Q. Kí hiệu phường ⊕ kích cỡ 12⊕ Q.

Bảng chân trị

p q p⊕ size 12⊕ q
T T F
T F T
F T T
F F F


Phép toán trên bit

Các máy vi tính dùng các bit để biểu diễn thông tin. Một bit bao gồm 2 giá bán trị khả dĩ là 0 với 1. Bit cũng tất cả thể được dùng để biểu diễn chân trị. Thường người ta dùng bit 1 để biểu diễn chân trị đúng cùng bit 0 để biểu diễn chân trị sai. Những phép toán trên bit trong máy tính xách tay là các phép toán logic. Thông tin thường được biển diễn bằng phương pháp dùng những xâu bit. Ta tất cả định nghĩa xâu bit như sau:

Định nghĩa : Một xâu bit (hoặc xâu nhị phân) là dãy tất cả một hoặc nhiều bit. Chiều dài của xâu là số các bit trong xâu đó.

Ví dụ : 101011000 là một xâu bit gồm chiều nhiều năm là 9

gồm thể mở rộng những phép toán trên bit tới những xâu bit. Người ta định nghĩa các OR bit, & bit và XOR bit đối với 2 xâu bit có cùng chiều nhiều năm là các xâu có những bit của bọn chúng là ca1c OR, AND, XOR của các bit tương ứng vào 2 xâu tương ứng. Họ cũng dùng những kí hiệu ^, v, ⊕ kích thước 12⊕ để biểu diễn những phép tính OR bit, và và XOR tương ứng.

Ví dụ : search OR bit, & bit và XOR bit đối với 2 xâu sau đây (mỗi xâu được bóc tách thành 2 khối, mỗi khối bao gồm 5 bit đến dễ đọc)

01101 10110

11000 11101

11101 11111 OR bit

01000 10100 and bit

10101 01011 XOR bit


Phép kéo theo (IMPLICATION)

Cho p. Và Q là nhì mệnh đề. Câu "Nếu p thì Q" là một mệnh đề mới được gọi là mệnh đề kéo theo của nhì mệnh đề P,Q. Kí hiệu p → Q. P. được gọi là giả thiết với Q được gọi là kết luận.

Ví dụ : cho hai mệnh đề phường và Q như sau

p. = " tam giác T là đều "

Q = " tam giác T tất cả một góc bằng 60°"

Để xét chân trị của mệnh đề phường → Q, ta bao gồm nhận xét sau :

- Nếu p đúng, nghĩa là tam giác T là đều thì cụ thể rằng p → Q là đúng.

- Nếu p. Sai, nghĩa là tam giác T ko đều cùng cũng không là cân thì mặc dù Q là đúng hay sai thì mệnh đề p → Q vẫn đúng.

Sau đây là bảng chân trị của ví dụ với cũng là bảng chân trị của mệnh đề p. →Q.

*

Qui tắc : mệnh đề kéo theo chỉ sai khi giả thiết đúng với kết luận sai. Những trường hợp khác là đúng.

Từ mệnh đề phường → Q, họ có thể tạo ra các mệnh đề kéo theo khác như là mệnh đề Q → p. Và ¬ kích thước 12 neg Q → P được gọi là mệnh đề đảo và mệnh đề phản đảo của mệnh đề phường → Q.

Xem thêm: Hướng Dẫn Cách Trang Trí Phòng Học Mầm Non Đẹp Sáng Tạo, Hướng Dẫn Trang Trí Các Góc Lớp Mầm Non

Ví dụ : tra cứu mệnh đề đảo cùng phản đảo của mệnh đề sau

" Nếu tôi gồm nhiều tiền thì tôi thiết lập xe hơi"

Mệnh đề đảo là :

" Nếu tôi tải xe hơi thì tôi bao gồm nhiều tiền"

Mệnh đề phản đảo là :

" Nếu tôi không cài xe hơi thì tôi không tồn tại nhiều tiền"


Phép tương đương (BICONDITIONAL)

Cho p. Và Q là nhì mệnh đề. Câu "P nếu và chỉ nếu Q" là một mệnh đề mới được gọi là p. Tương đương Q. Kí hiệu phường  Q. Mệnh đề tương đương là đúng khi phường và Q bao gồm cùng chân trị.

p  Q = (P → Q) ^ (Q → P)

Đọc là : phường nếu và chỉ nếu Q

p là cần cùng đủ đối với Q

Nếu p. Thì Q với ngược lại

Bảng chân trị

p q p↔ kích thước 12↔ q
T T T
T F F
F T F
F F T

Biểu thức mệnh đề (LOGICAL CONNECTIVES)

mang lại P, Q, R,... Là những mệnh đề. Nếu những mệnh đề này liên kết với nhau bằng những phép toán thì ta được một biểu thức mệnh đề.

chăm chú : . Một mệnh đề cũng là một biểu thức mệnh đề

. Nếu phường 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 những biến mệnh đề.

Ví dụ : kiếm tìm chân trị của biểu thức mệnh đề ¬ kích thước 12 neg P ^V (Q ^ R )

*

Do biểu thức mệnh đề là sự liên kết của nhiều mệnh đề bằng những phép toán nên bọn họ có thể so sánh để biểu diễn những biểu thức mệnh đề này bằng một cây mệnh đề.

Ví dụ : Xét câu vạc biểu sau :

" Nếu Michelle thắng vào kỳ thi Olympic, mọi người sẽ khâm phục cô ấy, và cô ta sẽ trở nên giàu có. Nhưng, nếu cô ta không thắng thì cô ta sẽ mất tất cả."

Đây là một biểu thức mệnh đề cùng phép toán chính là phép hội. Gồm thể viết lại như sau :

"Nếu Michelle thắng vào kỳ thi Olympic, mọi người sẽ khâm phục cô ấy, và cô ta sẽ trở đề xuất giàu có.

Nhưng,

nếu cô ta ko thắng thì cô ta sẽ mất tất cả. "

Cả hai mệnh đề chủ yếu trong biểu thức mệnh đề này là mệnh đề phức hợp. Có thể định nghĩa các biến mệnh đề như sau:

P: Michelle thắng trong kỳ thi Olympic

Q: mọi người sẽ khâm phục cô ấy

R: cô ta sẽ trở nên giàu có

S: cô ta sẽ mất tất cả

Biểu diễn câu phát biểu trên bằng các mệnh đề và những phép toán, ta bao gồm biểu thức mệnh đề sau : ( phường → (Q ^ R)) ^ (¬ form size 12 neg P → S)

Biểu diễn câu vạc biểu trên thành một cây ngữ nghĩa như sau :

Nếu Michelle thắng vào kỳ thi Olympic, mọi người sẽ khâm phục cô ấy, và cô ta sẽ trở phải giàu có. Nhưng, nếu cô ta không thắng thì cô ta sẽ mất tất cả. Nếu Michelle thắng vào kỳ thi Olympic, mọi người sẽ khâm phục cô ấy, và cô ta sẽ trở phải giàu có. Nếu cô ta ko thắng thì cô ta sẽ mất tất cả. AND Michelle thắng trong kỳ thi Olympic Mọi người sẽ khâm phục cô ấy, cùng cô ta sẽ trở cần giàu có. Cô ta không thắng Cô ta sẽ mất tất cả. Mọi người sẽ khâm phục cô ấy Cô ta sẽ trở cần giàu có. Cô ta sẽ mất tất cả. AND NOT


Các ứng dụng của lô ghích (EVERDAY LOGICAL)

Ngày nay, xúc tích mệnh đề được ứng dụng nhiều trong số lĩnh vực khác biệt như:

- Viết

- Nói

- tìm kiếm bên trên mạng (search engines)

- Toán học

- các chương trình máy tính xách tay (logic in programming)

bởi vì đó, hiểu biết các qui tắc để sử dụng ngắn gọn xúc tích là rất hữu ích. Sau đây là một vài ba ví dụ để chỉ ra những ứng dụng đó.


Ví dụ 1: lô ghích trong tra cứu kiếm trên mạng

Đặt vấn đề : Bạn muốn search tài liệu trên mạng có liên quan đến hai từ "disc golf". Nếu bạn gõ vào ô kiếm tìm kiếm nhị từ "disc golf" này, bạn sẽ search thấy các tài liệu về disc và các tài liệu về golf nhưng không kiếm thấy những các tài liệu về "disc golf".

biện pháp giải quyết : Bạn chỉ cần gõ vào ô tra cứu kiếm là "disc and golf"


Ví dụ 2 : ngắn gọn xúc tích trong lập trình (Logic in programming)

Đặt vấn đề : Bạn muốn đặt điều kiện là nếu 00 và x 0 với y > 0 . Đặt :

a + 51 = x2

a - 38 = y2

89 = 1.89 = x2 - y2 = ( x + y )( x - y )

Suy ra :

x + y = 1

x - y = 89

(loại vị x, y là nguyên dương đề nghị không thể có x + y = 1)

xuất xắc là :

x + y = 89

x - y = 1

Giải hệ phuơng trình này ta được x = 45 với y = 44. Vậy a = 1974.

bên trên đây là vài ví dụ đơn giản. Hy vọng rằng những ví dụ này cho họ thấy được sự quan tiền trọng của logic không chỉ vào toán học, khoa học máy vi tính mà còn vào cuộc sống hàng ngày.



Định nghĩa Hằng đúng (Tautologie):

Một hằng đúng là một mệnh đề luôn luôn có chân trị là đúng.

Một hằng đúng cũng là một biểu thức mệnh đề luôn có chân trị là đúng bất chấp sự lựa chọn chân trị của biến mệnh đề.

Ví dụ : xét chân trị của biểu thức mệnh đề P v p

*

Vậy ¬ form size 12 neg PvP là một hằng đúng.


Định nghĩa Hằng không đúng (Contradiction):

Một hằng sai là một mệnh đề luôn luôn có chân trị là sai.

Một hằng không nên cũng là một biểu thức mệnh đề luôn có chân trị là không nên bất chấp sự lựa chọn chân trị của biến mệnh đề.

Ví dụ : xét chân trị của biểu thức mệnh đề ¬ form size 12 neg P ^ p

*

Vậy ¬ size 12 neg P^P là một hằng sai.


Định nghĩa tiếp liên (Contingency):

Một tiếp liên là một biểu thức mệnh đề không phải là hằng đúng với không phải là hằng sai.

Ví dụ : tìm kiếm chân trị của biểu thức mệnh đề (P ^ Q ) v ¬ kích cỡ 12 neg Q

*

Vậy (P ∧ Q ) v ¬ kích cỡ 12 neg Q là một tiếp liên vì chưng nó ko phải là hằng đúng cùng cũng không phải là hằng sai.


Mệnh đề hệ quả

Định nghĩa : mang lại F cùng G là 2 biểu thức mệnh đề. Người ta nói rằng G là mệnh đề hệ quả của F giỏi G được suy ra từ F nếu F → G là hằng đúng.

Kí hiệu F |→ G

Ví dụ : cho F = ( phường → Q ) ^ ( Q → R )

G = phường → R

Xét coi G bao gồm là mệnh đề hệ quả của F không ?

*

Vậy G là mệnh đề hệ quả của F

Nhận xét : Nếu G là hệ quả của F thì khi F là đúng thì bắt bắt buộc G phải đúng. Ngược lại, nếu G là đúng thì chưa gồm kết luận gì vể chân trị của F.


Tương đương súc tích (LOGICALLY EQUIVALENT)

Định nghĩa 1 : Mệnh đề phường và mệnh đề Q được gọi là tương đương ngắn gọn xúc tích nếu phép tương đương của p. Và Q (PQ) là hằng đúng. Định nghĩa 2 : hai mệnh đề phường và Q được gọi là tương đương xúc tích nếu cùng chỉ nếu chúng gồm cùng chân trị. Mệnh đề phường và Q tương đương xúc tích được kí hiệu là p. ⇔ Q (hay p = Q)

Ví dụ 1 : cho F = Pv(Q^R)

G = (PvQ) ^ (PvR)

Xét xem nhì mệnh đề trên là bao gồm tương đương lô ghích không ?

Vậy F cùng G là tương đương súc tích hay F=G.

Xem thêm: Công Dụng Chữa Bệnh Tuyệt Vời Của Cây Tía Tô Chữa Bệnh Tuyệt Vời Của Cây Tía Tô

Ví dụ 2: đến F = phường → Q

G = ¬ size 12 neg (PvQ) Xét xem nhị mệnh đề trên là bao gồm tương đương ngắn gọn xúc tích không ?

*

Vậy F ⇔ G hay p → Q =  (PvQ)

Bảng các tương đương xúc tích và ngắn gọn thường dùng

Đặt T= hằng đúng, F = hằng sai

*

Domination laws : luật nuốt

Identity laws : luật đồng nhất

Idempotent laws : luật lũy đẳng

Double negation law : luật phủ định kép

Cancellation laws : luật xóa bỏ

Commutative laws : luật giao hoán

Associative laws : luật kết hợp

Distributive laws : luật phân bố

De Morgan’s laws : luật De Morgan

Ngoài các tương đương thường cần sử dụng trong bảng trên, tất cả một tương đương súc tích khác mà họ cũng sẽ hay gặp trong các chứng minh.

Đó là :

P v ( p ^ Q ) = P

p ^ ( phường v Q ) = P

( sinh viên tự chứng minh coi như bài bác tập )

Ví dụ 1 : ko 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.
*
Ví dụ 2 : Chứng minh rằng 

*

Ví dụ 3 : Áp dụng trong lập trình

Giả sử vào chương trình tất cả câu lệnh sau :

while(NOT(A!=0 and NOT(A>= 10)))

Ta bao gồm thể viết lại câu lệnh này một phương pháp đơn giản hơn bằng cách sử dụng công thức De Morgan.

while( A==0 OR A>= 10)

Ví dụ 4: Giả sử vào chương trình gồm câu lệnh sau :

while( (i10) OR (i= 10)))

Trước hết chúng ta sẽ áp dụng công thức De Morgan để biến đổi biểu thức cuối cùng như sau :

while( (i10) OR (i= 10) )

Sau đó, chúng ta lại sử dụng công thức về tính phân bố của phép hội đối với phép tuyển để rút gọn biểu thức phía trước. Ta có câu lệnh cuối cùng là :