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

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

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

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

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

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

26.

27.

В логике предикатов рассматриваются две операции, которыё превращают одноместный предикат в высказывание, для этого используются специальные слова, которые ставят перед предикатами. В логике их называют кванторами.

Различают два вида кванторов:

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

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

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

Пусть имеется предикат Р(х) определенный на множестве М

Символ называют квантором всеобщности (общности). Это перевернутая первая буква английского слова All- все. Читают «все», «каждый», «любой», «всякий». Переменную х в предикате Р(х) называют свободной (ей можно придавать различные значения из М), в высказывании же х называют связанной квантором всеобщности.

Пример №1: Р(х) – «Простое число х нечетно»

Добавим квантор общности – «Всякое простое число х нечетно» - ложное высказывание.

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

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

Пусть P(x) -предикат определенный на множестве М. Под выражением понимают высказывание , которое является истинным, если существует элемент , для которого P(x) истинно, и ложным – в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение звучит так: “Существует x, при котором P(x) истинно.” Символ называют квантором существования. В высказывании переменная x связана этим квантором (на нее навешен квантор).

(Читают: «Существует такое х из М, при котором Р от х истинно»)

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

Пример №2: Р(х) «Число х кратно 5»

Любое натуральное число кратно 5»

Каждое натуральное число кратно 5» ложные высказывания

Все натуральные числа кратны 5»

Существует натуральное число кратно 5

Найдется натуральное число кратно 5 истинные высказывания

Хотя бы одно натуральное число кратно 5

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

Для построения отрицаний с кванторами надо:

1) квантор общности заменить на квантор существования, а квантор существования – на квантор общности;

2) предикат заменить его отрицанием.

Таким образом, справедливы формулы:

Отрицание предложения записывать как , а отрицание предложения – как . Очевидно, что предложение имеет тот же смысл, а следовательно, то же значение истинности, что и предложение , а предложение – тот же смысл, что . Иначе говоря, равносильно ; равносильно .

П р и м е р №3. Построить отрицание высказывания «некоторые двузначные числа делятся на 12».

Р е ш е н и е. Заменим квантор существования (он выражен словом «некоторые») на квантор общности «все» и построим отрицание предложения, стоящего после слова «некоторые», поставив частицу «не» перед глаголом. Получим высказывание «Все двузначные числа не делятся на 12».

П р и м е р №4. Сформулировать отрицание высказывания «В каждом классе хотя бы один ученик не справился с контрольной работой».

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

Оператор, с помощью которого о к.-л. отдельном объекте преобразуется в высказывание о совокупности (множестве) таких объектов.
В логике используется два основных К.: К. общности, «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 сколько) символ, используемый для обозначения некоторых операций математической логики, одновременно логическая операция, дающая количественную характеристику области предметов, к которым относится выражение, получаемое в… … Начала современного естествознания

Кроме известных нам логических операций для предикатов вводятся две новые: операция навешивания кванторов существования и общности.

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

Высказывание «существует х » (для некоторых х , хотя бы для одного х, найдется такое х ) называется квантором существования и обозначается х.

Высказывание «существует одно и только одно х » (для единственного значения х ) называется квантором единственности : ! х.

Например: «Все кустарники являются растениями». Это высказывание содержит квантор общности («все»). Высказывание «существуют числа, кратные 5 » содержит квантор существования («существуют»).

Для того чтобы получить высказывание из многоместного предиката, надо связать кванторами каждую переменную. Например, если Р(х; у) - двухместный предикат, то (хХ) (уY) Р(х; у) - высказывание.

Если не каждая переменная связывается квантором, то получается не высказывание, а предикат, зависящий от той переменой, которая не связана квантором. Так, если перед предикатом Р(х; у) поставить квантор у, то получим предикат (уY) Р(х; у) , зависящий от переменной х.

Выясним, какие из следующих предложений являются высказываниями, а какие предикатами: а) найдется такое х, что х+ у = 2;

b) для любых х и у имеет место равенство х + у = у + х.

Решение : Выявим логическую структуру данных предложений.

а) Предложение «Найдется такое х, что х + у = 2 » можно записать в виде (хR) х + у = 2. Так как квантором связана только переменная х, то рассматриваемое предложение с двумя переменными является предикатом.

b) Предложение «для любых х и у имеет место х + у = у + х » можно записать в виде: (хR) (уR) х + у = у + х, где обе переменные являются связанными. Следовательно, данное предложение является высказыванием.

Если какое-либо предметное переменное в формуле не связано квантором, то его называют свободным переменным.

Например: (х) ху=ух. Здесь переменное у не связано каким-либо квантором, поэтому оно свободно. От него не зависит истинность данного высказывания.

Кванторы (х) (х ) называются двойственными друг другу.

Одноименные кванторы можно менять местами, что не влияет на истинность высказывания.

Например: (у) (х) х + у = 5. Это утверждение имеет тот же смысл, что и (х) (у) х + у = 5.

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

Например: (х) (у) х<у , т.е. для всякого числа х существует большее число у - истинное высказывание.

Поменяем местами кванторы: (х) (у) x cуществует число у большее любого числа х - ложное высказывание.