Разбор 2 задания ЕГЭ по информатике про таблицы истинности
2-е задание: «Таблицы истинности»
Уровень сложности — базовый,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 3 минуты.
Проверяемые элементы содержания: Умение строить таблицы истинности и логические схемы
Типичные ошибки и рекомендации по их предотвращению:
«Игнорирование прямо указанного в условии задания требования, что заполненная таблица истинности не должна содержать одинаковых строк. Это приводит к внешне правдоподобному, но на самом деле неверному решению»
ФГБНУ «Федеральный институт педагогических измерений»
Таблицы истинности и порядок выполнения логических операций
Для логических операций приняты следующие обозначения:
| операция | пояснение | в программировании |
|---|---|---|
| ¬ A, A | не A (отрицание, инверсия) | not(A) |
| A ∧ B, A ⋅ B | A и B (логическое умножение, конъюнкция) | A and B |
| A ∨ B, A + B | A или B (логическое сложение, дизъюнкция) | A or B |
| A → B | импликация (следование) | A |
| A ↔ B, A ≡ B, A ∼ B | эквиваленция (эквивалентность, равносильность) | A==B (python) A=B(pascal) |
| A ⊕ B | строгая дизъюнкция | A != B (python) A <> B (pascal) |
Отрицание (НЕ):
Таблица истинности операции НЕ
Конъюнкция (И):
Таблица истинности операции И (конъюнкция)
Дизъюнкция (ИЛИ):
Таблица истинности операции ИЛИ (дизъюнкция)
Импликация (если…, то…):
Таблица истинности операции Импликация (если…, то…)
Эквивалентность (тогда и только тогда, …):
Таблица истинности операции Эквивалентность (тогда и только тогда, …)
Сложение по модулю 2 (XOR):
| A | B | A ⊕ B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Порядок выполнения операций:
- если нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», импликация, равносильность
Еще о логических операциях:
- логическое произведение X∙Y∙Z∙… равно 1, т.е. выражение является истинным, только тогда, когда все сомножители равны 1 (а в остальных случаях равно 0)
- логическая сумма X+Y+Z+… равна 0, т.е. выражение является ложным только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1)
О преобразованиях логических операций читайте здесь.
Решение заданий 2 ЕГЭ по информатике
Плейлист видеоразборов задания на YouTube:
Задание 2_11: Решение 2 задания ЕГЭ по информатике:
Логическая функция F задается выражением
(¬x ∨ y ∨ z) ∧ (x ∨ ¬z ∨ ¬w)
Ниже приведен фрагмент таблицы истинности функции F, содержащей все наборы аргументов, при которых функция F ложна.
Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
| Перем.1 | Перем.2 | Перем.3 | Перем.4 | F |
| . | . | . | . | F |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
В ответе запишите буквы в том порядке, в котором идут соответствующие им столбцы.
✍ Решение:
✎ Способ 1. Электронные таблицы Excel + Логические размышления:
-
Отобразим перебор всех значений использующихся в выражении переменных (всю таблицу истинности). Поскольку в выражении используются 4 переменных, то строк таблицы будет 2 4 =16:
Выделите таблицу и отсортируйте строки по столбцу с результатом функции. Для этого в меню Главная =>Настраиваемая сортировка =>:
xwzy
-
✎ Способ 2. Программирование:
Язык python:
print('x y z w') for x in 0, 1: for y in 0, 1: for z in 0, 1: for w in 0, 1: F = (not(x) or y or z) and (x or not(z) or not(w)) if not(F): print(x, y, z, w)
print(‘x y z w’) for x in 0, 1: for y in 0, 1: for z in 0, 1: for w in 0, 1: F = (not(x) or y or z) and (x or not(z) or not(w)) if not(F): print(x, y, z, w)
x y z w 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1
xwzy
Язык pascalAbc.net:
begin writeln('x':7, 'y':7, 'z':7,'w':7); for var x:=false to true do for var y:=false to true do for var z:=false to true do for var w:=false to true do if not((not x or y or z) and (x or not z or not w)) then writeln(x:7, y:7, z:7,w:7); end.
begin writeln(‘x’:7, ‘y’:7, ‘z’:7,’w’:7); for var x:=false to true do for var y:=false to true do for var z:=false to true do for var w:=false to true do if not((not x or y or z) and (x or not z or not w)) then writeln(x:7, y:7, z:7,w:7); end.
x y z w False False True True False True True True True False False False True False False True
Ответ:
xwzy
-
✎ Способ 3. Логические размышления:
-
Внешняя операция выражения — конъюнкция (∧). Во всех указанных строках таблицы истинности функция принимает значение 0 (ложь). Конъюнкция ложна аж в трех случаях, поэтому проверить на ложь очень затруднительно. Тогда как конъюнкция истинна (= 1) только в одном случае: когда все операнды истинны. Т.е. в нашем случае:
(¬x ∨ y ∨ z) ∧ (x ∨ ¬z ∨ ¬w) = 1 когда: 1. (¬x ∨ y ∨ z) = 1 И 2. (x ∨ ¬z ∨ ¬w) = 1
Результат: xwzy
�� Видеорешение (бескомпьютерный вариант):
�� здесь
�� Видеорешение на RuTube здесь
Задание 2_12: Разбор 2 задания ЕГЭ:
Миша заполнял таблицу истинности функции:
(¬z ∧ ¬(x ≡ y)) → ¬(y ∨ w)
но успел заполнить лишь фрагмент из трех различных ее строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z:
| Перем.1 | Перем.2 | Перем.3 | Перем.4 | F |
| . | . | . | . | F |
| 1 | 1 | 0 | ||
| 1 | 0 | 0 | ||
| 1 | 1 | 0 | 0 |
Определите, какому столбцу таблицы соответствует каждая из переменных x, y, z, w.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы.
✎ Способ 1. Логические размышления (бескомпьютерный вариант):
- Решим задание методом построения полной таблицы истинности.
- Посчитаем общее количество строк в таблице истинности и построим ее:
4 переменных -> 24 = 16 строк
(¬z ∧ ¬(x ≡ y)) → ¬(y ∨ w) 1. Избавимся от импликации: ¬(¬z ∧ ¬(x ≡ y)) ∨ ¬(y ∨ w) 2. Внесем знак отрицания в скобки (закон Де Моргана): (z ∨ (x ≡ y)) ∨ (¬y ∧ ¬w) = 0 1 часть = 0 2 часть = 0 * Исходное выражение должно быть = 0. Дизъюнкция = 0, когда оба операнда равны 0.
(z ∨ (x ≡ y)) = 0 когда z = 0 и x ≡ y = 0 ¬y ∧ ¬w = 0 когда: 1. ¬y = 0 ¬w = 0 2. ¬y = 1 ¬w = 0 3. ¬y = 0 ¬w = 1
Результат: ywxz
✎ Способ 2. Программирование:
Язык PascalAbc.net:
begin writeln('x':7, 'y':7, 'z':7,'w':7); for var x:=false to true do for var y:=false to true do for var z:=false to true do for var w:=false to true do if not((not z and (x xor y)) = not(y or w)) then writeln(x:7, y:7, z:7,w:7); end.
begin writeln(‘x’:7, ‘y’:7, ‘z’:7,’w’:7); for var x:=false to true do for var y:=false to true do for var z:=false to true do for var w:=false to true do if not((not z and (x xor y))
x y z w False True False False False True False True True False False True
Сопоставив их с исходной таблицей, получим результат: ywxz
Язык Python:
print ('x y z w') for x in 0,1: for y in 0,1: for z in 0,1: for w in 0,1: F=(not z and not(x==y))(not(y or w)) if not F: print (x,y,z,w)
print (‘x y z w’) for x in 0,1: for y in 0,1: for z in 0,1: for w in 0,1: F=(not z and not(x==y))<=(not(y or w)) if not F: print (x,y,z,w)
x y z w 0 1 0 0 0 1 0 1 1 0 0 1
Результат: ywxz
�� Доступно видео решения этого задания (бескомпьютерный вариант):
�� здесь
�� Видеорешение на RuTube здесь
�� Видео (решение 2 ЕГЭ в Excel):
�� здесь
�� Видеорешение на RuTube здесь
�� Видеорешение на RuTube здесь (Программирование)
Задание 2_10: Решение 2 задания ЕГЭ по информатике:
Логическая функция F задается выражением
¬a ∧ b ∧ (c ∨ ¬d)
Ниже приведен фрагмент таблицы истинности функции F, содержащей все наборы аргументов, при которых функция F истинна.
Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a, b, c, d.
| Перем.1 | Перем.2 | Перем.3 | Перем.4 | F |
| . | . | . | . | F |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
В ответе запишите буквы в том порядке, в котором идут соответствующие им столбцы.
✍ Решение:
Результат: cbad
�� (Бескомьютерный вариант) Предлагаем подробный разбор посмотреть на видео:
�� здесь
�� Видеорешение на RuTube здесь
Задание 2_3: Решение задания 2. Демоверсия ЕГЭ 2018 информатика:
Логическая функция F задаётся выражением ¬x ∨ y ∨ (¬z ∧ w).
На рисунке приведён фрагмент таб. ист-ти функции F, содержащий все наборы аргументов, при которых функция F ложна.
Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z.
| Перем. 1 | Перем. 2 | Перем. 3 | Перем. 4 | F |
| . | . | . | . | F |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 |
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая первому столбцу; затем – буква, соответствующая второму столбцу, и т.д.) Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
✍ Решение:
-
✎ Логические размышления (бескомпьютерный вариант):
¬x ∨ y ∨ (¬z ∧ w)
Результат: xzwy
✎ Способ 2. Программирование:
Язык pascalABC.NET:
begin writeln('x ','y ','z ','w '); for var x:=false to true do for var y:=false to true do for var z:=false to true do for var w:=false to true do if not(not x or y or(not z and w)) then writeln(x:7,y:7,z:7,w:7); end.
begin writeln(‘x ‘,’y ‘,’z ‘,’w ‘); for var x:=false to true do for var y:=false to true do for var z:=false to true do for var w:=false to true do if not(not x or y or(not z and w)) then writeln(x:7,y:7,z:7,w:7); end.
�� (бескомпьютерный вариант) Подробное решение данного 2 задания из демоверсии ЕГЭ 2018 года смотрите на видео:
�� здесь
�� Видеорешение на RuTube здесь
Задание 2_13: Разбор досрочного егэ по информатике 2019
Логическая функция F задаётся выражением
(x ∧ ¬y) ∨ (y ≡ z) ∨ ¬w
Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы.
| Перем.1 | Перем.2 | Перем.3 | Перем.4 | F |
| . | . | . | . | F |
| 0 | 0 | 0 | ||
| 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 |
Результат: xwzy
�� Видеорешение (бескомпьютерный вариант):
�� здесь
�� Видеорешение на RuTube здесь
Задания для тренировки
Задание 2_2: Задание 2 ЕГЭ по информатике:
Каждое из логических выражений F и G содержит 5 переменных. В табл. истинности для F и G есть ровно 5 одинаковых строк, причем ровно в 4 из них в столбце значений стоит 1.
Сколько строк таблицы истинности для F ∨ G содержит 1 в столбце значений?
✍ Решение:
- Поскольку в каждом из выражений присутствует 5 переменных, то эти 5 переменных порождают таблицу истинности из 32 строк: т.к. каждая из переменных может принимать оно из двух значений (0 или 1), то различных вариантов с пятью переменными будет 2 5 =32, т.е. 32 строки.
- Из этих 32 строк и для F и для G мы знаем наверняка только о 5 строках: 4 из них истинны (=1), а одна ложна (=0).
- Вопрос стоит о количестве строк = 1 для таб. истинности F ∨ G. Данная операция — дизъюнкция, которая ложна только в одном случае — если F = 0 и одновременно G = 0
- В исходных таблицах для F и G мы знаем о существовании только одного 0, т.е. в остальных строках может быть 1. Т.о., и для F и для G в 31 строке могут быть единицы (32-1=31), а лишь в одной — ноль.
- Тогда для F ∨ G только в одном случае будет 0, когда и F = 0 и G = 0:
№ F G F ∨ G 1 0 0 0 2 0 1 1 … … … 1 32 … … 1 - Соответственно, истинными будут все остальные строки:
32 - 1 = 31
Результат: 31
Подробное объяснение данного задания смотрите на видео:
Задание 2_6: Решение 2 задания ЕГЭ по информатике:
Каждое логическое выражение A и B зависит от одного и того же набора из 7 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 4 единицы.
Каково максимально возможное число единиц в столбце значений таблицы истинности выражения A ∨ B?
✍ Решение:
- Полная таблица истинности для каждого из выражений A и B состоит из 2 7 = 128 строк.
- В четырех из них результат равен единице, значит в остальных — 0.
- A ∨ B истинно в том случае, когда либо A = 1 либо B = 1, или и A и B = 1.
- Поскольку А = 1 только в 4 случаях, то чтобы получить максимальное количество единиц в результирующей таблице истинности (для A ∨ B), расположим все единицы т.и. для выражения A так, чтобы они были в строках, где B = 0, и наоборот, все строки, где B = 1, поставим в строки, где A = 0:
A B 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 0 … … - Итого получаем 8 строк.
- Если бы в задании требовалось найти минимальное количество единиц, то мы бы совместили строки со значением = 1, и получили бы значение 4.
Результат: 8
Задание 2_7: Решение 2 задания ЕГЭ по информатике:
Каждое логическое выражение A и B зависит от одного и того же набора из 8 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 6 единиц.
Каково максимально возможное число нулей в столбце значений таблицы истинности выражения A ∧ B?
✍ Решение:
- Полная таблица истинности для каждого из выражений A и B состоит из 2 8 = 256 строк.
- В шести из них результат равен единице, значит в остальных — 0.
- A ∧ B ложно в том случае, когда:
A ∧ B = 0 если: 1. A = 0, B = 1 2. B = 0, A = 1 3. A = 0 и B = 0
Результат: 256
Задание 2_4: 2 задание:
Дан фрагмент таблицы истинности выражения F.
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | F |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
Каким из приведённых ниже выражений может быть F?
1) ¬x1 ∧ x2 ∧ ¬x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7
2) x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7
3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7
4) x1 ∨ ¬x2 ∨ x3 ∨ x4 ∨ ¬x5 ∨ ¬x6 ∨ x7
✍ Решение:
- В первом внешняя операция (выполняется последней) — конъюнкция. Начнем рассмотрение с нее. Соответственно, проверяем по второй строке таб. ист-ти, там где F = 1, так как в таком случае все аргументы должны быть истинными (см. таб. истинности для конъюнкции).
- Если мы подставим в нее все аргументы выражения, то функция действительно возвращает истину. Т.е. пункт первый подходит:
Результат: 1
Решение 2 задания ГВЭ по информатике смотрите на видео:
Задание 2_8: Решение 2 задания ЕГЭ по информатике:
Дано логическое выражение, зависящее от 5 логических переменных:
(¬x1 ∨ ¬x2 ∨ ¬x3 ∨ x4 ∨ x5) ∧ (x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5)
Сколько существует различных наборов значений переменных, при которых выражение истинно?
✍ Решение:
- Поскольку выражение включает 5 переменных, то таб. ист-ти состоит из 2 5 = 32 строк.
- Внешней операцией (последней) является конъюнкция (логическое умножение), а внутри скобок — дизъюнкция (логическое сложение).
- Обозначим первую скобку за А, а вторую скобку за B. Получим A ∧ B.
- Найдем сколько нулей существует для таб. истинности:
A B F 1. 0 0 0 2. 0 1 0 3. 1 0 0
Теперь рассмотрим каждый случай отдельно:
¬x1 ∨ ¬x2 ∨ ¬x3 ∨ x4 ∨ x5 = 0
и
x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 = 0.
32 - 2 = 30, что соответствует номеру 2
Результат: 2
Подробное решение задания смотрите в видеоуроке:
Задание 2_5: Решение 2 задания ЕГЭ по информатике:
Дан фрагмент таблицы истинности для выражения F:
| x1 | x2 | x3 | x4 | x5 | x6 | F |
| 0 | 0 | 1 | 1 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 0 |
Укажите максимально возможное число различных строк полной таблицы истинности этого выражения, в которых значение x3 не совпадает с F.
✍ Решение:
- Полная таблица истинности будет иметь 2 6 = 64 строк (т.к. 6 переменных).
- 4 из них нам известны: в них x3 два раза не совпадает с F.
- Неизвестных строк:
64 - 4 = 60
60 + 2 = 62
Результат: 62
Задание 2_9: Решение 2 задания ЕГЭ по информатике:
Дан фрагмент таблицы истинности для выражения F:
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | F |
| 0 | 0 | 0 | |||||
| 0 | 0 | 1 | |||||
| 1 | 1 | 1 |
Каким выражением может быть F?
1) x1 ∧ (x2 → x3) ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7
2) x1 ∨ (¬x2 → x3) ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ ¬x7
3) ¬x1 ∧ (x2 → ¬x3) ∧ x4 ∧ ¬x5 ∧ x6 ∧ x7
4) ¬x1 ∨ (x2 → ¬x3) ∨ x4 ∨ x5 ∨ x6 ∧ x7
✍ Решение:
- Рассмотрим отдельно каждый пункт и найдем последнюю операцию, которая должна быть выполнена (внешнюю).
(((x1 ∧ (x2 → x3) ∧ ¬x4) ∧ x5) ∧ x6) ∧ ¬x7
2 пункт:
(((x1 ∨ (¬x2 → x3) ∨ ¬x4) ∨ ¬x5) ∨ x6) ∨ ¬x7
3 пункт:
(((¬x1 ∧ (x2 → ¬x3) ∧ x4) ∧ ¬x5) ∧ x6) ∧ x7
Результат: 4
В видеоуроке рассмотрено подробное решение 2 задания:
Задание 2_1: Задание 2 ЕГЭ по информатике:
Логическая функция F задается выражением
(y → x) ∧ (y → z) ∧ z.
Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.
| № | Перем. 1 | Перем. 2 | Перем. 3 | F |
|---|---|---|---|---|
| . | . | . | F | |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 1 | 0 |
| 3 | 0 | 1 | 0 | 1 |
| 4 | 0 | 1 | 1 | 1 |
| 5 | 1 | 0 | 0 | 0 |
| 6 | 1 | 0 | 1 | 0 |
| 7 | 1 | 1 | 0 | 0 |
| 8 | 1 | 1 | 1 | 1 |
В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы.
✍ Решение:
- Сначала необходимо рассмотреть логическую операцию, которую мы будем выполнять в последнюю очередь — это логическое И (конъюнкция) или ∧. То есть внешнюю операцию:
(y → x) ∧ (y → z) ∧ z
(y → x) ∧ (y → z) ∧ z = 1 если: 1. (y → x) = 1 2. (y → z) = 1 3. z = 1
Результат: yzx
Детальный разбор данного задания 2 ЕГЭ по информатике предлагаем посмотреть в видео:
Таблицы истинности
Решение задач становится проще, если подойти к условию формально, выделив важные компоненты и связи. А если перевести это на язык логических операций, решать их станет также просто, как элементарные математические примеры. Это значительно ускорит процесс и избавит от лишней информации. Еще знание логических функций позволяет составлять простые электрические схемы.
План урока:
Способы решения задач по логике
Многие задачи можно решить, используя инструменты алгебры логики. Чтобы получить результат, можно пойти 3 путями:
- рассуждая над условием;
- решая логические операции;
- используя таблицы истинности.
Логический подход подразумевает перевод условия из естественного языка на язык символов, схем и формул. Для такой формализации высказываний нужно выполнить ряд шагов.
Этапы решения логических задач:
- Разобраться с условием на естественном языке, выделив простые высказывания, и дать им символьные обозначения (латиница).
- Записать условие в виде формулы. Решить ее поэтапно, упрощая, учитывая приоритеты (( ), ¬, &, V).
- Просчитать формулы строчно или при помощи таблиц истинности, учитывая законы алгебры логики.
- Проверить, соответствует ли полученный результат условию задачи.
Табличный способ – этапы, особенности
Таблица истинности – табличное выражение результата логических операций для каждого отдельного набора значений переменных.
Такие таблицы позволяют абстрагироваться от маловажной информации, сосредоточиться только на связях между исходными данными, над происходящими процессами. Таким образом, человек может абстрагироваться от непонятной для него информации, решать неспецифические задачи.
Метод таблиц
Чтобы использовать таблицы истинности, необходимо формализовать условие, то есть отойти от деталей задачи, обозначая первоначальную информацию при помощи букв и цифр 0 и 1.
Существует общий алгоритм построения таблиц:
- Определить число логических значений/переменных (n) в примере.
- Установить вид, число и тип операций. Важно заранее определить очередность действий, выразить это при помощи скобок.
- Полученные данные позволяют рассчитать сколько нужно столбцов – это сумма числа переменных и операций.
- Нарисовать таблицу, заполнить шапку, записав обозначение переменных и выбранные действия.
- Определить, сколько существует наборов логических переменных (т.е. число строчек) по формуле m = 2 n + 1 (шапка).
- Заполнить столбцы, вписав наборы значений логических переменных (0 или 1).
- Записать результаты логических операций, указанных в шапке для каждой совокупности значений.
- Сделать выводы на основании полученных результатов.
Если необходимо перебрать все значения простых выражений, то для задач:
- с 2-мя переменными может быть только 4 набора логических переменных;
Если словесно описывать все эти комбинаций, на каждый из примеров понадобится десятки строк текста.
Обязательно учитывают приоритет операций:
- Указанные в скобках.
- Отрицание.
- Логическая конъюнкция чисел.
- Дизъюнкция.
- Строгая дизъюнкция.
- Импликация.
- Эквивалентность.
Обозначение логических операций:
Сравнение методов решения
Метод рассуждений
Он заключается в пошаговом анализе условий с промежуточными выводами на каждом этапе. Выполняется анализ таблицы истинности каждого логического выражения.
Пример №1.
Андрей, Владимир, Георгий и Дмитрий живут на одной улице, они соседи. Они работают по таким специальностям: гитарист, плотник, егерь и стоматолог.
- дом плотника правее егеря;
- стоматолог проживает левее егеря;
- дом гитариста с самого краю;
- стоматолог живет рядом с гитаристом;
- Владимир не гитарист, и его дом не соседствует с гитаристом;
- дома Дмитрия и егеря соседние;
- здание, в котором прописан Андрей, правее стоматолога;
- между домами Андрея и Дмитрия один дом.
Чтобы рассуждать было проще, добавим изображение зданий, присвоим им номера:
Но стоматолог живет левее егеря, а правее егеря – плотник. Получается, что дом гитариста не может быть последним, а дом стоматолога не может быть предпоследними. То есть, егерь живет в предпоследнем доме:
Между домами Андрея и Дмитрия стоит один дом, значит, дом Андрея не может быть предпоследним, получается номер – 4, что автоматом исключает проживание там Дмитрия и Владимира.
Условие задачи заняло 2 предложения, а рассуждений получилось на 2 страницы.
Такой подход лучше не использовать, если условие сложное или много данных.
Табличный метод
Более удачным подходом к решению задач с большим количеством данных (несколько множеств), считается табличный, или графический (диаграммы).
Чтобы построить таблицу истинности логических выражений, следует:
- Разбить задачу на простейшие утверждения, которые обозначить символами (большие буквы латинского алфавита).
- Записать условие задачи, как составное выражение из символов логических операций.
- Нарисовать таблицу истинности для полученных данных.
- Выбрать такой вариант, при котором полученные значения подходят под условие.
- Проверить соответствие выбранного варианта и условия задачи.
Чтобы преобразовывать условие задачи в логические выражения и операции, удобно пользоваться такой сводной таблицей истинности логических операций:
Рассмотрим тот же пример.
Определяем, что только гитарист может жить в первом доме, далее смотрим на заметки и условия и получаем таких жителей:
Метод компактнее, для некоторых задач нагляднее.
Построение таблиц истинности для различных типов задач
Несмотря на многообразие задач, многие условия повторяются, если оставить сухие формулы, не вникая в имена, места, профессии. Разобравшись с примером один раз, можно решать аналогичные задачи без труда. Рассмотрим несколько любопытных заданий, решив при помощи логически.
Пример 2.
Известно, что если первый студент летал в Англию на стажировку, то и второй тоже летал, но неправда, что если летал третий, то и второй.
Разобьём условие на 3 простые высказывания, присвоим им буквенные обозначения:
А — «Первый студент летал в Англию»;
В — «Второй студент летал в Англию»;
С — «Третий студент летал в Англию».
Запишем выясненные данные при помощи логических операций:
Пример 3.
Есть три 8-ых класса (А, В, С), которые соревнуются между собой за средний бал. Учителя в начале года сделали такие предположения:
- Если А получит максимальный бал, то максимальный бал получат Ви С.
- А и С получат или не получат максимальный бал одновременно.
- Необходимым условием получения высшего бала С класса является получение высшего бала В классом.
По завершении года оказалось, что 2 предсказания оказались верными, а одно – ошибочным.
Выясним, какие же классы добились высшего бала.
Разбиваем условие задачи на элементарные высказывания:
А – «А добьется высшего бала»;
В – «В добьется высшего бала»;
С – «С добьется высшего бала».
Запишем логические операции, описанные в примере:
Мы заполнили таблицу истинности для всех возможных значений исходных данных. В примере говорилось, что только 2 утверждения в конце года казались истинными, а 1- ложным. Такому условию отвечает 3-я строка в таблице.
Пример 4.
Во время знакомства девушка, любительница загадок, сказала, что ее имя узнать легко:
- последняя – гласная (Х1);
- или первая буква согласная (Х2)
- вторая – согласная (Х3).
Предложенные имена: Арина, Артур, Кэтрин, София.
Решим задачу, используя таблицу.
Сначала решим пошагово, выполняя операции по приоритету:
Указанному условию соответствует первое имя.
Пример 5.
Попробуем решать задачи, в которые нет четких высказываний, истинных или ложных. В них половина информации, правда, половина – ложь, при этом неизвестно, какая именно. Под такой тип задач можно подставить любое условие, но научившись решать его, можно разобраться со всеми аналогичными.
Известно, что в олимпиаде по химии участвовали 4 ученицы 8 класса: Марина, Света, Саша и Галя. Они заняли первые 4 места. Какое место заняла каждая из девочек, если есть их высказывания о победителях, но в них лишь половина информации правдива – первая или вторая половина предложения.
Маша Марина: «Саша заняла второе место, а Света – первое».
Полина Света: «Нет, это не так, Саша – победительница, а Галя, – на втором месте».
Ольга Саша: «Зачем вы всех путаете? Третье место за Мариной, а Света – на четвертом месте».
Составляем таблица для перебора вариантов. Правду обозначаем «1», ложь – «0».
Берем любое (Марины) утверждение и принимаем его первую часть за правду. Значит, Саша – 2 место, тогда Света не 1-ое (вторая половина фразы – ложь), остальных девочек на 2 место ставим «0».
Берем утверждение второй девочки. Так как Саша не может быть победительницей, то в этой фразе первая часть – ложь, а вторая должна быть истинной. Но в нем и вторая часть – неверна (второе место за Сашей, мы так приняли в начале).Уже на второй фразе получается противоречие всему.
Итог: Победительницей олимпиады стала Светлана, на втором месте – Галина, на третьем – Марина, на последнем из четырех – Александра.
Построение электронных схем, реализующих логические операции
Если рассмотреть электросхемы с точки зрения логики, особенно компьютерные, то их также можно описать при помощи «1» и «0» – электричество идет или не идет по проводам.
Попробуем нарисовать логические элементы схемы питания лампочки для нескольких простых операций.
Электросхема с конъюнктором
Рассмотрим все варианты:
- Все контакты включены, тогда источник света горит.
- Первый контакт в положении «выключено» – свет не горит.
- Второй контакт выключен – лампа не светит.
- Все контакты отключены – свет не горит.
Заключение – эта электрическая цепь реализует операцию «И».
Дизъюнктор, схема электропитания
Рассмотрим этот вид электрической цепочки:
- Все контакты включены – лампа горит.
- Первый контакт включен, второй выключен – свет горит.
- Обратная ситуация – выключен первый, включен второй – лампа светится.
- Все контакты выключены – света нет.
Заключение – такой вид электросхем соответствует логической операции «ИЛИ».
Инвертор в электросхемах
В этой схеме переключатель не ручной, а автоматический. Здесь процесс обратный – когда ток не идет, контакты замыкаются, горит свет. Если же в сеть подается электричество, пластинка размыкается вследствие электромагнитной индукции, и сеть разъединяется – света нет.
Заключение: схема соответствует логической операции «НЕ».
Умение читать и решать логические операции, строить соответствующие электросхемы, позволяет создавать иерархически более сложные конструкции, которые используются для реализации процессов в современных ПК.
Обозначение логических элементов
Удобно создавать электросхемы в ПО SmartNotebook, которое используется с интерактивной доской.
Основы логики. Логические операции и таблицы истинности
На данной странице будут рассмотренны 5 логических операций: конъюнкция, дизъюнкция, инверсия, импликация и эквивалентность, которых Вам будет достаточно для решения сложных логических выражений. Также мы рассмотрим порядок выполнения данных логических операций в сложных логических выражениях и представим таблицы истинности для каждой логической операции. Советуем Вам воспользоваться нашими программами для решения задач по математике, геометрии и теории вероятности. Помоми большого количества программ для решения задач на сайте работает форум, на котором Вы всегда можете задать вопрос и на котором Вам всегда помогуть с решением задач. Пользуйтесь нашими сервисами на здоровье!
Глоссарий, определения логики
Высказывание — это повествовательное предложение, про которое можно определенно сказать истинно оно или ложно (истина (логическая 1), ложь (логический 0)).
Логические операции — мыслительные действия, результатом которых является изменение содержания или объема понятий, а также образование новых понятий.
Логическое выражение — устное утверждение или запись, в которое, наряду с постоянными величинами, обязательно входят переменные величины (объекты). В зависимости от значений этих переменных величин (объектов) логическое выражение может принимать одно из двух возможных значений: истина (логическая 1) или ложь (логический 0).
Сложное логическое выражение — логическое выражение, состоящее из одного или нескольких простых логических выражений (или сложных логических выражений), соединенных с помощью логических операций.
Логические операции и таблицы истинности
1) Логическое умножение или конъюнкция:
Конъюнкция — это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное сложеное выражение ложно.
Обозначение: F = A & B.
Таблица истинности для конъюнкции
| A | B | F |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
2) Логическое сложение или дизъюнкция:
Дизъюнкция — это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выраженныя ложны.
Обозначение: F = A + B.
Таблица истинности для дизъюнкции
| A | B | F |
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
3) Логическое отрицание или инверсия:
Инверсия — это сложное логическое выражение, если исходное логическое выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное логическое выражение ложно, то результат отрицания будет истинным. Другими простыми слова, данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО.
Таблица истинности для инверсии
| A | неА |
| 1 | 0 |
| 0 | 1 |
4) Логическое следование или импликация:
Импликация — это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. Тоесть данная логическая операция связывает два простых логических выражения, из которых первое является условием (А), а второе (В) является следствием.
Таблица истинности для импликации
| A | B | F |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
5) Логическая равнозначность или эквивалентность:
Эквивалентность — это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность.
Таблица истинности для эквивалентности
| A | B | F |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
Порядок выполнения логических операций в сложном логическом выражении
1. Инверсия;
2. Конъюнкция;
3. Дизъюнкция;
4. Импликация;
5. Эквивалентность.
Для изменения указанного порядка выполнения логических операций используются скобки.
1. Как решать задание ЕГЭ
7. Задание проверяет умение работать с логическими переменными, выполнять логические операции, строить таблицы истинности.
Пример задания
Николай заполнял таблицу истинности логической функции \(F\)
¬ ( y → ( x ≡ w ) ) ∧ ( z → x ) ,
но успел заполнить только фрагмент из трёх различных её строк, не указав, какому столбцу таблицы принадлежит каждая из переменных \(w\), \(x\), \(y\), \(z\).
Определи, какому столбцу таблицы принадлежит каждая из переменных \(w\), \(x\), \(y\), \(z\).
В ответе напиши буквы \(w\), \(x\), \(y\), \(z\) в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пиши подряд, никаких разделителей между буквами ставить не нужно.
Как решать задание?
Данное задание можно решать несколькими способами: путём логических рассуждений; использовать электронные таблицы \(+\) логические рассуждения; с помощью программирования.
Мы рассмотрим вариант решения с помощью языка программирования Python.
Вспомнить основные логические операции можно тут.
Правила построения таблиц истинности можно вспомнить тут.
Законы алгебры логики можно вспомнить тут.
Вспомним управляющие конструкции в Python:
цикл с параметром
тело цикла
for \(y\) in \(0\), \(1\):
тело цикла
if условие then:
действия, если условие истинно
else:
действия, если условие ложно
if \(C>D\):
print (‘ истина ‘)
else:
print (‘ ложь ‘)
Запись логических операций на Python
Название операции
Запись на Python
конъюнкция
дизъюнкция
импликация
Напишем программу
Для каждой переменной сформируем вложенный цикл, где будем перебирать все возможные значения (\(0\) и \(1\)) для каждой переменной;
in range (\(2\)): перебор значений \(0\) и \(1\), можно записать по другому: in range (\(0\),\(2\))
Запуск программы
 |
Полученный результат необходимо сравнить с таблицей из условия |
Сопоставим полученную таблицу истинности с таблицей из условия. Нам необходимо сравнивать условие с результатами, как по строкам, так и по столбцам, отыскивая некоторые закономерности и невозможности. Заметим, что столбец \(y\) содержит в себе три единицы, что может быть только в третьем столбце таблицы из условия. Четвёртый столбик таблицы из условия также можем дополнить единицей, и к этому столбику подходят как \(z\), так и \(w\).
Теперь проанализируем строки. В первой строке получилось три единицы, что соответствует четвёртой строке результата программирования, дополняем нулём первую строку. В третьей строке у нас два нуля, поэтому добавляем единицу. Проверяем, чтобы сошлось по строке. Заполним второй столбец, допишем единицу. Этот столбец как раз и будет являться \(x\). Остаётся проанализировать столбцы \(1\) и \(4\).
Рассмотрим первую строку: \(x = 0\), \(y = 1\), \(z = 0\), следовательно, \(z\) — это четвёртый столбик, а \(w\) — первый.