Логические выражения несколько отличаются от обычных математических. Например, Выражение 1 + 1 = 1 не имеет никакого смысла с точки зрения математики, но абсолютно верно с точки зрения логики. Логика оперирует понятиями Истина и Ложь, или True и False, или 1 и 0. Поэтому логическая сумма двух истинных высказываний также является истинной.

Цель урока: научиться строить таблицы истинности и логические схемы сложных логических выражений и решать задание №2 из ЕГЭ по информатике 2023.

Задачи урока:

  1. повторить определение логических операций; 
  2. повторить таблицы истинности простых логических выражений, 
  3. вспомнить порядок выполнения логических операций,
  4. записать законы алгебры логики,
  5. научиться упрощать сложные логические выражения,
  6. изучить понятия нормальной дизъюнктивной и нормальной конъюнктивной формы.

Приглашаем преподавателей на направления: разработка игр, программирование, подготовка к ЕГЭ

Бесплатно обучаем, освобождаем от рутины и отчетов, гарантируем стабильный доход, сами ищем учеников!

Начать преподавать
kk Skyteach

Содержание:

Детям преподаем основы программирования и создания игр, а подростков учим разработке на Python и написанию сайтов.

Хотели бы стать нашим преподавателем? Подробно знакомим вас со всеми направлениями!

Узнать детали
kk 1 Skyteach

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

В алгебре логики изучаются логические операции, производимые над высказываниями. Такие высказывания могут быть истинными или ложными. Применяя к простым высказываниям логические операции, можно строить составные высказывания.

Повторим основные логические операции (буквами A, B или C будем обозначать элементарные логические высказывания):

Отрицание (инверсия, логическое НЕ) — это логическая операция, которая делает ложное высказывание истинным, а истинное — ложным.

Обозначение: ¬A, или not(A), или НЕ(A), или informatika ege 2 zadaniye 2 Skyteach

Таблица истинности:
Ainformatika ege 2 zadaniye 2 Skyteach
01
1
0

Логическое сложение (дизъюнкция, логическое ИЛИ) — это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно, и ложно тогда и только тогда, когда оба простых логических выражения ложны.

Обозначение: A ∨ B, или A or B, или A ИЛИ B, или A + B

Таблица истинности:
ABA+B
000
011
101
111

Логическое умножение (конъюнкция, логическое И) — это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное сложное выражение ложно.

Обозначение: A ∧ B, или A and B, или A И B, или A * B

Преподаватели компьютерных курсов проходят бесплатное обучение во время отбора. У нас преподают Roblox, Unity, Unreal, Scratch, Construct 3, App Inventor, Minecraft, Thunkable, Web, Python.

Подробно рассказываем, как проходит обучение!

Узнать подробности
kk 2 Skyteach
Таблица истинности:
ABA * B
000
010
100
111

Логическое следование (импликация) — это сложное логическое выражение, которое истинно во всех случаях, кроме того случая, когда из истины следует ложь. То есть данная логическая операция связывает два простых логических выражения, из которых первое (А) является условием, а второе (В) является следствием.

Обозначение: A → B

Таблица истинности:
ABA → B
001
011
100
111

Логическая эквивалентность (равносильность) — это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность.

Обозначение: A ≡ B

Таблица истинности:
ABA ≡ B
001
010
100
111

Логическая операция XOR (сложение по модулю 2 или исключающее ИЛИ) — это логическая операция, по своему применению максимально приближенная к грамматической кон­струк­ции «либо … либо …».

Обозначение: A ⊕ B

Таблица истинности:
ABA ⊕ B
000
011
101
110

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

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

  1. Инверсия
  2. Конъюнкция
  3. Дизъюнкция
  4. Импликация
  5. Эквивалентность

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

informatika ege 2 zadaniye 3 Skyteach

Законы алгебры логики — это некоторые стандартные преобразования логических выражений, при которых сохраняется равносильность.

1. Законы поглощения констант

A + 0 = A

A * 1 = A

2. Законы поглощения переменных

A + 1 = 1

A * 0 = 0

3. Законы идемпотентности

A * A = A

A + A = A

4. Закон двойного отрицания

informatika ege 2 zadaniye 4 Skyteach= А

5. Закон противоречия

A * informatika ege 2 zadaniye 2 Skyteach = 0

6. Закон исключенного третьего

A + informatika ege 2 zadaniye 2 Skyteach = 1

7. Законы коммутативности

A * B = B * A

A + B = B + A

8. Законы ассоциативности

(A * B) * C = A * (B * C)

(A + B) + C = A + (B + C)

9. Законы дистрибутивности

A * (B + C) = (A * B) + (A * C)

A + (B * C) = (A + B) * (A + C) — обратите особое внимание!

10. Законы де Моргана

informatika ege 2 zadaniye 5 Skyteach

Правило для запоминания: «Крыша упала, знак поменяла (+ на *, * на +)».

11. Законы поглощения

A + (A * B) = A

A * (A + B) = A

12. Закон преобразования импликации

A → B = informatika ege 2 zadaniye 2 Skyteach + B — импликация из A в B  равна «не A плюс B»

Учимся упрощать сложные логические выражения

После этого можно тренироваться в упрощении логических выражений.

Логическое выражение будем обозначать буквой F. В качестве упрощения логического выражения удобно заменить логические символы конъюнкции и дизъюнкции на * и +, а затем можно избавиться и от импликации (при использовании программного метода импликацию в логическом выражении заменяют на выражение <=).

informatika ege 2 zadaniye 11 Skyteach
informatika ege 2 zadaniye 10 Skyteach

Практикуемся выполнять задание №2 ЕГЭ

Теперь можно переходить к изучению тонкостей и особенностей решения задания №2 по информатике.

На это задание по рекомендации ФИПИ требуется 3 минуты. Чтобы успешно справиться с ним, необходимо уметь строить таблицы истинности и логические схемы.

Строим таблицы истинности и логические схемы

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

Количество разных логических функций, удовлетворяющих неполной таблице истинности, равно informatika ege 2 zadaniye 8 Skyteach, где k  — число отсутствующих строк.

Например, полная таблица истинности выражения с тремя переменными содержит 23 = 8 строчек; если заданы только 6 из них, то можно найти 28−6 = 22 = 4 разные логические функции, удовлетворяющие этим 6 строчкам (но отличающиеся в двух оставшихся).

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

Полную таблицу истинности легче всего составить в табличном редакторе (Excel) или с использованием языка программирования (Python).

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

Если выражение равно 0, то нужно постараться привести данное в условие выражение к виду A + B + C + … . Логическая сумма A + B + C + … равна 0 (выражение ложно) тогда и только тогда, когда все слагаемые одновременно равны нулю, а в остальных случаях равна 1 (выражение истинно).

Если выражение равно 1, то приводите выражение к виду A · B · C · … . Логическое произведение A · B · C · … равно 1 (выражение истинно) тогда и только тогда, когда все сомножители одновременно равны единице, а в остальных случаях равно 0 (выражение ложно).

И еще два факта, которые пригодятся при анализе: логическое следование (импликация) А → В равно 0 тогда и только тогда, когда A (посылка) истинна, а B (следствие) ложно; эквивалентность А º B  равна 1 тогда и только тогда, когда оба значения одновременно равны 0 или одновременно равны 1.

Используем 3 способа решения задания

Способы решения задания:

  • ручной;
  • с помощью электронных таблиц;    
  • с помощью языка программирования (Python).
Ручной способ решения

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

Например, если в условии представлена часть таблицы истинности, в которой значение выражения равно 1 — то можно постараться привести логическое выражение к нормальной дизъюнктивной форме (ДНФ — произведение нескольких литералов). Тогда выражение будет истинным, только если каждый литерал (сомножитель) будет истинен.

Если же в таблице истинности логическое выражение равно 0 — приводим выражение к нормальной конъюнктивной форме (КНФ — сумма нескольких литералов). В этом случае выражение будет ложным, только если каждый литерал (слагаемое) ложен.

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

Решение с помощью электронных таблиц

При использовании электронных таблиц самым сложным является ввод в ячейку таблицы выражения, данного в условии в нотации, соответствующей программе. Чаще всего в качестве программ электронных таблиц используются электронные таблицы пакетов Libre Office, Open Office или Microsoft Office (Excel). Последняя — наиболее распространенная, поэтому здесь будем говорить про нее.

Шаг 1. Сначала количество столбцов в электронной таблице равно количеству переменных логического выражения. Каждый столбец обозначается по именам переменных логического выражения.

Шаг 2. Затем добавляется количество строк электронной таблицы, равное informatika ege 2 zadaniye 8 Skyteach, где k — количество переменных логического уравнения.

Шаг 3. После этого создается еще один столбец электронной таблицы, в первой строке которого (не заголовка) записывается формула, соответствующая логическому выражению. Растянув эту формулу при помощи маркера автозаполнения на все строки таблицы, получаем полную таблицу истинности выражения.

Таблица функций электронной таблицы Excel и их соответствия логическим операциям:

Логическая операцияСтрока Excel
Инверсия=ЕСЛИ(A2=1;0;1)
Дизъюнкция=ЕСЛИ(ИЛИ(A2=1;B2=1);1;0)
Конъюнкция=ЕСЛИ(И(A2=1;B2=1);1;0)
Импликация=ЕСЛИ(И(A2=1;B2=0);0;1)
Эквивалентность=ЕСЛИ(A2=B2;1;0)
Решение с помощью языка программирования (Python)

При использовании программы на языке Python можно описать функцию, например так:

def f(arg):
x, y, z, w = arg
return (здесь записывается логическое выражение),

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

print (‘x y w z’) # заголовок таблицы (в алфавитном порядке)
k = 0, 1 # k — кортеж констант (0 — False, 1 — True)
for x in k:
for y in k:
for w in k:
for z in k:
if f(x, y, w, z) == 1:
print(x, y, w, z) # если F = 1

Или просто вывести таблицу истинности print(x, y, w, z), не используя условный оператор во внутреннем цикле.

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

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

ОбозначениеНазваниеОператор в Python
конъюнкцияand

В Python логическое значение True воспринимается как 1, а False — как 0, благодаря этому можно использовать обычное умножение *

дизъюнкцияor

В Python логическое значение True воспринимается как 1, а False — как 0, благодаря этому можно использовать обычное сложение +

¬отрицаниеnot()
тождество==
строгая дизъюнкция!=
импликацияnot(a) or b или
not a or b или
a <= b

Желаем вашим ученикам высоких баллов по ЕГЭ!

Добавить комментарий

Ваш адрес email не будет опубликован.

×