Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
курс 1 семестр
Логическая информация и основы логики.
Тема: Основные понятия алгебры логики.
Цель: сформировать понятие алгебры логики, высказывания, логических связок, таблицы истинности, умение использовать логические связки, узнавать и различать высказывания и высказывательные формы, развить навыки мышления. Способствовать формированию логического мышления.
Оборудование:
План урока.
Тема нашего урока – «Основные понятия алгебры логики».
Алгебра логики – это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними.
Алгебра логики возникла в середине 19 века в трудах английского математика Джорджа Буля. Отсюда и другое ее название – булева алгебра. Ее создание представляло собой попытку решать традиционные логические задачи алгебраическими методами. В дальнейшем математический аппарат булевой алгебры позволил формализовать действия над логическими выражениями и явился базой для разработки логических элементов и, в целом, логических основ построения компьютеров.
Нам же с Вами нужно научиться решать логические задачи не просто интуитивно, а используя имеющиеся в настоящий момент приемы решения таких задач. Для понимания этих приемов познакомимся и запишем основные понятия алгебры логики:
Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.
Например: «6 – четное число» - высказывание
«ученик десятого класса» - не высказывание (о его истинности говорить бессмысленно)
«информатика – интересный предмет» - не высказывание (слишком неопределенное понятие «интересный предмет»)
«X>5» - не высказывание (об истинности можно говорить только тогда, когда точно известно значение переменной X)
Логическое выражение (высказывательная форма) – повествовательное предложение, которое прямо или косвенно содержит хотя бы одну переменную и становится высказыванием, когда все переменные замещаются своими значениями.
Например: «Компьютер имеет оперативную память объемом не менее 32 Мб»
«A>5»
Давайте потренируемся узнавать высказывания:
№ 1. Какие из предложений являются высказываниями? Определите их истинность.
Высказывания могут быть составными (сложными) и элементарными (простыми). Все высказывания рассмотренные нами выше были элементарными (простыми).
В составных высказываниях несколько простых высказываний связываются знаками логических операций (логическими связками)
В большинстве случаев мы имеем дело с составными высказываниями.
Например: 2 простых высказывания «Дима – ученик 10 класса»
«Дима – шахматист»
Можно объединить в одно сложное высказывание:
«Дима – ученик 10 класса и шахматист»
Истинность такого высказывания зависит от истинности исходных элементарных высказываний.
В качестве логической связки мы использовали союз «и». В логике используются такие логические связки как «и», «или», «не».
№ 2. Из двух простых высказываний постройте сложное высказывание, используя логические связки «И», «ИЛИ»: Например:
|
Все ученики изучают математику. Все ученики изучают литературу. |
Все ученики изучают математику и литературу. |
№ 3. Определите значение истинности следующих высказываний, укажите элементарные высказывания:
Чтобы обращаться к логическим высказываниям, им назначают имена. Пусть через А обозначено высказывание «Тимур поедет летом на море», а через В — высказывание «Тимур летом отправится в горы». Тогда составное высказывание «Тимур летом побывает и на море, и в горах» можно кратко записать как «А и В».
Попробуем и мы кратко записать такие выражения
№4. Выделите из составного высказывания элементарные, назначьте им имена и запишите высказывание в краткой форме.
Например: «Приставка есть часть слова, и она пишется раздельно со словом»
A = «Приставка есть часть слова.»
B = «Приставка пишется раздельно со словом»
Кратко: A и B
В результате выполнения операций над простыми высказываниями получается сложное высказывание, истинность которого зависит от истинности простых высказываний и от применяемой операции.
Например: Буква «а» — первая буква в слове «аист» или «сова». – истинное высказывание.
Замените операцию ИЛИ на И, и проверьте истинность полученного высказывания
Буква «а» — первая буква в слове «аист» и «сова». – ложное высказывание.
Каждая логическая связка рассматривается как операция над высказываниями и имеет свое название и обозначение. Рассмотрим их подробнее.
Операция И. В логике эта операция называется конъюнкцией и обозначается & или /\. Высказывание A /\ B (А конъюнкция Б или А И Б) истинно тогда и только тогда, когда истинны оба высказывания A и B. Представим определение в виде специальной таблицы – таблицы истинности:
Высказывание может быть истинным или ложным. Т.е. принимать значения «Ложь» или «Истина». В логике принято обозначать логическую величину «Ложь» символом «0», а логическую величину «Истина» - символом «1».
|
A |
B |
A /\ B |
|
0 |
0 |
0 |
|
0 |
1 |
0 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
Операция ИЛИ. Называется дизъюнкцией и обозначается \/. Высказывание A \/ B (А дизъюнкция Б или А ИЛИ Б) истинно тогда и только тогда, когда хотя бы одно из высказываний А или B истинно.
Этой операции соответствует таблица истинности:
|
A |
B |
A \/ B |
|
0 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
1 |
Найдите отличия.
Операция НЕ. Называется инверсией и обозначается чертой над высказыванием или знаком ┐. Высказывание истинно, когда A ложно, и ложно, когда A истинно.
Ей соответствует таблица истинности:
|
A |
|
|
0 |
0 |
|
1 |
1 |
В чем отличие данной операции от двух предыдущих?
Кроме рассмотренных трех основных операций в логике используются еще две:
Импликация. Обозначается →. Высказывание A→B (А импликация Б, из А следует Б) ложно тогда и только тогда, когда А – истинно, а B – ложно.
Данная операция на обычном языке может выражаться словами «если …, то…», «из … следует …», «… влечет …».
Таблица истинности выглядит так:
|
A |
B |
A→B |
|
0 |
0 |
1 |
|
0 |
1 |
1 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
Эквиваленция. Обозначается ↔. Высказывание A↔B (А эквиваленция Б, А равносильно Б) истинно тогда и только тогда, когда значения A и B совпадают.
Данная операция на обычном языке может выражаться словами «тогда и только тогда», «необходимо и достаточно», «… равносильно …».
Ее таблица истинности такова:
|
A |
B |
A↔B |
|
0 |
0 |
1 |
|
0 |
1 |
0 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
Высказывания A и В, образующие составное высказывание А↔В, могут быть совершенно не связаны по содержанию, например: «три больше двух» (A), «пингвины живут в Антарктиде» (В). Отрицаниями этих высказываний являются высказывания «три не больше двух» (), «пингвины не живут в Антарктиде» (). Образованные из высказываний А, В составные высказывания А↔В и истинны, а высказывания и ложны.
Итак, нами рассмотрены пять логических операций: отрицание, конъюнкция, дизъюнкция, импликация и эквиваленция.
Импликацию можно выразить, через дизъюнкцию и отрицание:
А→В= &B.
Эквивалентно можно выразить через отрицание, дизъюнкцию и конъюнкцию:
А↔В = (\/B)&(B\/A).
Таким образом, операций отрицания, дизъюнкции и конъюнкции достаточно, чтобы описывать и обрабатывать логические высказывания.
Порядок всех пяти логических операций по убыванию старшинства следующий:
Если требуется изменить порядок выполнения операций, то используются круглые скобки.
Применять на практике данные операции мы научимся на следующем занятии.
№5. Какие из следующих предложений являются высказываниями? Определите их истинность.
Назовите и дайте определения логическим операциям.
Приведите примеры истинных и ложных высказываний с применением каждой логической операции.
№6 Используя связку «ЕСЛИ..., ТО...», измените высказывания. Например: Человек, любящий животных, -- добрый. -> Если человек любит животных, то он — добрый.
№7. Могут ли быть истинными следующие высказывания?
№8. Запишите в виде логической формулы следующие высказы вания:
Домашнее задание: (5 минут).
№ 1. Определите истинность высказывания.
Выучить определения логических операций и их таблицы истинности.
Подведение итогов.
Основные законы алгебры логики.
Логическая информация и основы логики.
Тема: Логические формулы.
Цель: сформировать понятие логической формулы, умение выполнять логические операции над высказываниями, строить таблицы истинности. Способствовать развитию внимания, формированию логического мышления.
На предыдущем уроке мы узнали что такое высказывание, научились отличать высказывания от других предложений и от высказывательных форм, научились использовать логические связки для составления сложных высказываний, узнали какие логические операции при этом могут использоваться. Какие это логические операции?
С помощью логических переменных и символов логических операций любое высказывание можно формализовать, т.е. заменить логической формулой. Мы уже говорили, что логическая формула – это повествовательное предложение с переменными. Дадим теперь строгое определение:
В пункте 1 определены элементарные формулы, в пункте 2 даны правила образования из любых данных формул новых формул.
Например: формализуйте высказывания: «если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог», «если Игорь знает английский или японский язык, то он получит место переводчика». В обоих случаях получается одна и та же формула.
Давайте составим таблицу истинности для полученной формулы (A\/B)→C:
|
A |
B |
C |
A\/B |
(A\/B)→C |
|
0 |
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
0 |
1 |
|
0 |
1 |
0 |
1 |
1 |
|
0 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
0 |
|
1 |
0 |
1 |
1 |
1 |
|
1 |
1 |
0 |
1 |
0 |
|
1 |
1 |
1 |
1 |
1 |
Как показывает анализ формулы (A v В) -» С, при определенных сочетаниях значений переменных А, В и С она принимает значение «истина», а при некоторых других сочетаниях — значение «ложь». Такие формулы называются выполнимыми.
Некоторые формулы принимают значение «истина» при любых значениях истинности входящих в них переменных. Такой будет, например, формула A\/A, соответствующая высказыванию «этот треугольник прямоугольный или косоугольный». Эта формула истинна и тогда, когда треугольник прямоугольный, и тогда, когда треугольник непрямоугольный. Такие формулы называются тождественно-истинными формулами или тавтологиями.
Высказывания, которые формализуются тавтологиями, называются логически истинными высказываниями.
В качестве другого примера рассмотрим формулу А&, которой соответствует, например, высказывание «Катя – самая высокая девочка в классе, и в классе есть девочки выше Кати». Очевидно, что эта формула ложна, так как либо А, либо обязательно ложно. Такие формулы называются тождественно-ложными формулами или противоречиями.
Высказывания, которые формализуются противоречиями, называются «ложными высказываниями».
Если две формулы А и В одновременно, г. е. при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения, то они называются равносильными.
Равносильность двух формул алгебры логики обозначается символом «=» или символом «≡». Замена формулы другой, ей равносильной, называется равносильным преобразованием данной формулы.
№9. Из двух данных высказываний а и b постройте составное высказывание, которое было бы:
а) истинно тогда и только тогда, когда оба данных высказывания ложны;
б) ложно тогда и только тогда, когда оба данных высказывания истинны.
№10. Из трех данных высказываний а, b, с постройте составное высказывание, которое истинно, когда истинно какое-либо одно из данных высказываний, и только в этом случае.
Ответ:
№11*. Определите с помощью таблиц истинности, какие из следующих формул являются тождественно истинными или тождественно-ложными:
а) г) ж)
б) д)
в) e)
№2. Формализуйте предостережение, которое одна жительница Древних Афин сделала своему сыну, собиравшемуся заняться политической деятельностью: «Если ты будешь говорить правду, то тебя возненавидят люди. Если ты будешь лгать, то тебя возненавидят боги. Но ты должен говорить правду или лгать. Значит, тебя возненавидят люди или возненавидят боги».
Формализуйте также ответ сына: «Если я буду говорить правду, то боги будут любить меня. Если я буду лгать, то люди будут любить меня. Но я должен говорить правду или лгать. Значит, меня будут любить боги или меня будут любить люди».
№3. Определите с помощью таблиц истинности, какие из следующих формул являются тождественно истинными или тождественно-ложными (каждому индивидуально по 2 пункта):
PAGE \* MERGEFORMAT10