Сегодняшний выпуск посвящен краткому введению в логику высказываний. Здесь прежде всего нужно определиться с понятиями, потому что один и тот же раздел часто называют по-разному: математическакая логика, логика высказываний (предложений), символическая логика, двузначная логика, пропозициональная логика, булева алгебра... Я больше склоняюсь к "логике высказываний" (простое высказывание здесь рассматривается как неделимая частица).

Обо всем этом написано много умных книжек разными авторами в разное время на разных языках... Можно найти много "поучительных" ссылок в интернете... Я не стремлюсь объять необъятное (хотя иногда очень хочется), в данном случае моя цель, скорее, пострараться преподнести материал как инструмент для решения ряда интересных задач обычно бывает наоборот :) - задачи служат для понимания, осмысления и запоминания пройденного).

Это краткое введение, разумеется, не исчерпывает тему полностью, и если у вас возникают вопросы, спрашивайте. Лучше всего задавать их через форум http://book.by.ru/cgi-bin/book.cgi?book=logic, в этом случае ответить на вопрос могу не только я (кроме того, на форуме вас ждет новая задача - решение можно оставить там же).

Просматривая различные материалы я нашла симпатичную задачу (The Three Hotel Visitors - http://www.informatik.htw-dresden.de/~nestleri/htw2754/puzzleII.html) и решила "поделиться" ею с вами (по ссылке вы найдете оригинал задачи, подсказки и апплеты для решения; желающие обсудить приглашаются на форум :) ).

Мистер Блэк, Мистер Грей и мистер Вайт работают в большом известном отеле. Один из них официант, другой бухгалтер, а третий лыжный инструктор (вовсе не обязательно в таком порядке). На научный конгресс прибыли три профессора с такими же именами и, разумеется, поселились в этой гостинице. Известно, что

1. Профессор Вайт приехал из Шотландии.
2. Бухгалтер родился и учился в Манчестере.
3. Профессор Грей забыл все свои чемоданы в аэропорте (вот такой рассейнный).
4. Профессор, имя которого такое же как и у бухгалтера, живет в Брайтоне.
5. Бухгалтер и один из профессоров (заядлый спортсмен, который привез свое лыжное снаряжение из дома) посещали одну и ту же церковь.
6. Мистер Блэк обыгрывает лыжного инструктора в шахматной игре (что неудивительно - шахматы это не лыжи).

Перед тем как приступить к серьезному занятию, попробуйте ответить на вопрос:

Некий промышленник установил, что если бы люди среднего возраста чаще говорили правду, то ему (промышленнику) удавалось бы реализовать гораздо больше своей продукции.
Что он выпускает?

А теперь - за дело!

Для начала несколько определений от mega.km.ru (можно пропустить :)):

ЛОГИКА ВЫСКАЗЫВАНИЙ, раздел логики, в котором вопрос об истинности или ложности высказываний рассматривается и решается на основе изучения способа построения высказываний из т.н. элементарных (далее не разлагаемых и не анализируемых) высказываний с помощью логических операций конъюнкции ("и"), дизъюнкции ("или"), отрицания ("не"), импликации ("если..., то...") и др. Логику высказываний, задаваемую системой постулатов (аксиом и правил вывода), называют исчислением высказываний.

ВЫСКАЗЫВАНИЕ, мысль, выраженная повествовательным предложением и могущая быть истинной или ложной.

АНАЛИТИЧЕСКОЕ ВЫСКАЗЫВАНИЕ, высказывание, истинность или ложность которого может быть установлена исключительно на основе анализа его грамматической или логической структуры. Примеры истинных аналитических высказываний логические законы.

СУЖДЕНИЕ, форма мышления, представляющая собой сочетание понятий, из которых одно (субъект) определяется и раскрывается через другое (предикат).

ЛОГИЧЕСКИЙ ЗАКОН, название законов, образующих основу логической дедукции; схема логической связи высказываний, выражаемая общезначимой формулой логики (аксиомой или теоремой), убедительность которой вытекает из одного только истолкования входящих в нее логических операций и по существу не связана с фактической истинностью "наполняющих" ее высказываний.

ТОЖДЕСТВЕННАЯ ИСТИННОСТЬ, свойство сложных высказываний быть истинными в силу своей формально-логической структуры и смысла используемых в них логических операций. Будучи независимыми от содержания входящих в них конкретных высказываний, тождественно-истинные высказывания выступают в качестве логических законов.

Итак, какие бывают высказываний?

Пока нам достаточно того, что высказывание может быть простым или сложным, истинным или ложным. Например, высказывание "Идет дождь" - простое, а истинное оно или ложное зависит от того какая погода сейчас за окном. Если действительно не переставая льет дождь, то высказывание - истинное, а если нещадно палит солнце, и бесполезно ждать дождя раньше октября, то высказывание "Идет дождь" будет ложным.

А можно взять для примера более определенное (в смысле значения истинности) высказывание "Луна - спутник Земли" - простое и истинное. А вот "Солнце - спутник Земли" будет ложным высказывание (и простым). Усложняем задачу: "Луна - спутник Земли и Солнце - спутник Земли". На этот раз наше высказывание сложное, т.к. оно состоит из двух простых, и, что самое важное, это высказывание ложное, так уж устроена лоическая (пропозициональная) связка "и" (конъюнкция). Если она обьединяет истинные высказывания - сложное высказывание будет истинным, а во всех остальных случаях - ложным. А сколько всего случаев? Каждое высказывание может быть истинным или ложным, если рассматривать два высказывания, то получим 4 комбинации: оба истинные, оба ложные, одно истинное, другое ложное, и наоборот.

Рассмотрим теперь высказывание "Луна - спутник Земли или Солнце - спутник Земли" - сложное и истинное. На этот раз связующим звеном выступает "или" (дизъюнкция), которая принимает ложное значение только когда все входящие высказывания - ложные, если хотя бы одно истинное, то все дизъюнктивное высказывание - истинное.

Но мы еще можем превратить высказывание "Луна - спутник Земли" в ложное, а "Солнце - спутник Земли" в истинное, если скажем "Неверно, что Луна - спутник Земли" и "Неверно, что Солнце - спутник Земли". Так действует на высказывания связка "не" (отрицание): истинные высказывания превращает в ложные, а ложные - в истинные. Теперь высказывание "Луна - спутник Земли и неверно, что Солнце - спутник Земли" - истинное, "Неверно, что Луна - спутник Земли или Солнце - спутник Земли" - ложное.

Еще одна интересная связка "если ..., то ..." (импликация). Рассмотрим высказывание "Если Луна - спутник Земли, то и Солнце - спутник Земли". Здравый смысл подсказывает, что это высказывание ложное, но истинным будет "Если Луна - спутник Земли, то неверно, что Солнце - спутник Земли". Высказывание же "Если Солнце - спутник Земли, то и Луна - спутник Земли" - истинное, несмотря на кажущуюся абсурдность. И высказывание "Если Солнце - спутник Земли, то все что угодно" - тоже истинное. В таких случаях мне нравится высказывaние "Если я - балерина, то Луна - зеленая" или что-нибудь подобное.

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

Два высказывания - 4 строчки в таблице. Три различных высказывания - 8 комбинаций, 4 - 16 и т.д. n высказываний - 2^n комбинаций.

Какие символы лучше использовать для обозначения логических связок? Фантазия в этой области безгранична... :) Трудно найти две книги, в которых авторы придерживались бы одинаковых обозначений. Тем не менее, некоторая логика :) в этом есть. Но далеко не все символы могут быть воспроизведены в электронном тексте, поэтому часто прибегают к включению в текст небольших графических файлов, но это не выход в рамках данной рассылки, т.к. помимо html-версии есть и текстовая.
Остановимся пока на следующих обозначениях:

Обычно логические значения результатов применения связок записываются в виде таблиц (т.н. таблицы истинности). Но представление этих таблиц широко варьируется. Для обозначения высказываний, логических значений и связок используют как прописные, так и строчные буквы. Для обозначения истинности и ложности используют, соответственно, "1" и "0", "И" и "Л", "t" (true) и "f"(false)... Кому-то удобнее сначала выписывать "0", а потом "1", а кому-то - наоборот. Ниже представлены различные способы изображения таблицы истинности на примере дизъюнкции. Я предпочитаю первый вариант :).

Таблицы для связок:

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

Дизъюнкцию  "или" часто называют "нестрогой дизъюнкцией". А строгую диъюнкцию "либо ..., либо ..." обозначают символом "v" с точкой сверху или двойным "v" (перевернутое на 90 градусов против часовой стрелки "<<"), вероятно существуют и другие обозначения. Отличие таблицы истинности для строгой дизъюнкции от таблицы истинности для нестрогой дизъюнкции в первой строчке: когда значения а и b истинны, "либо а, либо b" - ложно.

Все в одной таблице:

И несколько полезных формул (пока без комментариев):

1. ~~a == a - закон снятия двойного отрицания
2. a & a == a - закон идемпотентности
3. a v a == a - закон идемпотентности
4. a & 0 == 0
5. a & 1 == a
6. a v 0 == a
7. a v 1 == 1
8. a & ~a == 0 - закон противоречия
9. a v ~a == 1 - закон исключенного третьего
10. ~(a & b) == ~a v ~b - закон Де Моргана
11. ~(a v b) == ~a & ~b - закон Де Моргана
12. a & b == ~(~a v ~b) - закон Де Моргана
13. a v b == ~(~a & ~b) - закон Де Моргана
14. a => b == ~a v b - выражение импликации через отрицание и дизъюнкцию
15. a <=> b == (a => b) & (b => a)
16. a & (b v a) == a - закон поглощения
17. a v (b & a) == a - закон поглощения
18. a & (~a v b) == a & b
19. a v (~a & b) == a v b
20. (a & b) v (a & ~b) == a - закон склеивания
21. (a v b) & (a v ~b) == a - закон склеивания

1. a & b == b & a - коммутативность конъюнкции
2. a v b == b v a - коммутативность дизъюнкции
3. a & (b & c) == (a & b) & c - ассоциативность конъюнкции
4. a v (b v c) == (a v b) v c - ассоциативность дизъюнкции
5. a & (b v c) == (a & b) v (a & c) - дистрибутивность конъюнкции относительно дизъюнкции
6. a v (b & c) == (a v b) & (a v c) - дистрибутивность дизъюнкции относительно конъюнкции

На своем опыте я убедилась, что вводить пропозициональные связки (на урокаx логики) приходится уже при рассмотрении некоторых задач (про рыцарей и лжецов) из книги Р.Смаллиана "Как же называется эта книга?" (страница Смаллиана на сайте "Логика для всех" http://ntl.narod.ru/logic/smullyan/index.html). Напомню, что рыцари это личности, которые всегда говорят только правду, а лжецы, соответственно, всегда лгут.

Попробуем разобраться в следующих задачах:

Raymond Smullyan. WHAT IS THE NAME OF THIS BOOK? The Riddle of Dracula and Other Logical Puzzles.

29.
Suppose A says, "Either I am a knave or B is a knight."
What are A and B?

30.
Suppose A says, "Either I am a knave or else two plus two equals five."
What would you conclude?

33.
Suppose A says, "Either I am a knave, but B isn't."
What are A and B?

29.
Предположим, что А говорит: "Или я лжец, или В рыцарь".
Кто из двух персонажей А и В рыцарь и кто лжец?

30.
Предположим, что А говорит: "Или я лжец, или два плюс два - пять".
К какому заключению можно прийти на основании этого утверждения?

33.
Предположим, что А высказывает утверждение: "Я лжец, а В не лжец".
Кто из островитян А и В рыцарь и кто лжец?

29.
Запишем высказывание А в символьной форме: {A-л v B-p}. Рассмотрим 2 случая:

• A - рыцарь: {0 v B-p == 1}, дизъюнкция будет истинной только если {B-p == 1}, т.е. В - рыцарь.
• A - лжец: {1 v B-p == 0}, такая дизъюнкция не может быть ложной, следовательно, А - не лжец.

30.
Bысказывание А в символьной форме: {A-л v 0}. Рассмотрим 2 случая:

• A - рыцарь: {0 v 0 == 1}
• A - лжец: {1 v 0 == 0}

33.
B этом случае: {A-л & B-p}:

• A - рыцарь: {0 & B-p == 1}, конъюнкция не может быть истинной, если хотя бы один из конъюнктов ложное высказывание.
• A - лжец: {1 & B-p == 0}, чтобы конъюнкция была ложной при одном истинном конъюнкте, второй должен быть ложным, т.е. если А - лжец, высказывание "В - рыцарь" - ложное.

Интересно отметить, что и рыцари и лжецы могут произносить фразу "Я - рыцарь". В устах рыцаря это истинное высказывания, лжеца - ложное. А высказывание "Я - лжец" не может принадлежать ни рыцарю, ни лжецу (т.н. парадокс лжеца), т.к. если рыцарь произнесет "Я - лжец", то это будет ложное высказывание, что непозволитетельно в подобных условиях, а если эту фразу скажет лжец, то она окажется истинной, что опять же противоречит нашим условиям.

И еще несколько случаев:

Following are several problem from the island of knights and knaves where knights always tell truth whereas knaves always lie.

1. If anybody on the island says "If I'm a knight then P." then the speaker must be a knight and P is true.
2. A makes the following statement: "If I am a knight then so is B." What are A and B?
3. Someone asks A, "Are you a knight?" He replies, "If I am a knight then I'll eat my hat". Must he eat his hat?
4. A says, "If I am a knight then 2+2=4." Is A a knave or a knight?
5. A says, "If B is a knight then I am a knave." What are A and B?

Если кто-то на острове рыцарей и лжецов скажет: "Если я рыцарь, то X", этот кто-то обязательно окажется рыцарем, а высказывание X - истинным. Убедимся в этом:

Предположим, что кто-то это А. Запишем высказывание {А-р => X}. Если А - лжец, то {А-р == 0}. Выражение {0 => X == 0} не будет верным ни при каких значениях высказывания X, т.к. импликация с ложным основанием может быть только истинной. А если А - рыцарь, то {А-р == 1} и в выражении {1 => X == 1} значениe высказывания X должно быть истинным.

Предположим, A утверждает: "Если я рыцарь, то и B - рыцарь." Следуя предыдущему рассуждению, можно убедиться, что и A, и B - рыцари.

Если же на вопрос "Вы рыцарь?" A ответит: "Если я рыцарь, то я съем свою шляпу", то аналогичным образом нетрудно убедиться в том, что А все-таки придется съесть шляпу.

В случае, когда A произносит: "Если я рыцарь, то 2 + 2 = 4", A опять будет рыцарем.

Гораздо интереснее, если А утверждает: "Если B рыцарь, то я лжец." Если А - рыцарь, то {В-р => 0 == 1}; выражение верно только если {В-р == 0}, т.е. В - лжец. Предположив, что А - лжец, получаем {В-р => 1 == 0}. Это выражение не будет верным ни при каких значения высказывания "В - рыцарь". Итак, А - рыцарь, а B - лжец.

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