Основы логики

ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ ЛОГИКИ
Логика – наука о формах и способах мышления. Основными формами мышления являются понятие, суждение, умозаключение.
Понятие – это форма мышления, фиксирующая основные, существенные признаки объекта.
Высказывание – это форма мышления, в которой что-либо утверждается или отрицается о реальных предметах, их свойствах и отношениях между ними.
Высказывание может быть либо истинно, либо ложно.
Умозаключение – это форма мышления, с помощью которой из одного или нескольких суждений (посылок) может быть получено новое суждение (вывод).

Логика — это наука, изучающая законы и формы мышления.
Алгебра логики — это математический аппарат, с помощью которого записывают (кодируют), упрощают, вычисляют и преобразовывают логические высказывания.
Высказывание — это повествовательное предложение, о котором можно сказать, истинно оно или ложно. При этом считается, что высказывание удовлетворяет закону исключенного третьего, т.е. каждое высказывание или истинно, или ложно и не может быть одновременно и истинным, и ложным.
Если высказывание:
истинно - его значение равно 1 (True, T);
ложно - 0 (False, F).
ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ
ЛОГИКИ

ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ
ЛОГИКИ
Высказывание не может быть выражено повелительным или вопросительным предложением, так как оценка их истинности или ложности невозможна.
Для образования сложных высказываний наиболее часто используются базовые логические операции, выражаемые с помощью логических связок И, ИЛИ и частицей НЕ. Значение истинности сложных высказываний зависит от истинности входящих в них простых высказываний и объединяющих их связок.
В математической логике не рассматривается конкретное содержание высказывания, важно только, истинно оно или ложно.

ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ
ЛОГИКИ
Поэтому высказывание можно представить некоторой переменной величиной, значением которой может быть 0 или 1.
Если высказывание:
истинно - его значение равно 1 (True, T),
ложно - 0 (False, F).
Простые высказывания назвали логическими переменными, а сложные высказывания логическими функциями. Значения логической функции также только 0 или 1. Для простоты записи высказывания обозначаются латинскими буквами А, В, С.
Пример простых высказываний:
A = “2+2=4” – истинно,
B = “Земля не вертится” – ложно.

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ
В основе булевой алгебры лежат 16 основных функций. Наиболее часто применяемые из них:
логическое отрицание (инверсия) – «не»; ¬ ; ¯ ;
логическое умножение (конъюнкция) – «и»; &; ^ ; • ;
логическое сложение (дизъюнкция) – «или»; +; ∨;
логическое следование (импликация) – → ;
логическая операция эквивалентности – ~ ; ⇔ ; ↔ ;
функция Вебба (отрицание дизъюнкции) – ИЛИ-НЕ;
функция Шеффера (отрицание конъюнкции) – И-НЕ;
сложение по модулю 2 (М2).

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ
Приведенные функции можно свести в таблицу истинности:

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ
Логическое отрицание (инверсия):
в естественном языке соответствует словам
неверно, что... и частице не;
в языках программирования Not.
Обозначение ¬ A; Ā.
Таблица истинности:
Диаграмма Эйлера-Венна

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ
Логическое сложение (дизъюнкция):
в естественном языке соответствует союзу или;
в языках программирования Or.
Обозначение +; v .
Таблица истинности:
Диаграмма Эйлера-Венна

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ
Логическое умножение (конъюнкция):
в естественном языке соответствует союзу и; в языках программирования And.
Обозначение &; ^ ; ∙ .
Таблица истинности:
Диаграмма Эйлера-Венна

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ
Логическое следование (импликация) - логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющимся ложным тогда и только тогда, когда из истинной предпосылки(первого высказывания) следует ложный вывод (второе высказывание). В естественном языке
соответствует обороту
«если ..., то ...».
Обозначение → .

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ
Логическое следование соответствует высказыванию
не A или B
Сравним таблицы истинности:
Логические выражения, у которых последние столбцы истинности совпадают, называются равносильными.

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ
Логическая операция эквивалентности (равнозначность) - логическое равенство образуется соединением двух простых высказываний в одно с помощью оборота речи
«... тогда и только тогда, когда …».
Обозначение ~ ; ⇔ ; ↔ .
Составное высказывание, образованное с помощью логической операции эквивалентности, истинно
тогда и только тогда, когда оба высказывания
одновременно либо ложны, либо истинны.

ПРИОРИТЕТ ВЫПОЛНЕНИЯ ЛОГИЧЕСКИХ ОПЕРАЦИЙ
Логическое отрицание (инверсия) – «не»; ¬ ; ¯ .
Логическое умножение (конъюнкция) – «и»; &; ^ ; ∙ .
Логическое сложение (дизъюнкция) – «или»; +; ∨ .
Логическое следование (импликация) – → .
Логическая операция эквивалентности – ~ ; ⇔ ; ↔ .
Для изменения указанного порядка могут
использоваться скобки.

ТАБЛИЦЫ ИСТИННОСТИ
Таблица истинности определяет истинность или ложность логической функции при всех возможных комбинациях исходных значений простых высказываний.
Правила построения таблиц истинности.
Подсчитать количество переменных n в логическом выражении.
Определить количество строк в таблице, которое равно m=2n
Подсчитать количество операций в логическом выражении и определить количество столбцов в таблице:
k = количество переменных (n) + количество операций.
Ввести названия столбцов таблицы в соответствии с последовательностью выполнения логических операций с учетом скобок и приоритетов.
Заполнить столбцы логических переменных наборами значений.
Провести заполнение таблицы истинности по столбцам, выполняя базовые логические операции в соответствии с установленной
в п. 4 последовательностью.

ТАБЛИЦЫ ИСТИННОСТИ
Пример. Определить истинность формулы
F=((C ∨ B) →B)^ (A^ B) →B
Формула является тождественно истинной, если все значения строк результирующего столбца будут равны 1.
1 шаг. Определяем количество строк в таблице: m=23=8
2 шаг. Определяем количество столбцов в таблице:
k=3+5=8

ТАБЛИЦА ИСТИННОСТИ
F=((C ∨ B) →B) ^ (A ^ B) →B
0
1
1
1
0
1
1
1
1
0
1
1
1
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1

ЗАКОНЫ ЛОГИКИ

Задание 1.
Для какого из указанных значений X истинно высказывание
¬((X > 2)→(X > 3))?
1) 1 2) 2 3) 3 4) 4

Определим порядок действий: сначала вычисляются результаты отношений в скобках, затем выполняется импликация (поскольку есть «большие» скобки), затем – отрицание (операция «НЕ») для выражения в больших скобках.
¬((X > 2)→(X > 3))
Решение
(Вариант 1. Прямая подстановка)

2) Выполняем операции для всех приведенных возможных ответов (1 обозначает истинное условие, 0 – ложное); определяем результаты сравнения в двух внутренних скобках:
1
1
1
0
0
0
1
0
Таким образом, ответ – 3.
Решение
(Вариант 1. Прямая подстановка)

Возможные ловушки и проблемы
Можно «забыть» отрицание (помните, что правильный ответ – всего один!)
Можно перепутать порядок операций (скобки, «НЕ», «И», «ИЛИ», «импликация»)
Нужно помнить таблицу истинности операции «импликация», которую очень любят составители тестов.
Этот метод проверяет только заданные числа и не дает общего решения, то есть не определяет все множество значений X, при которых выражение истинно.

Решение
(Вариант 2. Упрощение выражения)
¬((X > 2)→(X > 3))
Обозначим простые высказывания буквами:
A = X > 2, B = X > 3
Тогда можно записать все выражение в виде:
¬(A → B) или
Выразим импликацию через «НЕ» и «ИЛИ»:
A → B = ¬A + B = ¬A ∨ B или
Раскрывая по формуле де Моргана, получаем:
¬(¬A ∨ B)= A ∧ ¬B или
Таким образом, данное выражение истинно только тогда, когда A истинно (X > 2), а B – ложно (X ≤ 3),
то есть для всех X, таких что 2 < X ≤ 3
Таким образом, ответ – 3.

Возможные проблемы
Нужно помнить законы логики (например, формулы де Моргана).
При использовании формул де Моргана нужно не забыть заменить «И» на «ИЛИ» и наоборот.
Нужно не забыть, что инверсией (отрицанием) для выражения X > 3 является X ≤ 3, а не X < 3

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

A8 (базовый уровень, время – 1 мин)
Укажите, какое логическое выражение равносильно выражению A ∧ ¬(¬B ∨ C)
¬A ∨ ¬B ∨ ¬C
A ∨ ¬B ∨ ¬C
A ∧ B ∧ ¬C
A ∧ ¬B ∧ C

Решение
(Вариант 1. Использование законов де Моргана)
Перепишем заданное выражение в других обозначениях: A ∧ ¬(¬B ∨ C) =
Применим формулу де Моргана, а затем закон двойного отрицания:
Перепишем ответы в других обозначениях:
¬A ∨ ¬B ∨ ¬C =
A ∨ ¬B ∨ ¬C =
A ∧ B ∧ ¬C =
A ∧ ¬B ∧ C =
Таким образом, правильный ответ – 3 .

Возможные ловушки и проблемы
Серьезные сложности представляет применяемая в заданиях ЕГЭ форма записи логических выражений, поэтому рекомендуется сначала внимательно перевести их в удобный вид; потом сразу становится понятно.
При использовании законов де Моргана часто забывают, что нужно заменить «И» на «ИЛИ» и «ИЛИ» на «И».
Иногда для решения нужно упростить не только исходное выражение, но и заданные ответы, если они содержат импликацию или инверсию сложных выражений.

Решение
(Вариант 2. Через таблицы истинности,
если забыли формулы де Моргана)
Перепишем заданное выражение в других обозначениях: A ∧ ¬(¬B ∨ C) =
Перепишем ответы в других обозначениях:
¬A ∨ ¬B ∨ ¬C =
A ∨ ¬B ∨ ¬C =
A ∧ B ∧ ¬C =
A ∧ ¬B ∧ C =
Для доказательства равносильности двух логических выражений достаточно показать, что они принимают равные значения при всех возможных комбинациях исходных данных.

Решение
(Вариант 2. Продолжение)
Поэтому можно составить таблицы истинности для исходного выражения и всех ответов и сравнить их.
Здесь 3 переменных, каждая из которых принимает два возможных значения (всего 8 вариантов).

Решение.
(Вариант 2. Продолжение)
1
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
Таким образом, правильный ответ – 3 .

Решение
(комментарий к таблице)
Исходное выражение истинно только тогда, когда и , то есть только при (в таблице истинности одна единица, остальные – нули)
7) Выражение истинно, если хотя бы одна из переменных равна нулю, то есть, оно будет ложно только при (в таблице истинности один нуль, остальные – единицы).

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