Виталий Сигорский - Математический аппарат инженера

причем в случае x 1= x 2= 1 образуется единица переноса в старший разряд. Операция, задаваемая этой таблицей, называется сложением по модулю 2 . Если при сложении перенос не учитывается, то эта операция вместе с операцией умножения определяет на множестве двоичных чисел арифметику по модулю 2 .

1. Подстановкой в формулу a ∨ b переменных запишите новые формулы и упростите их, если это возможно: а) a = x̅y, b = z. б) a = xy, b = xy̅; в) a = x, b = xy; г) a = x, b = x̅y; д) a = xy, b = c ∨ d, c = xz, d = yz̅.

2. Запишите таблицы соответствия для следующих формул: а) xx̅; б) xy ∨ x̅; в) (p ∨ q)(p̅ ∨ q̅); г) x̅∨̅y̅.

3. Проверьте с помощью таблиц соответствия следующие тождества: а) x̅∨̅y̅ = x̅ y̅; б) x ( x ∨ y) = x; в) x ∨ x̅ y = x ∨ y.

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

а) xy∨x̅y∨x̅y̅=y ∨ x̅y̅

б) (x∨y)(x∨z) = x ∨ yz;

в) xyz∨xyz̅∨xy̅ = x.

5. Упростите следующие формулы:

а) x̅yz∨xy̅z̅∨xyz̅;

б) xy∨z∨x̅y̅∨̅z̅(zv∨x);

в) xy̅z̅∨xyz̅∨x̅yz∨xyz;

г) (x∨y)(x̅y̅∨z)∨z̅∨(x∨y)(u∨v).

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

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

- 71 -

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

9. Убедитесь с помощью таблиц соответствия в справедливости выражений для импликации и эквиваленции:

а) x 1→ x 2= x̅ 1∨x 2;

б) x 1∼ x 2= x 1x 2∨ x̅ 1x̅ 2= (x 1∨x̅ 2)(x̅ 1∨x 2);

в) x 1∼ x 2= ( x 1→ x 2)( x 2→ x 1).

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

11. Запишите формулу, соответствующую переключательной схеме рис. 25. Упростите эту формулу и постройте более простую схему.

Рис. 25. Граф переключательной схемы к задаче 11.

12. Постройте переключательные схемы по формулам:

а)(x 1∨ x 2x̅ 3)(x 1x 2∨ x 3x 4)

б) (x̅ 1(x 2∨ x̅ 3) ∨ x̅ 4)x 1.

13. Из простых высказываний x 1- «испытания проведены» и x 2- «программа выполнена» образуйте сложные высказывания по формулам а) x 1∨x̅ 2; б) x 1x 2; в) x 1→ x 2; г) x 1∼ x 2.

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

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

б) Вычисления выполнены точно или конструкция несовершенна.

в) Проект разработал Андрей или Петр, а эксперимента выполнил Иван.

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

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

е) Если я поеду на автобусе, то опоздаю на работу или я воспользуюсь такси.

ж) Андрей помогает Петру или Петр помогает Андрею, или они помогают друг другу.

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

16. Даны простые высказывания: x 1- «идет дождь), x 2- «очень жарко».

а) Запишите формулу сложного высказывания «Неверно, что идет дождь и очень жарко».

б) Преобразуйте формулу по закону де Моргана и составьте соответствующее высказывание.

в) Убедитесь в тожественности исходного и преобразованного высказываний.

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

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

- 72 -

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

в) Запишите соответствующую формулу и таблицу соответствия.

г) По таблице соответствия сформулируйте искомый вопрос.

18. Высказывание является логически истинным, если соответствующая ему формула тождественно равна единице, и логически ложным, если формула равна нулю. Определите с помощью таблиц соответствия, каким высказываниям соответствуют приведенные ниже формулы (истинным, ложным или ни тем и не другим): а) p ∼ p; б) p → p̅; в)(p∨q) ∼ pq; г)(p→q̅) → (q → p̅); д)(p→ q)→ p; е) ((p→ q)→ p)→ p; ж) p̅∨̅q̅ ∼ pq .

19. При x 1= 1; x 2= 0; x 3= 0 и x 4= 1 найдите значения каждой из следующих функций:

20. Пусть X — множество сотрудников отдела и на этом множестве определены относительно переменной x ∈ X одноместные предикаты P(x), Q(x), R(x), означающие соответственно: x — занимается спортом, изучает иностранный язык, имеет изобретения. Расшифруйте предикаты, образованные с помощью следующих логических операций: а) P(x) ∨ Q(x); б) P(x) Q(x); в) P̅(x) Q(x); г) Q(x) ∼ P(x); д) P̅(x) ∼ (Q(x) ∨ R(x)).

21. Пусть V — множество вершин и E — множество ребер графа, причем ребро e ∈ E соединяет вершины x,y ∈V. Что означают предикаты P(x,y), Q(e, x, y), R(x,e)?

22. Каким десятичным числам соответствуют следующие двоичные числа: а) 1011; б) 1000110; в) 110100111?

23. Переведите в двоичную систему счисления десятичные числа: а) 51; б) 64; в) 125; г) 1000.

24. Выполните в двоичной системе следующие операции над десятичными числами: 21 + 37; 31 + 105; в) 25 · 8; г) (8 + 19) · 11; д) 24 · 8 — 17. Проверьте полученные результаты в десятичной системе.

25. Переведите в двоичную систему счисления с точностью до пяти двоичных знаков после запятой числа: а) 0,131; б) 0,25; в) 175,26.

26. Дайте обоснование правил перевода десятичных числе в двоичные.

27. Сложите двоичные числа 11001110 и 11010111 по обычному правилу и по модулю два. Найдите разность полученных результатов и объясните ее смысл.

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