Міністерство освіти Республіки Білорусь
Установа освіти
"Гомельський державний університет ім.Ф. Скорини"
Математичний факультет
Кафедра МПУ
Реферат
Алгебра висловлювань на уроках інформатики
Виконавець:
Студентка групи М-42
Ларченко А.В.
Науковий керівник:
Канд. фіз-мат. наук, доцент
Звягіна Т.М.
Гомель 2006
Зміст
Введення
Завдання
Завдання для самостійного вирішення
Висновок
Використана література
Цікавим, перспективним напрямком є аналіз та вирішення логічних завдань за допомогою ЕОМ. Мета, яка переслідується при використанні комп'ютера при вирішенні логічних завдань наступна - розвиток в учнів алгоритмічного підходу до вирішення логічних завдань, а також формування уявлень про інформаційній картині світу, практичне освоєння комп'ютера як інструменту діяльності. У результаті має сформуватися вміння бачити інформаційну сутність світу, розпізнавати та аналізувати з логічної точки зору інформаційні процеси.
Зауваження: у більшості версій мови Бейсік немає змінних логічного типу. Тому, при виведенні змінних логічного типу рекомендується ставити знак мінус перед ім'ям змінної.
Рішення задачі на Паскалі:
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. Bas,
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 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. Фізик може вести другого або третього пару.
3. Хімік не може вести 2-у пару, а може 1 або третьою пару.
Учні вимагають, щоб не було здвоєних пар з одного предмета.
Рішення: Введемо позначення 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
Третє З двох показань одне істинно X3 = X1 OR X2
Четвертий Показання третього свідка брехня. 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 нічого не додають для вирішення завдання.
Перекласти на мову алгебри логіки наступний вислів: "Якщо буде сонячна погода, то хлопці підуть на пляж, а якщо буде похмура погода, то хлопці підуть в кіно"
Завдання № 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 "Уроки логіки"
На питання, хто з трьох учнів вивчав логіку, був отриманий наступний відповідь:
Якщо вивчав перший, то вивчав і другий
Але не вірно, що якщо вивчав третій, то вивчав і другий.
Хто з учнів вивчав логіку?
2. Гохман А.В. та ін "Збірник задач з математичної логіки і алгебри множин", видавництво Саратовського Університету, 1969р.
3. Гусєв В.В. Основи імпульсної техніки. М. Радянське радіо, 1975
4. Касаткін В.М. "Інформація, алгоритми, ЕОМ", М. Освіта, 1991р.
5. Машовця В.А. Вступні іспити з інформатики / / Інформатика. 1997, № 13
6. Орлов В.О. Про вступні іспити з інформатики / / Інформатика, 1997, № 15
7. Яснева Г.Г. Логічні основи ЕОМ / / Інформатика та освіта, 1998, № 2
8. Лискова В.Ю., Ракітіна Є.А. Логіка в інформатиці, М. Інформатика та освіта 1999
9. Шауцкова Л.З. "Рішення логічних задач засобами алгебри логіки", газета Інформатика 1999, № 5.
Установа освіти
"Гомельський державний університет ім.Ф. Скорини"
Математичний факультет
Кафедра МПУ
Реферат
Алгебра висловлювань на уроках інформатики
Виконавець:
Студентка групи М-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. Bas,
3. pas)
CLS
PRINT "x y"
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.
------ 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. Фізик може вести другого або третього пару.
3. Хімік не може вести 2-у пару, а може 1 або третьою пару.
Учні вимагають, щоб не було здвоєних пар з одного предмета.
Рішення: Введемо позначення 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
Третє З двох показань одне істинно X3 = X1 OR X2
Четвертий Показання третього свідка брехня. 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
Увага Андрія, Дениса і Марата залучив промчав повз них автомобіль.
Це англійська машина марки "Феррарі", - сказав Андрій.
Ні, машина італійська, марки "Понтіак", - заперечив Денис.
Це "Сааб", і зроблений він не в Англії, - сказав Марат.
Опинившись поруч знавець автомобілів сказав, що кожен з них має рацію тільки в одному з двох висловлених припущень.
Який ж марки цей автомобіль і в якій країні виготовлено?
Завдання № 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.