Рассмотрим несколько предложений с переменной:

- «- простое натуральное число»; область допустимых значений этого предиката – множество натуральных чисел;

- «- чётное целое число»; область допустимых значений этого предиката – множество целых чисел;

- «
- равносторонний»;

- «
»

- «студентполучил оценку»

- «делится нацело на 3»

Определение . Если предложение с переменными при любой за­мене переменных допустимыми значениями превращается в высказы­вание, то такое предложение называется предикатом.

,
,
,
- предикаты от одной переменной (одноместные пре­дикаты). Предикаты от двух переменных:
,
- двухместные предикаты. Высказывания – нульместные предикаты.

Квантор общности.

Определение . Символназывается квантором общности.

читается: для любого, для каждого, для всех.

Пусть
- одноместный предикат.

читается: для любых
- истина.

Пример.

- «Все натуральные числа простые» - Лож­ное высказывание.

- «Все целые числа чётные» - Ложное высказывание.

- «Все студенты получили оценку» - одноместный преди­кат. Навесили квантор на двуместный предикат, получили одномест­ный предикат. Аналогично
-n-местный предикат, то

- (n-1)-местный предикат.

- (n-2)-местный пре­дикат.

В русском языке квантор общности опускается.

Квантор существования.

Определение. Символназывается квантором существования.

читается: существует, есть, найдётся.

Выражение
, где
- одноместный предикат, чита­ется: существует, для которого
истинно.

Пример.

- «существуют простые натуральные числа». (и)

- «существуют целые чётные числа». (и).

- «существует студент, который получил оценку» - од­номестный предикат.

Если на n-местный предикат навесить 1 квантор, то получим (n-1)-ме­стный предикат, если навеситьnкванторов, то получим нульместный предикат, т.е. высказывание.

Если навешивать кванторы одного вида, то порядок навешива­ния кванторов безразличен. А если на предикат навешиваются разные кванторы, то порядок навешивания кванторов менять нельзя.

Построение отрицания высказываний, содержащих кван­торы. Законы Де Моргана.

Закон Де Моргана.

При построении отрицания высказывания, содержащего квантор общности, этот квантор общности заменяется на квантор существования, а предикат заменяется на своё отрицание.

Закон Де Мор­гана.

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

П.2. Элементы теорий множеств (интуитивная теория множеств). Числовые множества. Множество действительных чисел.

Описание множества : под словом множество понимается сово­купность объектов, которая рассматривается как одно целое. Вместо слова «множество» иногда говорят «совокупность», «класс».

Определение . Объект, входящий в множество, называется его элементом.

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

Не существует объекта, который одновременно принадлежит множеству и не принадлежит, то есть,

Множество не может содержать одинаковых элементов, т.е. если из множества, содержащего элемент , удалить элемент, то полу­чится множество, не содержащее элемент.

Определение. Два множестваиназываются равными, если они содержат одни те же элементы.

Специфическая природа предикатов позволяет ввести над ними такие операции, которые не имеют аналогов среди операций над высказываниями. Имеются в виду две кванторные операции над предикатами.

Квантор общности

Для превращения одноместного предиката в высказывание нужно вместо его переменной подставить какой-нибудь конкретный предмет из области задания предиката. Имеется еще один способ для такого превращения – это применение к предикату операций связывания квантором общности или квантором существования. Каждая из этих операций ставит в соответствие одноместному предикату некоторое высказывание, истинное или ложное в зависимости от исходного предиката.

Определение. называется правило, по которому каждому одноместному предикату Р(х), определенному на множестве М, сопоставляется высказывание, обозначаемое , которое истинно в том и только в том случае, когда предикат Р(х) тождественно истинен, и ложно в противном случае, то есть

Словесным аналогом квантору общности " является: «для любого», «для каждого», «для всякого» и т.п.

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

Если одноместный предикат Р(х) задан на конечном множестве М = { a 1 , a 2 , …, a n } , то высказывание эквивалентно конъюнкции Р(а 1) Р(а 2) … Р(а n).

Пример 59 .

Пусть х определен на множестве людей М , а Р(х) – предикат «х – смертен» . Дать словесную формулировку предикатной формулы .

Решение.

Выражение означает «все люди смертны». Оно не зависит от переменной х , а характеризует всех людей в целом, т. е. выражает суждение относительно всех х множества М .

Определение. Операцией связывания квантором общности n-местному ( n , сопоставляется новый ( , истинное в том и только в том случае, когда одноместный предикат , определенный на множестве М 1 , тождественно истинен, и ложное в противном случае, то есть:

Квантор существования

Определение. называется правило, по которому каждому одноместному предикату Р(х), определенному на множестве М, сопоставляется высказывание, обозначаемое , которое ложно в том и только в том случае, когда предикат Р(х) тождественно ложен, и истинно в противном случае, то есть

Словесным аналогом квантору существования $ является: «существует», «найдется» и т.п.

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

Если одноместный предикат Р(х) задан на конечном множестве М = { a 1 , a 2 , …, a n } , то высказывание эквивалентно дизъюнкции Р(а 1) Р(а 2) … Р(а n).

Пример 60.

Пусть Р(х) – предикат «х – четное число» , определенный на множестве N . Дать словесную формулировку высказыванию , определить его истинность.

Решение.

Исходный предикат Р(х): «х – четное число» является переменным высказыванием: при подстановке конкретного числа вместо переменной х он превращается в простое высказывание, являющееся истинным или ложным, например,

при подстановке числа 5 – ложным, при подстановке числа 10 – истинным.

Высказывание означает «во множестве натуральных чисел N существует четное число». Поскольку множество N содержит четные числа, то высказывание истинно.

Определение. Операцией связывания квантором существования по переменной х 1 называется правило, по которому каждому n-местному (n 2) предикату Р(х 1 , х 2 , …, х n), определенному на множествах М 1 , М 2 , …, М n , сопоставляется новый (n-1)-местный предикат, обозначаемый , который для любых предметов , превращается в высказывание , ложное в том и только в том случае, когда одноместный предикат , определенный на множестве М 1 , тождественно ложен, и истинное в противном случае, то есть:

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

Пример 61.

Пусть предикат Р(х, у) описывает отношение «х любит у» на множестве людей. Рассмотреть все варианты навешивания кванторов на обе переменные. Дать словесную интерпретацию полученных высказываний.

Решение.

Обозначим предикат «х любит у» через ЛЮБИТ(х, у) . Предложения, соответствующие различным вариантам навешивания кванторов, проиллюстрированы на рис. 2.3-2.8, где х и у показаны на разных множествах, что является условностью и предпринято только для объяснения смысла предложений (реальные множества переменных х и у , очевидно, должны совпадать):

— «для любого человека х существует человек у , которого он любит» или «всякий человек кого-нибудь любит» (рис. 2.3).

Рис. 2.3. Иллюстрация к высказыванию «для любого человека х существует человек у , которого он любит» или «всякий человек кого-нибудь любит»

Оператор, с помощью которого о к.-л. отдельном объекте преобразуется в высказывание о совокупности (множестве) таких объектов.
В логике используется два основных К.: К. общности, «V», и К. существования, «Э». В естественном языке отдаленными смысловыми аналогами К. общности являются слова «все», «любой», «каждый»; смысловыми аналогами К. существования - слова «некоторые», «существует». С помощью данных К. любое атрибутивное высказывание вида Р(х) о том, что объекту х присуще Р, может быть преобразовано в соответствующее кванторное высказывание вида VхР(х) и вида ЗхР(х). Содержательно сама кванторная формула «VxP(x)» читается как «для всех х имеет Р(х)», а формула «ЭхР(х)» - как «для некоторых х имеет место Р(х)». Высказывание вида VxP(x) истинно, если любой х обладает свойством Р; и ложно, если хотя бы один х не обладает свойством Р. Аналогичным образом, высказывание вида ЗхР(х) истинно, если хотя бы один х обладает свойством Р; и ложно, если ни один х не обладает свойством Р.
На основе элементарных кванторных формул «VxP(x)», «ЭхР(х)» могут быть построены др., более сложные кванторные формулы. Логические взаимосвязи между такими формулами изучаются в логике предикатов. В частности, формула «ЗхР(х)» логически эквивалентна формуле «) VxКВАНТОР| P(x)», а формула «VхР(х)» эквивалентна формуле «) Эх) Р(х)», где «)» - отрицания.
В неявной форме К. использовались уже Аристотелем, однако в строгом содержательном и формальном смысле они впервые были введены в логику Г. Фреге.

Философия: Энциклопедический словарь. - М.: Гардарики . Под редакцией А.А. Ивина . 2004 .

(от лат. quantum - сколько) , оператор логики предикатов, применение крого к формулам, содержащим лишь одну свободную переменную, даёт (высказывание) . Различают К. общности, обозначаемый символом (от англ. all - все) , и К. существования (от exist - существовать) : хР(х) интерпретируется (см. Интерпретация) как «для всех х имеет место свойство Р», а хР(х) - как «существует х такой, что имеет место свойство?(х) ». Если (универсум) конечна, то хР(х) равносильно конъюнкции всех формул Р(а) , где а - элемент предметной области. Аналогично, хР(х) равносильно дизъюнкции всех формул вида? (а) . Если же предметная область бесконечна, то xP(x) и хР(х) могут быть истолкованы соответственно как бесконечные и дизъюнкция. Введение К. в логике многоместных предикатов (т. е. неодноместных) обусловливает неразрешимость исчисления предикатов. Различные соотношения между К. общности и существования и логическими связками логики высказываний формализуются в исчислении предикатов.

Философский энциклопедический словарь. - М.: Советская энциклопедия . Гл. редакция: Л. Ф. Ильичёв, П. Н. Федосеев, С. М. Ковалёв, В. Г. Панов . 1983 .

(от лат. quantum - сколько) - логич. оператор, применяемый к логич. выражениям и дающий количеств. характеристику области предметов (а иногда и области предикатов), к к-рой относится получаемое в результате применения К. . В то как логич. средств логики высказываний недостаточно для выражения форм всеобщих, частных и единичных суждений, в логике предикатов, получаемой посредством расширения логики высказываний за счет введения К., такие суждения выразимы. Так, напр., четыре осн. формы суждений традиц. логики "Все А суть В", "Ни одно А не есть В", "Нек-рые А суть В" и "Нек-рые А не суть В" могут быть записаны (если отвлечься от предполагаемого аристотелевой логикой требования непустоты А в общих суждениях) при помощи поясняемой ниже символики следующим образом: ∀(х) (А (х) ⊃ В (х)), ∀(х) (А (х) ⊃ В(x)), ∃(х) (А (х) & В (х)) и ∃ (х) (А (х) & B (x)). Введение К. дает записывать на формализованном логич. языке выражения естеств. языка, содержащие количест. характеристики к.-л. предметных или предикатных областей. В естеств. языках носителями таких характеристик являются т. н. кванторные слова, к числу к-рых относятся, в частности, количеств. числительные, местоимения "все", "каждый", "нек-рый", глагол "существует", прилагательные "любой", "всякий", "единственный", наречия "бесконечно много" и т.п. Оказывается, что для выражения всех упомянутых кванторных слов в формализ. языках и логич. исчислениях достаточно двух наиболее употребит. К.: К. общности (или в с е о б щ н о с т и), обозначаемого обычно символом ∀(перевернутая буква А – начальная буква англ. слова "all", нем. "alle" и др.), и К. с у щ е с т в о в а н и я, обозначаемого обычно символом ∃ (перевернутая буква E – начальная буква англ. слова "exist", нем. "existieren" и др.); за знаками ∀ и ∃ в обозначении К. следует буква нек-рого алфавита, называемая кванторной переменной, к-рую рассматривают обычно как часть обозначения К.: ∀х, ∀у, ∀F, ∃х, ∃α и т.п. Для К. общности употребляют также обозначения:

для К. существования:

Знак К. ставится перед выражением, к к-рому применяется К. (операцию применения К. часто называют квантификацией); это выражение заключается в скобки (к-рые часто опускают, если это не приводит к двусмысленности). Содержащее К. общности выражение ∀x (А (х)) читается как "Для всех x верно, что А (х)", или "Для каждого x верно А (х)"; содержащее К. существования выражение ∃х (А(х)) читается как "Существует x такой, что А (х)", или "Для нек-рого x верно А(х)". В обоих этих случаях не предполагается, вообще говоря, что выражение A (х) в действительности зависит от переменной x ( может и вообще не содержать никаких переменных, т.е. может обозначать нек-рое высказывание; в этом случае не меняет смысла этого высказывания). Однако осн. назначение К. - высказываний из выражения, зависящего от кванторной переменной, или хотя бы уменьшение числа переменных, от к-рых это выражение, будучи незамкнутой (открытой) формулой (см. Замкнутая формула), зависит. Напр., выражение (y>0&z>0&x=у-z) содержит три переменные (х, y и z) и становится высказыванием (истинным или ложным) при к.-л. опред. замещении этих переменных именами нек-рых предметов из области их значений. Выражение ∃ z(y>0&z>0&x = y-z) зависит уже лишь от двух переменных (х и у), a ∃y∃z (y>0&z>0& &х = у –z) - от одной х. Последняя формула выражает, т.о., нек-рое свойство (одноместный ). Наконец, формула ∃х∃у∃z (y>0&z>0&x=y–z) выражает вполне опред. высказывание.

Др. примеры формул, содержащих К.: 1) ∀х(х>0); 2) ∃х(х>0); 3) ∀х (2+2=5); 4) ∃x (2+2=4); 5) ∀х (х = х)& (х+2=у); 6) ∀х∃у (∀z (x = z⊃x ≠ 0) & (x действие к.-л. К., наз. областью действия этого К. Так, в формуле 6) областями действия К. ∀х и ∃y являются стоящие справа от них части формулы, а область действия К. ∀z - формула (x = z⊃x ≠ 0). Вхождение к.-л. переменной в знак К. или в область действия К., содержащего эту переменную, наз. связанным вхождением переменной в формулу. В остальных случаях вхождение переменной наз. с в о б о д н ы м. Одна и та же может входить в к.-л. формулу в одном месте в связанном виде, а в др. месте – в свободном. Такова, напр., формула 5): первые три (считая слева) вхождения в нее переменной x – связанные, последнее же – свободное. Иногда говорят, что переменная связана в данной формуле, если все ее вхождения в эту формулу – связанные. В математике и логике всякое выражение, содержащее свободную переменную, может рассматриваться (при неформальном подходе) как ее в том обычном смысле этого слова, что оно (выражение) зависит от различных значений этой переменной; придавая этой переменной различные значения (т. е. замещая все ее свободные вхождения именем к.-л. предмета, принадлежащего к области значений этой переменной), мы получаем различные (вообще говоря) значения данного выражения, зависящие от значения переменной, т.е. от подставленной вместо нее константы. Что же касается связанных переменных, то заключающие их выражения в действительности от них не зависят. Напр., выражение ∃х(х = 2у), зависящее от у (входящего в него свободно), эквивалентно выражениям ∃z(z = 2y), ∃u(u = 2у) и т.п. Эта логич. выражений от входящих в них связанных переменных находит в т. н. правиле переименования с в я з а н н ы х п е р е м е н н ы х, постулируемом или выводимом в разл. логич. исчислениях (см. Переменная , Предикатов исчисление).

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

К. общности и существования не исчерпываются употребительные в логике виды К. Обширный К. представляют собой т. н. ограниченные К. вида ∀хP(x)А(х) или ∃xQ(x)A(x), в к-рых область изменения кванторной переменной x "ограничена" нек-рым спец. предикатом Р(х) (или Q(x)). Ограниченные К. сводятся к К. общности и существования при помощи след. эквивалентностей: ∀xP(x)A(x) КВАНТОР∀x(P(x) ⊃A(x)) и ∃xQ(x)A(x) КВАНТОР ∃x(Q(x)&A(x)). Часто употребляемый К. единственности ∃!хА(х) ("существует единственное x такое, что А(х)") также выражается через К. общности и существования, напр. так: xA(x) КВАНТОР ∃xA(x)& ∀y∀z(A(y)&A(z)⊃y=z).

Употребительны и др. виды К., не покрываемые понятием ограниченного К. Таковы "числовые" К. вида ∃хnА(х) ("существует в точности n различных x таких, что А(х)"), употребляемый в интуиционистской логике К. "квазисуществования" ∃ хА(х), или ("неверно, что не существует такого х, что А(х)"); с т. зр. классич. логики К. "квазисуществования" ничем не отличается от К. существования, в интуиционистской же логике предложение ∃xA(x), ничего не говорящее о существовании алгоритма для нахождения такого х, что А(х), действительно утверждает лишь "квази" такого x и К. бесконечности ∃x∞A(x) ("существует бесконечно много таких х, что А(х)"). Выражения, содержащие К. бесконечности и числовые К., также могут быть записаны при помощи К. общности и существования. В расширенном исчислении предикатов К. берутся не только по предметным, но и по предикатным переменным, т.е. рассматриваются формулы вида ∃F∀xF(x), ∀Ф∃у(Ф(y)) и т.п.

Лит.: Гильберт Д. и Аккерман В., Основы теоретической логики, пер. с англ., М., 1947, с. 81-108; Тарский А., Введение в логику и методологию дедуктивных наук, пер. с англ., М., 1948, о. 36-42, 100-102, 120-23; Клини С. К., Введение в метаматематику, пер. с англ., М., 1957, с. 72-80, 130-38; Чёрч Α., Введение в математическую логику, пер. с англ., т. 1, с. 42–48; Кузнецов А. В., Логические контуры алгоритма, перевода со стандартизованного русского языка на информационно-логический, в сб.: Тезисы докладов на конференции по обработке информации, машинному переводу и автоматическому чтению текста, М., 1961; Mostowski A., On a generalization of quantifiers, "Fundam. math.", 1957, t. 44, No 1, p. 12–36; Hailperin T., A theory of restricted quantification, I–II, "J. Symb. Logic", 1957, v. 22, No 1, p. 19–35, No 2, p. 113–29.

Ю. Гастев. Москва.

Философская Энциклопедия. В 5-х т. - М.: Советская энциклопедия . Под редакцией Ф. В. Константинова . 1960-1970 .

Синонимы :

Смотреть что такое "КВАНТОР" в других словарях:

Сущ., кол во синонимов: 1 оператор (24) Словарь синонимов ASIS. В.Н. Тришин. 2013 … Словарь синонимов

квантор - — Тематики электросвязь, основные понятия EN quantifier … Справочник технического переводчика

Квантор общее название для логических операций, ограничивающих область истинности какого либо предиката и создающих выcказывание. Чаще всего упоминают: Квантор всеобщности (обозначение: , читается: «для всех…», «для каждого…» или «каждый…» … Википедия

Общее название для логических операций, к рые по предикату Р(х)строят высказывание, характеризующее область истинности предиката Р(х). В математич. логике наиболее употребительны квантор всеобщности и квантор существования Высказывание означает,… … Математическая энциклопедия

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

При изучении высказывательных форм (предикатов) был указан один из способов получения высказываний: подстановка какого-нибудь значения переменной в Р(х) из некоторого множества А. Например,

Р(х):” х - простое число”. Подставив х = 7, получим высказывание

“ 7 - простое число”. Мы познакомимся ещё с двумя логическими операциями: навешивание квантора общности и квантора существования, которые позволяют получить из высказывательных форм высказывания.

Подставим перед высказывательной формой Р(х) слово “любое”: “ любое х - простое число”. Получили ложное высказывание. Подставим перед Р(х) слово “некоторые”: “ некоторые числа х - простые”. Получили истинное высказывание.

В математике слова “любые”, “некоторые” и их синонимы называются кванторами, которые соответственно называются квантор общности (") и квантор существования ($). Квантор общности заменяется в словесных формулировках словами: любой, все, каждый, всякий и т.д. Квантор существования в словесной формулировке заменяется словами: существует, хотя бы один, какой-нибудь найдётся и т.д.

Пусть Р(х) - высказывательная форма на М. Запись

("хÎМ) Р(х)

означает: для любого элемента х (из множества М) имеет место Р(х), что уже представляет собой высказывание. Чтобы доказать, что высказывание ("х)Р(х) - истинно, надо перебрать все элементы а, b, с и т.д. из М и убедиться, что Р(а), Р(b), Р(с),... истинны, и, если невозможно перебрать элементы М, должны доказать с помощью рассуждений, что для любого а из М высказывание Р(а) истинно. Чтобы убедиться, что ("х)Р(х) ложно, достаточно найти лишь один элемент аÎМ, для которого Р(а) ложно.

ПРИМЕР . Дана высказывательная форма

В(х):” - простое число”.

В(1): 2 2 + 1 = 5 - простое число;

В(2): = 17 - простое число;

В(3): = 257 - простое число;

В(4): = 65537 - простое число.

Можно ли сказать, что ("х)В(х) ? Это необходимо доказывать. Леонард Эйлер доказал, что В(5) - ложно, т.е. + 1 = 2 32 + 1 делится на 641 и, следовательно, ("х)В(х) - ложно.

ПРИМЕР . Рассмотрим высказывание ("х)С(х), где на N задано С(х): “х 3 + 5х делится на 6”.

Очевидно, С(1), С(2), С(3), С(4) истинны. Но если мы проверим даже миллион значений х всегда есть опасность, что для миллион первого значения х утверждение С(х) окажется ложным.

Доказать можно, например, так:

х 3 + 5х = х 3 - х + 6х = х(х 2 - 1) + 6х = (х - 1)х(х + 1) + 6х

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

Пусть С(х) некоторая высказывательная форма. Запись

означает: существует элемент х из множества М, для которого имеет место С(х). ($х)С(х) уже высказывание. Если во множестве М можно найти элемент а, для которого С(а) истинно, то высказывание($х)С(х) - истинно. Если же в М нет ни одного элемента а, для которого С(а) истинно, высказывание ($х)С(х) - ложно.

ПРИМЕР . На множествеN задано С(х):” ”. С(1) - ложно, С(2) - ложно, С(5) - истинно. Следовательно, ($х)С(х) - истинное высказывание.

ПРИМЕР . На множестве N задано К(х):” х 2 + 2х + 3 делится на 7”. К(1) = 6, 6 не делится на 7; К(2) = 11, 11 не делится на 7 и т.д.

Гипотеза: ($х)К(х) - ложно.

Докажем это. Любое натуральное число по теореме о делении с остатком можно представить в виде n = 7q + r, где r < 7.

n 2 + 2n + 3 = (7q + r) 2 + 2(7q + r) + 3 = 7(7q 2 + 2qr + 2q) + r 2 + 2r + 3.

Итак, число n 2 + 2n + 3 делится на 7 тогда и только тогда, когда r 2 + 2r + 3 делится на 7. Остаток r Î { 0, 1, 2, 3, 4, 5, 6 }. Методом перебора убедимся, что r 2 + 2r + 3 не делится на 7. Итак, ($х)К(х) - ложно.

Как построить отрицание высказывания с квантором?

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

[("x)P(x) Û ($x) P(x);

[($x)P(x) Û ("x) P(x).

Например, пусть даны два высказывания:

А: “каждое простое число нечётно”;

В: “ каждое простое число чётно”.

Будет ли В отрицанием высказывания А? Нет, так как ни одно из высказываний не является истинным. В данном случае

А: “не каждое простое число нечётно, т.е. существует чётное простое число” - истинное высказывание.

В дальнейшем считаем, что построено отрицание предложения, если не просто записано его отрицание, но и полученное предложение преобразовано к виду, где знаки отрицания стоят перед более простыми выражениями. Например, отрицанием предложения вида А Ù В будем считать не (А Ù В), а ему равносильное: А Ú В.

Пусть А(х,у) - высказывательная форма с двумя переменными.

Тогда ("х)А(х,у), ($х)А(х,у), ("х)А(х,у), ($х)А(х,у) тоже высказывательные формы но уже с одной переменной. В этом случае говорят, что квантор связывает одну переменную. Чтобы получить из высказывательной формы А(х,у) высказывание необходимо связать обе переменные. Например, ("х)($у)А(х,у) - высказывание.

Для высказывательной формы Р(х,у): “ x < y”, заданной на Z , рассмотрим все случаи получения высказывания путем добавления (навешивания) кванторов:

1) ("х)("у)Р(х,у) Û л - “ Для всякого х и для всякого у х < y”;

2) ("у)("х)(х < y) Û л - “Для всякого у и для всякого х х < y”;

3) ($x)($y) (x < y) Û и - “Существует х и существует у такие, что x < y”;

4) ($у)($х) (х < y) Û и - “Существует х и существует у такие, что x < y”;

5) ("х)($у) (x < y) Û и - “Для всякого х существует у такое, что x < y”;

6) ($у)("х) (x < y) Û л - “Существует у такое, что для всякого х х < y”;

7) ("у)($х) (х < y) Û и - “Для всякого у существует х такое, что x < y”;

8) ($х)("у) (x < y) Û л - “Существует x такое, что для всякого y х < y”.

` Обратите внимание на высказывания (1) и (2), (3) и (4). Структуры этих высказываний отличаются лишь порядком следования одноименных кванторов, но при этом не меняются смысл и значения истинности высказываний.

Высказывания (5) и (6), (7) и (8) отличаются порядком следования разноимённых кванторов, что приводит к изменению смысла и, возможно, значения истинности высказывания. Высказывание (7) утверждает о наличии в Z наименьшего числа, что ложно. (8) утверждает об отсутствии такого, что истинно.

Теоретические вопросы:

1. Понятие предиката от одного, нескольких переменных.

2. Примеры одноместных и двуместных предикатов. 3. Область истинности предиката.

4. Кванторы общности и существования. Свободные и связанные переменные. Операции над предикатами. Какова область истинности ; ; ; ? Дать геометрические интерпретации.

5. Преобразование формул логики предикатов. Определение тождественно истинного и тождественно ложного предиката, связь с областью истинности. Основные равносильности.

Упражнения

5.1. Укажите несколько значений переменных, при которых следующие предикаты истинны, ложны:

1. х 2 , х Î N; 9. = - x, x Î R;

2. х < 1 , x Î N ; 10. > 0 ,

3. x > 6® x ³ 3 , xÎZ; 11. sin x = - , xÎ R;

4. x + 3x +6 = 0 , x Î R; 12. cos x = , x ÎR;

5. = 0, xÎR; 13. x ³ y , x,y Î R;

6. | x - 5 | < 2, 14. x + y < 3, x,yÎ N;

7. | 2x + 3 | ³ 2x + 3, x Î R; 15. x (y - 1) = 0, x,yÎR;

8. = x, x Î R; 16. x + y =4, x, y ÎR.

5.2. Найдите область истинности предикатов упражнения 5.1. Случаи 13 - 16 изобразите на координатной плоскости.

5.3.

1. = 0; 7. | 3x - 2 | > 8;

2. = ; 8. | 5x - 3 | < 7;

3. - > ; 9. 2 - | x | = 1,7;

4. ; 10. | 3x - 1 | = 3x - 1;

5. < 0 ; 11. | 3x - 1 | = 1 - 3x;

6. > 0; 12. | 2x + 4 | ³ 2x + 4.

5.4. Найдите область истинности предикатов:

1. ( < x + 1,5) Ù (2x - 8 > 3 - 0,5 x);

2. ( - 4 < - 1) Ù ( x + 2 (2x- 1) < 3(x +1);

3.( - +2x<3x-3) Ù ( - 3(1-x)+2x< );

4.( - + x < 2x - 4)Ù( + 3 (x - 1)< );

5.((x+3) (x - 1) < 0) Ù (x + 4x + 6 > x (x - 5);

6.((x - 6x + 9)(2x - 10) < 0) Ù (6 + x (7 - x) < x +2x(5-x);

7.(1 + £ ) Ú (- 1 < 5x - 5)

8.( - > 2) Ú (- 3x - 1 > 2) ;

9.( + 6x > + 4) Ú ( - > - );

Рассматриваемые вопросы
1. Кванторы.
2. Квантор всеобщности.
3. Квантор существования.
4. Понятие формулы логики предикатов. Значение формулы
логики предикатов.
5. Равносильные формулы логики предикатов.

Понятие квантора

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

Операции для предиката

Для предикатов вводятся две новые по
сравнению с логикой высказываний операции:
квантор общности
квантор существования

Квантор общности

Пусть Р(x) – одноместный предикат, определенный на
предметном множестве М.
Универсальным высказыванием, соответствующим
предикату Р(x), называется высказывание:
«каждый элемент множества М удовлетворяет
предикату Р(x)»
или
«для всякого х выполняется предикат»
Это высказывание обозначается - (x)P(x)
Высказывание (x)P(x) считается истинным, если
предикат P(x) тождественно истинный, а ложным –
в противном случае.

Квантор общности

Символ x называется квантором
переменной х, его читают так:
«для всех х»
«для каждого х»
«для любого х»
общности по
Выражение (x)P(x) читается: «для всех х, Р(х)», или
«для каждого х, Р(х)».
Например, x(х=х) – это истинное универсальное
высказывание, а x(х>2) – ложное универсальное
высказывание.

конечном множестве {a1,a2,…am}, то:
P(x) P(a1) P(a2) ... P(am)

Квантор общности

Таким образом, квантор общности
можно понимать как оператор
конъюнкции по квантифицируемой
переменной.

Квантор существования

Экзистенциональным
высказыванием,
соответствующим
предикату
Р(x),
называется
высказывание «существует элемент множества М,
удовлетворяющий
предикату
Р(x)»,
которое
обозначается x P(x) и считается истинным, если
предикат Р(х) выполнимый, а ложным – в противном
случае.
Символ x называют квантором существования, а
выражение x, в котором этот квантор предшествует
переменной х, читают так:
«существует х такой, что…»
«для некоторого х, …»

Квантор существования

НАПРИМЕР
x(х>2) –истинное экзистенциональное высказывание
x(х=х+1) – ложное экзистенциональное высказывание.
Если Р(х)- одноместный предикат, определенный на
конечном множестве {a1,a2,…am}, то
P(x) P(a1) P(a2) ... P(am)

Квантор существования

Таким образом, квантор
существования можно понимать как
оператор дизъюнкции по
квантифицируемой переменной.

10. Примеры

Примеры записей формул и их словесные выражения:
x(x 2 1 (x 1)(x 1)) Для всех х выполняется предикат…
x(x 0)

неравенство...
x(x 0)
Для всех х, справедливо…..
y (5 y 5)
Существует y такой, что 5+y=5
y(y 2 y 1 0)
Для всех y выполняется предикат
y(y 2 y 1 0)
Существует y, что ….
x(x x)
Для некоторого х, справедливо
3
2

11. Формулы логики предикатов

В логике предикатов имеется следующая символика:
Символы p, q, r, …- переменные высказывания, принимающие
два значения: 1- истина, 0 – ложь.
Предметные переменные – x, y, z, …, которые пробегают
значения из некоторого множества М;
x0, y0, z0 – предметные константы, т. е. значения предметных
переменных.
P(·), Q(·), F(·), … - одноместные предикатные переменные;
Q(·,·,…,·), R(·,·, …,·) – n-местные предикатные переменные.
P0(·), Q0(·,·, …,·) – символы постоянных предикатов.
Символы логических операций: , .
Символы кванторных операций: х, х.
Вспомогательные символы: скобки, запятые.

12. Формулы логики предикатов

Предметная переменная называется свободной, если она
не следует непосредственно за квантором и не входит в
область действия квантора по этой переменной, все другие
переменные,
входящие
в
формулу,
называются
связанными.
y z (P(x,y) P(y,z))
Формулой логики предикатов являются:
Каждая предикатная буква и предикатная буква со
следующими за ней в скобках предметными переменными.
Выражения вида F G, F G, G, F G, F G, (y)F,
(y)G, где F и G – формулы логики предикатов, переменная
у М.

13. Формулы логики предикатов

Каждое высказывание как переменное, так
постоянное, является формулой (элементарной).
и
Если F(·,·, …,·) – n-местная предикатная переменная
или постоянный предикат, а x1, x2,…, xn– предметные
переменные или предметные постоянные (не
обязательно все различные), то F(x1, x2,…, xn) есть
формула. Такая формула называется элементарной, в
ней предметные переменные являются свободными, не
связанными кванторами.

14. Формулы логики предикатов

Если А и В – формулы, причем, такие, что одна и та же
предметная переменная не является в одной из них
связанной, а в другой – свободной, то слова A B,
A B, A B есть формулы. В этих формулах те
переменные, которые в исходных формулах были
свободны, являются свободными, а те, которые были
связанными, являются связанными.
Если А – формула, то A– формула, и характер
предметных переменных при переходе от формулы А к
формуле A не меняется.

15. Формулы логики предикатов

Если А(х) – формула, в которую предметная
переменная х входит свободно, то слова xA(x) и
xA(x) являются формулами, причем, предметная
переменная входит в них связанно.
Всякое слово, отличное от тех, которые названы
формулами в предыдущих пунктах, не является
формулой.

16. Формулы логики предикатов

Например, если Р(х) и Q(x,y) – одноместный и
двухместный предикаты, а q, r – переменные
высказывания, то формулами будут, выражения:
q, P(x), P(x) Q(x , y), xP(x) xQ(x, y), (Q(x, y) q) r
0
Не является формулой, например, слово: xQ(x, y) P(x)
Здесь нарушено условие п.3, так как формулу
xQ(x,y) переменная х входит связанно, а в формулу
Р(х) переменная х входит свободно.
Из определения формулы логики предикатов ясно, что
всякая формула алгебры высказываний является
формулой логики предикатов.

17. Интерпретация формулы предикатов

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

18. Формулы исчисления предикатов

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

19. Значение формулы логики предикатов

В качестве примера рассмотрим формулу
y z (P(x, y) P(y, z))
В формуле двухместный предикат Р(x, y) определен на
множестве MхM, где M={0,1,2,…,n,…}, т.е. MхM=NхN.
В формулу входит переменный предикат P(x,y), предметные
переменные x,y,z, две из которых y и z – связанные кванторами,
а x – свободная.
Возьмем
за
конкретное
значение
предиката
P(x,y)
фиксированный предикат P0(x,y): «x переменной х придадим значение x0=5 M.
Тогда при значениях y, меньших x0=5, предикат P0(x0,y)
принимает значение “ложь”, а импликация P(x,y) P(y,z) при
всех z M принимает значение “истина”, т.е. высказывание
имеет значение “истина”.

20. Равносильные формулы логики предикатов

Определение 1.

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

21. Равносильные формулы логики предикатов

Пусть А(х) и В(х) – переменные предикаты, а С – переменное
высказывание (или формула, не содержащая х). Тогда имеют
место следующие равносильности:

22. Равносильные формулы логики предикатов

Пример
Предикат Мать(x,y) означает, что x является матерью для y.
Тогда y xМать(x,y) означает, что у каждого человека есть
мать, - истинное утверждение.
x yМать(x,y) означает, что существует мать всех людей, что
является другим утверждением, истинность которого зависит от
множества значений, которые могут принимать y: если это
множество братьев и сестер, то оно истинно, а в противном
случае оно ложно.
Таким образом, перестановка кванторов всеобщности и
существования может изменить смысл и значение выражения.

23. Законы логических операций (общезначимые формулы логики предикатов)

24. Упражнение

Найти отрицание следующих формул

25. Упражнение

и
Упражнение
Доказать равносильность
x(A(x) B(x)) xA(x) xB(x)
Пусть предикаты А(х) и В(х) тождественно ложны. Тогда будет
ложным и предикат A(x) B(x)
x(A(x) B(x))
При этом будут ложными высказывания
xA(x) xB(x)
Пусть хотя бы один из предикатов (например, А(х)) не
тождественно ложный. Тогда будет не тождественно ложным и
предикат A(x) B(x)
При этом будут истинными высказывания xA(x) x(A(x) B(x))
Значит, будут истинными и исходные формулы
Следовательно: x(A(x) B(x)) xA(x) xB(x)

26.

Самостоятельно
Для более подробного изучения материала
самостоятельно читаем:
УЧЕБНИК: «Математическая логика и теория
алгоритмов»,
автор Игошин В.И.
Страницы 157-164
Страницы 165-178
Страницы 178-183

27.

Домашнее задание
Доказать равносильность
C xA(x) x(C A(x))
Доказать что формула является общезначимой
A V (P(x) Q(x)) xP(x) xQ(x)
Доказать что формула является противоречивой
A x((F (x) F (x)) (F (x) F (x)))

Советуем почитать

• Ваша каша не разваривается или пригорает?
• К чему снится падающий самолет?
• Оладьи из кабачков, рецепты оладьев из кабачков приготовленных быстро и вкусно
• Ледяной поход Возглавил первый кубанский ледяной поход