Шпаргалка по "Высшей математике"

1. Исчисление высказываний, логические операции.

Высказывание — это выражение, относительно которого можно сделать вывод o его истинности или ложности. Высказывания могут быть истинными, ложными или содержащими истину и ложь в разных соотношениях.

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

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

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

1) Конъюнкция

        Логическое умножение, выражение «AND», обозначается знаком «∧».

Таблица истинности для пары операндов — 1000. Конъюнкция возвращает 1 только тогда, когда оба операнда равны 1, иначе 0.

2) Дизъюнкция

Логическое сложение, выражение «OR», обозначается знаком «⋁». Также называется «слабой дизъюнкцией».

Таблица истинности для пары операндов — 1110. Возвращает 0 только тогда, когда оба операнда равны 0, иначе 1.

3) Отрицание

        Инверсия, негация, выражение «NOT», обозначается знаком «¬».

Возвращает противоположный знак: для 0 — 1, для 1 — 0.

4) Сильная дизъюнкция

        Исключающая дизъюнкция, выражение «XOR», обозначается символами «⊻» или «⊕».

Таблица истинности для пары операндов — 0110. Возвращает 1 только тогда, когда только один из них равен 1, а второй равен 0.

Может быть определена через основные операции: (A ⊻ B) = ((A ∧ ¬ B) ⋁ (¬ A ∧ B)).

5) Эквивалентность

Тождество, равенство, выражение «EQ», обозначается символами «↔», «⇔» или «≡».

Таблица истинности для пары операндов — 1001. Возвращает 1 только тогда, когда оба операнда равны одновременно 0 или 1.

6) Импликация

        Выражает зависимость причины и следствия, обозначается символами «⇒», «→» или «⊃».

Таблица истинности для пары операндов — 1011. То есть возвращает ложь только тогда, когда первый операнд равен 1, а второй — 0.

Может быть определена через основные операции: (A → B) = (¬ A ⋁ B).
7) Штрих Шеффера

Записывается обычно как «|»

Таблица истинности - 1110. Возвращает 0 только тогда, когда оба операнда равны 1.

Можно определить через основные операции как ¬ (A ∧ B)

2. Исчисление предикатов, кванторы.

Предикат — это утверждение, высказанное о субъекте. Субъектом высказывания называется то, о чём делается утверждение. Предикат имеет множество значений {0, 1}.

Например: 

Обозначим предикатом EQ(x, y) отношение равенства (“x = y”), где x и y принадлежат R. В этом случае предикат EQ будет принимать истинное значение для всех равных x и y.

Квантор – общее название для логических операций, ограничивающих область истинности какого-либо предиката и создающих высказывание. Чаще всего выделяют только два квантора:

- квантор всеобщности (обозначение: , читается: для любого…, для каждого…, для всех…, каждый…, любой…, все…)[pic 1]

- квантор существования (обозначение: , читается: существует…, найдётся…)[pic 2]

Исчисление предикатов же – это формальное исчисление, допускающее высказывания относительно переменных, фиксированных функций и предикатов. 

Предикаты, так же, как и высказывания, принимают два значения: истинное и ложное, поэтому к ним применимы все операции логики высказываний, а также кванторы:

[pic 3] [pic 4]