Алгебра высказываний на уроках информатики
Министерство образования Республики
Беларусь
Учреждение образования
"Гомельский государственный
университет им.Ф. Скорины"
Математический факультет
Кафедра МПУ
Реферат
Алгебра высказываний на уроках
информатики
Исполнитель:
Студентка группы М-42
Ларченко А.В.
Научный руководитель:
Канд. физ-мат. наук, доцент
Звягина Т.М.
Гомель 2006
Содержание
Введение
Задачи
Задачи для самостоятельного решения
Заключение
Используемая литература
Введение
Цель познания в науке в науке и повседневной жизни - получение истинных
знаний и полноценное использование их в практической деятельности. Знания
формальной логики помогает предвидеть события и лучшим способом планировать
деятельность, максимально предусматривать возможные последствия, выдвигать
различные гипотезы, эффективней обучаться. Учащимся логика поможет в процессе
овладения ими многообразной информацией, с которой они встретятся при изучении
различных наук. В ходе дальнейшего самообразования - логика, знания логики
помогут отделять главное от второстепенного, критически воспринимать различные
определения и классификации разнообразных понятий и явлений, подбирать формы
доказательства своих истинных суждений и опровергать ложные.
Интересным, перспективным направлением является анализ и решение логических
задач с помощью ЭВМ. Цель, которая преследуется при использовании компьютера
при решении логических задач следующая - развитие у учащихся алгоритмического
подхода к решению логических задач, а также формирование представлений о
информационной картине мира, практическое освоение компьютера как инструмента
деятельности. В результате должно сформироваться умение видеть информационную
сущность мира, распознавать и анализировать с логической точки зрения
информационные процессы.
Задачи
На компьютере легко получить таблицу истинности некоторого сложного
выражения, к примеру X= (A OR B) AND A AND B
Замечание: в большинстве версий языка Бейсик нет переменных логического
типа. Поэтому, при выводе переменных логического типа рекомендуется ставить
знак минус перед именем переменной.
Решение задачи на Паскале:
uses crt;
var a,b,x: boolean;
Begin
clrscr;
for a: =false to true do begin
for b: =false to true do begin
x: = (A or B) and A and B;
write (x: 10);
end;
end;
readkey;
end.
а также проверить следующие тождества:
NOT (NOT A) = A (закон двойного отрицания).
NOT (A AND NOT A) = 1 (закон отрицания противоречия).
A OR NOT A =1 (закон исключенного третьего).
Решение для первого тождества: (2. bas,
2. pas)
Решение на Паскале:
uses crt;
var a: boolean;
Begin
clrscr;
WRITELN ('not (not a) ': 12,'a': 7);
writeln ('---------------------');
for a: =false to true do
writeln (not (not a): 10,a: 10);
readkey;
end.
Доказательство проводим с помощью таблицы истинности. Как видно из
решения таблицы истинности для выражений стоящих по разные стороны от знака
равенства совпадают, следовательно можно утверждать что тождества верное.
Кроме того, с помощью компьютера можно упростить следующие выражения:
1. A IMP NOT A (NOT A)
2. A EQV NOT A (0)
3. (A IMP A) IMP A (A)
4. NOT A IMP (A IMP B) (1)
5. A IMP (A IMP B) (A IMP B)
6. A IMP (B IMP A) (1)
7. ( (A IMP B) IMP A) IMP B) (A IMP B)
8. (A EQV B) IMP (A IMP B) (1)
9. (A IMP B) IMP (B IMP A) (B IMP A)
10. (NOT A IMP B) IMP (NOT B IMP A) (1)
Как видно из таблиц истинности, многие выражения достаточно легко
сводятся к более простым.
Обладая всего лишь начальными навыками алгоритмического языка можно также
использовать компьютер для решения логических уравнений: Найти X,Y из следующих
уравнений:
(1 IMP
X) IMP Y=0 Отв: (x=1 y=0)
X OR Y = NOT X (x=0, y=1)
3. pas)
CLS
PRINT " x y"
PRINT
FOR x = 0 TO - 1 STEP - 1
FOR y = 0 TO - 1 STEP - 1
IF (x OR y) = (NOT (x)) THEN PRINT - x; - y
NEXT
NEXT
Замечание: в языке Паскаль для решения задач сначала следует выразить операции
следования и эквивалентности через операции OR и AND. Так операция следования
может быть записана следующим образом a IMP b = NOT (a) OR b), а операция
эквивалентности как a EQV b = (a OR (NOT b)) AND ( (NOT a) OR b) или следующим образом
a EQV b = (a AND b) OR ( (NOT a) AND (NOT b)).
Решение на Паскале:
uses crt;
var y,x, imp,a: boolean;
Begin
clrscr;
WRITELN ('x': 10,'y': 10);
writeln;
for x: =false to true do
begin
for y: =false to true do
begin
if not (not (true) or x) or y = false
then writeln (x: 10,y: 10);
end;
end;
readkey;
end.
Следует отметить то, что при решении на компьютере у учащихся постоянно
присутствует таблица истинности основных логических операций на компьютере, и,
к примеру, проверка формул на тавтологии, а также проверка основных логических
законов превращается в некоторое самостоятельное “исследование" основных
операций логики. Учитывая то, что доказательства законов явно не приводятся,
представляется возможным говорить о том, что учащимися познан новый метод доказательства,
которое приводится с помощью компьютера.
При рассмотрении темы: “Арифметические и логические основы ЭВМ"
можно предложить рассмотреть применение алгебры высказываний в
релейно-контактных схемах.
№4. Комитет из трех человек решил применить электрическую схему для
регистрации тайного голосования простым большинством голосов. Построить такую
схему, при использовании которой голосующий нажимал бы на кнопку, причем в
случае принятия решения загоралась бы сигнальная лампочка.
Используя операции конъюнкции и дизъюнкции получим сложное высказывание
удовлетворяющее условию задачи. Х= (A and B) OR (A and C) OR (B and C)
(4. bas)
CLS
FOR A=-1 TO 0
FOR B=-1 TO 0
FOR C=-1 TO 0
X= (A AND B) OR (A AND C) OR (B AND C)
PRINT - A; - B; - C,-X
NEXT
NEXT
NEXT
Решение задачи на Паскале: (4. pas)
uses crt;
var a,b,c,x: boolean;
Begin
clrscr;
WRITELN ('a': 10,'b': 10,'c': 10,'x': 10);
writeln;
for a: =false to true do begin
for b: =false to true do begin
x: = (A and B) or (A and c) or (B and C); writeln (a: 10,b:
10,c: 10,x: 10);
end;
end;
readkey;
end.
------ A ---- B ------
Схема выглядит так ------ A ---- C ------
------ B ---- C ------
Рассмотренные выше решения задач с помощью компьютера, призваны помочь
учащимся использовать компьютер, при прохождении темы, связанной с
рассмотрением основ алгебры логики. Цель, которая преследуется при
использовании компьютера для рассмотрения основных понятий логики, правил
построения логических выражений и логических схем, теорем алгебры логики и
приемам упрощения логического выражения следующая - учащийся представляет себе
компьютер как инструмент, который помогает ему решать задачи логического плана,
таким образом, расширяется поле применения компьютера. При этом компьютер
выступает теперь не только как объект изучения, но и как средство, которое
может помочь при решении ряда задач. Развивая вышесказанное, хотелось бы
рассмотреть еще одно применение компьютера при решении логических задач. Но
сначала следует ознакомиться с действиями, которые необходимо предпринять для решения
логической задачи на компьютере:
Изучить условие задачи.
Обозначить используемые высказывания символами.
Используя логические связи составить логическое выражение для всех
требований задачи.
Вычислить все значения этого логического выражения.
Проверить полученное решение по условию задачи.
№5: в соревнованиях по гимнастике участвуют Алла, Валя, Сима, Даша.
Болельщики высказали предположения о возможных победителях.
1) первой будет Сима, Валя второй,
2) второй будет Сима, Даша - третьей,
3) Алла будет второй, Даша - четвертой.
По окончании соревнований оказалось, что в каждом из предположений только
одно из высказываний истинно, другое ложно. Какое место на соревнованиях заняла
каждая из девушек, если все они оказались на разных местах?
Обозначим высказывания буквами соответственно A, B, C, D, E, F.
Так как только одно из высказываний истинно, то имеем исключающую
дизъюнкцию, которая будет истинна:
A XORB, C XOR D, E XOR F
Кроме того, ложными будут высказывания:
A AND C, B AND C, D AND F, B AND E, C AND E
а, следовательно, истинными
NOT (A AND C) NOT (B AND C) NOT (D AND F) NOT (B AND E) NOT
(C AND E)
Соединяя первую группу истинных высказываний в Х1, а вторую в Х2 получим
Х=Х1*Х2. Получив таблицу истинности, решим
Решение задачи на Паскале: (5. pas)
Uses crt;
Var a,b,c,d,e,f: boolean;
x1,x2,x: boolean;
Begin
clrscr;
writeln ('a': 10,'b': 10,'c': 10,'d': 10,'e': 10,'f': 10);
for a: =false to true do begin
for b: =false to true do begin
for c: =false to true do begin
for d: =false to true do begin
for e: =false to true do begin
for f: =false to true do begin
x1: = (a xor b) and (c xor d) and (e xor f);
x2: = (not (a and c)) and (not (b and c)) and (not (d and f))
and (not (b and e)) and (not (c and e));
x: =x1 and x2;
if x<>false then begin
writeln; write (a: 10,b: 10,c: 10,d: 10,e: 10,f: 10);
end;
end;
end;
end;
end;
end;
end;
readkey;
end.
Ответ:
1 0 0 1 1 0 (0 - false, 1 - true)
№6: Алеша, Боря и Гриша нашли в земле сосуд. Рассматривая удивительную
находку, каждый высказал предположение:
Алеша: "Это сосуд греческий и изготовлен в 5 веке".
Борис: "Это сосуд финикийский и изготовлен в 3 веке".
Гриша: "Это сосуд не греческий и изготовлен в 4 веке".
Учитель истории сказал ребятам, что каждый из них прав только в одном
предположении. Где и в каком веке изготовлен сосуд.
Решение:
Вданной задачи примем следующие обозначения:
G -
это сосуд греческий.
F -
это сосуд финикийский.
P -
изготовлен в 5 веке.
T -
изготовлен в 3 веке.
Q -
изготовлен в 4 веке.
Со слов учителя следует, что каждый мальчик прав только в одном
высказывании. Следовательно для Алеши либо G=-1 либо P=-1,
т.е. G XOR P=-1Аналогично: F XOR T =-1
NOT G XOR Q =-1
Но это недостаточно, следует учесть, что ложными будут высказывания:
F*G=0 P*T=0 P*Q=0 T*Q=0
Или тоже самое:
NOT (F AND G) =-1, NOT (P AND T) =-1, NOT (P AND Q) =-1, NOT
(T AND Q) =-1
Если все истинные высказывания логически перемножить, то получим сложное
высказывание, в котором сведено все, что говориться о сосуде:
X1= (G XOR P) AND (F XOR T) AND (NOT G XOR Q)
X2=NOT (F AND G) AND NOT (P AND T) AND NOT (P AND Q) AND NOT
(T AND Q)
X=X1 AND X2
Ответ: 0 1 1 0 0.
№7: На экзамене преподаватель предлагает студентам определить какие из
пяти утверждений истинны, а какие ложны. Студент знает, что всегда
преподаватель дает истинных утверждений больше, чем ложных, и никогда не задает
подряд три вопроса, требующих одинакового ответа. Из содержания первого и
последнего утверждения ему ясно, что ответы на них должны быть
противоположными. Единственный вопрос на который он знает ответ - второй (лож, истинна?)
Это уже гарантирует правильные ответы на все вопросы. Какими должны быть эти
ответы?
Решение задачи на Паскале: (7. pas)
Uses crt;
Var a,b,c,d,e: boolean;
x1,x2,x3,x4,x5,x6,x7,x8,x: boolean;
Begin
clrscr;
writeln ('a': 10,'b': 10,'c': 10,'d': 10,'e': 10);
for a: =false to true do begin
for b: =false to true do begin
for d: =false to true do begin
for e: =false to true do begin
x1: = not (a AND b AND c) AND NOT (NOT a AND NOT b AND NOT
c);
x2: = NOT (b AND c AND d) AND NOT (NOT b AND NOT c AND NOT
d);
x3: = NOT (c AND d AND e) AND NOT (NOT c AND NOT d AND NOT
e);
x4: = (a AND b AND c) OR (a AND b AND d) OR (a AND b AND e);
x5: = (a AND c AND d) OR (a AND c AND e) OR (a AND d AND e);
x6: = (b AND c AND d) OR (b AND c AND e) OR (b AND d AND e);
x7: = (c AND d AND e);
x8: = a XOR e;
x: = x1 AND x2 AND x3 AND (x4 OR x5 OR x6 OR x7) AND x8;
if x<>false then
begin
writeln;
write (a: 10,b: 10,c: 10,d: 10,e: 10);
end;
end;
end;
end;
end;
end;
readkey;
end.
Ответы:
0 1 0 1 1
0 1 1 0 1
1 0 1 1 0!!! (2 ложь)
1 1 0 1 0
№8: Упрощенный план в институте содержит 3 пары лекций в день. При этом:
1. Математик настаивает, чтобы его лекции не были последними.
2. Физик может вести 2-ую или 3-ю пару.
3. Химик не может вести 2-ю пару, а может 1 или 3-ю пару.
Учащиеся требуют, чтобы не было сдвоенных пар по одному предмету.
Решение: Введем обозначения M1, M2, F2,F3,H1, H3 -где символ это название предмета, а цифра номер пары.1. Из
условия видно, что:
X1=M1 OR M2
X2=F2 OR F3
X3=H1 OR H3
X4= NOT (M1 AND M2) AND NOT (F2 AND F3) AND NOT (H1 AND H2)
2. Дополнительные условия, чтобы не было совпадения предметов на одну
пару:
X5=NOT (M1 AND M2) AND NOT (M1 AND H1) AND NOT (F3 AND H3)
AND NOT (M2 AND F2)
Объединяя получим уравнение:
X=X1 AND X2 AND X3 AND X5
Решение задачи на Паскале: (8. pas)
Uses crt;
Var m1,m2,f2,f3,h1,h3: boolean;
x1,x2,x3,x4,x5,x: boolean;
Begin
clrscr;
writeln ('a': 10,'b': 10,'c': 10,'d': 10,'e': 10,'f': 10);
for m1: =false to true do begin
for m2: =false to true do begin
for f2: =false to true do begin
for f3: =false to true do begin
for h1: =false to true do begin
for h3: =false to true do begin
x1: = m1 OR m2;
x2: = f2 OR f3;
x3: = h1 OR h3;
x4: = NOT (m1 AND m2) AND NOT (f2 AND f3) AND NOT (h1 AND
h3);
x5: = NOT (m1 AND m2) AND NOT (m1 AND h1) AND NOT (f3 AND h3)
AND NOT (m2 AND f2);
x: = X1 AND X2 AND X3 AND X4 AND X5;
if x<>false then
begin
writeln;
write (m1: 10,m2: 10,f2: 10,f3: 10,h1: 10,h3: 10);
end;
end;
end;
end;
end;
end;
readkey;
end.
Ответ:
1) 0 1 0 1 1 0 1) мат., физ., хим.
2) 1 0 1 0 0 1 2) хим., мат., физ.
№9: В деле об убийстве имеются два подозреваемых А и В. Допросили четырех
свидетелей. Их показания:
1-го А не виноват X1=A
2-го В не виноват X2=B
3-го Из двух показаний одно истинно X3=X1 OR X2
4-ый Показания 3-го свидетеля ложь. X4=NOT X3
Четвертый свидетель оказался прав. Кто виноват?
Ответ: оба не виноваты, оба виноваты.
№10:
На вопрос кто из A,B,C,D,E играет в шахматы получено 5 ответов.
1. Если А играет, то и В играет. Х1= A IMP B
2. D и E играют оба или один из них играет. X2= D OR E
3. Из В и С только один играет. X3=B XOR C
4. C и D или оба играют или оба не играют. X4= C EQV D
5. Если Е играет, то А и D тоже играют. X5= E IMP (A AND D)
Кто из пятерых играет в шахматы? X=X1 AND X2 AND X3 AND X4 AND X5
Ответ: 0 0 1 1 0
№11: Находчивый комендант.
Во время ремонта общежития комендант был вынужден переселять студентов.
Дело это не простое. Посудите сами. На одну из новых комнат претендовало восемь
человек, а поселить в ней можно было только четверых. Комендант стал
расспрашивать студентов, кто с кем хочет жить. Вот, что он услышал:
АНДРЕЙ согласен на любых соседей.
БОРИС без КОСТИ не переселится. (K IMP B)
КОСТЯ не хочет жить в одной комнат с ВАСИЛИЕМ. (W IMP NOT K)
ВАСИЛИЙ согласен жить с кем угодно.
ДИМА не будет переселяться без ЮРЫ. D AND Q
ФЕДЯ не будет без ГРИШИ жить в одной комнате с ДИМОЙ, а без ДИМЫ не будет
жить в одной комнате с КОСТЕЙ. D IMP (F AND G) К IMP (F AND D)
ГРИША не хочет, чтобы его соседями были и БОРИС и КОСТЯ вместе, кроме
того, он не желает жить в одной комнате ни с АНДРЕЕМ, ни с ВАСИЛИЕМ. G IMP (NOT (B AND K))
GIMP (NOT A)
GIMP (NOT W)
ЮРА даст согласие переехать в новую комнату, если туда же переберутся
либо БОРИС либо ФЕДЯ. Кроме того, ЮРА не будет жить в одной комнате с КОСТЕЙ,
если туда не переедет ГРИША, и не желает жить в одной комнате ни с АНДРЕЕМ, ни
с ВАСИЛИЕМ.
(Q AND
B) XOR (Q AND F) K IMP (Q AND G) (Q AND NOT A) AND (Q AND NOT B)
“Задали мне задачу”, - подумал комендант. Но, в конце концов сумел учесть
все пожелания. Каким образом?
Решение на Паскале: (11. pas)
Uses crt;
Var a,b,k,w,d,q,f,g: boolean;
x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x: boolean;
Begin
clrscr;
writeln ('a': 10,'b': 10,'k': 10,'w': 10,'d': 10,'q': 10,'f':
10,'g': 10);
for a: =false to true do begin
for b: =false to true do begin
for k: =false to true do begin
for w: =false to true do begin
for d: =false to true do begin
for q: =false to true do begin
for f: =false to true do begin
for g: =false to true do begin
x2: = (NOT K OR B) AND (NOT W OR NOT K);
x4: = D AND Q;
x5: = NOT D OR (F AND G);
x6: = NOT K OR (F AND D);
x7: = NOT G OR (NOT (B AND K));
x8: = NOT G OR (NOT A);
x9: = NOT G OR NOT W;
x10: = (Q AND B) XOR (Q AND F);
x11: = NOT K OR (Q AND G);
x12: = (Q AND NOT A) AND (Q AND NOT B);
x: = x2 AND x4 AND x5 AND x6 AND x7 AND x8
AND x9 AND x10 {AND x11 AND x12};
if x<>false then
begin
writeln;
write (a: 10,b: 10,k: 10,w: 10,d: 10,q: 10,f: 10,g: 10);
end;
end;
end;
end;
end;
end;
end;
end;
readkey;
end.
Ответ: Дима, Юра, Федя, Гриша
Обратите внимание, что х11 и х12 ничего не добавляют для решения задачи.
Задачи для самостоятельного решения
Задача №1
Перевести на язык алгебры логики следующее высказывание: “Если будет
солнечная погода, то ребята пойдут на пляж, а если будет пасмурная погода, то
ребята пойдут в кино"
Задача №2
Найдите отрицание высказывания: “Если урок будет интересным, то никто из
учеников - Миша, Вика, света - не будет разговаривать”.
Задача №3
Внимание Андрея, Дениса и Марата привлёк промчавшийся мимо них
автомобиль.
Это английская машина марки “Феррари", - сказал Андрей.
Нет, машина итальянская, марки “Понтиак", - возразил Денис.
Это “Сааб", и сделан он не в Англии, - сказал Марат.
Оказавшись рядом знаток автомобилей сказал, что каждый из них прав только
в одном из двух высказанных предположений.
Какой же марки этот автомобиль и в какой стране изготовлен?
Задача №4
В клуб служебного собаководства на очередную тренировку пришли со своими
собаками Антон, Борис, Пётр, Виктор и Олег. Желая подшутить над новым
инструктором, на его вопрос “Кто же хозяин каждой из собак? ” каждый юноша дал
один правильный и один неправильный ответ:
Антон сказал: “Моя собака - Рекс, а собака Петра - Лайма".
Борис сказал: “Рекс - моя собака, а собака Виктора - Джек".
Петр сказал: ”Собака Виктора - Зевс, а моя - Рекс".
Виктор сказал: “Моя собака - Джек, а собака Олега - Бичо”.
Олег сказал: “ Да, моя собака - Бичо, а собака Бориса - Зевс”.
Кто же на самом деле хозяин каждой из собак?
Задача №5
Трое друзей, болельщиков автогонок “Формула - 1”, спорили о результатах
предстоящего этапа гонок.
Вот увидишь, Шумахер не придёт первым, - сказал Джон. - Первым будет
Хилл.
Да, нет же, победителем будет, как всегда, Шумахер, - воскликнул Ник. - А
об Алези и говорить нечего, ему не быть первым.
Питер, к которому обратился Ник, возмутилс:
Хиллу не видать первого места, а вот Алези пилотирует самую мощную
машину.
По возвращении этапа гонок оказалось, что каждое из двух предположений
двоих друзей подтвердилось, а оба предположения третьего оказались неверными.
Кто выиграл этап гонки?
Задача №6
Некий любитель приключений отправился в кругосветное путешествие на яхте,
оснащённой бортовым компьютером. Его предупредили, что чаще всего выходят из
строя три узла компьютера - a, b, c - и дали необходимые детали для замены. Выяснить какой
именно узел надо заменить, он может по сигнальным лампочкам на контрольной
панели. Лампочек тоже ровно три: x, y, z.
Инструкция по выявлению неисправных узлов такова:
если неисправен хотя бы один из узлов компьютера, то горит по крайне мере
одна из лампочек x, y, z;
если неисправен узел a, но
исправен узел с, то загорается лампочка у;
если неисправен узел с, но исправен узел b, загорается лампочка у, но не загорается лампочка x;
если неисправен узел b, но
исправен узел с, то загораются лампочки х и у или не загорается лампочка х;
если горит лампочка х и при этом либо неисправен узел а, либо все три
узла - а, b, c - исправны, то горит и лампочка у.
В пути компьютер сломался. На контрольной панели загорелась лампочка х.
Тщательно изучив инструкцию, путешественник починил компьютер. Но с этого
момента и до конца плавания его не оставляла тревога. Он понял, что инструкция
несовершенна и есть случаи, когда она ему не поможет.
Какие узлы заменил путешественник? Какие изъяны он обнаружил в
инструкции?
Задача №7
Три свидетеля дали показания, что преступники скрылись с места
преступления:
А) на чёрном “Бьюике”;
Б) на синем “Форде”;
В) не на черном “Крайслере".
Каждый из них в чём -то одном ошибался. На какой машине скрылись
преступники?
Задача №8
Кто из школьников - Андрей, Виктор, Света, Дима - играет в шахматы, а кто
не играет, если известно следующее:
А) если Андрей или Виктор играет, то Света не играет;
Б) если Виктор не играет, играют Света и Дима;
В) Света играет.
Задача №9 “Похитители"
Брауну, Джонсу и Смиту предъявлено обвинение в сооучастии в ограблении
банка. Похитители скрылись на поджидавшем их автомобиле. На следствии Браун
показал, что преступники скрылись на синем “Бьюике", Джонс показал, что
это был черный “Крайслер”, а Смит утверждал, что это был “Форд Мустанг" и
ни в коем случае не синий. Стало известно, что, желая запутать следствие,
каждый из них указал правильно либо только марку, либо только цвет машины.
Какого цвета и какой марки быль автомобиль?
Задача №10 “Происшествие”
Виновник ночного дорожного происшествия скрылся с места аварии.
Первый опрошенный свидетель сказал работникам ГАИ, что это были
“Жигули" и первая цифра номера машины - единица.
Второй свидетель сказал, что машина была марки “Москвич” и номер
начинался с семерки.
Третий свидетель заявил, что машина была иностранная, и номер начинался
не с единицы.
При дальнейшем расследовании выяснилось, что каждый из свидетелей
правильно указал либо марку машины, либо только первую цифру номера.
Какой марки машина, и с какой цифры начинался номер?
Задача №11 “Кто виноват?"
По обвинению в ограблении перед судом предстали Иванов, Петров, Сидоров.
Следствием установлено следующее:
Если Иванов не виновен или Петров невиновен, то Сидоров виновен
Если Иванов не виновен, то Сидоров не виновен.
Задача №12 “Финансовый прогноз”
Три подразделения А, В, С торговой фирмы стремились получить по итогам
года максимальную прибыль. Экономисты высказали следующие предположения:
Если А получит максимальную прибыль, то максимальную прибыль получат так
же В и С.
Либо А и С получат максимальную прибыль одновременно, либо одновременно
не получат.
Для того, чтобы С получило максимальную прибыль, необходимо, чтобы и В
получило максимальную прибыль.
По завершению года оказалось, что только одно из трех предположений
ложно. Какие из названных подразделений получили максимальную прибыль.
Задача №13 “Обмен валюты”
В нарушении правил обмена валюты подозреваются четыре работника банка -
Антипов (А), Борисов (В), Цветков (С) и Дмитриев (Д). Известно, что:
Если А нарушил, то и В нарушил правила обмена валюты
Если В нарушил, то и С нарушил или А не нарушил правила обмена валюты
Если Д не нарушил, то А нарушил, а С не нарушил
Если Д нарушил, то и А нарушил.
Кто из подозреваемых нарушил правила обмена валюты?
Задача №14 “Экзамен"
Перед сдачей вступительных экзаменов в институт Миша предполагал, что:
Если он сдаст математику, то информатику он сдаст только при условии, что
не завалит диктант
Не может быть, чтобы он завалил и диктант, и математику
Достаточное условие завала по информатике - двойка по диктанту.
После сдачи экзаменов оказалось, что из трех высказанных предположений
только одно было ложным. Как Миша сдал экзамены?
Задача №15 “Купание"
В санатории на берегу моря отдыхают отец О, мать М, сын С и две дочери
Д1, Д2. До завтрака члены семьи часто купаются в море, причем известно, что
если отец утром отправляется купаться, то с ним обязательно идут купаться
мать и сын.
Если сын идет купаться, то его сестра Д1 отправляется вместе с ним.
Вторая дочь Д2 купается тогда и только тогда, когда купается мать
Каждое утро купается, по крайней мере, один из родителей.
Если в воскресенье утром купалась лишь одна из дочерей, то кто из членов
семьи в это утро ходил на море?
Задача №16 “5 друзей”
Пятеро друзей решили записаться в кружок любителей логических задач:
Андрей (А), Виктор (В), Николай (Н), Григорий (Г), Дмитрий (Д). Но староста
кружка поставил условие: “Вы должны приходить к нам так, чтобы:
Если А приходит вместе с Д, то Н должен присутствовать обязательно
Если Д отсутствует, то Н должен быть, а В пусть не приходит
А и В не могут одновременно ни присутствовать, ни отсутствовать
Если придет Д, то Г пусть не приходит
Если Н отсутствует, то Д должен присутствовать, но это в том случае, если
не присутствует В, Есле же и В присутствует при отсутствии Н, то Д приходить не
должен, а Г должен прийти"
Сколько раз, и в каком составе друзья смогут прийти на занятия кружка?
Задача №17 “Автоматизированный участок”
На автоматизированном участке цеха стоят 5 станков, действия которых
скоординированы следующем образом:
Если работают первый и третий станки, то четвертый не работает при
условии, что подключен пятый станок.
Если же первый станок подключен без третьего или выключен пятый станок,
то четвертый обязательно подключен.
Если пятый станок работает вместе со вторым При включенным первом станке,
то включен третий станок.
Если выключен второй или пятый станок, то одновременно выключен и
четвертый.
Мы наблюдаем работу первого и четвертого станков. Что можно сказать о
состоянии остальных станков, скрытых за перегородкой?
Можно ли в данной системе остановить для ремонта одновременно третий и
четвертый станки, оставив хотя бы один из остальных станков включенным?
Задача №18 “Комиссар Мегре”
“Вернувшись домой, Мегрэ позвонил на набережную Орферт.
Говорит Мегрэ. Есть новости?
Да шеф. Поступили сообщения от инспекторов.
Торранс установил, что если Франсуа был пьян, то либо Этьен убийца, либо
Франсуа лжет.
Жуссье считает, что или Этьен убийца, или Франсуа не был пьян и убийство
произошло после полуночи.
Инспектор Люка просил передать вам, что если убийство произошло после
полуночи, то либо Этьен убийца, либо Франсуа лжет. Затем звонила …
Все, спасибо. Этого достаточно.
Комиссар положил трубку. Он знал, что трезвый Франсуа никогда не лжет.
Теперь он знал все. Что узнал комиссар?
Задача №19 “Уроки логики”
На вопрос, кто из трех учащихся изучал логику, был получен следующий
ответ:
Если изучал первый, то изучал и второй
Но не верно, что если изучал третий, то изучал и второй.
Кто из учащихся изучал логику?
Заключение
Среди задач, для которых привлекается ЭВМ, немало таких, которые принято
называть логическими. Кто не знает шуточной задачи о перевозке волка, козы и
капусты с одного берега на другой. В этой задачи властвует не арифметика, а
умение рассуждать. В логических задачах исходными данными являются не только
числа, а неожиданные и подчас весьма запутанные суждения. Эти суждения и связи
между ними бывают иногда столь противоречивыми, что они под силу не каждому
математику, а только ЭВМ. Такая область математической логики, как алгебра
высказываний, хорошо освоена в информатике. В настоящее время нет ни одного
языка программирования, который не включал бы в себя основные операции алгебры
высказываний.
Используемая литература
1. Вострикова
З.П. и др. "Программирование на языке "БЕЙСИК" для персональных
ЭВМ". Машиностроение, 1993г.
2. Гохман
А.В. и др. "Сборник задач по математической логике и алгебры
множеств", издательство Саратовского Университета, 1969г.
3. Гусев
В.В. Основы импульсной техники. М. Советское радио, 1975
4. Касаткин
В.Н. "Информация, алгоритмы, ЭВМ", М. Просвещение, 1991г.
5. Машовцев
В.А. Вступительные экзамены по информатике // Информатика. 1997, №13
6. Орлов
В.А. О вступительных экзаменах по информатике // Информатика, 1997, №15
7. Яснева
Г.Г. Логические основы ЭВМ // Информатика и образование, 1998, №2
8. Лыскова
В.Ю., Ракитина Е.А. Логика в информатике, М. Информатика и образование 1999
9. Шауцкова
Л.З. “Решение логических задач средствами алгебры логики”, газета Информатика
1999, №5.