З а д а н и е

Лабораторная работа №5

Тема ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ. ТАБЛИЦЫ ИСТИННОСТИ

Цель: изучить основные логические операции, освоить способы построения таблиц истинности.

Теоретическая часть

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

• логическое отрицание (инверсия): X;

• логическое сложение (дизъюнкция): X Ú Y;

• логическое умножение (конъюнкция): X Ù Y;

• импликация: X → Y;

• эквивалентность: X ↔ Y.

Таблица истинности для логических операций

Алгоритм заполнения таблицы истинности

1. Посчитать число переменных в сложном высказывании – n.

2. Определить порядок выполнения логических операций и рассчитать их число k.

3. Рассчитать число строк по формуле: 2 n + 2.

4. Рассчитать число столбцов как сумму числа переменных n и числа всех логических операций k, входящих в высказывание, т.е. n + k.

5. Пронумеровать столбцы от 1 до n + k, заполнив первую строку таблицы.

6. Заполнить первые n столбцов второй строки таблицы именами переменных.

7. Заполнить оставшиеся k столбцов второй строки соответствующими логическими операциями.

8. Заполнить первые n столбцов значениями 0 и 1 в следующем порядке:

• в первом столбце чередуются (2 n)/2 нулей и (2 n)/2 единиц;

• во втором столбце чередуются (2 n)/4 нулей и (2 n)/4 единиц и т.д.;

• в n столбце чередуются 1 ноль и 1 единица.

9. Заполнить остальные k столбцов значениями 0 и 1 в соответствии с порядком выполнения логических операций в

выражении.

Пример

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

F (A, B, C) = ((B Ú A) Ù C) Ú A.

Р е ш е н и е.Составим таблицу истинности в соответствии с алгоритмом. Сложное высказывание состоит из трех простых (n = 3). Определим порядок выполнения логических операций:

1 2 4 3

F (A, B, C) = ((B Ú A) Ù C) Ú A, т.е. k = 4 (4 логические операции: 2 дизъюнкции, конъюнкция и отрицание).

Число строк в таблице истинности равно 23 + 2 = 10 (2 строки для заголовка). Число столбцов равно n + k = 3 + 4 = 7.

Получим:

З а д а н и е

Составить таблицы истинности для логических выражений F1, F2 и F3

1. F1 = (X " Y) → ((X ∧ Z) ∨ Y)

F2 = ((YÚ Z) Ú X)" ((ZÙ Y)→ X)

F3 = YÚ (Z" X) Ù ((YÙ X)→ Z)

2. F1 = ((X " Y) → Z) ∧ (X ∨ Y)

F2 = (Z→ (YÙ X)) Ú (X" (ZÙ Y))

F3 = (Z Ú X) → ((Y" Z) Ú X)

3. F1 = X → ((Y ∧ Z) ∨ X " Y)

F2 = (YÙ Z) Ù ((X" (ZÚ Y))→ X)

F3 = ((X→ Y) " (Y Ù Z)) Ú X

4. F1 = ((X∧ Y)" Z)∧ (X→ Y)∨ Z

F2 = (((XÙ Z)→ Y)" ((ZÙ X))) Ú Y

F3 = Z" ((Z→ X)→ ((XÙ Y) Ú Y)))

5. F1 = (X" (Z∨ Y))→ (Y∧ (Z∨ X))

F2 = (ZÙ (YÚ X) → Y) " Z

F3 = ((XÙ Y))→ (Y " (X Ú Z))

6. F1 = ((X " Z) ∧ Y) → (Z ∨ Y)

F2 = (((XÙ Z)" Y) Ú (X → Y))

F3 = ((YÙ Z)" (XÙ Y)) Ù (X→ Z)

7. F1 = ((X∧ Y)" (Y∧ Z)) ∨ (X→ Z)

F2 = ((XÚ Y)) ↔ ((Y Ù Z) " X)

F3 = ((X → Z) Ù Y) " (X Ù Y)

8. F1 = ((X∨ Y))∧ (Z∨ X)→ (Y" Z)

F2 = Y" (XÚ Z) Ù ((X → Y))

F3 = ((Z" Y) Ù (Y→ X)) Ú (XÙ Z)

9. F1 = ((X" Y) → Z)) ∨ (Z ∧ X)

F2 = (XÚ ((Z→ Y))) " (Y Ú X)

F3 = (Z " (YÙ X)) ↔ ((YÙ X) Ú Z)

10. F1 = X→ (Y ∨ Z) ∧ ((X " Y))

F2 = ((XÙ Z)→ ((YÙ Z) " X))

F3 = ((YÙ X)" Z)→ ((XÙ Z)→ Y)

11. F1 = X∨ (Y" Z) ↔ (((X→ Y)∧ Z))

F2 = (((X→ Z) Ú ((YÙ Z)" X)))

F3 = ((XÚ Y)" Z) Ù ((X→ Z) Ú Y)

12. F1 = (((X∨ Y)∧ Z) ↔ (X → Y))

F2 = YÙ (ZÚ X)" (Y↔ (Z → X))

F3 = ((Z→ Y)" X) Ú (Z Ú Y)

13. F1 = (XÙ Y) Ù ((X ∧ Z) Ú Y)

F2 = ((YÙ Z) Ú X)" ((ZÙ Y)→ X)

F3 = YÙ (Z" X) Ù ((YÚ X)→ Z)

14. F1 = ((X " Y) → Z) Ù (X Ú Y)

F2 = (Z→ (Y→ X)) Ù (X" (ZÚ Y))

F3 = (Z ↔ ((Y" Z) Ú X)

15. F1 = X → ((Y Ù Z) Ù X " Y)

F2 = (YÙ Z) Ú ((X" (Z→ Y))→ X)

F3 = ((X→ Y) " (Y Ù Z)) Ú X

16. F1 = ((XÙ Y)" Z) Ú (X→ Y) Ù Z

F2 = (((XÙ Z) ↔ Y)" ((ZÙ X))) Ú Y

F3 = Z" ((Z→ X)→ ((XÙ Y) Ú Y)))

17. F1 = (X" (ZÚ Y))→ (YÚ (ZÚ X))

F2 = (ZÙ (Y↔ X) → Y) " Z

F3 = ((XÚ Y))→ (Y " (X Ù Z))

18. F1 = ((X " Z) Ù Y) → (Z Ú Y)

F2 = (((XÙ Z)" Y) Ù (X ↔ Y))

F3 = ((YÙ Z)" (XÚ Y)) → (X→ Z)

19. F1 = ((XÙ Y)" (YÙ Z)) Ú (X→ Z)

F2 = ((X↔ Y)) ↔ ((Y → Z) " X)

F3 = ((X → Z) Ú Y) " (X Ú Y)

20. F1 = ((XÙ Y)) Ú (ZÙ X)→ (Y" Z)

F2 = Y" (X↔ Z) Ú ((X → Y))

F3 = ((Z" Y) Ù (Y→ X)) Ù (XÚ Z)

21. F1 = ((X" Y) ↔ Z)) Ù (Z Ú X)

F2 = (XÙ ((Z→ Y))) " (Y → X)

F3 = (Z " (Y↔ X)) ↔ ((YÚ X) Ù Z)

22. F1 = X→ (Y → Z) Ú ((X " Y))

F2 = ((XÙ Z) ↔ ((YÙ Z) " X))

F3 = ((YÙ X)" Z)→ ((XÙ Z)→ Y)

23. F1 = XÚ (Y" Z) Ú (((X→ Y) Ú Z))

F2 = (((X→ Z) Ù ((Y→ Z)" X)))

F3 = ((XÙ Y)" Z) ↔ ((X→ Z) Ú Y))

24. F1 = (((XÙ Y) Ù Z) ↔ (X → Y))

F2 = YÚ (ZÚ X)" (YÙ (Z → X))

F3 = ((Z→ Y)" X) Ú (Z Ù Y)

25. F1 = (X " Y) → ((X Ù Z) Ú Y)

F2 = ((YÙ Z) Ù X)" ((ZÙ Y)→ X)

F3 = YÚ (Z" X) Ú ((Y→ X)→ Z)

26. F1 = ((X " Y) ↔ Z) Ú (X Ù Y)

F2 = (Z→ (YÚ X)) Ù (X" (ZÚ Y))

F3 = (Z Ù X) → ((Y" Z) Ù X)

27. F1 = X → ((Y Ú Z) Ù X " Y)

F2 = (YÚ Z) Ù ((X" (ZÚ Y))→ X)

F3 = ((X→ Y) " (Y Ú Z)) Ù X

28. F1 = ((X→ Y)" Z) ↔ (X→ Y) Ú Z

F2 = (((X→ Z)→ Y)" ((Z→ X))) Ú Y

F3 = Z" ((Z→ X) ↔ ((XÙ Y) Ù Y)))

29. F1 = (X" (ZÚ Y))→ (YÙ (Z→ X))

F2 = (ZÚ (YÙ X) → Y) " Z

F3 = ((XÚ Y)) ↔ (Y " (X Ù Z))

30. F1 = ((X " Z) Ú Y) → (Z → Y)

F2 = (((XÚ Z)" Y) Ù (X ↔ Y))

F3 = ((YÚ Z)" (XÚ Y)) Ù (X→ Z)

П р и м е ч а н и е

X " Y ≅ (X Ù Y)