В любом национальном языке употребляемые в обычной речи связки “и”, “или”, “если …, то …”, “тогда и только тогда, когда …” и т.п. позволяют из уже заданных высказываний строить новые сложные высказывания. Истинность или ложность получаемых таким образом высказываний зависит от истинности и ложности исходных высказываний и соответствующей трактовки связок как операций над высказываниями . Логическая операция полностью может быть описана таблицей истинности , указывающей, какие значения принимает сложное высказывание при всех возможных значениях простых высказываний.
Логической операцией называется способ построения сложного высказывания из элементарных высказываний, при котором истинностное значение сложного высказывания полностью определяется истинностными значениями исходных высказываний (см. статью “”).
В алгебре логики логические операции и соответствующие им логические связки имеют специальные названия и обозначаются следующим образом:
Конъюнкция - логическая операция, ставящая в соответствие каждым двум элементарным высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны 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.
Кроме известных нам логических операций для предикатов вводятся две новые: операция навешивания кванторов существования и общности.
«для всех х » (для любого х , для каждого х ) называется квантором общности и обозначается х.
Высказывание «существует х » (для некоторых х , хотя бы для одного х, найдется такое х ) называется квантором существования и обозначается х.
Высказывание «существует одно и только одно х » (для единственного значения х ) называется квантором единственности : ! х.
Например: «Все кустарники являются растениями». Это высказывание содержит квантор общности («все»). Высказывание «существуют числа, кратные 5 » содержит квантор существования («существуют»).
Для того чтобы получить высказывание из многоместного предиката, надо связать кванторами каждую переменную. Например, если Р(х; у) - двухместный предикат, то (хХ) (уY) Р(х; у) - высказывание.
Если не каждая переменная связывается квантором, то получается не высказывание, а предикат, зависящий от той переменой, которая не связана квантором. Так, если перед предикатом Р(х; у) поставить квантор у, то получим предикат (уY) Р(х; у) , зависящий от переменной х.
Выясним, какие из следующих предложений являются высказываниями, а какие предикатами: а) найдется такое х, что х+ у = 2;
b) для любых х и у имеет место равенство х + у = у + х.
Решение : Выявим логическую структуру данных предложений.
а) Предложение «Найдется такое х, что х + у = 2 » можно записать в виде (хR) х + у = 2. Так как квантором связана только переменная х, то рассматриваемое предложение с двумя переменными является предикатом.
b) Предложение «для любых х и у имеет место х + у = у + х » можно записать в виде: (хR) (уR) х + у = у + х, где обе переменные являются связанными. Следовательно, данное предложение является высказыванием.
Если какое-либо предметное переменное в формуле не связано квантором, то его называют свободным переменным.
Например: (х) ху=ух. Здесь переменное у не связано каким-либо квантором, поэтому оно свободно. От него не зависит истинность данного высказывания.
Кванторы (х) (х ) называются двойственными друг другу.
Одноименные кванторы можно менять местами, что не влияет на истинность высказывания.
Например: (у) (х) х + у = 5. Это утверждение имеет тот же смысл, что и (х) (у) х + у = 5.
Для разноименных кванторов изменение порядка может привести к изменению истинности высказывания.
Например: (х) (у) х<у , т.е. для всякого числа х существует большее число у - истинное высказывание.
Поменяем местами кванторы: (х) (у) x
В связи с введением кванторов необходимо учесть следующее:
1. Формула логики предикатов не может содержать одно и то же предметное переменное, которое было бы связано в одной части формулы и свободно в другой.
2. Одно и то же переменное не может находиться в области двойственных друг другу кванторов.
Нарушение этих условий называют коллизией переменных .
Как устанавливается значение истинности высказывания с квантором?
Для доказательства утверждения с квантором общности необходимо убедиться в том, что при подстановке каждого из значений х в предикат Р(х) последний обращается в истинное высказывание. Если множество Х конечно, то это можно сделать путем перебора всех случаев; если же множество Х бесконечно, то необходимо провести рассуждения в общем виде.
Высказывание (х) Р(х) ложно, если можно указать такое значение а Х , при котором Р(х) обращается в ложное высказывание Р(а). Поэтому, для опровержения высказывания с квантором общности достаточно привести пример.
Высказывание (х) Р(х) истинно, если можно указать такое значение а Х , при котором Р(х) обращается в истинное высказывание Р(а) . Поэтому, чтобы убедиться в истинности высказывания с квантором существования , достаточно привести пример и таким образом доказать.
Для того чтобы убедиться в ложности высказывания с квантором существования (х) Р(х), необходимо убедиться в ложности каждого Р(х ), Р(х ), …, Р(х ). Если множество Х конечно, то это можно сделать перебором. Если же множество Х бесконечно, то необходимо провести рассуждения в общем виде.
Примеры .
1. Найти значение истинности «средичисел1, 2, 3, 4 найдется простое число».
Решение: Высказывание содержит квантор существования и поэтому может быть представлено в виде дизъюнкции высказываний: «1 - простое число» или «2 - простое число» или «3 - простое число» или «4 - простое число». Для доказательства истинности дизъюнкции достаточно истинности хотя бы одного высказывания, например, «3 - простое число», которое истинно. Следовательно, истинно и исходное высказывание.
2. Докажем, что любой квадрат является прямоугольником.
Решение: Высказывание содержит квантор общности. Поэтому оно может быть представлено в виде конъюнкции: «квадрат - прямоугольник» и «квадрат - прямоугольник» и «квадрат - прямоугольник» и т.д. Так как все эти высказывания истинны, то истинна конъюнкция этих высказываний, следовательно, истинно и исходное предложение.
3. «Любой треугольник равнобедренный». Это ложное высказывание. Чтобы убедиться в этом, достаточно начертить треугольник, не являющийся равнобедренным.а
Для построения отрицания высказывания с кванторами надо:
1) квантор общности заменить квантором существования, а квантор существования - квантором общности;
2) предикат заменить его отрицанием.
Пример. Сформулируем отрицание для следующих высказываний:
а) все элементы множества Z четные; b) некоторые глаголы отвечают на вопрос «что делать?».
Решение: а) Заменим квантор общности квантором существования, а высказывание его отрицанием: некоторые элементы множества Z нечетные.
b) Заменим квантор существования квантором общности, а выражение его отрицанием: все глаголы не отвечают на вопрос «что делать?».
Функциональная природа предиката влечет за собой введение ещё одного понятия – квантора . (quantum – от лат. «сколько») Кванторные операции можно рассматривать как обобщение операций конъюнкции и дизъюнкции в случае конечных и бесконечных областей.
Квантор общности (все, всякий, каждый, любой (all – «всякий»)). Соответствующие ему словесное выражение звучит так:
«Для всякого x Р(x) истинно». Вхождение переменной в формулу может быть связанным, если переменная расположена либо непосредственно после знака квантора, либо в области действия квантора, после которого стоит переменная. Все прочие вхождения – свободные, переход от P(x) к x(Px) или (Px) называется связыванием переменной x или навешиванием квантора на переменную x (или на предикат P) или квантификацией переменной х. Переменная, на которую навешивается квантор, называется связанной , несвязанная квантования переменная называется свободной .
Например, переменная x в предикате Р(x) называется свободной (x – любое из М), в высказывании Р(x) переменную x называют связанной переменной.
Справедлива равносильность P(x 1)P(x 2)…P(x n),
P(x) – предикат, определенный на множестве М={х 1 ,х 2 ...х 4 }
Квантор существования (exist – «существовать»). Словесное выражение, соответствующее ему, звучит так: “Существует x, при котором Р(x) истинно”. Высказывание xР(x) уже не зависит от x, переменная x связана квантором .
Справедлива равносильность:
xP(x) = P(x 1)P(x 2)…P(x n), где
P(x) - предикат, определенный на множестве М={x 1 ,x 2 …x n }.
Квантор общности и квантор существования называют двойственными, иногда используется обозначение квантора ! – «существует, и притом, только один».
Ясно, что высказывание xP(x) истинно только в том единственном случае, когда Р(x) - тождественно истинный предикат, а высказывание ложно только тогда, когда Р(x) - тождественно ложный предикат.
Кванторные операции применяются и к многоместным предикатам. Применение кванторной операции к предикату P(x,y) по переменной x ставит в соответствие двухместному предикату P(x,y) одноместный предикат xP(x,y) или xP(x,y), зависящий от у и не зависящий от х.
К двухместному предикату можно применить кванторные операции по обеим переменным. Тогда получим восемь высказываний:
1. P(x,y); 2. P(x,y);
3. P(x,y); 4. P(x,y);
5. P(x,y); 6. P(x,y);
7. P(x,y); 8. P(x,y)
Пример 3. Рассмотреть возможные варианты навешивания кванторов на предикат P(x,y) – “x делится на y ”, определенный на множестве натуральных чисел (без нуля) N . Дать словесные формулировки полученных высказываний и определить их истинность.
Операция навешивания кванторов приводит к следующим формулам:
Высказывания “для любых двух натуральных чисел имеет место делимость одного на другое” (или 1) все натуральные числа делятся на любое натуральное число; 2) любое натуральное число является делителем для любого натурального числа) ложные;
Высказывания “существуют такие два натуральных числа, что первое делится на второе” (1. «существует такое натуральное число x, которое делится на какое-то число y»; 2. «существует такое натуральное число y, которое является делителем какого-то натурального числа x») истинны;
Высказывание “существует натуральное число, которое делится на любое натуральное”, ложное;
Высказывание “для всякого натурального числа найдется такое натуральное, которое делится на первое” (или для всякого натурального числа найдется свое делимое), истинное;
Высказывание “для всякого натурального x существует такое натуральное число y, на которое оно делится” (или «для всякого натурального числа найдется свой делитель»), истинное;
Высказывание “существует натуральное число, которое является делителем всякого натурального числа”, истинное (таким делителем является единица).
В общем случае изменение порядка следования кванторов изменяет смысл высказывания и его логическое значение, т.е. например, высказывания P(x,y) и P(x,y) различны.
Пусть предикат P(x,y) означает, что x является матерью для y, тогда P(x,y) означает, что у каждого человека есть мать – истинное утверждение. P(x,y) означает, что существует мать всех людей. Истинность этого утверждения зависит от множества значений, которые могут принимать y: если это множество братьев и сестер, то оно истинно, в противном случае оно ложно. Таким образом, перестановка кванторов всеобщности и существования может изменить сам смысл и значение выражения.
а) заменить начальный знак (или ) на противоположный
б) поставить знак перед остальной частью предиката
Рассмотрим несколько предложений с переменной:
-
«
-
простое натуральное число»; область
допустимых значений этого предиката –
множество натуральных чисел;
-
«
- чётное целое число»; область допустимых
значений этого предиката – множество
целых чисел;
-
«
- равносторонний»;
-
«
»
-
«студент
получил оценку
»
-
«
делится нацело на 3»
Определение . Если предложение с переменными при любой замене переменных допустимыми значениями превращается в высказывание, то такое предложение называется предикатом.
,
,
,
- предикаты от одной переменной
(одноместные предикаты). Предикаты
от двух переменных:
,
- двухместные предикаты. Высказывания
– нульместные предикаты.
Квантор общности.
Определение
. Символ
называется квантором общности.
читается:
для любого
,
для каждого
,
для всех
.
Пусть
- одноместный предикат.
читается: для любых
- истина.
Пример.
- «Все натуральные числа простые» -
Ложное высказывание.
-
«Все целые числа чётные» - Ложное
высказывание.
- «Все студенты получили оценку
»
- одноместный предикат. Навесили
квантор на двуместный предикат, получили
одноместный предикат. Аналогично
-n-местный предикат, то
- (n-1)-местный предикат.
- (n-2)-местный предикат.
В русском языке квантор общности опускается.
Квантор существования.
Определение.
Символ
называется квантором существования.
читается: существует
,
есть
,
найдётся
.
Выражение
,
где
- одноместный предикат, читается:
существует
,
для которого
истинно.
Пример.
- «существуют простые натуральные
числа». (и)
- «существуют целые чётные числа». (и).
-
«существует студент, который получил
оценку
»
- одноместный предикат.
Если на n-местный предикат навесить 1 квантор, то получим (n-1)-местный предикат, если навеситьnкванторов, то получим нульместный предикат, т.е. высказывание.
Если навешивать кванторы одного вида, то порядок навешивания кванторов безразличен. А если на предикат навешиваются разные кванторы, то порядок навешивания кванторов менять нельзя.
Построение отрицания высказываний, содержащих кванторы. Законы Де Моргана.
Закон Де Моргана.
При построении отрицания высказывания, содержащего квантор общности, этот квантор общности заменяется на квантор существования, а предикат заменяется на своё отрицание.
Закон Де Моргана.
При построении отрицания высказываний,
содержащих квантор существования, нужно
квантор существования заменить на
квантор общности, а предикат
- его отрицанием. Аналогично строится
отрицание высказываний, содержащих
несколько кванторов: квантор общности
заменяется на квантор существования,
квантор существования - на квантор
общности, предикат заменяется своим
отрицанием.
П.2. Элементы теорий множеств (интуитивная теория множеств). Числовые множества. Множество действительных чисел.
Описание множества : под словом множество понимается совокупность объектов, которая рассматривается как одно целое. Вместо слова «множество» иногда говорят «совокупность», «класс».
Определение . Объект, входящий в множество, называется его элементом.
Запись
обозначает, что
является
элементом множества
.
Запись
обозначает, что
не является элементом множества
.
Про любой объект можно сказать, является
он элементом множества или нет. Запишем
это утверждение с помощью логических
символов:
Не существует объекта, который одновременно принадлежит множеству и не принадлежит, то есть,
Множество не может содержать одинаковых
элементов, т.е. если из множества,
содержащего элемент
,
удалить элемент
,
то получится множество, не содержащее
элемент
.
Определение.
Два множества
и
называются равными, если они содержат
одни те же элементы.
