Phủ định

Sơ đồ Venn cho phép phủ định với một toán hạng.

Sơ đồ Venn cho phép phủ định với một toán hạng.

Phủ định (tiếng Anh: Negation), hay còn gọi là hàm NOT, là một toán tử logic một ngôi (chỉ cần một toán hạng) tác động lên một mệnh đề $P$ để tạo ra mệnh đề "không phải $P$". Phủ định được hiểu là đúng khi $P$ sai, và sai khi $P$ đúng. Ví dụ, nếu $P$ là "Trời đang mưa" thì phủ định của nó là "Trời đang không mưa".

Phủ định được ký hiệu bằng $\mathrm{\neg }p$ trong logic học, $\sim p$ trong một số ngữ cảnh khác, $\bar{p}$ trong điện tử số và đại số Boolean, và ! hoặc NOT trong nhiều ngôn ngữ lập trình.

Tính chất

Bảng chân trị phủ định

$P$	$\mathrm{\neg }P$
0	1
1	0

Trong toán học và logic học, phủ định có thể được biểu diễn qua phép hội và phép tuyển theo định lý De Morgan:

$\mathrm{\neg }(P\vee Q)\equiv \mathrm{\neg }P\wedge \mathrm{\neg }Q$

$\mathrm{\neg }(P\wedge Q)\equiv \mathrm{\neg }P\vee \mathrm{\neg }Q$

Phủ định kép

Trong logic cổ điển, phủ định của phủ định của một mệnh đề $P$ tương đương với chính $P$:

$\mathrm{\neg }\mathrm{\neg }P\equiv P$

Ngược lại trong logic trực giác, chiều thuận vẫn được chấp nhận:

$P\to \mathrm{\neg }\mathrm{\neg }P$

nhưng chiều ngược $\mathrm{\neg }\mathrm{\neg }P\to P$ thì không, vì logic trực giác chỉ công nhận một mệnh đề là đúng khi có thể xây dựng được một minh chứng tường minh cho nó chứ không chỉ lập luận rằng nó "không thể không đúng". Biết rằng $P$ "không thể sai" chưa đủ—mà cần chỉ ra cụ thể tại sao $P$ đúng.

Phủ định lượng từ

Trong logic vị từ, phủ định tương tác với các lượng từ theo quy tắc sau:

$\mathrm{\neg }\mathrm{\forall }xP(x)\equiv \mathrm{\exists }x\mathrm{\neg }P(x)$

$\mathrm{\neg }\mathrm{\exists }xP(x)\equiv \mathrm{\forall }x\mathrm{\neg }P(x)$

Ví dụ, phủ định của "Mọi người đều có thể sai" là "Tồn tại ít nhất một người không thể sai", không phải "Mọi người đều không thể sai".

Quy tắc suy diễn

Trong suy diễn tự nhiên, có hai quy tắc cơ bản liên quan đến phủ định:

Nhập đề phủ định (negation introduction): nếu từ giả thiết $P$ ta suy ra được cả $Q$ lẫn $\mathrm{\neg }Q$ (tức là một mâu thuẫn), thì $P$ phải sai:

$P\Rightarrow Q,P\Rightarrow \mathrm{\neg }Q⊢\mathrm{\neg }P$

Quy tắc này còn được gọi là reductio ad absurdum hay chứng minh bằng phản chứng (proof by contradiction): để chứng minh $P$ sai, ta giả sử $P$ đúng rồi suy luận dần ra mâu thuẫn.

Xuất đề phủ định (negation elimination): nếu cả $P$ và $\mathrm{\neg }P$ cùng đúng, thì bất kỳ mệnh đề nào cũng có thể suy ra được:

$P,\mathrm{\neg }P⊢Q$

Quy tắc này phản ánh nguyên lý ex falso quodlibet: từ một tiền đề sai, mọi thứ đều có thể suy ra.

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

Phép toán thao tác bit

Bài chi tiết: Phép toán thao tác bit

Trong lập trình hệ thống, phủ định bit (bitwise NOT) đảo ngược toàn bộ các bit trong một số nhị phân: mọi bit 0 thành 1 và ngược lại. Ký hiệu toán tử là ~ trong C và C++. Ví dụ:

unsigned char x = 0b00001111;  // x = 15
unsigned char y = ~x;          // y = 0b11110000 = 240

Phủ định bit được dùng phổ biến để tạo phần bù một và phần bù hai, là nền tảng của cách biểu diễn số âm trong máy tính.

Toán tử logic trong lập trình

Nhiều ngôn ngữ lập trình phân biệt phủ định bit và phủ định logic bằng hai toán tử khác nhau. Trong các ngôn ngữ theo truyền thống C, phủ định bit dùng ~, còn phủ định logic dùng !. Phủ định logic trả về giá trị boolean: !0 cho kết quả 1, còn ! với bất kỳ giá trị khác 0 nào đều cho kết quả 0.

Trong một số ngôn ngữ như Pascal và Ada, toán tử phủ định logic được viết là NOT thay vì !.

Một phương pháp phổ biến trong C và C++ là dùng phủ định kép !!x để chuyển một giá trị bất kỳ thành giá trị boolean chuẩn (0 hoặc 1), vì !x đã trả về 0 hoặc 1 nhưng đảo chiều, nên !!x khôi phục lại chiều ban đầu.

int x = 42;
int b = !!x;  // b = 1