Основные понятия и определения

Понятие множества является исходным не определяемым строго понятием. Приведем здесь определение множества (точнее, пояснение идеи множества), принадлежащее Г. Кантору: "Под многообразием или множеством я понимаю вообще все многое, которое возможно мыслить как единое, т.е. такую совокупность определенных элементов, которая посредством одного закона может быть соединена в одно целое".

Множества будем, как правило, обозначать большими буквами латинского алфавита, а их элементы — малыми, хотя иногда от этого соглашения придется отступать, так как элементами некоторого множества могут быть другие множества. Тот факт, что элемент а принадлежит множеству $A$ , записывается в виде $a\in A$ .

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

Индивидная константа (или просто константа) с областью значений $A$ обозначает фиксированный элемент множества $A$ . Таковы, например, обозначения (записи в определенной системе счисления) действительных чисел: $0;\,2;\,7,\!34$ . Для двух констант $b$ и $b$ с областью значений $A$ будем писать $a=b$ , понимая под этим совпадение обозначаемых ими элементов множества $A$ .

Индивидное переменное (или просто переменное) с областью значений $A$ обозначает произвольный, заранее не определенный элемент множества $A$ . При этом говорят, что переменное $x$ пробегает множество $A$ или переменное $x$ принимает произвольные значения на множестве $A$ . Можно фиксировать значение переменного $x$ , записав $x=a$ , где $a$ — константа с той же областью значений, что и $x$ . В этом случае говорят, что вместо переменного $x$ подставлено его конкретное значение $a$ , или произведена подстановка $a$ вместо $x$ , или переменное $x$ приняло значение $a$ .

Равенство переменных $x=y$ понимается так: всякий раз, когда переменное $x$ принимает произвольное значение $a$ , переменное $y$ принимает то же самое значение $a$ , и наоборот. Таким образом, равные переменные "синхронно" принимают всегда одни и те же значения.

Обычно константы и переменные, область значений которых есть некоторое числовое множество, а именно одно из множеств $\mathbb{N},\, \mathbb{Z},\, \mathbb{Q},\, \mathbb{R}$ и $\mathbb{C}$ , называют соответственно натуральными, целыми (или целочисленными), рациональными, действительными и комплексными константами и переменными. В курсе дискретной математики мы будем использовать различные константы и переменные, область значений которых не всегда является числовым множеством.

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

Логические операции (связки) над множествами

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

1. Дизъюнкция $\lor$ : высказывание $P\lor Q$ (читается: " $P$ или $Q$ ") истинно тогда и только тогда, когда истинно хотя бы одно из высказываний $P$ и $Q$ .

2. Конъюнкция $\land$ : высказывание $P\land Q$ (читается: " $P$ и $Q$ ") истинно тогда и только тогда, когда истинны оба высказывания $P$ и $Q$ .

3. Отрицание $\lnot$ : высказывание $\lnot P$ (читается: "не $P$ ") истинно тогда и только тогда, когда $P$ ложно.

4. Импликация $\Rightarrow$ : высказывание $P \Rightarrow Q$ (читается: "если $P$ , то $Q$ " или " $P$ влечет $Q$ ") истинно тогда и только тогда, когда истинно высказывание или оба высказывания ложны.

5. Эквивалентность (или равносильность) $\Leftrightarrow$ : высказывание $P \Leftrightarrow Q$ (читается: " $P$ , если и только если $Q$ ") истинно тогда и только тогда, когда оба высказывания $P$ и $Q$ либо одновременно истинны, либо одновременно ложны. Любые два высказывания $P$ и $Q$ , такие, что истинно $P \Leftrightarrow Q$ , называют логически эквивалентными или равносильными.

Записывая высказывания с помощью логических операций, мы предполагаем, что очередность выполнения всех операций определяется расстановкой скобок. Для упрощения записи скобки зачастую опускают, принимая при этом определенный порядок выполнения операций ("соглашение о приоритетах").

Операция отрицания всегда выполняется первой, и потому ее в скобки не заключают. Второй выполняется операция конъюнкции, затем дизъюнкции и, наконец, импликации и эквивалентности. Например, высказывание $(\lnot P)\lor Q$ записывают так: $\lnot P\lor Q$ . Это высказывание есть дизъюнкция двух высказываний: первое является отрицанием $P$ , а второе — $Q$ . В отличие от него высказывание $\lnot (P\lor Q)$ есть отрицание дизъюнкции высказываний $P$ и $Q$ .

Например, высказывание $\lnot P\land Q\lor\lnot Q\land P \Rightarrow\lnot Q$ после расстановки скобок в соответствии с приоритетами примет вид

$\bigl(((\lnot P)\land Q)\lor ((\lnot Q)\land P)\bigr)\Rightarrow (\lnot Q).$

Сделаем некоторые комментарии по поводу введенных выше логических связок. Содержательная трактовка дизъюнкции, конъюнкции и отрицания не нуждается в специальных разъяснениях. Импликация $P \Rightarrow Q$ истинна, по определению, всякий раз, когда истинно высказывание $Q$ (независимо от истинности $P$ ) или $P$ и $Q$ одновременно ложны. Таким образом, если импликация $P\Rightarrow Q$ истинна, то при истинности $P$ имеет место истинность $Q$ , но обратное может и не выполняться, т.е. при ложности $P$ высказывание $Q$ может быть как истинным, так и ложным. Это и мотивирует прочтение импликации в виде "если $P$ , то $Q$ ". Нетрудно также понять, что высказывание $P\Rightarrow Q$ равносильно высказыванию $\lnot P\lor Q$ и тем самым содержательно "если $P$ , то $Q$ " отождествляется с "не $P$ или $Q$ ".

Равносильность $\Leftrightarrow$ есть не что иное, как "двусторонняя импликация", т.е. $P\Leftrightarrow Q$ равносильно $(P \Rightarrow Q)\land (Q \Rightarrow P)$ . Это означает, что из истинности $P$ следует истинность $Q$ и, наоборот, из истинности $Q$ следует истинность $P$ .

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

В первых двух столбцах таблицы записывают все возможные наборы значений, которые могут принимать высказывания $P$ и $Q$ . Истинность высказывания обозначают буквой "И" или цифрой 1, а ложность — буквой "Л" или цифрой 0. Остальные столбцы заполняют слева направо. Так для каждого набора значений $P$ и $Q$ находят соответствующие значения высказываний.

Наиболее простой вид имеют таблицы истинности логических операций (табл. 1.1-1.5).

Рассмотрим сложное высказывание $(\lnot P\land Q)\Rightarrow (\lnot Q\land P)$ . Для удобства вычислений обозначим высказывание $\lnot P\land Q$ через $A$ , высказывание $\lnot Q\land P$ через $B$ , а исходное высказывание запишем в виде $A \Rightarrow B$ . Таблица истинности этого высказывания состоит из столбцов $P,\,Q,\,A,\,B$ и $A \Rightarrow B$ .