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

1.1. Понятие высказывания. Понятие “высказывание” является первичным, оно не определяется, а лишь поясняется. Под высказыванием понимают повествовательное предложение, о котором можно однозначно сказать, истинно оно или ложно. Например, “Земля — планета солнечной системы” (истинное высказывание), “Луна — искусственный спутник Земли” (ложное высказывание), “4>5” (ложное высказывание), “4>3” (истинное высказывание), “ х²0 для каждого действительного числа х” (истинное высказывание), “Существует действительное число х такое, что х²=1” (ложное высказывание).

Любое высказывание либо истинно, либо ложно, и никакое высказывание не является одновременно истинным и ложным.

Имеются повествовательные предложения, которые не являются высказываниями. Например, повествовательное предложение “Сегодня хорошая погода” не является высказыванием, так как о нём нельзя однозначно судить, истинно оно или ложно.

Следующие предложения “Который час?”, “Да здравствует наука!” не являются высказываниями, так как они не являются повествовательными. Такие предложения, как, определения, также не являются высказываниями. Например, определение “Натуральное число называется чётным, если оно делится на 2” не является высказыванием. Однако, повествовательное предложение “Если число делится на 2, то оно чётное” — высказывание, и притом истинное. Повествовательное предложение ”Если натуральное число является чётным, то оно делится на 2” — также истинное высказывание.

Упражнение 1.1.Какие из следующих предложений являются высказываниями?

а) Пермь — столица Пермского края.

б) Студент технического университета.

в) Треугольник АВСподобен треугольникуАВС.

г) Земля есть спутник Юпитера.

д) 3+.

е) Кислород — газ.

ж) Каша — вкусное блюдо.

з) Математика — интересный предмет.

и) Картины Пикассо слишком абстрактны.

к) Железо тяжелее свинца.

л) Да здравствуют музы!

м) Треугольник называется равносторонним, если все его стороны равны.

н) Если в треугольнике все углы равны, то он равносторонний.

о) Сегодня плохая погода.

п) В романе А.Дюма “Граф Монте-Кристо” 179 персонажей.

р) Река Кама впадает в Каспийское море.

Решение. б) Это предложение не является высказыванием, потому что оно ничего не утверждает о студенте.

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

ж) Предложение не является высказыванием, так как понятие “вкусное блюдо” слишком неопределенно.

В логике высказываний (раздел математической логики) отвлекаются от смыслового содержания высказывания и приписывают каждому высказыванию его истинностное значение (“истина”, “ложь”), отождествляя высказывание с его истинностным значением. Эти истинностные значения — истина и ложь — называют логическими значениями высказываний.

Высказывания будем обозначать строчными буквами латинского алфавита а, b, c, ... , a₁, a₂, …,. Эти буквы называются пропозициональными переменными. Их логические значения (истина, ложь) обозначаются через соответственно буквами И и Л, или знаками 1 и 0, соответственно. Во многих приложениях принято именно последнее обозначение, которого будем придерживаться и мы.

Пусть А — высказывание. Если это высказывание истинно, то пишут А=1, если же оно ложно, то пишут А=0. Например, (3>2)=1; (2>5)=0; (22)=0; (sin — периодическая функция)=1.

Упражнение 1.2.Укажите, какие из высказываний предыдущего упражнения истинные, а какие — ложные.

1.2. Основные логические операции над высказываниями. Из высказываний a, b, c, ... можно составить новые составные высказывания. Для этого используются следующие так называемые логические операции над высказываниями:

1) отрицание ();

2) конъюнкция ();

3) дизъюнкция ();

4) импликация ();

5) эквиваленция ().

Определение 1. Отрицанием высказывания a называется высказывание, обозначаемое символом a, которое является истинным, если a ложно, и ложным, если a истинно. Читается: “неверно, что a”, или, короче “не a”.

Например, для истинного высказывания “4>3” отрицанием будет ложное высказывание “неверно, что 4>3“, или короче “4 не больше 3”, которое обычно записывается так:  (4>3) или 43.

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

a	a
0 1	1 0

В строках первого столбца таблицы указаны два возможных логических значения высказывания a: 1 (истина) и 0 (ложь), в строках второго столбца таблицы — соответствующие логические значения отрицания a: 0 (ложь) в первом случае и 1 (истина) — во втором.

Упражнение 1.3. Сформулируйте отрицания следующих высказываний; укажите значения истинности данных высказываний и их отрицаний:

а) Кама впадает в Каспийское море.

б) Число 36 не делится на число 6.

в) 85.

г) 58.

д) Все простые числа нечётны.

Упражнение 1.4. Установите, какие из высказываний в следующих парах являются отрицаниями друг друга и какие — нет (объясните почему):

а) 34, 34.

б) 69, 69.

в) “Треугольник АВС прямоугольный”, “Треугольник АВС тупоугольный”.

г) “Натуральное число n чётно”, “Натуральное число n нечётно”.

д) “Функция f нечётна”, “Функция f чётна”.

е) “Все простые числа нёчетны”, “Все простые числа чётны”

ж) “Все простые числа нечётны”, “Существует простое чётное число”.

з) “Человеку известны все виды животных, обитающих на Земле”, “На Земле существует вид животных, не известный человеку”.

и) “Существуют иррациональные числа”, “Все числа рациональные”.

Решение. а) Высказывание “34” не является отрицанием высказывания “3<4” так как что требование не быть меньше 4 предполагает две возможности: быть равным 4 и быть больше 4. Таким образом, отрицанием высказывания “34” является высказывание “34”.

Упражнение 1.5. Следующие высказывания запишите без знака отрицания:

а) (аb); в) (аb);

б) (аb); г) (аb).

Определение 2. Конъюнкцией двух высказываний a и b называется высказывание, обозначаемое символом ab, которое является истинным, если истинны оба высказывания a и b, и ложным, если ложно хотя бы одно из них. Читается: “a и b”. Высказывания a и b называются членами конъюнкции.

Например, для высказываний “3<8” и “8<10” конъюнкция “(3<8)(8<10)” будет истинным высказыванием: “(3<8)(8<10)=1 (это высказывание записывают короче: “3<8<10”).

Зависимость логического значения конъюнкции ab от логических значений её членов a и b можно выразить следующей таблицей, называемой таблицей истинности конъюнкции:

a	b	ab
0 0 1 1	0 1 0 1	0 0 0 1

В строках двух первых её столбцов указаны всевозможные комбинации логических значений высказываний a и b, в строках третьего столбца — соответствующие логические значения конъюнкции .

Из определения 2 следует, что союз “и” в логике высказываний употребляется в том же смысле, что и в повседневной речи. Но в обычной речи не принято соединять союзом “и” два высказывания, далёкие друг от друга по содержанию. В логике же высказываний рассматривается конъюнкция двух любых высказываний.

Определение 3. Дизъюнкцией двух высказываний a и b называется высказывание, обозначаемое символом ab, которое является истинным, если истинно хотя бы одно из высказываний a и b, и ложным, если оба они ложны. Читается: “a или b”. Высказывания a и b называются членами дизъюнкции.

Например, для высказываний “10>8” и “8=10” дизъюнкция “(10>8)(8=10)” будет истинным высказыванием: “(10>8)(8=10)”=1 (это высказывание записывают короче: “107”).

Таблица истинности дизъюнкции, выражающая зависимость логического значения дизъюнкции ab от логических значений её членов a и b имеет вид:

a	b	ab
0 0 1 1	0 1 0 1	0 1 1 1

В повседневной речи союз “или” употребляется в различном смысле: во-первых, в неисключающем, когда он выражает, что из двух высказываний по крайней мере одно истинно, а возможно, что и оба истинны, и, во-вторых, в исключающем, в смысле “либо ..., либо ...”, когда он выражает, что из двух высказываний истинно только одно, а другое ложно. Например, в предложении “Студенты готовят экзамен по учебникам или конспектам лекций” союз “или” имеет неисключающий смысл, а в предложении “Сегодня вечером мы пойдем в театр или в цирк” союз “или” употребляется в исключающем смысле. В логике высказываний союз “или” употребляется только в неисключающем смысле, что и выражает определение 3. Кроме того, в повседневной речи употребляют только дизъюнкции, члены которых как-то связаны по содержанию, тогда как в логике рассматриваются дизъюнкции любых двух высказываний.

Упражнение 1.6.Определите значение истинности следующих высказываний:

а) Пермь расположена на Каме и 23=6.

б) 8 — простое число и 11 — простое число.

в) 8 — простое число или 11 — простое число.

г) Число 2 чётное или это число простое.

д) 4 5, 45, 3721, 3721.

е) 22=4 или подводные лодки бороздят Камское водохранилище.

ж) 22=4, и 225, и 224.

Решение. а) Так как оба высказывания, к которым применяется операция конъюнкции, истинны, то согласно определения этой операции, их конъюнкция является истинным высказыванием.

Упражнение 1.7.Определите значения истинности высказыванийa,b,c,dиe, если:

а) a&(22=4) — истинное высказывание,

б) c(22=5) — истинное высказывание,

в) b&(22=4) — ложное высказывание,

г) d(22=5) — ложное высказывание,

д) e& (22=5) — ложное высказывание.

Решение. а) Конъюнкция высказываний является истинным высказыванием лишь в случае, когда оба из входящих в конъюнкцию составляющих высказываний (членов конъюнкции) истинны. В нашем случае второе соcтавляющее высказывание “22=4” истинно, а конъюнкция двух высказываний истинна. Поэтому первое соcтавляющее высказываниеаистинно.

Упражнение 1.8.Сформулируйте и запишите в виде конъюнкции или дизъюнкции условие истинности каждого предложения (аиb— действительные числа):

а) аb0. г)=0. ж) |a|6.

б) аb=0. д) |a|=3. з) а²+b²0.

в) а²+b²=0. е) |a|<3. и)0.

Решение. г) Произведение не равно нулю лишь в случае, когда оба сомножителя не равны нулю, т.е. (а0)&(b0).

Определение 4. Импликацией двух высказываний a и b называется высказывание, обозначаемое символом ab, которое считается ложным, если a истинно и b ложно, и истинным при всех других логических значениях высказываний a и b. Высказывание a называется условием или посылкой, высказывание b — заключением или следствием импликации.Читается: “если a, то b”.

Импликация ab читается также следующим образом: “из a следует b“, “a влечёт b“, “a достаточно для b“, “b необходимо для a“, “a имплицирует В“.

Таблица истинности импликации имеет вид:

a	b	ab
0 0 1 1	0 1 0 1	1 1 0 1

Например, импликации: “если 22=5, то 3>5” и “если 22=4, то 9 делится на 3” обе истинны, так как у первой из них посылка ложна, а у второй истинно следствие. А импликация “если 22=4, то 3>5” ложна, так как посылка истинна, а следствие ложно.

Принятые в логике чтения импликации ab неудобны в том отношении, что в обычной речи предложения “если a, то b“, “из a следует b“ и “a влечёт b“ имеют совсем иной смысл: они выражают, что между высказываниями a и b существует некоторая зависимость, в силу которой высказывание b как-то может быть выведено из высказывания a. С этой точки зрения предложение “Если 22=5, то Лондон — столица Франции” лишено смысла. Но в силу определения 4 оно имеет смысл в логике высказываний. Причём оно является истинным высказыванием, так как посылка ложна. Таким образом, согласно определения 4 можно рассматривать импликацию любых двух высказываний, даже если они не связаны между собой по содержанию, и истинность импликации определяется только логическими значениями её посылки и заключения.

Значение импликации для математических доказательств состоит в том, что из истинности импликации и её посылки мы делаем вывод об истинности её следствия .

Определение 5. Эквиваленцией двух высказываний a и b называется высказывание, обозначаемое символом ab, которое является истинным, если оба высказывания a и b либо истинны, либо ложны, и ложным в остальных случаях. Читается: “a тогда и только тогда, когда b” или “a эквивалентна b“. Высказывания a и b называются членами эквиваленции.

Эквиваленция ab читается также следующим образом: “если a, то b, и обратно”, или “a равносильно b“, или же “a необходимо и достаточно для b“.

Таблица истинности эквиваленции имеет вид:

a	b	ab
0 0 1 1	0 1 0 1	1 0 0 1

Например, эквиваленция “SPQ с вершиной S и основанием PQ равнобедренный тогда и только тогда, когда в SPQ угол P равен углу Q“ истинна, так как оба её члена либо одновременно истинны, либо одновременно ложны, что известно из школьного курса геометрии.

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

Упражнение 1.9. Определите значения истинности следующих высказываний:

а) Если 12 делится на 6, то 12 делится на 3.

б) Если 11 делится на 6, то 11 делится на 3.

в) Если 15 делится на 6, то 15 делится на 3.

г) Если 15 делится на 3, то 15 делится на 6.

д) Если Саратов расположен на Каме, то белые медведи обитают в Африке.

е) 12 делится на 6 тогда и только тогда, когда 12 делится на 3.

ж) 11 делится на 6 тогда и только тогда, когда 11 делится на 3.

з) 15 делится на 6 тогда и только тогда, когда 15 делится на 3.

и) 15 делится на 5 тогда и только тогда, когда 15 делится на 4.

к) Тело массой m обладает потенциальной энергией mgh тогда и только тогда, когда оно находится нв высоте h над поверхностью земли.

Решение. а) Так как высказывание-посылка “12 делится на 6” истинно и высказывание-следствие “12 делится на 3” истинно, то и составное высказывание на основании определения импликации также истинно.

ж) Из определения эквивалентности видим, что высказывание вида РQ истинно, если логическое значение высказываний Р и Q совпадают, и ложно в противном случае. В данном примере оба высказывания, к которым применяется связка “тогда и только тогда”, ложны. Поэтому всё составное высказывание истинно.

Упражнение 1.10. Пусть через a обозначено высказывание “9 делится на 3”, а через b — высказывание “8 делится на 3”. Определите значения истинности следующих высказываний: а) ab; б) ba; в) ab; г) ab; д) ab; е) ba; ж) ab; з) aa; и) ab; к) ab; л) ab; м) ab.

Решение. е) Имеем a =1, b=0. Поэтому 01 =10=1.

Упражнение 1.11. Определите значения истинности высказываний a, b, c и d в следующих предложениях, из которых первые два истинны, а последние два ложны:

а) Если 4 — чётное число, то a.

б) Если b, то 4 — нечётное число.

в) Если 4 — чётное число, то c.

г) Если d, то 4 — нечётное число.

Решение. а) Согласно определения при истинной посылке импликация истинна только в том случае, когда истинно заключение. В нашем случае посылка «4 — чётное число» истинна и истинна вся импликация. Значит, a  истинна.

Упражнение 1.12. Определите значения истинности высказываний a, b, c и d в следующих предложениях, из которых первые два истинны, а последние два ложны: а) a  (2<3); б) b  (2>3); в) c  (2<3); г) d  (2>3).

Упражнение 1.13. Пусть через a обозначено высказывание “Этот треугольник равнобедренный”, а через b — высказывание “Этот треугольник равносторонний”. Прочитайте следующие высказывания:

а) ab; г) (ab)a;

б) (ab); д) (ab) b;

в) ab; е) (ab) a.

Решение. е) Если треугольник равнобедренный и неравносторонний, то неверно, что он неравнобедренный.

Упражнение 1.14. Следующие составные высказывания расчлените на простые и запишите символически, введя буквенные обозначения для простых их составляющих:

а) Если 18 делится на 2 и не делится на 3, то оно не делится на 6.

б) Произведение трёх чисел равно нулю тогда и только тогда, когда одно из них равно нулю.

в) Если производная функции в точке равна нулю и вторая производная этой же точке отрицательна, то данная точка есть точка максимума этой функции.

г) Если в треугольнике медиана не является высотой и биссектрисой, то этот треугольник неравнобедренный и неравносторонний.

Решение. г) Выделим и следующим образом обозначим простейшие составляющие высказывания:

a: “В треугольнике медиана является высотой”;

b: “В треугольнике медиана является биссектрисой”;

c: “Этот треугольник равнобедренный”;

d: “Этот треугольник равносторонний”.

Тогда данное высказывание символически записывается так:

(ab)(cd).

1.3. Дальнейшие логические операции над высказываниями. Наряду с введёнными выше основными логическими операциями рассматриваются также другие, не менее важные, операции. Это  следующие:

a|b  штрих Шеффера, ab  стрелка Пирса,  ab кольцевая сумма. Они определяются следующими таблицами истинностей:

a	b	a|b	ab	ab
0	0	1	1	0
0	1	1	0	1
1	0	1	0	1
1	1	0	0	0

Легко видеть, что эти операции  отрицания операций соответственно конъюнкции, дизъюнкции и эквиваленции (для этого достаточно сравнить с таблицами истинностей соответствующих операций). Поэтому первые два из них называются, соответственно, антиконъюнкцией и антидизъюнкцией. Третья же называется также логическим сложением или сложением по модулю 2.