Логические операции. Кванторы








Логические операции

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

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

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

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

Рассмотрим два высказывания: p = “Завтра будет мороз” и q = “Завтра будет идти снег”. Очевидно, новое высказывание p & q = “Завтра будет мороз, и завтра будет идти снег” истинно только в том случае, когда одновременно истинны высказывания p и q, а именно, что завтра будет и мороз и снег. Высказывание p & q будет ложно во всех остальных случаях: будет идти снег, но будет оттепель (т.е. не будет мороза); мороз будет, а снег не будет идти; не будет мороза, и снег не будет идти.

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

Рассмотрим два высказывания: p = “Колумб был в Индии” и q = “Колумб был в Египте”. Очевидно, что новое высказывание p q = “Колумб был в Индии или был в Египте” истинно как в случае, если Колумб был в Индии, но не был в Египте, так и в случае, если он не был в Индии, но был в Египте, а также в случае, если он был и в Индии, и в Египте. Но это высказывание будет ложно, если Колумб не был ни в Индии, ни в Египте.

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

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

Рассмотрим два высказывания: p = “Кошка охотится за мышами” и q = “Кошка спит на диване”. Очевидно, что новое высказывание p q истинно только в двух случаях — когда кошка охотится за мышами либо когда кошка мирно спит. Это высказывание будет ложно, если кошка не делает ни того, ни другого, т.е. когда оба события не происходят. Но это высказывание будет ложным и тогда, когда предполагается, что оба высказывания произойдут одновременно. В силу того, что этого произойти не может, высказывание и является ложным.

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

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

Логическая операция импликация задается следующей таблицей истинности:

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

Допустим, 1 = 2, тогда и 2 = 1. Складывая эти равенства, мы получим 3 = 3, т.е. из ложной посылки путем тождественных преобразований мы получили истинное высказывание.

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

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

Рассмотрим возможные значения сложного высказывания, являющегося эквивалентностью: “Учитель поставит ученику 5 в четверти тогда и только тогда, когда ученик получит 5 на зачете”.

1) Ученик получил 5 на зачете и 5 в четверти, т.е. учитель выполнил свое обещание, следовательно, высказывание является истинным.

2) Ученик не получил на зачете 5, и учитель не поставил ему 5 в четверти, т.е. учитель свое обещание сдержал, высказывание является истинным.

3) Ученик не получил на зачете 5, но учитель поставил ему 5 в четверти, т.е. учитель свое обещание не сдержал, высказывание является ложным.

4) Ученик получил на зачете 5, но учитель не поставил ему 5 в четверти, т.е. учитель свое обещание не сдержал, высказывание является ложным.

Отметим, что в математических теоремах эквивалентность выражается связкой “необходимо и достаточно”.

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

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

В русском языке для построения отрицания используется связка “неверно, что …”. Хотя связка “неверно, что …” и не связывает двух каких-либо высказываний в одно, она трактуется логиками как логическая операция, поскольку, поставленная перед произвольным высказыванием, образует из него новое.

Отрицанием высказывания “У меня дома есть компьютер” будет высказывание “Неверно, что у меня дома есть компьютер” или, что в русском языке то же самое, “У меня дома нет компьютера”. Отрицанием высказывания “Я не знаю китайского языка” будет высказывание “Неверно, что я не знаю китайского языка” или, что в русском языке одно и то же, “Я знаю китайский язык”.

Кванторы

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

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

Кванторы позволяют из конкретной высказывательной формы (см. “Высказывания. Логические значения”) получить высказывательную форму с меньшим числом параметров, в частности, из одноместной высказывательной формы получить высказывание 9.

Квантор общности позволяет из данной высказывательной формы с единственной свободной переменной x получить высказывание с помощью связки “Для всех x …”. Результат применения квантора общности к высказывательной форме A(x) обозначают x A(x). Высказывание x A(x) будет истинным тогда и только тогда, когда при подстановке в A(x) вместо свободной переменной x любого объекта из области возможных значений всегда получается истинное высказывание. Высказывание x A(x) может читаться следующим образом: “Для любого x имеет место A(x)”, “A(x) при произвольном x”, “Для всех x верно A(x)”, “Каждый x обладает свойством A(x)” и т.п.

 

Квантор существования позволяет из данной высказывательной формы с единственной свободной переменной x получить высказывание с помощью связки “Существует такой x, что …”. Результат применения квантора общности к высказывательной форме A(x) обозначают x A(x). Высказывание
x A(x) истинно тогда и только тогда, когда в области возможных значений переменной x найдется такой объект, что при подстановке его имени вместо вхождения свободной переменной x в A(x) получается истинной высказывание. Высказывание x A(x) может читаться следующим образом: “Для некоторого x имеет место A(x)”, “Для подходящего x верно A(x)”, “Существует x, для которого A(x)”, “Хотя бы для одного x верно A(x)” и т.п.

Кванторы играют для формализованных языков математической логики ту же роль, которую играют для естественного языка так называемые “количественные” (“кванторные”) слова, — определяют область применимости данного высказывания (или высказывательной формы).

При построении отрицания к высказыванию, содержащему квантор, действует следующее правило: частица “не” добавляется к сказуемому, квантор общности заменяется на квантор единственности и наоборот. Рассмотрим пример. Отрицанием высказывания “Все юноши 11-х классов — отличники” является высказывание “Неверно, что все юноши 11-х классов — отличники” или “Некоторые юноши 11-х классов — не отличники”.

В информатике кванторы применяются в логических языках программирования (см. “Языки программирования”) и языках запросов к базам данных.

Методические рекомендации

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

С логическими операциями дизъюнкция, конъюнкция и отрицание школьники знакомятся в основной школе. Там же вводится и понятие таблицы истинности. Скорее всего знакомство с данными понятиями возникает в языках программирования, но использовать их можно и в электронных таблицах — там логические операции реализованы через соответствующие функции OR, AND, NOT.

Более сложные логические операции могут быть рассмотрены в старшей школе. Задачи, использующие импликацию, встречаются в каждом из опубликованных вариантов ЕГЭ по информатике. Например: для какого числа X истинно высказывание ((X > 3) (X < 3)) –> (X < 1)? (Демоверсия ЕГЭ, 2007 г.)

При изучении операции импликации следует обратить внимание учащихся на тот факт, что большинство математических теорем являются импликациями. Однако те импликации, в которых посылки (условия) и заключения (следствиями) являются предложениями без взаимной (по существу) связи, не могут играть в науке более или менее важной роли. Они являются совершенно бесплодными предложениями, т.к. не ведут к выводам более глубокого содержания. Действительно, в математике ни одна теорема не является импликацией, в которой условие и заключение не были бы связаны по содержанию. Помимо связки “если, … то …”, в математических теоремах импликациями являются формулировки только необходимого или только достаточного условия.

Задания на построение достаточных и необходимых условий для школьников оказываются непростыми. При формировании этого умения необходимо особо отметить три момента:

а) используемая в математических утверждениях форма “необходимо и достаточно” соответствует связке “тогда и только тогда” (эквивалентность);

б) связка “для того чтобы …(A), необходимо, чтобы …(B)” реализуется прямой импликацией A B. (Для того чтобы квадратное уравнение имело решение, необходимо, чтобы дискриминант был неотрицательным);

в) достаточное условие реализуется обратной импликацией B ® A и может на русском языке выражаться, например, так: “для того чтобы... (А), достаточно, чтобы... (В)”.

В старшей школе (10–11-е классы) у учащихся полезно сформировать умение строить отрицание к высказыванию на русском языке. Это умение необходимо, например, для доказательства теорем методом “от противного”. Строить отрицание даже к простым высказываниям не всегда просто. Например, к высказыванию На стоянке стоят красные Жигули” следующие предложения отрицаниями являться не будут:

1) На стоянке стоят не красныеЖигули”;

2) На стоянке стоит белыйМерседес”;

3) Красные Жигулистоят не на стоянке.

Отрицанием к этому высказыванию будет “На стоянке не стоят красные “Жигули”. Объяснить школьникам это можно так: отрицание к предложению должно полностью исключать истинность исходного высказывания. Если же на стоянке стоит белый “Мерседес”, то ничто не мешает красным “Жигулям” стоять тоже.

Об алгоритме построения отрицания к сложному высказыванию можно прочитать в книге Е.Андреевой, Л.Босовой, И.Фалиной “Математические основы информатики”.

Изучение кванторов до настоящего времени не было традиционным для школьного курса информатики. Однако теперь они входят в стандарт профильной школы. Проще всего продемонстрировать роль кванторов при построении все тех же отрицаний к высказываниям на русском языке, причем как к математическим, так и произвольным. Правило замены квантора общности на квантор существования и наоборот легко обосновать с помощью законов де Моргана (см. “Логические выражения”).



6 От латинских слов idem — тот же самый и potens — сильный; дословно — равносильный.

7 Это определение легко распространяется на случай n высказываний (n > 2, n — натуральное число).

8 Это определение, как и предыдущее, распространяется на случай n высказываний (n > 2, n — натуральное число).

9 Успенский В.А., Верещагин Н.К., Плиско В.Е. Вводный курс математической логики. М.: Физматлит, 2002.





Наверх