Коммутативность дизъюнкции

коммутативность дизъюнкции - student2.ru

Коммутативность конъюнкции

коммутативность дизъюнкции - student2.ru

Ассоциативность дизъюнкции

коммутативность дизъюнкции - student2.ru

Ассоциативность конъюнкции

коммутативность дизъюнкции - student2.ru

Первый дистрибутивный закон

коммутативность дизъюнкции - student2.ru

Второй дистрибутивный закон

коммутативность дизъюнкции - student2.ru

Законы де Моргана

коммутативность дизъюнкции - student2.ru , коммутативность дизъюнкции - student2.ru

Законы идемпотентности

коммутативность дизъюнкции - student2.ru , коммутативность дизъюнкции - student2.ru .

10. Законы, включающие тождественно-истинные (I) и тождественно-ложные (L) высказывания

коммутативность дизъюнкции - student2.ru , коммутативность дизъюнкции - student2.ru коммутативность дизъюнкции - student2.ru

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

коммутативность дизъюнкции - student2.ru

Пример 23.Доказать равносильность

коммутативность дизъюнкции - student2.ru

Используя законы де Моргана, можем записать

коммутативность дизъюнкции - student2.ru

Согласно закону двойного отрицания, получаем

коммутативность дизъюнкции - student2.ru

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

коммутативность дизъюнкции - student2.ru

Ассоциативность дизъюнкции позволяет опустить две пары скобок

коммутативность дизъюнкции - student2.ru

учитывая законы пункта 10: коммутативность дизъюнкции - student2.ru и коммутативность дизъюнкции - student2.ru окончательно получаем

коммутативность дизъюнкции - student2.ru

Пример 24.Упростить высказывание

коммутативность дизъюнкции - student2.ru

Так как

коммутативность дизъюнкции - student2.ru , коммутативность дизъюнкции - student2.ru , коммутативность дизъюнкции - student2.ru ,

то предложенное высказывание равносильно высказыванию коммутативность дизъюнкции - student2.ru , т.е. является тождественно-ложным.

Задача 1.

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

Решение.

Рассмотрим высказывания:

A = {Машина синего цвета},

B = {Машина марки «Бьюик»},

C = {Машина черного цвета},

D = {Машина марки «Крайслер»},

E = {Машина марки «Форд Мустанг»}.

Так как либо цвет машины, либо марка каждым из соучастников преступления названы верно, то

коммутативность дизъюнкции - student2.ru

Отсюда следует, что

коммутативность дизъюнкции - student2.ru

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

коммутативность дизъюнкции - student2.ru

Но

коммутативность дизъюнкции - student2.ru

и, следовательно,

коммутативность дизъюнкции - student2.ru , т.е. преступники скрылись на черном «Бьюике».

Задача 2.

На одном заводе работают три друга: слесарь, токарь и плотник. Их фамилии: Борисов, Иванов, Семенов. Профессии и фамилии названы в произвольном порядке. У слесаря нет ни братьев, ни сестер, и он самый младший из друзей. Семенов женат на сестре Борисова, он старше токаря. Назовите фамилии слесаря, токаря и плотника.

Решение.

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

  Б И С
с
т
п

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

Условия 2 и 4 исключают возможность того, что Семенов – слесарь. Поэтому в клетку, стоящую в правом верхнем углу таблицы (клетку (с, С)), также вписываем 0. Но так как один из трех друзей слесарь, то им может быть только Иванов. Поэтому в клетку (с, И) вписываем 1, а в остальные клетки среднего столбца – 0 (если Иванов слесарь, то он не токарь и не плотник).

Условие 4 исключает возможность того, что Семенов токарь. Поэтому в клетку (т, С) вписываем 0, но тогда Семенов может быть только плотником, следовательно, в клетку (п, С) вписываем 1, а в клетку (п, Б) вписываем 0.

Теперь осталась лишь одна незаполненная клетка (т, Б), в которую мы должны, очевидно, вписать 1.

Итак, Борисов – токарь, Иванов – слесарь, Семенов – плотник.

Алгебра логики успешно применяется при анализе релейно-контактных и электронно-ламповых схем. Физическая природа таких схем (будем называть их переключательными) может быть самой разнообразной. Под переключательной системой будем понимать схематическое изображение какого-либо устройства, содержащего только двухпозиционные переключатели, т.е. переключатели, которые могут находиться только в двух состояниях: в замкнутом (ток проходит) и в разомкнутом (ток не проходит). Связь между переключательными схемами и алгеброй высказываний устанавливается следующим образом. Каждому переключателю ставится в соответствие высказывание, истинное тогда, когда переключатель замкнут, и ложное, если переключатель разомкнут. На схемах переключатели будем обозначать теми же буквами, что и соответствующие им высказывания.

Переключателям, соединенным параллельно, будет соответствовать при этом дизъюнкция соответствующих высказываний; переключателям, соединенным последовательно, − конъюнкция высказываний. Если два переключателя работают так, что один из них замкнут, когда другой разомкнут, и наоборот, то им ставятся в соответствие высказывания коммутативность дизъюнкции - student2.ru и коммутативность дизъюнкции - student2.ru .

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

Пример 25.Упростить схему:

 
  коммутативность дизъюнкции - student2.ru

Выписываем высказывание, соответствующее данной схеме, и упрощаем его:

коммутативность дизъюнкции - student2.ru =

= коммутативность дизъюнкции - student2.ru =

= коммутативность дизъюнкции - student2.ru =

= коммутативность дизъюнкции - student2.ru = коммутативность дизъюнкции - student2.ru .

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

 
  коммутативность дизъюнкции - student2.ru

1.5. Содержание отчета:

1. Выполнение заданий соответствующего варианта.

2. Ответы на контрольные вопросы.

1.6. Контрольные вопросы:

1. Что такое система счисления?

2. Чем отличаются позиционная и непозиционная системы счисления?

3. Почему основной системой счисления ЭВМ является двоичная?

4. Когда используется шестнадцатеричная система счисления?

5. Какие основные операции алгебры логики вы знаете?

6. Как можно проверить эквивалентность формул в алгебре высказываний?

Наши рекомендации