Составление логического уравнения (формулы) и приведение его к нормальной форме

⇐ ПредыдущаяСтр 5 из 8Следующая ⇒

Для решения логических задач 2 способом (путем составления логического уравнения и приведения его к нормальной форме) нужно:

1. Внимательно изучить условие.

2. Выделить элементарные (простые) высказывания и обозначить их – как принято –большими латинскими буквами.

3. Записать условие задачи на языке алгебры логики, соединив простые высказывания в сложные при помощи логических операций &, Ú и т. д.

4. Полученное выражение упростить, используя законы алгебры логики; преобразуя выражения, заменить заведомо истинные или ложные высказывания (в соответствии с условием задачи) их значением.

5. Выбрать решение – набор значений, при котором выражение (п. 3) является истинным.

6. Проверить, удовлетворяет ли полученное решение условию задачи.

Задача 1. Кто из абитуриентов А, В, С и D играет, а кто не играет в шахматы, если известно:

а) если А или В играет, то С не играет;

б) если В не играет, то играют С и D;

в) С играет.

Решение

Запишем высказывания. Полученные выражения упростим:

а) (А + В) ®`С = А + В +`С = `А`В +`С;

б) `В ®CD = B + CD;

в) С

Если все эти истинные высказывания логически перемножить, то получится истинное сложное высказывание:

(`А`В + `С)( B + CD) С = 1

Раскрыв скобки, получим: `А`В С D = 1.

Ответ: C и D играют, А и В не играют.

Задача 2. Аня, Вика и Сергей решили пойти в кино. Учитель, хорошо знавший этих ребят, высказал предположения:

а) Аня пойдет только тогда, когда пойдут Вика и Сергей;

б) Аня и Сергей пойдут в кино вместе или же оба останутся дома;

в) Чтобы Сергей пошел в кино, необходимо, чтобы пошла Вика.

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

Решение

а) А ®ВС = `А + ВС (X)

б) АС +`А`С (Y)

в) С ® В = `С +В (Z)

F = `XYZ +`YXZ +`ZXY

(1) (2) (3)

(1) `X =`А + ВС = А × ВС = А × (`В +`С) = А× `В + А× `С;
`XYZ = (А× `В + А× `С)( АС +`А`С)(`С +В) = (А`ВС + 0 + 0 + 0)( `С +В) = 0 + 0 = 0

(2) `Y = АС +`А`С = АС × `А`С = (`А +`С) × (А + С) = `АС + А`С;
`YXZ = (`АС + А`С)( `А + ВС)(`С +В) = (`АС +`АВС)(`С +В) = `АВС

(3) `Z = `С +В = С × `В;
`ZXY = (С × `В)(`А + ВС)( АС +`А`С) = (`А`С + АВС) × (С`В) = 0

Ответ: А = 0, В = 1, С = 1, т.е. в кино пойдут Вика и Сергей, а Аня не пойдет.

Задача 3. На вопрос, какая завтра будет погода, синоптик ответил:

а) если не будет ветра, то будет пасмурная погода без дождя;

б) если будет дождь, то будет пасмурно и без ветра;

в) если будет пасмурная погода, то будет дождь и не будет ветра.

Какая же будет погода? Что хотел сказать синоптик?

Решение

Введем простые высказывания:

В = “Будет ветер”

Р = “Будет пасмурная погода”

D = “Будет дождь”

Тогда составные условия задачи запишутся в виде:

`В® Р`D; б) D® Р`В; с) Р® D`В

Составив конъюнкцию этих высказываний и приведя ее к нормальной форме, получим В`Р`D. Таким образом, три высказывания синоптика можно заменить одним: “Будет ясная погода без дождя, но с ветром”.

Упражнения

Задача 1. Внимание Андрея, Дениса и Марата привлек промчавшийся мимо них автомобиль.

– Это английская машина марки «Феррари», — сказал Андрей.

– Нет, машина итальянская марки «Понтиак», — возразил Денис.

– Это «Сааб», и сделан он не в Англии, –сказал Марат.

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

Какой же марки этот автомобиль и в какой стране изготовлен?

Решение: Рассмотрим простые высказывания:

А= «Английская машина», F= «Феррари», I= «Итальянская», Р= «Понтиак», С= «Сааб».

Запишем на языке логики условие задачи, учитывая высказывания мальчиков и то, что верно указана либо страна либо марка автомобиля:

1) A" F = A`F +`A F = 1 (Слова Андрея)

2) I" P = I`P +`I P=1 (Слова Дениса)

3) `A" C =`A`C + AC=1 (Слова Марата)

Если все эти истинные высказывания перемножить, то получится истинное сложное высказывание.

(A`F +`A F) & (I`P +`I P) & (`A`C + AC) = 1

Учитывая, что AI=0; FP=0; PC=0; FC=0 (машина не может быть одновременно итальянской и английской, «Феррари», «Понтиак» и «Сааб»),. получаем выражение:

I`A F`P`C = 1 Делаем вывод: машина «Феррари», изготовлена в Италии.

Задача 2. В клуб служебного собаководствана очередную тренировку пришли со своими собаками Антон, Борис, Петр, Виктор и Олег. Желая подшутить над новым инструктором, на его вопрос: «Кто же хозяин каждой из собак? », каждый юноша дал один правильный и один неправильный ответ.

Антон сказал: «Моя собака — Рекс, а собака Петра — Лайма». Борис сказал: «Рекс — моя собака, а собака Виктора — Джек». Петр сказал: «Собака Виктора - Зевс, а моя — Рекс». Виктор сказал: «Моя собака — Джек, а собака Олега — Бичо». Олег сказал: «Да, моя собака - Бичо, а собака Бориса - Зевс».

Кто же на самом деле хозяин каждой из собак?

Задача 3. Трое друзей, болельщиков автогонок «Формула-1», спорили о результатах предстоящего этапа гонок.

— Вот увидишь, Шумахер не придет первым, — сказал Джон. — Первым будет Хилл.

— Да нет же, победителем будет, как всегда, Шумахер! — воскликнул Ник. — А об Алези и говорить нечего, ему не быть первым. Питер, к которому обратился Ник, возмутился:

— Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.

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

( Замечание: высказывание «Алези пилотирует самую мощную машину» совсем не означает, что он одержит победу)

Самостоятельная работа №3.

1) Упростить формулу;

2) решить задачу путем составления логического уравнения (формулы) и приведения его к нормальной форме)

Составление логического уравнения и решение его с помощью ЭВМ

Для решения логических задач 3 способом (путем составления логического уравнения и решения его с помощью ЭВМ) необходимо знать следующее:

1) В языке программирования Qbasic логическое значение “истина” кодируется числом
“-1”, а “ложь” кодируется числом “0”. В условном операторе после ключевого слова IF можно вместо условия писать логическую переменную. Пример:
x = 1: y = 2: z = x < y
IF z THEN x = 2*x ELSE y = 2*y
PRINT “z = ”; z, “х = ”; x, “у = ”; y
Результат выполнения программы:
z = -1 х = 2 у = 2

2) Логические операции обозначаются NOT - отрицание, AND - конъюнкция, OR - дизъюнкция, XOR - строгая дизъюнкция, IMP - импликация, EQV - эквиваленция.

Задача.

Вернувшись домой, Мегрэ позвонил на набережную Орфевр.

- Говорит Мегрэ. Есть новости?

- Да, шеф. Поступили сообщения от инспекторов. Торранс установил, что если Франсуа был пьян, то либо Этьен убийца, либо Франсуа лжет. Жуссье считает, что или Этьен убийца, или Франсуа не был пьян и убийство произошло после полуночи. Инспектор Люка просил передать вам, что если убийство произошло после полуночи, то либо Этьен убийца, либо Франсуа лжет. Затем звонила…

- Все. Спасибо. Этого достаточно. –

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

Решение.

Рассмотрим следующие простые высказывания:

А= «Франсуа был пьян»

В = «Этьен убийца»

С = «Франсуа лжет»

D = «Убийство произошло после полуночи»

Перепишем на языке алгебры логики условие задачи. Инспектора комиссара Мегрэ установили, что

А ® (В " С) = 1

В " (`А × D) = 1

D ® (B " C) = 1

Сам Мегрэ знает, что `А × `С = 1

Истинной будет и конъюнкция четырех высказываний. Программа на Qbasic будет выглядеть следующим образом:

CLS

FOR A = -1 TO 0

FOR B = -1 TO 0

FOR C = -1 TO 0

FOR D = -1 TO 0

X1 = A IMP (B XOR C)

X2= B XOR ((NOT A) AND D)

X3 = D IMP (B XOR C)

X4 = NOT A AND NOT C

X = X1 AND X2 AND X3 AND X4

IF X THEN

IF A THEN PRINT “ Франсуа был пьян “

IF A THEN PRINT “ Этьен убийца “

IF A THEN PRINT “ Франсуа лжет “

IF A THEN PRINT “ Убийство произошло после полуночи “

END IF

NEXT D, C, B, A

END

Переменные Х1, Х2, Х3 и Х4 – промежуточные переменные; A, B, C, D – простые высказывания; Х – конъюнкция Х1, Х2, Х3 и Х4.

Результат выполнения программы: Этьен убийца.

Решите на компьютере задачи 14-18 из «Заданий для самостоятельного выполнения».

⇐ Предыдущая 1 2 3 456 7 8 Следующая ⇒