Posted in Разное

Задачи на алгебру логики с решениями: Математическое Бюро. Страница 404

Содержание

§ 4. Примеры задач на использование законов алгебры логики и формализацию высказываний — ЗФТШ, МФТИ

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

`bar C vv` (`A` & `С`) `vv`  (`bar(A vv C vv bar(B)`)

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

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

1) Избавиться от операций импликации.

2) Продвинуть отрицание вглубь выражения. То есть применять законы де Моргана, и закон двойного отрицания пока знак отрицания не будет стоять только над переменными (но не над операциями).

После пункта 2 наступает относительная свобода действий. Можно использовать тождества поглощения или раскрывать скобки.

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

  `bar C vv ` (`A`  &  `C`) `vv` (`bar A` & `bar C` & `B`)

Если теперь внимательно посмотреть на выражение, то очевидно, что к первому и третьему слагаемому  можно применить первый закон поглощения, так как отрицание переменной `C` является первым слагаемым и входит в третье в качестве множителя.

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

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

`bar C` `vv` (`A` & `C`)

Применим второй (нестандартный для алгебры) закон дистрибутивности. Получаем: 

(`bar C vv A`) & (`bar C vv C`)

Ко второй скобке применяем закон исключённого третьего, превращаем её в единицу, а затем применяем закон поглощения константы `1` и в итоге получаем выражение: `bar C vv A`

, которое упростить уже нельзя.

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

Обратите внимание, что исходное логическое выражение зависело от трёх переменных (`A, B, C`) , в то время как упрощённое в итоге зависит от двух логических переменных (`A` и `C`). При этом выражения всё равно остаются равносильными! Это происходит потому, что в процессе упрощения применялись законы поглощения. Аналогичный результат мог бы получиться, если в процессе упрощения выражения используются законы поглощения переменных константами. Исчезновение переменной при упрощении означает, что в исходном выражении она является несущественной.

«Решение логических задач средствами алгебры логики»

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

Задачи урока:

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

развивающие – развитие логического мышления учащихся, памяти, внимания, а также интереса к разделу информатики — алгебре логики;

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

Тип урока: проверка знаний и изучение нового материала.

Возраст учащихся: 10-11 класс.

Оборудование урока:

Требования к знаниям и умениям учащихся:

учащиеся должны знать:

  • основные понятия и определения алгебры логики;
  • основные законы алгебры логики;

учащиеся должны уметь:

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

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

План урока:

  1. Организационная часть.
  2. Повторение пройденных тем.
  3. Физкультминутка.
  4. Изучение нового материала.
  5. Закрепление изученного материала.
  6. Подведение итогов урока.
  7. Домашнее задание.

Ход урока

1. Организационная часть

  • приветствие;
  • проверка отсутствующих;
  • постановка целей урока.

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

1. с помощью рассуждений;

2. с помощью таблиц;

3. средствами алгебры логики.

Первым способом мы умеем решать логические задачи с первого класса. Вторым способом мы научились решать на предыдущих уроках. А вот третьим способом – средствами алгебры логики – научимся решать сегодня.

2. Повторение пройденных тем.

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

(Все задачи на повторение пройденной темы решаются учениками на доске с объяснением применяемых правил и законов).

Первое задание. Упростить логическое выражение. (Демонстрируется слайд).

_______________

F =

Решение (используются законы де Моргана, закон двойного отрицания, распределительный закон):

_______________ _____

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

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

Второе задание. Проверить правильность упрощения построением таблиц истинности. (Демонстрируется слайд).

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

Решение:

Таблица истинности для исходного логического выражения

А

В

C

A V B

B V C

F

0

0

0

0

0

1

1

0

0

0

1

0

1

0

1

0

0

1

0

1

1

0

0

1

0

1

1

1

1

0

0

1

1

0

0

1

0

1

1

0

1

0

1

1

1

0

0

1

1

1

0

1

1

0

0

1

1

1

1

1

1

0

0

1

Таблица истинности для упрощенного логического выражения

 

А

В

C

A & C

B V А & C

0

0

0

0

0

0

0

1

0

0

0

1

0

0

1

0

1

1

0

1

1

0

0

0

0

1

0

1

1

1

1

1

0

0

1

1

1

1

1

1

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

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

Третье задание. Построить логическую схему полученного упрощенного логического выражения. (Демонстрируется слайд).

(Продемонстрировать и объяснить работу схемы).

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

Четвертое задание. Записать следующее высказывание в виде логического выражения: «Если я хорошо подготовлюсь по русскому языку, математике и физике, то я получу пятерки или четверки».

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

А – хорошо подготовлюсь по русскому языку;

В – хорошо подготовлюсь по математике;

С – хорошо подготовлюсь по физике;

D – получу пятерки;

Е – получу четверки.

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

F = (A & B & C) —> (D V E)

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

Пятое задание. Решить логическую задачу с помощью рассуждений. (Демонстрируется слайд).

Принцу необходимо спасти принцессу от злого колдуна. Принцесса находится в одной из комнат с надписями на дверях:

  1. В этой комнате сидит тигр.
  2. Принцесса находится в комнате 1.
  3. Тигр сидит в комнате 2.

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

Учитель. Сейчас мы узнаем, есть ли среди нас принцы. Кто поможет принцессе? Если кто-то готов выручить ее, то он должен щелкнуть мышкой по двери и дверь откроется. (Демонстрируется слайд)

III. Физкультминутка. Разгадывание кроссворда за компьютером.

(Учащиеся встают, разминаются, садятся за компьютеры и решают кроссворд, подготовленный в MS Excel. Оценку, выставленную компьютером, ученики заносят в карточку).

IV. Изучение нового материала. (Демонстрируются слайды)

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

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

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

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

Так какая же погода будет завтра? (Ответы учеников)

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

Решение:

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

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

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

С – «Дождь»

б) Запишем логические функции (сложные высказывания) через введенные переменные:

1. Если не будет ветра, то будет пасмурная погода без дождя:

A —> B & C

2. Если будет дождь, то будет пасмурно и без ветра:

С —> B & A

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

B —> C & A

в) Запишем произведение указанных функций:

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 =

= A&B&C

д) Приравняем результат единице, т.е. наше выражение должно быть истинным:

F = A & B & C = 1

е) Проанализируем результат:

Логическое произведение равно 1, если каждый множитель равен 1.

Поэтому:

A = 1; B = 1; C = 1;

Значит: A = 0; B = 0; C = 0;

Ответ: погода будет ясная, без дождя, но ветреная.

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

V. Закрепление изученного материала.

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

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

Учитель. Можно ли раскрыть это преступление? Имея в виду, что у нас каждое преступление раскрывается, и, учитывая, что следователи изучали в школе алгебру логики, с уверенностью можно сказать, что преступники будут наказаны. Кто из вас поможет следствию и правильно вычислит цвет и марку машины, узнаем на следующем уроке, а сейчас вместе напишем логическую функцию.(Учитель помогает детям записать правильно логическое выражение.)

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

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

VI.Подведение итогов урока.

Учитель. Сегодня мы научились решать логические задачи средствами алгебры логики. Мы с вами выяснили, что самым точным способом решения логических задач является изученный нами сегодня способ. Но более простым способом вам показался решение логических задач с помощью таблиц. К сожалению, не все логические задачи можно решить с помощью таблиц, поэтому приходится решать их средствами алгебры логики.

(Поставить оценки наиболее активным ученикам. Собрать индивидуальные карточки для проверки.)

VII. Домашнее задание.

Учитель. Попробуйте решить домашнее задание – задачу об ограблении банка всеми тремя известными вам способами и сравнить результаты.

Задачи на алгебру логики — 10 класс | Материал по информатике и икт (10 класс) по теме:

Логические задачи. Методы решения

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

Петя: Я учусь в школе №24, а Леня – в школе №8;

Леня: Я учусь в школе №24, а Петя – в школе №30;

Коля: Я учусь в школе №24, а Петя – в школе №8.

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

В какой школе учится каждый из мальчиков?

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

1) Сергей – первый, Роман – второй;

2) Сергей – второй, Виктор – третий;

3) Леонид – второй, Виктор – четвертый.

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

Как распределились места?

3. Пять школьников из 5 различных городов приехали в Смоленск для участия в областной математической олимпиаде. «Откуда вы ребята? – спросили мы их. Вот что ответил каждый.

Андреев: Я приехал из Рославля, а Григорьев живет в Гжатске.

Борисов: В Гжатске живет Васильев. Я прибыл из Вязьмы.

Васильев: Из Рославля приехал я, а Борисов – из Ельни.

Григорьев: Я прибыл из Гжатска, а Данилов – из Ярцева.

Данилов: Да, я действительно из Ярцева, Андреев живет в Вязьме.

Мы удивились противоречивости их ответов. Ребята объяснили: «Каждый высказал одно утверждение правильное, а другое ложное. Но по нашим ответам вполне можно установить, откуда мы приехали».

Откуда же приехал каждый из них?

4. 6 спортсменов – Адамов, Белов, Ветров, Глебов, Дронов и Ершов – в проходившем соревновании заняли первые шесть мест, причем ни одно место не было разделено между ними. О том, кто какое место занял, были получены такие высказывания:

«Кажется, первым был Адамов, а вторым – Дронов».

«Нет, на первом месте был Ершов, а на втором – Глебов».

«Вот так болельщики! Ведь Глебов был на 3 месте, а Белов на четвертом».

«И вовсе было не так: Белов был пятым, а Адамов – вторым».

«Вы все перепутали: пятым был Дронов, а перед ним Ветров»,

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

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

5. Три друга, Андрей (А), Васил (В) и Стефан (С), получили три путевки на три смены в спортивный лагерь. Андрей имеет возможность поехать в лагерь в первую или вторую смену. Васил – в первую или третью, а Стефан – во вторую или третью. Можно ли удовлетворить желания всех троих и сколькими способами?

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

Какого цвета и марки был автомобиль?

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

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

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

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

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

Где и в каком веке изготовлен сосуд?

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

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

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

Виновен ли Иванов?

Ответ

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

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

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

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

10. Алик, Слава и Борис – страстные болельщики. Их часто можно видеть на стадионе. На вопрос, были ли они на последнем футбольном матче, друзья ответили так:

Слава: Алик без Бориса на матчи не ходит.

Алик: Борису и Славе очень хотелось попасть на матч, но удалось это лишь одному из них.

Борис: Алик и Слава – большие любители футбола и кто-то из них обязательно бывает на каждом матче, а иногда случается – и оба; но не было еще случая, чтобы Слава был на матче, а Алика не было.

Кто же был на последнем матче?

11. Один из пяти братьев разбил окно.

Андрей сказал: «Это или Витя, или Толя».

Витя сказал: «Это сделал не я и не Юра».

Дима сказал: «Нет, один из них сказал правду, а другой неправду».

Юра сказал: «Нет, Дима, ты не прав».

Их отец, которому можно верить, уверен, что не менее 3-х братьев сказали правду.

Кто разбил окно?

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

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

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

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

С помощью алгебры логики определить погоду на завтра.

13. На съемки итальянского художественного фильма были приглашены 4 кинозвезды: из Голливуда (Г), Испании (И), Японии (Я) и Канады (К). В ответ на приглашение кинозвезды заявили:

1) Если кинозвезда И не будет участвовать в съемках, то К от съемок тоже откажется.

2) Если И будет сниматься в фильме, то в нем будут сниматься Я и К.

Режиссеру непременно хотелось, чтобы из 2-х кинозвезд Г и К участвовала хотя бы одна, го Г от съемок отказалась.

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

Снималась ли в фильме японская кинозвезда?

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

А) С не нарушил, если нарушили правила обмена А или В;

В) если В не нарушил, то нарушили С и D;

С) неверно, что D нарушил правила обмена валюты.

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

15. Три приятеля: Петя, Вася и Саша учатся в Математическом, программистском, Химическом колледжах. Каждый учится в одном колледже. Если Петя математик, то Саша не программист. Если Вася не программист, то Петя математик. Если Саша не математик, то Вася – химик. Кто Петя, если все утверждения верны?

16. Даны 3 посылки:

1) Если Иван – брат Марьи или Иван – сын Марьи, то Иван и Марья – родственники.

2) Иван и Марья – родственники.

3) Иван – не сын Марьи.

Можно ли вывести следствие, что «Иван – брат Марьи»?

17. Петя, Вася, Дима, Коля и Гена хотят (каждый по отдельности) поехать в одну из перечисленных ниже стран, где они не были. При этом:

1) Петя был в Китае и Англии;

2) Вася Был в Китае и во Франции;

3) Дима хочет поехать только в США;

4) Коля не был нигде;

5) Гена был во Франции и Алжире.

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

18. Петя, Миша, Ваня, Коля, Дима должны одновременно поехать в города Нальчик, Москву, Серпухов, Тольятти, Норильск. При этом:

1) Петя должен ехать только в Нальчик, Москву или Норильск;

2) Миша должен ехать только в Москву или Тольятти;

3) Ваня должен ехать только в Серпухов или Тольятти;

4) Коля может ехать в любой город;

5) Дима не может ехать вместе с Ваней или Петей в Москву.

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

19. Три подразделения А, В и С торговой фирмы стремились получить по итогам года прибыль. Экономисты высказали следующие предположения:

— подразделение А получит прибыль, а также получит прибыль либо подразделение В, либо подразделение С;

— либо подразделение С получит прибыль, либо получат прибыль подразделения А и В;

— получение прибыли подразделением С не является необходимым условием получения прибыли подразделениями А и В.

По завершению года оказалось, что одно из трех предположений ложно.

Это означает, что прибыль получили:

1) А, С; 2) А,В,С; 3) А,В; 4) В,С; 5) В.

20. Иванов, Дмитриев и Степанов преподают различные предметы – химию, биологию и физику в школах Москвы, Ленинграда и Киева. Известно, что:

1) Иванов работает не в Москве, а Дмитриев – не в Ленинграде;

2) москвич преподает не физику;

3) тот, кто работает в Ленинграде, преподает химию;

4) Дмитриев преподает не биологию.

Какой предмет и в каком городе преподает каждый из товарищей?

21. В купе одного из вагонов поезда Москва-Одесса ехали: москвич, ленинградец, туляк, киевлянин, харьковчанин и одессит. Их фамилии начинались буквами А, Б, В, Г, Д, Е.

В дороге выяснилось, что:

1) А и москвич – врачи, Д и ленинградец – учителя, а туляк и В – инженеры.

2) Б и Е – участники Отечественной войны, а туляк в армии не служил;

3) харьковчанин старше А, одессит старше В, Е – самый молодой;

4) Б и москвич сошли в Киеве, а В и харьковчанин в Виннице.

Определить начальную букву фамилии и профессию каждого из пассажиров.

22. В одном автобусе ехали на конференцию 4 ученых: Иванов, Петров, Кошкин и Чашкин. Среди них были историк, биолог, физик, химик. Каждый взялся прочитать доклад коллеги. Все углубились в чтение. Петров взял доклад Чашкина, но тут же поменялся с Ивановым. Историк читал доклад по химии. Биолог сказал, что не будет читать доклад по физике. Чашкин не биолог. Никто не читал свой же доклад. Кто кем был?

23. «Неприятная история». В одном из классов школы разбито окно. Выбить стекло мог только кто-нибудь из четырех учеников: Леня, Дима, Толя и Миша. При опросе учеников каждый их них дал по три ответа.

Леня. 1) Я не виноват. 2) Я даже не подходил к окну. 3) Миша знает, кто это сделал.

Дима. 1) Стекло разбил не я. 2) С Мишей я не был знаком до поступления в школу. 3) Это сделал Толя.

Толя. 1) Я не виновен. 2) Это сделал Миша. 3) Дима говорит неправду, утверждая, что я разбил стекло.

Миша. 1) Я не виноват. 2) Стекло разбил Леня. 3) Дима может поручиться за меня, так как знает меня очень давно.

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

24. Кто из людей A, B, C и D играет, а кто не играет в шахматы, если известно следующее:
а) если А или В играет, то С не играет;
б) если В не играет, то играют С и D;
в) С играет.

Решение логических задач — как решать задачи на логику

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

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

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

Самое главное в решении логических задач

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

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

Все задачи на развитие логики можно разделить на группы:

  • Математические ребусы;
  • Задачи на истинность утверждений;
  • Задачи на перемещение, взвешивание или переливание;
  • Задачи, которые решаются с конца;
  • Работа с множествами;
  • Задачи на сопоставление «Кто есть кто?»

Выбор способа решения зависит от того, к какой группе относится задание.

Известные техники решения логических задач

  1. Табличный метод (таблицы соответствий, истинности, совмещенные, кубические):
    таблицы создают наглядность, прозрачность рассуждений, помогают сделать верные выводы.
  2. Применение законов из алгебры логики: вводятся обозначения для простых высказываний и преобразовываются в некую формулу.
  3. Метод рассуждений: подходит для решения простых задач с небольшим количеством объектов. Последовательное рассуждение над каждым условием задачи приводит к правильному выводу.
  4. Черчение блок-схем: способ, подходящий для решения задач на переливание, взвешивание. Рисуется схема, на которой отмечают последовательность действий и результат, полученный при их выполнении.
  5. Графический метод: подходит для решения задач на объединение или пересечение множеств. Самый популярный графический метод называется «Круги Эйлера». Нарисованная геометрическая схема наглядно показывает отношение между множествами.
  6. Метод «математический бильярд»: используется для решения задач на переливание жидкостей. Вычерчивается траектория движения бильярдного шара, который отталкивается от бортов стола в форме параллелограмма.

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

Табличный метод

Условия задачи и результаты записываем в специальную таблицу. На пересечении строк и столбцов ставим «+», если утверждения не противоречат друг другу и «-», если они расходятся.

Задача:

У Сони, Маши, Антона, Кости и Юры есть домашние животные. У каждого из ребят живет или собака, или кошка, или попугай. Вот только девочки собак не держат, а у мальчиков нет попугаев. У Сони и Маши разные питомцы, а вот у Маши с Антоном – одинаковые. У Сони нет кошки. У Кости с Юрой живут одинаковые животные, а у Антона с Костей – разные. Какие животные живут у каждого?

Решение:

Чертим таблицу, где названия столбцов – имена ребят, а названия строк – животные. Ставим в каждой ячейке знаки «+» или «-», опираясь на условия задачи:

1. Девочки собак не держат (ставим «-» на пересечении этих ячеек).
2. У мальчиков нет попугаев (в этих ячейках тоже ставим «-»).
3. У Сони нет кошки (ставим «-»).
4. Значит, у Сони есть попугай (ставим «+»).
5. У Сони и Маши разные питомцы. Получается, у Маши нет попугая (ставим «-»), зато есть кошка (ставим «+»).
6. У Маши с Антоном одинаковые животные. Значит, у Антона тоже живет кошка (ставим «+») и нет собаки (ставим «-»).
7. У Антона с Костей разные питомцы, выходит, что у Кости нет кошки (ставим «-»), зато есть собака (ставим «+»).
8. У Кости с Юрой одинаковые животные, значит у Юры тоже собака (ставим «+»), а не кошка (ставим «-»).

Так мы узнали, какие питомцы живут у каждого из ребят (ячейки со знаком «+»).

Ответ: У Сони попугай, у Маши и Антона кошки, у Кости и Юры собаки.

Круги Эйлера

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

Задача:

Всему классу задали на лето читать книжки. В списке литературы были такие произведения, как «Робинзон Крузо» Даниэля Дефо и «Белый клык» Джека Лондона. Известно, что 15 человек из класса прочитали «Робинзон Крузо», а остальные 11 – «Белый клык». Но среди них были 6 ребят, которые прочитали обе книги. Сколько человек прочитало только «Белый клык»?

Решение:

Чертим два круга, каждый из которых – множество детей, прочитавших определенную книгу, а пересечение кругов – дети, прочитавшие обе книги.

1. 15 – 6 = 9 – дети, которые прочитали только «Робинзон Крузо».
2. 11 – 6 = 5 – дети, которые читали лишь «Белый клык».

Ответ: 5 человек.

Метод рассуждений

Поочередно рассматриваем каждое из условий задачи и делаем логические выводы.

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

Решение:

1. Больше всего букв в слове «оранжевая», значит она третья по счету.
2. Если зеленая ваза стоит между оранжевой и розовой, значит, она будет второй в ряду, так как если ее поставить четвертой, то не останется места для розовой.
3. Соответственно, розовая будет стоять первой.
4. Остается голубая, она будет четвертой, то есть последней.

Ответ: голубая ваза.

Метод рассуждений «с конца»

Начинаем раскручивать клубок с конца, а затем сопоставляем результат с условиями задачи.

Задача:

Маме, папе и сыну вместе 125 лет. Когда родился сын, маме был 21 год. А папа старше мамы на 2 года. Сколько лет сейчас каждому из них?

Решение:

1. 21+2= 23 — было папе ( значит вместе родителям было 44 года)
2. (125 — 44) : 3 = 27 — возраст сына
3. 27 + 21 = 48 — возраст мамы
4. 48 + 2 = 50 — возраст папы

Ответ: 27, 48 и 50 лет.

Мы рассмотрели самые популярные и доступные методы, с помощью которых можно легко справиться с заданием. Главное – подобрать подходящий способ решения, который быстро приведет к правильному результату.

Для этого необходимо регулярно практиковаться и развивать свои способности. Отточить навыки решения подобных логических задач и многих других вы можете с помощью образовательной онлайн-платформы «Умназия».

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

Поробуйте решить задачу Умназии прямо сейчас!

Попробовать

Математика

Умназисты соревновались в поедании пирожков. Соревнование длилось ровно 45 минут. За это время все соревнующиеся в сумме съели 179 пирожков.

Посмотри на информацию о соревнующихся на рисунке. Можешь ли ты сказать, кто из умназистов занял почётное третье место?

Выбери ответ:

Третье место заняла Ума Коала.

Третье место занял Мышлен.

Третье место занял Грамотигр.

Третье место занял Ква-Квариус.

Третье место заняла Сообразебра.

ответить

Логика решения:

Мы знаем, что Мышлен ел по 1 пирожку в минуту, значит за 45 минут соревнования он съел 45 пирожков (1 х 45 = 45).

Если Мышлен съел на 10 пирожков больше, чем Сообразебра, то Сообразебра съела 35 пирожков (45 – 10 = 35).

Если Ума-Коала съела на 5 пирожков меньше, чем Сообразебра, то Ума-Коала съела 30 пирожков (35 – 5 = 30).

Чтобы выяснить, сколько съели Грамотигр и Ква-Квариус, сложим все пирожки, которые съели Мышлен, Ума-Коала и Сообразебра. Получается 45 + 35 + 30 = 110 пирожков.

От общего количества съеденных пирожков вычтем съеденное тремя умназистами: 179 – 110 = 69. Значит, Ква-Квариус и Грамотигр вместе съели 69 пирожков.

Из условия мы знаем, что Грамотигр съел пирожков в 2 раза больше, чем Ква-Квариус.

Допустим, Ква-Квариус съел 23 пирожка, тогда Грамотигр съел в два раза больше, то есть 23 х 2 = 46 пирожков.

Теперь снова сложим их пирожки, чтобы проверить себя: 23 + 46 = 69. Сходится.

Значит, Грамотигр (46 пирожков) занял первое место, Мышлен (45 пирожков) – второе, а Сообразебра (35 пирожков) – третье.

Если вам понравилось, было весело интересно и полезно, то ждем вас на нашей онлайн платформе!
Умназия сегодня — это:

1. Онлайн тренажер развития навыков мышления — логики, внимания, эрудиции.
2. Программа «Культурный код» по развитию кругозора. Для самых любознательных и тех, кого кажется уже ничем не удивить!
3. Курсы развития памяти. Хотите чтобы Ваш ребенок без труда учил стихи, запоминал иностранные слова и всегда помнил про день рождения бабушки? На курсах покажем и расскажем как же этого достичь.
4. Пять ступеней финансовой грамотности. Увлекательная история героя, которая полностью зависит от действий ребенка и не имеет определенного результата. Сможет ли он пройти все финансовые ловушки и освоить пятую ступень?

Ждем вас, будет весело и интересно!

Математика и логика для детей 7-13 лет

Развиваем логическое мышление через решение сюжетных математических задач в интерактивном игровом формате

узнать подробнее

Читайте также:

 

Math.ru

Семен Григорьевич Гиндикин

М.: Наука, 1972. 288 с.
Тираж 50000 экз.

Загрузить (Mb)
djvu (3.22) pdf (-) ps (-) html (-) tex (-)

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

Содержание

Предисловие.
Путеводитель и указания к пользованию книгой.

§ 1. Операции над высказываниями. Задачи, указания и решения.

§ 2. Функции алгебры логики; нормальные формы. Задачи, указания и решения.

§ 3. Закон двойственности в алгебре логики. Задачи, указания и решения.

§ 4. Арифметические операции в алгебре логики. Задачи, указания и решения.

§ 5. Монотонные функции алгебры логики. Задачи, указания и решения.

§ 6. Функционально замкнутые классы и теорема Поста. Задачи, указания и решения.

§ 7. Общая теория функционально замкнутых классов. Задачи, указания и решения.

§ 8. Схемы из функциональных элементов. Задачи, указания и решения.

§ 9. Релейно-контактные схемы. Оценки сложности схем. Задачи, указания и решения.

§ 10. Элементы вероятностной логики. Задачи, указания и решения.

§ 11. Многозначные логики. Задачи, указания и решения.

§ 12. Логика предикатов. Задачи, указания и решения.

Приложение.

Литература.
Предметный указатель.

Загрузить (Mb)
djvu (3.22) pdf (-) ps (-) html (-) tex (-)


Урок по информатике ( 8 класс) на тему «Решение задач алгебры логики»

Тема: Решение задач на тему «Алгебра логики»

Цели:

образовательная – знакомство учащихся с методами решения логических задач;

развивающие – развитие логического мышления учащихся, памяти, внимания, интеллектуальных способностей средствами ИКТ, а также интереса к разделу информатики — алгебре логики;

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

Ход урока

Рассмотрим примеры решения задач различными способами

Пример 1
Проверить равносильность выражений А ~ E и (Ā ∧ Ē) v (A ∧ E).

Решение. Для проверки следует создать таблицу истинности, содержащую столько строк, сколько возможно наборов значений переменных, входящих в выражение. Для двух переменных (А и E) количество наборов равно четырем. К двум столбцам для значений переменных (А и E) нужно присовокупить количество столбцов, равное количеству операций в выражении. Таким образом, необходимо создать таблицу, содержащую 4 строки и 7 столбцов.

Заполним первые 2 столбца (А и E) всеми сочетаниями значений переменных. Запишем в качестве заголовков столбцов все операции выражения в порядке их выполнения (в соответствии с приоритетами и скобками). Рассчитаем значения этих операций: сначала выражения в скобках, затем результат их сложения.

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

Основные законы алгебры логики

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

Нормальная форма выражения содержит только операции отрицания, конъюнкции и дизъюнкции и не содержит отрицания выражений и двойных отрицаний.

Для упрощения используют равносильные преобразования, которые иначе называют основными законами алгебры логики.

Тождественные преобразования логических выражений

Для всех тождественных преобразований выполняется закон двойственности: если в формуле преобразования заменить конъюнкцию на дизъюнкцию, дизъюнкцию — на конъюнкцию, значения 1 — на 0, 0 — на 1, то закон, сформулированный для конъюнкции, примет форму аналогичного закона для дизъюнкции, и наоборот.

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

Пример 2
Выбрать выражение, которое равносильно выражению (A ∧ B) v (Ā ∧ B).

1) A         2) A ∧ B          3) Ā ∧ B           4) B

Решение. В соответствии с законом склеивания (A ∧ B) v (Ā ∧ B) = B, следовательно, исходное выражение равносильно выражению В.
Ответ: 4) В.

ОПРЕДЕЛЕНИЕ ЗНАЧЕНИЙ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ

Выражения, которые принимают логические значения (истина или ложь) в результате выполнения операций сравнения (больше >, меньше <, больше или равно ≥, меньше или равно ≤, равно =, не равно ≠), также являются логическими выражениями. Кроме операций сравнения и логических операций такие выражения могут включать функции и алгебраические операции. Приоритет выполнения этих операций таков:

  1. Вычисление значений функций.

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

  3. Выполнение операций сравнения (в порядке записи).

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

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

Пример 3
Для какого из приведенных ниже значений числа М истинно следующее выражение?
¬М ≥ 10 ∧ M > 3

1) 1          2) 2         3) 3        4) 4

Решение. В соответствии с приоритетами операций сначала следует выполнить операции сравнения, затем отрицания, а потом — конъюнкцию. Отрицанием высказывания М ≥ 10 является высказывание М < 10. Получим выражение М < 10 ∧ M > 3. Для того чтобы это выражение (конъюнкция) было истинным, должны выполняться (т. е. быть истинными) оба неравенства. Следовательно, значение М должно быть больше 3, но меньше 10. Среди предложенных значений этому условию удовлетворяет только одно — число 4.
Ответ: 4) 4.

Задачи, подобные предыдущему примеру, можно решать и с помощью таблиц истинности.

Пример 4
Для какого из приведенных ниже значений числа М истинно следующее выражение?
¬М ≥ 10 ∧ M > 3

1) 1           2) 2         3) 3        4) 4

Решение. Составим таблицу истинности: все операции выражения укажем в столбцах таблицы, все предложенные значения М укажем в ее строках. Рассчитаем значения таблицы:

Последний столбец содержит результат всего выражения. Истинным оно будет только для значения числа М, равного 4.
Ответ: 4) 4.

Пример 5
В табличной форме представлены ежемесячные данные о продаже групп товаров за полгода. Сколько групп товаров демонстрировали рост продаж в весенние месяцы или вышли на уровень свыше 80 % в июне?

Решение. Переформулируем условие задачи: необходимо найти группы товаров, для которых (Март < Апрель) ∧ (Апрель < Май) v (Июнь > 80).

Введем обозначения:
А = (Март < Апрель)
В = (Апрель < Май)
С = (Июнь > 80)

Тогда выражение можно записать как А ∧ В v С.

Логическое выражение состоит из одной конъюнкции и одной дизъюнкции. Значение выражения конъюнкции истинно только тогда, когда истинны оба составляющие его простых выражения ((Март < Апрель) и (Апрель < Май)). Значение выражения дизъюнкции будет истинным, если хотя бы одно из составляющих его простых высказываний будет истинным.

Составим таблицу истинности для исходных данных.

Логическому выражению удовлетворяют 3 записи — 4–я, 6–я и 7–я.
Ответ: 3.

Домашнее задание: повторить правила.

«Основы логики» — 9 класс

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

Дистрибутивность умножения относительно сложения Дистрибутивность сложения относительно умножения

аb + ас = а(b+с) — в алгебре

(А&В)v(A&С)=A&(ВvС) (А v В) & (А v С) = А v (В & С)

Дистрибутивность умножения относительно сложения Дистрибутивность сложения относительно умножения
аb + ас = а(b+с) — в алгебре 
(А&В)v(A&С)=A&(ВvС) (А v В) & (А v С) = А v (В & С)

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

(А & В) v (А & В).

Воспользуемся законом дистрибутивности и вынесем за скобки А:

(А & В) v (А & В) = А & (В v В).

По закону исключенного третьего В v В =1, следовательно:

А & (В v В) = А & 1 = А.

Условие задачи. В школе-новостройке в каждой из двух аудиторий может находиться либо кабинет информатики, либо кабинет физики. На дверях аудиторий повесили шутливые таблички. На первой повесили табличку «По крайней мере, в одной из этих аудиторий размещается кабинет информатики», а на второй аудитории — табличку с надписью «Кабинет физики находится в другой аудитории». Проверяющему, который пришел в школу, известно только, что надписи на табличках либо обе истинны, либо обе ложны. Помогите проверяющему найти кабинет информатики. Решение задачи. Переведем условие задачи на язык логики высказываний. Так как в каждой из аудиторий может находиться кабинет информатики, то пусть: А = «В первой аудитории находится кабинет информатики»; Б = «Во второй аудитории находится кабинет информатики».

Отрицания этих высказываний:

А= «В первой аудитории находится кабинет физики»; В = «Во второй аудитории находится кабинет физики».

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

X = АvВ.

Высказывание, содержащееся на табличке на двери второй аудитории, соответствует логическому выражению:

У = А.

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

(X &Y) v(X & Y) = 1. Подставим вместо X и У соответствующие формулы:

(X & Y) v (X & Y) = ((А v В) & А) v ((А v В) & А). Упростим сначала первое слагаемое. Всоответствии с законом дистрибутивности умножения относительно сложения:

(А v В) & А = А & А v В & А. В соответствии с законом непротиворечия:

А & А v В & А = О v В & А.

Упростим теперь второе слагаемое. В соответствии с первым законом де Моргана и законом двойного отрицания:

(А v В) &А=А&В&А = А&А&В.В соответствии с законом непротиворечия:А&А&В=0&В = 0. В результате получаем:

(О v В & А) v 0 = В & А.

Полученное логическое выражение оказалось простым и поэтому его можно проанализировать без построения таблицы истинности. Для того чтобы выполнялось равенство В&А = 1,В и А должны быть равны 1, то есть соответствующие им высказывания истинны.

Ответ: В первой аудитории находится кабинет физики, а во второй — кабинет информатики.

Булева алгебра и логическое упрощение

Почему в цифровой электронике используется логическая алгебра и логическое упрощение?

В этом разделе вы можете выучить и попрактиковаться в вопросах по цифровой электронике на основе «Булевой алгебры и упрощения логики» и улучшить свои навыки, чтобы пройти собеседование, конкурсные экзамены и различные вступительные испытания (CAT, GATE, GRE, MAT, Bank Exam, Железнодорожный экзамен и т. Д.) С полной уверенностью.

Где я могу получить вопросы и ответы по булевой алгебре и логическому упрощению по цифровой электронике с пояснениями?

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

Где я могу получить вопросы и ответы на собеседовании по булевой алгебре и логическому упрощению (тип цели, множественный выбор)?

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

Как решить задачи булевой алгебры и логического упрощения цифровой электроники?

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

Упражнение :: Булева алгебра и логическое упрощение — общие вопросы

2.

Определите значения A, B, C и D, при которых сумма равна нулю.

A. A = 1, B = 0, C = 0, D = 0
B. A = 1, B = 0, C = 1, D = 0
C. A = 0, B = 1, C = 0, D = 0
D. A = 1, B = 0, C = 1, D = 1

Ответ: Вариант Б

Пояснение:


Учебник по булевой алгебре и примеры булевой алгебры

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

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

Пример булева алгебры №1

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

Первые наблюдения говорят нам, что схема состоит из логического элемента И-НЕ с 2 входами, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с 2 входами и, наконец, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с 2 входами на выходе. Поскольку в цепи только 2 входа, обозначенных A и B, может быть только 4 возможных комбинации входа (2 2 ), а именно: 0-0, 0-1, 1-0 и, наконец, 1-1. . Построение логических функций каждого элемента в табличной форме даст нам следующую таблицу истинности для всей логической схемы, представленной ниже.

Входы Выход на
А B С D Q
0 0 1 0 0
0 1 1 1 1
1 0 1 1 1
1 1 0 0 1

Из приведенной выше таблицы истинности столбец C представляет функцию вывода, сгенерированную логическим элементом И-НЕ, а столбец D представляет функцию выхода логического элемента Ex-OR.Оба этих двух выходных выражения затем становятся входным условием для логического элемента Ex-NOR на выходе.

Из таблицы истинности можно видеть, что выход на Q присутствует, когда любой из двух входов A или B находится на логической 1. Единственная таблица истинности, которая удовлетворяет этому условию, — это таблица логики ИЛИ. Таким образом, вся вышеуказанная схема может быть заменена одним единственным вентилем OR с 2 входами .

Пример булева алгебры №2

Найдите выражение булевой алгебры для следующей системы.

Система состоит из ворот И, ИЛИ, и, наконец, ворот ИЛИ. Выражение для логического элемента И — A.B, а для логического элемента ИЛИ — A + B. Оба этих выражения также являются отдельными входами для логического элемента ИЛИ, который определяется как A + B. Таким образом, окончательное выходное выражение имеет вид:

Выход системы задается как Q = (A.B) + (A + B), но обозначение A + B такое же, как обозначение Де Моргана A.B. Затем подставляем A.B в выходное выражение дает нам окончательную выходную нотацию Q = (A.B) + (A.B), которая является логической нотацией для шлюза Exclusive-NOR, как показано в предыдущем разделе.

Входы Промежуточные продукты Выход
B А A.B А + В Q
0 0 0 1 1
0 1 0 0 0
1 0 0 0 0
1 1 1 0 1

Затем всю схему, указанную выше, можно заменить только одним единственным шлюзом Исключающее ИЛИ, и действительно шлюз Исключающее ИЛИ состоит из этих отдельных функций вентилей.

Пример булева алгебры №3

Найдите выражение булевой алгебры для следующей системы.

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

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

Выход логического элемента И с 3 входами имеет только логическую «1», когда ALL входы ворот имеют ВЫСОКИЙ уровень на логическом уровне «1» (A.B.C). На выходе нижнего логического элемента ИЛИ будет только «1», когда один или оба входа B или C находятся на логическом уровне «0». Выходной сигнал логического элемента И с двумя входами равен «1», когда вход A равен «1», а входы B или C имеют значение «0». Тогда на выходе Q будет только «1», когда входы A.B.C равны «1» или A равны «1», а оба входа B или C равны «0», A.(В + С).

При использовании «теоремы де Моргана » входы B и вход C компенсируются, так как для получения выхода на Q они могут быть либо на логической «1», либо на логическом «0». Тогда это просто оставляет вход A в качестве единственного входа, необходимого для вывода в Q, как показано в таблице ниже.

Входы Промежуточные продукты Выход
С B А A.B.C B С Б + К А.(В + С) Q
0 0 0 0 1 1 1 0 0
0 0 1 0 1 1 1 1 1
0 1 0 0 0 1 1 0 0
0 1 1 0 0 1 1 1 1
1 0 0 0 1 0 1 0 0
1 0 1 0 1 0 1 1 1
1 1 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 1

Затем мы можем видеть, что вся логическая схема, указанная выше, может быть заменена только одним единственным входом, обозначенным «A», тем самым сокращая схему из шести отдельных логических вентилей до одного единственного куска провода (или буфера).Этот тип анализа схем с использованием булевой алгебры может быть очень мощным и быстро идентифицировать любые ненужные логические вентили в цифровой логической схеме, тем самым уменьшая количество требуемых вентилей, потребляемую мощность схемы и, конечно же, стоимость.

(PDF) Нахождение всех решений проблемы логической выполнимости, если таковые имеются, с помощью решения логического уравнения

Нахождение всех решений проблемы логической выполнимости, если есть, с помощью решения логического уравнения 31

новый алгоритм поиска выполнимости, Труды

Международной конференции IEEE / ACM 1996 года по

Computer-Aided Design, стр.220-227 (1997).

Баярдо, младший, Р. Дж., И Шраг, Р., Использование методов просмотра CSP —

назад для решения реальных экземпляров SAT,

Proceedings of the AAAI / IAAI, pp. 203-208, (1997).

Москевич, М. В., Мэдиган, К. Ф., Чжао, Ю.,

Чжан, Л. и Малик, С., Чафф: Разработка эффективного решателя SAT

. Материалы 38-й ежегодной конференции по автоматизации проектирования ACM

, стр. 530-535

(2001).

Гольдберг Е., Новиков Ю., Быстрый и надежный SAT-решатель

, Дискретная прикладная математика, 155 (12):

1549-1561 (2002).

Эн, Н. и Серенссон, Н., Расширяемый решатель SAT-

, В: Теория и приложения выполнимости

Тестирование, стр. 502-518, Springer, Берлин-Гейдельберг,

Германия (2004).

Махаджан, Ю.С., Фу, З. и Малик, С., Zchaff2004 ,:

Эффективный спутниковый решатель.В теории и приложениях

Тестирование выполнимости, стр. 360-375, Springer, Berlin-

Heidelberg (2005).

Де Моура, Л. и Бьёрнер, Н., Z3: эффективный решатель SMT

. В инструментах и ​​алгоритмах построения

и анализа систем, стр. 337-340. Springer,

Берлин-Гейдельберг, Германия (2008 г.).

Ярвисало, М., Ле Берре, Д., Руссель, О. и Саймон,

L., Международные соревнования по поисковым решениям, AI

Magazine, 33 (1): 89-92 (2012).

Макницкас А.А. Формулировка линейного программирования

задачи логической выполнимости // В: G.-C. Ян и др.

др. (Редакторы), Transactions on Engineering

Technologies, Lecture Notes in Electrical Engineering

275, Springer Science + Business Media, Dordrecht,

Germany (2014).

Мурога С., Логический дизайн и теория коммутации,

Уайли, Нью-Йорк, Нью-Йорк, США (1979).

Маркес-Силва, Дж., Практическое применение логической выполнимости

. На 9-м международном семинаре IEEE по системам дискретных событий

(WODES 2008), стр. 74-80

(2008).

Де Моура, Л. и Бьёрнер, Н., Выполнимость по модулю

теорий: Введение и приложения,

Сообщения ACM, 54 (9), 69-77 (2011).

Prügel-Bennett, A. and Tayarani-Najaran, MH

Максимальная выполнимость: анатомия пригодности

ландшафт для жесткой комбинаторной оптимизации

проблема, транзакции IEEE на эволюционных

вычислениях, 16 (3), 319- 338 (2012).

Маня Ф. и Ли К. М. Новое понимание минимума

Выполнимость. В: Справочник 5-го Всемирного конгресса

и школы по универсальной логике, стр. 351-352

Биэр, А. и Синц, К. Разложение задач SAT

на связанные компоненты, Журнал по выполнимости,

Логическое моделирование и Расчет, 2: 201-208

(2014).

Браулт-Барон, Дж., Капелли, Ф. и Менгель, С.,

Понимание модельного подсчета для β-ациклических CNF-

формул, препринт arXiv, arXiv: 1405.6043 (2014).

[2] Лонсинг, Ф., Эгли, У. и Ван Гелдер, А., Эффективное обучение разделов

для количественных булевых формул с помощью

распространения псевдоединиц QBF. В: Теория и

Приложения проверки выполнимости — SAT 2013 (стр.

100-115). Springer Berlin Heidelberg (2013).

Нариццано М., Пулина Л. и Такчелла А., Отчет

о третьей оценке решателей QBF, Журнал

Satisfiability, Boolean Modeling and Computing, 2,

145-164 (2014).

Трабадо П. П., Льорис-Руис А. и Ортега-Лопера,

Дж., Решение уравнений переключения на основе табличной алгебры

, Транзакции IEEE на компьютерах, 42: 591 —

596 (1993).

Юнг, Г., Комментарии к «Некоторые дополнения к решению

уравнений переключения на основе табличной алгебры»,

IEEE Transactions on Computers, 44: 1357-1358

(1995).

Унгер, С. Х., Некоторые дополнения к решению переключающих уравнений

на основе табличной алгебры, IEEE

Transactions on Computers, 43, 365 — 367, (1994).

Постхофф, К. и Стейнбах, Б., Логические функции и

Двоичные модели уравнений для информатики.

Дордрехт, Нидерланды: Springer (2004).

Постхофф К., Стейнбах Б. Решение

задач дискретных ограничений с использованием булевых моделей.

В Дж. Филипе; А. Фред; Б. Шарп (редакторы), Материалы

2-й Международной конференции по агентам и

Искусственный интеллект-ICAART, Валенсия, Испания, стр.

978-989 (2010).

Стейнбах Б. и Постхофф К. Логические функции и

Уравнения — Примеры и упражнения. Springer

Science + Business Media B.V (2009 г.).

Стейнбах Б. и Постхофф К. Решение комбинаторных задач

с использованием булевых уравнений:

Новые задачи для обучения, Открытая математика

Образовательные заметки. ИМВИ ОМЕН, 5: 1-30, (2015).

Бохманн, Д., Закревский, А.D. and Posthoff, B.

G., Boolesche Gleichungen: Theorie, Anwendungen

und Algorithmen (Boolean Equations: Theory,

Applications and Algorithms), Sammelband-Verlag,

Berlin, Germany (1984).

Херли Р. Б. Карты вероятностей, Транзакции IEEE

о надежности, R-12 (3): 39-44 (1963).

Беннетс Р. Г., Об анализе деревьев отказов, IEEE

Веб-сайт Дэниела Д. Гайски

Просмотр только вопросов
Просмотр вопросов со стратегиями

Проблема 1

Вопрос

(Теоремы булевой алгебры) Дайте доказательства следующих теорем.

  1. Теорема 3 (a) и (b)
  2. Теорема 6 (a) и (b)

Решение

  1. Теорема 3 (a) и (b)

    ТЕОРЕМА 3 (а) Закон поглощения: yx + x = x.

    Проба:

     yx + x = yx + x1 по тождеству (Акс. 2b)
      = x (y + 1) по дистрибутивности (Акс. 4a)
      = x1 по теореме 2 (а)
      = x по тождеству (Акс. 2b)

    ТЕОРЕМА 3 (b): x (x + y) = x по двойственности.

  2. Теорема 6 (a) и (b)

    ТЕОРЕМА 6 (а) Законы Де Моргана: (x + y) ‘= x’y’.

    Доказательство: мы докажем, что x’y ‘является дополнением к x + y, доказав, что x’y’ удовлетворяет аксиоме 5, которая утверждает, что x + x ‘= 1 и что xx’ = 0. Таким образом, мы должны доказать что (a) (x + y) + (x’y ‘) = 1 и (b) (x + y) (x’y’) = 0.

    Часть (а):

     (x + y) + (x'y ') = x + (y + (x'y')) по ассоциативности (Th. 5a)
              = x + ((x'y ') + y') по коммутативности (Ax.3а)
              = (x + (x'y ')) + y по ассоциативности (Th. 5a)
              = (x + x ') (x + y') + y по дистрибутивности (Акс. 4b)
              = 1 (x + y ') + y с дополнением (Акс. 5a)
              = (x + y ') + y по тождеству (Акс. 2b)
              = x + (y '+ y) по ассоциативности (Th. 5a)
              = x + 1 с дополнением (Акс. 5a)
              = 1 по теореме 2 (б)

    Часть (b):

     (x + y) (x'y ') = x (x'y') + y (x'y ') по дистрибутивности (Акс.4а)
             = x (x'y ') + y (y'x') по коммутативности (Акс. 3b)
             = (xx ') y' + (yy ') x' по ассоциативности (Th. 3b)
             = 0y '+ 0x' дополнением (Акс. 5b)
             = 0 + 0 по тождеству (Акс. 2b)
             = 0

    ТЕОРЕМА 6 (b): (xy) ‘= x’ + y ‘по двойственности.

Задача 2

Вопрос

(Теоремы и доказательства) Используя таблицы истинности, докажите справедливость следующих тождеств.

  1. (xyz) ‘= x’ + y ‘+ z’

Решение

x y z (xyz) ‘ x ‘ г z ‘ x ‘+ y’ + z ‘
0 0 0 1 1 1 1 1
0 0 1 1 1 1 0 1
0 1 0 1 1 0 1 1
0 1 1 1 1 0 0 1
1 0 0 1 0 1 1 1
1 0 1 1 0 1 0 1
1 1 0 1 0 0 1 1
1 1 1 0 0 0 0 0

Задача 3

Вопрос

(Булевы функции) Вывести таблицы истинности для следующих булевых функций.

  1. F (x, y, z) = (x + z) ‘
  2. F (x, y, z) = (x + z) ‘(x + y’)

Решение

  1. F (x, y, z) = (x + z) ‘
    x y z x + z (x + z) ‘
    0 0 0 0 1
    0 0 1 1 0
    0 1 0 0 1
    0 1 1 1 0
    1 0 0 1 0
    1 0 1 1 0
    1 1 0 1 0
    1 1 1 1 0
  2. F (х, у, z) = (х + z) ‘(х + у’)
    x y z (xyz) ‘ x + y ‘ (x + z) ‘(x + y’)
    0 0 0 1 1 1
    0 0 1 0 1 0
    0 1 0 1 0 0
    0 1 1 0 0 0
    1 0 0 0 1 0
    1 0 1 0 1 0
    1 1 0 0 1 0
    1 1 1 0 1 0

Задача 4

Вопрос

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

  1. x’y ‘+ xy = (xy’ + x’y) ‘
  2. x’z + xy = x’y’z + yz + xy

Решение 

  1.  (xy '+ x'y)' = (xy ')' (x'y) 'Де Моргана
            = (x '+ y) (x + y') Де Моргана
            = x'x + x'y '+ xy + yy' дистрибутивность
            = x'y '+ xy тождество
 
  2.  x'z + xy = x'z + xy + xy идемпотентность
        = x'z (y + y ') + xy (z + z') + xy тождество
        = x'yz + x'y'z + xyz + xyz '+ xy дистрибутивность
        = x'y'z + (x + x ') yz + xy дистрибутивность
        = x'y'z + yz + xy тождество

Задача 5

Вопрос

(Алгебраические манипуляции) Минимизируйте количество операторов в следующих логических выражениях.

  1. x’y ‘+ xy + xy’
  2. (х + у) (х + у ‘)

Решение

  1. x + y ‘
  2. х

Задача 6

Вопрос

(логические реализации) Реализуйте функцию XOR с помощью:

  1. только ворота NAND
  2. только ворота NOR
  3. И, ИЛИ, и НЕ ворота

Решение

Задача 7

Вопрос

(логические реализации) Реализуйте x XOR y XOR z, используя компоненты базовой логической библиотеки, представленной в таблице 3.14. Найдите реализацию, в которой есть:

  1. Наименьшая стоимость
  2. Самая короткая задержка

Решение

Обратите внимание, что XNOR имеет наименьшую задержку. Поэтому сначала мы попробуем использовать реализацию XNOR .

 F = x XOR y XOR z
   = (x XOR y) z '+ (x XOR y)' z по определению XOR
   = (xy '+ x'y) z' + (xy '+ x'y)' z по определению XOR
   = xy'z '+ x'yz' + (xy '+ x'y)' z по дистрибутивности
   = xy'z '+ x'yz' + (x '+ y) (x + y') z по закону Де Моргана
   = xy'z '+ x'yz' + (x'x + x'y '+ xy + yy') z по дистрибутивности
   = xy'z '+ x'yz' + (x'y '+ xy) z дополнением
   = xy'z '+ x'yz' + x'y'z + xyz по распределительности
   = (xy '+ x'y) z' + (x'y '+ xy) z по дистрибутивности
   = (xy + x'y ')' z '+ (x'y' + xy) z дополнением
   = x XNOR y XNOR z по определению XNOR

Решения для (a), (b) и (c) одинаковы:

   Стоимость  = 12 + 12 =  24 
   Задержка  = 3.2 + 3,2 =  6,4

Задача 8

Вопрос

(Библиотеки логики) Используя базовую библиотеку логики, представленную в Таблице 3.14, реализуйте полный вычитатель, указанный в следующей таблице:

   Си Йи Би | Би + 1 Ди
 ------------------------------
   0 0 0 | 0 0
   0 0 1 | 1 1
   0 1 0 | 1 1
   0 1 1 | 1 0
   1 0 0 | 0 1
   1 0 1 | 0 0
   1 1 0 | 0 0
   1 1 1 | 1 1

Найдите реализацию, в которой есть:

  1. Наименьшая стоимость
  2. Самая короткая задержка

Решение

  1. Наименьшая стоимость с использованием логических элементов NAND

     Bi + 1 = x'y'b + x'yb '+ x'yb + xyb по определению
      = x '(y'b + yb') + yb (x '+ x) по дистрибутивности
      = x '(y'b + yb') + yb по дополнению
      = x '((y'b)' (yb ')') '+ yb по закону Де Моргана
      = ((x '((y'b)' (yb ')') ')' (yb) ')' по закону Де Моргана

 Di = x'y'b + x'yb '+ xy'b' + xyb по определению
    = x '(y'b + yb') + x (yb + y'b ') по дистрибутивности
    = x '((y'b)' (yb ')') '+ x ((yb') (y'b ')') 'по закону Де Моргана
    = ((x '((y'b)' (yb ')') ')' (x ((yb ') (y'b') ')') ')' по закону Де Моргана
 
       Стоимость  = 4 x 8 + 2 x 4 =  40 
   Задержка  = 1 x 2 + 1.4 х 4 =  7,6

  2. Самая короткая задержка

     Bi + 1 = x'y'b + x'yb '+ x'yb + xyb по определению
      = b (xy + x'y ') + x'y (b' + b) по дистрибутивности
      = (b ((xy) '(x'y') ')' + x'y дополнением
      = ((b ((xy) '(x'y') ')') '(x'y)') 'по закону Де Моргана

 Di = x'y'b + x'yb '+ xy'b' + xyb по определению
    = x '(x'y + xy') + b (xy + x'y ') по дистрибутивности
    = b '((x'y)' (xy '))' + b ((xy) '(x'y') ')' по закону Де Моргана
    = ((b '((x'y)' (xy '))') '(b ((xy)' (x'y ')') ')') 'по закону Де Моргана
 
       Стоимость  = 2 x 3 + 4 x 11 =  50 
   Задержка  = 1 + 1.4 х 4 =  6,6

Задача 9

Вопрос

(логические библиотеки) Повторите задачу 3.15, используя только вентили, приведенные в таблицах 3.15 и 3.16

Решение

  1. Самая маленькая стоимость
     F = (xy '+ x'y) z' + (xy '+ x'y)' z по определению XOR
   = ((xy '+ x'y)' + z) '+ (xy' + x'y) 'z по закону Де Моргана
 

       Стоимость  = 6x8 =  48 
   Задержка  = 1.8 + 2,0 + 2,8 + 2,8 =  9,4
  2. Самая короткая задержка и наименьшая задержка по затратам
     F = xyz + x'y'z + x'yz '+ xy'z' по определению XOR
   = ((xyz + x'y'z + x'yz '+ xy'z') ')' по инволюции
   = ((xyz) '(x'y'z)' (x'yz ')' (xy'z ')') 'по закону Де Моргана
    Или
     F = (x + y + z) (x + y '+ z') (x '+ y + z') (x '+ y' + z) по определению
   = (((x + y + z) (x + y '+ z') (x '+ y + z') (x '+ y' + z)) ')' по инволюции
   = ((x + y + z) '+ (x + y' + z ')' + (x '+ y + z') '+ (x' + y '+ z)') 'по закону Де Моргана
 

       Стоимость  = 7 x 8 + 10 =  66 
   Задержка  = 1.8 + 1,8 + 2,2 =  5,8 
   Стоимость x задержка  =  382,8

Задача 10 (3.18)

Вопрос

(логические библиотеки) Повторите задачу 3.15, используя любые стандартные логические элементы, приведенные в таблицах 3.14, 3.15 и 3.16

Решение

  1. Наименьшая стоимость и наименьшая отсрочка по затратам
     F = x XOR y XOR z = x XNOR y XNOR z по задаче 3.15
 

       Стоимость  = 2 x 12 =  24 
   Задержка  = 2 x 3.2 =  6,4 
   Стоимость x задержка  =  153,6
  2. Самая короткая задержка
     F = ((xyz) '(x'y'z)' (x'yz ')' (xy'z ')') 'по задаче 3.17
 

       Стоимость  = 3 x 2 + 4 x 8 + 10 =  48 
   Задержка  = 1,0 + 1,8 + 2,2 =  5,0 нс

Задача 11 (3.19)

Вопрос

(Массивы вентилей) Используя вентили NAND с 3 входами, выведите логическую схему:

  1. сумматор полный
  2. Вычитатель полный

Решение

  1. Полный сумматор
    1. Напишите таблицу истинности для полного сумматора.
        Си Йи Ци | Ci + 1 Si
 -------------------------
  0 0 0 | 0 0
  0 0 1 | 0 1
  0 1 0 | 0 1
  0 1 1 | 1 0
  1 0 0 | 0 1
  1 0 1 | 1 0
  1 1 0 | 1 0
  1 1 1 | 1 1
    2. Запишите выражение суммы произведения этой таблицы истинности.
      Ci + 1 = Xi'YiCi + XiYi'Ci + XiYiCi '+ XiYiCi
     = YiCi + XiCi + XiYi
Si = Xi'Yi'Ci + Xi'YiCi '+ XiYi'Ci' + XiYiCi
    3. Преобразуйте это выражение в формат, содержащий не более трех подвыражений операторов или трех литералов.Если выражения содержат более 3 операторов или литералов, сгруппируйте их в оператор с 3 входами.
      Ci + 1 = YiCi + XiCi + XiYi
     = (YiCi) '(XiCi)' (XiYi) ')'
 Si = Xi'Yi'Ci + Xi'YiCi '+ XiYi'Ci' + XiYiCi
     = (((Xi'Yi'Ci) '(Xi'YiCi') '(XiYi'Ci') ')' '(XiYiCi)') '
    4. Представьте эти два выражения с помощью вентилей NAND с 3 входами.

         Стоимость  = 6 x 14 =  84 
   Задержка : вход на Si = 1.8 х 5 =  9,0 
        Вход в Ci + 1 = 1,8 x 3 =  5,4
  2. Полный вычитатель
    1. Напишите таблицу истинности полного вычитателя.
        Си Йи Би | Би + 1 Ди
 -------------------------
  0 0 0 | 0 0
  0 0 1 | 1 1
  0 1 0 | 1 1
  0 1 1 | 1 0
  1 0 0 | 0 1
  1 0 1 | 0 0
  1 1 0 | 0 0
  1 1 1 | 1 1
    2. Запишите выражение суммы произведения этой таблицы истинности.
      Би + 1 = Xi'Yi'Bi + Xi'YiBi '+ Xi'YiBi + XiYiBi
Di = Xi'Yi'Bi + Xi'YiBi '+ XiYi'Bi' + XiYiBi
    3. Преобразуйте это выражение в формат, содержащий не более трех подвыражений операторов или трех литералов. Если выражения содержат более 3 операторов или литералов, сгруппируйте их в оператор с 3 входами.
      Би + 1 = Xi'Yi'Bi + Xi'YiBi '+ Xi'YiBi + XiYiBi
     = (((Xi'Yi'Bi) '(Xi'YiBi') '(XiYiBi)') '' (Xi'YiBi) ')'
 Di = Xi'Yi'Bi + Xi'YiBi '+ XiYi'Bi' + XiYiBi
     = (((Xi'Yi'Bi) '(Xi'YiBi') '(XiYiBi)') '' (XiYi'Bi ')') '
    4. Представьте эти два выражения с помощью вентилей NAND с 3 входами.

         Стоимость  = 6 x 12 =  72 
   Задержка : вход в Di = 1,8 x 5 =  9,0 
        Вход в Bi + 1 = 1,8 x 5 =  9,0

Практические задачи по логической алгебре

Разместите свои комментарии?

Практические задачи по булевой алгебре: придумайте себе логику

1 час назад Практические задачи по булевой алгебре : 1.A + AB¯¯¯¯¯¯¯¯. упрощаем выражение, берем общий термин. = A + (A¯¯¯¯ + B¯¯¯¯) = (A + A¯¯¯¯) + B¯¯¯¯ коммутативные и ассоциативные законы. = 1 + B¯¯¯¯ Правило дополнения. = 1 Правило идентификации. 2.

Веб-сайт: Booleanalgebraforyou.weebly.com