Решение задач булевой алгебры

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

В следующих разделах вы найдете другие примеры решений о булевых функциях:

Решения задач по булевым формулам онлайн

Задача 1. Проверить, является ли тавтологией формула: $a & b o(a & b vee c vee ar c)$

Задача 2. Преобразовать данную формулу так, чтобы она содержала только операции тесного отрицания, дизъюнкции и конъюнкции. Пользуясь свойствами операций дизъюнкции и конъюнкции, привести формулу к виду, не содержащему скобок.

$$(overline vee x_2) o (overline sim x_3)overline $$

Задача 3. Показать, что $x_1$ — фиктивная переменная функции $f$ (реализовав для этой цели функцию $f$ формулой, не содержащей явно переменную $x_1$).

Задача 4. Используя приведенные ниже (основные) эквивалентности и соотношения, доказать эквивалентность формул $U$ и $B$.

Задача 5. Классифицировать формулу $overline< (overline o x) vee y>$

Булева алгебра для чайников

Булева алгебра

Булевой алгеброй называется непустое множество $A$ с двумя бинарными операциями $land$ (аналог конъюнкции), $lor $ (аналог дизъюнкции), одной унарной операцией $lnot$ (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для любых a, b и c из множества A верны следующие аксиомы:

Логические операции

В алгебре логики основными (элементарными) операциями являются отрицание, логическое сложение (дизъюнкция), логическое умножение (конъюнкция), импликация, эквивалентность.

Основные формулы по алгебре логики: функции алгебры логики, таблица истинности, основные эквивалентности, преобразование к конъюнкции, дизъюнкции и отрицанию

Приоритет логических операций

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

$$
eg quad wedge quad vee quad o quad leftrightarrow $$

Словесно: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность.

Решение логических задач

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

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

Познакомимся с ними поочередно.

Обычно используется следующая схема решения:

1. изучается условие задачи;

2. вводится система обозначений для логических высказываний;

3. конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;

4. определяются значения истинности этой логической формулы;

5. из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.

Пример 1. Трое друзей, болельщиков автогонок “Формула-1”, спорили о результатах предстоящего этапа гонок.

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

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

Питер, к которому обратился Ник, возмутился:

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

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

Решение. Введем обозначения для логических высказываний:

Ш — победит Шумахер; Х — победит Хилл; А — победит Алези.

Реплика Ника “Алези пилотирует самую мощную машину” не содержит никакого утверждения о месте, которое займёт этот гонщик, поэтому в дальнейших рассуждениях не учитывается.

Зафиксируем высказывания каждого из друзей:

Джон: ¬Ш/Х

Ник: Ш/¬А

Питер: ¬Х

Высказывание Ш / ¬ А/ ¬Х истинно только при Ш=1, А=0, Х=0.

Ответ. Победителем этапа гонок стал Шумахер.

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

Пример 2. В симфонический оркестр приняли на работу трёх музыкантов: Брауна, Смита и Вессона, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе.

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

На каких инструментах играет каждый из музыкантов, если каждый владеет двумя инструментами?

Решение. Составим таблицу и отразим в ней условия задачи, заполнив соответствующие клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание.

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

Из условия 4 следует, что Смит не играет ни на альте, ни на трубе, а из условий 3 и 5, что Браун не умеет играть на скрипке, флейте, трубе и гобое. Следовательно, инструменты Брауна — альт и кларнет. Занесем это в таблицу, а оставшиеся клетки столбцов “альт” и “кларнет” заполним нулями:

Из таблицы видно, что на трубе может играть только Вессон.

Из условий 1 и 2 следует, что Смит не скрипач. Так как на скрипке не играет ни Браун, ни Смит, то скрипачом является Вессон. Оба инструмента, на которых играет Вессон, теперь определены, поэтому остальные клетки строки “Вессон” можно заполнить нулями:

Из таблицы видно, что играть на флейте и на гобое может только Смит.

Ответ: Браун играет на альте и кларнете, Смит — на флейте и гобое, Вессон — на скрипке и трубе.

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

Пример 3. Вадим, Сергей и Михаил изучают различные иностранные языки: китайский, японский и арабский. На вопрос, какой язык изучает каждый из них, один ответил: “Вадим изучает китайский, Сергей не изучает китайский, а Михаил не изучает арабский”. Впоследствии выяснилось, что в этом ответе только одно утверждение верно, а два других ложны. Какой язык изучает каждый из молодых людей?

Решение. Имеется три утверждения:

  1. Вадим изучает китайский;
  2. Сергей не изучает китайский;
  3. Михаил не изучает арабский.

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

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

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

Ответ: Сергей изучает китайский язык, Михаил — японский, Вадим — арабский.

Пример 4. Министры иностранных дел России, США и Китая обсудили за закрытыми дверями проекты соглашения о полном разоружении, представленные каждой из стран. Отвечая затем на вопрос журналистов: “Чей именно проект был принят?”, министры дали такие ответы:

Россия — “Проект не наш, проект не США”;
США — “Проект не России, проект Китая”;
Китай — “Проект не наш, проект России”.

Один из них (самый откровенный) оба раза говорил правду; второй (самый скрытный) оба раза говорил неправду, третий (осторожный) один раз сказал правду, а другой раз — неправду.

Определите, представителями каких стран являются откровенный, скрытный и осторожный министры.

Решение. Для удобства записи пронумеруем высказывания дипломатов:

Россия — “Проект не наш” (1), “Проект не США” (2);
США — “Проект не России” (3), “Проект Китая” (4);
Китай — “Проект не наш” (5), “Проект России” (6).

Узнаем, кто из министров самый откровенный.

Если это российский министр, то из справедливости (1) и (2) следует, что победил китайский проект. Но тогда оба утверждения министра США тоже справедливы, чего не может быть по условию.

Если самый откровенный — министр США, то тогда вновь получаем, что победил китайский проект, значит оба утверждения российского министра тоже верны, чего не может быть по условию.

Получается, что наиболее откровенным был китайский министр. Действительно, из того, что (5) и (6) справедливы, cледует, что победил российский проект. А тогда получается, что из двух утверждений российского министра первое ложно, а второе верно. Оба же утверждения министра США неверны.

Ответ: Откровеннее был китайский министр, осторожнее — российский, скрытнее — министр США.

Приводятся информационные и учебно-методические материалы к решению задач булевой алгебры.

Скачать:

Вложение Размер
reshenie_elementarnyh_zadach_bulevoy_algebry.docx 159 КБ

Предварительный просмотр:

СБОРНИК ЗАДАНИЙ ПО БУЛЕВОЙ АЛГЕБРЕ

Составитель: Чернышев Э.Н. (МБОУ СОШ №3, г. Красный Сулин, 2017г.)

ПОРЯДОК ВЫПОЛНЕЕНИЯ ДЕЙСТВИЙ

4.Импликация и эквиваленция.

Установите истинность высказываний.

«Земля имеет форму куба» ИЛИ «Сентябрь – зимний месяц».

«Земля имеет форму куба» И «Сентябрь – зимний месяц».

«Земля имеет форму шара» ИЛИ «Сентябрь – зимний месяц».

«Земля имеет форму шара» И «Сентябрь – зимний месяц».

«Земля имеет форму шара» ИЛИ «Сентябрь – осенний месяц».

«Земля имеет форму шара» И «Сентябрь – осенний месяц».

НЕ «Земля имеет форму куба» ИЛИ НЕ «Сентябрь – осенний месяц».

НЕ «Земля имеет форму куба» И НЕ «Сентябрь – осенний месяц».

«Земля имеет форму шара» ИЛИ НЕ «Сентябрь – осенний месяц».

«Земля имеет форму шара» И НЕ «Сентябрь – осенний месяц».

Установите истинность высказываний.

  1. Если дважды два – четыре , то четыре равно два умножить на два .
  2. Если ноябрь – зимний месяц , то январь- тоже зимний месяц .
  3. Если Земля – планета , то Солнце – тоже планета .
  4. Если золото – это металл , то железо – это золото .
  5. Если ЕГЭ сдают в 4 классе , то ОГЭ сдают тоже в 4 классе .

Заполните таблицу истинности.

Определите, являются ли сложные высказывания тождественными: A ⇒ B·A; AvB

Построить таблицу истинности

Определите, являются ли сложные высказывания эквивалентными

Для какого имени истинно высказывание:

¬(Первая буква имени гласная -> Четвертая буква имени согласная)

  1. ЕЛЕНА 2) ВАДИМ 3) АНТОН 4) ФЕДОР

Для какого имени истинно высказывание

Первая буква имени согласная ^ (¬Вторая буква имени согласная -> Четвертая буква имени гласная)

1) ИВАН 2)ПЕТР 3) ПАВЕЛ 4) ЕЛЕНА

Составить таблицы истинности для следующих логических выражений:

Переведите на язык логических выражений следующие высказывания:

  1. «Я поеду в Москву, и если встречу там друзей, то мы интересно проведем время».
  2. «Если будет солнечная погода, то ребята пойдут в лес, а если будет пасмурная погода, то ребята пойдут в кино».
  3. «Неверно, что если дует ветер, то солнце светит только тогда, когда нет дождя».
  4. «Если урок информатики будет интересным, то никто из школьников – Миша, Вика и Света – не будет смотреть в окно».
  5. «Неверно, что для того, чтобы человек достиг в жизни высоких результатов, необходимо и достаточно, чтобы он был гением».

В соревнованиях по бегу участвуют Алла, Таня, Валя и Даша. Болельщики высказали предположения о возможных победителях:

  1. Первой будет Таня, Валя будет второй.
  2. Второй будет Таня, Даша – третьей.
  3. Алла будет второй, Даша – четвертой.

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

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

  1. Если Иванов не виновен или Петров виновен, то Сидоров виновен.
  2. Если Иванов не виновен, то Сидоров не виновен.

Кто из подозреваемых участвовал в преступлении?

Виктор, Роман, Юрий и Сергей заняли на математической олимпиаде первые четыре места. Когда их спросили о распределении мест, они дали три таких ответа:

  1. Сергей — первый, Роман — второй;
  2. Сергей — второй, Виктор — третий;
  3. Юрий — второй, Виктор — четвертый.

Как распределились места, если в каждом ответе только одно утверждение истинно?

Брауну, Джонсу и Смиту предъявлено обвинение в соучастии в ограблении банка. В ходе следствия Браун сказал, что преступники были на синем "Бьюике", Джонс сказал, что это был черный "Крайслер", Смит утверждал, что это был "Форд", но не синий. Каждый указал неправильно либо марку, либо цвет автомобиля. Определите истинный цвет и истинную марку автомобиля.

Обсуждая свои возможности по поступлению в вуз, абитуриенты Андрей, Борис и Владимир высказали следующие предположения

Андрей: «Я не смогу поступить, а Владимир — поступит».

Борис: «Владимир не поступит, а Андрей — поступит».

Владимир: «Если я поступлю, то Борис — не поступит или наоборот».

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

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

  • Это английская машина марки "Феррари", — сказал Андрей.
  • Нет, машина итальянская марки "Понтиак", — возразил Денис.
  • Это "Сааб", и сделан он не в Англии, — сказал Марат.

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

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

Алеша: «Это сосуд греческий и изготовлен в V веке».

Боря: «Это сосуд финикийский и изготовлен в III веке ».

Гриша: «Это сосуд не греческий и изготовлен в IV веке».

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

В нарушении правил обмена валюты подозреваются четыре работника банка – A, B, C, D. Известно, что:

  1. Если A нарушил, то и B нарушил правила обмена валюты.
  2. Если B нарушил, то и C нарушил или A не нарушал.
  3. Если D не нарушил, то A нарушил, а C не нарушал.
  4. Если D нарушил, то и A нарушил.

Кто из подозреваемых нарушил правила обмена валюты?

ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ ПО БУЛЕВОЙ АЛГЕБРЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Оцените статью
Topsamoe.ru
Добавить комментарий