540

21

18. Дано: Е = {1; 2; 3; 4; 5; 6; 7; 8; 9; 10} (универсальное множест-

во); А = {2; 4; 6; 8}; В = {1; 5; 9}. Найти: À È Â , А , В , À Ç Â , А È В ,

АÇ В .

19.Дано: Е = (–∞;+∞) (универсальное множество); А = (0; 11]; В =

=[–4; 16). Найти: À È Â , А , В , À Ç Â , А È В , А Ç В .

20.Пусть множество А = [2; 7]; множество В = [–2; 4], а множест-

во С = [3; 6]. Найти: ( А \ В) È С ; ( А \ С) È В ; A \ (С Ç B) ; ( A È В) \ С ; A È (В \ С) .

21.На первом курсе института обучаются100 человек. Из 100 обучающихся 70 человек знают английский язык, 45 – французский и 23 человека знают оба языка. Сколько обучающихся на первом курсе не знают ни английского, ни французского языка?

22.Компания студенческой молодежи из20 человек поехала на пикник. При этом 5 из них обгорели, 8 были сильно покусаны комарами, а 10 остались всем довольны. Сколько человек обгорели, но не были покусаны комарами? Сколько человек были покусаны комарами

иодновременно обгорели?

24

Пример 4. С помощью диаграмм Эйлера-Венна проверим истинность следующего утверждения: «Если ни один лицемер не может быть наказан, то, значит, ни один, понесший наказание, не является лицемером».

Пусть А – множество лицемеров, а В – множество людей, понесших наказание. Тогда очевидно, что À Ç Â = Æ и данное утвержде-

ние истинно (рис. 2.4).

Рис. 2.4

Многие науки и искусства Древнего мира навсегда ушли в прошлое и представляют интерес исключительно как памятники старины. Однако некоторые из них пережили века и в настоящее время не потеряли свою актуальность. К их числу относится и логика Аристотеля.

§ 2. Основные понятия математической логики

Основоположником математической логики является великий немецкий математик Готфрид Вильгельм Лейбниц(1646–1716 гг.). Он сделал попытку построить универсальный язык, с помощью которого споры между людьми можно было бы разрешать посредством вычислений. На заложенном Лейбницем фундаменте ирландский математик Джордж Буль построил здание новой науки – математической логики, которая, в отличие от обычной алгебры, оперирует не числами, а высказываниями. Суждения в математической логике называются

высказываниями или логическими выражениями.

Высказывание – это любое утверждение, относительно которого имеет смысл говорить, что оно истинно или ложно. Следует заметить, что высказывания принято обозначать строчными или прописными буквами латинского алфавита: A, B, C, D, …, a, b, c, d, … .

25

Пример 5. Примерами высказываний могут служить следующие утверждения:

1.Марс дальше от солнца, чем Венера (истинное высказывание).

2.Москва – столица России (истинное высказывание).

3.Число 26 – простое (ложное высказывание).

4.11 < 17 (истинное высказывание).

Таким образом, каждое высказывание или истинно, или ложно. Вообще существуют разные варианты обозначения истинности и ложности высказываний: истинна – И, True, T, 1; ложь – Л, False, F, 0.

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

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

зываниями не являются: «Какого цвета этот дом?», «Здравствуйте!». Предложения «Он сероглаз», «Треугольник равнобедренный» с

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

Отметим, что предложение «Некоторые люди сероглазы» уже является истинным высказыванием.

Замечание 1. Повествовательное предложение «Я лгу» не является высказыванием, поскольку если оно истинно (т.е. я действительно лгу) – значит, я не лгу, а говорю правду! И наоборот. Это пример логического парадокса. Логические парадоксы не относятся к высказываниям.

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

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

Высказывания, сформированные из простых высказываний с использованием логических связок, называются сложными (составными). Например: «В Москве зимой часто идет снег, и видимость на до-

26

рогах резко ухудшается» (это сложное высказывание состоит из двух простых).

Пример 6. Укажите, какие из следующих предложений являются высказываниями, и определите, истинны они или ложны:

1)1917 : 852 = 9 : 4 ;

2)«Все треугольники – равнобедренные»;

3)«Вы были в театре?»;

4)à Ì { a, b, c } ;

5)«С Новым годом!».

Решение. Среди приведенных предложений высказываниями являются те, о которых можно сказать, истинны они или ложны. Поэтому предложения 1, 2, 4 являются высказываниями, причем 1 и 4 – истинны, 2 – ложно. Предложения 3 и 5 высказываниями не являются.

§ 3. Операции над высказываниями

Каждая логическая связка имеет для обозначения свой собственный символ и производит логическую операцию над высказываниями.

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

Логическое отрицание. Самой простой логической операцией является операция «НЕ» (по-другому ее часто называют отрицанием или инверсией и обозначают NOT А, À или ¬ А). Результат отрицания всегда противоположен значению переменной. Например, А: «Тоска

зеленая», тогда А : «Тоска НЕ зеленая» или НЕВЕРНО, что «Тоска зеленая».

Логическая операция «НЕ» является унарной, т.е. имеет всего одну переменную. Все остальные операции являются бинарными, так как представляют собой результаты действий над двумя логическими величинами. Определение отрицания может быть записано с помощью таблицы истинности (табл. 1):

Таблица 1

28

Логическое сложение. Логическая операция «ИЛИ» соответствует логическому сложению(по-другому ее называютдизъюнкция и обозначают А OR В, А Ú В).

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

Таблица 3

Дизъюнкция из n высказываний будет истинна, если хотя бы одно из n высказываний истинно, и ложна, когда все высказывания ложны.

Логическое следование. Логическая операция «ЕСЛИ …, ТО»

соответствует логическому следованию (по другому ее называют импликация и обозначают А Þ В или А ® В).

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

Таблица 4

29

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

Логическое тождество. Логическая операция «ТОГДА И ТОЛЬКО ТОГДА, КОГДА» соответствует логическому тождеству (по другому ее называют эквивалентностью или двойной импликацией и обозначают А Û В или А « В).

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

Таблица 5

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

Формулировка этой теоремы заключает две импликации:

1.Если некоторый параллелограмм – ромб, то его диагонали взаимно перпендикулярны (импликация А ® В).

2.Если диагонали некоторого параллелограмма взаимно перпендикулярны, то такой параллелограмм – ромб (В ® А – обратная импликация).

30

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

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

Например, сложное высказывание: «Если Волга впадает в Каспийское море, то 2 + 2 = 4» – истинное, а сложное высказывание: «Если Волга впадает в Каспийское море, то 2 + 2 = 5» – ложное.

Очевидно, что эти логические высказывания (истинное и ложное с точки зрения математической логики) одинаково грамматически бессмысленны.

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

1.«Быть иль не быть – вот в чем вопрос» (В. Шекспир). Ú А « В.

2.«Если хочешь быть красивым, поступи в гусары» (К. Прутков).

А® В.

3.«Если человек избавлен от физического труда и не приучен к

умственному, зверство овладевает им» (К. Ушинский). ( À Ù Â ) ® Ñ .

§ 4. Построение таблиц истинности для логических функций

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

Пример 14. Сложное высказывание: «2 × 2 = 4 и 2 × 3 = 6, и 2 × 4 = 8» можно представить как функцию трех переменных: f ( А, В,С ) = А Ù В Ù С, которая принимает истинное значение, если все три переменные А, В, С – истинны. Каждая переменная обозначает элементарное высказывание, входящее в данное сложное высказывание. Соответственно

А: «2 × 2 = 4»; В: «2 × 3 = 6»; С: «2 × 4 = 8».