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

Логика – наука о законах и формах мышления, об общих схемах рассуждений.

Основоположник- английский математик Джорджан Буль (1815-1864 гг.)

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

Понятие «высказывание» первично.

Под высказываниями мы будем понимать такие повествовательные предложения, о которых имеет смысл говорить, что они истинны или ложны (но не то и другое вместе). Логическими значениями высказываний являются «истина» и «ложь». Высказывания будем обозначать большими латинскими буквами А, В, С, …, а их значения, т.е. «истина» или «ложь» – соответственно буквами «И» и «Л». Эти значения называются значениями истинности высказывания. Вместо обозначения «И» используют также обозначения: «1», «+», а вместо «Л» –– «0», «–».

Приведем примеры высказываний.

1) Минск – столица Республики Беларусь.

2) Рим – столица Англии.

3) Карп не рыба.

4) Число 10 делится на 2 и на 5.

5) Число 5 является корнем уравнения х2 + 5х – 50 = 0.

Высказывания 1), 4), 5) истинны, а высказывания 2) и 3) ложны.

Не являются высказываниями: вопросительные, восклицательные предложения, определения.

Пример. Определение «целое число называется четным, если оно делится на 2» не является высказыванием. Но повествовательное предложение «если целое число делится на 2, то оно четное» есть высказывание, и притом, истинное.

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

Логические операции над высказываниями.

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

Определение 1. Отрицанием высказывания А называется высказывание «не А», истинное, когда А ложно, и ложное, когда А истинно. Отрицание высказывания А обозначается символом .

Логические значения высказывания можно описывать с помощью таблицы истинности

А
И	Л
Л	И

Пусть А –– высказывание. Отрицание высказывания , т.е. высказывание , называется двойным отрицанием высказывания А. Очевидно, что логические значения высказываний и А совпадают.

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

Термин «конъюнкция» происходит от латинского слова «conjunctio» –– союз, связь.

Логические значения конъюнкции описываются следующей таблицей истинности:

А	В
И	И	И
И	Л	Л
Л	И	Л
Л	Л	Л

Например, для высказываний «10 делится на 2», «10 делится на 5» их конъюнкцией будет высказывание «10 делится на 2 и 10 делится на 5», которое, очевидно, истинно.

Из определений 1 и 2 ясно, что высказывание всегда ложно.

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

Термин «дизъюнкция» происходит от латинского слова «disjunctio» –– разобщение, различие.

Логические значения дизъюнкции описываются следующей таблицей истинности:

А	В
И	И	И
И	Л	И
Л	И	И
Л	Л	Л

Например, если высказывание А –– «5 < 7», а высказывание В –– «5 = 7», то –– «5 ≤7» (истинное высказывание).

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

Теорема 1 (закон де Моргана). При любых высказываниях А и В высказывания и одновременно истинны (или ложны).

Доказательство. Составим таблицы истинности для высказываний и .

А	В
И	И	Л	Л	И	Л	Л
И	Л	Л	И	И	Л	Л
Л	И	И	Л	И	Л	Л
Л	Л	И	И	Л	И	И

Ясно, что совпадение этих таблиц устанавливает справедливость утверждения теоремы.

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

Термин «импликация» происходит от латинского слова «implico» –– тесно связываю.

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

Замечание 1. Между посылкой и заключением может отсутствовать причинно–следственные связи, но это не повлияет на истинность или ложность импликации. Например, высказывание «если 7 –– простое число, то биссектриса равностороннего треугольника является медианой» будет истинным, хотя в обычном понимании второе высказывание не следует из первого.

Замечание 2. Если посылка ложна, то импликация будет истинна независимо от истинностного значения заключения. Этот факт кратко формулируют так: «истина следует из чего угодно».

Теорема 2 (закон силлогизма). Для любых высказываний А, В и С высказывание

((А ? В) Ù (В ? С)) ? (А ? С) (1)

истинно.

Доказательство. По определению импликация (1) истинна во всех случаях, когда истинно ее заключение А ? С. Поэтому будем рассматривать лишь случай ложного А ? С, а это возможно только при истинном А и ложном С. Рассмотрим случаи:

1) В истинно, тогда В ? С ложно; 2) В ложно, тогда ложно и А ? В.

Таким образом, при любом В высказывание (А ? В) Ù (В ? С) ложно, а, значит, импликация (1) истинна.

Импликация играет важную роль в математических доказательствах, т.к. многие теоремы формулируются в условной форме «Если А, то В». Если при этом известно, что А истинно и доказана истинность импликации А ? В, то мы вправе сделать вывод об истинности заключения В.

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

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

А	В
И	И	И
И	Л	Л
Л	И	Л
Л	Л	И

Если эквивалентность истинна, то высказывания А и В называют эквивалентными, т. е., два высказывания эквивалентны, когда они одновременно истинны (или ложны). Используя введенный термин, закон де Моргана можно сформулировать, например, так: «При любых высказываниях А и В высказывания и эквивалентны».

Теорема 3. При любых высказываниях А и В высказывания А Û В и (А ? В) Ù (В ? А) эквивалентны.

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