2. Графический способ решения систем логических уравнений.

Рассматривая алгебру высказываний, мы сопоставляем ее с алгеброй чисел. Обратимся к сравнению еще раз. В школьной алгебре для решения уравнений и систем уравнений широко используется графический метод. В алгебре высказываний графические методы применяются не менее успешно. При решении логических задач очень часто полезно вычертить “дерево логических условий”. Это “дерево” выражает в виде простого чертежа логическую взаимосвязь между данными высказываниями. Научимся “выращивать” логические деревья на простых примерах. Выращивание любого дерева начинается с рассмотрения исходной формулы. Логической сумме на логическом дереве будет соответствовать “разветвление” ветвей. Логическому произведению на выращиваемом дереве будет соответствовать “следование” ветвей друг за другом. Пример 1. Построить дерево для высказывания А+В. Решение. Каждому простому высказыванию в формуле на выращиваемом дереве будет соответствовать одна ветвь.

Пример 2.

Пример 3.

Пример 4.

 

Пример 5.

 

Пример 6.

Пример 7.

Вернемся к условию задачи № 1, построим к ней графическое дерево и проанализируем каждую его ветвь. Для вычерчивания графического дерева нам понадобятся уравнения (1), (2), (3).

Проанализируем каждую ветвь. Ветвь 1: т.к. T₁ T₂ 0, A₂ T₂ 0 Ветвь 2: т.к. T₁ T₂ 0 Ветвь 3: Ветвь 4: , т.к. D₃ D₄  0 Ветвь 5: , т.к. W₂ T₂ 0, T₂ A₂ _ Ветвь 6: , т.к. W₂_{ 2} _ Ветвь 7: , т.к. W₂ _{ 2} _ Ветвь 8: , т.к. D₃ D₄  _ Итак, только выражение ветви 3 эквивалентно 1: Из этого выражения следует: Таня - первая; Алла - вторая; Даша - третья; Валя - четвертая.

3. Решение логических задач на эвм.

Имея математическую модель для задачи № 1 в виде системы уравнений (1), (2), (3) можно составить алгоритм.

Бейсик- программа. CLS T₁ =0 2 W₂ =0 3 T₂ =0 4 D₃ =0 5 A₂ =0 6 D₄ =0 7 F₁ =T₁ AND NOT W₂ OR NOT T₁ AND W₂ F₂ =T₂ AND NOT D₃ OR NOT T₂ AND D₃ F₃ =A₂ AND NOT D₄ OR NOT A₂ AND D₄ F₄ =NOT (T₁ AND T₂) F₅ =NOT (T₂ AND W₂) F₆ =NOT (T₂ AND A₂) F₇ =NOT (A₂ AND W₂) F₈ =NOT (D₃ AND D₄) F=F₁ AND F₂ AND F₃ AND F₄ AND F₅ AND F₆ AND F₇ AND F₈ IF F=1 THEN ? “F, T₁, W₂, T₂, D₃, A₂, D₄“: ? “F, T₁, W₂, T₂, D₃, A₂, D₄“: END IF Т₁ =0 THEN Т₁ =1: GOTO 7 IF W₂ =0 THEN W₂ =1: GOTO 6 IF T₂=0 THEN T₂ =1: GOTO 5 IF D₃=0 THEN D₃=1: GOTO 4 IF A₂ =0 THEN A₂ =1: GOTO 3 IF D₄=0 THEN D₄=1: GOTO 2

Задача 2. Алеша, Боря и Гриша нашли в земле сосуд. Каждый из них высказал по два предположения. Алеша: " Это сосуд греческий, V века". Боря: " Это сосуд финикийский, III века". Гриша: " Это сосуд не греческий, IV века". Учитель истории сказал ребятам, что каждый из них прав только в одном из двух своих предположений. Где и в каком веке был изготовлен сосуд? Решение. Введем обозначения: G - это сосуд греческий, F - сосуд финикийский. Цифры 3, 4, 5 - век. (1) (2) (3) Умножая (1) на (2), получим: Отбросим те логические произведения, в которых речь идет о невозможных событиях, получим: (4) Умножая уравнение (4) на уравнение (3), получим: Сосуд изготовлен в Финикии в V веке. Проверяем ответ по условию задачи. Проанализируйте самостоятельно графическое дерево задачи № 2 и убедитесь в правильности ответа.

Задача 3. На ледяном поле 5 хоккеистов: Ольховский, Малышев, Белов, Таманин, Лавров - штурмовали ворота. Раздался свисток судьи. "Удаляет двух", - подумали спортсмены. "Без Малышева или Ольховского я не останусь на поле", - сказал Таманин. "Я тоже, "- сказал Лавров. "Удаляют либо меня с Беловым, либо Таманина с Лавровым", - сказал Малышев. Когда судья объявил о своем решении, все оказались правы и, кроме того, Ольховский и Белов не остались вместе на поле. Кто остался на поле ? Решение. Введем буквенные обозначения: O - Ольховский, M - Малышев, B - Белов, T - Таманин, L - Лавров. Высказывания каждого хоккеиста можно задать формулами : M T+O T 1 (1) M L+O L 1 (2) _ _ _ _ M B + T L  1 (3) Для решения системы логических уравнений умножим уравнение (1) на уравнение (2): (M T+O T) (M L+O L)  M T M L + M T O L + O T M L+ O T O L  M T L + M T O L + O T L (4) Полученное выражение (4) умножим на уравнение (3) Из полученного выражения (5) следует, что на поле остались Ольховский, Таманин, Лавров.

Графическое дерево

Проанализировав все ветви графического дерева, можно сделать за-ключение, что единственно правильным решением является ветвь 5

Задача 4. В спортивных соревнованиях принимали участие пять команд: "Вымпел", "Метеор", "Нептун", "Старт" и "Чайка". Об их итогах соревнования имеется пять высказываний: 1). Второе место занял "Вымпел", a "Cтарт" оказался на третьем. 2). Хорошо выступала команда "Нептун", она стала победителем, а "Чайка" вышла на второе место. 3). Да нет же, "Чайка" заняла только третье место, а "Нептун"- был последним. 4). Первое место по праву завоевал "Cтарт", а "Метеор" был 4-м. 5). Да, "Метеор", действительно, был четвертым, а "Вымпел" был 2-м. Известно, что команды не делили места между собой и что в каждом высказывании одно утверждение правильное, а другое нет. Как распределились места между командами?

Задача 5. Шесть спортсменов - Адамов, Белов, Ветров, Глебов, Дронов, Ершов - в проходившем соревновании заняли первые шесть мест, причем ни одно место не было разделено между ними. О том, кто какое место занял, были получены такие высказывания: - "Кажется, первым был Адамов, а вторым - Дронов." - "Нет, на первом месте был Ершов, а на втором - Глебов." - "Вот так болельщики! Ведь Глебов был на третьем месте, Белов - на четвертом." - "И вовсе было не так: Белов был пятым, а Адамов - вторым." - "Вы все перепутали: пятым был Дронов , а перед ним- Ветров." Какое место на соревнованиях заняли участники, если все они оказались на разных местах ?

Задача 6. Перед началом забегов зрители обсуждали скаковые возможности трех лучших лошадей с кличками "Абрек", "Ветер", "Стрелок". - Победит или "Абрек", или "Стрелок", - сказал один болельщик. - Если "Абрек" будет вторым, то победу принесет "Ветер", - сказал другой болельщик. - Много вы понимаете в лошадях, - возмутился третий болельщик. Вто-рым придет или 'Ветер", или "Абрек". - А я вам скажу, - вмешался четвертый болельшик, - что если "Абрек" придет третьим, то "Стрелок" не победит. После забега выяснилось, что три лошади - "Абрек", "Ветер" и "Стрелок" - заняли три первых места, не деля между собой ни одного из мест, и что все четыре предсказания болельщиков были правильны. Как кончился забег?

Задача 7. Один из 3 братьев поставил на скатерть кляксу. - Кто запачкал скатерть ? - спросила бабушка. - Витя не ставил кляксу, - сказал Алеша, - Это сделал Боря. - Ну а ты что скажешь? - спросила бабушка Борю. - Это Витя поставил кляксу, - сказал Боря, - А Алеша не пачкал скатерть. - Так я и знала, что вы друг на друга сваливать будете, - рассердилась бабушка. - Ну а каков твой ответ? - спросила она Витю. - Не сердись бабуля! Я знаю, что Боря не мог этого сделать. А я сегодня не готовил уроков. - сказал Витя. Оказалось, что двое мальчиков в каждом из двух своих заявлений сказали правду, а один оба раза сказал неправду. Кто поставил на скатерть кляксу?

Задача 8. Нужно для 4 дежурных - Антипова, Климова, Маркова и Лебедева - составить график дежурств на агитпункте с соблюдением следующих условий: 1) Если Лебедев не будет дежурить в понедельник, то в понедельник согласен дежурить Климов. 2) Ecли Климов не сможет дежурить ни в понедельник, ни в чет- верг, то Антипов будет дежурить в понедельник. 3) Если Марков не сможет дежурить в четверг, то Климов будет дежу- рить в среду. 4) Если Лебедев придет дежурить во вторник, то Климов не будет дежурить в понедельник. 5) Если Антипов не сможет дежурить в Понедельник, то Марков не сможет дежурить во вторник. Каким должен быть график дежурств ?

Задача 9. Обсуждался вопрос о включении в состав сборной команды пяти молодых игроков: Асеева, Валеева, Сватеева, Деева и Евтеева. Выбор обусловлен следующими условиями: 1) В команду необходимо включить не менее чем одного из трех игро- ков: Асеева, Валеева, Евтеева, но не более чем одного из трех игроков: Асеева, Сватеева, Деева. 2) Сватеева можно включить в сборную без Валеева тогда и только тогда, когда Асеев будет включен, а Деев не будет включен. 3) Если Валеев будет включен в сборную, а Сватеев не будет включен, то сборную нужно пополнять и Деевым, и Евтеевым. 4) Если Асеев не будет включен в команду, то нужно в нее включить и Сватеева, и Евтеева. Кого из игроков можно включить в сборную команду?

Задача 10. Семья, состоящая из отца, матери и трех дочерей - Ани, Веры и Cветы, - купила телевизор. Каждому, конечно, хотелось посмотреть передачу в первый вечер. - Нам нужно распределить обязанности, чтобы не остаться без ужи-на, - сказал папа. - Правильно, - поддержала мама. - Но только когда ты будешь смотреть передачу, я тоже сяду у телевизора. - Хорошо, - согласился папа. - Кому из нас повезло, так это Свете и Вере, - улыбнулся папа. - По крайней мере, одна из них получит удовольствие. - А нам с тобой, Анечка, придется смотреть передачу только по очереди, - сказала мама. - Я согласна, - ответила Аня. - Только ты нам разреши с Верой вместе работать на кухне или вместе быть у телевизора. - Пожалуй, Свету одну нельзя оставлять. - сказал папа. - Если она пожелает смотреть передачу, то придется и мне с Верой посидеть с ней. Все предложения были приняты. Кто смотрел передачу в первый вечер?

Задача 11. Четыре молодых рабочих - Антонов, Петров, Степанов и Демьянов - работают на одном предприятии и учатся заочно. Как составить для них график свободных от работы дней в первые четыре дня, исходя из таких условий производства: 1) если во вторник выходными будут Демьянов или Антонов, то Сте- панову нужно дать выходной в понедельник; 2) если Демьянова освободить от работы в четверг, то Антонова нужно освободить в понедельник, и Степанова в среду; 3) если Степанова освободить от работы во вторник или Демьянова освободить в среду, то Петрову нужно давать выходной день в четверг; 4) если Антонов будет освобожден в среду, то у Петрова выходной день будет во вторник, а если Петрову поставить выходной в среду, то Антонов может не приходить на работу во вторник; 5) если Демьянову высвободить понедельник, то у Степанова выходной прийдется на среду, а если Демьянов получит выходной в среду, то тогда Антонов может не приходить на работу во вторник.

В основе обработки компьютером информации лежит алгебра логики, разработанная Дж. Булем. Было доказано, что все электронные схемы ЭВМ могут быть реализованы с помощью логических элементов И, ИЛИ, НЕ.

Элемент НЕ

A
0	1
1	0

При подаче на вход схемы сигнала низкого уровня (0) транзистор будет заперт, т.е. ток через него проходить не будет, и на выходе будет сигнал высокого уровня (1). Если же на вход схемы подать сигнал высокого уровня (1), то транзистор “откроется”, начнет пропускать электрический ток. На выходе за счет падения напряжения установится напряжение низкого уровня. Таким образом, схема преобразует сигналы одного уровня в другой, выполняя логическую функцию.

Элемент ИЛИ

А	В	С
0	0	0
0	1	1
1	0	1
1	1	1

Функция “ИЛИ” - логическое сложение (дизъюнкция), ее результат равен 1, если хотя бы 1 из аргументов равен 1. Здесь транзисторы включены параллельно друг другу. Если оба закрыты, то их общее сопротивление велико и на выходе будет сигнал низкого уровня (логический “0”). Достаточно подать сигнал высокого уровня (“1”) на один из транзисторов, как схема начнет пропускать ток, и на сопротивлении нагрузки установится также сигнал высокого уровня (логическая “1”).

Элемент И

A	B	C
0	0	0
0	1	0
1	0	0
1	1	1

Если на входы Вх1 и Вх2 поданы сигналы низкого уровня (логические “0”), то оба транзистора закрыты, ток через них не проходит, выходное напряжение на R_н близко к нулю. Пусть на один из входов подано высокое напряжение (“1”). Тогда соответствующий транзистор откроется, однако другой останется закрытым, и ток через транзисторы и сопротивление проходить не будет. Следовательно, при подаче напряжения высокого уровня лишь на один из транзисторов, схема не переключается и на выходе остается напряжение низкого уровня. И лишь при одновременной подаче на входы сигналов высокого уровня (“1”) на выходе мы также получим сигнал высокого уровня.

Вариант № 1

Четыре ученицы: Мария, Нина, Ольга, Поля участвовали в соревновании и заняли первые 4 места. На вопрос, кто из них какое место занял, 3 девушки ответили: 1. Ольга была вторая, Поля - третья; 2. Ольга была первая, Нина - вторая; 3. Мария была вторая, Поля - четвертая.

В каждом из этих ответов одна часть верна, другая нет. Кто какие места занял в соревнования?

Вариант № 2

При составлении расписания на понедельник в 9-а классе преподаватели высказали просьбы завучу: 1. Учитель математики: “Желаю иметь первый или второй урок” 2. Учитель истории: “Желаю иметь первый или третий урок” 3. Учитель литературы: “Желаю иметь второй или третий урок”

Какое расписание будет составлено?

Вариант № 3

Предстоят спортивные соревнования между четырьмя восьмыми классами одной школы. В учительской живо обсуждаются возможные результаты и высказываются прогнозы. 1). Первое место займет 8-А, а второе - 8-Б,- сказал учитель математики. 2). Да что вы! - сказал учитель географии. - Я недавно ходил с ними в поход и знаю их возможности. 8-А займет второе место, а 8-Г-только третье. 3). А я думаю, что на втором месте будет 8-В,- сказала завуч школы,- а 8-Г будет на последнем месте.

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

Вариант № 4

Четыре марсианки, оказавшиеся на Земле в 2... году, на вопрос об их возрасте дали ответы: 1. МИ - 22 года, МЕ - 21 год 2. МО - 19 лет, МИ - 21 год 3. МА - 21 года, МО - 18 лет

Все марсианки - разных возрастов, притом только данных: 18, 19, 21 и 22. В каждом ответе одна часть верна, другая - нет. Сколько лет каждой?

Вариант 1.

1. Докажите эквивалентность:

2. Докажите, является ли данное высказывание тавтологией:

3. Установите истинность высказывания:

4. Для формулы придумайте формализуемое ею высказывание:

5. Данное высказывание преобразуйте в эквивалентное, но уже не содержащее отрицаний сложных высказываний:

6. Упростите:

Вариант 2.

1. Докажите эквивалентность:

2. Докажите, является ли данное высказывание тавтологией:

3. Установите истинность высказывания:

4. Для формулы придумайте формализуемое ею высказывание:

5. Данное высказывание преобразуйте в эквивалентное, но уже не содержащее отрицаний сложных высказываний:

6. Упростите:

Вариант 3.

1. Докажите эквивалентность:

2. Докажите, является ли данное высказывание тавтологией:

3. Установите истинность высказывания:

4. Для формулы придумайте формализуемое ею высказывание:

5. Данное высказывание преобразуйте в эквивалентное, но уже не содержащее отрицаний сложных высказываний:

6. Упростите:

Вариант 4.

1. Докажите эквивалентность:

2. Докажите, является ли данное высказывание тавтологией:

3. Установите истинность высказывания:

4. Для формулы придумайте формализуемое ею высказывание:

5. Данное высказывание преобразуйте в эквивалентное, но уже не содержащее отрицаний сложных высказываний:

6. Упростите:

Вариант №1.

1. Докажите эквивалентность:

2. Докажите, является ли данное высказывание тавтологией:

3. Установите истинность высказывания:

4. Упростите:

5. Записать логическую функцию, описывающую состояние логической схемы. Составить таблицу истинности.

6. По заданной таблице истинности записать логическую функцию. Упростить полученную логическую функцию. Составить логическую схему.

A	B	C	F(a,b,c)
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	0

Вариант №2.

1. Докажите эквивалентность:

2. Докажите, является ли данное высказывание тавтологией:

3. Установите истинность высказывания:

4. Упростите:

5. Записать логическую функцию, описывающую состояние логической схемы. Составить таблицу истинности.

6. По заданной таблице истинности записать логическую функцию. Упростить полученную логическую функцию. Составить логическую схему.

A	B	C	F(a,b,c)
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

Вариант №3.

1. Докажите эквивалентность:

2. Докажите, является ли данное высказывание тавтологией:

3. Установите истинность высказывания:

4. Упростите:

5. Записать логическую функцию, описывающую состояние логической схемы. Составить таблицу истинности.

6. По заданной таблице истинности записать логическую функцию. Упростить полученную логическую функцию. Составить логическую схему.

A	B	C	F(a,b,c)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

Вариант №4.

1. Докажите эквивалентность:

2. Докажите, является ли данное высказывание тавтологией:

3. Установите истинность высказывания:

4. Упростите:

5. Записать логическую функцию, описывающую состояние логической схемы. Составить таблицу истинноcти.

6. По заданной таблице истинности записать логическую функцию. Упростить полученную логическую функцию. Составить логическую схему.

A	B	C	F(a,b,c)
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	0

Задача №1. (Бур Оля, Гимельфарб Наташа, Мельник Маша)

Семья, состоящая из отца, матери и трех дочерей - Ани, Веры и Светы, - купила телевизор. Каждому, конечно, хотелось посмотреть передачу в первый вечер.

- Нам нужно распределить обязанности, чтобы не остаться без ужина, - сказал папа. - Правильно, - поддержала мама. - Но только когда ты будешь смотреть передачу, я тоже сяду у телевизора. - Хорошо, - согласился папа. - Кому из нас повезло, так это Свете и Вере, - улыбнулся папа. - По крайней мере одна из них получит удовольствие. - А нам с тобой, Анечка, придется смотреть передачу только по очере-ди, - сказала мама. - Я согласна, - ответила Аня. - Только ты нам разреши с Верой вместе работать на кухне или вместе быть у телевизора. - Пожалуй, Свету одну нельзя оставлять. - сказал папа. - Если она пожелает смотреть передачу, то придется и мне с Верой посидеть с ней.

Все предложения были приняты. Кто смотрел передачу в первый вечер?

Решение.

Введем буквенное обозначение: A - Аня, B - Валя, C - Света, O - отец, M - мать. На основе высказываний членов семьи составим систему логических уравнений. Т.к. по условию задачи либо отец и мать смотрят телевизор вдвоем, либо отец не смотрит телевизор, либо оба не смотрят, составим уравнение 1:

По условию смотреть телевизор могут по крайней мере или Света, или Вера, или обе. Уравнение (2) будет иметь вид:

Если Света смотрит телевизор, то имеем CЧOЧB, если же Света не смотрит, то остаются возможности, что отец и Валя оба смотрят или нет, или смотрит только отец или только Валя:

Аня и мама смотрят телевизор только по очереди:

Аня и Валя либо у телевизора вместе, либо на кухне:

Систему уравнений из пяти логических уравнений решаем так: умножим (1) на (2), получим:

Умножим полученное уравнение (6) на уравнение (4), получим:

Умножим полученное уравнение (7) на (5), получим:

Умножим полученное уравнение (8) на (3), получим:

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

Алгоритм. алг Задача 2 (цел F, F1, F2, F3, F4, F5) арг F1, F2, F3, F4, F5 рез F нач 0:=0 1: М:=0 2: А:=0 3: В:=0 4: С:=0 5: F1:=(О и М) или (не О) F2:=(В и не С) или С F3:=(не М и А) или (М и не В) F4:=(А и В) или (не А и не В) F5:=( не С) или (С и О и В) F:=F1 и F2 и F3 и F4 и F5 если F:=1 то вывод F; O; M; A; B; C все если С<1 то С:=1:Перейти к 5 все если В<1 то B:=1: Перейти к 4 все если A<1 то A:=1: Перейти к 3 все если М<1 то M:=1: Перейти к 2 все если O<1 то O:=1: Перейти к 1 все кон

Задача №2. (Cорокина Марина, Тимофеева Юлия, Cерпенин Евгений)

Четыре молодых рабочих - Антонов, Петров, Степанов и Демьянов- работают на одном предприятии и учатся заочно. Как составить для них график свободных от работы дней в первые четыре дня, исходя из таких условий производства:

1. Если во вторник выходными будут Демьянов или Антонов, то Степанову нужно дать выходной в понедельник;

2. Если Демьянова освободить от работы в четверг, то Антонова нужно освободить в понедельник, и Степанова в среду;

3. Если Степанова освободить от работы во вторник или Демьянова освободить в среду, то Петрову нужно давать выходной день в четверг;

4. Если Антонов будет освобожден в среду, то у Петрова выходной день будет во вторник, а если Петрову поставить выходной в среду, то Антонов может не приходить на работу во вторник;

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

Решение. Введем буквенные обозначения: А1- Антонов выходной в Понедельник; А2- Антонов выходной во Вторник; А3- Антонов выходной в среду; P2- Петров выходной во вторник ; P3- Петров выходной в среду; P4- Петров выходной в четверг; S1- Степанов выходной в Понедельник; S2- Степанов выходной во Вторник; S3- Степанов выходной в среду; D1- Демьянов выходной в Понедельник; D2- Демьянов выходной во Вторник; D3- Демьянов выходной в среду; D4- Демьянов выходной в четверг.

Условия производства можно задать формулами: Умножим уравнение (1) на уравнение (2):

Умножим полученное выражение (6) на уравнение (5):

Умножим полученное выражение (7) на уравнение (4):

Умножая полученное выражение (8) на уравнение (3), получим после сокращения ложных высказываний:

Согласно выражению (9) ответом может быть: A1*S3*P4 (а) или A1*S3*P2 (б), или S1*A2*P4 (в), однако (а и б) не подходят по условию задачи. Cледовательно, Степанов свободен в понедельник, Антонов - во вторник, Демьянов - в среду, Петров - в четверг.

Графическое дерево.

Алгоритм.

алг Задача 3 (F,F1,F2,F3,F4,F5,f6,f7,f8,f9,fa,fb,fc,fe,ff,fg,fh,fk,fj) арг F1,F2,F3,F4,F5,f6,f7,f8,f9,fa,fb,fc,fe,ff,fg,fh,fk,fj рез Fj нач 1: А1:=0 2: А2:=0 3: А3:=0 4: S1:=0 5: S2:=0 6: S3:=0 7: D1:=0 8: D2:=0 9: D3:=0 10: D4:=0 11: P2:=0 12: P3:=0 13: P4:=0 14: F1:=((не D2)и (не А2))или S1 F2:=(не D4)или (A1и S3) F3:=(не S2и D3)или Р4 F4:=((не A3)или P2)и ((не P3)или A2) F5:=((не D1)или S3)и ((не D3)или A2) F6:=(не a1или не a2) и (не a или не a3) F7:=(не s1 или не s2) и (не s2 или не s3) и (не s1 или не s3) F8:=(не d1 или не d2) и (не d2 или не d3) и (не d1 или не d3) F9:=(не d1 или не d4) и (не d2 или не d4) и (не d3 или не d4) fa:=(не p2 или не p3) и (не p3 или не p4) и (не p2 или не p4) fb:=(не a1 или не s1) и (не s1 или не d1) и (не d1 или не a1) fc:=(не a2 или не s2) и (не a2 или не d2) и (не d2 или не s2) fe:=(не p2 или не a2) и (не p2 или не s2) и (не p2 или не d2) ff:=(не a3 или не s3) и (не s3 или не d3) и (не d3 или не p3) fg:=(не p3 или не a3) и (не p3 или не s3) и (не a3 или не d3) fh:=(не d4 или не p4) Fj:=F1 и F2 и F3 и F4 и F5 и f6 и f7 и f8 и f9 fk:= fa и fb и fc и ff и fe и ff и fg и fh f:=fj и fk если F=1 то вывод F ;A1 ;A2 ;A3 ;S1 ;S2 ;S3 ;D1 ;D2 ;D3 ;D4 ;P2 ;P3 ;P4 все если P4<1 то P4=1: переход на 14 все если P3<1 то P3=1: переход на 13 все если P2<1 то P2=1: переход на 12 все если D4<1 то D4=1: переход на 11 все если D3<1 то D3=1: переход на 10 все если D2<1 то D2=1: переход на 9 все если D1<1 то D1=1: переход на 8 все если S3<1 то S3=1: переход 7 все если S2<1 то S2=1: переход 6 все если S1<1 то S1=1: переход 5 все если A3<1

то A3=1: переход 4 все если A2<1 то A2=1: переход 3 все если A1<1 то A1=1: переход 2 все кон

Бейсик-программа.

1CLS ?" f";" a1 ";"a2 ";"a3 ";"s1 ";"s2 ";"s3 ";"d1 ";"d2 ";"d3 ";"d4 ";"p2 ";"p3 ";"p4 " 10 A1=0 20 A2=0 30 A3=0 40 S1=0 50 S2=0 60 S3=0 70 D1=0 80 D2=0 90 D3=0 100 D4=0 110 P2=0 120 P3=0 130 P4=0 140 F1=( (not D2) and (not A2)) OR S1 150 F2=(not D4) OR ( A1 and S3) 160 F3=( not S2 and D3) OR ( P4) 170 F4=( (not A3) OR P2) and ( (not P3) OR A2) 180 F5=((NOT D1) OR S3) and ((NOT D3) OR A2) 181 f6=(not a1 or not a2) and (not a2 or not a3) and (not a1 or not a3) 182 f7=(not s1 or not s2) and (not s2 or not s3) and (not s1 or not s3) 183 f8=(not d1 or not d2) and (not d2 or not d3) and (not d1 or not d3) 184 f9=(not d1 or not d4) and (not d2 or not d4) and (not d3 or not d4) 185 fa=(not p2 or not p3) and (not p3 or not p4) and (not p2 or not p4) 186 fb=(not a1 or not s1) and (not s1 or not d1) and (not d1 or not a1) 187 fc=(not a2 or not s2) and (not a2 or not d2) and (not d2 or not s2) 188 fe=(not p2 or not a2) and (not p2 or not s2) and (not p2 or not d2) 189 ff=(not a3 or not s3) and (not s3 or not d3) and (not d3 or not p3) 190 fg=(not p3 or not a3) and (not p3 or not s3) and (not a3 or not d3) 191 fh=(not d4 or not p4) 192 Fj=F1 AND F2 AND F3 AND F4 AND F5 and f6 and f7 and f8 and f9 193 fk= fa and fb and fc and ff and fe and ff and fg and fh 194 f=fj and fk 200 IF F=1 THEN ?F ;A1 ;A2 ;A3 ;S1 ;S2 ;S3 ;D1 ;D2 ;D3 ;D4 ;P2 ;P3 ;P4 210 IF P4<1 THEN P4=1:GOTO 140 220 IF P3<1 THEN P3=1:GOTO 130 230 IF P2<1 THEN P2=1:GOTO 120 240 IF D4<1 THEN D4=1:GOTO 110 250 IF D3<1 THEN D3=1:GOTO 100 260 IF D2<1 THEN D2=1:GOTO 90 270 IF D1<1 THEN D1=1:GOTO 80 280 IF S3<1 THEN S3=1:GOTO 70 290 IF S2<1 THEN S2=1:GOTO 60 300 IF S1<1 THEN S1=1:GOTO 50 310 IF A3<1 THEN A3=1:GOTO 40 320 IF A2<1 THEN A2=1:GOTO 30 330 IF A1<1 THEN A1=1:GOTO 20 ?"end" 340 END

Паскаль-программа.

program zadacha3; {Сорокина М., Тимофеева Ю.} uses crt; var a1,a2,a3,s1,s2,s3,d1,d2,d3,d4,p2,p3,p4,f1,f2,f3,f4,f5,f6,f7,f8,f9:boolean; f10,f11,f12,f13,f14,f15,f16,f17,f18:boolean; n:integer; function func{(a1,a2,a3,b1,b2,c1)}:boolean; var f:array[1..18] of boolean; begin f[1]:=((not d2) and (not a2)) or s1; f[2]:=(not d4) or (a1 and s3); f[3]:=(not s2 and d3) or p4; f[4]:=((not a3) or p2) and (( not p3) or a2); f[5]:=((not d1) or s3) and (( not d3) or a2); f[6]:=(not a1 or not a2) and ( not a2 or not a3) and ( not a1 or not a3); f[7]:=(not s1 or not s2) and ( not s2 or not s3) and ( not s1 or not s3); f[8]:=(not d1 or not d2) and (not d2 or not d3) and ( not d1 or not d3); f[9]:=(not d1 or not d4) and (not d2 or not d4) and ( not d3 or not d4); f[10]:=(not p2 or not p3) and (not p3 or not p4) and ( not p2 or not p4); f[11]:=(not a1 or not s1) and (not s1 or not d1) and ( not d1 or not a1); f[12]:=(not a2 or not s2) and (not a2 or not d2) and ( not d2 or not s2); f[13]:=(not p2 or not a2) and (not p2 or not s2) and ( not p2 or not d2); f[14]:=(not a3 or not s3) and (not s3 or not d3) and ( not d3 or not p3); f[15]:=(not p3 or not a3) and (not p3 or not s3) and ( not a3 or not d3); f[16]:=(not d4 or not p4); f[17]:=f[1] and f[2] and f[3] and f[4] and f[5] and f[6] and f[7] and f[8] and f[9]; f[18]:=f[10] and f[11] and f[12] and f[13] and f[14] and f[15] and f[16]; func:=f[17] and f[18]; end; procedure ff(i:integer); begin case i of 1:begin a1:=false;n:=n-1;ff(i+1); a1:=true;n:=n+1;ff(i+1); end; 2:begin a2:=false;n:=n-1;ff(i+1); a2:=true;n:=n+1;ff(i+1); end; 3:begin a3:=false;n:=n-1;ff(i+1); a3:=true;n:=n+1;ff(i+1); end; 4:begin s1:=false;n:=n-1;ff(i+1); s1:=true;n:=n+1;ff(i+1); end; 5:begin s2:=false;n:=n-1;ff(i+1); s2:=true;n:=n+1;ff(i+1); end; 6:begin s3:=false;n:=n-1;ff(i+1); s3:=true;n:=n+1;ff(i+1); end; 7:begin d1:=false;n:=n-1;ff(i+1); d1:=true;n:=n+1;ff(i+1); end; 8:begin d2:=false;n:=n-1;ff(i+1); d2:=true;n:=n+1;ff(i+1); end; 9:begin d3:=false;n:=n-1;ff(i+1); d3:=true;n:=n+1;ff(i+1); end; 10:begin d4:=false;n:=n-1;ff(i+1); d4:=true;n:=n+1;ff(i+1); end; 11:begin p2:=false;n:=n-1;ff(i+1); p2:=true;n:=n+1;ff(i+1); end; 12:begin p3:=false;n:=n-1;ff(i+1); p3:=true;n:=n+1;ff(i+1); end; 13:begin p4:=false;n:=n-1;ff(i+1); p4:=true;n:=n+1;ff(i+1); end; 14:begin if (func=true) and (n>3) then begin writeln('a1 a2 a3 s1 s2 s3 d1 d2 d3 d4 p2 p3 p4'); writeln(a1,' ',a2,' ',a3,' ',s1,' ',s2,' ',s3,' ',d1,' ',d2,' ',d3,' ',d4,' ',p2,' ',p3,' ',p4,' ' ); end; end; end; end; begin clrscr; n:=13; ff(1); end.

Задача №3. (Драгунов Денис, Кириллов Михаил)

Следователь допросил трех лиц A, B и C, подозреваемых в совершении преступления. На допросе A сказал, что показания B неверны. B сказал, что показания С неверны. Наконец, C сказал, что и A говорит неправду и B говорит неправду. Может ли следователь на основании этих показаний установить, кто из допрошенных говорит правду?

Решение. Допрошенный А мог сказать правду, а мог сказать и неправду. Поэтому его показания можно записать такой формулой :

Показания допрошенного B можно задать такой формулой:

Рассмотрим, что скрывается в показаниях допрошенного С. С может говорить правду, в таком случае неправду говорят A и B: Но С может сказать и неправду, в таком случае, по крайней мере, один из A или B говорит правду:

Объединяя знаком дизъюнкции высказывания (3) и (4), получим содержание сказанного С:

Таким образом, имеем систему логических уравнений:

Для решения системы уравнений умножим уравнение (1) на уравнение (2):

Умножаем уравнение (5) на уравнение (6):

Cледовательно, правду сказал подозреваемый B.

Графическое дерево. Анализируя графическое дерево можно сделать вывод, что ответом является ветвь 9.

Алгоритм.

алг задача 4 ( цел F1, F2, F3, F5 ) арг F1, F2, F3 рез F5 нач цел F4 1: A:=0 2: B:=0 3: C:=0 4: F1:= A и не B или не A и B F2:= B и не C или не B и C F3:= C и не A и не B или не C и ( A или B ) F4:= F1 и F2 F5:= F3 и F4 если F5=1 то вывод F5, A, B, C все если c<1 то c:=1: переход к 4 все если B<1 то B:=1: переход к 3 все если A<1 то A:=1: переход к 2 все кон

Бейсик-программа.

10 A=0 20 B=0 30 C=0 40 F1=A AND NOT B OR NOT A AND B 50 F2=B AND NOT C OR NOT B AND C 60 F3=C AND NOT A AND NOT B OR NOT C AND (A OR B) 70 F4=F1 AND F2 80 F5=F3 AND F4 90 IF F5=1 THEN ?"F5";" A";" B";" C":?F5;A;B;C:END 100 IF C<1 THEN C=1:GOTO 40 110 IF B<1 THEN B=1:GOTO 30 120 IF A<1 THEN A=1:GOTO 20 130 END

Паскаль-программа.

program zad4;{ДРАГУНОВ ДЕНИС} uses crt; var a,b,c:boolean; function func:boolean; var f:array[1..4] of boolean; begin f[1]:=(a and not b) or (not a and b); f[2]:=(b and not c) or (not b and c); f[3]:=(c and not a and not b) or (not c and a or b); f[4]:=f[1] and f[2]; func:=f[3] and f[4]; end; procedure ff(i:integer); begin case i of 1:begin a:=false;ff(i+1); a:=true;ff(i+1); end; 2:begin b:=false;ff(i+1); b:=true;ff(i+1); end; 3:begin c:=false;ff(i+1); c:=true;ff(i+1); end; 4:begin if func=true then begin writeln('a b c'); writeln(a,' ',b,' ',c); end; end; end; end; begin CLRSCR; ff(1); end.

Задача №4. ( Ящук Александр, Динер Светлана)

Обсуждая вопрос о включении в состав сборной команды пяти молодых игроков : Асеева, Валеева, Сватеева, Деева и Евтеева.

Выбор обусловлен следующими условиями:

1. В команду необходимо включить не менее чем одного из трех игроков: Асеева, Валеева, Евтеева, но не более чем одного из трех игроков: Асеева, Сватеева, Деева.

2. Сватеева можно включить в сборную без Валеева тогда и только тогда, когда Асеев будет включен, а Деев не будет включен.

3. Если Валеев будет включен в сборную, а Сватеев не будет включен, то сборную нужно пополнять и Деевым, и Евтеевым.

4. Если Асеев не будет включен в команду, то нужно в нее включить и Сватеева, и Евтеева.

Кого из игроков можно включить в сборную команду?

Решение. Введем буквенные обозначения: A-Асеев, E-Евтеев, B-Валеев, D-Деев, C-Сватеев. Условия выбора игроков для сборной команды заданы в задаче высказываниями 1,2,3,4. По этим высказываниям выпишем формулы:

Для решения системы логических уравнений сначала умножим уравнение (2) на уравнение (3):

Умножим полученное выражение (6) на уравнение (4), получим:

Умножим полученное выражение (7) на уравнение (1), получим: В уравнении (8) перемножим сначала выражение, заключенное в первые скобки, на выражение, заключенное в третьи скобки, получим:

Перемножим полученное выражение (9) на выражение, заключенное в вторые скобки, уравнения (8), получим:

Ответ. В команду включены: Валеев, Сватеев, Евтеев.

Алгоритм.

алг задача (цел a,e,b,d,q,w,r,f1,f2,f3,f4,f) арг a,e,b,d,q,w,r,f1,f2,f3,f4 рез f нач 1: a:=0 2: e:=0 3: b:=0 4: d:=0 5: c:=0 6: q:=(a и не e и не b) или (не a и не e и b) или (не a и e и не b) w:=(a и e и не b) или (a и не e и b) или (не a и b и e) или (a и e и b) r:=(a и не c и не d или не a и c и не d или не a и не c и d) f1:=(q или w) и r f2:=((c и не b) и (a и не d)) или (не(c и не b) и не(a и не d)) f3:=не(b и не c) или (d и e) f4:=a или (c и e) f:=f1 и f2 и f3 и f4 если f=1 то вывод a;e;b;d;c все если c<1 то c:=1: переход на 6 все если d<1 то d:=1: переход на 5 все если b<1 то b:=1: переход на 4 все если e<1 то e:=1: переход на 3 все если a<1 то a:=1: переход на 2 все кон

Бейсик-программа.

cls 10 a=0 20 e=0 30 b=0 40 d=0 50 c=0 60 q=(a and not e and not b)or(not a and not e and b)or(not a and e and not b) w=(a and e and not b)or(a and not e and b)or(not a and b and e)or(a and e and b) r=(a and not c and not d or not a and c and not d or not a and not c and d) f1=(q or w) and r f2=((c and not b) and (a and not d))or(not(c and not b) and not(a and not d)) f3=not(b and not c) or (d and e) f4=a or (c and e) f=f1 and f2 and f3 and f4 if f=1 then ?" A ";"E ";"B ";"Д ";"C ":? a;e;b;d;c if f=1 then stop if c<1 then c=1:goto 60 if d<1 then d=1:goto 50 if b<1 then b=1:goto 40 if e<1 then e=1:goto 30 if a<1 then a=1:goto 20 end

Паскаль-программа.

program zad5; {Ящук Александр} uses crt; var c,e,b,a,d:boolean; function func{(a1,a2,a3,b1,b2,c1)}:boolean; var f:array[1..7] of boolean; begin f[1]:=(a and e and not b)or(not a and not e and b)or(not a and e and not b); f[2]:=(a and e and not b)or(a and not e and b)or(not a and b and e)or(a and e and ); f[3]:=(a and not c and not d or not a and c and not d or not a and not c and d); f[4]:=(f[1] or f[2]) and f[3]; f[5]:=((c and not b)and(a and not d))or(not(c and not b) and not(a and not d)); f[6]:=not(b and not c) or (d and e); f[7]:=a or (c and e); func:=f[4] and f[5] and f[6] and f[7]; end; procedure ff(i:integer); begin case i of 1:begin a:=false;ff(i+1); a:=true;ff(i+1); end; 2:begin e:=false;ff(i+1); e:=true;ff(i+1); end; 3:begin b:=false;ff(i+1); b:=true;ff(i+1); end; 4:begin d:=false;ff(i+1); d:=true;ff(i+1); end; 5:begin c:=false;ff(i+1); c:=true;ff(i+1); end; 6:begin if func=true then begin writeln('a e b d c'); writeln(a,' ',e,' ',b,' ',d,' ',c); end; end; end; end; begin clrscr; ff(1); 8:end.

Задача №5 (Гусарова Д., Межуева О.)

Один из 3 братьев поставил на скатерть кляксу. -Кто запачкал скатерть ? - спросила бабушка. -Витя не ставил кляксу, - сказал Алеша, - Это сделал Боря. -Ну а ты что скажешь? - спросила бабушка Борю. -Это Витя поставил кляксу,- сказал Боря,- А Алеша не пачкал скатерть. -Так я и знала, что вы друг на друга сваливать будете, - рассердилась бабушка. - Ну а каков твой ответ? - спросила она Витю. -Не сердись бабуля! Я знаю, что Боря не мог этого сделать. А я сегодня не готовил уроков.- сказал Витя. Оказалось, что двое мальчиков в каждом из двух своих заявлений сказали правду, а один оба раза сказал неправду. Кто поставил на скатерть кляксу?

Решение. Введем буквенные обозначения: V-Витя, B-Боря, A-Алеша. Высказывание каждого мальчика о том, кто поставил кляксу можно задать формулами: По условию задачи, двое мальчиков оба раза сказали правду, а 1 мальчик оба раза сказал неправду. Поэтому среди записанных нами 3 формул две истинны, а одна ложна. Мы не знаем, какая именно формула ложна. Но мы утверждаем, что если из этих формул образовать попарные дизъюнкции, то поскольку в каждую дизъюнкцию будут, входит, по крайней мере, одна истинная формула, эти дизъюнкции будут истинными. Образуем их. Умножим уравнение (4) на уравнение (5), получим: Умножим выражение (7) на уравнение (6), получим:

Ответ: Кляксу поставил Витя.

Графический способ решения системы логических уравнений: Анализируя вычерченное дерево, делаем вывод, что решением системы логических уравнений является ветвь 8. Ей соответствует формула:

Алгоритм.

алг задача 6 (цел F1,F2,F3,F) арг F1,F2,F3 рез F нач V:=0 3: B:=0 2: A:=0 1: F1:= не V и B или V и не A F2:= V и не A или не B F3:= (не V и B) или не B F := F1 и F2 и F3 если F=1 то вывод V, A, B все если A<1 то A:=1: переход к 1 все если B<1 то B:=1: переход к 2 все если V<1 то V:=1: переход к 3 все кон

Бейсик-программа.

CLS 10 V=0 20 B=0 30 A=0 40 F1=NOT V AND B OR V AND NOT A 50 F2=V AND NOT A OR NOT B 60 F3=(NOT V AND B) OR NOT B 70 F=F1 AND F2 AND F3 80 IF F=1 THEN ?" V A B":? V;A;B:END 90 IF A<1 THEN A=1 : GOTO 40 100 IF B<1 THEN B=1 : GOTO 30 110 IF V<1 THEN V=1 : GOTO 20 120 END

Паскаль - программа.

program zadacha6;{Межуева} uses crt; var v,a,b:boolean; function func:boolean; var f:array[1..3] of boolean; begin f[1]:=(not v and b) or (v and not a); f[2]:=(v and not a) or (not b); f[3]:=(not v and b) or (not b); func:=f[1] and f[2] and f[3]; end; procedure ff(i:integer); begin case i of 1:begin v:=false;ff(i+1); v:=true;ff(i+1); end; 2:begin b:=false;ff(i+1); b:=true;ff(i+1); end; 3:begin a:=false;ff(i+1); a:=true;ff(i+1); end; 4:begin if func=true then begin writeln('v b a'); writeln(v,' ',b,' ',a); end; end; end; end; begin ff(1); end.

Четверо друзей - шахматистов перед началом шахматного турнира обсуждали свои возможности на призовые места. Друзья были уверены, что они займут 4 первых места ,но не знали, в какой последовательности. Вот что они говорили: Олег: "Если я займу 1 место, то Леонид-4". Леонид: "Если Сергей не займет 1 место, тогда Олег выйдет на 3 место". Сергей: "У Олега положение в турнирной таблице будет лучше, чем у Павла". Павел: "Могу сказать только, что все мы займем разные места". Предположение друзей целиком оправдались. Кто, какие места занял в шахматном турнире?

Решение. Введем буквенные обозначения: L-Леонид, O-Олег, P-Павел, S - Сергей. Составим уравнения согласно высказываниям друзей:

Ответ. Из полученного выражения выберем первое, т.к. Павел не может быть на четвертом месте, поскольку 4 место уже занято Леонидом. Поэтому Сергей -1 место, Олег -2, Павел - 3, Леонид - 4.

Графическое дерево. Ответом является ветвь 1.

Алгоритм.

алг Задача N 9 (цел F1, F2, F4, F5, F, A, B, T, D, K) арг F1, F2, F4, F5, A, B, T, D, K рез F нач A:=0 2: B:=0 3: T:=0 4: D:=0 5: K:=0 6: F1:=(B ИЛИ T) F2:=(НЕ B) И (НЕ K) F4:=(F1 И (НЕ F2)) ИЛИ ((НЕ F1) И F2) F5:=НЕ F4 F:=(F1) И (F2) И (F5) если F=1 то вывод A, B, T, D, K все если K<1 то K:=1 переход к 6 все если D<1 то D:=1 переход к 5 все если T<1 то T:=1 переход к 4 все если B<1 то B:=1 переход к 3 все если A<1 то A:=1 переход к 2 все кон

Бейсик-программа.

cls 10 o1=0 20 o2=0 30 o3=0 40 p1=0 50 p2=0 60 p3=0 70 L4=0 80 s1=0 90 f1=(not o1 or L4) 100 f2=(s1 or o3) 110 f3=(o1 and not p1)or(not o1 and o2 and not o3 and not p1 and not p2 and not p3) 111 f4=not(o1 and o2): f5=not(p1 and p2): f6=not(o1 and s1) 112 f7=not(o1 and p1): f8=not(o2 and p2): f9=not(o3 and p3): fa=not(o1 and o3) 113 fb=not(o2 and o3): fc=not(p1 and p3): fd=not(p2 and p3) 120 f=f1 and f2 and f3 and f4 and f5 and f6 and f7 and f8 and f9 and fa and fb and fc and fd 130 if f=1 then ?" f ";"o1 ";"o2 ";"o3 ";"p1 ";"p2 ";"p3 ";"L4 ";"s1 ":?f;o1;o2;o3;p1;p2;p3;L4;s1 140 if s1<1 then s1=1:goto 90 150 if L4<1 then L4=1:goto 80 160 if p3<1 then p3=1:goto 70 170 if p2<1 then p2=1:goto 60 180 if p1<1 then p1=1:goto 50 190 if o3<1 then o3=1:goto 40 200 if o2<1 then o2=1:goto 30 210 if o1<1 then o1=1:goto 20 220 end

Паскаль - программа.

program log8;{Мелехин} uses crt; var o1,o2,o3,p1,p2,p3,l4,s1:boolean; function func{(a1,a2,a3,b1,b2,c1)}:boolean; var f:array[1..13] of boolean; begin f[1]:=not o1 or l4; f[2]:=s1 or o3; f[3]:=(o1 and not p1) or (not o1 and o2 and not o3 and not p1 and not p2 and not p3); f[4]:=not(o1 and o2); f[5]:=not(p1 and p2); f[6]:=not(o1 and s1); f[7]:=not(o1 and p1); f[8]:=not(o2 and p2); f[9]:=not(o3 and p3); f[10]:=not(o1 and o3); f[11]:=not(o2 and o3); f[12]:=not(p1 and p3); f[13]:=not(p2 and p3); func:=f[1] and f[2] and f[3] and f[4] and f[5] and f[6] and f[7] and f[8] and f[9] and f[10] and f[11] and f[12] and f[13]; end; procedure ff(i:integer); begin case i of 1:begin o1:=false;ff(i+1); o1:=true;ff(i+1); end; 2:begin o2:=false;ff(i+1); o2:=true;ff(i+1); end; 3:begin o3:=false;ff(i+1); o3:=true;ff(i+1); end; 4:begin p1:=false;ff(i+1); p1:=true;ff(i+1); end; 5:begin p2:=false;ff(i+1); p2:=true;ff(i+1); end; 6:begin p3:=false;ff(i+1); p3:=true;ff(i+1); end; 7:begin l4:=false;ff(i+1); l4:=true;ff(i+1); end; 8:begin s1:=false;ff(i+1); s1:=true;ff(i+1); end; 9:begin if func{(a1,a2,a3,b1,b2,c1)}=true then begin clrscr; writeln(' f o1 o2 o3 p1 p2 p3 l4 s1'); writeln(func,' ',o1,' ',o2,' ',o3,' ',p1,' ',p2,' ',p3,' ',l4,' ',s1); end; end; end; end; begin ff(1); end.

Задача №7.( Черкасова Вера, Абрамова Светлана )

Один из пяти братьев разбил окно. -Это мог сделать только или Витя, или Толя, - сказал Андрей. -Я окно не разбивал, - возразил Витя, - и Коля тоже. -Вы оба говорите неправду, - заявил Толя. -Нет, Толя, один из них сказал правду, а другой сказал неправду, - возразил Дима. -Ты, Дима, неправ, - вмешался Коля. Их отец, которому, конечно, можно доверять, уверен, что трое братьев сказали правду. Кто разбил окно?

Решение. Введем буквенные обозначения: A - Андрей, W - Витя, T - Толя, D - Дима, K - Коля. Составим уравнения согласно высказываниям братьев:

Высказывание Димы упрощено путем отнесения отрицания к элементарным высказываниям, раскрытием скобок, применением свойства поглощения, а также за счет того, что высказывание (T K) ложное, т.к. по условию задачи окно разбил один из братьев.

По условию задачи трое братьев сказали правду. Образуем из формул A,B,T,D,K конъюнкции, беря в каждую конъюнкцию по 3 формулы: A B T, A B D, A B K, A T D, A T K, A D K, B T D, B T K, B D K, T D K. Т.к. A и T, B и T, D и T в конъюнкции дают противоречия, то из десяти сочетаний оставляем только два: A B D и A B K. Но конъюнкция A B D дает противоречие. Следовательно, истинной является A B K.

Ответ: Стекло разбил Толя.

Алгоритм.

алг Задача №9 (цел F1, F2, F4, F5, F, A, B, T, D, K) арг F1, F2, F4, F5, A, B, T, D, K рез F нач A:=0 2: B:=0 3: T:=0 4: D:=0 5: K:=0 6: F1:=(B ИЛИ T) F2:=(НЕ B) И (НЕ K) F4:=(F1 И (НЕ F2)) ИЛИ ((НЕ F1) И F2) F5:=НЕ F4 F:=(F1) И (F2) И (F5) если F=1 то вывод A, B, T, D, K все если K<1 то K:=1: переход к 6 все если D<1 то D:=1: переход к 5 все если T<1 то T:=1: переход к 4 все если B<1 то B:=1: переход к 3 все если A<1 то A:=1: переход к 2 все кон

Графический способ решения задачи.

Бейсик-программа.

CLS 10 A=0 20 B=0 30 T=0 40 D=0 50 K=0 60 f1=(B OR T) 70 f2=(NOT B) AND (NOT K) 100 f5=NOT F4 103 F8=(F1 AND F2 AND F5) 119 F=f1 AND f2 AND F5 120 IF F=1 THEN ?" A ";" B ";" T ";" D ";" K ":? A;B;T;D;K:END 130 IF K<1 THEN K=1 : GOTO 60 140 IF D<1 THEN D=1 : GOTO 50 150 IF T<1 THEN T=1 : GOTO 40 160 IF B<1 THEN B=1 : GOTO 30 170 IF A<1 THEN A=1 : GOTO 20 180 END

Паскаль-программа.

program a9; {Абрамова} uses crt; var a,b,d,t,k:boolean; function func:boolean; var f:array[1..4] of boolean; begin f[1]:=b or t; f[2]:=not b and not k; f[3]:=(f[1] and (not f[2])) or ((not f[1]) and f[2]); f[4]:=not f[3]; func:=f[1] and f[2] and f[4]; end; procedure ff(i:integer); begin case i of 1:begin a:=false;ff(i+1); a:=true;ff(i+1); end; 2:begin b:=false;ff(i+1); b:=true;ff(i+1); end; 3:begin t:=false;ff(i+1); t:=true;ff(i+1); end; 4:begin d:=false;ff(i+1); d:=true;ff(i+1); end; 5:begin k:=false;ff(i+1); k:=true;ff(i+1); end; 6:begin if func=true then begin writeln(' a b t d k '); writeln(a,' ',b,' ',t,' ',d,' ',k,' ');halt; end; end; end; end; begin clrscr; ff(1); end.

ЗАДАЧА №8. (Власова Светлана, Рынгач Марина)

Нужно для 4 дежурных - Антипова, Климова, Маркова и Лебедева - составить график дежурств на агитпункте с соблюдением следующих условий:

1. Если Лебедев не будет дежурить в понедельник, то в понедельник согласен дежурить Климов.

2. Ecли Климов не сможет дежурить ни в понедельник, ни в четверг, то Антипов будет дежурить в понедельник.

3. Если Марков не сможет дежурить в четверг, то Климов будет дежурить в среду.

4. Если Лебедев придет дежурить во вторник ,то Климов не будет дежурить в понедельник .

5. Если Антипов не сможет дежурить в понедельник, то Марков не сможет дежурить во вторник.

Каким должен быть график дежурств ?

Решение. Введем обозначения: L- Лебедев, K - Климов, A - Антипов, M - Марков. Цифры означают 1 - Понедельник,2 - Вторник,3 - Среда, 4 -Четверг. Согласно условиям задачи составим систему логических уравнений:

То обстоятельство, что один и тот же человек не может дежурить дважды и в один день не могут дежурить два человека зададим формулами:

L2 * L1 0 (6) К1* L1 0 (7) К1* А1 0 (8) К4* M4 0 (9) L1 А1 0 (10)

Для решения системы уравнений умножим сначала уравнение (1) на уравнение (2):

Ответ. Из полученного выражения следует, что Климов дежурит в понедельник, Антипов - во Вторник, Лебедев - в среду, Марков - в Четверг.

Алгоритм.

алг Задача 12 (цел F1, F2, F3, F4, F5, F6, F7, F8, F9, Fa, Fb, F, K1, K3, K4, L2, L1, M4, A1) арг F1, F2, F3, F4, F5, F6, F7, F8, F9, Fa, Fb рез F, K1, K3, K4, L2, L1, M4, A1 нач 15: М2:=0 20: К1:=0 30: К3:=0 40: К4:=0 50: L2:=0 60: L1:=0 70: M4:=0 80: A1:=0 90: F1:=( L1 или К1 ) F2:=( K1 или К4 ) или А1 F3:=( M4 или К3 ) F4:=( не L2) или не К1 F5:=( A1 или не М2 ) F6:=( не ( К1 и К3 )) и ( не (К3 и К4)) и (не (К1 и К4)) F7:= не ( L2 и L1) F8:= не ( К1 и L1 ) F9:= не ( К1 и А1 ) Fa:= не ( К4 и М4 ) Fb:= не ( L1 и А1) F:=F1 и F2 и F3 и F4 и F5 и F6 и F7 и F8 и F9 и Fa и Fb если F=1 то вывод F, K1, K3, K4, L2, L1, M4, A1 все если А1>1 то А1:=1: перейти к 90 все если М4<1 то М4:=1: перейти к 80 все если L1<1 то L1:=1: перейти к 70 все если L2<1 то L2:=1: перейти к 60 все если К4<1 то К4:=1: перейти к 50 все если К3<1 то К3:=1: перейти к 40 все если К1<1 то К1:=1: перейти к 30 все если М2<1 то М2:=1: перейти к 20 все кон

Бейсик-программа.

10 CLS 20 K1=0 30 K3=0 40 K4=0 50 L2=0 60 L1=0 70 M4=0 80 A1=0 90 F1=(l1 OR K1 ) 100 F2=( K1 or K4) or A1 110 F3=(m4 OR K3) 120 F4=( NOT l2) OR not K1 130 F5=(a1 or not m2) 140 f6=(not(k1 and k3)) and (not(k3 and k4)) and (not(k1 and k4)) 150 F7= NOT(L2 AND L1) 160 F8= NOT(K1 AND L1) 170 F9= NOT(K1 AND A1) 180 Fa= NOT(K4 AND M4) 190 Fb= NOT(L1 AND A1) 200 F=F1 AND F2 ANd F3 AND F4 AND F5 AND f6 and F7 AND F8 AND F9 AND fa and fb 210 IF F=1 THEN ?" F ";"K1 ";"K3 ";"K4 ";"L2 ";"L1 ";"M4 ";"A1 ":?F;K1;K3;K4;L2;L1;M4;A1 220 IF A1<1 THEN A1=1:GOTO 90 230 IF M4<1 THEN M4=1:GOTO 80 240 IF L1<1 THEN L1=1:GOTO 70 250 IF L2<1 THEN L2=1:GOTO 60 260 IF K4<1 THEN K4=1:GOTO 50 270 IF K3<1 THEN K3=1:GOTO 40 280 IF K1<1 THEN K1=1:GOTO 30 290 END

Паскаль-программа.

PROGRAM LOG12;{ВЛАСОВА ЗАДАЧА 12} uses crt; var M2,K1,K3,K4,L2,L1,M4,A1:boolean; function func:boolean; var f:array[1..11] of boolean; begin f[1]:=(L1 OR K1); f[2]:=(K1 or K4)OR A1; f[3]:=(M4 OR K3); f[4]:=(not L2) or (not K1); f[5]:=(a1 OR NOT M2); f[6]:=not(K1 and K3) AND (NOT(K3 AND K4)) AND (NOT(K1 AND K4)); f[7]:=not(L2 and L1); f[8]:=not(K1 and L1); f[9]:=not(K1 and A1); f[10]:=not(K4 and M4); f[11]:=not(L1 and A1); func:=f[1] and f[2] and f[3] and f[4] and f[5] and f[6] and f[7] and f[8] and f[9] and f[10] and f[11] ; end; procedure ff(i:integer); begin case i of 1:begin M2:=false;ff(i+1); M2:=true;ff(i+1); end; 2:begin K1:=false;ff(i+1); K1:=true;ff(i+1); end; 3:begin K3:=false;ff(i+1); K3:=true;ff(i+1); end; 4:begin K4:=false;ff(i+1); K4:=true;ff(i+1); end; 5:begin L2:=false;ff(i+1); L2:=true;ff(i+1); end; 6:begin L1:=false;ff(i+1); L1:=true;ff(i+1); end; 7:begin M4:=false;ff(i+1); M4:=true;ff(i+1); end; 8:begin A1:=false;ff(i+1); A1:=true;ff(i+1); end; 9:begin if func=true then begin writeln('K1 K3 K4 L2 L1 M4 A1'); writeln(K1,' ',K3,' ',K4,' ',L2,' ',L1,' ',M4,' ',A1); end; end; end; end; begin CLRSCR; ff(1); end.

ЗАДАЧА №9. (Федеряшин Дмитрий, Cилин Михаил, Гусев Олег).

На ледяном поле 5 хоккеистов: Ольховский, Малышев, Белов, Таманин, Лавров - штурмовали ворота. Раздался свисток судьи. "Удаляет двух", - подумали спортсмены. "Без Малышева или Ольховского я не останусь на поле", - сказал Таманин. "Я тоже, "- сказал Лавров. "Удаляют либо меня с Беловым, либо Таманина с Лавровым", - сказал Малышев. Когда судья объявил о своем решении все оказались правы и кроме того Ольховский и Белов не остались вместе на поле. Кто остался на поле ? Решение. Введем буквенные обозначения: O - Ольховский, M - Малышев, B - Белов, T - Таманин, L - Лавров. Высказывания каждого хоккеиста можно задать формулами :

Для решения системы логических уравнений умножим уравнение (1) на уравнение (2):

Полученное выражение (4) умножим на уравнение (3): Из полученного выражения (5) следует, что на поле остались Ольховский, Таманин, Лавров.

Графическое дерево. Проанализировав все ветви графического дерева, можно сделать заключение, что единственно правильным решением является ветвь 5.

Алгоритм.

алг Задача N13(цел F1,F2,F3,T,O,M,L,B,F) арг F1,F2,F3,T,O,M,L,B рез F нач 1: T:=0 2: O:=0 3: M:=0 4: L:=0 5: B:=0 6: F1:=(M и Т) или (О и Т) F2:=(М и L) или (О и L) F3:=(не М и не В) или (не Т и не L) F:=F1 и F2 и F3 если F=1 то вывод F,T,O,M,B,L все если В<1 то B:=1: переход к 6 все если L<1 то L:=1:переход к 5 если М<1 то М:=1:переход к 4 все если О<0 то О:=1:переход к 3 все если Т<1 то Т:=1:переход к 2 все кон

Бейсик-программа.

CLS 10 T=0 20 O=0 30 M=0 40 L=0 50 B=0 60 F1=(M AND T) OR (O AND T) 70 F2=(M AND L) OR (O AND L) 80 F3=(NOT M AND NOT B) OR (NOT T AND NOT L) 90 F=F1 AND F2 AND F3 100 IF F=1 THEN ?" F ";" T ";" O ";" M ";" L ";" B ":?F;T;O;M;L;B 110 IF B<1 THEN B=1: GOTO 60 120 IF L<1 THEN L=1: GOTO 50 130 IF M<1 THEN M=1: GOTO 40 140 IF O<1 THEN O=1: GOTO 30 150 IF T<1 THEN T=1: GOTO 20 160 END

Паскаль-программа.

program nhl3;{СИЛИН & ФЕДЕРЯШИН} uses crt; var t,o,m,b,l:boolean; function func:boolean; var f:array[1..3] of boolean; begin f[1]:=(m and t) or (o and t); f[2]:=(m and l) or (o and l); f[3]:=(not m and not b) or (not t and not l); func:=f[1] and f[2] and f[3]; end; procedure ff(i:integer); begin case i of 1:begin t:=false;ff(i+1); t:=true;ff(i+1); end; 2:begin o:=false;ff(i+1); o:=true;ff(i+1); end; 3:begin m:=false;ff(i+1); m:=true;ff(i+1); end; 4:begin l:=false;ff(i+1); l:=true;ff(i+1); end; 5:begin b:=false;ff(i+1); b:=true;ff(i+1); end; 6:begin if func=true then begin writeln(' f t o m l b '); writeln(func,' ',t,' ',o,' ',m,' ',l,' ',b); end; end; end; end; begin ff(1); end.