Отрицание.
Высказывание , которое истинно, если р ложно, и ложно, если р истинно, называется отрицанием.
Таблица истинности:
р | |
Пример:
р - число 5 делится на 3. р = 0.
- число 5 не делится на 3. = 1.
Конъюнкция (логическое умножение).
Пусть даны два высказывания р и q.
Конъюнкцией двух высказываний называется высказывание, которое истинно только тогда, когда истинны оба высказывания.
Задается союзом И. Обозначение .
Таблица истинности:
р | q | |
Пример:
А) Высказывание р: 15 делится на 3 - истина.
Высказывание q: 15 делится на 5 - истина.
: 15 делится на 3 и 5.- это истинное высказывание
Б) Высказывание р: 15 делится на 3 - истина.
Высказывание q: 15 делится на 6 - ложь.
: 15 делится на 3 и 6.- это ложное высказывание
3) Дизъюнкция (логическое сложение).
Дизъюнкцией двух высказываний называется высказывание, которое ложно только тогда, когда оба высказывания ложны.
Задается союзом ИЛИ. Обозначение .
Таблица истинности:
р | q | |
Пример:
А) Высказывание р: 15 делится на 3 - истина.
Высказывание q: 15 делится на 5 - истина.
: 15 делится на 3 или 5.- это истинное высказывание
Б) Высказывание р: 15 делится на 4 - ложь.
Высказывание q: 15 делится на 6 - ложь.
: 15 делится на 4 или 6.- это ложное высказывание
В) Высказывание р: 15 делится на 3 - истина.
Высказывание q: 15 делится на 6 - ложь.
: 15 делится на 3 или 5.- это истинное высказывание
Импликация.
Импликацией двух высказываний р и q называется высказывание, которое ложно только тогда, когда р – истинно, а q- ложно.
ЕСЛИ р, ТО q. Обозначение .
Таблица истинности:
р | q | |
Пример:
А) Высказывание р: 15 делится на 3 - истина.
Высказывание q: 15 делится на 5 - истина.
: Если 15 делится на 3, то 15 делится на 5.- это истинное высказывание
Б) Высказывание р: 15 делится на 3 - истина.
Высказывание q: 15 делится на 6 - ложь.
Если 15 делится на 3, то 15 делится на 6.- это ложное высказывание
В) Высказывание р: 15 делится на 4 – ложь.
Высказывание q: 15 делится на 6 - ложь.
Если 15 делится на 4, то 15 делится на 6.- это истинное высказывание
5) Эквиваленция.
6) Эквиваленцией двух высказываний р и q называется высказывание, которое истинно, если оба высказывания принимают одинаковые значения.
В словесной формулировке: тогда и только тогда; необходимо и достаточно; если и только если. Обозначение
Таблица истинности:
р | q | |
Пример:
р - треугольник равнобедренный.
q - углы при основании треугольника равны.
: Для того чтобы треугольник был равнобедренным необходимо и достаточно, чтобы углы при основании были равными.
7) Стрелка Пирса - ↓.
Логическая операция задается таблицей:
р | q | р ↓ q |
Стрелка Пирса является отрицанием дизъюнкции.
8) Штрих Шеффера - |.
Логическая операция задается таблицей:
р | q | р | q |
Штрих Шеффера является отрицанием конъюнкции.
Формулы.
Используя определенные выше логические операции (логические связки), мы можем конструировать все более сложные высказывания, которые будем записывать в виде формул.
Дадим декларативное определение формулы.
1) 0 и 1 –это формула.
2) Простые высказывания (р) и (q) есть формула.
3) Если () и () - формулы, то () – формула; () () - формула; () () - формула; () () – формула; () () – формула.
4) Других формул нет.
Пример:
() ()-формула.
Доказательство:
(р) и (q)-формулы (по 2), - формула (по 3), ()- формула (по 3), -формула (по 3), () -формула (по 3).
Соглашение о скобках.
1) Элементарные высказывания в скобки заключать не будем.
2) Будем считать, что отрицание связывает сильнее остальных операций, и поэтому скобок писать не будем.
3) связывает сильнее, чем , , .
4) связывает сильнее, чем и .
5) связывает сильнее, чем .
Пример:
Вместо ((р) (q)) ((r) ()) пишем р q r . Знак конъюнкции можно опускать: р q r .
Булевы функции.
Так как каждое высказывание задается на множестве {0,1}, то любая формула отображает свои значения на множество {0,1}. Таким образом, формула логики высказываний определяет на множестве {0,1} логическую функцию со значениями 0,1. Эти функции получили название булевых.
Равносильные формулы.
Две формулы Φ и Φ называются равносильными, если они принимают одинаковые значения при одинаковых наборах значений высказывательных переменных, входящих в эти формулы.
Обозначение равносильности:
Пример:
Φ = и Φ = q.
Их таблицы истинности:
р | q | Ф = | Ф2 = q | |
Сравнивая значения столбца Φ и Φ , приходим к выводу, что Φ равносильно Φ , то есть Φ Φ .