Тема 4. Кванторная логика.

или логика предикатов является расширением пропозициональной логики путем изучения операций ", $. Из определения этих операций следует, что значения высказываний "хp, $хp, понимаются соответственно как конъюнкция p₁Ùp₂Ùp₃Ù… и дизъюнкция p₁Úp₂Úp₃Ú… значений высказывания p для всевозможных значений переменной х. Высказывание p называется кванторологически истинным при любой интерпретации.

Из определений следует, что тавттологически истинное высказывание является кванторологически истинным. Обратное вообще говоря не верно: высказывание "хpÞ$хp является кванторологически истинным, но не является тавтологически истинным.

 

Истинностная таблица.

" х p	$ х p	" х p Þ $ х p
Л	Л	И
Л	И	И
И	Л	Л
И	И	И

 

Истинностная схема.

p 1, p 2, p 3 …	" х p  p1 Ù p2 Ù p3 Ù …	$ х p p1 Ú p2 Ú p3 Ú …	" х p Þ $ х p
ЛЛЛ…	Л	Л	И
ЛЛЛ…	Л	И	И
………	…	…	…
ИИИ…	И	И	И

 

Высказывание q называется кванторологическим следствием (из) высказываний р₁,…,p_n, если p является истинным в любой интерпретации, в которой истинными являются p₁,…,p_n.

Вхождением переменной c в высказывание p называется связанным, если оно является вхождением в некоторое подвысказывание вида "х(q) или вида $х(q); в противном случае это вхождение называется свободным.

Например, первое и второе вхождения c₁ в высказывание

((g (c₁))Ù(g (c₁, c₂)))Þ($ c₁(g (c₁)))

являются свободными, а третье и четвертое – связанными.

Через р{х, а} обозначается результат подстановки терма, а вместо всех свободных вхождений переменной х в высказывание р, причем, если при такой подстановке все вхождения переменных из а остаются свободными, то терм а называется допустимым заменителем для х в р. Например, терм f (c₅) является допустимым заменителем для c₆ в высказывании g ((c₅, (c₆), и не является

допустимым заменителем для c₆ в высказывании $c₅ (g (c₅, c₆)). Высказывание р называется замкнутым (открытым), если оно не имеет свободных (связанных) вхождений переменных.

Теорема о всезначности переменной: р = И тттк "хр = И

Теорема об отрицании обобщения и подтверждения:

Ø"хр равносильно $хØр

Ø$хр равносильно "хØр

Теорема о взаимоисключении кванторов:

"хр равносильно Ø$хØр

$хр равносильно Ø"хØр

Теорема о перестановочности кванторов:

"х"ур равносильно "у"хр

$х$ур равносильно $у$хр

Типовые кванторы. Запись "_qхр обозначает высказывание "х(qÞр), а запись $_qхр обозначает высказывание $х(qÙр).

Теорема о равносильной замене: пусть q есть результат замены в высказывании р какого-либо вхождения подвысказывания r₁ на высказывание r₂; тогда если r₁ и r₂ равносильны, то р и q тоже равносильны.

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

Теорема о позитивной форме: если отрицания предикатных компонент высказывания р имеют равносильные себе предикаты, то р равносильно некоторому позитивному высказыванию q; высказывание q можно построить с помощью теоремы о равносильной замене, теорем об исключении операций Þ, Û и теорем об отрицании для операций ", $, Ø, Ù, Ú.

Пример построения позитивной формы отрицания высказывания: «для каждого положительного числа е существует положительное число d т.ч. для каждого числа х из х<d следует, что х<е или х£1».

Ø"е$d"х(х<dÞх<еÚх£1 = $e"d$хØ(х<dÞх<eÚх£1) = $e"d$хØ(Øх<dÚх<eÚх£1) = $e"d$х(х<dÙØх<eÙØх£1) = $e"d$х(х<dÙх³eÙх>1) = «существует положительное число е т.ч. для каждого положительного числа d существует число х т.ч. х<d и х³e и х>1».

Теорема о выводе в логике предикатов: нижеследующие шесть правил преобразования высказываний образуют достаточный набор правил вывода в логике предикатов т.е. р₀ является кванторологическим следствием из p₁,…,p_n тттк р₀ может быть получено из р₁,…,р_n с помощью этих шести правил:

D t – правило тавтологии

D s, s Þ r, r – правило отделения

D"хрÞp{x, a} – правило обобщения

D p{x, a} Þ$ xp – правило подтверждения

D qÞr, q Þ"хr – правило общевнесения

D rÞq, $ xrÞq – правило сущевнесения

где t есть тавтология, q не имеет свободных вхождений x, терм а является допустимым заменителем для х в р. Теорема не исключает случай n = 0.

⇐ Предыдущая12345Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: