Урок " Логические выражения и операции "
Алгебра высказываний
Алгебра высказываний была разработана для того, чтобы можно было определять истинность или ложность составных высказываний, не вникая в их содержание.
В алгебре высказываний суждениям (простым высказываниям) ставятся в соответствие логические переменные, обозначаемые прописными буквами латинского алфавита.
Рассмотрим два простых высказывания:
А = «Два умножить на два равно четырем». В = «Два умножить на два равно пяти».
Высказывания, как уже говорилось ранее, могут быть истинными или ложными. Истинному высказыванию соответствует значение логической переменной 1, а ложному — значение 0. В нашем случае первое высказывание истинно (А = 1), а второе ложно (В = 0).
В алгебре высказываний высказывания обозначаются именами логических переменных, которые могут принимать лишь два значения:
«истина» (1) и «ложь» (0).
До сих пор мы рассматривали простые высказывания. На основании простых высказываний могут быть построены составные высказывания. Например, высказывание «Процессор является устройством обработки информации и принтер является устройством печати» является составным высказыванием, состоящим из двух простых, соединенных союзом «и».
Если истинность или ложность простых высказываний устанавливается в результате соглашения на основании здравого смысла, то истинность или ложность составных высказываний вычисляется с помощью использования алгебры высказываний.
Приведенное выше составное высказывание истинно, так как истинны входящие в него простые высказывания.
В алгебре высказываний над высказываниями можно производить определенные логические операции, в результате которых получаются новые, составные высказывания.
Для образования новых высказываний наиболее часто используются базовые логические операции, выражаемые с помощью логических связок «и», «или», «не».
И — Логическое умножение (конъюнкция)
Объединение двух (или нескольких) высказываний в одно с помощью союза «и» называется операцией логического умножения или конъюнкцией.
Составное высказывание, образованное в результате операции логического умножения (конъюнкции), истинно тогда и только тогда, когда истинны все входящие в него простые высказывания.
Так, из приведенных ниже четырех составных высказываний, образованных с помощью операции логического умножения, истинно только четвертое, так как в первых трех составных высказываниях хотя бы одно из простых высказываний ложно:
(1) «2 • 2 = 5 и 3 • 3 = 10», (2) «2 • 2 = 5 и 3 • 3 = 9»,
(3) «2 -2 = 4 и 3 • 3 = 10», (4) «2 • 2 == 4 и 3 • 3 = 9».
Перейдем теперь от записи высказываний на естественном языке к их записи на формальном языке алгебры высказываний (алгебры логики). В ней операцию логического умножения (конъюнкцию) принято обозначать значком «&» либо «/». Образуем составное высказывание Р, которое получится в результате конъюнкции двух простых высказываний: F = А & В
С точки зрения алгебры высказываний мы записали формулу функции логического умножения, аргументами которой являются логические переменные А и В, которые могут принимать значения «истина» (1) и «ложь» (0).
Сама функция логического умножения F также может принимать лишь два значения «истина» (1) и «ложь» (0). Значение логической функции можно определить с помощью таблицы истинности данной функции, которая показывает, какие значения принимает логическая функция при всех возможных наборах ее аргументов:
Цели урока:
- Обучающая – формировать у учащихся понятие логической величины и логических операций; ввести понятие основных логических операций; вырабатывать умение формализовать сложные высказывания, знакомство с разделом математики алгебра логики; формировать практические умения решать логические задачи.
- Развивающая – развивать логическое мышление, умение определять высказывание из различных видов предложений.
- Воспитательная – способствовать воспитанию аккуратности, терпению, культурному и интеллектуальному развитию учеников.
Оборудование: ПК, проектор, экран, Презентация (Приложение 1).
План урока:
- Организационный момент.
- Проверка домашнего задания.
- Усвоение новых знаний. Лекция.
- Первичная проверка понимания изученного.
- Обобщение и систематизация знаний.
- Подведение итогов.
- Постановка домашнего задания.
1. Организационный момент
2. Ответьте на вопросы:
– Может ли быть высказывание выражено в форме вопросительного предложения?
– Как определяется истинность или ложность простого высказывания? Составного высказывания?
3. Лекция
Алгебра в широком смысле этого слова наука об общих операциях, аналогичных сложению и умножению, которые могут выполняться над различными математическими объектами (алгебра переменных и функций, алгебра векторов, алгебра множеств и т.д.). Объектами алгебры логики являются высказывания.
Алгебра логики отвлекается от смысловой содержательности высказываний. Ее интересует только один факт — истинно или ложно данное высказывание, что дает возможность определять истинность или ложность составных высказываний алгебраическими методами.
Простые высказывания в алгебре логики обозначаются заглавными латинскими буквами:
Составные высказывания на естественном языке образуются с помощью союзов, которые в алгебре высказываний заменяются на логические операции.
Логические операции задаются таблицами истинности и могут быть графически проиллюстрированы с помощью диаграмм Эйлера-Венна.
Логическое умножение (конъюнкция)
Объединение двух высказываний в одно при помощи союза «И» называется операцией логического умножения(конъюнкцией). Полученное таким образом высказывание называется логическимпроизведением.
Опр.: Составное высказывание, образованное в результате операции логического умножения, истинно тогда и только тогда, когда истинны все входящие в него простые высказывания
Логическое умножение
Объединение двух высказываний в одно с помощью союза «ИЛИ», называется операцией логического сложения (дизъюнкцией).
Составное высказывание, образованное в результате логического сложения (дизъюнкции), истинно тогда, когда истинно хотя бы одно из входящих в него простых высказываний.
Логическое отрицание (инверсия)
Присоединение частицы «не» к высказыванию называется операцией логического отрицания или инверсией.
Логическое отрицание (инверсия) делает истинное высказывание ложным и, наоборот, ложное – истинным.
Импликация (логическое следование)
в естественном языке соответствует обороту если . то . ; обозначение ––> .
Импликация – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие (первое высказывание) истинно, а следствие (второе высказывание) ложно.
Эквиваленция (РАВНОЗНАЧНОСТЬ):
в естественном языке соответствует оборотам речи тогда и только тогда; в том и только в том случае;
обозначения Û ,
.
Эквиваленция – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или одновременно ложны.
Определим истинность составного высказывания:
(не А & не В) & (C Ú D),
состоящего из простых высказываний:
А = <Принтер – устройство вывода информации>,
В = <Процессор – устройство хранения информации>,
С = <Монитор – устройство вывода информации>,
D = <Клавиатура – устройство обработки информации>.
Сначала на основании знания устройства компьютера устанавливаем истинность простых высказываний:
А = 1, В = 0, С = 1, D = 0.
Определим теперь истинность составного высказывания, используя таблицы истинности логических операций:
( не 1& не 0 ) &(1 Ú 0) = (0&1) & (1 Ú 0) = 0
Составное высказывание ложно.
Определим какие из высказываний А, В, С должны быть истинны и какие ложны, чтобы было ложно логическое выражение
((A Ú В)& В) ––> С.
Импликация ложна на единственном наборе логических значений (1, 0).
Значит, ((A Ú В) & В) = 1, С = 0.
Конъюнкция истинна на единственном наборе логических значений (1, 1).
Значит, (A Ú В) = 1 и В = 1.
Дизъюнкции истинна при наборах логических значений (0, 1) и (1, 1).
Следовательно, существуют два набора логических значений, удовлетворяющих условию задачи:
(А = 0, В = 1, С = 0) и (А = 1, В = 1, С = 0).
4. Первичная проверка понимания изученного.
1. Заполнить таблицу:
Этимология названия логической операции
Название логической операции
Таблица истинности логической операции
Соответствующие операции в теории множеств
Пример высказывания, построенного с использованием логической связки
«Неверно, что число 10 отрицательное» ИСТИНА
2. Для каждого составного высказывания (логического выражения) можно построить таблицу истинности, которая определяет истинность или ложность логического выражения при всех возможных комбинациях исходных значений простых высказываний (логических переменных).
3. При построении таблиц истинности целесообразно руководствоваться определенной последовательностью действий:
1) записать выражение и определить порядок выполнения операций
2) определить количество строк в таблице истинности. Оно равно количеству возможных комбинаций значений логических переменных, входящих в логическое выражение (определяется по формуле Q = 2 n , где n – количество входных переменных)
3) определить количество столбцов в таблице истинности (= количество логических переменных + количество логических операций)
4) построить таблицу истинности, обозначить столбцы (имена переменных и обозначения логических операций в порядке их выполнения) и внести в таблицу возможные наборы значений исходных логических переменных.
заполнить таблицу истинности, выполняя базовые логические операции в необходимой последовательности и в соответствии с их таблицами истинности
Теперь мы можем определить значение логической функции для любого набора значений логических переменных.
Например, построим таблицу истинности для логической функции: 
Количество входных переменных в заданном выражении равно трем (A, B, C). Значит, количество входных наборов, а значит и строк Q = 2 3 = 8. Количество столбцов равно 6 (3 переменные + 3 операции).
5. Обобщение и систематизация знаний
Проверочная работа по теме «Дизъюнкция, конъюнкция, отрицание
1. Найдите значения логических выражений:
2. Даны два простых высказывания:
Какие из высказываний истинны:
а) А; б) В; в) А&В; г) AvB ; д) ¬A; е) A ^ В; ж) А ^ ¬В?
3. Даны простые высказывания:
Проверочная работа по теме «Импликация и эквивалентность»
1. Даны истинные высказывания: А = «на улице идет снег» и В = «нужно надеть шапку». Составьте высказывания: а) А => B, б) B => A, которые будут принимать ложные значения.
2. Даны истинные высказывания А = «Карлсон хочет варенье» и В = «Карлсон летает на свежем воздухе». Составьте истинные высказывания вида A B.
3. Даны простые высказывания:
Определите истинность составных высказываний:
4. Даны простые высказывания:
6. Подведение итогов
Обобщить пройденный материал
7. Домашнее задание
1. Выучить определения, знать обозначения.
2. Даны высказывания:
Составьте два сложных высказывания, одно из которых в любой ситуации всегда будет ложным, а другое истинным.
3. Составьте таблицу истинности для формул:
Тема программы: Высказывания и операции над ними.
1) Обобщить теоретические знания по теме: «Высказывания и операции над ними».
2) Рассмотреть алгоритмы решений заданий теме «Высказывания и операции над ними», решить задачи.
3) Формировать умение прогнозировать собственную деятельность, умение организовать свою деятельность и анализировать ее.
Время выполнения: 1 час.
Теоретические основы
Основным понятием математической логики является понятие «простого высказывания». Под высказыванием обычно понимают всякое повествовательное предложение, утверждающее что-либо о чем-либо, и при этом мы можем сказать, истинно оно или ложно в данных условиях места и времени. Логическими значениями высказываний являются «истина» и «ложь».
Примеры высказываний.
1) Москва стоит на Неве.
2) Лондон — столица Англии.
3) Сокол не рыба.
4) Число 6 делится на 2 и на 3.
Высказывания 2), 3), 4) истинны, а высказывание 1) ложно.
Очевидно, предложение «Да здравствует Россия!» не является высказыванием.
Различают два вида высказываний.
Высказывание, представляющее собой одно утверждение, принято называть простым или элементарным. Примерами элементарных высказываний могут служить высказывания 1) и 2).
Высказывания, которые получаются из элементарных с помощью грамматических связок «не», «и», «или», «если . то . », «тогда и только тогда», принято называть сложными или составными.
Так, высказывание 3) получается из простого высказывания «Сокол — рыба» с помощью отрицания «не», высказывание 4) образовано из элементарных высказываний «Число 6 делится на 2», «Число 6 делится на З», соединенных союзом «и».
Аналогично сложные высказывания могут быть получены из простых высказываний с помощью грамматических связок «или», «тогда и только тогда».
В алгебре логики все высказывания рассматриваются только с точки зрения их логического значения, а от их житейского содержания отвлекаются. Считается, что каждое высказывание либо истинно, либо ложно и ни одно высказывание не может быть одновременно истинным и ложным.
Элементарные высказывания обозначаются малыми буквами латинского алфавита: х, у, z, . а, b, с, . ; истинное значение высказывания цифрой 1, а ложное значение — буквой цифрой 0.
Если высказывание а истинно, то будем писать а = 1, а если а ложно, то а = 0.
Логические операции над высказываниями
Отрицанием высказывания х называется новое высказывание 
, которое является истинным, если высказывание х ложно, и ложным, если высказывание х истинно.
Отрицание высказывания х обозначается и читается «не х» или «неверно, что х».
Логические значения высказывания можно описать с помощью таблицы.
Таблицы такого вида принято называть таблицами истинности.
Пусть х высказывание. Так как также является высказыванием, то можно образовать отрицание высказывания , то есть высказывание 
, которое называется двойным отрицанием высказывания х. Ясно, что логические значения высказываний х и совпадают.
Например, для высказывания «Путин президент России» отрицанием будет высказывание «Путин не президент России», а двойным отрицанием будет высказывание «Неверно, что Путин не президент России».
Конъюнкцией (логическим умножением) двух высказываний х и у называется новое высказывание, которое считается истинным, если оба высказывания х и у истинны, и ложным, если хотя бы одно из них ложно.
Конъюнкция высказываний х и у обозначается символом х&у ( 
, ху ) , читается «х и у» . Высказывания х и у называются членами конъюнкции.
Логические значения конъюнкции описываются следующей таблицей истинности:
Например, для высказываний «6 делится на 2», «6 делится на 3» их конъюнкцией будет высказывание «6 делится на 2 и 6 делится на 3», которое, очевидно, истинно.
Из определения операции конъюнкции видно, что союз «и» в алгебре логики употребляется в том же смысле, что и в повседневной речи. Но в обычной речи не принято соединять союзом «и» два высказывания далеких друг от друга по содержанию, а в алгебре логики рассматривается конъюнкция двух любых высказываний.
Дизъюнкцией (логическим сложением) двух высказываний х и у называется новое высказывание, которое считается истинным, если хотя бы одно из высказываний х, у истинно, и ложным, если они оба ложны. Дизъюнкция высказываний х, у обозначается символом «x V у» , читается «х или у» . Высказывания х, у называются членами дизъюнкции.
Логические значения дизъюнкции описываются следующей таблицей истинности:
В повседневной речи союз «или» употребляется в различном смысле: исключающем и не исключающем. В алгебре логики союз «или» всегда употребляется в не исключающем смысле.
Импликацией двух высказываний х и у называется новое высказывание, которое считается ложным, если х истинно, а у — ложно, и истинным во всех остальных случаях.
Импликация высказываний х, у обозначается символом 
, читается«если х, то у» или «из х следует у». Высказывание х называют условием или посылкой, высказывание у — следствием или заключением, высказывание следованием или импликацией.
Логические значения операции импликации описываются следующей таблицей истинности:
Употребление слов «если . то . » в алгебре логики отличается от употребления их в обыденной речи, где мы, как правило, считаем, что, если высказывание х ложно, то высказывание «Если х, то у» вообще не имеет смысла. Кроме того, строя предложение вида «если х, то у» в обыденной речи, мы всегда подразумеваем, что предложение у вытекает из предложения х . Употребление слов «если . то . » в математической логике не требует этого, поскольку в ней смысл высказываний не рассматривается.
Импликация играет важную роль в математических доказательствах, так как многие теоремы формулируются в условной форме «Если х, то у». Если при этом известно, что х истинно и доказана истинность импликации , то мы вправе сделать вывод об истинности заключения у .
Эквивалентностью двух высказываний х и у называется новое высказывание, которое считается истинным, когда оба высказывания х, у либо одновременно истинны, либо одновременно ложны, и ложным во всех остальных случаях.
Эквивалентность высказываний х, у обозначается символом 
, читается«для того, чтобы х, необходимо и достаточно, чтобы у» или «х тогда и только тогда, когда у». Высказывания х, у называются членами эквивалентности.
Логические значения операции эквивалентности описываются следующей таблицей истинности:
Эквивалентность играет важную роль в математических доказательствах. Известно, что значительное число теорем формулируется в форме необходимых и достаточных условий, то есть в форме эквивалентности. В этом случае, зная об истинности или ложности одного из двух членов эквивалентности и доказав истинность самой эквивалентности, мы заключаем об истинности или ложности второго члена эквивалентности.
Практические задания
1. Установить логическую структуру следующих предложений и записать их на языке логики высказываний:
- Если металл нагревается, он плавится.
- Неправда, что философские споры неразрешимы.
- Деньги — продукт стихийного развития товарных отношений, а не результат договоренности или какого-либо иного сознательного акта.
2. Записать логической формулой следующие высказывания:
а) если на улице дождь, то нужно взять с собой зонт или остаться дома;
б) если — прямоугольный и стороны — равны, то
3. Проверить истинность высказывания:
4. Проверить истинность высказывания:
а) Чтобы завтра пойти на занятия, я должен встать рано. Если я сегодня пойду в кино, то лягу спать поздно. Если я лягу спать поздно, то встану поздно. Следовательно, либо я не пойду в кино, либо не пойду на занятия.
б) Я пойду либо в кино, либо в бассейн. Если я пойду в кино, то получу эстетическое удовольствие. Если я пойду в бассейн, то получу физическое удовольствие. Следовательно, если я получу физическое удовольствие, то не получу эстетического удовольствия.
5 
. На вопрос: «Кто из трех студентов изучал дискретную математику?» получен верный ответ: «Если изучал первый, то изучал и третий, но неверно, что если изучал второй, то изучал и третий». Кто изучал дискретную математику?
6. Определите, кто из четырех студентов сдал экзамен, если известно:
если первый сдал, то и второй сдал;
если второй сдал, то третий сдал или первый не сдал;
если четвертый не сдал, то первый сдал, а третий не сдал;
если четвертый сдал, то и первый сдал.
Контрольные вопросы
1. Какие элементы входят язык логики?
2. Какие способы установления общезначимости формулы логики вы знаете?
Список литературы
| 1.Аляев Ю.А. Тюрин С.Ф. Дискретная математика и математическая логика. — М.: Финансы и статистика, 2006. — 368 с. |
| 2.Варпаховский Ф.Л. Элементы теории алгоритмов. — М., Просвещение, 1970. — 25 с. (МГЗПИ) |
| 3.Гуц А.К. Математическая лоrика и теория алrоритмов. — Омск: Издательство Наследие. Диалог-Сибирь, 2003. — 108 с. |
| 4.Босс В. Лекции по математике. Т. 6: От Диофанта до Тьюринга. — М.: КомКнига, 2006. — 208 с. |
| 5.Босс В. Лекции по математике. Т. 10: Перебор и эффективные алгоритмы: Учебное пособие. — М.: Издательство ЛКИ, 2008. — 216 с. |
Практические занятия № 10-11
Тема программы: Формулы алгебры высказываний.
Дата добавления: 2018-02-28 ; просмотров: 2999 ; ЗАКАЗАТЬ РАБОТУ
