Задачи по булевой алгебре с ответами – Логические задачи в алгебре логики с примерами, решениями и ответами

Содержание

Решение элементарных задач булевой алгебры.

    Логика очень древняя наука. Ещё в античные времена была известна формальная логика, позволяющая делать заключения о правильности какого-либо суждения не по его фактическому содержанию, а только по форме его построения. Например, уже в древности был известен закон исключения третьего. Его содержательная трактовка была такова: «Во время своих странствований Платон был в Египте ИЛИ не был Платон в Египте». В такой форме это или любое другое выражение будут правильны (тогда говорили: истинно). Ничего другого быть не может: Платон либо был, либо не был в Египте — третьего не дано.
    Другой закон логики — закон непротиворечивости. Если сказать: «Во время своих странствий Платон был в Египте И не был Платон в Египте», то очевидно, любое высказывание, имеющее такую форму, всегда будет ложно. Если из теории следуют два противоречащих друг другу вывода, то такая теория безусловно неправильная (ложная) и должна быть отвергнута.
    Ещё один закон, известный в древности — закон отрицания: «Если НЕверно, что Платон НЕ был в Египте, то значит, Платон был в Египте».
    Формальная логика основана на “высказываниях”. “Высказывание” — это основной элемент логики, определяемый как повествовательное предложение, относительно которого можно однозначно сказать, истинное или ложное утверждение оно содержит.
    Например: Листва на деревьях опадает осенью. Земля прямоугольная.
    Первое высказывание содержит истинную информацию, а второе — ложную. Вопросительное, побудительное и восклицательное предложения не являются высказываниями, так как в них ничего не утверждается и не отрицается.
    Пример предложений, не являющихся высказываниями: Не пейте сырую воду! Кто не хочет быть счастливым?
    Высказывания могут быть и такими: 21, Н2О+SO3=h3SO4. Здесь используются языки математических символов и химических формул.
    Приведённые выше примеры высказываний являются простыми. Но из простых высказываний можно получить сложные, объединив их с помощью логических связок. Логические связки — это слова, которые подразумевают определённые логические связи между высказываниями. Основные логические связки издавна употребляются не только в научном языке, но и в обыденном, — это “и”, “или”, “не”, “если … то”, “либо … либо” и другие известные нам из русского языка связки. В рассмотренных нами трёх законах формальной логики использовались связки “и”, “или”, “не”, “если … то” для связи простых высказываний в сложные.
    Высказывания бывают общими, частными и единичными. Общее высказывание начинается со слов: всё, все, всякий, каждый, ни один.Частное высказывание начинается со слов: некоторые, большинство и т.п. Во всех других случаях высказывание является единичным.
    Формальная логика была известна в средневековой Европе, она развивалась и обогащалась новыми законами и правилами, но при этом вплоть до 19 века она оставалась обобщением конкретных содержательных данных и её законы сохраняли форму высказываний на разговорном языке.

    В 1847 году английский математик Джордж Буль, преподаватель провинциального университета в маленьком городке Корке на юге Англии разработал алгебру логики.
    Алгебра логики очень проста, так как каждая переменная может принимать только два значения: истинно или ложно. Трудность изучения алгебры логики возникает из-за того, что для обозначения переменных принимают символы 0 и 1, которые по написанию совпадают с обычными арифметическими единицей и нулём. Но совпадение это только внешнее, так как смысл они имеют совсем иной.
    Логическая 1 означает, что какое-то событие истинно, в противоположность этому логический 0 означает, что высказывание не соответствует истине, т.е. ложно. Высказывание заменилось на логическое выражение, которое строится из логических переменных (А, В, Х, …) и логических операций (связок).
    В алгебре логики знаки операций обозначают лишь три логические связки ИЛИ, И, НЕ.
    1.Логическая операция ИЛИ. Логическую функцию принято задавать в виде таблицы. В левой части этой таблицы перечисляются все возможные значения аргументов функции, т.е. входные величины, а в правой указывается соответствующее им значение логической функции. Для элементарных функций получается таблица истинности данной логической операции. Для операции ИЛИ таблица истинности имеет вид:

    Операцию ИЛИ называют также логическим сложением, и потому её можно обозначать знаком «+».
    Рассмотрим сложное единичное высказывание: «Летом я поеду в деревню или в туристическую поездку». Обозначим через А простое высказывание «Летом я поеду в деревню», а через В — простое высказывание «Летом я поеду в туристическую поездку». Тогда логическое выражение сложного высказывания имеет вид А+В, и оно будет ложным только, если ни одно из простых высказываний не будет истинным.
    2. Логическая операция И. Таблица истинности для этой функции имеет вид:

Из таблицы истинности следует, что операция И — это логическое умножение, которое ничем не отличается от традиционно известного умножения в обычной алгебре. Операцию И можно обозначить знаком по-разному:

В формальной логике операции логического умножения соответствуют связки и, а, но, хотя.
3. Логическая операция НЕ. Эта операция является специфичной для алгебры логики и не имеет аналога в обычной алгебре. Она обозначается чертой над значением переменной, либо знаком приставки перед значением переменной:

Читается в обоих случаях одинаково «Не А». Таблица истинности для этой функции имеет вид:

В вычислительной технике операцию НЕ называют отрицанием или инверсией, операцию ИЛИ — дизъюнкцией, операцию И — конъюнкцией. Набор логических функций “И”, “ИЛИ”, “НЕ” является функционально полным набором или базисом алгебры логики. С помощью него можно выразить любые другие логические функции, например операции “строгой дизъюнкции”, “импликации” и “эквивалентности” и др. Рассмотрим некоторые из них.
Логическая операция “строгая дизъюнкция”. Этой логической операции соответствует логическая связка “либо … либо”. Таблица истинности для этой функции имеет вид:

Операция “строгая дизъюнкция” выражается через логические функции “И”, “ИЛИ”, “НЕ” любой из двух логических формул:

и иначе называется операцией неравнозначности или “сложения по модулю 2”, так как при сложении чётного количества единиц, результатом будет “0”, а при сложении нечётного числа единиц, результат станет равен “1”.
Логическая операция “импликация”. Выражение, начинающееся со слов если, когда, коль скоро и продолжающееся словами то, тогда,называется условным высказыванием или операцией «импликация». Таблица истинности для этой функции имеет вид:

Операцию “импликация” можно обозначить по-разному:

Эти выражения эквивалентны и читаются одинаково: «Игрек равен импликации от А и В». Операция “импликация” выражается через логические функции “ИЛИ”, “НЕ” в виде логической формулы

Логическая операция “эквивалентность” (равнозначность). Этой логической операции соответствуют логические связки “если и только если”, «тогда и только тогда, когда». Таблица истинности для этой функции имеет вид:

Операция “эквивалентность” обозначается по-разному. Выражения

обозначают одно и тоже, и можно сказать, что А эквивалентна В, если и только если они равнозначны. Логическая операция “эквивалентность” выражается через логические функции “И”, “ИЛИ”, “НЕ” в виде логической формулы

С помощью алгебры логики можно очень кратко записать законы формальной логики и дать им математически строгое доказательство.

В алгебре логики, как в элементарной, справедливы переместительный(закон коммутативности), сочетательный (закон ассоциативности) и распределительный (закон дистрибутивности) законы, а также аксиома идемпотентности (отсутствие степеней и коэффициэнтов) и др., в записях которых используются логические переменные, принимающие только два значения — логический ноль и логическая единица. Применение этих законов позволяет производить упрощение логических функций, т.е. находить для них выражения, имеющие наиболее простую форму. Основные аксиомы и законы алгебры логики приведены в таблице:

Примеры использования основных аксиом и законов:

multiurok.ru

Применение инструмента алгебры логики при решении логических задач

История с амфорой

Антон, Борис и Григорий нашли в земле сосуд, о котором каждый высказал по два предположения:

Антон: «Сосуд греческий и изготовлен в V столетии»;
Борис: «Сосуд финикийский и изготовлен в III столетии»;
Григорий: «Сосуд не греческий и изготовлен в IV столетии».

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

Решение:

Введем следующие обозначения:

$G$ — «Сосуд греческий»;

$F$ — «Сосуд финикийский»;

$S_3$ — «Сосуд изготовлен в $III$ столетии»;

$S_4$ — «Сосуд изготовлен в $IV$ столетии»;

$S_5$ — «Сосуд изготовлен в $V$ столетии».

Запишем условие задачи с помощью обозначений:

Антон прав только в одном предположении: $G = 1$ или $S_5 = 1$. Тогда $G\overline{S_5}\vee \overline{G}S_5=1$.

Аналогично для слов Бориса: $F\overline{S_3}\vee \overline{F}S_3=1$.

Для слов Григория: $\overline{G}\overline{S_4}\vee GS_4=1$.

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

\[S_3\overline{S_4}\overline{S_5}\vee \overline{S_3}S_4\overline{S_5}\vee \overline{S_3}\overline{S_4}S_5=1,\] \[F\overline{G}\vee \overline{F}G=1.\]

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

\[\left(G\overline{S_5}\vee \overline{G}S_5\right)\wedge \left(F\overline{S_3}\vee \overline{F}S_3\right)\wedge \left(\overline{G}\overline{S_4}\vee GS_4\right)\wedge \left(F\overline{G}\vee \overline{F}G\right)\wedge \] \[\wedge \left(S_3\overline{S_4}\overline{S_5}\vee \overline{S_3}S_4\overline{S_5}\vee \overline{S_3}\overline{S_4}S_5\right)=\]

Перемножим первую на третью скобку и вторую на четвертую:

\[=\left(G\overline{S_5}\overline{G}\overline{S_4}\vee \overline{G}S_5\overline{G}\overline{S_4}\vee G\overline{S_5}GS_4\vee \overline{G}S_5GS_4\right)\wedge \] \[\wedge \left(F\overline{S_3}F\overline{G}\vee \overline{F}S_3F\overline{G}\vee F\overline{S_3}\overline{F}G\vee \overline{F}S_3\overline{F}G\right)\wedge \left(S_3\overline{S_4}\overline{S_5}\vee \overline{S_3}S_4\overline{S_5}\vee \overline{S_3}\overline{S_4}S_5\right)=\]

Т.к. $G\overline{G}=0$, $GG=G$, $\overline{G}\overline{G}=\overline{G}$, упростим выражения:

\[=\left(\overline{G}S_5\overline{S_4}\vee G\overline{S_5}S_4\right)\wedge \left(F\overline{S_3}\overline{G}\vee \overline{F}S_3G\right)\wedge \left(S_3\overline{S_4}\overline{S_5}\vee \overline{S_3}S_4\overline{S_5}\vee \overline{S_3}\overline{S_4}S_5\right)=\]

Перемножим первые две скобки и упростим выражение:

\[=\left(\overline{G}S_5\overline{S_4}\overline{F}S_3G\vee G\overline{S_5}S_4\overline{F}S_3G\vee \overline{G}S_5\overline{S_4}F\overline{S_3}\overline{G}\vee G\overline{S_5}S_4F\overline{S_3}\overline{G}\right)\wedge \] \[\wedge \left(S_3\overline{S_4}\overline{S_5}\vee \overline{S_3}S_4\overline{S_5}\vee \overline{S_3}\overline{S_4}S_5\right)=\] \[=\left(G\overline{S_5}S_4\overline{F}S_3\vee \overline{G}S_5\overline{S_4}F\overline{S_3}\right)\wedge \left(S_3\overline{S_4}\overline{S_5}\vee \overline{S_3}S_4\overline{S_5}\vee \overline{S_3}\overline{S_4}S_5\right)=\] \[=\left(G\overline{S_5}S_4\overline{F}S_3\vee \overline{G}S_5\overline{S_4}F\overline{S_3}\right)\wedge \left(S_3\overline{S_4}\overline{S_5}\vee \overline{S_3}S_4\overline{S_5}\vee \overline{S_3}\overline{S_4}S_5\right)=\overline{G}S_5\overline{S_4}F\overline{S_3};\]

$\overline{G}S_5\overline{S_4}F\overline{S_3}=1$, что возможно только в случае:

\[\overline{G}=1, S_5=1, \overline{S_4}=1, F=1, \overline{S_3}=1.\]

Ответ: сосуд финикийский и изготовлен в $V$ столетии.

spravochnick.ru

решение задач с помощью алгебры логики.

Одним из мощных методов решения логических задач является решение с помощью законов алгебры логики.

Алгоритм решения логических задач с помощью алгебры логики: 1) внимательно изучить условие; 2) выделить простые высказывания и обозначить их латинскими буквами; 3) записать условие задачи на языке алгебры логики; 4) составить конечную формулу, для этого объединить логическим умножением формулы каждого утверждения, приравнять произведение единице; 5) упростить формулу, проанализировать полученный результат или составить таблицу истинности, найти по таблице значения переменных, для которых F = 1, проанализировать результаты.

Задача1 » Кто преступник»

Определить участника преступления, исходя из двух

посылок:

1) «Если Иванов не участвовал или Петров участвовал,

то Сидоров участвовал»;

2) «Если Иванов не участвовал, то Сидоров не

участвовал».

Рассмотрим решение этой несложной задачи двумя способами: с помощью таблиц истинности и с помощью алгебраических преобразований.

1 способ

Составим выражения:

I — «Иванов участвовал в преступлении»;

P — «Петров участвовал в преступлении»;

S — «Сидоров участвовал в преступлении»

.
Запишем посылки в виде формул:

¬I˅P→S и ¬I→¬S

Из таблицы видно, что совершил преступление Иванов

Способ 2

Применим для решения этой же задачи преобразования с

помощью законов алгебры логики:

( ¬I˅P→S) &( ¬I→¬S)=(¬(¬I˅P)˅S) & (I˅¬S) =

= (I & ¬P ˅S) &(I ˅¬S) = I&¬P˅ I & S˅ I &¬P &¬S ˅0=

= I&¬P ˅ I & S =I & (¬P˅S)

Из последнего выражения видно, что выражение верно, если I=1, значит преступник — Иванов.

Задача 2 «Прогноз погоды»

На вопрос, какая завтра будет погода, синоптик ответил: 1. Если не будет ветра, то будет пасмурная погода без дождя. 2. Если будет дождь, то будет пасмурно и без ветра. 3. Если будет пасмурная погода, то будет дождь и не будет ветра. Так какая же погода будет завтра?

Решим эту задачу средствами алгебры логики.

1.         Выделим простые высказывания и запишем их через переменные:

A – «Ветра нет»

B – «Пасмурно»

С – «Дождь» 2.          Запишем логические функции (сложные высказывания) через введенные переменные:

Если не будет ветра, то будет пасмурная погода без дождя:
A → B & C
Если будет дождь, то будет пасмурно и без ветра:
С → B & A
Если будет пасмурная погода, то будет дождь и не будет ветра
B → C &

в) Запишем произведение указанных функций:
F=(A→ B & C) & (C→B & A) & (B→ C & A)
Упростим формулу (используются законы де Моргана, переместительный закон, закон противоречия):

F=(A→ B & ¬C) & (C→B & A) & (B→ C & A)

= (¬A v B & ¬C) & (¬C v B&A) & (¬B v C&A) =

= (¬A v B & ¬C) & (¬B v C&A) & (¬C v B&A) =

= (¬A &¬ B v B&¬C&¬B v ¬A&C&A v B&¬C&C&A) &
(C v B&A)=

= ¬A & ¬B &(C v B&¬A) =A&¬B&C v¬ A&¬B&B&¬A = 3.         Приравняем результат единице, т.е. наше выражение должно быть истинным:F = ¬A &¬ B & ¬C = 1 и проанализируем результат: Логическое произведение равно 1, если каждый множитель равен 1. ¬A = 1; ¬B = 1; ¬C = 1.значит: A = 0; B = 0; C = 0;

Ответ: погода будет ясная, без дождя, но ветреная.
Задача 3 «История с амфорой».
Алеша, Боря и Гриша нашли в земле сосуд. Рассматривая удивительную находку, каждый высказал по два предположения.
Алеша: «Это сосуд греческий и изготовлен в V веке». Боря: «Это сосуд финикийский и изготовлен в III веке». Гриша: «Это сосуд не греческий и изготовлен в IV веке». Учитель истории сказал ребятам, что каждый из них прав только в одном из двух предположений. Где и в каком веке изготовлен сосуд?
Введем следующие обозначения:
«Это сосуд греческий» — G;
«Это сосуд финикийский» — F;
«Сосуд изготовлен в III веке» — V₃;
«Сосуд изготовлен в IV веке» — V₄;
«Сосуд изготовлен в V веке» — V₅. Формализуем задачу, записав в данных обозначениях условия задачи. Со слов учителя следует, что Алеша прав только в чем-то одном: или G = 1, или V₅ = 1. Таким образом, тождественно истинным будет высказывание: G¬V₅ v ¬GV₅.=1 Аналогично, из слов Бори и учителя следует: F¬V₃ v ¬FV₃ = 1, а из слов Гриши и учителя:
¬G¬V₄ v GV₄ = 1. Кроме того, ясно, что сосуд может быть изготовлен только в одном из веков и только в одной из стран. Эти условия можно записать так: V3¬V4¬V₅˅ ¬V3V4¬V5 ˅ ¬V3¬V4V5 = 1, Итак, мы получили пять тождественно истинных высказываний. Их нужно логически перемножить. Результат должен быть также тождественно истинным высказыванием: 1 = (G¬V₅ v ¬GV₅) & (F¬V₃ v ¬FV₃) & (¬G¬V₄ v GV₄) & (F¬G v ¬FG) & ( V3¬V4¬V₅˅ ¬V3V4¬V5 ˅ ¬V3¬V4V5) = (упростим: сначала перемножим первую и третью скобки и вторую и четвертую скобки) =(G¬V₅¬G¬V₄˅¬GV₅¬G¬V₄˅ G¬V₅GV₄ ˅ ¬GV₅ GV₄)&( F¬V₃ F¬G˅¬FV₃ F¬G˅ F¬V₃ ¬FG ˅ ¬FV₃¬FG) & (V3¬V4¬V₅˅ ¬V3V4¬V5 ˅ ¬V3¬V4V5) = учитывая, что, G¬G = 0, GG = G,¬ G¬G =¬ G, упростим выражения в первой и второй скобках: =(¬GV₅¬V₄˅ ¬V₅GV₄ ) &( ¬FV₃G ˅¬V₃ F¬G)& (V3¬V4¬V₅˅ ¬V3V4¬V5 ˅ ¬V3¬V4V5) = (перемножим первую и вторую скобки и упростим полученное выражение) (¬GV₅¬V₄¬FV₃G˅¬V₅GV₄¬FV₃G˅¬GV₅¬V₄¬V₃ F¬G ˅ ¬V₅GV₄¬V₃ F¬G) & (V3¬V4¬V₅˅ ¬V3V4¬V5 ˅ (¬V3¬V4V5)= (¬V₅V₄¬FV₃G˅¬GV₅¬V₄¬V₃ F) & (V3¬V4¬V₅˅ ¬V3V4¬V5 ˅ ¬V3¬V4V5)= ¬GV₅¬V₄¬V₃ F ¬GV₅¬V₄¬V₃ F=1, если ¬G=1, V₅=1, ¬V₄=1_, ¬V₃=1, F=1 Итак, сосуд финикийский и изготовлен в V веке.

Задача 4 «Поход в кино».
Андрей, Аня и Маша решили пойти в кино. Каждый из них высказал свои пожелания по поводу выбора фильма. Андрей сказал: «Я хочу посмотреть французский боевик». Маша сказала: «Я не хочу смотреть французскую комедию». Аня сказала: «Я хочу посмотреть американскую мелодраму». Каждый из них слукавил в одном из двух пожеланий. На какой фильм пошли ребята? 1.         Выделим простые высказывания и запишем их через переменные: А — «Французский фильм» С — «Комедия» 2. Запишем логические функции (сложные высказывания). Учтем условие о том, что каждый из ребят оказался прав в одном предположении: а) «Французский боевик» ¬A&B˅A&¬B б) «Американскую мелодраму» ¬¬A&¬B˅¬ А &¬¬В
в) «Нефранцузская комедия» ¬¬A&C˅¬A&¬C
3. Запишем произведение :
(¬A&B˅A&¬B) & (¬¬A&¬B˅¬ А&¬¬В)&( ¬¬A&C˅¬A&¬C)=1. Упростим формулу: (¬A&B˅A&¬B) & (¬¬A&¬B˅¬ А&¬¬В)&( ¬¬A&C˅¬A&¬C)= (¬A&B˅A&¬B) & (A&¬B˅¬ А&В)&( A&C˅¬A&¬C)= =(¬A&B& A&¬B˅ A&¬B& A&¬B˅¬A&B &¬А&В˅ A&¬B&¬A&B)&( A&C˅¬A&¬C)= =(A&¬B ˅¬A&B)&( A&C˅¬A&¬C)= A&¬B& A&C˅¬A&B& A&C˅ A&¬B&¬A&¬C˅¬A&B&¬A&¬C= = ¬A&B&¬C˅ A&¬B&C =1 6. Составим таблицу истинности для выражения:
¬A&B&¬C˅ A&¬B&C:
7. Найдем по таблице значения переменных, для которых F=1. 8. Проанализируем результат: Результат Б) не является решением, т.к. в ответе Маши оба утверждения оказываются неверными, что противоречит условию задачи. Результат А) полностью удовлетворяет условию задачи и поэтому является верным решением.
Ответ: ребята выбрали американский боевик.
А
Решите самостоятельно задачи уровня 3
inf61.blogspot.com
Методы решения логических задач
Исходными данными в логических задачах являются высказывания. Эти высказывания и взаимосвязи между ними бывают так сложны, что разобраться в них без использования специальных методов достаточно трудно.
Многие логические задачи связаны с рассмотрением нескольких конечных множеств и связей между их элементами. Для решения таких задач зачастую прибегают к помощи таблиц или графов, при этом успешность решения во многом зависит от удачно выбранной структуры таблицы или графа. Аппарат же алгебры логики позволяет построить формальный универсальный способ решения логических задач.
Формальный способ решения логических задач
Выделить из условия задачи элементарные (простые) высказывания и обозначить их буквами.
Записать условие задачи на языке алгебры логики, соединив простые высказывания в сложные с помощью логических операций.
Составить единое логическое выражение для всех требований задачи.
Используя законы алгебры логики, попытаться либо упростить полученное выражение и вычислить все его значения, либо построить таблицу истинности для рассматриваемого выражения, либо доказать истинность (ложность) некоторых утверждений методом рассуждений.
Выбрать решение — набор значений простых высказываний, при котором построенное логическое выражение является истинным.
Проверить, удовлетворяет ли полученное решение условию задачи.
Рассмотрим, как можно использовать эти способы для решения задач.
Решение логических задач средствами алгебры логики
Задача «Уроки логики». На вопрос, кто из трех учащихся изучал логику, был получен ответ: «Если изучал первый, то изучал и второй, но неверно, что если изучал третий, то изучал и второй». Кто из учащихся изучал логику?
Решение. Введём обозначения:
Р₁ – первый учащийся изучал логику;
Р₂ – второй учащийся изучал логику;
Р₃ – третий учащийся изучал логику.
Из условия задачи следует истинность высказывания . Воспользуемся соотношением (20) и упростим исходное высказывание:
.
Высказывание (согласно (11)), а, следовательно, ложно и высказывание . Поэтому должно быть истинным высказывание .
Ответ. Логику изучал третий учащийся, а первый и второй не изучали.
Задача «Прогноз». Трое друзей, болельщиков автогонок «Формула-1», спорили о результатах предстоящего этапа гонок.
— Вот увидишь, Шумахер не придет первым, — сказал Джон. Первым будет Хилл.
— Да нет же, победителем будет, как всегда, Шумахер, — воскликнул Ник. — А об Алези и говорить нечего, ему не быть первым.
Питер, к которому обратился Ник, возмутился:
— Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.
По завершении этапа гонок оказалось, что каждое из двух предположений двоих друзей подтвердилось, а оба предположения третьего из друзей оказались неверны. Кто выиграл этап гонки?
Решение. Введем обозначения для логических высказываний:
Ш — победит Шумахер; Х — победит Хилл; А — победит Алези.
Реплика Ника «Алези пилотирует самую мощную машину» не содержит никакого утверждения о месте, которое займёт этот гонщик, поэтому в дальнейших рассуждениях не учитывается.
Зафиксируем высказывания каждого из друзей:
Джон: ,Ник: , Питер: .
Учитывая то, что предположения лишь двух друзей подтвердились, а предположения третьего неверны, запишем все возможные комбинации истинности двух из трёх высказываний. Тогда истинное высказывание будет иметь вид:
=1.
Упростим это выражение. Используя (11), установим, что первые два слагаемые тождественно-ложные. Тогда, с учётом формул де Моргана для третьего слагаемого:
Произведение будет истинным только при Ш=1, А=0, Х=0.
Ответ. Победителем этапа гонок стал Шумахер.
studfiles.net
Алгебра логики. Задачи

Алгебра
логики.
Задачи
2) ИЛИ НЕ (X 1)? 1) 1 2) 2 3) 3 4) 4 «
Задача №2
Для какого из указанных значений числа X ложно выражение (X 2) ИЛИ НЕ (X 1)?
1) 1
2) 2
3) 3
4) 4
2) И НЕ (X 3)? 1)   1 2)   2 3)   3 4)   4 «
Задача №3
Для какого из указанных значений числа X истинно выражение (X 2) И НЕ (X 3)?
1)   1
2)   2
3)   3
4)   4

Задача №4
Для какого из указанных значений числа X истинно выражение (X 2))?
1)   1
2)   2
3)   3
4)   4

Задача №5
Для какого из приведенных чисел истинно высказывание:
НЕ(Первая цифра четная) И НЕ(Вторая цифра нечетная)?
1) 4562
2) 6843
3) 3561
4) 1234

Задача №6
Для какого имени истинно высказывание:
¬ ( Первая буква имени гласная → Четвертая буква имени согласная )?
ЕЛЕНА    2) ВАДИМ
3) АНТОН        4) ФЕДОР

Задача №7
Для какого имени ложно высказывание:
( Первая буква гласная ^ Последняя буква согласная ) →    ¬ (Третья буква согласная) ?
ДМИТРИЙ                     2) АНТОН
   3) ЕКАТЕРИНА       4) АНАТОЛИЙ

Задача №8
Для какого имени истинно высказывание:
( Вторая буква гласная → Первая буква гласная ) ^ Последняя буква согласная ?
АЛИСА                  2)МАКСИМ          3) СТЕПАН             4) ЕЛЕНА

Задача №9
Для составления цепочек разрешается использовать бусины четырех типов,
обозначенные буквами У, М, К, И. Каждая цепочка должна состоять из трех бусин, при
этом должны соблюдаться правила:
— любая цепочка заканчивается гласной буквой,
— после согласной буквы не может идти буква У, а после гласной К,
— на первом месте не может быть К или М.
Какая из цепочек построена по этим правилам?
1) МКУ 2) ИКИ 3) УМИ 4) КУУ
Решение:
Здесь правила есть логические высказывания. Требуется определить, какая из цепочек символов удовлетворяет всем высказываниям. Для каждого из ответов проверим истинность высказываний:
Ответы любая цепочка заканчивается гласной буквой после согласной буквы не может идти буква У,
а после гласной К на первом месте не может быть К или М
1) МКУ да нет нет
2) ИКИ да нет да
3) УМИ да да да
4) КУУ да нет нет
Все высказывания истинны только для ответа № 3.
Ответ: № 3

Задача №10
При составлении расписания на понедельник учителя высказали свои пожелания по поводу первых пяти уроков. Учитель черчения хочет иметь второй или третий урок,
учитель математики – первый или второй урок, учитель информатики – третий или четвертый, учитель географии – третий или четвертый, учитель русского языка согласен
только на первый или пятый уроки.
Какой вариант расписания подойдет всем учителям школы? (Обозначения: Ч – черчение, М – математика, И – информатика, Г – география, Р – русский язык.)
1) Ч М И Г Р 2) М Ч И Г Р 3) Р Ч М Г И 4) М Р Ч И Г
Решение:
Требуется выяснить, для какого из вариантов ответов все высказывания учителей истинны. Внесем их в таблицу,.
Номер урока 1 2 3 4 5
Предмет М, Р Ч, М Ч, И, Г И, Г Р
Проверим истинность высказываний для каждого ответа.
Ответы: 1: М, Р 2: Ч, М 3: Ч, И, Г 4: И, Г 5: Р
1) ЧМИГР нет да да да да
2) МЧИГР да да да да да
3) РЧМГИ да да нет да нет
4) МРЧИГ да нет да да нет
Все высказывания истинны только для ответа № 2
Ответ: № 2
10) ∧ ￢ (X + 3 ￢ (X 0) ? 1) 0 2) 2 3) 4 4) 7 Решение: Преобразуем неравенства так, чтобы слева оставалась только переменная X. Получим ( X 5) ∧ ￢ (X ￢ (X 0). Далее выполним операции отрицания, получим ( X 5) ∧ (X = 5) ∨ (X ( X 5) ∧ (X = 5), результатом выполнения которой будет истина только в том случае, если оба неравенства будут выполняться. Это возможно только при X 5. Наконец, последней выполняется операция дизъюнкции. Для получения истины необходимо, чтобы хотя бы один из операндов был истинным: Х 5 или X числа положительные, но только 7 5, значит, ответ Х = 7. Эту задачу можно решить составлением таблицы истинности. Введем логические переменные А, В и С: А = ( X*2 10), В = ( X + 3 0 ). Тогда выражение можно записать в виде А ∧ ￢ В ∨ ￢ С. Порядок выполнения операций: отрицание В, отрицание С, логическое умножение, логическое сложение. X А ( X 5) В ( X С ( X 0 ) ￢ В А ∧ ￢ В ￢ С А ∧ ￢ В ∨ ￢ С 0 0 1 1 0 0 0 0 2 0 1 1 0 0 0 0 4 0 1 1 0 0 0 0 7 1 0 1 1 1 0 1 Ответ: № 4 «
Задача №11
Для какого из указанных значений числа X истинно выражение
( X * 2 10) ∧ ￢ (X + 3 ￢ (X 0) ?
1) 0 2) 2 3) 4 4) 7
Решение: Преобразуем неравенства так, чтобы слева оставалась только переменная X.
Получим ( X 5) ∧ ￢ (X ￢ (X 0). Далее выполним операции отрицания, получим
( X 5) ∧ (X = 5) ∨ (X
( X 5) ∧ (X = 5), результатом выполнения которой будет истина только в том случае,
если оба неравенства будут выполняться. Это возможно только при X 5. Наконец,
последней выполняется операция дизъюнкции. Для получения истины необходимо, чтобы
хотя бы один из операндов был истинным: Х 5 или X
числа положительные, но только 7 5, значит, ответ Х = 7.
Эту задачу можно решить составлением таблицы истинности. Введем логические
переменные А, В и С: А = ( X*2 10), В = ( X + 3 0 ). Тогда выражение
можно записать в виде А ∧ ￢ В ∨ ￢ С. Порядок выполнения операций: отрицание В,
отрицание С, логическое умножение, логическое сложение.
X А
( X 5)
В
( X
С
( X 0 )
￢ В А ∧ ￢ В ￢ С А ∧ ￢ В ∨ ￢ С
0 0 1 1 0 0 0 0
2 0 1 1 0 0 0 0
4 0 1 1 0 0 0 0
7 1 0 1 1 1 0 1
Ответ: № 4
= (X + 1) ・ (X + 1)) равно ___________ Решение: Преобразуем выражение, используя формулу A→B = ￢ A ∨ B. Отрицанием высказывания (256 X ・ X ) является (256 X ・ X ). Получим выражение (256 X ・ X ) ∨ (256 = (X + 1) ・ (X + 1)) Для того чтобы выражение было истинным, должны выполняться хотя бы одно неравенство. Первое неравенство выполняется при –16 Х – 17 Х Ответ: –17. «
Задача №12
Наименьшее целое значение числа X, при котором истинно выражение
(256 X ・ X ) → (256 = (X + 1) ・ (X + 1))
равно ___________
Решение: Преобразуем выражение, используя формулу A→B = ￢ A ∨ B. Отрицанием
высказывания (256 X ・ X ) является (256 X ・ X ). Получим выражение
(256 X ・ X ) ∨ (256 = (X + 1) ・ (X + 1))
Для того чтобы выражение было истинным, должны выполняться хотя бы одно
неравенство. Первое неравенство выполняется при –16 Х
– 17 Х
Ответ: –17.

Задача №13
Какое из приведенных названий животных удовлетворяет логическому условию
￢ (есть мягкий знак ∧ (вторая буква гласная → пятая буква согласная))
1) МЕДВЕДЬ 2) ВЫХУХОЛЬ 3) МУРАВЬЕД 4) ОБЕЗЬЯНА
Решение:
Введем обозначения логических высказываний
А – есть мягкий знак (не А – нет мягкого знака)
В – вторая буква гласная (не В – вторая буква согласная)
С — пятая буква согласная (не С – пятая буква гласная)
Запишем условие с использованием обозначений и построим таблицу истинности
для каждого варианта ответа с учетом правил очередности выполнения операций.
￢ (А ∧ (В → С))
Ответ А В С В → С А ∧ (В → С) ￢ (А ∧ (В → С))
МЕДВЕДЬ 1 1 0 0 0 1
ВЫХУХОЛЬ 1 1 1 1 1 0
МУРАВЬЕД 1 1 1 1 1 0
ОБЕЗЬЯНА 1 0 0 1 1 0
Ответ № 1.

Задача №14
Какое из приведенных имен удовлетворяет логическому условию
￢ (первая буква гласная → последняя буква гласная) ∧ вторая буква согласная
1) ИРИНА 2) ОЛЕГ 3) СТЕПАН 4) ИЛОНА
Решение. Подобную задачу мы рассмотрели выше, где решали ее построением таблицы
истинности. В этом примере введем обозначения и выполним преобразования логического
выражения.
А – первая буква гласная
В – последняя буква гласная
С – вторая буква согласная
￢ (А →В) ∧ С = ￢ ( ￢ А ∨ В) ∧ С = А ∧ ￢ В ∧ С
Полученное выражение означает, что все три сомножителя одновременно должны быть
истиной. Возвращаясь к высказываниям, получим, что в слове
первая буква гласная и последняя буква согласная и вторая буква согласная.
Этому условию удовлетворяет имя ОЛЕГ.
Ответ № 2
videouroki.net
Решение комбинаторных задач с помощью алгебры логики.
   Логические задачи очень разнообразны. Способов их решения тоже немало. Но наи-большее распространение получили следующие три способа решения логических задач:
• средствами алгебры логики;
• табличный;
• с помощью рассуждений;

Обычно используется следующая схема решения:
1. Изучается условие задачи.
2. Вводится система обозначений для логических высказываний.
3. Конструируется логическая формула, описывающая логические связи между всеми высказываниями, выделенными из условия задачи.
4. Определяются значения истинности этой логической формулы.
5. Из полученных значений истинности формулы определяются значения истин-ности введённых логических высказываний, на основании которых делается заключение о решении.
Рассмотрим текстовые задачи, которые могут быть решены с привлечением аппарата алгебры логики, т. е. основных законов алгебры логики.
ЗАДАЧА 1.

Однажды гномы, решившие отправиться за сокровищами, собрались на совет, чтобы обсудить возможные опасности, которые их ожидают. Было высказано три предложения:
1. Их либо захватят гоблины, либо нападёт дракон, либо они заблудятся в лесу, либо их ожидают какие – то две, а может быть, и все три из этих опасностей.
2. Если дракон не нападёт, то они утонут в реке.
3. И дракон нападёт, и заблудятся в лесу.
Помогавший им волшебник успокоил их и сказал, что второе и третье предположения ложны. Каких же опасностей следует ожидать гномам?

Решение:
Введём логические переменные:
x – гномов захватят гоблины;
y – на гномов нападёт дракон;
z – они утонут в реке;
w – они заблудятся в лесу.
Первому высказыванию соответствует формула x+y+w, второму – y→z и третьему– z&w.
С учётом, что второе и третье высказывания ложны, запишем истинное составное вы-сказывание и упростим его.
(x+y+w)&(y→z)&z&w= (x+y+w)&(y+z)&(z+w)= (x+y+w)&y&z&(z+w)= (x&y&z+y&z&w)&(z+w)= x&y&z+x&y&z&w+y&z&w= x&y&z+y&z&w.
Из полученного выражения видно, что исходное высказывание истинно, когда истин-но x, а y и z – ложны, либо когда истинно w, а y и z – ложны, либо когда x и w одновременно истинны, а y и z – ложны. Возвращаясь к исходной интерпретации, можно сказать, что гно-мам следует приготовиться и к нападению гоблинов, и к переходу через лес.
ЗАДАЧА 2.

Один король как – то подвергся нападению вражеской армии и был осаждён в крепо-сти, в которой были северные и южные ворота. Чтобы выдержать штурм, ему необходимо было точно знать, на какие из этих ворот готовится атака.
Рано утром перед началом штурма к нему привели пленника, захваченного у против-ника. Об этом пленнике было известно, что он либо рыцарь, который всегда говорит правду, либо лжец, который всегда лжёт, и, кроме того, на все вопросы он отвечает только «да» или «нет».
Король быстро понял, что задавать простые вопросы бесполезно. Если бы он спросил: «Назначен ли штурм на северные ворота?» — и получил бы ответ «да», то из этого ответа нельзя было бы сделать правильного вывода. Если бы штурм действительно был назначен на северные ворота, то рыцарь ответил бы «да», а лжец «нет». А если бы на южные, то рыцарь сказал бы «нет», а лжец – «да». Поскольку король не знал, кто перед ним (рыцарь или лжец), то ответ «да» не позволял бы понять, верно ли, что штурм назначен на северные ворота.
Король впал в отчаяние, но присутствующий при допросе логик задал вопрос, с по-мощью которого удалось установить, на какие ворота готовится штурм. Какой это вопрос?

Решение:
Необходимо рассмотреть четыре возможности.
Место штурма Кто пленник Ответ
северные ворота Рыцарь да
северные ворота Лжец да
южные ворота Рыцарь нет
южные ворота Лжец нет
Надо сформулировать вопрос, ответ на который в первых двух случаях будет «да», и «нет» в двух остальных. Пусть вопрос будет таким: «Верно ли, что штурм назначен на юж-ные ворота и ты лжец, или неправда, что штурм назначен на южные ворота и ты рыцарь?»
В первом случае (северные ворота – рыцарь) на первую часть вопроса: «Верно ли, что штурм назначен на южные вопросы и ты лжец?» — рыцарь ответит «нет», потому что на са-мом деле штурм назначен на северные ворота. На вторую часть вопроса: «Верно ли, что не-правда, что штурм назначен на южные ворота и ты рыцарь?» — рыцарь ответит «да», потому что это действительно неправда. Поэтому ответ на весь вопрос будет «да».
Во втором случае (северные ворота – лжец) на первую часть вопроса лжец ответит «да», потому что на самом деле штурм назначен на северные ворота, а лжец говорит неправ-ду. Поэтому независимо от ответа на вторую часть вопроса ответ на весь вопрос будет «да», это следует из определения дизъюнкции.
В третьем случае (южные ворота – рыцарь) на первую половину вопроса рыцарь отве-тит «нет», потому что он не лжец. На вторую половину вопроса он также скажет «нет», по-тому что верно, что штурм назначен на южные ворота и он рыцарь. Значит, ответ на весь во-прос будет «нет».
В четвёртом случае (южные ворота – лжец) на первую половину вопроса лжец отве-тит «нет», потому что это истина. На вторую половину он также скажет «нет», потому что он не рыцарь, значит, это в самом деле неправда, но лжец вместо «да» всегда говорит «нет». От-сюда ответ на весь вопрос будет «нет».
Таким образом, независимо от того, рыцарь это или лжец, каждый из них ответит «да», если штурм назначен на северные ворота, и «нет» — если на южные.
ЗАДАЧА 3.

Менеджер банка должен установить 4 банкомата. В течение каждого дня работы должны выполняться следующие условия:
1. Если работает первый банкомат, то третий банкомат не должен работать, а второй и четвёртый должны.
2. Если работает третий банкомат, то первый и четвёртый не должны работать, а вто-рой должен.
3. Должен работать по крайней мере один банкомат.
Необходимо определить наибольшее число дней, которое могут работать банкоматы при выполнении этих условий, так, чтобы их назначение ни в один из дней не повторялось, а также указать допустимое расписание на каждый день.

Решение:
Максимальное количество дней и соответствующее расписание можно най-ти прямым перебором. При четырёх переменных надо рассмотреть 16 логических возможно-стей. Однако более рационально построить составное высказывание, истинное для заданных условий, а затем преобразовать соответствующую ему формулу к СДНФ. Введём логические переменные:
w – работает первый банкомат;
x – работает второй банкомат;
y – работает третий банкомат;
z – работает четвёртый банкомат.
Первому условию соответствует формула w→x&y&z, а второму- y→w&x&z. Запи-шем формулу истинного составного высказывания, определяющего ежедневную работу бан-коматов в соответствии с первыми двумя условиями: (w→x&y&z)&(y→w&x&z)=(w+x&y&z)&(y+w&x&z). Раскроем скобки и получим: w&y+w&x&z+x&y&z. Учитывая, что выражения
(x&z+x&z+x&z+x&z)=1
(y+y)=1
(w+w)=1
перепишем исходную формулу в виде эквивалентного выражения:
w&y&(x&z+x&z+x&z+x&z)+w&x&z&(y+y)+x&y&z&(w+w)= w&x&y&z+w&x&y&z+w&x&y&z+w&x&y&z+w&x&y&z+w&x&y&z+w&x&y&z+w&x&y&z
исключив из него повторяющиеся элементарные конъюнкции, а также конъюнкцию w&x&y&z, которая противоречит третьему условию, получим выражение в форме СДНФ: w&x&y&z+w&x&y&z+w&x&y&z+w&x&y&z+w&x&y&z.
Анализируя его, можно сказать, что максимальное число дней, при котором нет по-вторений в работе банкоматов, равно пяти, потому что в полученном выражении 5 элемен-тарных конъюнкций, а каждая элементарная конъюнкция этого выражения определяет на-значение банкоматов на один день работы. Допустимое расписание работы может быть та-ким: в первый день работает четвёртый банкомат (это следует из того, что в первую конъ-юнкцию w&x&y&z переменная z входит без отрицания), во второй день – второй банкомат, в третий день должны работать второй и четвёртый, в четвёртый день – второй и третий бан-коматы и, наконец, в пятый день – первый, второй и четвёртый банкоматы.
ЗАДАЧА 4.

Имеется множество из 8 различных букв {A, B, C, D, E, F, G, H}. Один из играющих задумывает любую букву из этого множества. Другой играющий должен угадать эту букву. Он имеет возможность задать три вопроса, ответы на которые должны быть «да» или «нет». Вопросы должны быть заданы независимо один от другого, т. е. второй играющий узнает от-веты только после того, как он задал все три вопроса. Какие вопросы необходимо задать?

Решение:
Если выбрать какую – то букву из заданного множества и спросить, являет-ся ли она задуманной, то в общем случае потребуется 7 вопросов для установления искомой буквы. Чтобы была возможность определять любую букву при помощи трёх вопросов, надо разбить множество на три подмножества. Возьмём три такие подмножества: {B, D, F, H}, {E, F, G, H}, {C, D, G, H}.
Три вопроса будут такими:
1. Входит ли задуманная буква в первое подмножество?
2. Входит ли задуманная буква во второе подмножество?
3. Входит ли задуманная буква в третье подмножество?
Если получено три ответа «да», то задумана буква H, поскольку только она входит во все три подмножества. Если получены «да», «да», «нет», то задумана буква F, потому что только она входит в первое и второе подмножества, но не входит в третье. Если получены ответы «да», «нет», «да», то задумана буква D, потому что только она входит в первое и третье подмножества и не входит во второе, и т. д. Наконец, если получено три ответа «нет», то это буква A, потому что она не входит ни в одно из подмножеств.
Этот пример иллюстрирует прямую аналогию между алгеброй логики и алгеброй множеств. Если вместо операции конъюнкции рассматривать операцию пересечения мно-жеств, а вместо операции дизъюнкции – операцию объединения множеств, то эти операции над подмножествами заданного множества подчиняются тем же законам, что и операции над высказываниями. В то же время любая алгебраическая система, подчиняющаяся этим зако-нам, называется булевой алгеброй. Поэтому если подмножества обозначать переменными, то с помощью операций объединения и пересечения можно строить сложные выражения (фор-мулы), также определяющие некоторые подмножества. Используя булеву алгебру, можно преобразовывать и упрощать формулы.
ЗАДАЧА 5.

Трое друзей, болельщиков автогонок «Формула — 1», спорили о результатах пред-стоящего этапа гонок.
— Вот увидишь, Шумахер не придёт первым, — сказал Джон. — Первым будет Хилл.
— Да нет же, победителем будет, как всегда Шумахер,- воскликнул Ник. — А об Алези и говорить нечего, ему не быть первым.
Питер, к которому обратился Ник, возмутился:
— Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.
По завершении этапа гонок оказалось, что каждое из двух предположений двоих дру-зей подтвердилось, а оба предположения третьего оказались неверными. Кто выиграл этап гонки?

Решение:
Введём обозначения для логических высказываний:
Ш – победит Шумахер;
Х – победит Хилл;
А – победит Алези.
Реплика Ника «Алези пилотирует самую мощную машину» не содержит никакого ут-верждения о месте, которое займёт этот гонщик, поэтому в дальнейших рассуждениях не учитывается.
Зафиксируем высказывания каждого из друзей:
Джон: Ш&Х;
Ник: Ш&А;
Питер: Х;
Учитывая то, что предположения двух друзей подтвердились, а предположения третьего неверны, запишем истинное высказывание:
(Ш&Х)&(Ш&А)&Х+(Ш&Х)&(Ш&А)&Х+(Ш&Х)&(Ш&А)&Х= (Ш+Х)&Ш&А&Х= Ш&А&Х.
Высказывание Ш&А&Х истинно только при Ш=1, А=0, Х=0.
Победителем этапа гонок стал Шумахер.
ЗАДАЧА 6.

По обвинению в ограблении перед судом предстали Иванов, Петров, Сидоров. Следствием установлено следующее:
1. Если Иванов невиновен или Петров виновен, то Сидоров виновен.
2. Если Иванов невиновен, то Сидоров невиновен.
Виновен ли Иванов?

Решение:
Рассмотрим простые высказывания:
A = Иванов виновен,
B = Петров виновен,
C = Сидоров виновен.
Запишем на языке алгебры логики факты, установленные следствием:
(A+B)→C и A→C.
Пусть F(A,B,C) = ((A+B)→C)&(A→C).
Решить задачу – это значит указать, при каких значениях A это сложное высказыва-ние истинно. И если хотя бы в одном случае (при разных значениях B и C) F=1 при A=0 (Иванов невиновен), то у следствия недостаточно фактов для того, чтобы обвинить Иванова в преступлении.
Составим таблицу истинности:

А В С F
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 1

Из таблицы истинности видно, что сложное высказывание истинно только когда A – истинно, т. е. Иванов виновен в ограблении.
ЗАДАЧА 7.

На вопрос, кто из трёх школьников изучал логику, был получен правильный ответ: если изучал первый, то изучал и второй, но неверно, что если изучал третий, то изучал и вто-рой. Кто из учащихся изучал логику?

Решение:
Обозначим через P1, P2, P3, высказывания, состоящие в том, что, соответ-ственно, первый, второй, третий школьник изучали логику. Из условия задачи следует ис-тинность высказывания:
(P1→P2)&(P3→P2).
Воспользуемся тем, что A→B=A+B, и упростим полученное высказывание:
(P1+P2)&P3+P2)=(P1+P2)&(P3&P2)=(P1&P3&P2)+(P2&P3&P2).
Высказывание P2&P2 ложно, а следовательно, ложно и высказывание P2&P3&P2. По-этому истинным является высказывание P1&P3&P2, а это означает, что логику изучал третий учащийся, а первый и второй не изучали.
ЗАДАЧА 8.

Алёша, Боря и Гриша нашли в земле старинный сосуд. Рассматривая удивительную находку, каждый высказал по два предположения:
Алёша: «Это сосуд греческий и изготовлен в V веке».
Боря: «Это сосуд финикийский и изготовлен в III веке».
Гриша: «Это сосуд не греческий и изготовлен в IV веке».
Учитель истории сказал ребятам, что каждый из них прав только в одном из двух предположений.
Где и в каком веке изготовлен сосуд?

Решение:
Рассмотрим простые высказывания:
A = сосуд греческий,
B = сосуд финикийский,
C = сосуд изготовлен в III веке,
D = изготовлен в IV веке,
E = сосуд изготовлен в V веке.
Запишем предположения школьников на языке алгебры логики:
A&E (слова Алёши),
B&C (слова Бори),
A&D (слова Гриши).
Из слов учителя следует, что каждое из этих высказываний ложно, так как каждый мальчик прав только в чём-то одном. Предположим, Алёша угадал, что сосуд греческий (А=1), но ошибся во времени его изготовления (Е=0). В противном случае (верно угадано время изготовления, но неправильно – место) А=0 и Е=1. Следовательно, всегда А+Е=1.
Рассуждая аналогично, получаем ещё два истинных сложных высказывания:
В+С=1,
А+D=1.
Если все эти высказывания логически перемножить, то получится истинное сложное высказывание:
(A+E)&(B+C)&(A+D)=1
Раскроем скобки:
(A&B+A&C+E&B+E&C)&(A+D)=1 (2)
Исходя из того, что сосуд мог быть изготовлен только в одной стране и в одном веке, запишем высказывания заведомо ложные:
A&B=0,
E&C=0.
Получим из (2):
(0+A&C+E&B+0)&(A+D)=1
(A&C+E&B)&(A+D)=1
A&C&A+A&C&D+E&B&A+E&B&D=1 (2´)
Снова запишем высказывания заведомо ложные:
A&A=0,
C&D=0,
E&D=0.
Следовательно:
A&C&A=0,
A&C&D=0,
E&B&D=0.
Подставим в (2´)
0+0+E&B&A+0=1
Значит, Е&B&A=1.
Мы установили, что сосуд финикийский и изготовлен в V веке, что удовлетворяет ус-ловию задачи.
ЗАДАЧА 9.

Брауну, Джонсу и Смиту предъявлено обвинение в соучастии в ограблении банка. Похитители скрылись на поджидавшем их автомобиле. На следствии Браун показал, что преступники скрылись на синем «Бьюике», Джонс сказал, что это был чёрный «Крайслер», а Смит утверждает, что это был «Форд Мустанг», и ни в коем случае не синий. Стало извест-но, что желая запутать следствие, каждый из них указал правильно либо только марку маши-ны, либо только её цвет.
Какого цвета и какой марки был автомобиль?

Решение:
Рассмотрим простые высказывания:
A = машина синего цвета,
B = машина марки «Бьюик»,
C = машина чёрного цвета,
D = машина марки «Крайслер»,
E = машина марки «Форд Мустанг».
Так как либо цвет, либо марка машины каждым из соучастников названа верно, то из их слов можно заключить, что:
A+B=1 (из слов Брауна),
C+D=1 (из слов Джонса),
A+E=1 (из слов Смита).
Если все эти высказывания логически перемножить, то получится истинное высказы-вание:
(A+B)&(C+D)&(A+E) = 1&1&1 =1. (1)
По аналогии с алгеброй чисел выполним преобразование левой части этого выраже-ния:
(A&C&A)+(A&C&E)+(A&D&A)+(A&D&E)+(B&C&A)+(B&C&E)+(B&D&A)+(B&D&E)=1
Запишем заведомо ложные высказывания.
Во — первых:
A&A=0.
Так как разыскиваемый автомобиль определённой марки и цвета, то все логические произведения, содержащие высказывания о разных цветах одного автомобиля, являются ложными:
A&C=0,
D&E=0,
B&E=0,
B&D=0.
Следовательно:
A&C&A=0,
A&C&E=0,
A&D&A=0,
A&D&E=0,
B&C&E=0,
B&D&E=0,
B&D&A=0.
Подставим эти значения в (1):
0+0+0+0+(B&C&A)+0+0+0=1.
Единственное выражение, значение которого может быть истинным, это B&C&A. Действительно, чёрный «Бьюик» удовлетворяет условию задачи.
Следовательно, B&C&A=1, т. е. автомобиль был чёрного цвета марки «Бьюик».
Задача Эйнштейна.
Условие: Есть 5 домов разного цвета, стоящие в ряд. В каждом доме живет по одному человеку отличной от другого национальности. Каждый жилец пьет только один определенный напиток, курит определенную марку сигарет и держит животное. Никто из пяти человек не пьет одинаковые напитки, не курит одинаковые сигареты и не держит одинаковых животных.

Известно, что:
Англичанин живет в красном доме.
Швед держит собаку.
Датчанин пьет чай.
Зеленой дом стоит слева от белого.
Жилец зеленого дома пьет кофе.
Человек, который курит Pallmall, держит птицу.
Жилец среднего дома пьет молоко.
Жилец из желтого дома курит Dunhill.
Норвежец живет в первом доме.
Курильщик Marlboro живет около того, кто держит кошку.
Человек, который содержит лошадь, живет около того, кто курит Dunhill.
Курильщик Winfield пьет пиво.
Норвежец живет около голубого дома.
Немец курит Rothmans.
Курильщик Marlboro живет по соседству с человеком, который пьет воду.
Вопрос: У кого живет рыба?
Решение:
ШАГ 1
По условию, норвежец живёт в первом доме (9). Из (14) следует, что второй дом синий.
Какого цвета первый дом? Он не может быть ни зелёным, ни белым, поскольку дома? этих двух цветов должны располагаться рядом (5). Красным он тоже не может быть, потому что в красном доме живёт англичанин (1). Итак, первый дом жёлтый.
Следовательно, в первом доме курят «Данхел» (7), а во втором доме держат лошадь (11).
Что пьёт норвежец (который живёт в первом, жёлтом, доме и курит «Данхел»)? Это не чай, поскольку чай пьёт датчанин (4). И не кофе, потому что кофе пьют в зелёном доме (3). И не молоко, которое пьют в третьем доме (8). И не пиво, потому что человек, который пьёт пиво, курит «Винфилд» (12). Следовательно, норвежец пьёт воду.
ДОМ 1 2 3 4 5
ЦВЕТ желтый
НАЦИОНАЛЬНОСТЬ норвежец
НАПИТОК вода молоко
СИГАРЕТЫ данхел
ЖИВОТНОЕ лошадь

ШАГ 2
Из (15) следует, что человек, живущий во втором, синем, доме, курит «Мальборо».
Какой национальности человек, живущий во втором, синем, доме, предпочитающий «Мальборо» и держащий лошадь? Это не норвежец — он в первом доме (9). Не англичанин — он в красном доме (1). Не швед — у шведа собака (2). Не немец — немец курит «Ротманс» (13). Значит, во втором доме живёт датчанин и, как следует из (4), пьёт чай.
ДОМ 1 2 3 4 5
ЦВЕТ желтый синий
НАЦИОНАЛЬНОСТЬ норвежец датчанин
НАПИТОК вода чай молоко
СИГАРЕТЫ данхел мальборо
ЖИВОТНОЕ лошадь

ШАГ 3
Зеленый дом не может быть третьим, поскольку в нём пьют кофе, а не молоко (3). Зеленый дом не может быть пятым, поскольку справа от него есть дом (5). Следовательно, зеленый дом — четвёртый. Значит, белый дом — пятый, а красный — третий, и в нём живёт англичанин (1). В зеленом доме пьют кофе, и для белого дома остаётся только пиво. Из (12) следует, что в белом доме курят «Винфилд».
ДОМ 1 2 3 4 5
ЦВЕТ желтый синий красный зеленый белый
НАЦИОНАЛЬНОСТЬ норвежец датчанин англичанин
НАПИТОК вода чай молоко кофе пиво
СИГАРЕТЫ данхел мальборо винфилд
ЖИВОТНОЕ лошадь

ШАГ 4
Где живёт немец, который курит «Ротманс» (13)? Он может жить только в четвёртом, зелёном доме. А значит, человек, который курит «Пал Мал» и разводит птиц, может жить только в третьем, красном доме — это англичанин.
ДОМ 1 2 3 4 5
ЦВЕТ желтый синий красный зеленый белый
НАЦИОНАЛЬНОСТЬ норвежец датчанин англичанин немец
НАПИТОК вода чай молоко кофе пиво
СИГАРЕТЫ данхел мальборо пал мал ротманс винфилд
ЖИВОТНОЕ лошадь птицы

Тогда шведу, у которого собака (2), остаётся пятый дом. По условию (10), кошка живет в первом или в третьем доме, но в третьем доме — птицы, а значит, кошка в первом доме.
Следовательно, рыбку держит немец.

ДОМ 1 2 3 4 5
ЦВЕТ желтый синий красный зеленый белый
НАЦИОНАЛЬНОСТЬ норвежец датчанин англичанин немец швед
НАПИТОК вода чай молоко кофе пиво
СИГАРЕТЫ данхел мальборо пал мал ротманс винфилд
ЖИВОТНОЕ кошка лошадь птицы рыбка собака

Конечно, это решение предполагает, что недостающие в условиях задачи животное и есть искомая рыбка. Кроме того, предполагается, что первый дом — слева. Тем не менее, прямо в условиях это нигде не указано. Многие поэтому утверждают, что единственный правильный ответ — «в задаче не хватает данных», так как мы не можем быть уверены в том, что рыбки, например, вообще живут хотя бы в одном из этих домов. Однако, этим суждением зачастую «покрывают» свою неудачу в решении задачи.
Если предположить, что первый дом находится справа, и в нём живёт норвежец (по условию задачи), то первым слева стоит зелёный, а рядом белый, дальше красный и синий. Разница между первым вариантом решения задачи, в расположении домов по цветам (а в условии об этом ничего не сказано). В итоге решение задачи такое же как и в первом варианте — рыбок разводит немец, пьёт — кофе, курит — Ротманс.

www.openclass.ru
Решение логических задач средствами алгебры логики
Обычно используется следующая схема решения:

изучается условие задачи;
вводится система обозначений для логических высказываний;
конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;
определяются значения истинности этой логической формулы;
из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.
Задача.
Три свидетеля дорожного происшествия сообщили сведения о скрывшемся нарушителе. Боб утверждает, что тот был на красном «Рено», Джон сказал, что нарушитель уехал на синей «Тойоте», а Сэм показал, что машина была точно не красная, и по всей видимости, это был «Форд».
Когда удалось отыскать машину, выяснилось, что каждый из свидетелей точно определил только один из параметров автомобиля. А в другом ошибся, какая и какого цвета была машина у нарушителя?
Ответ записать в виде двух слов, разделенных пробелом: МАРКА, ЦВЕТ.
Решение.
Обозначим высказывания:
A = «машина красного цвета»;
B = «машина была «Рено»;
C = «машина синего цвета»;
D = «машина была «Тойота»;
E = «машина была «Форд».
Согласно условию:
из показаний Боба следует, что A \/ B истинно;
из показаний Джона следует, что C \/ D истинно;
из показаний Сэма следует, что ¬A \/ E истинно.
Следовательно, истинна конъюнкция (A \/ B) /\ (C \/ D) /\ (¬A \/ E) = 1
Раскрывая скобки, получаем:
(A \/ B) /\ (C \/ D) /\ (¬A \/ E) = (A /\ C \/ A /\ D \/ B /\ C \/ B /\ D) /\ ( ¬A \/ E) =
A /\ C /\ ¬A \/ A /\ D /\ ¬A \/ B /\ C /\ ¬A \/ B /\ D /\ ¬A \/ A /\ C /\ E \/ A /\ D /\ E \/ B /\ C /\ E \/ B /\ D /\ E = 1.
Из полученных восьми слагаемых семь (согласно условию) являются ложными. Остается единственное истинное слагаемое:
B /\ C /\ ¬A = 1.
Значит, нарушитель скрылся на автомобиле «Рено» синего цвета.
Ответ: РЕНО, СИНИЙ.
Пример.
Трое друзей, болельщиков автогонок «Формула-1», спорили о результатах предстоящего этапа гонок.
— Вот увидишь, Шумахер не придет первым, — сказал Джон. Первым будет Хилл.
— Да нет же, победителем будет, как всегда, Шумахер, — воскликнул Ник. — А об Алези и говорить нечего, ему не быть первым.
Питер, к которому обратился Ник, возмутился:
— Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.
По завершении этапа гонок оказалось, что каждое из двух предположений двоих друзей подтвердилось, а оба предположения третьего из друзей оказались неверны. Кто выиграл этап гонки?
Решение.
Введем обозначения для логических высказываний:
Ш — победит Шумахер;
Х — победит Хилл;
А — победит Алези.
Реплика Ника «Алези пилотирует самую мощную машину» не содержит никакого утверждения о месте, которое займёт этот гонщик, поэтому в дальнейших рассуждениях не учитывается.
Зафиксируем высказывания каждого из друзей:

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

Высказывание истинно только при Ш=1, А=0, Х=0.
Ответ.
Победителем этапа гонок стал Шумахер.
Задача для самопроверки:
На перемене в кабинете биологии 8 ребят баловались и разбили дорогой микроскоп. Их всех вызвали к директору и выслушали:
Ира: Это Антон разбил.
Наташа: Нет, Антон не бил!
Сергей: А я тоже знаю, что это Наташа разбила!
Антон: Нет, ни Наташа, ни Сергей этого не делали!
Оля: А я видела, что разбил Сергей!
Максим: Это кто-то чужой!
Костя: Это либо Наташа, либо Сергей – больше некому!
Кто разбил микроскоп, если известно, что из этих восьми высказываний истинны только два?
Ответ записать в виде первой буквы имени.

logikinformatik.blogspot.com