Có bao nhiêu hàm Boolean với n biến đầu vào?

Với n biến nhị phân đầu vào, tổng số hàm Boolean khả dĩ là 2^(2^n), ví dụ với 2 biến có 16 hàm và với 3 biến có 256 hàm.

Tập cổng logic nào có tính đầy đủ chức năng?

Tập cổng {AND, OR, NOT}, {AND, NOT}, hoặc chỉ riêng một cổng NAND (hoặc NOR) đều là các tập đầy đủ chức năng để tạo ra mọi mạch logic.

Dạng chuẩn tắc DNF và CNF khác nhau như thế nào?

DNF (chuẩn tắc tuyển) là tổng của các tích (OR của các AND), còn CNF (chuẩn tắc hội) là tích của các tổng (AND của các OR).

Hàm Boolean là gì? Bảng chân trị, DNF/CNF và đại số logic

Q: Hàm Boolean là gì?

Hàm Boolean là ánh xạ toán học nhận đầu vào là các biến nhị phân (0 hoặc 1) và trả về một kết quả nhị phân duy nhất.

Hàm Boolean (Boolean function) là một ánh xạ toán học nhận đầu vào là các biến nhị phân và trả về đầu ra là một giá trị nhị phân duy nhất:

f: \{0, 1\}^n \rightarrow \{0, 1\} \quad \text{hoặc} \quad f: \{-1, 1\}^n \rightarrow \{-1, 1\}

Trong đó $n \in \mathbb{N}$ là số lượng biến đầu vào. Hàm Boolean là viên gạch nền móng của lý thuyết mạch số, kiến trúc máy tính điện tử, mật mã học, lý thuyết độ phức tạp tính toán và thuật toán tối ưu hóa tổ hợp.

Không gian biểu diễn và số lượng hàm Boolean

Với $n$ biến đầu vào, bảng chân trị (truth table) của hàm chứa $2^n$ hàng tương ứng với tất cả các tổ hợp giá trị nhị phân có thể có. Do mỗi hàng có thể nhận 1 trong 2 giá trị đầu ra (0 hoặc 1), tổng số hàm Boolean khả dĩ bậc $n$ là:

N = 2^{2^n}

Ví dụ:

Với $n = 1$ : Có $2^{2^1} = 2^2 = 4$ hàm (Hằng 0, Hằng 1, Hàm đồng nhất $x$ , Phủ định $\neg x$ ).
Với $n = 2$ : Có $2^{2^2} = 2^4 = 16$ hàm (gồm AND, OR, XOR, NAND, NOR, XNOR,...).
Với $n = 3$ : Có $2^{2^3} = 2^8 = 256$ hàm.
Với $n = 4$ : Có $2^{2^4} = 2^{16} = 65536$ hàm.

Các phép toán cơ bản và tính đầy đủ chức năng

Đại số Boolean vận hành dựa trên ba phép toán cơ bản:

Phép hội (AND / Conjunction): $x \land y$ (cho kết quả 1 khi và chỉ khi cả hai biến bằng 1).
Phép tuyển (OR / Disjunction): $x \lor y$ (cho kết quả 0 khi và chỉ khi cả hai biến bằng 0).
Phép phủ định (NOT / Negation): $\neg x$ hoặc $\bar{x}$ (đảo ngược giá trị logic).

Một tập hợp các phép toán được gọi là đầy đủ chức năng (functionally complete) nếu mọi hàm Boolean bất kỳ đều có thể biểu diễn qua các phép toán đó. Các tập đầy đủ kinh điển bao gồm $\{\land, \lor, \neg\}$ , $\{\land, \neg\}$ , $\{\lor, \neg\}$ , và đặc biệt là các cổng đơn lẻ như NAND (phủ định hội) hoặc NOR (phủ định tuyển) – nguyên lý chế tạo vi mạch tích hợp VLSI hiện đại.

Các dạng chuẩn tắc biểu diễn hàm

Mọi hàm Boolean đều có thể chuẩn hóa thành các cấu trúc đại số chính quy (Crama và Hammer, 2011):

Dạng biểu diễn	Cấu trúc đại số	Đặc điểm ứng dụng
Dạng chuẩn tắc tuyển (DNF)	Tổng của các tích (Sum-of-Products): $\bigvee \bigwedge l_i$	Ghép nối các minterm tương ứng với các hàng có giá trị đầu ra bằng 1 trong bảng chân trị.
Dạng chuẩn tắc hội (CNF)	Tích của các tổng (Product-of-Sums): $\bigwedge \bigvee l_i$	Định dạng đầu vào tiêu chuẩn cho các thuật toán giải bài toán thỏa mãn mệnh đề SAT (SAT Solvers).
Đa thức Zhegalkin (ANF)	Đa thức trên trường hữu hạn $\mathbb{F}_2$ dùng phép XOR ( $\oplus$ ) và AND	Phân tích bậc phi tuyến và tính đại số trong mật mã học khối (S-boxes).

Phân tích Fourier trên Hàm Boolean

Trong toán học rời rạc nâng cao (O'Donnell, 2014), khi không gian đầu vào được gán nhãn trên trường số thực $\{-1, 1\}^n$ , mọi hàm Boolean $f: \{-1, 1\}^n \rightarrow \mathbb{R}$ đều có thể khai triển Fourier duy nhất dạng trực giao:

f(x) = \sum_{S \subseteq [n]} \hat{f}(S) \chi_S(x)

Trong đó $\chi_S(x) = \prod_{i \in S} x_i$ là các ký tự Fourier và $\hat{f}(S) = \mathbb{E}[f(x)\chi_S(x)]$ là hệ số Fourier. Biểu diễn Fourier cho phép định lượng độ nhạy cảm của biến (influence of variables), kiểm tra tính tuyến tính và chứng minh độ phức tạp tính toán của các mạch logic.

Ứng dụng thực tiễn trong kỹ thuật số và bảo mật

Ứng dụng của hàm Boolean bao trùm mọi lĩnh vực tính toán hiện đại: