Лекция Булева Алгебра

ТЕМА БУЛЕВА АЛГЕБРА

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

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

Известнейший Готфрид Вильгельм Лейбниц сформулировал понятие «математическая логика», задачи которой были доступны для понимания только узкому кругу ученых. Особого интереса это направление не вызывало, и до середины XIX века о математической логике знали немногие.

Большой интерес в научных сообществах вызвал спор, в котором англичанин Джордж Буль заявил о своем намерении создать раздел математики, не имеющий абсолютно никакого практического применения. Как мы помним из истории, в это время активно развивалось промышленное производство, разрабатывались всевозможные вспомогательные машины и станки, т. е. все научные открытия имели практическую направленность. Забегая вперед, скажем, что булева алгебра – самая используемая в современном мире часть математики. Так что спор свой Буль проиграл. Джордж Буль Сама личность автора заслуживает отдельного внимания. Даже учитывая то, что в прошлом люди взрослели раньше нас, все равно нельзя не отметить, что в 16 лет Дж. Буль преподавал в деревенской школе, а к 20 годам открыл собственную школу в Линкольне. Математик отлично владел пятью иностранными языками, а в свободное время зачитывался работами Ньютона и Лагранжа. И все это - о сыне простого рабочего! .

Основные понятия и определения Не вдаваясь в глубины, разберемся с терминологией. Итак, булева алгебра предполагает наличие: высказываний; логических операций; функций и законов. Высказывания – любые утвердительные выражения, которые не могут быть истолкованы двузначно. Они записываются в виде чисел (5 3) или формулируются привычными словами (слон – самое большое млекопитающее). При этом фраза «у жирафа нет шеи» также имеет право на существование, только булева алгебра определит её как «ложь»

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

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 =

= ¬A&¬B&¬C

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,

F¬G v ¬FG = 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. Проанализируем результат:

 Результат Б) не является решением, т.к. в ответе Маши оба утверждения оказываются неверными, что проти­воречит условию задачи.

 Результат А) полностью удовлетворяет усло­вию задачи и поэтому является верным решением.

Ответ: ребята выбрали американский боевик.