Тема 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 (c1))Ù(g (c1, c2)))Þ($ c1(g (c1))) являются свободными, а третье и четвертое – связанными. Через р{х, а} обозначается результат подстановки терма, а вместо всех свободных вхождений переменной х в высказывание р, причем, если при такой подстановке все вхождения переменных из а остаются свободными, то терм а называется допустимым заменителем для х в р. Например, терм f (c5) является допустимым заменителем для c6 в высказывании g ((c5, (c6), и не является допустимым заменителем для c6 в высказывании $c5 (g (c5, c6)). Высказывание р называется замкнутым (открытым), если оно не имеет свободных (связанных) вхождений переменных. Теорема о всезначности переменной: р = И тттк "хр = И Теорема об отрицании обобщения и подтверждения: Ø"хр равносильно $хØр Ø$хр равносильно "хØр Теорема о взаимоисключении кванторов: "хр равносильно Ø$хØр $хр равносильно Ø"хØр Теорема о перестановочности кванторов: "х"ур равносильно "у"хр $х$ур равносильно $у$хр Типовые кванторы. Запись "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-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (207)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |