Алгебра высказываний

Разделы: Информатика


Цели урока:

  • Обучающая – формировать у учащихся понятие логической величины и логических операций; ввести понятие основных логических операций; вырабатывать умение формализовать сложные высказывания, знакомство с разделом математики алгебра логики; формировать практические умения решать логические задачи.
  • Развивающая – развивать логическое мышление, умение определять высказывание из различных видов предложений.
  • Воспитательная – способствовать воспитанию аккуратности, терпению, культурному и интеллектуальному развитию учеников.

Оборудование: ПК, проектор, экран, Презентация (Приложение 1).

План урока:

  1. Организационный момент.
  2. Проверка домашнего задания.
  3. Усвоение новых знаний. Лекция.
  4. Первичная проверка понимания изученного.
  5. Обобщение и систематизация знаний.
  6. Подведение итогов.
  7. Постановка  домашнего задания.

ХОД УРОКА

1. Организационный момент

2. Ответьте на вопросы:

– Может ли быть высказывание выражено в форме вопросительного предложения?
– Как определяется истинность или ложность простого высказывания? Составного высказывания?

3. Лекция

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

Простые высказывания  в алгебре логики обозначаются  заглавными  латинскими буквами:

А = {Аристотель – основоположник логики}
В = {На яблонях растут бананы}.
Истинному высказыванию ставится в соответствие 1, ложному — 0. Таким образом, А = 1, В = 0.

Составные высказывания на естественном языке образуются с помощью союзов, которые в алгебре высказываний заменяются на логические операции.
Логические операции задаются таблицами истинности и могут быть графически проиллюстрированы с помощью диаграмм Эйлера-Венна. 

Логическое умножение (конъюнкция)

Объединение двух высказываний в одно при помощи союза «И» называется операцией логического умножения(конъюнкцией). Полученное таким образом высказывание называется логическимпроизведением.
Опр.: Составное высказывание, образованное в результате операции логического умножения, истинно тогда и только тогда, когда истинны все входящие в него простые высказывания

Логическое умножение

Объединение двух высказываний в одно с помощью союза «ИЛИ», называется операцией логического сложения (дизъюнкцией).
Составное высказывание, образованное в результате логического сложения (дизъюнкции), истинно тогда, когда истинно хотя бы одно из входящих в него простых высказываний.

Логическое отрицание (инверсия)

Присоединение частицы «не» к высказыванию называется операцией логического отрицания или инверсией.
Логическое отрицание (инверсия) делает истинное высказывание ложным и, наоборот, ложное – истинным.

Импликация (логическое следование)

в естественном языке соответствует обороту  если ..., то ...; обозначение ––> .
Импликация – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие (первое высказывание) истинно, а следствие (второе высказывание) ложно.

Эквиваленция  (РАВНОЗНАЧНОСТЬ):

в естественном языке соответствует оборотам речи тогда и только тогда; в том и только в том случае;
обозначения Û , ~ .
Эквиваленция – это логическая операция,  ставящая  в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или одновременно ложны.
Определим истинность составного высказывания:
(не А & не В) & (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. Заполнить таблицу:

Этимология названия логической операции

Название логической операции

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

Соответствующие операции в теории множеств

Пример высказывания, построенного с использованием логической связки

лат. Inversio – переворачивание Отрицание     «Неверно, что число 10 – четное» ЛОЖЬ
«Неверно, что число 10 отрицательное» ИСТИНА
лат. Conjunctio – связывание Логическое умножение     «Число 10 – четное и отрицательное» ЛОЖЬ
Лат. Disjunctio – разделение Логическое сложение     «Число 10 – четное или отрицательное» ИСТИНА
лат. Implicatio – переплетение Логическое следование     «Если число 10 – четное, то оно является отрицательным» ЛОЖЬ
лат. Aequivalens – равноценное Логическое равенство     «Число 10 – четное тогда и только тогда, когда отрицательное» ЛОЖЬ

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

3. При построении таблиц истинности целесообразно руководствоваться определенной  последовательностью действий:

1) записать выражение и определить порядок выполнения операций
2) определить количество строк в таблице истинности. Оно равно количеству возможных комбинаций значений логических переменных, входящих в логическое выражение (определяется по формуле Q = 2n, где n – количество входных переменных)
3) определить количество столбцов в таблице истинности (= количество логических переменных + количество логических операций)
4) построить таблицу истинности, обозначить столбцы (имена переменных и обозначения логических операций  в порядке их выполнения) и внести в таблицу возможные наборы значений исходных логических переменных.
заполнить таблицу истинности, выполняя базовые логические операции в необходимой последовательности и в соответствии с их таблицами истинности
Теперь мы можем определить значение логической функции для любого набора значений логических переменных.
Например, построим таблицу истинности для логической функции:
Количество входных переменных в заданном выражении равно трем (A, B, C). Значит, количество входных наборов, а значит и строк Q = 23 = 8. Количество столбцов равно 6 (3 переменные + 3 операции).

5. Обобщение и систематизация знаний

Проверочная работа по теме «Дизъюнкция, конъюнкция, отрицание

1. Найдите значения логических выражений:

а) (l v l) v (l v O);
б) ((l v O) v l) v l;
в) (0 v 1) v (1 v 0);
г) (0 & 1) & 1;
е) ((l v O) & (l & l)) & (O v l);
ж) ((l&O) v (l&O)) v l;
з) ((l&l) v O) & (O v l);
и) ((0&0) v0) & (l v l).

2. Даны два простых высказывания:

А = {2 • 2 = 4}, В = {2 •  2 = 5}.

Какие из высказываний истинны:

а) А;     б) В;     в) А&В;     г) AvB ;    д)  ¬A;     е)  A ^ В;     ж) А ^ ¬В?

3.  Даны простые высказывания:

А = {Принтер — устройство ввода информации},
В = {Процессор — устройство обработки информации},
С = {Монитор — устройство хранения информации},
D = {Клавиатура — устройство ввода информации}.
Определите истинность высказывания: (A & B) & (C v D).   

Проверочная работа по теме «Импликация и эквивалентность»

1. Даны истинные высказывания: А = «на улице идет снег» и В = «нужно надеть шапку». Составьте высказывания: а) А => B,      б) B => A, которые будут принимать ложные значения. 

2. Даны истинные высказывания А = «Карлсон хочет варенье» и В = «Карлсон летает на свежем воздухе». Составьте истинные высказывания вида A <=> B. 

3. Даны простые высказывания:

А = {Принтер — устройство ввода информации},
В = {Процессор — устройство обработки информации},
С = {Монитор — устройство хранения информации},
D = {Клавиатура — устройство ввода информации}.

Определите истинность составных высказываний:

а) (AvB) <=> (C&D);   б) А ↔ В.

4. Даны простые высказывания:

А = {5>3}, В = {2=3} и С = {4<2}.

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

a) (A v B) & C => (A & C) v (B & C);         б) (A & B) v C ↔  (A v C) & (A &B ).

6. Подведение итогов

Обобщить пройденный материал

7. Домашнее задание

1. Выучить определения, знать обозначения.
2. Даны высказывания:

А = {На улице светит солнце},
В = {На улице дождь},
С = {На улице пасмурная погода},
В = {На улице идет снег}.

Составьте два сложных высказывания, одно из которых в любой ситуации всегда будет ложным, а другое истинным.

3. Составьте таблицу истинности для формул: