Tương đương logic

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Trong logic học, hai mệnh đề PQ gọi là tương đương logic hay tương đương với nhau nếu PQ đồng thời có cùng một giá trị chân lý; nghĩa là PQ cùng đúng (hoặc cùng sai), trong những điều kiện hoàn toàn như nhau, ta viết:

"P ⇔ Q"

và đọc là

"P đúng khi và chỉ khi Q đúng"

"⇔" gọi là dấu liên hệ tương đương.

Lôgic toán[sửa | sửa mã nguồn]

Trong lôgic toán, bảng chân lý của một quan hệ tương đương như sau:

P Q P ⇔ Q
Đúng Đúng Đúng
Đúng Sai Sai
Sai Đúng Sai
Sai Sai Đúng

Dễ thấy, mối quan hệ tương đương P ⇔ Q chẳng qua là (P ⇒ Q) ∧ (Q ⇒ P) ((P kéo theo Q) và (Q kéo theo P)).

Nói cách khác, hai mệnh đề PQ tương đương nhau khi và chỉ khi mệnh đề này kéo theo mệnh đề kia và ngược lại.

Trong trường hợp này, hai phát biểu "P ⇒ Q" và "Q ⇒ P" gọi là đảo đề của nhau.

Để chứng minh mối quan hệ tương đương P ⇔ Q, ta phải chứng minh mối quan hệ kéo theo P ⇒ Q và chiều ngược lại.

Chú ý rằng (P ⇔ Q) ⇔ (Q ⇔ P)

Trong ngôn ngữ tự nhiên, để diễn đạt mối liên hệ tương đương giữa PQ, người ta có nhiều cách nói:

  • P đúng khi và chỉ khi Q đúng.
  • Để cho P đúng, điều kiện cần và đủ là Q đúng.
  • Điều kiện cần và đủ để P đúng là Q đúng.
  • P đúng là một điều kiện cần và đủ để Q đúng.
  • P tương đương với Q.

Tính chất[sửa | sửa mã nguồn]

  • P ⇔ P (tính phản xạ)
  • (P ⇔ Q) ⇒ (Q ⇔ P) (tính đối xứng)
  • ((P ⇔ Q) ⇔ R) ⇔ (P ⇔ (Q ⇔ R)) (tính kết hợp)
  • ¬¬P ⇔ P (tương đương với nguyên lý triệt tam)
  • (P ⇔ Q) ⇔ (¬P ⇔ ¬Q) (contraposition)

Thí dụ

  • Ta có
\forall n\in \mathbb N, n\geq 2, \forall x\in\mathbb R - \{1\}, (x+1)^n=(x-1)^n\Leftrightarrow \frac{(x+1)^n}{(x-1)^n}=1
  • Mối quan hệ "tương đương" ∀x, y∈ℝ (x=y ⇔ x2=y2) (bình phương lên) là sai vì thí dụ 22=(-2)2 không kéo theo được 2=-2
  • Mối quan hệ tương đương sau là đúng
\forall x\in [-1, +\infty], x-1\geq \sqrt{x+1} \Leftrightarrow ((x-1)^2\geq x+1\quad \wedge \quad x-1\geq 0) (bình phương lên)

Khi bình phương lên, ta mất thông tin "x-1 lớn hơn hoặc bằng một căn bậc hai" nên nó không âm, vậy để đạt được tương đương, ở mệnh đề sau ta phải bổ sung x-1>=0.

Nhận xét:

Chứng minh bằng các quan hệ tương đương không phải lúc nào cũng đơn giản, nhiều khi cần phải chứng minh riêng lẻ từng đảo đề tương ứng.

Phát biểu rằng "quan hệ tương đương P ⇔ Q là đúng" không có nghĩa là "PQ đều đúng", mà là "khi một trong hai mệnh đề là đúng (hoặc sai), mệnh đề còn lại cũng đúng (hoặc sai) đồng thời".

Quan hệ tương đương giữa nhiều mệnh đề[sửa | sửa mã nguồn]

Xem xét ba mệnh đề P, QR.

Để chứng minh các mối quan hệ tương đương P ⇔ Q ⇔ R, chỉ cần chứng minh các quan hệ kéo theo sau:

P ⇒ Q, Q ⇒ R và R ⇒ P.

Giả sử các quan hệ P ⇒ Q, Q ⇒ R và R ⇒ P đã được thiết lập.

Để chứng minh rằng Q ⇒ P, ta dùng hai quan hệ Q ⇒ R và R ⇒ P.

Tương tự, từ R ⇒ P và P ⇒ Q suy ra R ⇒ Q.

Cuối cùng P ⇒ R, do P ⇒ Q và Q ⇒ R.

Cách chứng minh như trên gọi là chứng minh vòng.

Ta có thể tổng quát hóa đối với n mệnh đề P1, P2… Pn.

Để chứng minh các mối quan hệ tương đương P1 ⇔ P2 ⇔… ⇔ Pn, chỉ cần chứng minh các quan hệ kéo theo:

P1 ⇒ P2, P2 ⇒ P3… Pn-1 ⇒ Pn và Pn ⇒ P1.