Cơ sở logic | Tóm tắt lý thuyết Toán rời rạc | Đại học Ngoại Ngữ Tin Học TP Hồ Chí Minh

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.1)

hoặc dưới dạng sơ đồ

𝑝 → 𝑞

𝑝

∴𝑞

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.1) đượ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.

2. Xét tam đoạn luận

Một con ngựa rẻ thì hiếm

Cái gì hiếm thì đắt

Suy ra một con ngựa rẻ thì đắt

Tam đoạn luân trên hoàn toàn hợp logic. Tuy nhiên kết luận mâu thuẫn là do dựa trên một tiền đề sai.

3. Ta hãy xét một ví dụ trong đó có sử dụng cả hai quy tắc trên

Bình đi chơi thì Bình không học Toán rời rạc

Bình không học Toán rời rạc thì Bình trượt Toán rời rạc

Mà Bình thích đi chơi

Vậy Bình trượt Toán rời rạc.

Nếu trừu tượng hóa các med nguyên thủy thành các biến mệnh đề p, q, r thì lý luận trên có dạng

𝑝 → ¬ 𝑞

¬ 𝑞 → 𝑟

𝑝

\ 𝑟

Ta có thể suy luận như sau:

𝑝 → ¬ 𝑞

¬ 𝑞 → 𝑟

\𝑝 → 𝑟 (Tam đoạn luận)

mà

𝑝

\𝑟 (Modus Ponens)

Hoặc là

𝑝 → ¬ 𝑞

𝑝

¬ 𝑞 (Modus Ponens)

Mà

¬ 𝑞 → 𝑟

\𝑟 (Modus Ponens)

Quy tắc Modus Tollens (Phương pháp phủ định)

Phương pháp này được thể hiện bởi hằng đúng

[ ( 𝑝 → 𝑞) 𝗏 ¬ 𝑞] → ¬ 𝑝

hay dưới dạng mô hình

𝑝→ 𝑞

¬ 𝑞

 𝑝 → 𝑟

𝑟 → 𝑠

𝑡 𝗏 ¬ 𝑠

¬ 𝑡˅𝑢

¬ 𝑢

\¬ 𝑝

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 thuẫn ( Chứng minh bằng phản chứng)

Ta có tương đương logic

[($p_1$฀ $p_2$฀ …𝑝_n ) → q] $\iff$ [($p_1$฀ $p_2$ ฀…฀$p_n$ ฀¬q) →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:

¬ ( ¬ 𝑟 → 𝑠) ⟺  ¬ ( 𝑟 𝗏 𝑠)  ⟺ ¬ 𝑟 𝗏 ¬ 𝑠

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 ƒ( 𝑛) =  𝑛3 + 2𝑛 luôn chia hết cho 3 ta viết ƒ( 𝑛)  =  𝑛( 𝑛2 + 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) ² + 2 =  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.

Ta hãy xem một ví dụ trong đó có sử dụng nhiều quy tắc:

• Nếu nghệ sĩ Văn Ba không trình diễn hay số vé bán ra ít hơn 50 thì đêm diễn sẽ bị hủy bỏ và ông bầu rất buồn.
• Nếu đêm biểu diễn bị hủy bỏ thì phải trả lại tiền vé cho người xem.
• Nhưng tiền vé đã không được trả lại cho người xem.
• Vậy nghệ sĩ Văn Ba có trình diễn.

Ta thay các mệnh đề nguyên thủy bằng các biến mệnh đề

𝑝: “nghệ sĩ Văn Ba đã trình diễn”

𝑞: “số vé bán ra ít hơn 50”

𝑟: “đêm diễn sẽ bị hủy bỏ”

𝑡: “trả lại tiền vé cho người xem”

Khi ấy lý luận cần chứng minh là

( ¬ 𝑝 𝗏 𝑞) →  ( 𝑟 𝖠 𝑠)

𝑟 →  𝑡

¬𝑡

\𝑝

Suy luận trên có thể được thực hiên theo các bước sau:

¬ 𝑝 𝗏 𝑞  →  𝑟 𝖠 𝑠              (Tiền đề)

𝑟 𝖠 𝑠  → 𝑟                         (hằng đúng gọi là phép đơn giản nối liền)

𝑟  →  𝑡                               (Tiền đề)

Phản ví dụ

Bây giờ ta hãy xem một bài toán ngược: khi nào một chứng minh (suy luận) là sai, nghĩa là phải kiểm tra (𝑝1 𝑝2 ฀…$p_n$ ฀¬ q) → 𝑞 không phải là một hằng đúng. Nói cách khác tìm các chân trị của biến mệnh đề làm cho các tiền đề đều đúng trong khi kết luận q là sai. Ta nói ví dụ dẫn đến các giá trị của biến mệnh đề như trên là một phản ví dụ của định lý cần chứng minh.

Ví dụ: hãy tìm phản ví dụ cho suy luận dưới đây

Ông Minh đã khẳng định rằng nếu không được tăng lương thì ông ta sẽ xin nghĩ việc. Mặt khác nếu ông ta nghỉ việc mà vợ ông ta bị mất việc thì phải bán xe. Biết rằng nếu vợ ông Minh hay đi làm trễ thì sẽ mất việc và cuối cùng ông Minh đã được tăng lương. Suy ra nếu ông Minh không bán xe thì vợ ông ta không đi làm trễ.

Ta đặt các biến mệnh đề như sau:

Định nghĩa 1.4.1:

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.2:

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 𝑝( 𝑎) 𝗏 𝑞( 𝑎) , 𝑝( 𝑎) → 𝑞( 𝑎) , …)

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.2:

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ó

Định lý 1.4.1: nếu 𝑝( 𝑥, 𝑦) là một vị từ theo 2 biến 𝑥, 𝑦 thì các mệnh đề sau là đúng

i. [ ∀𝑥 ∈ 𝐴, ∀𝑦 ∈ 𝐵, 𝑝( 𝑥, 𝑦) ] ⟷ [ ∀𝑦 ∈ 𝐵, ∀𝑥 ∈ 𝐴, 𝑝( 𝑥, 𝑦) ] và [ ∃𝑥 ∈ 𝐴, ∃𝑦 ∈ 𝐵, 𝑝( 𝑥, 𝑦) ] ⟷ [ ∃𝑦 ∈ 𝐵, ∃𝑥 ∈ 𝐴, 𝑝( 𝑥, 𝑦) ]

ii. [ ∃𝑥 ∈ 𝐴, ∀𝑦 ∈ 𝐵, 𝑝( 𝑥, 𝑦) ] ⟷ [ ∀𝑦 ∈ 𝐵, ∃𝑥 ∈ 𝐴, 𝑝( 𝑥, 𝑦) ]

“∀𝑦 ∈ 𝐵, 𝑝( 𝑎, 𝑦) ” là đúng, nghĩa là nếu thay 𝑦 =   𝑏 ∈ 𝐵 tùy ý thì 𝑝( 𝑎, 𝑏) đúng. Như vậy với

𝑦 = 𝑏 ∈ 𝐵 tùy ý ta có thể chọn 𝑥 = 𝑎 để khẳng định rằng “∃𝑥 ∈ 𝐴, 𝑝( 𝑥, 𝑏) ” là đúng.

Do đó “∀𝑦 ∈ 𝐵, ∃𝑥 ∈ 𝐴, 𝑝( 𝑥, 𝑦) ” là một mệnh đề đúng.

Chú ý: mệnh đề đảo của ii không nhất thiết đúng trong trường hợp tổng quát. Thật vậy ta hãy xem một ví dụ

Gọi 𝑝( 𝑥, 𝑦) là vị từ theo hai biến thực:

“𝑥 +  𝑦  =  1”

Ta nhận xét rằng nếu thay y=b là một số thực tùy ý thì ta có thể chọn 𝑥 = 1 − 𝑏 để cho x + b = 1 nên mệnh đề “∃𝑥 ∈ 𝑅, 𝑥 + 𝑏 = 1” là đúng. Điều này chứng tỏ mệnh đề “∀𝑦 ∈ 𝑅, ∃𝑥 ∈ 𝑅, 𝑥 + 𝑦 = 1” đúng. Ngược lại nếu thay 𝑥 = 𝑎 tùy ý, ta có thể chọn 𝑦 =   −𝑎 để cho 𝑎 +   𝑦   =   0 ≠   1 nên mệnh đề “∀𝑦 ∈ 𝑅, 𝑎 +   𝑦   =   1” là sai. Điều này chứng tỏ mệnh đề “∃𝑥 ∈ 𝑅, ∀𝑦 ∈ 𝑅, 𝑥 + 𝑦 = 1” là sai. Do đó phép kéo theo sau là sai:

( ∀𝑦 ∈ 𝑅, ∃𝑥 ∈ 𝑅, 𝑥 + 𝑦 = 1) ⟶ ( ∃𝑥 ∈ 𝑅, ∀𝑦 ∈ 𝑅, 𝑥 + 𝑦 = 1)

Các kết quả trên đây có thể được mở rộng dễ dàng cho các vị từ theo nhiều biến tự do. Đặc biệt ta có:

Định lý 1.4.2: trong một mệnh đề lượng từ hóa từ một vị từ theo nhiều biến độc lập nếu ta hoán vị hai lượng từ đứng cạnh nhau thì

Mệnh đề mới vẫn còn tương đương logic với mệnh đề cũ nếu hai lượng từ này cùng loại

Mệnh đề mới sẽ là một hệ quả logic của mệnh đề cũ nếu hai lượng từ trước khi hoán vị có dạng ∃∀.

Ví dụ: một hàm thực liên tục đều trên một khoảng 𝐼⊂ 𝑅 được định nghĩa bởi mệnh đề:

∀s > 0, ∃ð > 0, ∀𝑥 ∈ 𝐼, ∀𝑥′ ∈ 𝐼, ( |𝑥 − 𝑥′| < ð) ⟶ ( |ƒ( 𝑥) − ƒ′( 𝑥) | <  s)

Theo mệnh đề 1.4.2 thì mệnh đề trên có hệ quả logic là

∀s > 0, ∀𝑥 ∈ 𝐼, ∃ð >  0, ∀𝑥′ ∈ 𝐼, ( |𝑥 − 𝑥′| <  ð) ⟶ ( |ƒ( 𝑥) − ƒ′( 𝑥) | <  s)

hay tương đương

∀𝑥 ∈ 𝐼, ∀s > 0, ∃ð >  0, ∀𝑥′ ∈ 𝐼, ( |𝑥 − 𝑥′| <  ð) ⟶ ( |ƒ( 𝑥) − ƒ′( 𝑥) | <  s)

Nói cách khác một hàm liên tục đều trên I thì liên tục.

Để lấy phủ định một mệnh đề lượng từ hóa, chú ý 2 của định nghĩa 1.4.3 có thể được mở rộng thành

Định lý 1.4.3 :

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 𝑥0 ∈ 𝑅 được định nghĩa bởi:

∀s > 0, ∃ð > 0, ∀𝑥 ∈ 𝑅, ( |𝑥 − 𝑥0| < ð) ⟶ ( |ƒ( 𝑥) − ƒ( 𝑥0) | < s)

Do đó lấy phủ định theo định lý 1.4.3 ta sẽ được định nghĩa của hàm không liên tục tại 𝑥₀:

∃s > 0, ∀ð >  0, ∃𝑥 ∈ 𝑅, ( | 𝑥 − 𝑥0| <  ð) 𝗏 ( |ƒ( 𝑥) − ƒ( 𝑥0) | ≥ s)

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:

∀𝑥,( 𝑥 𝑙à 𝑛𝑔ười) ⟶ ( 𝑥 𝑠ẽ 𝑐ℎế𝑡)

Để á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 𝑥 = 𝑆o𝑐𝑟𝑎𝑡e

(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

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

∀𝑥, 𝑝( 𝑥) ⟶ 𝑞( 𝑥)

∀𝑥, 𝑞( 𝑥) ⟶ 𝑟( 𝑥)                                                 

∴ ∀𝑥, 𝑝( 𝑥) ⟶ 𝑟( 𝑥)

Sự đúng đắn của lý luận trên được cho bởi

Định lý 1.4.4:

Gọi 𝑝( 𝑥) , 𝑞( 𝑥) , 𝑟( 𝑥) là các vị từ theo một biến 𝑥 ∈ 𝐴, khi ấy suy luận 1.4.1 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 𝑥 = 𝑥0. Suy luận cần chứng minh có dạng:

∀s >  0, ∃ð > 0, ∀𝑥, ( |𝑥 − 𝑥₀| <  ð) → ( |ƒ( 𝑥) − ƒ( 𝑥₀) | <  s)

∀s > 0, ∃5 > 0, ∀𝑦, ( |𝑦 − 𝑦₀| < 5) → ( |𝑔( 𝑦) − 𝑔( 𝑦₀) | < s)

∴ ∀s > 0, ∃ð > 0, ∀𝑥, ( | 𝑥 − 𝑥₀| < ð) → ( |𝑔 ∘ ƒ( 𝑥) − 𝑔 ∘ ƒ( 𝑥₀) | < s)

Sử dụng phép tổng quát hóa phổ dụng ta s bởi một số dương cố định nhưng tùy ý. Để tiện ta sẽ dùng cùng ký hiệu s dể chỉ số cố định trên. Khi ấy ta cần tìm ð > 0 dể cho mệnh đề sau là đúng

∀𝑥, ( |𝑥 − 𝑥₀| < ð) → ( |𝑔 ∘ ƒ( 𝑥) − 𝑔 ∘ ƒ( 𝑥₀) | <  s)

Dùng phép đặc biệt hóa phổ dụng cho tiền đề thứ hai với s > 0 như trên, ta sẽ tìm được 5 > 0 sao cho:

∀𝑦,( |𝑦 − 𝑦₀| < 5) → ( |𝑔( 𝑦) − 𝑔( 𝑦₀) | < s)     ( 1.4.2)               

Tiếp theo, ta đặc biệt hóa s bởi 5 vừa tìm được cho tiền đề thứ nhất và tìm được $\partial$ > 0 sao cho:

∀𝑥,( |𝑥 − 𝑥₀| <  ð) → ( |ƒ( 𝑥) − ƒ( 𝑥₀) | < 5        ( 1.4.3)                                             

Thay 𝑥 bởi số thực tùy ý mà ta vẫn ký hiệu là 𝑥 thì 1.4.3 được đặc biệt hóa bởi

( |𝑥 − 𝑥₀| <  ð) → ( |ƒ( 𝑥) − ƒ( 𝑥₀) | <  5)   ( 1.4.4)

Khi ấy ta đặc biệt hóa 1.4.2 với y = f(x) ta được

( |ƒ( 𝑥) − 𝑦₀| <  5) → ( | 𝑔 ∘ ƒ( 𝑥) − 𝑔 ∘ ƒ( 𝑥₀) | <  s)    ( 1.4.5)

áp dụng tam đoạn luận cho 1.4.4 và 1.4.5 ta được

( |𝑥 − 𝑥₀| <  ð) → ( | 𝑔 ∘ ƒ( 𝑥) − 𝑔 ∘ ƒ( 𝑥₀) | <  s)

Do đó theo phương pháp tổng quát hóa phổ dụng ta có

∀𝑥, ( |𝑥 − 𝑥₀| < ð) → ( |𝑔 ∘ ƒ( 𝑥) − 𝑔 ∘ ƒ( 𝑥₀) | <  s)

Áp dụng một lần nữa phương pháp tổng quát hóa phổ dụng ta thấy mệnh đề sau là

∀s > 0, ∃ð > 0, ∀𝑥,( |𝑥 − 𝑥₀| < ð) → ( |𝑔 ∘ ƒ( 𝑥) − 𝑔 ∘ ƒ( 𝑥₀) | < s)

nghĩa là làm 𝑔 ∘ ƒ liên tục tại 𝑥 = 𝑥₀.

NGUYÊN LÝ QUY NẠP

Trong nhiều trường hợp, quy tắc tổng quát hóa phổ dụng không cho kết quả, ngay cả với các vị từ mà biến tự do thuộc N. Tuy nhiên đối với các vị từ này ta có một công cụ rất mạnh là:

Nguyên lý quy nạp: Mệnh đề ∀𝑛 ∈ 𝑁, 𝑝( 𝑛) là hệ quả của

𝑝( 0) 𝖠 [ ∀𝑛 ∈ 𝑁, 𝑝( 𝑛) → 𝑝( 𝑛 + 1)]

Chú ý:

Theo ngôn ngữ thông thường ta nói: giả sử 𝑝( 0) đúng và nếu 𝑝( 𝑛) đúng thì 𝑝( 𝑛 + 1) cũng đúng, khi ấy suy ra 𝑝( 𝑛) đúng với 𝑛 ∈ 𝑁 tùy ý.

Nguyên lý này có thể bắt đầu từ 𝑛0 ∈ 𝑁: nghĩa là

[𝑝( 𝑛0) 𝖠 [ ∀𝑛 ≥ 0, 𝑝( 𝑛) → 𝑝( 𝑛 + 1)]] → [ ∀𝑛 ≥ 𝑛0, 𝑝( 𝑛) ]

Ví dụ: xét vị từ 𝑝( 𝑛) :

0 + 1 + ⋯ + 𝑛 = $\frac{n(n+1)}{2}$

Trước hết 𝑝( 0) đúng vì nó có dạng:

$0=\frac{0\times 1}{2}$

Để chứng minh ∀𝑛, 𝑝( 𝑛) → 𝑝( 𝑛 + 1) ta dùng phép tổng quát hóa phổ dụng, thay 𝑛 bởi , một số nguyên tùy ý và chứng minh 𝑝( 𝑛) → 𝑝( 𝑛 + 1). Muốn vậy giả sử 𝑝( 𝑛) đúng:

Khi ấy

0 + 1 + ⋯ + 𝑛 = $\frac{n(n+1)}{2}$

0 + 1 + ⋯ + 𝑛 + 𝑛 + 1 = $\frac{n(n+1)}{2}+n+1=\frac{(n+1)(n+2)}{2}$

nghĩa là 𝑝( 𝑛 + 1) đúng. Do đó theo nguyên lý quy nạp “∀𝑛, 𝑝( 𝑛) ” là một mệnh đề đúng.

Áp dụng: để kiểm tra một chương trình máy tính có chạy đúng ý định cuả người thiết kế khôn, ta thường tạo ra các số liệu giả định để chạy thử (Test). Thật ra phương pháp này không thể khẳng định chắc chắn rằng chương trình chạy có đúng không. Hơn nữa trong nhiều trường hợp, ví dụ như khi chương trình đang xét là một bộ phận của chương trình lớn mà dữ liệu chỉ có thể sinh ra từ chương trình lớn, thì khi ấy ta không thể tạo ra dữ liệu giả dể chạy chuong trình con được. May mắn là trong một số trường hợp ta có thể sử dụng công cụ toán học để chứng minh rằng chương trình khi chạy sẽ luôn cho ra kết quả mong muốn. Một trong những công cụ đó là ngyên lý quy nạp như ví dụ dưới đây cho thấy