Алгоритм построения таблиц истинности логических выражений. Тождественные преобразования логических выражений

Страница 1

Урок информатики по теме "Основы логики, таблицы истинности"

Тема: Как построить таблицу истинности?

Продолжительность урока: 40 мин

Тип урока: комбинированный:

• 
  проверка знаний – устная работа;
• 
  новый материал – лекция;
• 
  закрепление – практические упражнения;
• 
  проверка знаний – задания для самостоятельной работы.

Цели урока:

1. 
   Обучающие:
   1. 
      Научить составлять логические выражения из высказываний
   2. 
      Ввести понятие “таблица истинности”
   3. 
      Изучить последовательность действий построения таблиц истинности
   4. 
      Научить находить значение логических выражений посредством построения таблиц истинности
2. 
   Развивающие:
   1. 
      Развивать логическое мышление
   2. 
      Развивать внимание
   3. 
      Развивать память
   4. 
      Развивать речь учащихся
3. 
   Воспитательные:
   1. 
      Воспитывать умение слушать учителя и одноклассников
   2. 
      Воспитывать аккуратность ведения тетради
   3. 
      Воспитывать дисциплинированность

План урока:

1. 
   Организационный момент (2 мин).
2. 
   Повторение материала предыдущего урока +проверка домашнего задания (устный опрос) (5 мин).
3. 
   Объяснение нового материала (10 мин).
4. 
   Физкультминутка (1 мин).
5. 
   Закрепление
   • 
     разбор примера (5 мин);
   • 
     практические упражнения (10 мин);
   • 
     задания для самостоятельной работы (5 мин).
6. 
   

Оборудование и программный материал:

• 
  белая доска;
• 
  раздаточный справочный материал “Таблицы истинности”;
• 
  демонстрация презентации “Таблицы истинности”.

Ход урока

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

• 
  Приветствие.
• 
  Проверка отсутствующих в классе.
• 
  Объявление оценок за прошлый урок.

2. Повторение материала предыдущего урока + проверка домашнего задания

3 учащихся работают по карточкам:

Соедините правильные определения или обозначения:

1. Логика	1.
2. Высказывание	2. Логическое сложение
3. Алгебра логики	3. Наука о формах и способах мышления
4. Логическая переменная	4. Логическое отрицание
5. Дизъюнкция	5. ИСТИНА и ЛОЖЬ
6. Инверсия	6.
7. Конъюнкция	7.
8. Импликация	8. Наука об операциях над высказываниями
9. Эквивалентность	9. Повествовательное предложения, в котором что-либо утверждается или отрицается, которое может быть истинным или ложным

Остальные устно.

1)Примеры записаны на доске:

1. 
   Для логических выражений сформулируйте составные высказывания на обычном языке:

А) (Y>1 и Y 4) (Ответ: число Y принадлежит промежутку (1,3) и (4,8))

Б) (X=Y) и (X=Z). (Ответ: числа X , Y и Z равны между собой)

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

Какие логические связки вы использовали? (Инверсия, дизъюнкция и конъюнкция)

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

Давайте вспомним основные определения и понятия:

3. Объяснение нового материала

Из составного высказывания составьте формулу, заменяя простые высказывания переменными.

Задача: В классе оказалось разбито стекло. Учитель объясняет директору: это сделал Коля или Саша. Но Саша этого не делал, так как в это время сдавал мне зачет. Следовательно, это сделал Коля.

Решение: Формализуем данное сложное высказывание:

К – это сделал Коля; С – это сделал Саша.

Форма высказывания:

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

Итак, тема сегодняшнего урока: «Как построить таблицу истинности?»

Мы уже несколько уроков подряд используем понятие “таблица истинности”? так что же такое таблица истинности ?

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

Еще раз рассмотрим наш пример

и построим таблицу истинности для этого составного высказывания

При построении таблиц истинности есть определенная последовательность действий. Давайте запишем

1. 
   Необходимо определить количество строк в таблице истинности.

• 
  количество строк = 2 n , где n – количество логических переменных

1. 
   Необходимо определить количество столбцов в таблице истинности.

• 
  количество столбцов = количеству логических переменных + количество логических операций.
• 
  Необходимо построить таблицу истинности с указанным количеством строк и столбцов, ввести названия столбцов таблицы в соответствии с последовательностью выполнения логических операций с учетом скобок и приоритетов (¬, &, V);

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

К	С
0	0	1	0	0	1
0	1	0	1	0	1
1	0	1	1	1	1
1	1	0	1	0	1

4. Физкультминутка

1. 
   Закрепление

• 
  разбор примера.
• 
  практические упражнения.
• 
  задания для самостоятельной работы.

Построить таблицы истинности для таких составных высказываний:

А)

А	В
0	0	0	1
0	1	0	0
1	0	0	0
1	1	1	0

Б)

А	В
0	0	1	0	1
0	1	0	1	0
1	0	1	1	1
1	1	0	1	0

В)

А	В	С
0	0	0	1	0	0
0	0	1	1	1	1
0	1	0	0	0	0
0	1	1	0	0	0
1	0	0	1	0	1
1	0	1	1	1	1
1	1	0	0	0	1
1	1	1	0	0	1

Задание для самостоятельной работы «Кто быстрей?»

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

А	В	С

Ответ:

А	В	С
0	0	0	1	0	1	0
0	0	1	0	0	0	1
0	1	0	1	0	1	0
0	1	1	0	0	0	1
1	0	0	1	0	1	0
1	0	1	0	0	0	1
1	1	0	1	1	1	0
1	1	1	0	1	1	0

1. 
   Обобщение урока, домашнее задание (2 мин).

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

Д/З не задается, так как урок спаренный, дети приходят через урок и продолжаем изучать тему «Основы логики и логические основы компьютера».

страница 1

Основные логические операции

Отрицание (инверсия), от латинского inversio -переворачиваю:

Соответствует частице НЕ, словосочетанию НЕВЕРНО, ЧТО;

Обозначение: не A, A, -A;

таблица истинности:

Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна.

Пример: A = {На улице идет снег}.

A={Не верно, что на улице идет снег}

A={На улице не идет снег};

Логическое сложение (дизъюнкция), от латинского disjunctio - различаю:

Соответствует союзу ИЛИ;

Обозначение: +, или, or, V;

Таблица истинности:

Дизъюнкция ложна тогда и только тогда, когда оба высказывания ложны.

Пример: F={На улице светит солнце или дует сильный ветер};

Логическое умножение (конъюкция), от латинского conjunctio -связываю:

Соответствует союзу И

(в естественном языке: и А, и В, как А, так и В,А вместе с В,А, не смотря на В, А, в то время как В);

Обозначение: Ч, , &, и, ^, and;

Таблица истинности:

Конъюкция истинна тогда и только тогда, когда оба высказывания истинны.

Пример: F={На улице светит солнце и дует сильный ветер};

Любое сложное высказывание можно записать с помощью основных логических операций И, ИЛИ, НЕ.С помощью логических схем И, ИЛИ, НЕ можно реализовать логическую функцию, описывающую работу различных устройств компьютера.

2) Таблица истинности - это таблица, описывающая логическую функцию.

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

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

Конъю́нкция- логическая операция, по своему применению максимально приближённая к союзу "и".логи́ческое умноже́ние, иногда просто "И".

Дизъю́нкция-логическая операция, по своему применению максимально приближённая к союзу «или» в смысле «или то, или это, или оба сразу». логи́ческое сложе́ние, иногда просто «ИЛИ».

Импликация - бинарная логическая связка, по своему применению приближенная к союзам «если…то…».Импликация записывается как посылка следствие; применяются также стрелки другой формы и направленные в другую сторону (остриё всегда указывает на следствие).

Эквивале́нция (или эквивале́нтность) - двуместная логическая операция. Обычно обозначается символом ≡ или ↔.

7 . Логические выражения, таблицы истинности логических выражений.

Логическое выражение – запись или устное утверждение, в которое, наряду с постоянными, обязательно входят переменные величины (объекты). В зависимости от значений этих переменных логическое выражение может принимать одно из двух возможных значений: ИСТИНА (логическая 1) или ЛОЖЬ (логический 0)

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

Логические операции и таблицы истинности

Логическое умножение КОНЪЮНКЦИЯ - это новое сложное выражение будет истинным только тогда, когда истинны оба исходных простых выражения. Конъюнкция определяет соединение двух логических выражений с помощью союза И.

Логическое сложение – ДИЗЪЮНКЦИЯ - это новое сложное выражение будет истинным тогда и только тогда, когда истинно хотя бы одно из исходных (простых) выражений. Дизъюнкция определяет соединение двух логических выражений с помощью союза ИЛИ

Логическое отрицание: ИНВЕРСИЯ - если исходное выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное выражение ложно, то результат отрицания будет истинным/ Данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО

Логическое следование: ИМПЛИКАЦИЯ - связывает два простых логических выражения, из которых первое является условием (А), а второе (В)– следствием из этого условия. Результатом ИМПЛИКАЦИИ является ЛОЖЬ только тогда, когда условие А истинно, а следствие В ложно. Обозначается символом "следовательно" и выражается словами ЕСЛИ … , ТО …

Логическая равнозначность: ЭКВИВАЛЕНТНОСТЬ - определяет результат сравнения двух простых логических выражений А и В. Результатом ЭКВИВАЛЕНТНОСТИ является новое логическое выражение, которое будет истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны. Обозначается символом "эквивалентности"

Порядок выполнения логических операций в сложном логическом выражении:

1. инверсия

2. конъюнкция

3. дизъюнкция

4. импликация

5. эквивалентность

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

Построение таблиц истинности для сложных выражений:

Количество строк = 2n + две строки для заголовка (n - количество простых высказываний)

Количество столбцов = количество переменных + количество логических операций

При построении таблицы надо учитывать все возможные сочетания логических значений 0 и 1 исходных выражений. Затем – определить порядок действий и составить таблицу с учетом таблиц истинности основных логических операций.

ПРИМЕР: составить таблицу истинности сложного логического выражения D = неA & (B+C)

А,В, С - три простых высказывания, поэтому:

количество строк = 23 +2 = 10 (n=3, т.к. на входе три элеманта А, В, С)

количество столбцов: 1) А

4) не A это инверсия А (обозначим Е)

5) B + C это операция дизъюнкции (обозначим F)

6) D = неA & (B+C), т.е. D = E & F это операция конъюнкции

А В С E = не А (не 1) F = В+С (2+3) D = E&F (4*5)

Определение 1

Логическая функция – функция, переменные которой принимают одно из двух значений: $1$ или $0$.

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

Определение 2

Таблица истинности – таблица, которая показывает, какие значения примет составное выражение при всех возможных наборах значений простых выражений, входящих в него.

Определение 3

Равносильными называются логические выражения, последние столбцы таблиц истинности которых совпадают. Равносильность обозначается с помощью знака $«=»$.

При составлении таблицы истинности важно учитывать следующий порядок выполнения логических операций:

Рисунок 1.

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

Алгоритм построения таблицы истинности логической функции

Определяют количество строк: кол-во строк = $2^n + 1$ (для строки заголовка) , $n$ – количество простых выражений. Например, для функций двух переменных существует $2^2 = 4$ комбинации наборов значений переменных, для функций трех переменных – $2^3 = 8$ и т.д.

Определяют количество столбцов: кол-во столбцов = кол-во переменных + кол-во логических операций. При определении количества логических операций учитывают также порядок их выполнения.

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

Рисунок 2.

Пример 1

Составить таблицу истинности логического выражения $D=\bar{A} \vee (B \vee C)$.

Решение:

Определим количество строк:

кол-во строк = $2^3 + 1=9$.

Количество переменных – $3$.

1. инверсия ($\bar{A}$);
2. дизъюнкция, т.к. она находится в скобках ($B \vee C$);

3. дизъюнкция ($\overline{A}\vee \left(B\vee C\right)$) – искомое логическое выражение.

   Кол-во столбцов = $3 + 3=6$.

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

Рисунок 3.

Пример 2

По данному логическому выражению построить таблицу истинности:

Решение:

Определим количество строк:

Количество простых выражений – $n=3$, значит

кол-во строк = $2^3 + 1=9$.

Определим количество столбцов:

Количество переменных – $3$.

Количество логических операций и их последовательность:

1. отрицание ($\bar{C}$);
2. дизъюнкция, т.к. она находится в скобках ($A \vee B$);
3. конъюнкция ($(A\vee B)\bigwedge \overline{C}$);
4. отрицание, которое обозначим $F_1$ ($\overline{(A\vee B)\bigwedge \overline{C}}$);
5. дизъюнкция ($A \vee C$);
6. конъюнкция ($(A\vee C)\bigwedge B$);
7. отрицание, которое обозначим $F_2$ ($\overline{(A\vee C)\bigwedge B}$);

8. дизъюнкция – искомая логическая функция ($\overline{(A\vee B)\bigwedge \overline{C}}\vee \overline{(A\vee C)\bigwedge B}$).

1. Определить порядок действий.

2. Определить размерность таблицы истинности.

Количество столбцов определяется количеством логических переменных (их две А, В) и количеством действий (их тоже два).

4. Сформулировать ответ.
В последнем столбце один "0", соответствующий А, равному "1", и В, равному "0". Получается, что данная функция ложна тогда и только тогда, когда логическая переменная А истинна, а логическая переменная В ложна, что соответствует логической функции СЛЕДСТВИЕ.
Значит, данная функция равна логическому следствию переменных А и В: Если А, то В.

Составить таблицу истинности для логической функции:

1. Определить порядок действий.

2. Определить размерность таблицы истинности.

"Шапка" таблицы содержит две строки - номера действий и логические операции действий.
Количество столбцов определяется количеством логических переменных (их две А, В) и количеством действий (их пять).
Количестко строк в таблице равно двойке в степени, равной количеству логических переменных - в случае двух переменных получается 4 строки..
3. Поочередно заполнить столбики таблицы в соответствии с логической функцией данного столбца.


4. Сформулировать ответ.
В последнем столбце "1", соответствуют А равному В, а "0" - А неравному В. Получается, что данная функция истинна, когда А равно В и ложна, когда А не равно В, что соответствует логической функции ТОЖДЕСТВО.
Значит, данная функция равна логическому ТОЖДЕСТВУ переменных А и В: А тождественно В.

Продолжительность урока: 45 мин

Тип урока: комбинированный:

• проверка знаний – устная работа;
• новый материал – лекция;
• закрепление – практические упражнения;
• проверка знаний – задания для самостоятельной работы.

Цели урока:

• дать понятие таблицы истинности;
• закрепление материала предыдущего урока “Алгебра высказываний”;
• использование информационных технологий;
• привитие навыка самостоятельного поиска нового материала;
• развитие любознательности, инициативы;
• воспитание информационной культуры.

План урока:

1. Организационный момент (2 мин).
2. Повторение материала предыдущего урока (устный опрос) (4 мин).
3. Объяснение нового материала (12 мин).
4. Закрепление

• разбор примера (5 мин);
• практические упражнения (10 мин);
• задания для самостоятельной работы (10 мин).

Обобщение урока, домашнее задание (2 мин).

Оборудование и программный материал:

• белая доска;
• мультимедийный проектор;
• компьютеры;
• редактор презентаций MS PowerPoint 2003;
• раздаточный справочный материал “Таблицы истинности”;
• демонстрация презентации “Таблицы истинности”.

Ход урока

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

Мы продолжаем изучение темы “Основы логики”. На предыдущих уроках мы увидели, что логика достаточно крепко связана с нашей повседневной жизнью, а также увидели, что почти любое высказывание можно записать в виде формулы.

II. Повторение материала предыдущего урока

Давайте вспомним основные определения и понятия:

Вопрос	Ответ
1. Какое предложение является высказыванием?	Повествовательное предложение, в котором что-либо утверждается или отрицается
2. На какие виды делятся высказывания по своей структуре?	Простые и сложные
3. Истинность каких высказываний является договорной?	Простых
4. Истинность каких высказываний вычисляется?	Сложных
5. Как обозначаются простые высказывания в алгебре высказываний?	Логическими переменными
6. Как обозначается истинность таких высказываний?	1 и 0
7. Что связывает переменные в формулах алгебры высказываний?	Логические операции
8. Перечислите их.	Инверсия (отрицание) Конъюнкция (умножение) Дизъюнкция (сложение) Импликация (следование) Эквиваленция (равносильность)
9. Определите, соответствует ли формула сложному высказыванию. Назовите простые высказывания. Определите причину несоответствия. (Задание на экране)	Нет, неправильно поставлен знак
10. Определите, соответствует ли формула сложному высказыванию. Назовите простые высказывания. Определите причину несоответствия. (Задание на экране)	Да

III. Объяснение нового материала

Последние два примера относятся к сложным высказываниям. Как же определить истинность сложных высказываний?

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

Итак, тема урока ТАБЛИЦЫ ИСТИННОСТИ.

3.1) Определение. Таблица истинности – это таблица, показывающая истинность сложного высказывания при всех возможных значениях входящих переменных (Рисунок 1).

3.2) Разберем подробнее каждую логическую операцию в соответствии с ее определением:

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

Эта операция относится только к одной переменной, поэтому для нее отведено только две строки, т.к. одна переменная может иметь одно из двух значений: 0 или 1.

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

Легко увидеть, что данная таблица действительно похожа на таблицу умножения.

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

Можно убедиться, что таблица похожа на таблицу сложения кроме последнего действия. В двоичной системе счисления 1 + 1 = 10, в десятичной – 1 + 1 = 2. В логике значения переменной 2 невозможно, рассмотрим 10 с точки зрения логики: 1 – истинно, 0 – ложно, т.о. 10 – истинно и ложно одновременно, чего быть не может, поэтому последнее действие строго опирается на определение.

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

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

Последние две операции были разобраны нами на предыдущем уроке.

3.3) Разберем алгоритм составления таблицы истинности для сложного высказывания:

3.4) Рассмотрим пример составления таблицы истинности для сложного высказывания:

Пример. Построить таблицу истинности для формулы: А U В -> ¬А U С.

Решение (Рисунок 2)

Из примера видно, что таблицей истинности является не все решение, а только последнее действие (столбец, выделенный красным цветом).

IV. Закрепление.

Для закрепления материала вам предлагается решить самостоятельно примеры под буквами а, б, в, дополнительно г–ж (Рисунок 3).

V. Домашнее задание, обобщение материала.

Домашнее задание дано вам также на экране монитора (Рисунок 4)

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