"Логика для всех" выпуск No6 oт 2001-04-03
Здравствуйте! Сегодня разберемся с некоторыми формулами и законами логики высказываний. Но сначала головоломка: The Old Girls' reunion
А теперь пришла пора вспомнить про задачу из первого выпуска (Nо0) и на ее примере научиться записывать высказывания в символьной форме и строить таблицы истинности (представленное ниже решение не является оптимальным, оно приведено в качестве поучительного разбора). Напомню, к чему сводится условие задачи. Нужно определить единственную даму сердца, зная что:
Итак, есть пять имен (Таня, Лена, Аня, Катя и Марина) и, соответственно, пять простых высказываний (Т, Л, А, К, М):
Представим условие задачи в символьном виде:
Построим для каждого условия таблицу истинности (в первой строке обозначена последовательность выполнения). Нет необходимости выписывать таблицы полностью (для трех входящих высказываний - 8 строчек, а для пяти - 32), достаточно рассмотреть случаи, когда ровно одно из высказываний истинно.
Легко заметить что в третьей таблице всегда получается истина (действительно, если "я люблю" кого-то из двух, то "я не могу любить" кого-то третьего :) ), то есть это условие практически никак не влияет на решение. А вот в четвертой таблице только один "истинный случай" (т.к. следствие импликации ложное (нельзя любить сразу двух), то импликация будет истинной, только когда основание тоже ложное (а основание представляет "~К"), т.е. когда истинно высказывание "К"). Сверяя этот случай с первой и второй таблицей, находим ответ: "Я люблю Катю". Можно построить таблицу истинности для всех четырех условий сразу (ограничиваясь пятью строчками). Вот как это будет выглядеть (все условия объединяются посредством конъюнкции):
В четвертой строке таблицы ( K == 1 ) все условные высказывания истинные. Прокомментирую некоторые формулы, приведенные в выпуске No4.
Все формулы, за исключением последней, при замене "&" на знак умножения и "v" на знак сложения превращаются в знакомые арифметические формулы перестановки, сочетания и распределения. А кроме того действует так называемый принцип двойственности (свойство симметрии): при замене всех "и" на "или", всех "или" на "и" и всех "1" на "0", а всех "0" на "1" формула останется верной. Богатый иллюстративный материал для логических связок можно обнаружить в обычном школьном учебнике геометрии. Наверное, замечали, что теоремы часто начинаются со слов "Если..." и выглядят примерно так: "если а и б, то c" или "если а, то б и c", а аксиомы имеют вид соединительных (конъюнктивных) или разделительных (дизъюнктивных) высказываний. Как только мне на глаза попадется подобное учебное пособие (если у вас на примете есть ссылка, напишите), попробую написать более подробные рассуждения на эту тему.
здесь, думаю, все ясно. 1 & 1 == 1, 0 v 0 == 0 1 v 1 == 1, 0 v 0 == 0 ложь, помноженная на "все, что угодно" - ложь. "все, что угодно" и истина - "все, что угодно". ложь или "все, что угодно" - "все, что угодно". истина или "все, что угодно" - истина. одно из двух: если одно истинно, то другое ложно. а или не а, третьего не дано. 10-15 легко проверить, построив таблицы истинности для левой части выражения и правой. a(b + a) = ab + aa = ab + a = a(b + 1) = a 1 = a a + ba = a (1 + b) = a a(~a + b) = a~a + ab = 0 + ab = ab (!) a + ~ab = (a + ~a)(a + b) = 1(a + b) = a + b ab + a ~b = a (b + ~b) = a 1 = 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 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 - Головоломный форум
Использование материалов рассылки без согласования с ведущим рассылки не одобряется.
Приглашаю к сотрудничеству рекламодателей и спонсоров.