Отправляет email-рассылки с помощью сервиса Sendsay

Логика для всех

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Занимательные задачи и головоломки" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Апрель 2001   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Автор
Natalia

Статистика

4.156 подписчиков
0 за неделю
←   Все выпуски   →

Логика для всех


Служба Рассылок Subscribe.Ru проекта Citycat.Ru
 

"Логика для всех" выпуск No6 oт 2001-04-03

 

Здравствуйте!

Сегодня разберемся с некоторыми формулами и законами логики высказываний. Но сначала головоломка:

The Old Girls' reunion

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").

Присылайте свои решения на ntl@yandex.ru.
И не забывайте про форум.

А теперь пришла пора вспомнить про задачу из первого выпуска (Nо0) и на ее примере научиться записывать высказывания в символьной форме и строить таблицы истинности (представленное ниже решение не является оптимальным, оно приведено в качестве поучительного разбора).

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

  1. Если я люблю Таню, то я люблю Лену или Аню.
  2. Если я люблю Лену, то я люблю Аню и Катю.
  3. Если я люблю Аню или Катю, то я не люблю Марину.
  4. Если я не люблю Катю, то я люблю Таню и Марину.

Итак, есть пять имен (Таня, Лена, Аня, Катя и Марина) и, соответственно, пять простых высказываний (Т, Л, А, К, М):

  • Т - "я люблю Таню"
  • Л - "я люблю Лену"
  • А - "я люблю Аню"
  • К - "я люблю Катю"
  • М - "я люблю Марину"

Представим условие задачи в символьном виде:

1. Если я люблю Таню, то я люблю Лену или Аню. T => (Л v A)
2. Если я люблю Лену, то я люблю Аню и Катю. Л => (A & K)
3. Если я люблю Аню или Катю, то я не люблю Марину. (A v K) => ~M
4. Если я не люблю Катю, то я люблю Таню и Марину. ~K => (T & M)

Построим для каждого условия таблицу истинности (в первой строке обозначена последовательность выполнения). Нет необходимости выписывать таблицы полностью (для трех входящих высказываний - 8 строчек, а для пяти - 32), достаточно рассмотреть случаи, когда ровно одно из высказываний истинно.

 2 1 
T=>ЛvA
10000
01110
01011
01000
 2 1 
Л=>A&K
10000
01100
01001
01000
 1 21 
AvK=>~M
110110
011110
000101
000110
1 2 1 
~K=>T&M
011000
100100
100001
100000

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

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

        2 1  3 2 1  3 1 2  3 2 1 
TЛAKM  (T=>ЛvA) &(Л=>A&K) &(AvK=>~M) &(~K=>T&M)
100001 10000 001000 000011 010100
010002 01110 010000 000011 010000
001003 01011 001100 011011 010000
000104 01000 101001 101111 101000
000015 01000 001000 000010 010001

В четвертой строке таблицы ( K == 1 ) все условные высказывания истинные.

Прокомментирую некоторые формулы, приведенные в выпуске No4.

  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) - дистрибутивность дизъюнкции относительно конъюнкции

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

А кроме того действует так называемый принцип двойственности (свойство симметрии): при замене всех "и" на "или", всех "или" на "и" и всех "1" на "0", а всех "0" на "1" формула останется верной.

Богатый иллюстративный материал для логических связок можно обнаружить в обычном школьном учебнике геометрии. Наверное, замечали, что теоремы часто начинаются со слов "Если..." и выглядят примерно так: "если а и б, то c" или "если а, то б и c", а аксиомы имеют вид соединительных (конъюнктивных) или разделительных (дизъюнктивных) высказываний. Как только мне на глаза попадется подобное учебное пособие (если у вас на примете есть ссылка, напишите), попробую написать более подробные рассуждения на эту тему.

  1. ~~a == a - закон снятия двойного отрицания

    2. здесь, думаю, все ясно.
  2. a & a == a - закон идемпотентности

    3. 1 & 1 == 1, 0 v 0 == 0
  3. a v a == a - закон идемпотентности

    4. 1 v 1 == 1, 0 v 0 == 0
  4. a & 0 == 0

    5. ложь, помноженная на "все, что угодно" - ложь.
  5. a & 1 == a

    6. "все, что угодно" и истина - "все, что угодно".
  6. a v 0 == a

    7. ложь или "все, что угодно" - "все, что угодно".
  7. a v 1 == 1

    8. истина или "все, что угодно" - истина.
  8. a & ~a == 0 - закон противоречия

    9. одно из двух: если одно истинно, то другое ложно.
  9. a v ~a == 1 - закон исключенного третьего

    10. а или не а, третьего не дано.
  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. 10-15 легко проверить, построив таблицы истинности для левой части выражения и правой.
  16. a & (b v a) == a - закон поглощения

    17. a(b + a) = ab + aa = ab + a = a(b + 1) = a 1 = a
  17. a v (b & a) == a - закон поглощения

    18. a + ba = a (1 + b) = a
  18. a & (~a v b) == a & b

    19. a(~a + b) = a~a + ab = 0 + ab = ab
  19. a v (~a & b) == a v b

    20. (!) a + ~ab = (a + ~a)(a + b) = 1(a + b) = a + b
  20. (a & b) v (a & ~b) == a - закон склеивания

    21. ab + a ~b = a (b + ~b) = a 1 = a
  21. (a v b) & (a v ~b) == a - закон склеивания

    22. (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

x + y(x + ~y) = x + yx + y ~y = x(1 + y) + 0 = x

~x ~(~y + x) = ~x(~~y ~x) = ~x y

 ~(x (~x ~y))= ~x + ~(~x ~y)= ~x + ~~x + ~~y =

= ~x + x + y = 1 + y = 1

~(x + ~(~x ~y)) = ~x ~~(~x ~y) = ~x ~x ~y = ~x ~y = ~(x+y)

или

~(x + ~(~x ~y)) = ~(x + ~~x + ~~y) = ~(x + x + y) = ~(x + y) = ~x ~y

~x + ~(x y ~y) = ~x + ~(x 0) = ~x + ~0 = ~x + 1 = 1

~(~x ~y) + ~x = ~~x + ~~y + ~x = x + y + ~x = 1 + y = 1

До новой рассылки!

 

  Вопросы, пожелания и замечания пишите на ntl@yandex.ru.

Natalia

  http://ntl.narod.ru/logic - Логика для всех

  http://book.by.ru/cgi-bin/book.cgi?book=logic - Головоломный форум

Использование материалов рассылки без согласования с ведущим рассылки не одобряется.

 

Приглашаю к сотрудничеству рекламодателей и спонсоров.

Рассылки Subscribe.Ru
Логика для всех
Рассылка 'Логика для всех'
Архив на Subscribe.Ru
Поиск по архиву рассылки
"Логика для всех"
Архив Рассылки Описание Рассылки Статистика Рассылки
 
http://subscribe.ru/
E-mail: ask@subscribe.ru
В избранное