Алгебра высказываний на уроках информатики
/>
№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 c: =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;
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;
end;
readkey;
end.
Ответ: Дима, Юра, Федя, Гриша
Обратите внимание, что х11 и х12 ничего не добавляют для решения задачи.
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
Задача №1
Перевести на язык алгебры логики следующее высказывание: “Если будет солнечная погода, то ребята пойдут на пляж, а если будет пасмурная погода, то ребята пойдут в кино"
Задача №2
Найдите отрицание высказывания: “Если урок будет интересным, то никто из учеников - Миша, Вика, света - не будет разговаривать”.
Задача №3
Внимание Андрея, Дениса и Марата привлёк промчавшийся мимо них автомобиль.
Это английская машина марки “Феррари", - сказал Андрей.
Нет, машина итальянская, марки “Понтиак", - возразил Денис.
Это “Сааб", и сделан он не в Англии, - сказал Марат.
Оказавшись рядом знаток автомобилей сказал, что каждый из них прав только в одном из двух высказанных предположений.
Какой же марки этот автомобиль и в какой стране изготовлен
| |  скачать работу |
Алгебра высказываний на уроках информатики |
