Тема 4. Кванторная логика.
или логика предикатов является расширением пропозициональной логики путем изучения операций ", $. Из определения этих операций следует, что значения высказываний "хp, $хp, понимаются соответственно как конъюнкция p1Ùp2Ùp3Ù… и дизъюнкция p1Úp2Úp3Ú… значений высказывания p для всевозможных значений переменной х. Высказывание p называется кванторологически истинным при любой интерпретации. Из определений следует, что тавттологически истинное высказывание является кванторологически истинным. Обратное вообще говоря не верно: высказывание "хpÞ$хp является кванторологически истинным, но не является тавтологически истинным.
Истинностная таблица.
Истинностная схема.
Высказывание q называется кванторологическим следствием (из) высказываний р1,…,pn, если p является истинным в любой интерпретации, в которой истинными являются p1,…,pn. Вхождением переменной c в высказывание p называется связанным, если оно является вхождением в некоторое подвысказывание вида "х(q) или вида $х(q); в противном случае это вхождение называется свободным. Например, первое и второе вхождения c1 в высказывание ((g являются свободными, а третье и четвертое – связанными. Через р{х, а} обозначается результат подстановки терма, а вместо всех свободных вхождений переменной х в высказывание р, причем, если при такой подстановке все вхождения переменных из а остаются свободными, то терм а называется допустимым заменителем для х в р. Например, терм f
допустимым заменителем для c6 в высказывании $c5 (g Теорема о всезначности переменной: р = И тттк "хр = И Теорема об отрицании обобщения и подтверждения: Ø"хр равносильно $хØр Ø$хр равносильно "хØр Теорема о взаимоисключении кванторов: "хр равносильно Ø$хØр $хр равносильно Ø"хØр Теорема о перестановочности кванторов: "х"ур равносильно "у"хр $х$ур равносильно $у$хр Типовые кванторы. Запись "qхр обозначает высказывание "х(qÞр), а запись $qхр обозначает высказывание $х(qÙр). Теорема о равносильной замене: пусть q есть результат замены в высказывании р какого-либо вхождения подвысказывания r1 на высказывание r2; тогда если r1 и r2 равносильны, то р и 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».
Теорема о выводе в логике предикатов: нижеследующие шесть правил преобразования высказываний образуют достаточный набор правил вывода в логике предикатов т.е. р0 является кванторологическим следствием из p1,…,pn тттк р0 может быть получено из р1,…,р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.
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|