Высказывания. Логика высказываний.

Основным понятием математической логики является понятие «высказывания».

Высказывание – это всякое повествовательное предложение, о котором можно однозначно сказать, что оно истинно или ложно.

Примеры. Высказывание 1) «Лондон – столица летних Олимпийских игр 2012 года» - истинно.

2) «21>23» - ложно.

3) Каждый параллелограмм есть квадрат — ложно.

4) Земля, планета солнечной системы — истинно.

Примеры предложений не являющихся высказываниями.

а) Студенты университета - предложение не является высказыванием, так как оно ничего не утверждает о студентах.

б) Треугольник ABC равен треугольнику А*В*С* - предложение не является высказыванием, так как мы не можем определить, истинно оно или ложно, потому что не знаем, о каких именно треугольниках идет речь.

Еще раз подчеркнем, что отличительным признаком любого высказывания является его свойство быть истинным или ложным, а этим свойством два вышеприведенных предложения не обладают.

Элементарное (простое) высказывание – это одно утверждение. Будем обозначать элементарные высказывания малыми буквами латинского алфавита x, y, z,…, истинное высказывание – цифрой 1, ложное высказывание – цифрой 0.

Мы будем рассматривать функции на множестве переменных x и y. Переменные и функции могут принимать только значения 0 и 1. Это булевы функции.

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

Обозначаются F(x,y,z…)

Также могут принимать значения «ИСТИНА» или «ЛОЖЬ» в зависимости от того, какие значения имеют входящие в их состав логические переменные и от действий над ними.

Пример. Так, из элементарных высказываний «Петров – врач», «Петров - шахматист» при помощи связки «и» можно получить составное высказывание «Петров - врач и шахматист», понимаемое как «Петров - врач, хорошо играющий в шахматы». При помощи связки «или» из этих же высказываний можно получить составное высказывание «Петров — врач или шахматист», понимаемое в алгебре логики как «Петров или врач, или шахматист, или и врач и шахматист одновременно».

Основные логические операции

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

Отрицание ¬x ( читается «не x»).

Присоединение частицы «НЕ» к высказыванию называется операцией логического отрицания, или инверсией.

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

F(x) = ¬x или F(x) = или F(x) = not x

Таблица истинности этой функции имеет следующий вид:

x	¬x
0	1
1	0

Мы видим, что отрицание меняет возможные значения переменной на противоположные.

Примеры:

x	¬x
«Число 5 является делителем числа 45»	«Число 5 не является делителем числа 45»
«На полке стоит книга Л.Н.Толстого»	«На полке не стоит книга Л.Н.Толстого» или «На полке стоит книга М.Е. Салтыкова-Щедрина» или «Книга Л.Н.Толстого находится не на полке»
«Все юноши 11-х классов – отличники »	«Неверно, что все юноши 11-х классов – отличники» или «Не все юноши 11-х классов – отличники »

Дизъюнкция xy (читается «x или y»).

Объединение двух или более высказываний в одно с помощью союза «ИЛИ» называется операцией логического сложения, или дизъюнкцией.

Логическая функция, полученная в результате дизъюнкции, истинна тогда, когда истинна хотя бы одна из входящих в него логических переменных

F(x, y) = xÚy или F(x, y) = x + y или F(x, y) = x or y

Таблица истинности этой функции имеет следующий вид:

x	y	xÚy
0	0	0
0	1	1
1	0	1
1	1	1

Мы видим, что дизъюнкция равна 1, если хотя бы один из ее аргументов равен 1.

Примеры.

x	y	xÚy	xÚy
«Девять число кратное трем»	«20>35»	«Девять число кратное трем или 20>35»	Истинно - 1
«10 не делится на 2	5 не больше 3»	«10 не делится на 2 или 5 не больше 3»	Ложно - 0
«Колумб был в Индии»	«Колумб был в Египте»	«Колумб был в Индии или в Египте»	Истинно - 1

Конъюнкция x&y (читается «x и y»).

Объединение двух или более высказываний в одно с помощью союза «И» называется операцией логического умножения, или конъюнкцией

Логическая функция, полученная в результате конъюнкции, истинна тогда и только тогда, когда истинны все входящие в него логические переменные.

F(x, y) = x & y или F(x, y) = x  y или F(x, y) = x * y или F(x, y) = x and y

Таблица истинности этой функции имеет следующий вид:

x	y	x&y
0	0	0
0	1	0
1	0	0
1	1	1

Мы видим, что конъюнкция равна 1 тогда и только тогда, когда оба ее аргумента равны 1.

Примеры.

x	y	x&y	x&y
«Москва столица России»	«2+2=4»	«Москва столица России и 2+2=4»	Истинно - 1
«10 не делится на 2»	«5 больше 3»	«10 не делится на 2 и 5 больше 3»	Ложно - 0
«10 делится на 2»	«5 больше 3»	«10 делится на 2 и 5 больше 3»	Истинно - 1

Сложение по модулю «2» xy (читается «исключающее ИЛИ», «логическое ЛИБО», «неравносильность», «неэквивалентность», «логическое сложение», «строгая дизъюнкция»).

Функция Å даёт 1 только когда первый операнд не равен второму операнду. Она похожа на арифметическое сложение: 0Å0=0, 0Å1=1, 1Å0=1, но не всегда: в булевой алгебре 1Å1=0, а не 2, как в арифметике - булевы величины 1 и 0 не являются числами и для них арифметика неприменима. Обозначения этой функции: Å, +2, +, xor, ЛИБО.

Таблица истинности этой функции имеет следующий вид:

x	y	xÅy
0	0	0
0	1	1
1	0	1
1	1	0

Пример.

x	y	xÅy
«Кошка охотится за мышами»	«Кошка спит на диване».	Кошка охотится за мышами либо кошка спит на диване.
Очевидно, что новое высказывание XÅY истинно только в двух случаях: когда кошка охотится за мышами или когда кошка мирно спит. Это высказывание будет ложным, если кошка не делает ни того, ни другого, т.е. когда оба события не происходят. И высказывание будет ложным и тогда, когда предполагается, что оба события будут происходить одновременно.

Импликация xy (читается «если x то y»).

Объединение двух высказываний, из которых первое является условием, а второе – следствием из него, называется импликацией.

Импликация ложна тогда и только тогда, когда условие истинно, а следствие ложно

Таблица истинности этой функции имеет следующий вид:

x	y	xy
0	0	1
0	1	1
1	0	0
1	1	1

Импликация как булева функция ложна лишь тогда, когда посылка истинна, а следствие ложно.

Примеры. 1) «Данный четырёхугольник – квадрат» (А) и «около данного четырёхугольника можно описать окружность» (В). Рассмотрим составное высказывание А→В, понимаемое как если данный четырёхугольник квадрат, то около него можно описать окружность. Есть три варианта, когда высказывание А→В истинно:

I) А истинно и В истинно, то есть данный четырёхугольник квадрат, и около него можно описать окружность;

II) А ложно и В истинно, то есть данный четырёхугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырёхугольника);

III) A ложно и B ложно, то есть данный четырёхугольник не является квадратом, и около него нельзя описать окружность;

IV) Ложен только один вариант, когда А истинно, а В ложно, то есть данный четырёхугольник является квадратом, но около него нельзя описать окружность.

2) Утверждение «если каждое слагаемое делится на 3, то и сумма делится на 3» истинно, т.е. из высказывания «каждое слагаемое делится на 3» следует высказывание «сумма делится на 3». Посмотрим, какие наборы значений истинности условия и заключения возможны, когда истинно все утверждение. Возьмем, например, в качестве слагаемых числа 6 и 9. В этом случае истинны и условие, и заключение, и все утверждение. Если же взять числа 4 и 5, то условие будет ложным, а заключение истинным. Для чисел 4 и 7 и условие и заключение ложны. (Если Вы сомневаетесь в истинности высказывания для последнего случая попробуйте произнести его в сослагательном наклонении: если бы числа 4 и 7 делились бы на 3, то и их сумма делилась бы на 3). Очевидно, что только один случай невозможен: мы не найдем таких двух слагаемых, чтобы каждое из них делилось на 3, а их сумма не делилась на 3, т.е. чтобы условие было истинным, а заключение ложным. Из истины не может следовать ложь, иначе логика теряет смысл.

Эквиваленция ( или эквивалентность) x~y (x y) (читается «x тогда и только тогда, когда y»).

Эквивалентность – это логическая операция, объединяющая два простых высказывания в одно составное и которое является истинным тогда и только тогда, когда оба исходных высказывания одновременно либо истинны, либо ложны.

Таблица истинности этой функции имеет следующий вид:

x	y	x~y
0	0	1
0	1	0
1	0	0
1	1	1

Пример. Рассмотрим возможные значении сложного высказывания, являющегося эквивалентностью: Учитель утверждает, что 5 в четверти ученику он поставит тогда и только тогда, когда ученик получит 5 на зачёте. 1) Ученик получил 5 на зачёте и 5 в четверти, т.е. учитель выполнил своё обещание, следовательно, высказывание является истинным. 2) Ученик не получил на зачёте 5, и учитель не поставил ему 5 в четверти, т.е. учитель своё обещание сдержал, высказывание является истинным. 3) Ученик не получил на зачёте 5, но учитель поставил ему 5 в четверти, т.е. учитель своё обещание не сдержал, высказывание является ложным. 4) Ученик получил на зачёте 5, но учитель не поставил ему 5 в четверти, т.е. учитель своё обещание не сдержал, высказывание является ложным.