Лекция 4. Наряду с пропозициональными операциями в математической логике рассматриваются кванторы, позволяющие из данной высказывательной формы получать

Кванторы.

Наряду с пропозициональными операциями в математической логике рассматриваются кванторы, позволяющие из данной высказывательной формы получать высказывательную форму с меньшим числом параметров, в частности, из одноместной высказывательной формы — высказывание.

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

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

Отметим, что в предложениях ∀x A(x) и ∃ х А(х) переменная х не является свободной переменной: кванторы «связывают» эту переменную. Очевидно также, что кванторы можно применять и к высказывательным формам, содержащим наряду c х и другие параметры. В результате получится высказывательная форма, имеющая те же параметры, что и исходная, кроме х.

Важное значение для математической логики имеет анализ логической структуры высказываний и высказывательных форм, т.е. выявление того, каким образом данное повествовательное предложение построено из более простых предложений с помощью пропозициональных операций и кванторов. Логический анализ предложений есть своего рода искусство, практические навыки которого можно приобрести путем упражнений. Рассмотрим некоторые примеры. Высказывание «2 — простое число, а 6 — составное число», очевидно, может быть представлено в виде «2 — простое число» & «6 — составное число». Предложение «Каждое рациональное число есть действительное число» можно иначе записать так:

∀x [(х — рациональное число) ® (х — действительное число)],

а предложение «Некоторые действительные числа являются рациональными» — так:

∃ х [ (х — действительное число) & (х — рациональное число)].

Проверим, может правильнее вместо & поставить ®?

Для этого рассмотрим два варианта представления очевидно ложного высказывания: «Некоторые мнимые числа являются рациональными»

∃ х [ (х — мнимое число) & (х — рациональное число)].

∃ х [ (х — мнимое число) ® (х — рациональное число)].

Если в 1-ом варианте получаем очевидно ложное составное высказывание, то во 2-ом варианте составное высказывание – истинное, т.к. когда простое высказывание (х — рациональное число) – истинно, а такие х существуют, то предшествующее простое высказывание (х — мнимое число) – ложно. Как мы знаем, из лжи следует истина дает истину.

Таким образом правильно будет использовать &, а не ®!

Упражнение.

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

а) ∀x∃ у (х + у = 3); г) ∀x ∀ y (х + у = 3) ⊃ 7 = 11;

б) ∃ у ∀ x (х + у = 7); д) ∀a ( ∃ х (ах = 3) ≡а ≠ 0);

в) ∃ х ∃ у (х + у = 11); е) ∃a ∀ b ∃ х (х² + ах + b = 0).

Логическая эквивалентность ( обозначение: ≡). Можно обозначать ~. Хотя этот символ в некоторых книгах обозначает отрицание!

Определение. Два составных высказывания Р, Q называются логически эквивалентными Р ≡ Q, если они принимают идентичные истинностные значения для каждого набора истинностных значений своих компонент (простых высказываний).

Пример.

Доказать, что (p ∨ q) и (p ∧ q) - логически эквивалентны.

p	q	p	q	(p ∨ q)	(p∧q)	(p ∧ q)
Т	Т	F	F	F	Т	F
T	F	F	Т	Т	F	Т
F	Т	Т	F	Т	F	Т
F	F	Т	Т	Т	F	Т

ТЕОРЕМА 1 Если Р логически эквивалентно Q (Р ≡ Q), то формула (Р ↔ Q) - тавтология.

ТЕОРЕМА 2 (обратная). Если биусловие (Р ↔ Q) - тавтология, то Р и Q логически эквивалентны (Р ≡ Q).

Примечание: Если заменить биусловие на следование в любую сторону, то теорема 1 будет иметь место, а теорема 2 нет.

Дата добавления: 2014-01-20