Математическая логика

Размещено на http://www.allbest.ru/

Математическая логика



План

1. Высказывание

2. Логические операции и их таблицы истинности

3. Формулы логики высказываний

4. Равносильность формул. Законы логики высказываний

5. Аксиоматический метод ИВ

6. Нормальные формы формул логики высказываний

7. Решение логических задач



1. Высказывание

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

Примеры высказываний

1) Новгород стоит на Волхове.

2) Париж - столица Англии.

3) Карась не рыба.

4) Число 6 делится на 2 и на 3.

5) Если юноша окончил среднюю школу. то он получает аттестат зрелости.

Высказывания 1), 4), 5) истинны, а высказывания 2) и 3) ложны.

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

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

В алгебре логики все высказывания рассматриваются только с точки зрения их логического значения, а от их житейского содержания отвлекаются. Считается, что каждое высказывание либо истинно, либо ложно и ни одно высказывание не может быть одновременно истинным и ложным.

Элементарные высказывания обозначают малыми буквами латинского алфавита: x, y, z, а, b, c истинное значение высказывания - буквой и или цифрой 1, а ложное значение - буквой л или цифрой 0. Например, если высказывание a, истинно, то будем писать a=1, а если a ложно, то a=0.



2. Логические операции и их таблицы истинности

Логические операции - мыслительные действия, результатом которых является изменение содержания или объема понятий, а также образование новых понятий.

Логические операции и таблицы истинности

1) Логическое умножение или конъюнкция:

Конъюнкция - это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное сложеное выражение ложно.

Обозначение: F = A & B.

Таблица истинности для конъюнкции

A	B	F
1	1	1
1	0	0
0	1	0
0	0	0

2) Логическое сложение или дизъюнкция:

Дизъюнкция - это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выраженныя ложны.

Обозначение: F = A + B.

Таблица истинности для дизъюнкции

A	B	F
1	1	1
1	0	1
0	1	1
0	0	0



3) Логическое отрицание или инверсия:

Инверсия - это сложное логическое выражение, если исходное логическое выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное логическое выражение ложно, то результат отрицания будет истинным. Другими простыми слова, данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО.

Таблица истинности для инверсии

A	неА
1	0
0	1

4) Логическое следование или импликация:

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

Таблица истинности для импликации

A	B	F
1	1	1
1	0	0
0	1	1
0	0	1

5) Логическая равнозначность или эквивалентность:

Эквивалентность - это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность.



Таблица истинности для эквивалентности

A	B	F
1	1	1
1	0	0
0	1	0
0	0	1

Порядок выполнения логических операций в сложном логическом выражении

1. Инверсия;

2. Конъюнкция;

3. Дизъюнкция;

4. Импликация;

5. Эквивалентность.

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

3. Формулы логики высказывания

4. Равносильность формул. Законы логики высказываний

Формулы называются равносильными, если таблицы истинности этих формул будут совпадать Равносильные формулы называются еще эквивалентными, так как в процессе каждого набора значений для своих переменных они наб бывают одинакового значения истинности или значение ложности (см. таблицу истинности для формулы эквивалентности А = ВВ).

Равносильную формулу можно получить в результате замены пропозициональных связок на основании отношения зависимости между ними Определяют, что для любой формулы можно назвать равносильное для нее формулу, которая а содержит символы-и V, V Например, формулу вида -1 А V-\"В можно заменить формулой вида -\" (А л В), что означает-oА /-ов = - \"(А л В); есть А - В =-и А V В; формулу А V В можно заменить формулой - \"(-\" А Л В), что означает А V В = - (- * А Л - В В), що означає А V В =->(-* А Л -> В).

Равносильные формулы называются законами логики высказываний

Законы логики высказываний (ЛО) - равносильны, тождественно-истинные формулы, входящие в структуру классической символической логики как формальной системы К ним относятся: закон тождества, закон несуперечнос сти, закон исключенного третьего, закон ассоциативности, закон дистрибутивности, закон идемпотентности, закон коммутативности, закон контра позиции, закон поглощения, закон двойного отрицания, законы де Моргана и ин.

Закон тождества определяет, что каждое высказывание является логическим следствием самого себя Формальный выражение закона А- А

Закон непротиворечивости определяет, что высказывания А неправильное, если одновременно истинные его утверждения и его отрицание Формальный выражение закона -1 (А л - А)

Закон исключенного третьего определяет, что высказывания А или истинное, или ложное по значению истинности, но не может быть одновременно истинным и ложным Формальный выражение закона А 1 А

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

С возникновением и последующим развитием символической логики были определены новые законы логики высказываний

Закон ассоциативности (лат associ ют определенные логические операции над высказываниями А, В, С для конъюнкции, дизъюнкции, над классами Так, выви-

Закон дистрибутивности (лат (размещение, распределение) выражает соотношение конъюнкции и дизъюнкции в логических операциях сборки и умножения:

Закон експортации определяет, что когда переменные А, В, С соединены символами конъюнкции и импликации, то из истинности конъюнкции А а В вытекает истинность С (А а В - С) К А - ( производительных вывода (чит: если истинность конъюнкции А л В имплицирует С, то, если истинное А, - следует из истинности В следует истинность Синність С).

Закон идемпотентности (лат - то, что сохраняет то же самое) означает: произведение двух высказываний А л А сумма двух высказываний А V А эквивалентна самому высказыванию А, то есть, для конъюнкции А л А = А ( (конъюнкция двух высказываний А и А эквивалентна А), для дизъюнкции А V А = А (дизъюнкция двух высказываний А А эквивалентна А).

Закон коммутативности (лат - изменяющий) означает, что при умножении (конъюнкции) и добавлении (дизъюнкции) результат не зависит от порядка переменных Закон коммутативности: для конъюнкции (А Л В) = В л А) ( (чит: А и В эквивалентно В и А), для дизъюнкции (А V В) = (В V А) (чит: А или В эквивалентно, что В или Або А).

Закон контрапозиции (лат - противопоставление) - закон, по которому импликации можно противопоставить ее отрицание (А - В) = (- В --o А) (чит: если из высказывания А следует высказывание В, то с ния высказывания В следует отрицание Аеречення А).

Закон поглощения определяет, что в конъюнктивный или дизъюнктивной высказывании со сменными А, В осуществляется поглощения дополнительного высказывания Закон поглощения для конъюнкции А л (А v В) = А (чит т: А и (А или В) эквивалентно А), для дизъюнкции А V (А V В) = А (чит: А или (А или В) эквивалентно А А).

Закон двойного отрицания определяет, что двойное отрицание высказывания А (отрицание отрицания) эквивалентно его утверждению изображают формулам:

1 - \"А - А (чит: если неправильно, что не А, то А);

2 * \"\" - \"А = А (чит: неправильно, что не А эквивалентно утверждению А)

Законы де Моргана сформулировал шотландский логик О де Морган:

5. Аксиоматический метод ИВ

АКСИОМАТИЧЕСКИЙ МЕТОД - метод построения теорий, в соответствии с которым разрешается пользоваться в доказательствах лишь аксиомами и ранее выведенными из них утверждениями. Основания для применения аксиоматического метода могут быть разными, что обычно приводит к различению аксиом не только по их формулировкам, но и по их методологическим (прагматическим) статусам. Например, аксиома может иметь статус утверждения, или статус предположения, или статус лингвистического соглашения о желаемом употреблении терминов. Иногда это различие в статусах отражается в названиях аксиом (в современных аксиоматиках для эмпирических теорий среди всех аксиом выделяют часто т.н. постулаты значения, выражающие лингвистические соглашения, а древние греки делили геометрические аксиомы на общие понятия и постулаты, полагая, что первые описывают, вторые строят). Вообще говоря, учет статусов аксиом обязателен, так как можно, например, изменить содержание аксиоматической теории, не изменив при этом ни формулировку, ни семантику аксиом, а поменяв лишь их статус, объявив, скажем, одну из них новым постулатом значения. Аксиоматический метод был впервые продемонстрирован Евклидом в его «Началах», хотя понятия аксиомы, постулата и определения рассматривались уже Аристотелем. В частности, к нему восходит толкование аксиом как необходимых общих начал доказательства. Понимание аксиом как истин самоочевидных сложилось позднее, став основным с появлением школьной логики Пор-Рояля, для авторов которой очевидность означает особую способность души осознавать некоторые истины непосредственно (в чистом созерцании, или интуиции). Между прочим, убеждение Канта в априорном синтетическом характере геометрии Евклида зависит от этой традиции не считать аксиомы лингвистическими соглашениями или предположениями. Открытие неевклидовой геометрии (Гаусс, Лобачевский, Бойяи); появление в абстрактной алгебре новых числовых систем, причем сразу целых их семейств (напр., р-адические числа); появление переменных структур вроде групп; наконец, обсуждение вопросов типа «какая геометрия истинна?» - все это способствовало осознанию двух новых, по сравнению с античным, статусов аксиом: аксиом как описаний (классов возможных универсумов рассуждений) и аксиом как предположений, а не самоочевидных утверждений. Так сформировались основы современного понимания аксиоматического метода. Это развитие аксиоматического метода становится особенно наглядным при сопоставлении «Начал» Евклида с «Основаниями геометрии» Д.Гильберта - новой аксиоматики геометрии, базирующейся на высших достижениях математики 19 в.

К концу того же века Дж.Пеано дал аксиоматику натуральных чисел. Далее аксиоматический метод был использован для спасения теории множеств после нахождения парадоксов. При этом аксиоматический метод был обобщен и на логику. Гильберт сформулировал аксиомы и правила вывода классической логики высказываний, а П. Бернайс - логики предикатов. Ныне аксиоматическое задание является стандартным способом определения новых логик и новых алгебраических понятий. В последние десятилетия по мере развития моделей теории аксиоматический метод стал в почти обязательном порядке дополняться теоретико-модельным. Н.Н.Непейвода

6. Нормальные формы формул логики высказываний

Для каждой формулы алгебры высказываний можно указать равносильную ей формулу, содержащую из логических связок лишь отрицание, конъюнкцию и дизъюнкцию. Для этого нужно, используя равносильности теоремы 4.4, пункты у), ч), выразить все имеющиеся в формуле импликации и эквивалентности через отрицание, конъюнкцию и дизъюнкцию. Так, для формулы равносильной ей формулой, не содержащей логических связок > и - , будет, например, формула

¬(¬X?(¬X?Y))?Y

Выразить данную формулу через отрицание, конъюнкцию и дизъюнкцию возможно не одним способом, а многими. К примеру, рассматриваемая формула равносильна также следующим формулам, содержащим из логических связок лишь ¬,? и ?:

¬¬X?Y,X?Y,(X?Y)?(¬Y?Y),(X?¬Y)?Y,(X?¬Y)?((X?¬X)?Y),(X?¬Y)?(X?Y)?(¬X?Y).

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

Понятие нормальных форм

Конъюнктивным одночленом от переменных

X1,X2,…,Xn

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

X1?X1,X1?¬X2?X3,X2?¬X1?X3?¬X2?X5,X1?X2?¬X1?X3?X1.

Дизъюнктивным одночленом от переменных

X1,X2,…,Xn

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

¬X1?X2?X3,X2?X2,X1?X2?¬X3?¬X1?X4?X2,¬X2?X1?¬X4?X1?X4.

Дизъюнктивной нормальной формой называется дизъюнкция конъюнктивных одночленов, т.е. выражение вида

K1?K2?…?Kp , где все

Ki, i=1,2,…,p , являются конъюнктивными одночленами (не обязательно различными). Аналогично конъюнктивной нормальной формой называется конъюнкция дизъюнктивных одночленов

D1?D2?…?Dq

, где все

Dj, j=1,2,…,q, являются дизъюнктивными одночленами (не обязательно различными). Будем также называть дизъюнктивной (конъюнктивной) нормальной формой указанные выражения при

p=1 (q=1) Нормальную форму, представляющую формулу F (то есть равносильную F), будем называть просто нормальной формой этой формулы.

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

Очевидно, что у данной формулы F существует неограниченно много как дизъюнктивных, так и конъюнктивных нормальных форм. Одни из них более громоздкие и сложные, другие -- более простые. Здесь мы можем продолжить до некоторого момента аналогию со школьной алгеброй. В школьной алгебре выражения типа ax,xyz,(a+b)uv (последнее действие в них -- умножение) называются одночленами, а выражения типа a+b, ax+b, xy+uv+p (последнее действие -- сложение) называются многочленами. В алгебре логики логическое умножение (конъюнкция) и логическое сложение (дизъюнкция) равноправны по своим свойствам. Поэтому выражения типа

X?Y, X?Y?Z называются конъюнктивными одночленами, а выражения типа X?Y, X?Y?Z -- дизъюнктивными одночленами. Образования из одночленов выражений типа

(X?Y)?(P?Q?R),(P?Q)?(X?Y?Z)

называются не многочленами, а нормальными формами. На этом аналогия заканчивается. Далее вводятся понятия совершенных нормальных форм -- дизъюнктивной и конъюнктивной.

Совершенные нормальные формы

Среди множества дизъюнктивных (равно как и конъюнктивных) нормальных форм, которыми обладает данная формула алгебры высказываний, существует уникальная форма: она единственна для данной формулы. Это так называемая совершенная дизъюнктивная нормальная форма (среди конъюнктивных форм -- совершенная конъюнктивная нормальная форма).

Определение 5.1. Одночлен (конъюнктивный или дизъюнктивный) от переменных

X1,X2,…,Xn называется совершенным, если в него от каждой пары Xi,¬Xi (i=1,2,…,n) входит только один представитель ( Xi или ¬Xi ). Нормальная форма (дизъюнктивная или конъюнктивная) от переменных X1,X2,…,Xn называется совершенной от этих переменных, если в нее входят лишь совершенные одночлены (конъюнктивные или дизъюнктивные соответственно) от X1,X2,…,Xn Приведем пример совершенной конъюнктивной нормальной формы от четырех переменных X1,X2,X3,X4: (X1?X2?X3?X4)?(¬X1?X2?¬X3?X4)?(X1?¬X2?¬X3?X4). Вот несколько примеров совершенных дизъюнктивных нормальных форм: (X?Y)?(¬X?Y)?(X?¬Y)(X?Y?¬Z)?(¬X?Y?¬Z)?(X?¬Y?Z)?(X?¬Y?¬Z)?(X?Y?Z),(X1?X2?X3?X4)?(¬X1?¬X2?X3?X4)?(X1?X2?¬X3?X4).

7. Решение логических задач

Решение логических задач средствами алгебры логики

Обычно используется следующая схема решения:

1. изучается условие задачи;

2. вводится система обозначений для логических высказываний;

3. конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;

4. определяются значения истинности этой логической формулы;

5. из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.

Пример 1.

Трое друзей, болельщиков автогонок "Формула-1", спорили о результатах предстоящего этапа гонок.

-- Вот увидишь, Шумахер не придет первым, -- сказал Джон. Первым будет Хилл.

-- Да нет же, победителем будет, как всегда, Шумахер, -- воскликнул Ник. -- А об Алези и говорить нечего, ему не быть первым.

Питер, к которому обратился Ник, возмутился:

-- Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.

По завершении этапа гонок оказалось, что каждое из двух предположений двоих друзей подтвердилось, а оба предположения третьего из друзей оказались неверны. Кто выиграл этап гонки?

Решение. Введем обозначения для логических высказываний:

Ш -- победит Шумахер; Х -- победит Хилл; А -- победит Алези.

Реплика Ника "Алези пилотирует самую мощную машину" не содержит никакого утверждения о месте, которое займёт этот гонщик, поэтому в дальнейших рассуждениях не учитывается.

Зафиксируем высказывания каждого из друзей:

Учитывая то, что предположения двух друзей подтвердились, а предположения третьего неверны, запишем и упростим истинное высказывание

Высказывание истинно только при Ш=1, А=0, Х=0.

Ответ. Победителем этапа гонок стал Шумахер.

Пример 2. Некий любитель приключений отправился в кругосветное путешествие на яхте, оснащённой бортовым компьютером. Его предупредили, что чаще всего выходят из строя три узла компьютера -- a, b, c, и дали необходимые детали для замены. Выяснить, какой именно узел надо заменить, он может по сигнальным лампочкам на контрольной панели. Лампочек тоже ровно три: x, y и z.

Инструкция по выявлению неисправных узлов такова:

1. если неисправен хотя бы один из узлов компьютера, то горит по крайней мере одна из лампочек x, y, z;

2. если неисправен узел a, но исправен узел с, то загорается лампочка y;

3. если неисправен узел с, но исправен узел b, загорается лампочка y, но не загорается лампочка x;

4. если неисправен узел b, но исправен узел c, то загораются лампочки x и y или не загорается лампочка x;

5. если горит лампочка х и при этом либо неисправен узел а, либо все три узла a, b, c исправны, то горит и лампочка y.

В пути компьютер сломался. На контрольной панели загорелась лампочка x. Тщательно изучив инструкцию, путешественник починил компьютер. Но с этого момента и до конца плавания его не оставляла тревога. Он понял, что инструкция несовершенна, и есть случаи, когда она ему не поможет.

Какие узлы заменил путешественник? Какие изъяны он обнаружил в инструкции?

Решение. Введем обозначения для логических высказываний:

a -- неисправен узел а; x -- горит лампочка х;

b -- неисправен узел b; y -- горит лампочка y;

с -- неисправен узел с; z -- горит лампочка z.

Правила 1-5 выражаются следующими формулами:

Формулы 1-5 истинны по условию, следовательно, их конъюнкция тоже истинна:

Выражая импликацию через дизъюнкцию и отрицание (напомним, что ), получаем:

Подставляя в это тождество конкретные значения истинности x=1, y=0, z=0, получаем:

Отсюда следует, что a=0, b=1, c=1.

Ответ на первый вопрос задачи: нужно заменить блоки b и c; блок а не требует замены. Ответ на второй вопрос задачи получите самостоятельно.

II. Решение логических задач табличным способом

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

Пример 3. В симфонический оркестр приняли на работу трёх музыкантов: Брауна, Смита и Вессона, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе.

Известно, что:

1. Смит самый высокий;

2. играющий на скрипке меньше ростом играющего на флейте;

3. играющие на скрипке и флейте и Браун любят пиццу;

4. когда между альтистом и трубачом возникает ссора, Смит мирит их;

5. Браун не умеет играть ни на трубе, ни на гобое.

На каких инструментах играет каждый из музыкантов, если каждый владеет двумя инструментами?

Решение. Составим таблицу и отразим в ней условия задачи, заполнив соответствующие клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание.

Так как музыкантов трoе, инструментов шесть и каждый владеет только двумя инструментами, получается, что каждый музыкант играет на инструментах, которыми остальные не владеют.

Из условия 4 следует, что Смит не играет ни на альте, ни на трубе, а из условий 3 и 5, что Браун не умеет играть на скрипке, флейте, трубе и гобое. Следовательно, инструменты Брауна -- альт и кларнет. Занесем это в таблицу, а оставшиеся клетки столбцов "альт" и "кларнет" заполним нулями:

	скрипка	флейта	альт	кларнет	гобой	труба
Браун	0	0	1	1	0	0
Смит			0	0		0
Вессон			0	0

Из таблицы видно, что на трубе может играть только Вессон.

Из условий 1 и 2 следует, что Смит не скрипач. Так как на скрипке не играет ни Браун, ни Смит, то скрипачом является Вессон. Оба инструмента, на которых играет Вессон, теперь определены, поэтому остальные клетки строки "Вессон" можно заполнить нулями:

	скрипка	флейта	альт	кларнет	гобой	труба
Браун	0	0	1	1	0	0
Смит	0		0	0		0
Вессон	1	0	0	0	0	1

Из таблицы видно, что играть на флейте и на гобое может только Смит.

	скрипка	флейта	альт	кларнет	гобой	труба
Браун	0	0	1	1	0	0
Смит	0	1	0	0	1	0
Вессон	1	0	0	0	0	1

Ответ: Браун играет на альте и кларнете, Смит -- на флейте и гобое, Вессон -- на скрипке и трубе.

Пример 4. Три одноклассника -- Влад, Тимур и Юра, встретились спустя 10 лет после окончания школы. Выяснилось, что один из них стал врачом, другой физиком, а третий юристом. Один полюбил туризм, другой бег, страсть третьего -- регби.

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

Забавно, но у двоих из друзей в названиях их профессий и увлечений не встречается ни одна буква их имен.

Определите, кто чем любит заниматься в свободное время и у кого какая профессия.

Решение. Здесь исходные данные разбиваются на тройки (имя -- профессия -- увлечение).

Из слов Юры ясно, что он не увлекается туризмом и он не врач. Из слов врача следует, что он турист.

Имя	Юра
Профессия		врач
Увлечение		туризм

Буква "а", присутствующая в слове "врач", указывает на то, что Влад тоже не врач, следовательно врач -- Тимур. В его имени есть буквы "т" и "р", встречающиеся в слове "туризм", следовательно второй из друзей, в названиях профессии и увлечения которого не встречается ни одна буква его имени -- Юра. Юра не юрист и не регбист, так как в его имени содержатся буквы "ю" и "р". Следовательно, окончательно имеем:

Имя	Юра	Тимур	Влад
Профессия	физик	врач	юрист
Увлечение	бег	туризм	регби

Ответ. Влад -- юрист и регбист, Тимур -- врач и турист, Юра -- физик и бегун.

Пример 5. Три дочери писательницы Дорис Кей -- Джуди, Айрис и Линда, тоже очень талантливы. Они приобрели известность в разных видах искусств -- пении, балете и кино. Все они живут в разных городах, поэтому Дорис часто звонит им в Париж, Рим и Чикаго.

Известно, что:

1. Джуди живет не в Париже, а Линда -- не в Риме;

2. парижанка не снимается в кино;

3. та, кто живет в Риме, певица;

4. Линда равнодушна к балету.

Где живет Айрис, и какова ее профессия?

Решение.

Составим таблицу и отразим в ней условия 1 и 4, заполнив клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание:

Париж	Рим	Чикаго		Пение	Балет	Кино
0			Джуди
			Айрис
	0		Линда		0

Далее рассуждаем следующим образом. Так как Линда живет не в Риме, то, согласно условию 3, она не певица. В клетку, соответствующую строке "Линда" и столбцу "Пение", ставим 0.

Из таблицы сразу видно, что Линда киноактриса, а Джуди и Айрис не снимаются в кино.

Париж	Рим	Чикаго		Пение	Балет	Кино
0			Джуди			0
			Айрис			0
	0		Линда	0	0	1

Согласно условию 2, парижанка не снимается в кино, следовательно, Линда живет не в Париже. Но она живет и не в Риме. Следовательно, Линда живет в Чикаго. Так как Линда и Джуди живут не в Париже, там живет Айрис. Джуди живет в Риме и, согласно условию 3, является певицей. А так как Линда киноактриса, то Айрис балерина.

В результате постепенного заполнения получаем следующую таблицу:

Париж	Рим	Чикаго		Пение	Балет	Кино
0	0	1	Джуди	1	0	0
1	0	0	Айрис	0	1	0
0	0	1	Линда	0	0	1

Ответ. Айрис балерина. Она живет в Париже.

Решение логических задач с помощью рассуждений

Этим способом обычно решают несложные логические задачи.

Пример 6. Вадим, Сергей и Михаил изучают различные иностранные языки: китайский, японский и арабский. На вопрос, какой язык изучает каждый из них, один ответил: "Вадим изучает китайский, Сергей не изучает китайский, а Михаил не изучает арабский". Впоследствии выяснилось, что в этом ответе только одно утверждение верно, а два других ложны. Какой язык изучает каждый из молодых людей?

Решение. Имеется три утверждения:

1. Вадим изучает китайский;

2. Сергей не изучает китайский;

3. Михаил не изучает арабский.

Если верно первое утверждение, то верно и второе, так как юноши изучают разные языки. Это противоречит условию задачи, поэтому первое утверждение ложно.

Если верно второе утверждение, то первое и третье должны быть ложны. При этом получается, что никто не изучает китайский. Это противоречит условию, поэтому второе утверждение тоже ложно.

Остается считать верным третье утверждение, а первое и второе -- ложными. Следовательно, Вадим не изучает китайский, китайский изучает Сергей.

Ответ: Сергей изучает китайский язык, Михаил -- японский, Вадим -- арабский.

Пример 7. В поездке пятеро друзей -- Антон, Борис, Вадим, Дима и Гриша, знакомились с попутчицей. Они предложили ей отгадать их фамилии, причём каждый из них высказал одно истинное и одно ложное утверждение:

Дима сказал: "Моя фамилия -- Мишин, а фамилия Бориса -- Хохлов". Антон сказал: "Мишин -- это моя фамилия, а фамилия Вадима -- Белкин". Борис сказал: "Фамилия Вадима -- Тихонов, а моя фамилия -- Мишин". Вадим сказал: "Моя фамилия -- Белкин, а фамилия Гриши -- Чехов". Гриша сказал: "Да, моя фамилия Чехов, а фамилия Антона -- Тихонов".

Какую фамилию носит каждый из друзей?

Решение. Обозначим высказывательную форму "юноша по имени А носит фамилию Б" как А_Б, где буквы А и Б соответствуют начальным буквам имени и фамилии.

Зафиксируем высказывания каждого из друзей:

1. Д_М и Б_Х;

2. А_М и В_Б;

3. В_Т и Б_М;

4. В_Б и Г_Ч;

5. Г_Ч и А_Т.

Допустим сначала, что истинно Д_М. Но, если истинно Д_М, то у Антона и у Бориса должны быть другие фамилии, значит А_М и Б_М ложно. Но если А_М и Б_М ложны, то должны быть истинны В_Б и В_Т, но В_Б и В_Т одновременно истинными быть не могут.

Значит остается другой случай: истинно Б_Х. Этот случай приводит к цепочке умозаключений:

Б_Х истинно Б_М ложно В_Т истинно А_Т ложно Г_Ч истинно В_Б ложно А_М истинно.

Ответ: Борис -- Хохлов, Вадим -- Тихонов, Гриша -- Чехов, Антон -- Мишин, Дима -- Белкин.

Пример 8.Министры иностранных дел России, США и Китая обсудили за закрытыми дверями проекты соглашения о полном разоружении, представленные каждой из стран. Отвечая затем на вопрос журналистов: "Чей именно проект был принят?", министры дали такие ответы:

Россия -- "Проект не наш, проект не США";

США -- "Проект не России, проект Китая";

Китай -- "Проект не наш, проект России".

Один из них (самый откровенный) оба раза говорил правду; второй (самый скрытный) оба раза говорил неправду, третий (осторожный) один раз сказал правду, а другой раз -- неправду.

Определите, представителями каких стран являются откровенный, скрытный и осторожный министры.

Решение. Для удобства записи пронумеруем высказывания дипломатов:

Россия -- "Проект не наш" (1), "Проект не США" (2);

США -- "Проект не России" (3), "Проект Китая" (4);

Китай -- "Проект не наш" (5), "Проект России" (6).

Узнаем, кто из министров самый откровенный.

Если это российский министр, то из справедливости (1) и (2) следует, что победил китайский проект. Но тогда оба утверждения министра США тоже справедливы, чего не может быть по условию.

Если самый откровенный -- министр США, то тогда вновь получаем, что победил китайский проект, значит оба утверждения российского министра тоже верны, чего не может быть по условию.

Получается, что наиболее откровенным был китайский министр. Действительно, из того, что (5) и (6) справедливы, cледует, что победил российский проект. А тогда получается, что из двух утверждений российского министра первое ложно, а второе верно. Оба же утверждения министра США неверны.

Ответ: Откровеннее был китайский министр, осторожнее -- российский, скрытнее -- министр США.

Размещено на Allbest.ru

...