Алгебра логики.

Тема 5.

1. Что изучает алгебра логики?

Алгебра логики — это раздел, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними.

2. Что такое «логическое высказывание»?

Логическое высказывание — это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

3. Что такое «логическая связка»?

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

4. Какое логическое высказывание называется «составным», а какое «элементарным»?

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

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

а) Операция, выражаемая словом " не", называется отрицанием и обозначается чертой над высказыванием. Высказывание Ā истинно, когда A ложно, и ложно, когда A истинно.

б) Операция, выражаемая связкой " и", называется конъюнкцией (лат. conjunctio — соединение) или логическим умножением и обозначается точкой ". ". Высказывание А. В истинно тогда и только тогда, когда оба высказывания А и В истинны.

в) Операция, выражаемая связкой " или" называется дизъюнкцией (лат. disjunctio — разделение) или логическим сложением и обозначается знаком v. Высказывание А v В ложно тогда и только тогда, когда оба высказывания А и В ложны.

г) Операция, выражаемая связками " если..., то", " из... следует", называется импликацией (лат. implico — тесно связаны) и обозначается знаком →. Высказывание А → В ложно тогда и только тогда, когда А истинно, а В ложно.

д) Операция, выражаемая связками " тогда и только тогда", " необходимо и достаточно", "... равносильно...", называется эквивалентностью и обозначается знаком ↔. Высказывание А↔ В истинно тогда и только тогда, когда значения А и В совпадают.

6. Что значит «формализация логического высказывания»?

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

7. Что называют «логической формулой»?

1. Всякая логическая переменная и символы " истина" (1) и " ложь" (0) - формулы.

2. Если А и В — формулы, то Ā, Аˑ В, А v В, А → В, А↔ В формулы.

3. Никаких других формул в алгебре логики нет.

8. Какие формулы называются «выполнимыми»?

Как показывает анализ формулы (А v В) → С, при определённых сочетаниях значений переменных A, B и C она принимает значение " истина", а при некоторых других сочетаниях — значение " ложь". Такие формулы называются выполнимыми.

9. Какие формулы называются «тождественно истинными»?

Некоторые формулы принимают значение " истина" при любых значениях входящих в них переменных. Такие формулы называются тождественно истинными формулами или тавтологиями.

10. Какие формулы называются «тождественно ложными»?

Некоторые формулы принимают значение " ложь" при любых значениях входящих в них переменных. Такие формулы называются тождественно ложными формулами или противоречиями.

11. Какие формулы называются «равносильными»?

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

12. Что такое «равносильное преобразование формулы»?

Равносильность двух формул алгебры логики обозначается символом " =". Замена формулы другой, ей равносильной, называется равносильным преобразованием данной формулы.

13. Что такое «логический элемент компьютера»?

это часть электронной логической схемы, которая реализует элементарную логическую функцию.

14. Что такое «таблица истинности»?

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

15. Построить таблицы истинности основных логических операций.

-

16. Изобразить структурные схемы основных логических операций.

-

17. Сформулировать основные законы алгебры логики.

Переместительный закон

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

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

Правило идемпотентности

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

Правила операций с константами

Законы инверсии (отрицания)

Снятие двойного отрицания

18. Что такое «логическая схема»?

Логическая схема — это схематическое изображение некоторого устройства, состоящего из переключателей и соединяющих их проводников, а также из входов и выходов, на которые подаётся и с которых снимается электрический сигнал.

19. В чем заключается синтез логической схемы?

Синтез схемы по заданным условиям ее работы сводится к следующим трём этапам:

1. составлению функции проводимости по таблице истинности, отражающей эти условия;

2. упрощению этой функции;

3. построению соответствующей схемы.

20. В чем заключается анализ логической схемы?

1. определению значений её функции проводимости при всех возможных наборах входящих в эту функцию переменных.

2. получению упрощённой формулы.

21. Выделить основные способы решения логических задач.

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

I. Решение логических задач средствами алгебры логики

Обычно используется следующая схема решения:

1. изучается условие задачи;

2. вводится система обозначений для логических высказываний;

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

4. определяются значения истинности этой логической формулы;

5. из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.

II. Решение логических задач табличным способом

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

III. Решение логических задач с помощью рассуждений

Этим способом обычно решают несложные логические задачи.

22. Установить, какие из следующих предложений являются логическими высказываниями, а какие — нет (объяснить почему):

а) " Солнце есть спутник Земли" – является логич. высказванием, т.к. это повествоват. предложение, в отношении которого можно сказать истинно оно или ложно

б) " 2+3=4" – является

в) " сегодня отличная погода" не является, т.к. ничего не утверждает

г) " в романе Л.Н. Толстого " Война и мир" 3 432 536 слов" – является

д) " Санкт-Петербург расположен на Неве" – является

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

истинны: д

ложны: а, б

истинность трудно или невозможно установить: г

24.Привести примеры истинных и ложных высказываний:

математика: 2+2=4, 3*3=8

физика: Действию всегда есть равное и противоположное противодействие; сила тяжести находится по формуле: Fтяж+m/g

информатика: 1+1=10; 1–0=0

из жизни: В. Путин – президент РФ, Д. Медведев – брат В. Путина

25. Сформулировать отрицания следующих высказываний:

а) " Эльбрус — не высочайшая горная вершина Европы"

б) " 2> =5" 2< 5

д) " теннисист Кафельников не проиграл финальную игру" теннисист Кафельников проиграл финальную игру

е) " мишень поражена первым выстрелом" мишень не поражена первым выстрелом

26. Из двух данных высказываний a и b построить составное высказывание, которое было бы:

а) ; б) .

27. Составить таблицы истинности логических формул:

-

28. Упростить логические формулы:

-

29. Составить таблицу истинности для логической схемы, представленной на рис. 5.8. Записать выражения для точек схемы а, б, в.

-

30. Составить таблицу истинности для логической схемы, представленной на рис. 5.9. Записать выражения для точек а и в. Нельзя ли схему упростить?

-

31. Построить логическую схему для формулы

-

32. В соревнованиях по гимнастике участвуют Маша, Света, Лена и Таня. Болельщики высказали предположения о возможных победителях:

а) Л – 1, С – 2, б) Л – 2, Т – 3, в) М – 2, Т – 4.

Если верно 1 утверждение, значит, Лена будет первой, тогда Саша не будет второй, иначе это противоречит условиям задачи, тогда во втором утверждении Таня будет третьей, т.к. Лена первая и она не может быть второй, тогда в третьем утверждении Маша будет второй, а Таня не будет четвертой, т.к Таня – третья.

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

Роза выращивает анютины глазки, Маргарита выращивает розы, Анюта выращивает маргаритки.

34. Виновник ночного дорожно-транспортного происшествия скрылся с места аварии. Первый из опрошенных свидетелей сказал работникам ГАИ, что это были " Жигули", первая цифра номера машины — единица.
Второй свидетель сказал, что машина была марки " Москвич", а номер начинался с семёрки. Третий свидетель заявил, что машина была иностранная, номер начинался не с единицы. При дальнейшем расследовании выяснилось, что каждый из свидетелей правильно указал либо только марку машины, либо только первую цифру номера. Какой марки была машина и с какой цифры начинался номер?

1) Жигули – номер 1

2) Москвич – номер 7

3) Иномарка – номер не 1

Если верно 1 утверждение, значит марка машины – Жигули, а номер не начинается с 1, тогда в третьем утверждении верно, что номер машины не 1, и подтверждается, что машина не иномарка, тогда во втором утверждении видно, что номер машины начинается с 7.

Ответ: машина – Жигули, номер начинается с 7.

35. Школьник попросил троих друзей отгадать, какое он задумал число из набора: положительное, отрицательное, четное, нечетное, целое и дробное.

1) Саша – первый, Виктор – второй

2) Саша – второй, Дима – четвертый

3) Андрей – второй, Дима – четвертый

Если верно 1 утверждение, значит Виктор не занял 2 место, во втором случае получается, что Дима занял 3 место, т.к. утверждение что Саша займет 2 место – ложно, т.к. Саша займет 1 место, в третьем высказывании Андрей займет 2 место, а Дима не займет 4, т.к. он займет 3 место, значит Виктор займет 4 место.

36. В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что вода и молоко не в бутылке. Сосуд с лимонадом находится между кувшином и сосудом с квасом, в банке – не лимонад и не вода. Стакан находится между банкой и сосудом с молоком. Как распределены жидкости по сосудам?

Число у нас может быть либо положительным, либо отрицательным (0 в наборе нет). Пусть число будет положительным - тогда (3) оно нечетное и (2) целое. Первая импликация роли не играет, т.к. посылка ложна. Итого: целое положительное нечетное подходит. Пусть отрицательное - тогда оно не (целое и положительное) - поэтому (2) оно четное. Из этого (1) следует, что оно положительное. Противоречие.