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

Математическая логика (она же булева алгебра) является неотъемлемым блоком знаний как в школьном курсе информатики, так и в ЕГЭ. В чистом виде логика в экзамене представлена в двух заданиях: №2 и №15, которые идут по увеличению сложности. Кроме этого, логика в том или ином виде встречается и в других разделах экзамена – от кодирования информации до программирования.

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

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

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

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

Конъюнкция (логическое умножение, логическое «И») обозначает объединение двух или нескольких высказываний в одно таким образом, что результат будет истинным тогда и только тогда, когда истинны все входящие в него высказывания. Пусть есть два высказывания:

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

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

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

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

Дизъюнкция (логическое сложение, логическое «ИЛИ») обозначает объединение двух или нескольких высказываний в одно таким образом, что результат будет истинным тогда, когда истинно хотя бы одно входящее в него высказывание.

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

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

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

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

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

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

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

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

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

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

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

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

1. Инверсия
2. Конъюнкция
3. Дизъюнкция
4. Более сложные логические операции, о которых поговорим чуть позже.

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

Например, у выражения A \/ B /\ (С \/¬D) будет следующий порядок действий:

2. (С \/¬D)

3. B /\ (С \/¬D)

4. A \/ B /\ (С \/¬D)