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

Математическая логика (она же булева алгебра) является неотъемлемым блоком знаний как в школьном курсе информатики, так и в ЕГЭ.

Цель логики как науки – определить, истинно или ложно некоторое высказывание, а также прослеживать связь между высказываниями относительно друг друга. Высказывания обозначаются логическими переменными, которые могут принимать лишь два значения:

Истина = 1, Ложь = 0

Логические выражения (которые состоят из более чем одного высказывания) на естественном языке образуются с помощью связок «И», «ИЛИ», «НЕ». В математической логике аналогом этих связок являются базовые логические операции — конъюнкция, дизъюнкция и инверсия. Чтобы определить значение составного логического выражения, надо знать значения входящих в него логических переменных (высказываний). Чтобы рассмотреть все возможные случаи, в булевой алгебре есть специальный аппарат — таблица истинности. Таблица истинности строится следующим образом: в столбцах записываются логические переменные и само выражение, а в строках — всевозможные комбинации переменных и соответствующий для них результат выражения. Для выражения, содержащего n переменных, количество комбинаций для них будет равно 2ⁿ. Подробнее про таблицы истинности написано ниже.

Логическое умножение. Конъюнкция

Пусть есть два высказывания:

• А = «в ЕГЭ по информатике есть программирование»
• В = «в ЕГЭ по информатике есть логика»

Эти высказывания истинны. Значит, их объединение с помощью конъюнкции («В ЕГЭ по информатике есть программирование И логика») — истинно.

Операцию конъюнкции в булевой алгебре принято обозначать знаком « /\ » или, реже, « & » (амперсанд). Операция логического умножения, аргументами которой являются логические переменные А и В, записываются следующей формулой: A /\ B. Таблица истинности для конъюнкции:

Логическое сложение. Дизъюнкция

Операцию дизъюнкции в булевой алгебре принято обозначать знаком « \/ ». Операция логического сложения, аргументами которой являются логические переменные А и В, записывается следующей формулой: A \/ B. Таблица истинности для дизъюнкции:

Логическое отрицание. Инверсия

Например, высказывание «Москва — столица России» истинно, а данное высказывание, образованное с помощью логического отрицания («Москва — не столица России») — ложно. Ложное высказывание можно сделать истинным с помощью инверсии:

• А = «Екатеринбург — столица России» (ложно)
• НЕ А = «Екатеринбург — не столица России» (истинно)

Операцию инверсии в булевой алгебре принято обозначать знаком « ¬ ». Операция логического отрицания, аргументом которой является логическая переменная А, записывается следующей формулой: ¬A. Результатом операции логического отрицания является Истина, когда аргумент Ложь, и значение Ложь, когда аргумент Истина. Таблица истинности для инверсии:

Построение таблиц истинности логических выражений

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

1. Определить количество строк, которое равно количеству возможных комбинаций значений логических переменных, входящих в логическое выражение (если переменных n штук, то количество строк будет равно 2ⁿ). Еще одну строку стоит добавить для указания самих переменных, итого строк в таблице будет 2ⁿ + 1.

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

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

a) разделить столбец значений первой переменной пополам и заполнить верхнюю часть колонки нулями, а нижнюю — единицами;

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

в) продолжать деление столбцов значений последующих переменных на 8, 16, 32 и т.д. частей.

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

Импликация и эквиваленция

В логике, помимо базовых логических операций, существуют еще другие. Для ЕГЭ необходимо и достаточно знать ровно две дополнительные логические операции – импликацию и эквиваленцию. Эти логические операции еще можно назвать составными, ведь они на самом деле состоят из базовых. Любую логическую операцию можно «разложить» на базовые — конъюнкцию, дизъюнкцию и инверсию. Выражение, связывающее логическую операцию с её разложением на базовые, называется равносильным выражением.

Импликация

Импликация по смыслу похожа на использование союзов «если… то…». Обозначается стрелкой от первой логической переменной ко второй: A → B. Для импликации равносильное выражение выглядит так:

A → B = ¬A \/ B

Это значит, что таблица истинности для A → B и для ¬A \/ B будет выглядеть идентично. Ниже приведена таблица истинности и диаграмма Эйлера для импликации:

Эквиваленция

Эквиваленция проверяет, одинаковы ли (эквивалентны ли) значения логических переменных — и выдает Истину, если одинаковы (1 и 1, 0 и 0) и Ложь, если не одинаковы (1 и 0, 0 и 1). Обозначается эквиваленция тремя полосами (как равно, только с еще одной чертой): A ≡ B. Для эквиваленции существует два равносильных выражения:

A ≡ B = (A /\ B) \/ (¬A /\ ¬B) = (¬A \/ B) /\ (A \/ ¬B)

Ниже приведена таблица истинности и диаграмма Эйлера для эквиваленции:

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

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

1. Инверсия

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

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

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

5. Эквиваленция

Скобки, разумеется, могут этот порядок менять.