Алгебра логики
НАВИГАЦИЯ ПО СТРАНИЦЕ
легко понять и запомнить
Высказывание (суждение) — некоторое предложение, которое может быть истинно (верно) или ложно.
Утверждение — суждение, которое требуется доказать или опровергнуть.
Логическое выражение — запись или устное утверждение, в которое, наряду с постоянными, обязательно входят переменные величины. В зависимости от значений этих переменных логическое выражение может принимать одно из двух возможных значений: ИСТИНА (логическая 1) или ЛОЖЬ (логический 0).
Сложное логическое выражение — логическое выражение, составленное из одного или нескольких простых (или сложных) логических выражений, связанных с помощью логических операций.
Основные логические операции
Логическое отрицание (инверсия, логическое НЕ) —если исходное выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное выражение ложно, то результат отрицания будет истинным. Обозначается ¬
Логическое сложение (дизъюнкция, логическое ИЛИ) — это новое сложное выражение будет истинным тогда и только тогда, когда истинно хотя бы одно из исходных (простых) выражений. Обозначение: ∨ или +.
Логическое умножение (конъюнкция, логическое И) — это новое сложное выражение будет истинным только тогда, когда истинны оба исходных простых выражения. Обозначение: ∧ или &.
Логическое следование (импликация) — связывает два простых логических выражения, из которых первое является условием (А), а второе (В) — следствием из этого условия. Результатом ИМПЛИКАЦИИ является ЛОЖЬ только тогда, когда условие А истинно, а следствие В ложно. Обозначение: →.
Логическая равнозначность (эквивалентность, тождество) — определяет результат сравнения двух простых логических выражений А и В. Результатом ЭКВИВАЛЕНТНОСТИ является новое логическое выражение, которое будет истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны. Обозначение: ≡ или ↔ или ~.
Приоритет логических операций в сложном логическом выражении:
Инверсия.
Конъюнкция.
Дизъюнкция.
Импликация.
Эквивалентность.
Для изменения указанного порядка выполнения операций используются скобки.
Таблицы истинности для сложных выражений
Таблица истинности — это таблица, устанавливающая соответствие между всеми возможными наборами логических переменных, входящих в логическую функцию, и значениями функции.
Таблицы истинности применяются для:
вычисления истинности сложных высказываний;
установления эквивалентности высказываний.
Для построения таблицы истинности надо определить количество строк и столбцов.
Количество строк = 2n + одна строка для заголовка (n — количество простых высказываний).
Количество столбцов = количество переменных + количество логических операций.
При построении таблицы надо учитывать все возможные сочетания логических значений 0 и 1 исходных выражений. Затем — определить порядок действий и составить таблицу с учетом таблиц истинности основных логических операций.
ПРИМЕР: составить таблицу истинности сложного логического выражения .
А, В, С — три простых высказывания, поэтому:
количество строк = 23 +1 = 9 (n=3, т. к. на входе три элемента А, В, С),
количество столбцов:3 переменные + 3 операции = 6.
Алгоритм решения задачи №2 ЕГЭ.
for x in range(2):
for y in range(2):
for z in range(2):
for w in range(2):
if логическое высказывание == True (False):
print(x,y,z,w) Обозначения логических операций, которые могут встретиться в заданиях 2 и 15, приведены ниже.
Логическая операция | Обозначение | Запись в Питоне |
|---|---|---|
Инверсия | A ∧ B | A and B |
Конъюнкция | A ∨ B | A or B |
Дизъюнкция | ¬ A | not (A) |
Импликация | A → B | A <= B |
Тождество | A ≡ B | A == B |
Обращайте внимание на скобки! Не забывайте про приоритеты логических операций, рекомендуется каждую логическую операцию ставить в скобки.
Алгоритм решения задачи № 15 ЕГЭ.
А) Задачи на отрезки.
Чтобы найти длину отрезка, нужно из координат конца вычесть координаты начала.
Чтобы найти количество точек – конец минус начало + 1.
Б) Задачи на ДЕЛ.
Обязательно обращайте внимание на ЦЕЛЫЕ НЕОТРИЦАТЕЛЬНЫЕ ИЛИ ПОЛОЖИТЕЛЬНЫЕ ЗНАЧЕНИЯ элементов!
Пример представлен ниже.
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа А формула
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
for a in range (1, 1500):
f = 0
for x in range (1,1500):
if ((((x % 23 )!= 0) or ((x % 17) != 0)) <= ((x % a) != 0)) == 0:
f = 1
if f == 0:
print (a)Ответ: 391
В) Задачи на побитовую конъюнкцию.
Пример представлен ниже.
Определить наименьшее натуральное число A, такое, что выражение
тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)?
for a in range (1, 500):
f = 0
for x in range (1,1350):
if (((x & 135) !=0) <=(((x & 233) ==0) <= ((x & a) !=0))) == 0:
f = 1
if f == 0:
print (a)Ответ: 6
Общий вариант решения задач:
for A in range(1,500):
flag = 1
for x in range(1,1000):
if (логическое выражение из задачи) == 0: #ОБРАТИТЕ ВНИМАНИЕ НА ОБЩУЮ СКОБКУ
flag = 0
if flag == 1:
print(A)