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

Let's analyze the expression ¬X→Z given X=0, Y=0, Z=1. ¬X is equivalent to 1. Therefore, ¬X→Z becomes 1→1 which evaluates to 1. Now let's analyze (¬X→Y ) ∧ (¬Y → Z ). With X=0, Y=0, and Z=1, ¬X becomes 1 and ¬Y becomes 1. Therefore, (¬X→Y ) becomes (1→0) which is 0. Also, (¬Y→Z) becomes (1→1) which is 1. Consequently, (¬X→Y ) ∧ (¬Y → Z ) becomes (0 ∧ 1) which evaluates to 0. Since ¬X→Z evaluates to 1 and (¬X→Y ) ∧ (¬Y → Z ) evaluates to 0, the original expression (¬X→Y ) ∧ (¬Y → Z ) → (¬X→Z) which simplifies to 0 → 1 is equivalent to 1.

Trong đại số Boole, ta có các quy tắc cơ bản sau:

- X + 0 = X (Đúng, vì 0 là phần tử trung hòa của phép OR)

- X + 1 = 1 (Đây là quy tắc quan trọng cần lưu ý. X + 1 luôn bằng 1, bất kể giá trị của X là gì)

- X + (Y + Z) = (X + Y) + Z = X + Y + Z (Tính kết hợp của phép OR, đúng)

- (W + X)(Y + Z) = WY + XY + WZ + XZ (Đây là phép phân phối, đúng)

Vậy biểu thức sai là X + 1 = X vì X + 1 phải bằng 1 chứ không phải 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.