Tuyển loại

Phép tuyển loại, hay còn gọi là phép hoặc loại trừ, còn được biết đến với tên gọi hàm XOR, là một toán tử logic. Với hai toán hạng $A$ và $B$ , XOR chỉ có kết quả đúng khi và chỉ khi $A$ và $B$ không bằng nhau. Tổng quát hóa cho nhiều toán hạng đầu vào khác nhau, hàm XOR sẽ cho kết quả đúng khi tổng số lượng toán hạng với giá trị là 1 lẻ.^[1]^[2]

Để diễn giải theo ngôn ngữ thông dụng, phép tuyển loại mang ý nghĩa "chỉ một trong hai toán hạng này là đúng". Nếu $A$ đúng thì $B$ phải sai, nếu $A$ mà sai thì $B$ phải đúng. Phép tuyển loại thường được biểu diễn bởi các ký hiệu sau: $\oplus \veebar {\hat {}}\not \equiv {\dot {\vee }}$ .

Tính chất

Bảng chân trị hàm XOR
$A$	$B$	$A\oplus B$
0	0	0
0	1	1
1	0	1
1	1	0

Trong tiếng Việt, cả phép tuyển loại và phép tuyển thật ra thường được dùng với cùng một từ "hoặc" hoặc là "hay", chẳng hạn như "Mọi số tự nhiên đều là số chẵn hoặc số lẻ" cho phép tuyển loại và "Học sinh được khuyến khích xem lại các bài giảng hoặc làm các bài kiểm tra các năm trước để ôn thi" cho phép tuyển. Tiếng Anh cũng gặp vấn đề tương tự với từ "or" mang cả hai nghĩa.^[3] Thông thường người đọc hoặc người nghe phải dựa và ngữ cảnh để đoán xem từ này mang nghĩa nào.

Tuy nhiên đối với toán học và logic học, hai phép này được phân định rạch ròi. Phép tuyển loại còn có thể được biểu diễn bằng phép tuyển, phép phủ định, và phép hội:^[2]

$A\oplus B=(A\lor B)\land \neg (A\lor B)=(A\land \neg B)\lor (\neg A\land B)=\neg ((A\lor B)\land (\neg A\land \neg B))$

Việc này giúp thiết kế các cổng logic được thuận tiện hơn.

Phép tuyển loại có một vài tính chất đặc biệt, giúp nó được sử dụng rộng rãi trong ngành khoa học máy tính: ^[2]^[4]

$A\oplus 0=A$ , XOR với 0 giữ nguyên giá trị
$A\oplus A=0$ , XOR với chính nó ra kết quả là 0
$A\oplus B\oplus B=A$ , XOR hai lần với một giá trị ra kết quả là giá trị ban đầu

Ứng dụng trong khoa học máy tính

Phép toán thao tác bit

Phép tuyển loại được sử dụng khá phổ biến trong các phép toán thao tác bit để kiểm tra hai giá trị có khác nhau không. Nếu $A\oplus B=0$ thì $A=B$ , ngược lại thì khác nhau. Cách này nhanh hơn so sánh tuần tự từng byte khi làm việc với dữ liệu lớn.^[4]

Bên cạnh đó, nó còn có thể được tận dụng để hoán đổi hai biến không cần biến trung gian.^[5] Thông thường để hoán đổi hai biến $a$ và $b$ , ta cần một biến tạm $tmp$ .

tmp = aa = bb = tmp

Với XOR, ta có thể làm như sau:

a = a ^ bb = a ^ b # b = a ^ b ^ b = aa = a ^ b # a = a ^ b ^ a = b

XOR còn là thành phần cốt lõi của bộ cộng nhị phân. Với hai bit $a$ và $b$ , tổng của chúng (mà không có phần nhớ) chính là $a\oplus b$ . Ví dụ $0+1=0$ , có thể tính bằng $0\oplus 1=1$ . Mạch cộng toàn phần (full adder) mở rộng điều này để xử lý cả bit nhớ từ vị trí trước với hai cổng XOR. ^[6]

Mã hóa XOR

Mã hóa XOR là một kỹ thuật mã hóa đơn giản dựa trên tính chất $A\oplus B\oplus B=A$ của XOR. Ý tưởng cơ bản là dùng một khóa bí mật (key) để mã hóa dữ liệu gốc (plaintext) thành dữ liệu đã mã hóa (ciphertext), và dùng chính khóa đó để giải mã.

ciphertext = plaintext ^ key # Mã hóaplaintext = ciphertext ^ key # Giải mã

Trong trường hợp key ngắn hơn dữ liệu, key sẽ được lặp lại tuần hoàn cho đến khi độ dài hai bên bằng nhau trước khi mã hóa. Tuy nhiên, đây cũng chính là điểm yếu chí mạng của mã hóa XOR: nếu kẻ tấn công đoán được độ dài của key, họ có thể phân tích tần suất xuất hiện của các byte để phá khóa.^[7] Vì vậy, mã hóa XOR thuần túy không được dùng độc lập trong thực tế, mà thường là một thành phần trong các thuật toán mã hóa phức tạp hơn như AES.

Bit chẵn lẽ trong RAID

RAID (Redundant Array of Independent Disks) là kỹ thuật kết hợp nhiều ổ đĩa cứng lại để tăng tốc độ hoặc khả năng chịu lỗi. Trong RAID 3 và 4, XOR được dùng để tính bit chẵn lẻ (parity), một giá trị dự phòng cho phép khôi phục dữ liệu khi một ổ đĩa bị hỏng.^[8] Giả sử có ba ổ đĩa $A,B,C$ . Thay vì lưu dữ liệu lên cả ba, RAID 5 lưu dữ liệu lên $A$ và $B$ còn $C$ lưu giá trị parity.

$C=A\oplus B$

Nếu ổ A bị hỏng, ta có thể khôi phục lại nó:

$A=B\oplus C=B\oplus B\oplus A$

RAID 5 dùng nhiều ổ đĩa hơn, và parity được phân tán đều ra các ổ thay vì tập trung ở một ổ, nhưng nguyên lý XOR vẫn giữ nguyên.

Bài toán XOR

Bài toán XOR là một bài kiểm tra cổ điển trong học máy, đặc biệt liên quan đến mạng thần kinh nhân tạo. Bài toán đặt ra như sau: xây dựng một mô hình nhận hai đầu vào nhị phân và dự đoán kết quả XOR của chúng.

Bài toán này tưởng đơn giản nhưng không thể giải bằng mô hình tuyến tính (linear classifier), vì không tồn tại một đường thẳng nào chia bốn điểm dữ liệu trên thành hai nhóm đúng hoặc sai. Đây gọi là bài toán phân tách phi tuyến tính.

Năm 1969, Minsky và Papert chứng minh điều này trong cuốn Perceptrons, và chỉ ra rằng Perceptron đơn lớp không thể học được XOR.^[9] Phát hiện này góp phần gây ra "mùa đông AI" đầu tiên, khi nguồn tài trợ cho nghiên cứu AI bị cắt giảm mạnh.

Tuy nhiên, việc triển khai mạng thần kinh nhiều lớp không đơn giản: thuật toán của perceptron đơn lớp không tổng quát hóa được cho kiến trúc nhiều lớp, nên người ta chưa có cách hiệu quả để điều chỉnh trọng số của các lớp ẩn. Vấn đề này chỉ được giải quyết khi Rumelhart, Hinton và Williams phổ biến thuật toán truyền ngược vào năm 1986, cho phép tính gradient xuyên qua nhiều lớp và cập nhật trọng số tự động. ^[10]

Tham khảo

↑ Weisstein, Eric W. "XOR". mathworld.wolfram.com (bằng tiếng Anh). Truy cập ngày 3 tháng 4 năm 2026.
1 2 3 Bryant, Randal E.; O'Hallaron, David Richard (2011). Computer systems: a programmer's perspective (ấn bản thứ 2). Boston, Mass.: Prentice Hall. ISBN 978-0-13-610804-7.
↑ Felton, Casey; Jasbi, Masoud (ngày 24 tháng 1 năm 2025). "Non-Implicature Sources of Exclusivity in Linguistic Disjunction". Experiments in Linguistic Meaning (bằng tiếng Anh). Quyển 3. tr. 163–175. doi:10.3765/elm.3.5806. ISSN 2694-1791.
1 2 Knuth, Donald Ervin (1982), The art of computer programming. 1: Fundamental algorithms , Reading, Mass: Addison-Wesley, ISBN 978-0-201-03801-9
↑ Warren, Henry S. (2013). Hacker's delight (ấn bản thứ 2). Upper Saddle River, NJ: Addison-Wesley. ISBN 978-0-321-84268-8.
↑ Singh, Ajay Kumar (2011). Digital VLSI design. New Delhi: PHI Learning. ISBN 978-81-203-4187-6.
↑ Schneier, Bruce (1996). Applied cryptography: protocols, algorithms, and source code in C (ấn bản thứ 2). New York: Wiley. ISBN 978-0-471-12845-8.
↑ Patterson, David A.; Gibson, Garth; Katz, Randy H. (ngày 1 tháng 6 năm 1988). "A case for redundant arrays of inexpensive disks (RAID)". ACM Digital Library (bằng tiếng Anh). doi:10.1145/50202.50214. Truy cập ngày 4 tháng 4 năm 2026.
↑ Minsky, Marvin; Papert, Seymour (1972). Perceptrons: an introduction to computational geometry . Cambridge/Mass.: The MIT Press. ISBN 978-0-262-13043-1.
↑ Rumelhart, David E.; Hinton, Geoffrey E.; Williams, Ronald J. (tháng 10 năm 1986). "Learning representations by back-propagating errors". Nature (bằng tiếng Anh). Quyển 323 số 6088. tr. 533–536. doi:10.1038/323533a0. ISSN 1476-4687.

[1] Weisstein, Eric W. "XOR". mathworld.wolfram.com (bằng tiếng Anh). Truy cập ngày 3 tháng 4 năm 2026.

[:0-2] 1 2 3 Bryant, Randal E.; O'Hallaron, David Richard (2011). Computer systems: a programmer's perspective (ấn bản thứ 2). Boston, Mass.: Prentice Hall. ISBN 978-0-13-610804-7.

[3] Felton, Casey; Jasbi, Masoud (ngày 24 tháng 1 năm 2025). "Non-Implicature Sources of Exclusivity in Linguistic Disjunction". Experiments in Linguistic Meaning (bằng tiếng Anh). Quyển 3. tr. 163–175. doi:10.3765/elm.3.5806. ISSN 2694-1791.

[:1-4] 1 2 Knuth, Donald Ervin (1982), The art of computer programming. 1: Fundamental algorithms , Reading, Mass: Addison-Wesley, ISBN 978-0-201-03801-9

[5] Warren, Henry S. (2013). Hacker's delight (ấn bản thứ 2). Upper Saddle River, NJ: Addison-Wesley. ISBN 978-0-321-84268-8.

[6] Singh, Ajay Kumar (2011). Digital VLSI design. New Delhi: PHI Learning. ISBN 978-81-203-4187-6.

[7] Schneier, Bruce (1996). Applied cryptography: protocols, algorithms, and source code in C (ấn bản thứ 2). New York: Wiley. ISBN 978-0-471-12845-8.

[8] Patterson, David A.; Gibson, Garth; Katz, Randy H. (ngày 1 tháng 6 năm 1988). "A case for redundant arrays of inexpensive disks (RAID)". ACM Digital Library (bằng tiếng Anh). doi:10.1145/50202.50214. Truy cập ngày 4 tháng 4 năm 2026.

[9] Minsky, Marvin; Papert, Seymour (1972). Perceptrons: an introduction to computational geometry . Cambridge/Mass.: The MIT Press. ISBN 978-0-262-13043-1.

[10] Rumelhart, David E.; Hinton, Geoffrey E.; Williams, Ronald J. (tháng 10 năm 1986). "Learning representations by back-propagating errors". Nature (bằng tiếng Anh). Quyển 323 số 6088. tr. 533–536. doi:10.1038/323533a0. ISSN 1476-4687.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

x t s Các toán tử logic thông dụng
Hằng đúng/Đúng $\top$
NAND logic (cổng NAND) $\uparrow$ Kéo theo đảo $\leftarrow$ Kéo theo (cổng IMPLY) $\rightarrow$ Tuyển (cổng OR) $\lor$
Phủ định (cổng NOT) $\neg$ Tuyển loại (cổng XOR) $\not \leftrightarrow$ Tương đương (cổng XNOR) $\leftrightarrow$ Phát biểu (Buffer điện tử)
NOR logic (cổng NOR) $\downarrow$ Không kéo theo (cổng NIMPLY) $\nrightarrow$ Không kéo theo đảo $\nleftarrow$ Hội (cổng AND) $\land$
Mâu thuẫn/Sai $\bot$
Cổng thông tin Triết học