Билет 61. Создателем алгебры логики является живший в ХIХ веке английский математик Джордж Буль, в честь которого алгебра логики также называется булевой алгеброй

Алгебра логики — это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания

Создателем алгебры логики является живший в ХIХ веке английский математик Джордж Буль, в честь которого алгебра логики также называется булевой алгеброй.

Логическое высказывание (выражение) — это любoе повествовательное пpедлoжение, в oтнoшении кoтopoгo мoжно oднoзначнo сказать, истиннo oнo или лoжнo.

Так, например, предложение “ 6 — четное число ” следует считать логическим высказыванием, так как оно истинно.

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

Алгебра логики рассматривает любое высказывание только с точки зрения — является ли оно истинным или ложным. Употребляемые в обычной речи слова и словосочетания "не”, “и”, “или”, “если..., то”, “тогда и только тогда” и некоторые другие позволяют из уже заданных высказываний строить новые логические высказывания. Такие слова и словосочетания называются логическими связками. Bысказывания, образованные из других высказываний с помощью логических связок, называются составными. Высказывания, не являющиеся составными, т.е. без связок, называются элементарными.

Истинность или ложность составных высказываний зависит от истинности или ложности элементарных высказываний. Чтобы формально обращаться к логическим высказываниям, им назначают имена переменных. Пусть через А обозначено элементарное высказывание “ Тимур поедет летом на море ”, а через В — высказывание “ Тимур летом отправится в горы ”. Тогда составное высказывание “ Тимур летом побывает и на море, и в горах ” можно формально записать как А и В. Здесь “ и ” — логическая связка, А, В — логические переменные, которые мoгут принимать только два значения — “ истина ” или “ ложь ”. В компьютере значения “истина” и “ложь” обозначаются просто как “1” и “0” соответственно.Каждая логическая связка рассматривается в булевой алгебре как логическая операция над логическими высказываниями и имеет свое название и обозначение:

1. Операция, выражаемая словом “ не ”, в алгебре логики называется отрицанием и обычно обозначается знаком ù;иличертой над высказыванием. Высказывание ­ ­ истинно, когда A ложно, и ложно, когда A истинно. Например, “ Луна — спутник Земли ” (А); “ Луна — не спутник Земли ” ().

2. Операция, выражаемая связкой “ и ”, называется конъюнкцией или логическим умножением и обозначается словом “ and ”, или точкой " • ", или знаками Ù и & (амперсенд).

Правило выполнения операции: Высказывание А•В истинн о тогда и только тогда, когда оба высказывания А и В истинны, иначе оно ложно. Например, высказывание

“10 делится на 2 и 5 больше 3” истинно, а высказывания

“10 делится на 2 и 5 не больше 3”, ложны.

3. Операция, выражаемая связкой “ или ” называется дизъюнкцией или логическим сложением и обозначается в логических формулах словом “ OR ”, или знаком U, Ú или плюсом "+ ". Правило выполнения операции: Высказывание А U В ложно тогда и только тогда, когда оба высказывания А и В ложны, иначе оно будет истинно. Например, высказывание

“10 не делится нацело на 2 или 5 не больше 3” - ложно,

а все три высказывания: “10 делится на 2 или 5 больше 3”,“10 делится на 2 или 5 не больше 3” или “10 не делится на 2 или 5 больше 3” - будут истинны.

4. Операция, выражаемая связками вида “ если.., то… ”, “ из... следует … ” или “ ... влечет... ”, называется импликацией и обозначается в формулах знаком à. Правило выполнения операции: Высказывание А à В ложн о тогда и только тогда, когда А истинно, а В — ложно. Каким образом импликация связывает два элементарных высказывания? Покажем это на примере высказываний: “ данный четырёхугольник — квадрат ” (А) и “ около данного четырёхугольника можно описать окружность ” (В). Рассмотрим составное высказывание А à В, понимаемое как “ если данный четырёхугольник квадрат, то около него можно описать окружность ”.

Есть три варианта, когда высказывание А àВ будет истинно:

1. А - истинно и В - истинно, то есть данный четырёхугольник квадрат, и около него можно описать окружность;

2. А- ложно и В - истинно, то есть данный четырёхугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырёхугольника);

3. A - ложно и B - ложно, то есть данный четырёхугольник не является квадратом, и около него нельзя описать окружность.

Ложен только один вариант: А- истинно и В - ложно, то есть данный четырёхугольник является квадратом, но около него нельзя описать окружность. В обычной речи связка “ если..., то ” описывает причинно - следственную связь между высказываниями. Но в логических операциях смысл высказываний не учитывается, а рассматривается только их истинность или ложность.

5. Операция, выражаемая связками “ тогда и только тогда ”, " необходимо и достаточно ”, “... равносильно...”, называется эквиваленцией или двойной импликацией и обозначается знаком ~ (тильда) или º ( тождество ).

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

В выражениях без скобок сначала выполняется операция отрицания (“ не ”), затем конъюнкция (“ и ”), потом — дизъюнкция (“ или ”) и в последнюю очередь — сначала импликация, а затем эквиваленция.