Các phép toán logic cơ bản toán rời rjax

Trong toán học ta quan tâm đến những mệnh đề có giá trị hân lý xác định (đúng hoặc sai nhưng không thể vừa đúng vừa sai). Các khẳng định như vậy được gọi là mệnh đề. Các mệnh đề đúng được nói là có giá trị chân lý đúng (hay chân trị đúng ), các mệnh đề sai được nói là có chân t rị sai. Ví dụ:

1. Các khẳng định sau là mệnh đề:  Môn Toán rời rạc là môn bắt buộc cho ngành Tin học.  1+1=2.  4 là số nguyên tố. Hai mệnh đề đầu có chân trị 1, mệnh đề thứ ba có chân trị 0.
2. Các khẳng định dưới dạng tán than hoặc mệnh lệnh không phải mệnh đề vì nó không có chân trị xác định.
3. Khẳng định “ ݊ là số nguyên tố ” không phải mệnh đề. Tuy nhiên, nếu thay n bằng một số nguyên cố định thì ta sẽ có một mệnh đề: chẳng hạn với ݊= 3 ta có một mệnh đề đúng, trong khi với ݊= 4 ta có một mệnh đề sai. Khẳng định này được gọi là một vị từ và cũng là đối tượn khảo sát của logic. Ta thường ký hiệu các mệnh đề bởi các chữ ܲ,ܳ,ܴ, ... và chân trị đúng (sai) được ký hiệu bởi 1 (0). Đôi khi ta còn dùng các ký hiệu ܶ,ܸ để chỉ chân trị đúng và ܨ dể chỉ chân trị sai. Phân tích kỹ các ví dụ ta thấy các mệnh đề được chia ra làm 2 loại:  Các mệnh đề được xây dựng từ các mệnh đề khác nhờ liên kết chúng lại bằng các liên từ(và, hay, nếu... thì... ) hoặc trạng từ “không”. Ta nói các mệnh đề này là mệnh đề phức hợp. Ví dụ: “ Nếu trời đẹp thì tôi đi dạo” là một mệnh đề phức hợp.  Các mệnh đề không thể xây dựng từ các mệnh đề khác bằng các liên từ hoặc trạng từ “không”. Ta nói các mệnh đề này là mệnh đề nguyên thủy hay sơ cấp. Ví dụ: “Hôm nay trời đẹp”, “3 là số nguyên tố” là các mệnh đề nguyên thủy. Mục đích của phép tính mệnh đề là nghiên cứu chân trị của một mệnh đề phức hợp từ chân trị của các mệnh đề đơn giản hơn và các phép nối của những mệnh đề này thể hiện qua lien từ hoặc trạng từ “không”. Các phép nối: Phép phủ định: phủ định của mệnh đề P được ký hiệu bởi ¬ ܲ (đọc là không P). Chân trị của ¬ ܲ là 0 nếu chân trị của ܲ là 1 và ngược lại. Ta có bảng sau gọi là bảng chân trị của phép phủ định:

maibaoquat

ܲ ܳ ܲ∨ܳ

0

0

1

1

0

1

0

1

0

1

1

0

Phép kéo theo: nếu P thì Q được ký hiệu là ܳ → ܲ (cũng đọc là ܲ kéo theo ܳ, hay ܲ là điều kiện đủ của ܳ, hay ܳ là điều kiện đủ của ܲ). Để xác định chân trị cho ܳ → ܲ ta hãy xem ví dụ mệnh đề “nếu trời đẹp thì tôi đi dạo”. Ta có các trường hợp sau:  trời đẹp và tác giả của khẳng định đang đi dạo: khi ấy hiển nhiên là mệnh đề đúng.  trời đẹp và tác giả ngồi nhà: mệnh đề rõ ràng sai.  trời xấu và tác giả đi dạo: mệnh đề vẫn đúng  trời xấu và t ác giả ngồi nhà: mặc dù trời xấu nhưng tác giả không vi phạm khẳng định của mình nên mệnh đề phải được xem là đúng. Từ đó ta có bảng chân trị của phép kéo theo như sau: ܲ ܳ ܲ→ܳ 0 0 1 1

0

1

0

1

1

1

0

1

Chú ý: 1. Với quy ước về chân trị như trên, ta sẽ cò những khẳng định đúng rất ngộ nghĩnh như: “nếu 2=1 thì Quang Trung và Trần Hưng Đạo là một người” 2. Cần phân biệt mệnh đề ܳ → ܲ với lệnh ܳ ݊݁ℎݐ ܲ ݂ܫ trong một số ngôn ngữ lập trình ví dụ như Pascal, Basic. Trong ܳ → ܲ thì cả ܲ và ܳ là mệnh đề còn trong lệnh ℎݐ ܳ ݊݁ℎݐ ܲ ݂ܫìܲ là một mệnh đề còn ܳ là một dãy liên tiếp dòng lệnh sẽ được thực hiện nếu mệnh đề P có chân trị 1 và sẽ được bỏ qua nếu P có chân trị là 0. Nhắc lại rằng các dòng lệnh là những mệnh lệnh mà máy phải thực hiện nên không phải là một mệnh dề theo nghĩa ta xét. Dù sao cũng có một sự tương tự giữa hai đối tượng “ܳ → ܲ” và “ܳ ݊݁ℎݐ ܲ ݂ܫ”. Hơn nữa có thể lợi dụng các tương đương logic để thực hiện lệnh “ܳ ݊݁ℎݐ ܲ ݂ܫ” có hiệu quả. 3. Trong ngôn ngữ hằng ngày, người ta thường hay nhầm lẫn phép kéo theo với kéo theo hai chiều, chẳng hạn như phát biểu ”giảng viên khoa Toán dạy nghiêm túc” mà viết theo phép nối là “nếu anh là giáo viên khoa Toán thì anh dạy nghiêm túc” thường bị phản ứng giáo viên các khoa khác vì họ cho rằng người nói đã ám chỉ “nếu là giảng viên khoa khác thì dạy không nghiêm túc”. Thật ra khi phát biểu, người nói có khi cũng muốn ám chỉ “nếu anh là giáo viên khoa Toán thì anh dạy nghiêm túc”. Ở đây nếu viết phát biểu ban đầu dưới dạng ܳ → ܲ thì hai phát biểu hiểu nhầm sẽ có dạng ( ¬ ܲ) → ( ¬ ܳ) và ܲ → ܳ. Tuy nhiên, nếu bao gồm them một trong hai phát biểu sau, thì phát biểu ܳ → ܲ thành một phép kéo theo hai chiều theo nghĩa dưới đây.

maibaoquat

Phép kéo theo hai chiều: mệnh đề nếu ܲ thì ܳ và ngược lại được ký hiệu là ܳ ↔ ܲ (cũng đọc là ܲ khi và chỉ khi ܳ,ܲ nếu và chỉ nếu ܳ, hay P là điều kiện cần và đủ để có ܳ). Theo trên, cả hai chiều ܳ → ܲ và ܲ → ܳ đều đúng nên nếu ܲ đúng thì ܳ cũng đúng và ngược lại. Do đó ta có bảng chân trị của phép kéo theo hai chiều như sau:

ܲ ܳ ܲ↔ܳ 0 0 1 1

0

1

0

1

1

0

0

1

§2 DẠNG MỆNH ĐỀ

Trong Đại số ta có các biểu thức đại số được xây dựng từ:  các số nguyên, hữu tỉ, thực,... mà ta gọi là hằng số.  các biến ݔ,ݕ, ... có thể lấy giá trị là các hằng số.  các phép toán thao tác trên các hằng số và các biến theo một thứ tự nhất định. Khi thay thế các biến trong một biểu thức đại số bởi các hằng số thì kết quả thực hiện phép toán trong biểu thức sẽ là một hằng số nào đó. Trong phép toán mệnh đề ta cũng có các “biểu thức logic” tương tự mà ta gọi là các dạng mệnh đề được xây dựng từ:  các mệnh đề (hằng mệnh đề).  các biến mệnh đề ݌,ݍ, ... có thể lấy giá trị là các mệnh đề nào đó.  các phép nối thao tác trên các hằng mệnh đề và biến mệnh đề theo một thứ tự nhất định. Ở đây thứ tự được xác định bởi các dấu “()” để chỉ rõ phép nối thực hiện trên cặp mệnh đề nào, đúng ra là trên các biểu thức con nào. Ví dụ như: ܧ( ݌,ݍ,ݎ) = ( ݌ ∧ ݍ) ˅ ( ( ¬ ݎ) ݌ →) là một dạng mệnh đề trong đó ݌,ݍ,ݎ là các biến mệnh đề còn ܲ là một hằng mệnh đề. Giả sử ܧ,ܨ là 2 dạng mệnh đề, khi ấy ¬ ܧ,ܧ ∧ ܨ,ܨ → ܧ,ܨ ↔ ܧ là các dạng mệnh đề. Bằng cách này ta có thể xây dựng được các dạng mệnh đề càng ngày càng phức tạp. Mặt khác, điều ta quan tâm đối với một dạng mệnh đề ܧ( ݌,ݍ,ݎ, ...) là chân trị của mệnh đề đó có được ܧ( ܲ,ܳ,ܴ, ...) khi thay các biến mệnh đề ݌,ݍ,ݎ, ... bởi các hằng mệnh đề ܲ,ܳ,ܴ, ... có chân trị xác định, nghĩa là sự phụ thuộc của chân trị của ܧ( ݌,ݍ,ݎ, ...) theo các chân trị của ݌,ݍ,ݎ, ... chứ không phải theo các thể hiện cụ thể ݌,ݍ,ݎ, ... qua các mệnh đề cu thể ܲ,ܳ,ܴ, ... Nói cách khác mỗi một dạng mệnh đề ܧ( ݌,ݍ,ݎ, ...) có một bảng chân trị xác định trong đó mỗi dòng cho biết chân trị của ܧ( ݌,ݍ,ݎ, ...) theo các chân trị cụ thể của ݌,ݍ,ݎ, ...

maibaoquat

Nếu chỉ để ý đến phép kéo theo một chiều ta có Định nghĩa 1.2: dạng mệnh đề ܨđược nói là hệ quả logic của mệnh đề ܧ nếu ܨ → ܧ là một hằng đúng. Khi ấy ta viết ܨ ⟹ ܧ. Ta cũng nói ܧ là hệ quả logic của ܨ. Như thế nói rằng ܧ tương đương logic với ܨ có nghĩa là ܨ là hệ quả logic của ܧ và ܧ là hệ quả logic của ܨ. Trong phép tính mệnh đề, ta thường không phân biệt các dạng mệnh đề tương đương logic. Ta có Quy tắc t hay thế thứ nhất: trong dạng mệnh đề ܧ nếu ta thay thế biểu thức con ܨ bởi một dạng mệnh đề tương đương logic thì dạng mệnh đề thu được vẫn còn tương dương logic với ܧ. Chú ý: Ta đã sử dụng khái niệm biểu thức con theo một nghĩa hết sức tự nhiên: dạng mệnh đề ܨ “xuất hiện” trong ܧ, hay nói cách khác ܧ có thể xây dựng từ ܨ và một số dạng mệnh đề khác qua các phép nối. Ví dụ: → ݌( ݎ → ݍ) tương đương logic với → ݌( ¬ ݎ˅ݍ) vì trong đó biểu thức con ݎ → ݍđã được thay thế bởi dạng mệnh đề tương dương logic là ¬ ݎ˅ݍ. Với quy tắc thay thế trên ta có thể “rút gọn” một dạng mệnh đề bằng cách thay một biểu thức con bởi một dạng mệnh đề tương đương nhưng đơn giản hơn hoặc giúp cho bước rút gọn tiếp theo dễ dàng hơn. Ngoài ra, cũng cần nhận biết một số hằng đúng. Thường các hằng đúng này có thể suy từ một số hằng đúng đơn giản nhờ: Quy tắc thay thế t hứ hai: giả sử dạng mệnh đề ܧ( ݌,ݍ,ݎ, ...) là một hằng đúng. Nếu ta thay thế những nơi p xuất hiện trong E bởi một dạng mệnh đề tùy ý ܨ( ݌’,ݍ’,ݎ’, ...) thì dạng mệnh đề nhận được theo các biến ݌,ݍ,ݎ, ...,ݍ’,ݍ’,ݎ’, ... vẫn còn là một hằng đúng. Ngoài hai quy tắc thay thế trên, ta còn sử dụng 10 quy luật logic được phát biểu dưới dạng các tương đương logic có thể rút gọn một dạng mệnh đề cho trước. Ta có Định lý 1.2 (Quy luật logic) : với ݌,ݍ,ݎ là các biến mệnh đề, 1 là một hằng đúng và 0 là một mâu thuẫn (hằng sai), ta có các tương đương logic: i. Phủ định của phủ định: ¬ ¬ ݌ ⇔ ݌ ii. Quy tắc De Morgan: ¬ ( ݍ ∧ ݌) ⇔¬ ∨ ݌¬ ݍ ¬ ( ݍ ∨ ݌) ⇔¬ ∧ ݌¬ ݍ iii. Luật giao hoán: ݌∨ ݍ ⇔ ݍ∨ ݌ ݌∧ ݍ⇔ ݍ∧ ݌ iv. Luật kết hợp: ݌∧ ( ݎ ∧ ݍ) ⇔ ( ݍ ∧ ݌) ∧ ݎ) ∨ ݌( ݎ ∨ ݍ) ⇔ ( ݍ ∨ ݌) ݎ ∨) v. Luật phân bố: ݌ ∧( ݎ ∨ ݍ) ⇔( ݍ ∧ ݌) ∨( ݎ ∧ ݌) ∨ ݌( ݎ ∧ ݍ) ⇔ ( ݍ ∨ ݌) ∧ ( ݎ ∨ ݌)

maibaoquat

vi. Luật lũy đẳng (I dempotent Rules) ݌ ⇔ ݌ ∧ ݌ ݌ ⇔ ݌ ∨ ݌ vii. Luật trung hòa: ∧ ݌ 1 ⇔ ݌ ∨ ݌ 0 ݌ ⇔ viii. Luật về phần tử bù: ∧ ݌¬ ݌⇔ 0 ∨ ݌¬ ݌⇔ 1 ix. Luật thống trị: ∧ ݌ 0 ⇔ 0 ∨ ݌ 1 ⇔ 1 x. Luật hấp thụ: ∧ ݌( ݍ ∨ ݌) ⇔ ݌ ∨ ݌( ݍ ∧ ݌) ⇔ ݌ Chứng minh: đọc giả có thể kiểm tra dễ dàng 10 quy luật logic trên bằng cách lập bảng chân trị của hai vế của tương đương logic.  đpcm Ví dụ:

1. Từ quy tắc De morgan ta được hằng đúng ¬ ( ݍ ∧ ݌)  ⟺¬ ∨ ݌¬ ݍ Thay thế p bởi r฀s ta sẽ được một hằng đúng mới ¬ ( ( ݏ ∧ ݎ) ݍ ∧)  ⟺ ¬ ( ݏ ∧ ݎ) ∨¬ ݍ
2. Hãy chứng minh dạng mệnh đề sau là hằng đúng [ ( ݏ → ݎ) ∧ [ ( ݏ → ݎ) → ( ¬ ݑ ∨ ݐ) ] ] → ( ¬ ݑ ∨ ݐ) (1.2) Muốn vậy ta thay thế r→s bởi p và ¬t฀u bởi q và đưa về chứng minh dạng mệnh đề sau là hằng đúng: [ ݌∧ ( ݌ → ݍ) ] → ݍ Ta sử dụng liên tiếp quy tắc thay thế thứ nhất và được các tương đương logic sau: [ ݌ ∧( ݌ → ݍ) ] → ݍ  [ ݌ ∧( ¬ ݍ ∨ ݌) ] → ݍ  [ ( ∧ ݌¬ ݌) ∨( ݍ ∧ ݌) ] → ݍ  [ 0 ∨( ݍ ∧ ݌) ] → ݍ  [ ( ݍ ∧ ݌) ] → ݍ  ¬ ∨ ݌¬ ݍ ∨ ݍ  ¬ ∨ ݌ 1  1 Do đó 1.2 là một hằng đúng.
3. Tương tự như trên ta có: ( ݍ ∧ ݌) → ݎ  ¬ ∨ ݌¬ ݎ ∨ ݍ  ¬ ∨ ݌( ¬ ݍ ∨ ݎ)  ¬ ∨ ݌( ݍ → ݎ) (1.2)

maibaoquat

§3 QUY TẮC SUY DIỄN

Trong một chứng minh toán học, xuất phát từ một số khẳng định đúng p1, p2,..., pn gọi là tiền đề, ta áp dụng các quy tắc suy diễn để suy ra chân lý của một khẳng định q mà ta gọi là kết luận. Nói cách khác, các quy tắc suy diễn được áp dụng để suy ra q là hệ quả logic của p1฀ p2฀...฀pn, hay nói cách khác dạng mệnh đề ( ݌ଵ݌˄ଶ ˄...݌˄௡) ݍ → là một hằng đúng, trong đó p 1 , p 2 ,..., pn, q là các dạng mệnh đề theo một số biến logic nào đó. Thường thì các biến logic không xuất hiện một cách tường minh mà được trừu tượng hóa (bỏ đi một phần nội dung cụ thể) từ các mệnh đề nguyên thủy như ví dụ sau đây cho thấy. Giả sử ta có các tiền đề: ݌ଵ: nếu An học chăm thì An đạt môn Toán rời rạc. ݌ଶ: nếu An không đi chơi thì An học chăm. ݌ଷ: An trượt môn Toán rời rạc. Ta muốn dùng các quy tắc suy diễn để suy ra kết luận sau là đúng: ݍ: An hay đi chơi. Muốn vậy ta trừu tượng hóa các mệnh đề nguyên thủy “An học chăm”, “An hay đi chơi”, “An đạt môn toán rời rạc” thành các biến mệnh đề ݌,ݍ,ݎ. Như vậy các tiền đề bây giờ trở thành các dạng mệnh đề ݌ଵ = ݌ → ݎ ݌ଶ = ¬ ݍ → ݍ ݌ଷ = ¬ ݎ Ta phải chứng minh dạng mệnh đề sau là một hằng đúng: [ ( ݎ → ݌) ∧ ( ¬ ݍ → ݍ) ∧¬ ݎ] → ݍ Ta có thể kiểm tra dễ dàng dạng mệnh đề trên là một hằng đúng bằng cách lập ra bảng chân trị của nó. Tuy nhiên, đây không phải là một phương pháp tốt nếu số biến mệnh đề lớn. Một phương pháp khác là sử dụng các qui tắc suy diễn để chia bài toán thành ra các bước nhỏ, nghĩa là từ các tiền đề suy ra một số kết luận trung gian trước khi tiếp tục áp dụng các quy tắc suy diễn để suy ra kết luận. Để tiện ra mô hình hóa phép suy điễn thành sơ đồ sau: ݌ଵ ݌ଶ . . . ݌n ݍ

maibaoquat

Dưới đây là một số quy tắc suy diễn thường dùng mà chân lý có thể dược kiểm tra dễ dàng bằng cách lập bảng chân trị. Quy tắc Modus Ponens (Phương pháp khẳng định) Quy tắc này được thể hiện bởi hằng đúng [ ( ݍ → ݌) ݌ ∧] → ݍ (1.3) hoặc dưới dạng sơ đồ ݍ → ݌ ݌  ݍ Ví dụ: Nếu Minh học chăm thì Minh đạt Toán rời rạc Mà Minh học chăm Suy ra Minh đạt Toán rời rạc. Thật ra trong quy tắc Modus Ponens, mệnh đề p→q thường có dạng tổng quát hơn “với bất kỳ sinh viên X nào, nếu X học chăm thì X đạt Toán rời rạc” và ta đã đặc biệt hóa nó cho trường hợp X= sinh viên Minh. Các phép đặc biệt hóa sẽ được xem xét trong phần vị từ và lượng từ. Một ví dụ cổ điển khác của Qui tắc Modus ponens là: Mọi người đều chết mà Socrate là người vậy Socrate sẽ chết. Thường thì quy tắc Modus Ponens được áp dụng cùng với quy tắc thay thế để đơn giản hóa các bước suy luận. Chẳng hạn ta có phép suy diễn ݏ ∨ ݎ ( ݏ ∨ ݎ) → ( ¬ ݑ ∧ ݐ) ݎ → ݌ Ở đây Quy tắc Modus Ponens (dạng mệnh đề 1.3) được áp dụng cùng với phép thay thế ݌ bởi ݏ˅ݎ và q bởi ¬ ݑ˄ݐ. Tam đoạn luận ( Syllogism) được thể hiên bởi hằng đúng ݍ → ݌ ݎ → ݍ ݎ → ݌ Ví dụ: 1.  Hai tam giác vuông có cạnh huyền bằng nhau và một góc nhọn bằng nhau thì chúng có một cạnh bằng nhau kèm giữa hai góc bằng nhau.  Hai tam giác có một cạnh bằng nhau kèm giữa hai góc bằng nhau thì chúng bằng nhau.  Suy ra hai tam giác vuông có cạnh huyền bằng nhau và một góc nhọn bằng nhau thì chúng bằng nhau.

maibaoquat

hay dưới dạng mô hình ݍ → ݌ ¬ ݍ ¬ ݌ Ví dụ: xét chứng minh ݎ → ݌ ݏ → ݎ ∨ ݐ¬ ݏ ¬ ݑ˅ݐ ¬ ݑ ¬ ݌ Ta có thể suy luận như sau: ta thấy các tiền đề ˅ݐ¬ ݏ, ¬ ݑ˅ݐ bởi các dạng mệnh đề tương đương ݒ ݐ → ݏàݑ → ݐ . Khi ấy ݎ → ݌ ݏ → ݎ ݐ → ݏ ݑ → ݐ ݑ → ݌ (Tam đoạn luận lập lại nhiều lần) mà ¬ ݑ ¬ ݌ (Phương pháp phủ định) Tam đoạn luận rời: được thể hiện bởi hằng đúng [ ( ݍ ∨ ݌) ∧¬ ݌] ݍ → Ý nghĩa của quy tắc này là khi chỉ có đúng hai trường hợp có thể xảy ra và một trong hai trường hợp đã được khẳng định là sai thì trường hợp còn lại là đúng. Quy tắc mâu t huẫn ( Chứng minh bằng phản chứng) Ta có tương đương logic [(݌ 1 ฀ ݌ 2 ฀...฀݌n ) → ݍ] ⟺ [(݌ 1 ฀ ݌ 2 ฀...฀݌n ฀¬ݍ) →0] Do đó nếu chứng minh được dạng mệnh đề ở bên phải là một hằng đúng thì dạng mệnh đề ở bên trái cũng là một hằng đúng. Nói cách khác nếu thêm giả thiết phụ ¬ ݍ vào các tiền đề cho trước mà dẫn đến một mâu thuẫn thì q là hệ quả logic của các tiền điền cho trước. Ví dụ: hãy sử dụng phương pháp phản chứng cho chứng minh sau: ݎ → ݌ ¬ ݍ → ݌ ݏ → ݍ ¬ ݏ → ݎ Phủ định của kết luận sẽ tương đương với: ¬ ( ¬ ݏ → ݎ) ⟺ ¬ ( ݏ ∨ ݎ) ⟺¬ ∨ ݎ¬ ݏ

maibaoquat

Như thế ta thêm vào các tiền đề hai giả thiết phụ ¬r và ¬s và tìm cách chứng minh suy luận sau là đúng: ݎ → ݌ ¬ ݍ → ݌ ݏ → ݍ ¬ ݎ ¬ ݏ  0 Ta có các bước sau đây ¬ ݍ → ݌ ݏ → ݍ  ¬ ݏ → ݌ (Tam đoạn luận) mà ¬ ݏ  ¬ ( ¬ ݌) (Phương pháp phủ định) hay tương đương ݌ mà ݎ → ݌ ݎ (Phương pháp khẳng định) Kết luận ݎ cùng với giả thiết phụ ¬ ݎ cho ta: ∧ ݎ¬ ݎ ⟺ 0 Do đó theo phương pháp phản chứng, chứng minh ban đầu là đúng. Quy tắc chứng minh theo trường hợp Quy tắc này được thể hiện bởi hằng đúng sau: [ ( ݎ → ݌) ∧( ݎ → ݍ) ] →[ ( ݍ ∨ ݌) ݎ →] Ý nghĩa của quy tắc này là một giả thiết có thể tách thành hai trường hợp ݌ đúng hay q đúng, và ta đã chứng minh được riêng rẻ cho từng trường hợp là kết luận ݎ đúng, khi ấy ݎ cũng đúng trong cả hai trường hợp. Ví dụ: Để chứng minh rằng ݂( ݊) = ݊ ଷ+ 2݊ luôn chia hết cho 3 ta viết ݂( ݊) = ݊ ( ݊ଶ+ 2) và lấy n là một số nguyên tùy ý. Khi ấy có hai trường hợp xảy ra:  ݊ chia hết cho 3: khi ấy rõ ràng f(n) cũng chia hết cho 3.  ݊ không chia hết cho 3, khi ấy ta có thể viết ݊= 3݇± 1 với một số nguyên k nào đó. Ta có ݊ଶ+ 2 = ( 3݇± 1) ଶ + = 9 ݇ଶ ± 6 ݇+ 3 = 3( 3݇ଶ ± 2 ݇+ 1) Suy ra ݂( ݊) = ݊ ( ݊ 2 + 2) cũng chia hết cho 3. Như vậy trong mọi trường hợp ݂( ݊) chia hết cho 3.

maibaoquat

Ta đặt các biến mệnh đề như sau: ݌: Ông Minh được tăng lương ݍ: Ông Minh xin nghỉ việc ݎ: Vợ ông Minh bị mất việc ݏ: Ông Minh phải bán xe ݐ: Vợ ông Minh đi làm trễ Mô hình suy luận sẽ là ݌ ¬ ݌ → ݍ ( ݎ ∧ ݍ) → ݏ ݐ → ݎ ¬ ݏ → ¬ ݐ Để tìm phản ví dụ ta cần tìm các gái trị của các biến mệnh đề sao cho các tiền đề là đúng trong khi kết luận là sai. Trước hết dể kết luận sai ta cần có ¬ ݏ đúng và ¬ ݐ sai, nghĩa là ݏ sai và ݐ đúng. Khi ấy để cho tiền đề thứ tư đúng r cũng phải đúng. Để tiền đề thứ ba đúng ta cần có q sai. Khi ấy p phải đúng để hai tiền đề đầu là đúng. Tóm lại phản ví dụ ừng với các chân trị của biến là ݌= 1,ݍ= 0,ݎ= 1,ݏ= 0 vàݐ = 1. Đó là trường hợp: Ông Minh được tăng lương (݌= 1) và ông Minh không nghỉ việc (ݍ= 0), vợ ông Minh bị mất việc (ݎ= 1), ông Minh không bán xe (ݏ= 0) và vợ ông Minh hay đi làm trễ (ݐ= 1).

§4 VỊ TỪ VÀ LƯỢNG TỪ

Định nghĩa 1.4: một vị từ là một khẳng định ݌( ݔ,ݕ, ...) trong đó có chứa một số biến ݔ,ݕ, ... lấy giá trị trong những tập hợp cho trước ܣ,ܤ, ... sao cho: i. bản thân ݌( ݔ,ݕ, ...) không phải là mệnh đề ii. nếu thay ݔ,ݕ, ... bằng những phần tử cố định nhưng tùy ý ܽ ∈ ܣ,ܾ ∈ ܤ, ... ta sẽ được một mệnh đề ݌( ܽ,ܾ, ...) , nghĩa là chân trị của nó hoàn toàn xác định. Các biến ݔ,ݕ, ... được nói là biến tự do của vị từ. Ví dụ: ݌( ݊) = “݈ ݊àݕݑ݃݊ ốݏ ݐộ݉ êốݐ ݊” là một vị từ theo một biến tự do ݊ ∈ ࡺ: với ݊= 1, 2, 11 ta được các mệnh đề đúng ݌( 1) ,݌( 2) ,݌( 11) , còn với ݊= 4, 6, 15 ta được các mệnh đề sai ݌( 4) ,݌( 6) ,݌( 15). ݍ( ݔ,ݕ) = “ݕ+ 2,ݕ − ݔ,ݔ+ 2݈ ݕà݊ℎẵܿ ốݏ ” là một vị từ với 2 biến tự do ݔ,ݕ ∈ ࢆ: chẳng hạn ݍ( 4, 2) là một mệnh đề đúng trong khi ݍ( 5, 2) ,ݍ( 4, 7) là những mệnh đề sai. Định nghĩa 1.4: cho trước các vị từ ݌( ݔ) ,ݍ( ݔ) theo một biến ݔ ∈ ܣ. Khi ấy: i. Phủ định của p, ký hiệu ¬p là vị từ mà khi thay x bởi một phần tử ܽ cố định của ܣ thì ta được mệnh đề ¬ ( ݌( ܽ) ) ii. Phép nối liền (tương ứng nối rời, kéo theo...) của ݌ và ݍ, ký hiệu bởi ݍ ∧ ݌ (tương ứng ݍ ∨ ݌, ݍ → ݌,...) là vị từ theo biến ݔ mà khi thay ݔ bởi phần tử cố định ܽ ∈ ܣ ta được mệnh đề ݌( ܽ) ݍ ∧( ܽ) (tương ứng ݌( ܽ) ݍ ∨( ܽ) ,݌( ܽ) ݍ →( ܽ) , ...)

maibaoquat

Giả sử ݌( ݔ) là một vị từ theo biến ݔ ∈ ܣ. Khi ấy có 3 trường hợp có thể xảy ra: Trường hợp 1: khi thay ݔ bởi một phần tử a tùy ý trong ܣ, ta được mệnh đề đúng ݌( ܽ). Trường hợp 2: với một số giá trị ܽ ∈ ܣ thì ݌( ܽ) thì mệnh đề đúng, một số giá trị ܾ ∈ ܣ thì ݌( ܾ) là mệnh đề sai. Trường hợp 3: khi thay ݔ bởi phần tử tùy ý trong ܽ, ta được mệnh đề sai ݌( ܽ). Nếu trường hợp 1 xảy ra thì mệnh đề “với mọi ݔ ∈ ܣ,݌( ݔ) ” là một mệnh đề đúng. Mệnh đề này được ký hiệu bởi ” ∀ݔ ∈ ܣ,݌( ݔ) ”. Như thế mệnh đề này sai nếu trường hợp 2 hay trường hợp 3 xảy ra. Mặt khác nếu trường hợp 1 hay trường hợp 2 xảy ra thì mệnh đề “tồn tại ݔ ∈ ܣ ,݌( ݔ) ” là một mệnh đề đúng. Mệnh đề này được ký hiệu bởi “∃ݔ ∈ ܣ,݌( ݔ) ”. Nếu vậy mệnh đề này sẽ sai nếu trườgn hợp 3 xảy ra. Định nghĩa 1.4: các mệnh đề “∀ݔ ∈ ܣ,݌( ݔ) ” và “∃ݔ ∈ ܣ,݌( ݔ) ” được gọi là lượng từ hóa của vị từ ݌( ݔ) bởi lượng từ phổ dụng (∀) và lượng từ tồn tại (∃). Chú ý:

1. Trong các mệnh đề lượng từ hóa, biến ݔ không còn là tự do nữa. ta nói nó đã bị buộc bởi các lượng từ ∀ hay ∃.
2. Theo nhận xét trên, phủ định của mệnh đề “∀ݔ ∈ ܣ,݌( ݔ) ” là đúng nếu trường hợp 2 hay trường hợp 3 xảy ra. Trường hợp 3 có thể viết lại: khi thay x bởi ܽ ∈ ܣ tùy ý thì ¬ ݌( ܽ) đúng. Như thế nếu trường hợp 2 hay trường hợp 3 xảy ra thì mệnh đề “∃ݔ ∈ ܣ,݌( ݔ) ” là mệnh đề đúng. Nói cách khác, phủ định của mệnh đề “∀x ∈ A, p(x)” là mệnh đề “∃ݔ ∈ ܣ,݌( ݔ) ”. Cũng thế phủ định của mệnh đề “∃ݔ ∈ ܣ,݌( ݔ) ” là mệnh đề “∀ݔ ∈ ܣ,݌( ݔ) ” vì cả hai cùng đúng nếu trường hợp 3 xảy ra và cùng sai nếu trường hợp 1 hay trường hợp 2 xảy ra. Bây giờ ta xem một vị từ theo hai biến ݌( ݔ,ݕ) với ݔ ∈ ܣ,ݕ ∈ ܤ. Khi ấy nếu thay ݔ bằng một phần tử cố định nhưng tùy ý ℎݐ ܣ ∈ ܽì݌ ( ܽ,ݕ) trở thành vị từ theo biến ݕ ∈ ܤ nên ta có thể lượng tử hóa nó theo biến ݕ và được hai mệnh đề “∀ݕ ∈ ܤ,݌( ܽ,ݕ) ” và “∃ݕ ∈ ܤ,݌( ܽ,ݕ) ”. Bằng cách này ta được hai vị từ theo một biến ݔ ∈ ܣ: “∀ݕ ∈ ܤ,݌( ݔ,ݕ) ” và “∃ݕ ∈ ܤ,݌( ݔ,ݕ) ”. Nếu lượng tử hóa chúng ta sẽ được 4 mệnh đề: ∀ݔ ∈ ܣ,∀ݕ ∈ ܤ, ݌( ݔ,ݕ) ∃ݔ ∈ ܣ,∀ݕ ∈ ܤ, ݌( ݔ,ݕ) ∀ݔ ∈ ܣ,∃ݕ ∈ ܤ, ݌( ݔ,ݕ) ∃ݔ ∈ ܣ,∃ݕ ∈ ܤ, ݌( ݔ,ݕ) Đương nhiên ta có thể lượng từ hóa theo biến x trước rồi theo biến y sau để được 4 mệnh đề nữa. Hãy xét một trong các mệnh đề đó:”∀ݕ ∈ ܤ,∀ݔ ∈ ܣ,݌( ݔ,ݕ) ”. Giả sử mệnh đề này đúng. Suy ra mệnh đề “∀ݔ ∈ ܣ,∀ݕ ∈ ܤ,݌( ݔ,ݕ) ” đúng. Rõ ràng điều ngược lại cũng đúng nên ta có mệnh đề đúng [ ∀ݔ ∈ ܣ,∀ݕ ∈ ܤ,݌( ݔ,ݕ) ] ⟷ [ ∀ݕ ∈ ܤ,∀ݔ ∈ ܣ,݌( ݔ,ݕ) ] Tương tự mệnh đề sau cũng đúng: [ ∃ݔ ∈ ܣ,∃ݕ ∈ ܤ,݌( ݔ,ݕ) ] ⟷[ ∃ݕ ∈ ܤ,∃ݔ ∈ ܣ,݌( ݔ,ݕ) ] Hơn nữa ta có

maibaoquat

Định lý 1.4 : phủ định của một mệnh đề lượng từ hóa từ vị từ ݌( ݔ,ݕ, ...) có được bằng cách thay lượng từ ∀ bởi lượng từ ∃ và lượng từ ∃ bởi lượng từ ∀, và vị từ ݌( ݔ,ݕ, ...) bởi phủ định ¬ ݌( ݔ,ݕ, ...). Ví dụ: một hàm thực liên tục tại ݔ଴ࡾ ∈ được định nghĩa bởi: ߝ∀> 0,ߜ∃> 0,ࡾ ∈ ݔ∀,( |ݔ − ݔ଴|< ߜ) ⟶( |݂( ݔ) ݂ −( ݔ଴) |< ߝ) Do đó lấy phủ định theo định lý 1.4 ta sẽ được định nghĩa của hàm không liên tục tại ݔ଴: ߝ∃> 0,ߜ∀> 0,ࡾ ∈ ݔ∃,( |ݔ − ݔ଴|< ߜ) ∨( |݂( ݔ) ݂ −( ݔ଴) |ߝ ≥) Thông thường các định lý trong toán học được phát biểu liên quan đến các mệnh đề lượng từ hóa trong đó có lượng từ phổ dụng. Do đó ngoài các quy tắc suy diễn ta còn sử dụng quy tắc đặc biệt hóa phổ dụng và quy tắc tổng quát hóa phổ dụng. Quy tắc đặc biệt hóa phổ dụng: nếu một mệnh đề đúng có dạng lượng từ hóa trong đó một biến ܣ ∈ ݔ bị buộc bởi lượng từ phổ dụng ∀, khi ấy nếu thay thế ݔ bởi ܣ ∈ ܽ ta sẽ được một mệnh đề đúng. Ví dụ: 1. Khi ta phát biểu “mọi người đều chết”, thực chất là ta đã sử dụng mệnh đề lượng từ hóa: ݔ∀, ( ݈ ݔà݅ườ݃݊ ) ⟶( ݐℎếܿ ẽݏ ݔ) Để áp dụng được phương pháp khẳng định, ta dùng quy tắc đặc biệt háo phổ dụng với ݔ= ݁ݐܽݎܿ݋ܵ (Socrate là người) ⟶ (Socrate sẽ chết) Do đó kết hợp với tiền đề “Socrate là người”, phương pháp khẳng định cho phép kết luận “Socrate sẽ chết”. 2. Trong các định lý tóan học, ví dụ như trường hợp bằng nhau của hai tam giác, khẳng định là một mệnh đề lượng từ hóa phổ dụng cho một cặp tam giác bất kỳ. khi áp dụng ta sẽ đặc biệt hóa cho một cặp tam giác cụ thể nào đó. Bài toán ngược lại là nếu một kết luận có dạng lượng từ hóa phổ dụng thì làm cách nào suy diễn nó từ các tiền đề. Nếu tập hợp tương ứng A là một tập hợp hữu hạn không quá nhiều phần tử, ta có thể dùng phương pháp vét cạn bằng cách thay thế biến ݔ lần lượt bởi các phần tử của A và chứng minh mệnh đề là đúng. Mặt khác nếu A=N ta thường sử dụng nguyên lý quy nạp sẽ trình bày ở §5. Tuy nhiên nếu A vô hạn không đếm được, hay ngay khi A hữu hạn nhưng số phần tử của A quá lớn, các phương pháp trên không sử dụng được và ta phảo sử dụng: Quy tắc tổng quát hóa phổ dụng: nếu trong một mệnh đề lượng từ hóa, khi thay một biến buộc bởi lượng từ ∀ bằng một phần tử cố định nhưng tùy ý của tập hợp tương ứng mà mệnh đề nhận được có chân trị 1 thì bản thân mệnh đề lượng từ hóa ban đầu cũng có chân trị 1. Ví dụ: Khi giải phương trình 4 − ݔ5 = 15 ta lý luận như sau: Giả sử 4 − ݔ5 = 15 , khi ấy 4 ݔ= 20 Giả sử 4 ݔ= 20 , khi ấyݔ = 5 Như vậy nếu 4 − ݔ5 = 15 thì ݔ= 5

maibaoquat

Nếu gọi ݌( ݔ) ,ݍ( ݔ) ,ݎ( ݔ) là các vị từ “ 4 − ݔ5 = 15”, “ 4 ݔ= 20”, “ݔ= 5” thì lý luận trên có dạng

ݔ∀,݌( ݔ) ݍ ⟶( ݔ)

ݔ∀,ݍ( ݔ) ݎ ⟶( ݔ) (1.4)

∴ ∀ݔ,݌( ݔ) ݎ ⟶( ݔ)

Sự đúng đắn của lý luận trên được cho bởi Định lý 1 .4: gọi ݌( ݔ) ,ݍ( ݔ) ,ݎ( ݔ) là các vị từ theo một biến ܣ ∈ ݔ, khi ấy suy luận 1.4 là đúng. Muốn vậy ta đặc biệt hóa hai tiền đề và được hai mệnh đề đúng

݌( ܽ) ݍ →( ܽ) ݍ( ܽ) ݎ →( ܽ) Suy ra ݌( ܽ) ݎ →( ܽ) theo tam đoạn luận. Do đó quy tắc tổng quá hóa phổ dụng cho phép kết luận ݔ∀,݌( ݔ) ݍ →( ݔ) là một mệnh đề đúng. Ví dụ: Gọi ݂,݃ là 2 hàm thực Giả sử ݂( ݔ) liên tục tại ݔ= ݔ଴ và ݃( ݕ) liên tục tại ݕ= ݕ଴= ݂( ݔ଴). Khi ấy ℎ( ݔ) = ( ∘ ݃ ݂) ( ݔ) liên tục tại ݔ= ݔ଴. Suy luận cần chứng minh có dạng: ߝ∀> 0,ߜ∃> 0,ݔ∀, ( |ݔ − ݔ଴|< ߜ) →( |݂( ݔ) ݂ −( ݔ଴) |< ߝ) ߝ∀> 0,ߟ∃> 0,ݕ∀, ( |ݕ − ݕ଴|< ߟ) →( |݃( ݕ) ݃ −( ݕ଴) |< ߝ) ∴ ∀ߝ> 0,ߜ∃> 0,ݔ∀, ( |ݔ − ݔ଴|< ߜ) →( |݂ ∘ ݃( ݔ) − ݃∘ ݂( ݔ଴) |< ߝ) Sử dụng phép tổng quát hóa phổ dụng ta ߝ bởi một số dương cố định nhưng tùy ý. Để tiện ta sẽ dùng cùng ký hiệu ߝ dể chỉ số cố định trên. Khi ấy ta cần tìm ߜ> 0 dể cho mệnh đề sau là đúng ݔ∀, ( |ݔ − ݔ଴|< ߜ) →( |݂ ∘ ݃( ݔ) − ݃∘ ݂( ݔ଴) |< ߝ) Dùng phép đặc biệt hóa phổ dụng cho tiền đề thứ hai với ߝ> 0 như trên, ta sẽ tìm được ߟ> 0 sao cho: ݕ∀,( |ݕ − ݕ଴|< ߟ) →( |݃( ݕ) ݃ −( ݕ଴) |< ߝ) (1.4) Tiếp theo, ta đặc biệt hóa ߝ bởi ߟ vừa tìm được cho tiền đề thứ nhất và tìm được ߜ> 0 sao cho: ݔ∀, ( |ݔ − ݔ଴|< ߜ) →( |݂( ݔ) ݂ −( ݔ଴) |< ߟ) (1.4) Thay ݔ bởi số thực tùy ý mà ta vẫn ký hiệu làݔ thì 1.4 được đặc biệt hóa bởi ( |ݔ − ݔ଴|< ߜ) →( |݂( ݔ) ݂ −( ݔ଴) |< ߟ) (1.4) Khi ấy ta đặc biệt hóa 1.4 với ݕ= ݂( ݔ) ta được ( |݂( ݔ) ݕ −଴|< ߟ) →( |݂ ∘ ݃( ݔ) − ݃∘ ݂( ݔ଴) |< ߝ) (1.4) Áp dụng Tam đoạn luận cho 1.4 và 1.4 ta được