Đại số Logic / Logic Algebra / Boolean Algebra

Mở đầu

• Chào mừng các bạn đã quay lại với series bài viết "Lên trình Thuật toán - Lập trình thi đấu 🏆"

• Nếu các bạn đã từng tham gia các cuộc thi lập trình thi đấu, thì chắc các bạn cũng biết rằng: Toán học đóng vai trò quan trọng trong các cuộc thi này.

• Trong bài viết này, chúng ta sẽ cùng nhau thảo luận về Đại số Logic - một kiến thức nền tảng quan trọng, được sử dụng rất nhiều trong việc lập trình nói riêng, và các kỳ thi lập trình thi đấu nói chung.

• Các bạn có thể xem phiên bản video của bài viết này tại đây:

Định nghĩa

• Đại số Logic, hay thuật ngữ tiếng Anh gọi là Logic Algebra hoặc Boolean Algebra.

• Boolean là một kiểu giá trị phổ biến ở trong lập trình mà có thể các bạn đã được biết đến.

• Ví dụ:

  • Mình có một biến a có kiểu dữ liệu boolean.

  • Khi đó, a có thể nhận 2 giá trị là True và False, tức là Đúng và Sai.

  • Hay ở trong hệ nhị phân, sẽ tương đương với 1 và 0.

Các toán tử logic thường sử dụng

• Có 3 toán tử logic phổ biến nhất mà chúng ta thường sử dụng đó là AND, OR và NOT.

• Trong đó, toán tử NOT là dễ nhớ nhất. Nó là phép phủ định.

  • Ví dụ a = True, thì NOT a = False

  • Và ngược lại, a = False thì NOT a = True

• Còn toán tử AND và OR, mình nhớ hồi học đại học các thầy có hướng dẫn một cách nhớ đó là:

  "Phép AND chỉ đúng (True) khi cả 2 vế đều đúng (True)"

  "Phép OR chỉ sai (False) khi cả 2 vế đều sai (False)"

• Cách này cũng khá là dễ nhớ đúng không nào?

• Tuy nhiên, mình thì thích những ví dụ thực tế và có thể hình tượng hóa được hơn, nên khi hướng dẫn các bạn học sinh cấp 3 trong CLB Lập trình - THPT Ngọc Tảo, thì mình thường lấy 2 ví dụ đó là:

• Đối với phép AND, các bạn có thể tưởng tượng giống như việc Xét học lực Giỏi.

  • Ví dụ các bạn sẽ chỉ đạt được học lực Giỏi khi và chỉ khi điểm số cả 2 môn Toán và Văn đều >= 8.0.

  • Còn nếu điểm của 1 trong 2 môn < 8.0, hoặc cả 2 môn đều < 8.0, thì bạn sẽ không đạt được học lực Giỏi.

  • Nó cũng giống như việc phép AND chỉ trả về giá trị True, khi cả 2 vế đều là True.

• Còn đối với toán tử OR, mình hay lấy ví dụ về việc Lớp trưởng và Lớp phó mỗi người cầm 1 chiếc chìa khóa để mở cửa lớp học.

  • Nếu Lớp trưởng mang chìa khóa, hoặc Lớp phó mang chìa khóa, hoặc cả 2 người đều mang chìa khóa, thì lớp học sẽ có thể mở được bình thường.

  • Chỉ có duy nhất trường hợp, nếu cả 2 quên chìa khóa, thì cửa lớp mới không thể mở được.

  • Nó cũng giống như việc phép OR chỉ trả về giá trị False, khi cả 2 vế đều là False.

Bảng chân trị (Truth Table)

• Khi đã hiểu được các logic trên rồi thì lúc này, đọc vào bảng chân trị, hay thuật ngữ tiếng Anh gọi là Truth Table, chắc chắn sẽ vô cùng dễ hiểu.

• Chúng ta lần lượt có các giá trị của a và b. Vì a và b là 2 biến có kiểu dữ liệu boolean. Mà boolean thì chỉ có 2 giá trị là True và False, nên ta sẽ có tổng cộng 2² = 4 trường hợp có thể xảy ra.

• Trường hợp thứ nhất: a = False, b = False

  • Khi đó a AND b = False

  • Các bạn còn nhớ ví dụ ở trên mình đưa ra không? Đây chính là trường hợp cả môn Toán và môn Văn của mình đều < 8.0, nên mình sẽ không được học lực Giỏi.

  • Và a OR b = False, vì nó tương đương với việc cả Lớp trưởng và Lớp phó đều quên chìa khóa lớp, nên sẽ không mở được cửa lớp.

  • Thế còn NOT a thì là phủ định của a, ở đây a = False, nên NOT a sẽ là True.

  • Rất là đơn giản đúng không nào?

• Tương tự như vậy, chúng ta sẽ có được giá trị của những dòng còn lại.

Một số cách ký hiệu khác

• Khi đọc các tài liệu chuyên ngành, có thể các bạn sẽ gặp phải một số cách ký hiệu khác cho các toán tử logic này.

• Toán tử AND:

  • Có những tài liệu khác sẽ ký hiệu là dấu chấm (.)

  • Hoặc ⋀.

  • Hoặc ở môn Toán rời rạc, mình nhớ nó còn có tên đó là Phép hội.

  • Chắc nhiều bạn sẽ thắc mắc sao đặt cái tên gì mà lạ hoắc thế? Thì thực ra không phải tự nhiên mà mọi người lại gọi là Phép hội đâu, nó xuất phát từ thuật ngữ tiếng Anh của toán tử này, được gọi là Conjunction. Dịch sang tiếng Việt là sự liên kết, sự giao hội hoặc sự hội họp. Thuật ngữ Phép hội có ý nghĩa chính là vì như thế.

• Tương tự như vậy, toán tử OR cũng có một số cách ký hiệu khác, đó là:

  • Dấu cộng (+)

  • Hoặc ⋁

  • Hoặc ở môn Toán rời rạc sẽ được gọi là Phép tuyển, thuật ngữ tiếng anh gọi là Disjunction.

• Còn toán tử NOT:

  • Trong lập trình thì mọi người hay sử dụng dấu chấm than (!)

  • Còn trong các tài liệu về Toán như môn Toán rời rạc, thì có thể các bạn sẽ gặp các kiểu ký hiệu khác, ví dụ như dấu gạch ngang ở trên đầu, hoặc một ký hiệu giống chữ L nằm ngang như thế này (¬). Thuật ngữ tiếng Anh gọi là Negation.

    

Hi vọng kiến thức này hữu ích với bạn. Hẹn gặp lại 👋