Мощность.
Мощность конечного множества равна числу его элементов. Мощность множества AA обозначается как ∣A∣.
Два множества A и B называют равномощными, если число элементов в них совпадает. Обозначение: ∣A∣=∣B∣ для мощностей или A∼B для самих множеств.
Важно не путать равномощные множества с равными, это не одно и то же. Равные множества всегда равномощные, а вот равномощные не обязательно равны: у них совпадает только количество элементов, но сами элементы могут быть и разными.
Формула включений-исключений
Для трёх множеств
Высказывания и основные логические операторы
Высказывание — это повествовательное предложение, которое либо истинно, либо ложно. Но оно не может быть и тем, и другим одновременно. Если высказывание истинно, его значение приравнивают к единице, если ложно — к нулю. Если высказывания содержат только одно утверждение, то их называют элементарными. Из них можно собирать более сложные, составные высказывания. Для этого используют грамматические связки «не», «и», «или», «если..., то...», «тогда и только тогда, когда» и другие.
Отрицание высказывания A — составное высказывание, которое является истинным, если высказывание A ложно, и ложным, если A истинно. Отрицание обозначается как ¬A или ‾A и читается «неверно, что A».
Отрицание — это унарная операция, так как работает с одним высказыванием. Большинство же операций являются бинарными, то есть работают с двумя высказываниями.
Конъюнкция (логическое умножение) двух высказываний A, B — новое высказывание, которое считается истинным, если оба исходных высказывания истинны, и ложным во всех остальных случаях.
Конъюнкция высказываний A, B обозначается A∧B. Также можно встретить обозначение A & B или даже просто AB без дополнительного знака.
Дизъюнкция (логическое сложение) двух высказываний A, B — составное высказывание, которое считается ложным, если оба исходных высказывания ложны, и истинным во всех остальных случаях.
Дизъюнкция высказываний A, B обозначается A∨B и читается как «A или B».
Формулы и таблицы истинности
Формула — элементарное или составное высказывание. В составном высказывании используются элементарные, а также логические операции и скобки.
Операции внутри формул выполняют по порядку. Вот он:
- Отрицание ¬.
- Конъюнкция ∧.
- Дизъюнкция ∨.
Подформула — часть формулы, которая тоже является формулой.
Формулы X и Y называют равносильными, если они принимают совпадающие значения на каждом из возможных наборов входящих в них высказываний. То есть у равносильных формул совпадают правые столбцы в таблице истинности.
Если формула X принимает значение 11 при любых значениях входящих в неё элементарных высказываний, то она называется тождественно истинной. В этом случае пишут X≡1
Если формула X принимает значение 0 при любых значениях входящих в неё элементарных высказываний, то она называется тождественно ложной. В этом случае пишут X≡0