Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán BFS(I) là:

Biểu thức hội cơ bản (minterm) là một biểu thức logic được tạo thành bằng cách kết hợp các biến mệnh đề hoặc phủ định của chúng bằng phép toán AND (phép hội). Mỗi biến xuất hiện một lần trong biểu thức, hoặc ở dạng khẳng định, hoặc ở dạng phủ định.

Do đó, đáp án đúng là:

\(F = {q_1} \wedge {q_2} \wedge ... \wedge {q_n}\) với q_j = p_j hoặc \({q_j} = \overline {{p_j}} (j = 1,...,n)\)

Trong các phương án đã cho, chỉ có phương án 3 thể hiện đúng cấu trúc của một biểu thức hội (AND). Phương án 1 và 2 sử dụng phép tuyển (OR), không phải phép hội (AND).

Ta có X = 0, Y = 0, Z = 1. Thay vào biểu thức (\(\neg \)X→Y ) \(\wedge \) (\(\neg \)Y → Z ) và (\(\neg \)X →Z) như sau:

- (\(\neg \)X→Y ) \(\wedge \) (\(\neg \)Y → Z ) = (\(\neg \)0 → 0) \(\wedge \) (\(\neg \)0 → 1) = (1 → 0) \(\wedge \) (1 → 1) = 0 \(\wedge \) 1 = 0

- (\(\neg \)X →Z) = (\(\neg \)0 → 1) = (1 → 1) = 1

Vậy, chân trị của biểu thức là 0 và 1.

Để giải quyết câu hỏi này, chúng ta cần xem xét tính đúng sai của từng biểu thức logic Boole:

• X + 0 = X: Biểu thức này đúng, vì phép OR (tức là '+') với 0 không ảnh hưởng đến giá trị của X.


• X + 1 = X: Biểu thức này; sai. Vì phép OR với 1 luôn cho kết quả là 1, bất kể giá trị của X là gì. Do đó, X + 1 = 1 chứ không phải là X.


• X + (Y + Z) = (X + Y) + Z = X + Y + Z: Biểu thức này đúng, thể hiện tính kết hợp của phép OR.


• (W + X)(Y + Z) = WY + XY + WZ + XZ: Biểu thức này đúng, nó tuân theo quy tắc phân phối của phép AND (nhân) đối với phép OR (cộng).

Vậy, biểu thức sai là X + 1 = X.

Trong một đồ thị vô hướng, mỗi cạnh liên kết hai đỉnh. Do đó, mỗi cạnh đóng góp 2 vào tổng bậc của tất cả các đỉnh. Với m cạnh, tổng bậc của tất cả các đỉnh sẽ là 2*m.