1.7: Логічна еквівалентність

Last updated
Save as PDF

Page ID: 65145

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

У ваших попередніх класах математики (таких як алгебра та тригонометрія) ви зустрічали багато прикладів, коли дві різні на вигляд формули виявилися рівними. Аналогічно, в Логіці може бути два різних твердження, які мають однакову цінність істини у всіх можливих ситуаціях. (Це означає, що для кожного можливого призначення true або false змінним, або обидва твердження є істинними, або обидва є помилковими.) Такі твердження, як кажуть, логічно рівнозначні.

Позначення$\PageIndex{1}$

Ми напишемо${A} \equiv {B}$, щоб позначити,${A}$ що логічно еквівалентно${B}$.

Це може зайняти багато роботи, щоб перевірити, що два твердження логічно еквівалентні. З іншого боку, щоб показати, що два твердження не є логічно еквівалентними, вам потрібно лише знайти один приклад присвоєння змінним, таким чином, що одне з тверджень є істинним, а інше - помилковим.

Приклад$\PageIndex{2}$

Якщо$A$ істинно і$B$ є помилковим, то$A \lor B$ є істинним, але$A \Rightarrow B$ помилковим. Тому твердження$A \lor B$ і логічно$A \Rightarrow B$ не рівнозначні.

Вправа$\PageIndex{3}$

Показати, що кожна з наступних пар речень не є логічно рівнозначними.

$A \lor B \lor \lnot C$,$(A \lor B) \& (C \Rightarrow A)$
$(P \Rightarrow Q) \lor (Q \Rightarrow P)$,$P \lor Q$
$(X \& Y) \Rightarrow Z$,$X \lor (Y \Rightarrow Z)$

Приклад$\PageIndex{4}$

Покажіть, що$\lnot(A \lor B) \equiv \lnot A \& \lnot B$.

Рішення

Змінні$A$ і$B$ можуть бути або true або false, і ми будемо оцінювати обидва твердження для всіх можливих комбінацій. Щоб було зрозуміло, що жодна з можливостей не була пропущена, ми продовжуємо систематично: для кожного значення$A$ ми розглядаємо два можливих значення для$B$.

Припустімо$A$, що це правда.
1. Припустімо$B$, що це правда. У нас є\[\lnot(A \lor B) \quad=\quad \lnot(T \lor T) \quad=\quad \lnot T \quad=\quad F\] і\[\lnot A \& \lnot B \quad=\quad \lnot T \& \lnot T \quad=\quad F \& F \quad=\quad F .\] Обидва твердження є помилковими.
2. Припустімо$B$, що помилково. У нас є\[\lnot(A \lor B) \quad=\quad \lnot(T \lor F) \quad=\quad \lnot T \quad=\quad F\] і\[\lnot A \& \lnot B \quad=\quad \lnot T \& \lnot F \quad=\quad T \& F \quad=\quad F .\] Обидва твердження є помилковими.
Припустімо$A$, що помилково.
1. Припустімо$B$, що це правда. У нас є\[\lnot(A \lor B) \quad=\quad \lnot(F \lor T) \quad=\quad \lnot T \quad=\quad F\] і\[\lnot A \& \lnot B \quad=\quad \lnot F \& \lnot T \quad=\quad T \& F \quad=\quad F .\] Обидва твердження є помилковими.
2. Припустімо$B$, що помилково. У нас є\[\lnot(A \lor B) \quad=\quad \lnot(F \lor F) \quad=\quad \lnot F \quad=\quad T\] і\[\lnot A \& \lnot B \quad=\quad \lnot F \& \lnot F \quad=\quad T \& T \quad=\quad T .\] Обидва твердження вірні.

У всіх випадках або обидва твердження є істинними, або обидва є помилковими. Тому вони логічно рівнозначні.

Ми також можемо вирішити проблему, не виконуючи стільки роботи:

Простіше рішення

Зауважте, що твердження$\lnot(A \lor B)$ є істинним, якщо і тільки якщо$A \lor B$ є помилковим, що означає, що ні$A$ ні$B$ є істинним. Тому,\[\text{$\lnot(A \lor B)$ is true if and only if $A$ and~$B$ are both false.}\] Крім того,$\lnot A \& \lnot B$ є істинним тоді і тільки тоді,$\lnot A$ коли і$\lnot B$ є істинними, що означає, що:\[\text{$\lnot A \& \lnot B$ is true if and only if $A$ and~$B$ are both false.}\]

Таким чином, два твердження$\lnot(A \lor B)$ і$\lnot A \& \lnot B$ вірні в точно тій же ситуації (а саме, коли$A$ і обидва$B$ є помилковими); і вони обидва є помилковими у всіх інших ситуаціях. Тому вони логічно рівнозначні.

Вправа$\PageIndex{5}$

Перевірте кожне з наступних важливих логічних еквівалентів. Для більшості з них вам не потрібно оцінювати твердження для всіх можливих значень змінних.

правила заперечення:\[\begin{aligned} \lnot \lnot A \qquad &\equiv \qquad A \\ \lnot(A \& B) \qquad &\equiv \qquad \lnot A \lor \lnot B \\ \lnot(A \lor B) \qquad &\equiv \qquad \lnot A \& \lnot B \\ \lnot ( A \Rightarrow B) \qquad &\equiv \qquad A \& \lnot B \\ \lnot ( A \Leftrightarrow B) \qquad &\equiv \qquad A \Leftrightarrow \lnot B \end{aligned}\]
комутативність$\&$$\lor$, і$\Leftrightarrow$:\[\begin{aligned} A \& B \qquad &\equiv \qquad B \& A \\ A \lor B \qquad &\equiv \qquad B \lor A \\ A \Leftrightarrow B \qquad &\equiv \qquad B \Leftrightarrow A \end{aligned}\]
асоціативність$\&$ і$\lor$:\[\begin{aligned} (A \& B) \& C \qquad &\equiv \qquad A \& (B \& C) \\ (A \lor B) \lor C \qquad &\equiv \qquad A \lor (B \lor C) \end{aligned}\]

Правила заперечення$\&$ і$\lor$ часто називаються законами Де Моргана, на честь британського математика Августа Де Моргана (1806—1871, http://en.Wikipedia.org/wiki/Augustus_De_Morgan).

Правила заперечення можуть бути використані для спрощення заперечення будь-якого твердження.

Приклад$\PageIndex{6}$

Спростити$\lnot \bigl( (A \lor B) \Rightarrow (A \& \lnot C) \bigr)$.

Рішення

У нас є\[\begin{aligned} \lnot \bigl( (A \lor B) \Rightarrow (A \& \lnot C) \bigr) &\equiv (A \lor B) \& \lnot (A \& \lnot C) \\& \equiv (A \lor B) \& (\lnot A \lor \lnot \lnot C) \\& \equiv (A \lor B) \& (\lnot A \lor C) . \end{aligned}\]

Якщо${A} \equiv {B}$, то${A}, \ \therefore {B}$ діє відрахування. Наприклад, наведений вище приклад показує, що\[\lnot \bigl( (A \lor B) \Rightarrow (A \& \lnot C) \bigr), \ \therefore (A \lor B) \& (\lnot A \lor C)\] є дійсним відрахуванням.

Вправа$\PageIndex{7}$

Використовуйте правила заперечення, щоб спростити кожне з наступних тверджень (поки заперечення не буде застосовано ні до чого, крім змінних).

$\lnot \bigl( (A \lor B) \Rightarrow (C \& D) \bigr)$
$\lnot \bigl( (A \Rightarrow B) \lor (C \& D) \bigr)$
$\lnot \Bigl( A \Rightarrow \bigl( B \Rightarrow( C \Rightarrow D) \bigr) \Bigr)$
$\lnot \Bigl( \bigl( (A \Rightarrow B) \Rightarrow C \bigr) \Rightarrow D \Bigr)$
$\lnot \bigl( (P \lor \lnot Q) \& R \bigr)$
$\lnot (P \& Q \& R \& S)$
$\lnot \Bigl( \bigl( P \Rightarrow ( Q \& \lnot R) \bigr) \lor (P \& \lnot Q) \Bigr)$

Вправа$\PageIndex{8}$

Використовуйте правила заперечення, щоб спростити заперечення кожного з цих тверджень. Висловлюйте свої відповіді англійською мовою.

Якщо буде дощ, то автобус не буде вчасно.
Я хворий, і я втомився.
Або Папа Римський тут, або Королева і Секретар обидва тут.
Якщо Том забув свій рюкзак, то Сем з'їсть або розсіл, або картоплю, і або Боб не буде обідати, або Аліса поїде в магазин.

Приклад\(\PageIndex{2}\)

Вправа\(\PageIndex{3}\)

Приклад\(\PageIndex{4}\)

Вправа\(\PageIndex{5}\)

Приклад\(\PageIndex{6}\)

Вправа\(\PageIndex{7}\)

Вправа\(\PageIndex{8}\)

Позначення\(\PageIndex{1}\)