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

Совет

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

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

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

$A$	$\mathrm{\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\vee B$; $A||B$ (A или B), истинность которого определяется таблицей:

$A$	$B$	$A\vee 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

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

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

$\mathrm{\neg }(A\wedge B)=(\mathrm{\neg }A)\vee (\mathrm{\neg }B)$

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

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

$A$	$B$	$\mathrm{\neg }(A\wedge B)$	$(\mathrm{\neg }A)\vee (\mathrm{\neg }B)$
1	1	0	0
1	0	1	1
0	1	1	1
0	0	1	1

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

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

$A\vee B=B\vee A$

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

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

$A$	$B$	$A\vee B$	$B\vee A$
1	1	1	1
1	0	1	1
0	1	1	1
0	0	0	0

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

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

$(A\vee B)\vee C=A\vee (B\vee C)$

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

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

$A$	$B$	$C$	$(A\vee B)\vee C$	$A\vee (B\vee 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

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

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

$\mathrm{\neg }(A\vee B)=(\mathrm{\neg }A)\wedge (\mathrm{\neg }B)$

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

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

$A$	$B$	$\mathrm{\neg }(A\vee B)$	$(\mathrm{\neg }A)\wedge (\mathrm{\neg }B)$
1	1	0	0
1	0	0	0
0	1	0	0
0	0	1	1

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

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

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

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

$A$	$B$	$C$	$A\wedge (B\vee C)$	$(A\wedge B)\vee (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\vee (B\wedge C)=(A\vee B)\wedge (A\vee C)$

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

$A$	$B$	$C$	$A\wedge (B\vee 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

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

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

$\mathrm{\neg }(\mathrm{\neg }A)=A$

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

1. $A\wedge A=A$
   
2. $A\wedge 1=A$
   
3. $A\wedge 0=0$
   
4. $A\vee A=A$
   
5. $A\vee 1=1$
   
6. $A\vee 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=(\mathrm{\neg }A)\vee B$

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

$A$	$B$	$A\to B$	$(\mathrm{\neg }A)\vee B$
1	1	1	1
1	0	0	0
0	1	1	1
0	0	1	1

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

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

$\mathrm{\neg }(A\to B)=A\vee (\mathrm{\neg }B)$

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

$\mathrm{\neg }(A\to B)=\mathrm{\neg }((\mathrm{\neg }A)\vee B)=A\vee (\mathrm{\neg }B)$

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

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

Совет

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

$A\to B=(\mathrm{\neg }B)\to (\mathrm{\neg }A)$

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

$A$	$B$	$A\to B$	$(\mathrm{\neg }B)\to (\mathrm{\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

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

---

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

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

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

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