Сегодня разберемся с некоторыми формулами и законами логики высказываний.
Но сначала головоломка:
The Old Girls' reunion
На банкете ежегодной встречи выпускников пять старых (судя по картинке,
действительно немолодых) подруг сидели за одним столиком. Каждая из них
заказывала какой-нибудь напиток, основное блюдо и десерт. Брэнда и миссис
Берн пили мартини, а Бетти и миссис Браун предпочли шерри. Мисс Бейкер
была за рулем и поэтому она попросила принести ей фруктовый сок. Бренда
и мисс Броад заказывали стейк, а Берил и мисс Бейкер - рост-биф. На десерт
Берил и мисс Блэк ели выпечку, а Барбара и мисс Бейкер - мороженое. Одна
из подруг заказывала фруктовый салат. Ни у кого из сидящих рядом друг с
другом не было двух одинаковых блюд.
Кто заказывал утку и что ела Бриджит?
(Mathematical Funfair by Brian Bolt, No17)
At their school's annual reunion five friends shared a table for dinner. Each
friend ordered something to drink, a meat course and a dessert. Brenda
and Mrs Burns had martinis while Betty and Mrs Brown ordered sherry. Ms
Baker had a fruit juice since she was driving. Brenda and Miss Broad ordered
steak. Beryl and Ms Baker had roast beef. For dessert Beryl and Miss Black
ate gateau, while Barbara and Ms Baker had ice cream. The other friend
had a fruit salad. No two friends sitting next to each other were served
two things the same.
Who had duck and what did Bridget eat?
Примечание: Я стараюсь не переводить (пока) названия задач и книг, т.к.
дословный перевод не всегда интересен. Если вам в голову придет какое-нибудь
удачное сочетание, поделитесь :) (например, название книги Перельмана "Живая
математика" переведено на английский как "Figures for Fun").
А теперь пришла пора вспомнить про
задачу из первого выпуска (Nо0) и
на ее примере научиться записывать высказывания в символьной форме и строить
таблицы истинности (представленное ниже решение не является оптимальным, оно приведено в качестве
поучительного разбора).
Напомню, к чему сводится условие задачи. Нужно определить единственную
даму сердца, зная что:
Если я люблю Таню, то я люблю Лену или Аню.
Если я люблю Лену, то я люблю Аню и Катю.
Если я люблю Аню или Катю, то я не люблю Марину.
Если я не люблю Катю, то я люблю Таню и Марину.
Итак, есть пять имен (Таня, Лена, Аня, Катя и Марина) и,
соответственно, пять простых высказываний (Т, Л, А, К, М):
Т - "я люблю Таню"
Л - "я люблю Лену"
А - "я люблю Аню"
К - "я люблю Катю"
М - "я люблю Марину"
Представим условие задачи в символьном виде:
1.
Если я люблю Таню, то я люблю Лену или Аню.
T => (Л v A)
2.
Если я люблю Лену, то я люблю Аню и Катю.
Л => (A & K)
3.
Если я люблю Аню или Катю, то я не люблю Марину.
(A v K) => ~M
4.
Если я не люблю Катю, то я люблю Таню и Марину.
~K => (T & M)
Построим для каждого условия таблицу истинности (в первой строке обозначена
последовательность выполнения). Нет необходимости выписывать таблицы полностью
(для трех входящих высказываний - 8 строчек, а для пяти - 32), достаточно
рассмотреть случаи, когда ровно одно из высказываний истинно.
2
1
T
=>
Л
v
A
1
0
0
0
0
0
1
1
1
0
0
1
0
1
1
0
1
0
0
0
2
1
Л
=>
A
&
K
1
0
0
0
0
0
1
1
0
0
0
1
0
0
1
0
1
0
0
0
1
2
1
A
v
K
=>
~
M
1
1
0
1
1
0
0
1
1
1
1
0
0
0
0
1
0
1
0
0
0
1
1
0
1
2
1
~
K
=>
T
&
M
0
1
1
0
0
0
1
0
0
1
0
0
1
0
0
0
0
1
1
0
0
0
0
0
Легко заметить что в третьей таблице всегда получается истина (действительно,
если "я люблю" кого-то из двух, то "я не могу любить" кого-то третьего
:) ), то есть это условие практически никак не влияет на решение. А вот
в четвертой таблице только один "истинный случай" (т.к. следствие импликации
ложное (нельзя любить сразу двух), то импликация будет истинной, только
когда основание тоже ложное (а основание представляет "~К"), т.е.
когда истинно высказывание "К"). Сверяя этот случай с первой и второй
таблицей, находим ответ: "Я люблю Катю".
Можно построить таблицу истинности для всех четырех условий сразу (ограничиваясь
пятью строчками). Вот как это будет выглядеть (все условия объединяются
посредством конъюнкции):
2
1
3
2
1
3
1
2
3
2
1
T
Л
A
K
M
(T
=>
Л
v
A)
&
(Л
=>
A
&
K)
&
(A
v
K
=>
~M)
&
(~K
=>
T
&
M)
1
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
0
1
0
1
0
0
0
1
0
0
0
2
0
1
1
1
0
0
1
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
1
0
0
3
0
1
0
1
1
0
0
1
1
0
0
0
1
1
0
1
1
0
1
0
0
0
0
0
0
0
1
0
4
0
1
0
0
0
1
0
1
0
0
1
1
0
1
1
1
1
1
0
1
0
0
0
0
0
0
0
1
5
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
В четвертой строке таблицы ( K == 1 ) все условные высказывания истинные.
Прокомментирую некоторые формулы, приведенные в выпуске No4.
a & b == b & a - коммутативность конъюнкции
a v b == b v a - коммутативность дизъюнкции
a & (b & c) == (a & b) & c - ассоциативность конъюнкции
a v (b v c) == (a v b) v c - ассоциативность дизъюнкции
a & (b v c) == (a & b) v (a & c) - дистрибутивность конъюнкции относительно дизъюнкции
a v (b & c) == (a v b) & (a v c) - дистрибутивность дизъюнкции относительно конъюнкции
Все формулы, за исключением последней, при замене "&"
на знак умножения и "v" на знак сложения превращаются в знакомые
арифметические формулы перестановки, сочетания и распределения.
А кроме того действует так называемый принцип двойственности
(свойство симметрии): при замене всех "и" на "или", всех
"или" на "и" и всех "1" на "0", а всех "0"
на "1" формула останется верной.
Богатый иллюстративный материал для логических связок можно обнаружить
в обычном школьном учебнике геометрии. Наверное, замечали, что теоремы
часто начинаются со слов "Если..." и выглядят примерно так: "если а
и б, то c" или "если а, то б и c", а аксиомы имеют вид соединительных
(конъюнктивных) или разделительных (дизъюнктивных) высказываний. Как только
мне на глаза попадется подобное учебное пособие (если у вас на примете
есть ссылка, напишите), попробую написать более подробные рассуждения на
эту тему.
~~a == a - закон снятия двойного отрицания
здесь, думаю, все ясно.
a & a == a - закон идемпотентности
1 & 1 == 1, 0 v 0 == 0
a v a == a - закон идемпотентности
1 v 1 == 1, 0 v 0 == 0
a & 0 == 0
ложь, помноженная на "все, что угодно" - ложь.
a & 1 == a
"все, что угодно" и истина - "все, что угодно".
a v 0 == a
ложь или "все, что угодно" - "все, что угодно".
a v 1 == 1
истина или "все, что угодно" - истина.
a & ~a == 0 - закон противоречия
одно из двух: если одно истинно, то другое ложно.
a v ~a == 1 - закон исключенного третьего
а или не а, третьего не дано.
~(a & b) == ~a v ~b - закон Де Моргана
~(a v b) == ~a & ~b - закон Де Моргана
a & b == ~(~a v ~b) - закон Де Моргана
a v b == ~(~a & ~b) - закон Де Моргана
a => b == ~a v b - выражение импликации через отрицание и дизъюнкцию
a <=> b == (a => b) & (b => a)
10-15 легко проверить, построив таблицы истинности для левой части выражения и правой.
a & (b v a) == a - закон поглощения
a(b + a) = ab + aa = ab + a = a(b + 1) = a 1 = a
a v (b & a) == a - закон поглощения
a + ba = a (1 + b) = a
a & (~a v b) == a & b
a(~a + b) = a~a + ab = 0 + ab = ab
a v (~a & b) == a v b
(!) a + ~ab = (a + ~a)(a + b) = 1(a + b) = a + b
(a & b) v (a & ~b) == a - закон склеивания
ab + a ~b = a (b + ~b) = a 1 = a
(a v b) & (a v ~b) == a - закон склеивания
(a + b)(a + ~b) = aa + ab + a ~b + b ~b = a + a(b + ~b) + 0 = a
Здесь и далее для облегчения воспроизведения формул знак дизъюнкции
"v" заменен на "+", а знак конъюнкции "&" опущен (запись "a b" следует
понимать как "a и b").
И несколько примеров использования формул. Если вы внимательно их просмотрите,
а еще лучше возьмете бумагу, ручку и прорешаете (заодно и проверите, не
ошиблась ли я где-нибудь, выписывая все эти "крестики-нолики"), то многие
формулы станут понятнее и ближе.
(a + c)(a + ~c)(~b + c) = (a + ~cc)(~b + c) =
= (a + 0)(~b + c) = a(~b + c)
~a ~b + a ~b + ab + bc = ~a ~b + a ~b + a ~b + ab + bc =
= ~b(~a + a) + a(~b + b) + bc = ~b + a + bc =
= a + ~b + bc
ab + bc + ~ac = ab + bc(a + ~a) + ~ac =
= ab + bca + bc~a + ~ac = ab + abc + ~acb + ~ac =
= ab(1 + c) + ~ac(b + 1) = ab + ~ac
~((~a ~b + c)~ad) = ~(~a ~b + c) + ~~a + ~d =
= ~(~a ~b)~c + a + ~d = (~~a + ~~b)~c + a + ~d =
= a + (a + b)~c + ~d = a + a ~c + b ~c + ~d = a + b ~c + ~d