Учебник MAXIMUM Education

Интернет-энциклопедия по школьным предметам от Maximum Education. Учебник поможет решить домашнее задание, подготовиться к контрольной и вспомнить прошлые темы.

9 класс
Информатика

Логические функции

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

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

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

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

Чтобы определить значение составного логического выражения, надо знать значения входящих в него логических переменных (высказываний). Чтобы рассмотреть все возможные случаи, в булевой алгебре есть специальный аппарат — таблица истинности.

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

Для выражения, содержащего n переменных, количество комбинаций для них будет равно 2n. Подробнее про таблицы истинности написано ниже.

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

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

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

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

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

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

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

A B A И B
0 0 0
0 1 0
1 0 0
1 1 1

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

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

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

A B A ИЛИ B
0 0 0
0 1 1
1 0 1
1 1 1

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

Инверсия (логическое отрицание, логическое «НЕ») получает из истинного высказывания ложное и, наоборот, из ложного — истинное.

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

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

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

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

A НЕ (A)
0 1
1 0

Порядок выполнения логических операций

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

1. Инверсия (логическое отрицание, НЕ)

2. Конъюнкция (логическое умножение, И)

3. Дизъюнкция (логическое сложение, ИЛИ)

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

Рассмотрим пример правильного порядка вычислений.

Определим значение выражения НЕ(А) ИЛИ B ИИЛИ D) при значениях переменных: A = 0, B = 1, C = 1, D = 0.

  1. Первыми выполнятся скобки: С ИЛИ D = 1 ИЛИ 0 = 1

  2. Затем идёт отрицание: НЕ(А) = НЕ(0) = 1

  3. Дальше идёт логическое умножение: B ИИЛИ D) = 1 И 1 = 1

  4. Последним в данном примере будет логическое сложение: НЕ(А) ИЛИ B ИИЛИ D) = 1 ИЛИ 1 = 1

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

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

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

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

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

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

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

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

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

Ниже пример построения таблицы истинности для выражения: НЕ(А) ИЛИ B И С

В выражении содержится 3 переменных, значит есть 8 различных комбинаций их значений. С учётом шапки таблица истинности будет содержать 9 строк. В выражении 3 операции, значит столбцов потребуется 6.

А B C НЕ(А) B И С НЕ(А) ИЛИ B И С
0 0 0 1 0 1
0 0 1 1 0 1
0 1 0 1 0 1
0 1 1 1 1 1
1 0 0 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
1 1 1 0 1 1