Tài liệu Logic toán và cơ sở logic của kiến thức môn toán trung học phổ thông

MỞ ĐẦU ........................................................................................................... 2 1. Lí do chọn đề tài ......................................................................................... 3 2. Mục đích nghiên cứu................................................................................... 3 3. Nhiệm vụ nghiên cứu .................................................................................. 3 4. Giả thiết khoa học ....................................................................................... 4 5. Đối tƣợng nghiên cứu ................................................................................. 4 6. Phƣơng pháp nghiên cứu ............................................................................. 4 7. Đóng góp của khóa luận .............................................................................. 4 8. Cấu trúc của khóa luận ................................................................................ 4 Chƣơng 1. SƠ LƢỢC VỀ LOGIC TOÁN XÂY DỰNG THEO NGỮ NGHĨA . 4 1.1. Đại số mệnh đề ...................................................................................... 5 1.1.1. Mệnh đề và các phép toán mệnh đề.................................................... 5 1.1.2. Công thức của đại số mệnh đề ......................................................... 10 1.1.3. Các quy tắc suy luận của đại số mệnh đề. ........................................ 17 1.2. Đại cƣơng về đại số vị từ....................................................................... 18 1.2.1. Vị từ và các phép toán vị từ ............................................................. 20 1.2.2. Công thức của đại số vị từ................................................................ 21 1.2.3. Các quy tắc suy luận của đại số vị từ ............................................... 22 1.3. Cơ sở logic toán trong môn Toán phổ thông........................................... 23 1.3.1. Một số yếu tố logic toán trong môn Toán tiểu học ........................... 23 1.3.2. Kiến thức logic toán trong môn Toán trung học cơ sở...................... 23 1.3.3. Kiến thức logic toán trong môn Toán trung học phổ thông .............. 24 1.3.4. Vấn đề chứng minh các kết luận trong môn Toán trung học phổ thông .................................................................................................................. 25 1.3.5. Vấn đề phát triển tƣ duy logic cho hoc sinh ..................................... 26 Chƣơng 2: GIỚI THIỆU LÔGIC TOÁN XÂY DỰNG BẰNG PHƢƠNG PHÁP TIÊN ĐỀ .......................................................................................................... 30 2.1. Giới thiệu hệ toán mệnh đề. ................................................................... 30 2.1.1. Kí hiệu nguyên thủy và quy tắc xây dựng công thức. ....................... 30 1 2.1.2. Các tiên đề. ..................................................................................... 31 2.2. Giới thiệu hệ toán vị từ........................................................................... 32 2.2.1. Các kí hiệu nguyên thủy và quy tắc xây dựng công thức. ................ 32 2.2.2. Các tiên đề và các quy tắc dẫn ra công thức đúng. .......................... 33 2.3. Phƣơng pháp tiên đề với việc xây dựng các lý thuyết toán học. ............. 33 2.3.1. Sơ lƣợc lịch sử ra đời của phƣơng pháp tiên đề. ............................... 33 2.3.2. Hệ tiên đề của một số lí thuyết toán học. .......................................... 35 2.3.3. Các hệ tiên đề đƣợc dùng để xây dựng kiến thức hình học ở trƣờng phổ thông. .................................................................................................. 40 KẾT LUẬN ..................................................................................................... 46 TÀI LIỆU THAM KHẢO.............................................................................. 47 2 MỞ ĐẦU 1. Lí do chọn đề tài Phong trào cải cách giáo dục toán học đƣợc khởi xƣớng từ đầu thể kỉ XX đã đặt ra vấn đề phải làm giảm khoảng cách giữa nội dung môn Toán trong nhà trƣờng với thành tựu phát triển của Toán học. Một số nhà lí luận dạy học đã đƣa ra ý kiến cho rằng: cần phải đƣa một số kiến thức toán học hiện đại vào giảng dạy trong các trƣờng phổ thông. Tuy nhiên, thực tiễn giáo dục đã cho thấy mọi sự cố gắng cải cách một cách triệt để nội dung dạy học môn Toán trong các trƣờng phổ thông đều không mang lại hiệu quả. Từ thực tế đó, xu hƣớng chung đƣợc mọi ngƣời thừa nhận là nội dung môn Toán ở trƣờng phổ thông chủ yếu vẫn bao gồm các tri thức toán học truyền thống nhƣng cần đƣợc trình bày dƣới sự soi sáng của toán học hiện đại. Với quan điểm đó không cần đƣa nhiều kiến thức toán hiện đại vào chƣơng trình dạy học mà vẫn làm cho kiến thức môn Toán tiếp cận đƣợc với xu thế phát triển của Toán học. Với cƣơng vị là một sinh viên chuyên ngành Sƣ phạm Toán sắp rời giảng đƣờng đại học cùng lòng yêu thích bộ môn, tôi muốn đóng góp công sức nhỏ bé của mình giúp bạn đọc nắm vững nội dung, mối liên hệ logic giữa Toán phổ thông với toán học Cao cấp. Chính điều đó đã thôi thúc tôi làm khóa luận với đề tài: “Logic Toán và cơ sở logic của kiến thức môn Toán Trung học phổ thông”. 2. Mục đích nghiên cứu - Tìm hiểu mối liên hệ logic toán phổ thông với toán cao cấp cho sinh viên ĐHSP Toán trƣờng Đại học Tây Bắc. - Nâng cao sự hiểu biết và hiệu quả học tập của bản thân. 3. Nhiệm vụ nghiên cứu Trình bày kiến thức cơ sở về logic Toán và những yếu tố của logic toán có mặt trong hệ thống kiến thức môn toán Trung học phổ thông. 3 4. Giả thiết khoa học Nếu sinh viên có thể nắm vững các kiến thức Toán cao cấp và hiểu rõ mối liên hệ của nó với các kiến thức Toán Phổ thông thì họ có thể giảng dạy tốt hơn sau khi ra trƣờng. 5. Đối tƣợng nghiên cứu - Nghiên cứu nội dung môn toán cao cấp đã đƣợc dạy ở trƣờng Đại học Tây Bắc. - Nghiên cứu nội dung, mối liên hệ logic toán và cơ sở logic Toán của kiến thức môn toán phổ thông. 6. Phƣơng pháp nghiên cứu - Nghiên cứu tài liệu. - Phân tích, tổng hợp các kiến thức. - Kinh nghiệm bản thân, trao đổi thảo luận với giáo viên hƣớng dẫn. 7. Đóng góp của khóa luận Khóa luận sau khi hoàn thành sẽ làm tài liệu tham khảo cho sinh viên chuyên ngành Toán trƣờng Đại học Tây Bắc. 8. Cấu trúc của khóa luận Khóa luận gồm phần mở đầu, phần nội dung gồm 2 chƣơng và phần kết luận. Phần nội dung bao gồm các chƣơng sau: Chƣơng 1: Sơ lƣợc về logic toán xây dựng theo ngữ nghĩa. Chƣơng 2: Giới thiệu logic toán xây dựng bằng phƣơng pháp tiên đề. 4 Chƣơng 1. SƠ LƢỢC VỀ LOGIC TOÁN XÂY DỰNG THEO NGỮ NGHĨA Nghiên cứu logic toán thông qua ngữ nghĩa là chúng ta dựa vào nội dung các phát biểu và đối chiếu với thực tiễn để khẳng định tính đúng hay sai của phát biểu đó. Trình bày logic toán theo ngữ nghĩa bao gồm hai phần chính là đại số mệnh đề và đại số vị từ. Sau đây chúng ta sẽ tìm hiểu một cách sơ lƣợc về hai phần này để có những hiểu biết cơ bản về logic toán giúp cho việc phân tích các yếu tố logic toán trong kiến thức môn Toán phổ thông. 1.1 . Đại số mệnh đề 1.1.1. Mệnh đề và các phép toán mệnh đề 1.1.1.1. Khái niệm mệnh đề Đại số mệnh đề bắt đầu với khái niệm mệnh đề. Đó là những phát biểu mà ta có thể xác định đƣợc nó đúng hay sai. Một mệnh đề chỉ đúng hoặc sai mà không thể vừa đúng vừa sai. Việc phân định đúng hay sai là dựa vào nội dung phát biểu và đối chiếu với thực tiễn. Chú ý rằng, thực tiễn nói đến ở đây bao gồm thực tiễn trong đời sống sinh hoạt bình thƣờng và cả thực tiễn khoa học, tức là những tri thức khoa học đã đƣợc xác định. Vậy, mệnh đề là một khẳng định có tính đúng hoặc sai. Không có mệnh đề vừa đúng vừa sai, những câu cảm thán, những câu nghi vấn, câu mệnh lệnh,… không là mệnh đề. Để kí hiệu các mệnh đề ta dùng các chữ cái a, b, c,... Trong đại số mệnh đề, ngƣời ta không quan tâm đến cấu trúc ngữ pháp của các mệnh đề mà chỉ quan tâm đến tính “đúng” hoặc “sai". Nhƣ vậy, ngữ nghĩa ở đây chỉ đƣợc sử dụng để xác định giá trị đúng hay sai của mệnh đề (thƣờng đƣợc gọi là giá trị chân lí của mệnh đề). Nếu a là mệnh đề đúng thì ta nói nó có giá trị chân lí bằng 1 , kí hiệu là G(a )  1 , nếu b là mệnh đề sai thì ta nói nó có giá trị chân lí bằng 0, kí hiệu là G(b)  0 . Chẳng hạn, các câu: +) “Hà Nội là thủ đô của nƣớc Việt Nam” là mệnh đề đúng. 5 +) “1 lớn hơn 2” là mệnh đề sai. +) “15 là số lẻ” là mệnh đề đúng. Các câu: “2 nhân 2 bằng mấy?” ; “Anh tốt nghiệp phổ thông năm nào?” ; “Bộ phim này hay quá”, đều không phải là mệnh đề. Chú ý: 1. Trong thực tế ta gặp những mệnh đề mở mà giá trị đúng, sai của nó phụ thuộc vào những điều kiện nhất định (thời gian, địa điểm). Nó đúng ở thời gian, địa điểm này nhƣng sai ở thời gian, địa điểm khác. Song ở bất kì thời điểm nào, địa điểm nào nó cũng luôn có giá trị chân lí đúng hoặc sai. Chẳng hạn: +) Sinh viên năm thứ nhất đang tập quân sự. +) Năng suất lúa năm nay cao hơn năm ngoái. +) 12 giờ trƣa hôm nay tôi đang ở Hà Nội. 2. Để kí hiệu a là mệnh đề “ 2  3  5 ” ta viết : a  "2  3  5" 3. Ta thừa nhận các luật sau đây của logic mệnh đề: a) Luật bài trung: Mỗi mệnh đề phải hoặc đúng hoặc sai, không có mệnh đề nào không đúng cũng không sai. b) Luật mâu thuẫn (hay còn gọi là luật phi mâu thuẫn): Không có mệnh đề nào vừa đúng lại vừa sai. 1.1.1.2. Các phép toán mệnh đề a) Phép phủ định Phủ định của mệnh đề a là một mệnh đề, kí hiệu a , đúng khi a sai và sai khi a đúng. Bảng giá trị chân lí của phép phủ định đƣợc cho bởi bảng sau: a a 1 0 0 1 Ví dụ: +) Mệnh đề a  “Số 30 chia hết cho 4” ta thiết lập đƣợc mệnh đề a = “Số 30 không chia hết cho 4”. +) Mệnh đề b  “Nhôm là một kim loại” ta thiết lập đƣợc mệnh đề 6 b = “Nhôm không phải là kim loại”. Chú ý: Phủ định của một mệnh đề có nhiều cách diễn đạt khác nhau, chẳng hạn: “Nhôm không phải là kim loại” “Không phải nhôm là kim loại” “Nói nhôm là kim loại không đúng”. b) Phép hội Hội của hai mênh đề a , b là một mệnh đề c , đọc là a và b , kí hiệu c  a  b , đúng khi cả hai mệnh đề a , b cùng đúng và sai trong các trƣờng hợp còn lại. Bảng giá trị chân lí của phép hội nhƣ sau: a b c  a b 1 1 1 1 0 0 0 1 0 0 0 0 Ví dụ: Từ hai mệnh đề: a = “Mỗi năm có 12 tháng”, b = “Mỗi năm có 4 mùa” ta thiết lập mệnh đề c = “Mỗi năm có 12 tháng và 4 mùa” Mệnh đề c là hội của hai mệnh đề a và b đã cho. Chú ý: 1. Đề thiết lập hội của hai mệnh đề a , b ta ghép hai mệnh đề đó bởi liên từ “và” hay bởi liên từ khác cùng loại. Những liên từ đó là: mà, song, đồng thời, vẫn… hoặc dấu phẩy hoặc không dùng liên từ gì. 2. Phép hội có tính chất giao hoán, tính chất kết hợp và có p  p  p ; p 1  p ; p  0  0 ; p  p  0 . c) Phép tuyển Tuyển của hai mệnh đề a ; b là một mệnh đề c , đọc là a hoặc b , kí hiệu c  a  b , đúng khi ít nhất một trong hai mệnh đề a , b là đúng và sai khi cả hai mệnh đề a , b cùng sai. Bảng giá trị chân lí của phép tuyển 7 a b c 1 1 1 1 0 1 0 1 1 0 0 0 Ví dụ: Từ hai mệnh đề a = “Mỗi năm có 12 tháng”, b = “Mỗi năm có 52 tuần” ta thiết lập mệnh đề c = “Mỗi năm có 12 tháng hoặc 52 tuần”. Mệnh đề c là tuyển của hai mệnh đề đã cho. Chú ý: 1. Để thiết lập tuyển của hai mệnh đề a , b ta ghép hai mệnh đề đó bởi liên từ “hoặc” hay một liên từ khác cùng loại. 2. Khi thiết lập tuyển của nhiều mệnh đề, ta dùng dấu chấm phẩy thay cho liên từ “hoặc”. Chẳng hạn: “Số có tận cùng bằng 0; 2; 4; 6 hoặc 8 thì chia hết cho 2” 3. Phép tuyển có tính chất giao hoán, tính chất kết hợp và có p  p  p ; p  0  p ; p  1  1 ; p  p  1. 4. Ngoài ra giữa phép tuyển và phép hội còn có tính chất phân phối. 5. Giữa các phép toán phủ định, hội và tuyển còn liên hệ với nhau bởi luật Đờ Moocgăng nhƣ sau: p  q  p  q; p  q  p  q . Với luật này, khi chứng tỏ một hội của hai mệnh đề là mệnh đề sai ta chỉ cần chỉ ra một trong hai mệnh đề thành phần sai là đƣợc và để chứng tỏ tuyển của hai mệnh đề là sai thì phải chứng tỏ cả hai mệnh đề thành phần đồng thời sai. d) Phép kéo theo Mệnh đề a kéo theo b là một mệnh đề, kí hiệu là a  b , sai khi a đúng mà b sai và đúng trong các trƣờng hợp còn lại. Bảng giá trị chân lí của phép kéo theo 8 a b a b 1 1 1 1 0 0 0 1 1 0 0 1 Ví dụ: Từ hai mệnh đề a = “Số tự nhiên a có tổng các chữ số chia hết cho 3”; b = “Số tự nhiên a chia hết cho 3”. Ta thiết lập mệnh đề c = “Nếu số tự nhiên a có tổng các chữ số chia hết cho 3 thì nó chia hết cho 3”. Mệnh đề c trong ví dụ trên là mệnh đề kéo theo thiết lập từ hai mệnh đề a ;b. Chú ý: Mệnh đề “ a kéo theo b ” thƣờng đƣợc diễn đạt dƣới nhiều hình thức khác nhau, chẳng hạn: “nếu a thì b ”; “ a suy ra b ”; “có a thì có b ”. e) Phép tương đương Mệnh đề a tương đương b là một mệnh đề, kí hiệu là a  b , đúng khi cả hai mệnh đề a , b cùng đúng hoặc cùng sai và sai trong các trƣờng hợp còn lại.Bảng giá trị chân lí của mệnh đề tƣơng đƣơng a b a b 1 1 1 1 0 0 0 1 0 0 0 1 Ví dụ: Từ hai mệnh đề a = “Số 45 có tận cùng bằng 5”; b = “Số 45 chia hết cho 5”. Ta thiết lập mệnh đề c = “Số 45 có tận cùng bằng 5 khi và chỉ khi nó chia hết cho 5”. Mệnh đề c trong ví dụ trên là mệnh đề tƣơng đƣơng đƣợc thiết lập từ hai mệnh đề đã cho. Chú ý: Mệnh đề “ a tƣơng đƣơng b ” còn đƣợc diễn đạt bằng nhiều hình thức khác nhau, chẳng hạn: “ a khi và chỉ khi b ”; “ a nếu và chỉ nếu b ”. 9 1.1.2. Công thức của đại số mệnh đề 1.1.2.1. Khái niệm công thức của đại số mệnh đề Giả sử cho p, q, r, … là các biến mệnh đề. Từ các biến mệnh đề đó, sử dụng các phép toán logic ,  ,  ,  ,  ta lập đƣợc những mệnh đề mới, phức tạp hơn nhƣ q  p ; ( p  q)  r … Từ các mệnh đề mới lập đƣợc, lại áp dụng các phép toán logic, ta lại đƣợc các mệnh đề mới, chẳng hạn p  ( p  q) ; ( p  q)  ( q  p) ; ( p  q)  r ; ( p  q)  ( p  r ) … Cứ nhƣ vậy, ta xây dựng đƣợc một dãy các kí hiệu gọi là công thức của logic mệnh đề. Nhƣ vậy, mỗi công thức của logic mệnh đề là một dãy các kí hiệu thuộc ba loại: +) Các mệnh đề sơ cấp p, q, r, … +) Các kí hiệu phép toán logic ,  ,  ,  ,  . +) Các dấu ngoặc ( ) chỉ thứ tự phép toán Theo định nghĩa trên thì: +) Bản thân các mệnh đề sơ cấp cũng là một công thức. +) Nếu P, Q là những công thức thì P , P  Q , P  Q , P  Q , P  Q cũng đều là công thức. Nhận xét: Khái niệm công thức trong logic mệnh đề tƣơng tự nhƣ khái niệm biểu thức đại số trong đại số. Ví dụ 1: Xét công thức ( p  q)  r . a. Khi thay p bằng mệnh đề “45 chia hết cho 3” q bằng mệnh đề “45 chia hết cho 5” r bằng mệnh đề “45 chia hết cho 15” thì công thức ( p  q)  r trở thành mệnh đề “Nếu 45 chia hết cho 3 và 45 chia hết cho 5 thì 45 chia hết cho 15”. b. Nếu thay p bằng mệnh đề “45 chia hết cho 3” q bằng mệnh đề “45 chia hết cho 5” r bằng mệnh đề “45 chia hết cho 8” thì công thức ( p  q)  r trở thành mệnh đề “Nếu 45 chia hết cho 3 và 45 chia 10 hết cho 5 thì 45 chia hết cho 8”. 1.1.2.2. Giá trị chân lí của công thức Nhƣ trên đã thấy, khi thay p, q, r, … trong công thức bởi các mệnh đề cụ thể (tức là biết tính đúng sai của nó) thì công thức sẽ trở thành một mệnh đề xác định. Giá trị chân lí của mệnh đề này phụ thuộc vào giá trị chân lí của các mệnh đề p, q, r, … và kết quả thực hiện của các phép tính logic. Trở lại công thức ( p  q)  r trong ví dụ ở trên. Trong trƣờng hợp a. ta có p  1 , q  1, lúc đó p  q  1 (theo định nghĩa của phép hội), mặt khác r  1. Nhƣ vậy, theo định nghĩa của phép kéo theo (dòng 1 của bảng chân lí của phép kéo theo) mệnh đề ( p  q)  r là đúng, tức là mệnh đề “Nếu 45 chia hết cho 3 và 45 chia hết cho 5 thì 45 chia hết cho 15” là mệnh đề đúng. Trong trƣờng hợp b. ta có p  1 , q  1, lúc đó p  q  1 (theo định nghĩa của phép hội), mặt khác r  0 nên mệnh đề ( p  q)  r sai (dòng hai bảng chân lí của phép kéo theo) nghĩa là mệnh đề “Nếu 45 chia hết cho 3 và 45 chia hết cho 5 thì 45 chia hết cho 8” là mệnh đề sai. Tổng quát: Cho S ( p1 , p2 ,.... pn ) là công thức chứa n mệnh đề p1 , p2 ,.... pn . Khi thay p1 , p2 ,.... pn bằng các mệnh đề cụ thể (cũng có nghĩa là khi gán cho p1 , p2 ,.... pn các giá trị 0 và 1) thì công thức S ( p1 , p2 ,.... pn ) trở thành một mệnh đề xác định và có một giá trị chân lí xác định. Giá trị chân lí này là giá trị của công thức ứng với bộ giá trị ( p1 , p2 ,.... pn ) đã cho. Nó có thể tính đƣợc bằng cách lập bảng giá trị chân lí của công thức. Ví dụ 2: Lập bảng chân lí của công thức ( p  q)  ( p  q ) . p q p q pq p q ( p  q)  ( p  q ) 0 0 1 1 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 1 0 1 11 Qua bảng chân lí này ta có thể nói: Khi p là mệnh đề đúng, q là mệnh đề sai thì mệnh đề ( p  q)  ( p  q ) là mệnh đề sai (dòng 3). Khi p là mệnh đề sai, q là mềnh đề sai thì ( p  q)  ( p  q ) lại là mệnh đề đúng (dòng 1). Chú ý: +) Khi lập bảng chân lí ta phải nêu đầy đủ tất cả các bộ giá trị có thể có của bộ các mệnh đề. +) Với công thức chứa hai biến mệnh đề nhƣ trên bảng chân lí gồm 4 dòng vì mỗi mệnh đề nhận 2 giá trị 0 hoặc 1 nên có 2  2  4 bộ giá trị +) Với công thức chứa 3 mệnh đề ta phải lập bảng chân lí gồm 2  2  2  23  8 dòng, và nếu công thức chứa n mệnh đề thì bảng giá trị chân lí có 2 n dòng. *) Sự bằng nhau của hai công thức: Hai công thức A và B đƣợc gọi là bằng nhau và kí hiệu A  B nếu giá trị của chúng tại mọi bộ giá trị của biến đều nhƣ nhau. Kí hiệu A  B , trong đó A và B là các công thức của đại số mệnh đề cũng đƣợc gọi là một đẳng thức. Nhƣ vậy, hai công thức bằng nhau về mặt hình thức chúng có thể đƣợc viết bởi các phép toán và cấu tạo khác nhau, miễn là chúng nhận giá trị nhƣ nhau tại mọi bộ giá trị của các biến. Ta có thể kiểm tra hay chứng minh sự bằng nhau của hai công thức của đại số mệnh đề bằng cách lập bảng giá trị chân lí của chúng và so sánh các giá trị tƣơng ứng của hai công thức đó. Tuy nhiên, đây không phải là cách duy nhất mà ngƣời ta còn có những cách khác, chẳng hạn sử dụng phép biến đổi tƣơng đƣơng nhƣ trình bày ngay sau đây. 1.1.2.3. Biến đổi tƣơng đƣơng các công thức của đại số mệnh đề Việc thay thế một công thức của đại số mệnh đề bởi một công thức bằng công thức đó đƣợc gọi là phép biến đổi đồng nhất hay phép biến đổi tƣơng đƣơng. Ngƣời ta thƣờng dùng các công thức bằng nhau để biểu thị các tính chất của phép toán. Sau đây chúng ta liệt kê một số tính chất của các phép toán mệnh 12 đề dƣới dạng các đẳng thức. Những đẳng thức này thƣờng đƣợc sử dụng để chứng minh các công thức bằng nhau hay đƣa một công thức về dạng nào đó bằng các phép biến đổi tƣơng đƣơng. Việc kiểm tra lại sự đúng đắn của các đẳng thức đƣợc thực hiện bằng cách lập bảng giá trị chân lí hoặc một vài nhận xét đơn giản sau + p p + Tính chất giao hoán của phép hội, tuyển: p  q  q  p, p  q  q  p + Tính chất kết hợp của phép hôi, tuyển: ( p  q)  r  p  (q  r ) , ( p  q)  r  p  ( q  r) + Tính chất phân phối của phép hội đối với phép tuyền: p  ( q  r )  ( p  q)  ( p  r ) + Tính chất phân phối của phép tuyển đối với phép hội: p  ( q  r )  ( p  q)  ( p  r ) + p q  pq + Luật Đờ Moocgăng: p  q = p  q ; p  q = p  q . 1.1.2.4. Dạng chuẩn tắc của công thức Tích sơ cấp (Hội sơ cấp): Ta gọi một công thức có dạng hội các biến mệnh đề hoặc phủ định của biến mệnh đề là một tích sơ cấp. Chẳng hạn: p  q  r ; p  q  r ; p  q  r ; … là các tích sơ cấp. Dạng chuẩn tắc tuyển: Một công thức gọi là có dạng chuẩn tắc tuyển nếu nó biểu thị ở dạng tuyển của các tích sơ cấp. Kí hiệu “dạng chuẩn tắc tuyển” là CT – dạng. Chẳng hạn: ( p  q  r )  ( p  q  r )  ( p  q  r ) là công thức có dạng chuẩn tắc tuyển. Mệnh đề: “Mọi công thức của đại số mệnh đề luôn biến đổi tƣơng đƣơng đƣợc về dạng chuẩn tắc tuyển”. Tuyển sơ cấp: Ta gọi một công thức có dạng tuyển của các biến mệnh đề 13 hoặc phủ định của biến mệnh đề là một tuyển sơ cấp. Dạng chuẩn tắc hội: Một công thức gọi là dạng chuẩn tắc hội nếu nó biểu thị ở dạng hội của các tuyển sơ cấp. Kí hiệu “dạng chuẩn tắc hội” là CH – dạng. Mệnh đề: “Mọi công thức của đại số mệnh đề luôn biến đổi tƣơng đƣơng đƣợc về dạng chuẩn tắc hội”. Tích sơ cấp đầy đủ của n biến mệnh đề: Xét các công thức của n biến mệnh đề p1 , p2 ,.... pn . Ta gọi một công thức có dạng hội của các biến mệnh đề hoặc phủ định của biến mệnh đề sao cho với mỗi i , trong công thức có mặt pi hoặc pi nhƣng không đồng thời có mặt cả hai, không lặp lại hai lần với một kí hiệu biến là một tích sơ cấp đầy đủ của n biến mệnh đề. Với n biến mệnh đề ta lập đƣợc đúng 2n tích sơ cấp đầy đủ. Dạng chuẩn tắc tuyển hoàn toàn: Một công thức được nói là có dạng chuẩn tắc tuyển hoàn toàn nếu nó là tuyển của các tích sơ cấp đầy đủ. Mệnh đề: “Một công thức không hằng sai của đại số mệnh đề luôn biến đổi tƣơng đƣơng đƣợc về dạng chuẩn tắc tuyển hoàn toàn”. Tuyển sơ cấp đầy đủ của n biến mệnh đề: Xét các công thức của n biến mệnh đề p1 , p2 ,.... pn . Ta gọi một công thức dạng tuyển của các biến mệnh đề hoặc phủ định của biến mệnh đề sao cho với mỗi i , trong công thức có mặt pi hoặc pi nhƣng không đồng thời có mặt cả hai, không lặp lại hai lần một kí hiệu biến là một tuyển sơ cấp đầy đủ của n biến mệnh đề. Với n biến mềnh đề ta lập đƣợc đúng 2 n tuyển sơ cấp đầy đủ. Dạng chuẩn tắc hội hoàn toàn: Một công thức được nói là có dạng chuẩn tắc hội hoàn toàn nếu nó là hội của các tuyến sơ cấp đầy đủ. Ví dụ: “Một công thức không hằng đúng của đại số mệnh đề luôn biến đổi tƣơng đƣơng đƣợc về dạng chuẩn tắc hội hoàn toàn”. 14 1.1.2.5. Hệ đầy đủ các phép toán của đại số mệnh đề Khi xây dựng công thức của đại số mệnh đề ta sử dụng năm phép toán là phủ định, hội, tuyển, kéo theo, tƣơng đƣơng. Thậm chí có thể sử dụng cả những phép toán khác mà ta chƣa nói đến ở đây. Tuy nhiên, khi xét đến dạng chuẩn tắc tuyển hay dạng chuẩn tắc hội ta nhận thấy rằng có thể biến đổi tƣơng đƣơng các công thức này về dạng chỉ sử dụng đến phép phủ định, phép hội và phép tuyển. Nhƣ vậy, chỉ cần ba phép toán này là biểu diễn đƣợc mọi công thức của đại số mệnh đề. Định nghĩa: Ta gọi một tập hợp S gồm các phép toán mệnh đề nào đó là một hệ đầy đủ các phép toán của đại số mệnh đề nếu mọi công thức của đại số mệnh đề đều biến đổi tƣơng đƣơng đƣợc về dạng chỉ sử dụng các phép toán có trong S . Hiển nhiên hệ S = {phủ định, hội, tuyển, kéo theo, tƣơng đƣơng} là một hệ đầy đủ. Sử dụng các mệnh đề về dạng chuẩn tắc tuyển và dạng chuẩn tắc hội ta đi đến khẳng định hệ S1 = {phủ định, hội, tuyển} cũng là hệ đầy đủ. Bằng cách sử dụng các đẳng thức chuyển đổi phép toán mệnh đề p  q = p  q và p  q = p  q , ta có các hệ S2 = {phủ định, hội} và hệ S3 = {phủ định, tuyển} cũng đầy đủ. Từ đẳng thức p  q  p  q , ta cũng có p  q  ( p  q) , nên hệ S4 = {phủ định, kéo theo} cũng là hệ đầy đủ. Nhƣ vậy, chỉ cần sử dụng một số ít phép toán thích hợp là có thể biểu thị đƣợc tất cả các công thức của đại số mệnh đề. 1.1.2.6. Công thức đối ngẫu Nhƣ trên ta thấy có thể biến đổi một công thức bất kì của đại số mệnh đề về dạng chuẩn tắc, nghĩa là về dạng trong đó chỉ có các phép toán phủ định, hội và tuyển. Định nghĩa: Giả sử A  ( p, q,..., r ) là công thức chỉ chứa các phép toán phủ định, hội, tuyển. Nếu trong công thức A  ( p, q,..., r) ta thay phép hội bởi tuyển và ngƣợc lại thay tuyển bởi hội thì công thức mới nhận đƣợc sau phép thay thế đó gọi là 15 công thức đối ngẫu của công thức A và kí hiệu bởi A Phép biến đổi từ A sang A gọi là phép đối ngẫu. Ta cũng nói phép hội và phép tuyển là hai phép đối ngẫu của nhau. Ví dụ: Công thức đối ngẫu của công thức ( p  q)  ( p  q  r ) là ( p  q)  ( p  q  r ) . Chú ý: Nếu A là đối ngẫu của A thì A là đối ngẫu của A . Vì thế ta gọi A và A là hai công thức đối ngẫu nhau. Công thức đối ngẫu của công thức dạng chuẩn tắc tuyển gọi là công thức dạng chuẩn tắc hội. Dùng khái niệm công thức đối ngẫu ta có thể mở rộng công thức Đờ Moocgăng đã biết về sự phủ định của hội và tuyển: p  q  p  q , p  q  p  q . Xét công thức A  ( p, q,..., r) chỉ chứa các phép toán phủ định, hội, tuyển. Áp dụng công thức trên đồng thời sử dụng luật phân phối của phép hội với phép tuyển và của phép tuyển đối với phép hội, ta thấy rằng muốn phủ định công thức A , trƣớc hết trong A ta thay dấu hội, tuyển lần lƣợt bởi dấu tuyển, hội sau đó trong công thức nhận đƣợc thay p, q,....r tƣơng ứng bởi p, q ,..., r . Nhƣ vậy ta có: S ( p, q,..., r)  S * ( p, q ,..., r ) . Đó là nội dung của định lí sau đây: Định lí: Cho A  ( p, q,..., r ) là một công thức ở dạng chỉ chứa các phép toán phủ định, hội, tuyển. Khi đó ta có đẳng thức S ( p, q,..., r)  S * ( p, q ,..., r ) Ví dụ 1: Tìm phủ định của công thức ( p  q )  r . Giải: Trƣớc hết ta có công thức đối ngẫu của ( p  q )  r là ( p  q )  r Trong công thức đối ngẫu thay các mệnh đề bởi phủ định của nó ta đƣợc công thức ( p  q)  r . Vậy ( p  q )  r  ( p  q)  r . Ví dụ 2: Tìm phủ định của công thức p  q . Giải: Ta có p  q  p  q nên p  q  p  q  p  q . 1.1.2.7. Luật của đại số mệnh đề Cho công thức A . Ta gọi: a) A là công thức hằng đúng, nếu nó luôn nhận giá trị chân lí bằng 1 với 16 mọi hệ chân lí gán cho các biến mệnh đề có mặt trong công thức đó. b) A là công thức hằng sai, nếu nó luôn nhận giá trị chân lí bằng 0 với mọi hệ chân lí gán cho các biến mệnh đề có mặt trong công thức đó. Công thức đƣợc gọi là thực hiện đƣợc nếu tồn tại ít nhất một bộ giá trị của các biến sao cho giá trị tƣơng ứng của công thức là 1. Công thức hằng đúng của đại số mệnh đề còn dƣợc goi là luật của đại số mệnh đề. Một số luật thƣờng gặp của đại số mệnh đề: - Luật đồng nhất: p  q - Luật bài trung: p  p - Luật phi mâu thuẫn : p  p Mệnh đề: Cho A và B là các công thức của đại số mệnh đề. Khi đó có đẳng thức A  B khi và chỉ khi có luật A  B . Chú ý: A  B  ( A  B)  ( B  A) . Do đó có các đẳng thức A  B khi và chỉ khi có cả hai luật A  B và B  A . 1.1.3. Các quy tắc suy luận của đại số mệnh đề Định nghĩa: Cho A1 , A2 ,..., An và B là những công thức của đại số mệnh đề (chứa các biến mệnh đề nào đó). Ta nói một quy tắc suy luận với tiên đề là A1 , A2 ,..., An và kết luận B nếu ứng với mọi bộ giá trị của các biến sao cho tất cả các công thức A1 , A2 ,..., An đều nhận giá trị chân lí bằng 1 ta có B cũng nhận giá trị chân lí bằng 1. Khi đó ta sử dụng kí hiệu A1 , A2 ,..., An B Từ định nghĩa ta có các nhận xét sau: + Khi xét một quy tắc suy luận ta không quan tâm đến các bộ giá trị của các biến mà ít nhất một trong các công thức A1 , A2 ,..., An nhận giá trị 0. + Khi công thức B là hằng đúng thì bất cứ các công thức A1 , A2 ,..., An nào cũng có quy tắc suy luận A1 , A2 ,..., An . B Định lí: Cho A1 , A2 ,..., An và B là những công thức của đại số mệnh đề. Khi đó 17 ta có quy tắc suy luận A1 , A2 ,..., An khi và chỉ khi có luật A1  A2  ...  An  B . B Danh sách các quy tắc suy luận của đại số mệnh đề thƣờng đƣợc sử dụng trong giải toán: + Quy tắc kết luận: + Quy tắc bắc cầu: A, A  B B A  A2 , A2  A3 ,..., An1  An A  B, B  C hoặc 1 AC A1  An + Quy tăc suy luận phản đảo: A B BA + Quy tắc suy luận phản chứng : + Quy tắc hoán vị giả thiết: B  A C C A B A  (B  C) B  ( A  C) + Quy tắc tách giả thiết: A B  C A  (B  C) + Quy tắc nhập giả thiết: A  (B  C) A B  C + Quy tắc suy luận loại trừ: + Một số quy tắc khác: A  B, A B A A  B, C  D A  B , C  D ; ; ; B  A AC  B  D AC  B  D A B AC ; ( A  C)  ( A  B  C) (B  C)  ( A  B  C) 1.2. Đại cƣơng về đại số vị từ 1.2.1. Vị từ và các phép toán vị từ 1.2.1.1. Vị từ, miền đúng của vị từ Định nghĩa: Giả sử D là một tập cho trƣớc. Ta gọi mỗi ánh xạ f : D  I , trong đó I  {0,1}, là một vị từ (hàm mệnh đề) trên tập hợp D . Ngƣời ta thƣờng dùng một chữ, chẳng hạn chữ x , để chỉ một biến nhận giá trị 18 trên tập hợp D . Nhƣ vậy, một vị từ trên tập hợp D là một phát biểu f về mối quan hệ của tập hợp D sao cho với mỗi x thuộc D , f ( x ) là một mệnh đề (tức là f ( x ) là một phát biểu đúng hoặc một phát biểu sai). Biến x đƣợc gọi là biến tử (để phân biệt với mệnh đề). Xét một vị từ f : D  I - Tập hợp {x  D| f(x) = 1}đƣợc gọi là miền đúng của vị từ f và kí hiệu là Ef hay Ef ( x ) . - Tập hợp D \ f ( x ) đƣợc gọi là miền sai của vị từ f . - Một vị từ trên tập hợp D đƣợc gọi là vị từ hằng đúng nếu miền đúng của nó là D . - Một vị từ trên tập hợp D đƣợc gọi là vị từ hằng sai nếu miền đúng của nó là tập hợp rỗng. 1.2.1.2. Các phép toán vị từ Cho các vị từ f ( x ) , g ( x ) trên tập hợp D . Kí hiệu Ef ( x ) , Eg ( x ) là các miền đúng của chúng. Ta có các định nghĩa: - Phép phủ định: Phủ định của vị từ f ( x ) là vị từ trên tập hợp D nhận tập hợp D \ Ef ( x ) làm miền đúng. Phủ định của vị từ f ( x ) đƣợc kí hiệu là f ( x ) . Nhƣ vậy ta có E f ( x )  D \ Ef ( x ) . - Phép hội: Hội của các vị từ f ( x ) và g ( x ) là vị từ trên D , kí hiệu là f ( x)  g ( x) , nhận Ef ( x)  Eg ( x) làm miền đúng. Nhƣ vậy, E ( f ( x)  g ( x))  Ef ( x)  Eg ( x) . - Phép tuyển: Tuyển của f ( x ) với g ( x ) , kí hiệu là f ( x)  g ( x) , là một vị từ trên D nhận Ef ( x)  Eg ( x) làm miền đúng. Ta cũng có E ( f ( x)  g ( x))  Ef ( x)  Eg ( x) . - Phép kéo theo: Vị từ f ( x ) kéo theo g ( x ) đƣợc định nghĩa là f ( x )  g ( x ) và kí hiệu là f ( x)  g ( x) . Rõ ràng, E ( f ( x)  g ( x))  ( D \ Ef ( x))  Eg ( x) . - Phép tương đương: Vị từ f ( x ) tƣơng đƣơng với g ( x ) đƣợc xác định nghĩa là 19 ( f ( x)  g ( x))  ( g ( x)  f ( x)) và kí hiệu là f ( x)  g ( x) . Ta cũng có: E( f ( x)  g ( x))  E ( f ( x)  g ( x))  E ( g ( x)  f ( x))  (( D \ Ef ( x))  Eg ( x))  (( D \ Eg ( x))  Ef ( x)) . Nhận xét: + Nếu f ( x ) là phủ định của vị từ f ( x ) thì f ( x ) là phủ định của f ( x ) . + Phép hội vị từ có tính chất giao hoán, kết hợp. + Phép tuyển vị từ có tính chất giao hoán, kết hợp. + Phép hội vị từ phân phối đối với phép tuyển vị từ. + Phép tuyển vị từ phân phối đối với phép hội vị từ. + Với mọi vị từ f ( x ) trên tập D luôn có f ( x )  f ( x) là một vị từ hằng đúng và f ( x )  f ( x) là một vị tự hằng sai. + Với các vị tự f ( x ) và g ( x ) trên D ta có E ( f ( x)  g ( x))  D \ E ( f ( x)  g ( x))  D \ ( Ef ( x )  Eg ( x))  ( D \ Ef ( x))  ( D \ Eg ( x))  E f ( x)  E g ( x )  E ( f ( x )  g ( x )) . Do đó : f ( x)  g ( x)  f ( x)  g ( x) . 1.2.1.3. Lƣợng từ a. Lượng từ tồn tại () Xét các hàm mệnh đề xác định trên tập số tự nhiên: “Số x thỏa mãn đẳng thức x  1  0 ”; “Số x thỏa mãn bất đẳng thức 2  x  3 ”. Khi đặt từ “tồn tại” trƣớc câu trên ta đƣợc các câu sau: “Tồn tại số x thỏa mãn đẳng thức x  1  0 ” đây là một mệnh đề đúng, vì có số 1 thỏa mãn x  1  0 . “Tồn tại số tự nhiên x thỏa mãn bất đẳng thức 2  x  3 ” sai vì không có số tự nhiên nào lớn hơn 2 nhỏ hơn 3. Nhƣ vây, việc đặt từ “tồn tại” trƣớc một hàm mệnh đề đã biến mệnh đề đó thành một mệnh đề hoàn toàn xác định. Tổng quát: Giả sử f ( x ) là hàm mệnh đề trên tập X . Đặt lƣợng từ “tồn tại” trƣớc hàm mệnh đề f ( x ) ta có mệnh đề “tồn tại x sao cho f ( x ) ”. Ta kí hiệu mệnh đề này là f ( x ) hay (x  X )( f ( x)) . 20