Законы математической логики

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

Таблица 1.16. Основные законы алгебры логики

Закон

Для дизъюнкции

Для конъюнкции

Переместительный

X V у = у V X

X • у = у • X

Сочетательный

X V (у V 1) = (х V у) V 1

X-{у-1) = (Х ? у)-1

Рас п редел ител ьн ы й

х-{у^і) = х- у/х-і

X м(у- і) = (х V у)-(х V 1)

Правила де Моргана

X V у = у • X

X • у = у V X

Идемпотенции

X V X = X

X X = X

Поглощения

X V (х • у) - X

X ? (х V у) - X

Склеивания

(х у) V (х у) = у

(х V у) ? (х V у) = у

Операция переменной с ее инверсией

X V X = 1

XX = 0

Операция с константами

лу0 = х;ху1=1

х • 1 = х; х ? 0 = 0

Двойного отрицания

X = X

Примечание. Если левая и правая части одновременно, т. е. при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения, то закон доказан.

На основании аксиом алгебры конов.

  • 1. Коммутативные законы
  • 2. Ассоциативные законы
  • 3. Дистрибутивные законы

логики можно вывести ряд за-

х + у=у + 1

ху =ух '

  • + у) + I = х + (у + і)
  • у) -1 =х (у -I)

х-(у + і) = х ? у + X ? і х + у ? г =(х + у)-(х + z) '

4. Операции склеивания

X у + X ? у = X (х + у)(х + у)=х

X + X ? у = X + у х(х + у) = ху

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

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

  • 1) если А нарушил, то и В нарушил правила обмена валюты;
  • 2) если В нарушил, то и С нарушил или А не нарушал;
  • 3) если О не нарушил, то А нарушил, а С не нарушал;
  • 4) если О нарушил, то и И нарушил.

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

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

Указание 2. Если количество переменных (простых высказываний) больше трех, то решение с помощью таблицы истинности приводит, как правило, к большему объему вычислений.

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

А — «А нарушил правила обмена валюты»;

В — «В нарушил правила обмена валюты»;

С — «С нарушил правила обмена валюты»;

О — «И нарушил правила обмена валюты».

Запишем сложные высказывания, выражающие известные факты:

А^В; В^(С + А); Ъ ->(ЛС) О ^ А.

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

Р=(А -> В){В ->(С +Л))(Я ->(АС))(й -+А).

Используя соответствующие свойства, упростим полученную логическую функцию:

^ =(А + В)(В +С + Л)Ф + АС)ф + А) =

= (А + В)(В + С + А)ф + АС)ф + А) =

= (АВ + ВВ +АС + ВС + АА + ВА)(В + АС)ф + А) =

= (АВ + ВВ + СА + ВС + АА + АВ)(ОП + АСИ + АО + АСА) =

= (А(В + В) + СА + ВС + А)(Ь + Аф + СО) + АС) =

= (А+СА + ВС)(А(0 + С) + АС)=(А + ВС)(АО + АС) =

= ААО + АВСО + ААС + ВСАС = Ь + АВСй = АВСй = 1.

Поскольку АВСй = 1, то отсюда следует, что высказывания А, В, С и /) истинны, а следовательно, все работники банка нарушили правила обмена валюты.

Пр и м е р 1.22. Определить, кто из абитуриентов А, В, С, /) играет, а кто не играет в шахматы, если известно следующее:

  • 1) если А или В играет, то С не играет;
  • 2) если В не играет, то играют Си/);
  • 3) С — играет в шахматы.

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

А — «абитуриент А играет в шахматы»;

В — «абитуриент В играет в шахматы»;

С — «абитуриент С играет в шахматы»;

/) — «абитуриент /) играет в шахматы».

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

а) (А + В) С; б) В СО в) С.

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

В = ((А + В)^С)(В ^СО)С.

Приведем указанную логическую функцию к нормальной форме:

((А + В) -> С)(В -> СО)С = (АФВ + С)(В + С/))С =

= (АВ + С)(В + СО)С =АВС(В + С/)) = АВСй =1.

Отсюда —

Л = 0; В= 0; С= 1, /) = 1 (1 — истина; 0 — ложь).

Таким образом, в шахматы играют абитуриенты Си Д а абитуриенты А и В не играют.

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

  • а) Аня пойдет в кино только тогда, когда пойдут Вика и Сергей;
  • б) Аня и Сергей пойдут в кино вместе или же оба останутся дома;
  • в) для того чтобы Сергей пошел в кино, необходимо, чтобы пошла Вика.

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

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

А — «Аня пойдет в кино»;

В — «Вика пойдет в кино»;

С — «Сергей пойдет в кино».

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

а )А^ВС; 6) АС + АС; в )С^В.

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

/ =(Л -> ВС)(АС + АС)(СВ) + {АВС){АС + АС)(СВ) +;

+ -> ВС)(АС + АС)(С -> В).

Указание. Функцию /’такого вида можно составить с помощью следующей таблицы истинности (табл. 1.17).

Функция Р имеет истинные значения в трех случаях:

Т (0, 1, 1), Т2 (1, 0, 1) и Г3 (1, 1, 0), тогда

Р = ху1 + ху1 + ху1,

Таблица 1.17. Таблица истинности

X

У

I

р

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

0

здесь х, у, і — сложные высказывания, описывающие приведенные факты в условии задачи.

Преобразуем указанную функцию У7 по частям:

1) (А -> ВС)(ЛС + АС)(С -> В) = (А + ВС)(АС + АС)(С + В) =

= А(В +С)(АС + АС)(С + В) = АС(С + В)(С + В) =

АС(С + ВВ)= 0;

  • 2) -> ВС)(АС + АС)(С -> В) = (А + ВС)(АС ? Ж)(С + В) =
  • (А + ВС)(А + С)(А + С)(С + В) = (С + АВ)(А + С)(А + ВС) =

= (АС +АВС)(А + ВС) = (АВС + АВС) =АВС

3) -> ВС)(АС + А С)(С -> В) = (А + ВС)(АС + АС)(С + В) =

= (АВС + АС)(СВ) = 0.

Таким образом, АВС = 1. Отсюда А = 0, В= 1, С= 1, т. е. в кино пойдут Вика и Сергей, а Аня не пойдет в кино.

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

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

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

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

В — «будет ветер», Р — «будет пасмурная погода», И — «будет дождь».

Составные высказывания, выражающие известные факты (а,

б, в) в условии задачи, запишутся в виде:

а) В -> Р ? И;

  • б) И -> Р ? Ъ
  • в) Р -> И ? В.

Составим конъюнкцию этих высказываний:

-> РЙ){И -> РВ)(Р -> ИВ) = (В + Р1))ф + РВ)(Р + ИВ) =

= ВР(И + РВ) = ВРИ.

Слагаемые РРВ, ВИВ, РИИВ равны нулю.

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

Пр и мер 1.25. Миша решил поступить в МИЭТ[1] и послал домой три сообщения:

• если я сдам математику, то информатику я сдам только при

условии, что не получу двойку за диктант;

  • • не может быть, чтобы я получил двойки за диктант и математику;
  • • достаточное условие провала по информатике — это двойка за диктант.

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

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

И — «Миша сдаст информатику»;

М — «Миша сдаст математику»;

Д — «Миша сдаст диктант».

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

М^(И^Д); ДМ; Д^Й.

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

Р = (М ^Д))СШ)(Д -> й) + + ->(#-> Д)){Д М)(Д -> И) +

+ (М^(И -> Д))(ДМ)(Д -+Й).

Преобразуем полученную функцию по частям:

1) -» (Я -> Д))ОПЬ(Д ->Й) =

= (М + (И ->Д))(Д + А/)(Д + Й) =

= М(Й ->Д)(Д + М)( Д + Й) =

= М{Й + Д){Д + Л/)( Д + Й) = МИД(Д + Мй) = 0;

2) (М^(И ^ Д))(ДМ)(Д -> #) =

= (М + (И ->Д))ДМ(Д + Й) = (М + Й + Д)ДМЙ =ДМЙ;

3) (м -> (я -> Д))СШ)(Д -> Й) =

= (М + -> Д))(Д + Л/)(Д + Й) =

= (М + Й + Д)(Д + М)(ДИ)=(М + Й + Д)МИД =0.

Таким образом, Р = Д И М, т. е. Миша провалит все экзамены: по математике, информатике и диктанту.

Пр и мер 1.26. Проверьте правильность следующего умозаключения. Для того чтобы Саша прошел по конкурсу в МИЭТ, достаточно, чтобы или Аня, или Вика не прошли по конкурсу в институт. Вика пройдет по конкурсу вместе с Димой. Не может быть, чтобы по конкурсу прошли и Аня, и Саша.

Вывод. Для того чтобы Аня прошла по конкурсу в институт, необходимо, чтобы по конкурсу прошли Дима и Саша.

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

А — «Аня пройдет по конкурсу в институт»;

С — «Саша пройдет по конкурсу в институт»;

/) — «Дима пройдет по конкурсу в институт»;

В — «Вика пройдет по конкурсу в институт».

Тогда соответствующие посылки и заключение (вывод) в символической форме примут вид:

  • а) (А + В) -> С;
  • б) Во-
  • в) АС.

Вывод. А -+ОС. Запишем теперь умозаключение в символической форме:

{{А + В)^> С), ВО, (АС) | = -> ОС).

Составим импликацию:

((А + В) -> С) ? ВО ? АС ->(А -> ОС).

Выясним, является ли данное высказывание тавтологией. Упростив формулу, получим:

((А + В) -> С) ? ВО ? АС -> (А -> ОС) =

= ((А + В) + С)ВИ(А +С)->(А + ОС) = (АВ + С)ВО(А + С) ->

^ (А + ОС) = (СА + АВС)ВО +А +ОС =

= (СА + АВС) + ВО + А + ОС =СА АВС + В + 0+ А+0С =

= (С +А)(А + В +С)+ В+ А+ 0+ С =

= СА + СВ + АВ + АС +В+А + 0+ С = В+ А + 0+ С.

СА =СВ = АВ =0

Таким образом, данная функция не является тождественно истинной, и, следовательно, данное умозаключение неправильное.

  • [1] Московский институт электронной техники (Технический Университет) — МИЭТ (ТУ).
 
< Пред   СОДЕРЖАНИЕ     След >