Понятия логики высказываний. Лекция 1

Высказывания и операции над ними

Определение
Под высказыванием понимают языковое предложение, о котором можно сказать, истинно оно или ложно

Логические значения высказываний:
«истина» (И, 1, t)
«ложь» (Л, 0, f)

Примеры:
Париж – столица Англии
Шесть делится на два
Сколько будет 7*7?
7 * х = 21
Укажите высказывания и их логические значения

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

Пример
Карась не рыба
Это простое или сложное высказывание?

Все высказывания будем рассматривать с точностью до их логического значения
Пример
«В Красноярске есть педагогический вуз»
«Два – простое число»
Эти высказывания для нас одинаковые (оба истинны)

Элементарные высказывания будем обозначать латинскими буквами:
А, В, С, …
x, y, z, ...

Логическое значение высказывания определяется функцией истинности, которая принимает значения в двухэлементном множестве {0; 1}

Определение
Отрицанием высказывания А называется новое высказывание, которое является истинным, если А – ложно, и ложным, если А – истинно
Обозначение:
Читается: «не А», «Неверно, что А»

Определение
Отрицанием высказывания А называется новое высказывание, которое является истинным, если А – ложно, и ложным, если А – истинно
Таблица истинности

Определение
Конъюнкцией двух высказываний А, В называется новое высказывание, которое является истинным в единственном случае, если оба высказывания А, В – истинны
Обозначение:
Читается: «А и В»

Определение
Конъюнкцией двух высказываний А, В называется новое высказывание, которое является истинным в единственном случае, если оба высказывания А, В – истинны
Таблица истинности

Конъюнкция: логическое умножение АВ
Таблица истинности

Определение
Дизъюнкцией двух высказываний А, В называется новое высказывание, которое является ложным в единственном случае, если оба высказывания А, В – ложны
Обозначение:
Читается: «А или В»

Определение
Дизъюнкцией двух высказываний А, В называется новое высказывание, которое является ложным в единственном случае, если оба высказывания А, В – ложны
Таблица истинности

Определение
Импликацией двух высказываний А, В называется новое высказывание, которое является ложным в единственном случае, если первое высказывание А - истинно, а второе высказывание В – ложно

Импликация
Обозначение:
Читается: «если А, то В»
«из А следует В»
«А имплицирует В»
А – посылка
В – заключение

Определение
Импликацией двух высказываний А, В называется новое высказывание, которое является ложным в единственном случае, если первое высказывание А - истинно, а второе высказывание В – ложно
Таблица истинности

Определение
Эквивалентностью двух высказываний А, В называется новое высказывание, которое является истинным, если высказывания А, В имеют одинаковые логические значения, и ложным – в остальных случаях

Эквивалентность
Обозначение: A~B,
Читается:
- «А тогда и только тогда, когда В»
- «для того, чтобы А, необходимо и достаточно, чтобы В»
- «А эквивалентно В»

Определение
Эквивалентностью двух высказываний А, В называется новое высказывание, которое является истинным, если высказывания А, В имеют одинаковые логические значения, и ложным – в остальных случаях
Таблица истинности

Разделительное «или»
Обозначение:
Читается:
«А не эквивалентно В»
Операция “XOR”

Определение
Разделительное «или» для двух высказываний А, В это новое высказывание, которое истинно, если высказывания А, В имеют разные логические значения, и ложно – в остальных случаях.

Дополнительные связки

Таблицы истинности
Составляются для любой формулы логики высказываний
Если в формуле n переменных, то в таблице строк 2n
Пусть дана формула F(x1,x2,…,xn)
Список переменных формулы
Оценки списка переменных <0,0,…,0>,<0,1,…,1>, <1,1,0,…,1>, <1,1,…,1> и т.п.

Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре: (0,0), (0,1), (1,0), (1,1).
Если формула содержит три переменные, то возможных наборов значений переменных восемь:
(0,0,0), (0,0,1), (0,1,0), (0,1,1),
(1,0,0), (1,0,1), (1,1,0), (1,1,1).
Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д.

Основные законы алгебры логики

Выражение одних логических связок через другие:
А⊃В≡¬А∨В≡¬(А∧¬В)
А~В≡(А⊃В)∧(В⊃А)≡(¬A∨B)∧(¬B∨A) ≡ (А∧В)∨(¬А∧¬В)
А∨В≡¬А⊃В≡¬(¬А∧¬В)
А∧В≡¬(А⊃¬В)≡(¬(¬А∨¬В))
А В≡ ¬ (А~В) =(А∧¬В)∨(¬А∧В)

Тавтология
Некоторые формулы принимают значение “истина” при любых значениях истинности входящих в них переменных. Например, формула А v
Такие формулы называются тождественно истинными формулами или тавтологиями.
Высказывания, которые формализуются тавтологиями, называются логически истинными высказываниями.

Тождественная ложь
В качестве другого примера рассмотрим формулу А & , которой соответствует, например, высказывание “Катя самая высокая девочка в классе, и в классе есть девочки выше Кати”. Очевидно, что эта формула ложна, так как либо А, либо обязательно ложно.
Такие формулы называются тождественно ложными формулами или противоречиями.
Высказывания, которые формализуются противоречиями, называются логически ложными высказываниями.

Тождественная ложь
При всех наборах значений переменных x и y формула принимает значение 0, то есть является тождественно ложной.