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  và , XOR chỉ có kết quả đúng khi và chỉ khi  và  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ẻ.

Để 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  đúng thì  phải sai, nếu  mà sai thì  phải đúng. Phép tuyển loại thường được biểu diễn bởi các ký hiệu sau: .

Tính chất 

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

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: 

 , XOR với 0 giữ nguyên giá trị
 , XOR với chính nó ra kết quả là 0
 , 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  thì , 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.

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. Thông thường để hoán đổi hai biến  và , ta cần một biến tạm .tmp = a
a = b
b = tmpVới XOR, ta có thể làm như sau:a = a ^ b
b = a ^ b # b = a ^ b ^ b = a
a = 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  và , tổng của chúng (mà không có phần nhớ) chính là . Ví dụ , có thể tính bằng . 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.

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  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óa

plaintext = 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. 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. Giả sử có ba ổ đĩa . Thay vì lưu dữ liệu lên cả ba, RAID 5 lưu dữ liệu lên  và  còn  lưu giá trị parity.

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

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

Tham khảo 

Toán tử logic