Лекция 5. 1. Алгебра логики (алгебра высказываний) раздел математической логики
 Скачать 23.5 Kb.
|
|
1. Алгебра логики (алгебра высказываний) — раздел математической логики, в котором изучаются логические операции над высказываниями[1]. Чаще всего предполагается, что высказывания могут быть только истинными или ложными, то есть используется так называемая бинарная или двоичная логика, в отличие от, например, троичной логики. Основоположником её является Дж. Буль, английский математик и логик, положивший в основу своего логического учения аналогию между алгеброй и логикой. Алгебра логики стала первой системой математической логики, в которой алгебраическая символика стала применяться к логическим выводам в операциях с понятиями, рассматриваемыми со стороны их объёмов. Буль ставил перед собой задачу решить логические задачи с помощью методов, применяемых в алгебре. Любое суждение он пытался выразить в виде уравнений с символами, в которых действуют логические законы, подобные законам алгебры. 2. Логическое высказывание – это повествовательное предложение, про которое можно однозначно сказать, истинно оно или ложно. Математический аппарат, с помощью которого записывают, упрощают и преобразуют логические высказывания, вычисляют их значения, называется алгеброй логики. Основными логическими операциями, определенными над высказываниями, являются: инверсия, конъюнкция и дизъюнкция. 3. Логическая связка– это союзы или выражения, которые употребляются в естественном языке для соединения простых высказываний в сложные. Итак, первая логическая операция – инверсия. Ей соответствуют следующие логические связки: «не», «неверно, что». Вторая – конъюнкция и соответственно её логические связки: «и», «а», «но», «хотя». И последняя, третья логическая операция – дизъюнкция. У неё всего одна логическая связка «или». 4. Высказывание называется простым (элементарным), если оно рассматривается как некое неделимое целое. Сложным (составным) называется высказывание, составленное из простых с помощью логических связок (операций). Основными логическими операциями над высказываниями являются: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность, неравнозначность. 5. Логические операции — это создание сложных суждений из двух и более простых. Ещё они называются логическими связками. С помощью логических операций можно проверить, если связь между высказываниями является истинной или ложной. Основные логические операции: конъюнкция (логическое "и", A ⋀ B); дизъюнкция (логическое "или", A ∨ B); отрицание ("не", Ā); импликация ("если…, то…", A → B); эквиваленция ("тогда и только тогда, когда", A ↔ B). 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 слов" – является д) "Санкт-Петербург расположен на Неве" – является е) "музыка Баха слишком сложна" – не является, т.к. используется слишком неопределенное понятие «слишком сложна» ж) "первая космическая скорость равна 7.8 км/сек" – является з) "железо — металл" - является и) "если один угол в треугольнике прямой, то треугольник будет тупоугольным" – является к) "если сумма квадратов двух сторон треугольника равна квадрату третьей, то он прямоугольный" – является. 23. истинны: д, з, и, к ложны: а, б истинность трудно или невозможно установить: г, ж 24. математика: 2+2=4, 3*3=8 физика: Действию всегда есть равное и противоположное противодействие; сила тяжести находится по формуле: Fтяж+m/g биология: Ч. Дарвин – основоположник эволюционной теории; корова – млекопитающее животное информатика: 1+1=10; 1–0=0 геометрия: Сфера является поверхностью шара; если один из углов треугольника больше 90о, такой треугольник не является тупоугольным из жизни: В. Путин – президент РФ, Д. Медведев – брат В. Путина 25. а) "Эльбрус — не высочайшая горная вершина Европы" б) "2>=5" 2<5 в) "10<7" 10>=7 г) "все натуральные числа целые" не все целые числа натуральные д) "теннисист Кафельников не проиграл финальную игру" теннисист Кафельников проиграл финальную игру е) "мишень поражена первым выстрелом" мишень не поражена первым выстрелом 26. не(a*b) = 1, если a=0, b=0. не(a*b) = 0, если a=1, b=1. 27. . В соревнованиях по гимнастике участвуют Маша, Света, Лена и Таня. Болельщики высказали предположения о возможных победителях: а) «Первой будет Лена, Света будет второй»; б) «Второй будет Лена, Таня будет третьей»; в) «Второй будет Маша, Таня будет четвертой». Первое место заняла Лена, второе – Маша, третье – Таня, четвертое – Света. 28.
29. Вычисляется очень просто. Значит, свидетели указали следующее: 1. Жигули, с единицы номер. 2. Москвич, с семерки номер. 3. Иномарка, не с единицы. Каждый сказал один факт правду и один - ложь. Предположим, что первый верно указал цифру 1. Значит, он обманул относительно жигулей. Раз номер с единицы начинается, то другие двое обманули относительно номера, а значит, верно указали марку машины. Но они не могли оба верно указать марку, ведь один сказал - "Москвич", а второй - "иномарка". Значит первое предположение, что номер начинается с единицы - привело нас в тупик. Раз номер не с единички, то первый обманул про номер, значит правду сказал про марку - это "Жигули". Раз марка жигули, то второй обманул про Москвич, а значит верно сказал про номер с семерки. Третий значит, обманул про иномарку, но верно сказал, что номер не с единицы начинается. Итого - это были "Жигули" и номер начинается с семерки. 30. 1. Если число четное, то из предположения первого следует, что оно положительное. Тогда из предположения третьего следует, что число нечетное, и приходим к противоречию. Значит, число нечетное. 2. Первое из двух возможных предположений второго участника игры, т. е., что число четное, не верно, значит, число целое и положительное. 3. Следовательно, приходим к чрезвычайно важному, для всего человечества, заключению: задуманное школьником число положительное, целое и нечетное. Ответ: положительное, целое и нечетное. 31. Бутылка - НЕ вода, НЕ молоко (т.к. вода и молоко не в бутылке Стакан - НЕ молоко (т.к. Стакан находится около сосуда с молоком) Кувшин -НЕ лимонад, НЕ квас (т.к. а сосуд с лимонадом находится между кувшином и сосудом с квасом) Банка - НЕ лимонад, НЕ вода, НЕ молоко (т.к. в банке - не лимонад и не вода., ...около банки и сосуда с молоком), остается, что в банке - квас т.к. в бутылке и стакане НЕ молоко, значит молоко в кувшине т.к. в бутылке НЕ вода, значит вода в стакане значит остается, что в бутылке - лимонад Ответ: в банке - квас молоко в кувшине вода в стакане в бутылке - лимонад 32.
|