Алгебра высказываний на уроках информатики

БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Алгебра высказываний на уроках информатики

Алгебра высказываний на уроках информатики

27

Министерство образования Республики Беларусь

Учреждение образования

"Гомельский государственный университет им.Ф. Скорины"

Математический факультет

Кафедра МПУ

Реферат

Алгебра высказываний на уроках информатики

Исполнитель:

Студентка группы М-42

Ларченко А.В.

Научный руководитель:

Канд. физ-мат. наук, доцент

Звягина Т.М.

Гомель 2006

Содержание

• Введение
• Задачи
• Задачи для самостоятельного решения
• Заключение
• Используемая литература

------ 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 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. Вострикова З.П. и др. "Программирование на языке "БЕЙСИК" для персональных ЭВМ". Машиностроение, 1993г.

2. Гохман А.В. и др. "Сборник задач по математической логике и алгебры множеств", издательство Саратовского Университета, 1969г.

3. Гусев В.В. Основы импульсной техники. М. Советское радио, 1975

4. Касаткин В.Н. "Информация, алгоритмы, ЭВМ", М. Просвещение, 1991г.

5. Машовцев В.А. Вступительные экзамены по информатике // Информатика. 1997, №13

6. Орлов В.А. О вступительных экзаменах по информатике // Информатика, 1997, №15

7. Яснева Г.Г. Логические основы ЭВМ // Информатика и образование, 1998, №2

8. Лыскова В.Ю., Ракитина Е.А. Логика в информатике, М. Информатика и образование 1999

9. Шауцкова Л.З. “Решение логических задач средствами алгебры логики”, газета Информатика 1999, №5.