Логические операции#

Совет

Подробнее про обозначениях можно посмотреть тут

Определение отрицания#

Отрицанием высказывания A называется высказывание, обозначаемое \(\neg A\) (не A), истинность которого определяется таблицей:

\(A\)	\(\neg A\)
1	0
0	1

Определение конъюнкции#

Конъюнкцией высказываний A и B называется высказывание, обозначаемое \(A \wedge B\); \(A\) & \(B\) (A и B), истинность которого определяется таблицей:

\(A\)	\(B\)	\(A \wedge B\)
1	1	1
1	0	0
0	1	0
0	0	0

Определение дизъюнкции#

Дизъюнкцией высказываний A и B называется высказывание, обозначаемое \(A \lor B\); \(A \mspace{5mu} || \mspace{5mu} B\) (A или B), истинность которого определяется таблицей:

\(A\)	\(B\)	\(A \lor B\)
1	1	1
1	0	1
0	1	1
0	0	0

Свойства некоторых логических операций#

Заметка

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

Коммуникативность конъюнкции#

\(A \wedge B = B \wedge A\)

От перестановки мест результат не меняется

Доказательство:

\(A\)	\(B\)	\(A \wedge B\)	\(B \wedge A\)
1	1	1	1
1	0	0	0
0	1	0	0
0	0	0	0

Последние два столбца совпадают, а значит что выражения равносильны

Ассоциативность конъюнкции#

\((A \wedge B) \wedge C = A \wedge (B \wedge C)\)

Порядок выполнения не важен

Доказательство:

\(A\)	\(B\)	\(C\)	\((A \wedge B) \wedge C\)	\(A \wedge (B \wedge C)\)
1	1	1	1	1
1	1	0	0	0
1	0	1	0	0
1	0	0	0	0
0	1	1	0	0
0	1	0	0	0
0	0	1	0	0
0	0	0	0	0

Последние два столбца совпадают, а значит что выражения равносильны

Отрицание конъюнкции#

\(\neg (A \wedge B) = (\neg A) \lor (\neg B)\)

Отрицание конъюнкции равняется дизъюнкции отрицаний

Доказательство:

\(A\)	\(B\)	\(\neg(A \wedge B)\)	\((\neg A) \lor (\neg B)\)
1	1	0	0
1	0	1	1
0	1	1	1
0	0	1	1

Последние два столбца совпадают, а значит что выражения равносильны

Коммуникативность дизъюнкции#

\(A \lor B = B \lor A\)

От перестановки мест результат не меняется

Доказательство:

\(A\)	\(B\)	\(A \lor B\)	\(B \lor A\)
1	1	1	1
1	0	1	1
0	1	1	1
0	0	0	0

Последние два столбца совпадают, а значит что выражения равносильны

Ассоциативность дизъюнкции#

\((A \lor B) \lor C = A \lor (B \lor C)\)

Порядок выполнения не важен

Доказательство:

\(A\)	\(B\)	\(C\)	\((A \lor B) \lor C\)	\(A \lor (B \lor C)\)
1	1	1	1	1
1	1	0	1	1
1	0	1	1	1
1	0	0	1	1
0	1	1	1	1
0	1	0	1	1
0	0	1	1	1
0	0	0	0	0

Последние два столбца совпадают, а значит что выражения равносильны

Отрицание дизъюнкции#

\(\neg (A \lor B) = (\neg A) \wedge (\neg B)\)

Отрицание дизъюнкции равняется конъюнкции отрицаний

Доказательство:

\(A\)	\(B\)	\(\neg (A \lor B)\)	\((\neg A) \wedge (\neg B)\)
1	1	0	0
1	0	0	0
0	1	0	0
0	0	1	1

Последние два столбца совпадают, а значит что выражения равносильны

Дистрибутивность конъюнкции относительно дизъюнкции#

\(A \wedge (B \lor C) = (A \wedge B) \lor (A \wedge C)\)

Доказательство:

\(A\)	\(B\)	\(C\)	\(A \wedge (B \lor C)\)	\((A \wedge B) \lor (A \wedge C)\)
1	1	1	1	1
1	1	0	1	1
1	0	1	1	1
1	0	0	0	0
0	1	1	0	0
0	1	0	0	0
0	0	1	0	0
0	0	0	0	0

Последние два столбца совпадают, а значит что выражения равносильны

Дистрибутивность дизъюнкции относительно конъюнкции#

\(A \lor (B \wedge C) = (A \lor B) \wedge (A \lor C)\)

Доказательство:

\(A\)	\(B\)	\(C\)	\(A \wedge (B \lor C)\)	\((A \wedge B) \wedge (A \wedge C)\)
1	1	1	1	1
1	1	0	1	1
1	0	1	1	1
1	0	0	1	1
0	1	1	1	1
0	1	0	1	1
0	0	1	0	0
0	0	0	0	0

Последние два столбца совпадают, а значит что выражения равносильны

Закон двойного отрицания #

\(\neg (\neg A) = A\)

Бонус-теоремки #

\(A \wedge A = A\)
\(A \wedge 1 = A\)
\(A \wedge 0 = 0\)
\(A \lor A = A\)
\(A \lor 1 = 1\)
\(A \lor 0 = A\)

Импликация и Эквиваленция#

Определение импликации#

Импликацией высказываний A и B называется высказывание, обозначаемое \(A \to B\) ("Если A, то B"; "A достаточно для B"), истинность которого определяется таблицей:

\(A\)	\(B\)	\(A \to B\)
1	1	1
1	0	0
0	1	1
0	0	1

Определение эквиваленции#

Эквиваленцией высказываний A и B называется высказывание, обозначаемое \(A \leftrightarrow B\) ("A равносильно B"; "A тогда и только тогда когда B"), истинность которого определяется таблицей:

\(A\)	\(B\)	\(A \leftrightarrow B\)
1	1	1
1	0	0
0	1	0
0	0	1

Свойства импликации#

Выражение импликации через другие логические операции#

\(A \to B = (\neg A) \lor B\)

Доказательство:

\(A\)	\(B\)	\(A \to B\)	\((\neg A) \lor B\)
1	1	1	1
1	0	0	0
0	1	1	1
0	0	1	1

Последние два столбца совпадают, а значит что выражения равносильны

Отрицание Импликации#

\(\neg (A \to B) = A \lor (\neg B)\)

Доказательство:

\(\neg(A \to B) = \neg((\neg A) \lor B) = A \lor (\neg B)\)

Путем равносильных преобразований, опираясь на теоремы ("Выражение через другие операции" и "Двойное отрицание), доказанные выше, мы преобразовали исходное выражение в желаемое

Обоснование доказательства от противного#

Совет

Освежить в памяти такое доказательство можно тут

\(A \to B = (\neg B) \to (\neg A)\)

Доказательство:

\(A\)	\(B\)	\(A \to B\)	\((\neg B) \to (\neg A)\)
1	1	1	1
1	0	0	0
0	1	1	1
0	0	1	1

Последние два столбца совпадают, а значит что выражения равносильны

Транзитивность импликации#

Заметка

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

\(((A \to B) \wedge (B \to C)) \to (A \to C)\)

Доказательство:

\(A\)	\(B\)	\(C\)	\(((A \to B) \wedge (B \to C)) \to (A \to C)\)
1	1	1	1
1	1	0	1
1	0	1	1
1	0	0	1
0	1	1	1
0	1	0	1
0	0	1	1
0	0	0	1

Последний столбец состоит только из истины, а значит при любых значениях высказываний данное выражение будет верно

Над статьей работали:

Лавелин Михаил (Тг): редактор

Выражаем благодарность:

Олегу Вадимовичу, за конспект для данной статьи