МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ. Математическая логика
 Скачать 1.08 Mb.
|
Пояснения:
Утверждения:
Эти утверждения можно проиллюстрировать графически бинарным функциональным соответствием q= Мn, B, P, с помощью которого возникает высказывание , если в качестве значений хi ( i = 1…n)  B=JmP Dom P   Область истинности предикатов Ru Мn  Мn u л Говорят, что предикат является выполнимым, если Ru и Ru Мn (т.е. предикат выполняется хотя бы для одного набора значений аргументов, само соответствие сюрьективно). В том случае, если область истинности предиката Pn(x1, x2,…, xn) пуста, т.е. Ru , то говорят, что предикат является тождественно-ложным (невыполнимым), а в случае Ru Мn=Dom P предикат является тождественно-истинным (общезначимым) – он выполняется для всех наборов аргументов (такой предикат выражает закон логики)
Ru ={<в, а>, <в,c >,
Утверждение 3. Всякой алгебраической операции f: Мn M можно поставить в соответствие (n+1)-местный предикат такой, что Pn+1(x1, x2,…, xn+1) истинен, если и только если fn(a1, a2,…, an)= аn+1 Однако обратное соответствие, т.е. от (n+1)-местного предиката к n-местной функции возможно не всегда, а только при условии, чтобы для любого а1n+1аn+1 Pn+1(а1, а2,…, а1n+1 )= (т.е. предикат был бы ложным). семьи М, то в случае: КВАНТИФИКАЦИЯ ПРЕДИКАТОВ. Навешивание квантора на предикат уменьшает в нем число свободных переменных и превращает его предикат от меньшего числа переменных. Пример.  Пример.  Пример.  - высказывания, истинностное значение которых обусловлено универсумом рассмотрения М.Примечание.
хР(х)=хР(х), хР(х)=хР(х), т.е. взаимовыразимость кванторов означает, что один квантор определяет сокращенную запись другим. Именно поэтому в логике предикатов первого уровня достаточно только один из кванторов. Эквивалентные преобразования кванторных формул.
хР(х) хР(х), хР(х) хР(х). Эти эквивалентности являются обобщением законов де-Моргана. Пример. Пусть Р – сдал экзамен, а М – студент учебной группы. Тогда высказывание хР(х) ( “не все студенты группы сдали экзамен”) эквивалентно высказыванию хР(х) (“существуют студенты группы, которые не сдали экзамен”) 2) Законы коммутативности одноименных кванторов. ху Р(х, у) ухР(х,у), ху Р(х, у) ух Р(х, у). Однако, для разноименных кванторов действительна импликация: ху Р(х, у) у х Р(х, у). 3) Законы пронесения и вынесения кванторов (эквивалентности предваренных приведенных формул):
х(Р(х)Z) хP(x) )Z ZхР(х), х(Р(х)Z) хP(x) )Z ZхР(х), х(Р(х)Z) хP(x) )Z ZхР(х). Пример. х(F(x)Q(y)) H(x) Q(y)) х(Q(y)(H(x)F(x)) Q(y)х(H(x) )F(x))
х(P1(x)P2(x)) хP1(x)х P2(x), Это т.н. законы дистрибутивности квантора относительно операции и относительно . Для квантора относительно и относительно действительны соотношения (верно лишь в одну сторону): (хP1(x)хP2(x)) х(P1(x)P2(x)), х(P1(x)P2(x)) хP1(x)х P2(x). Примечание. 1) Предикатная формула, построенная только с привлечением булевых логических операций и кванторов , так, что логическая операция (обращение) встречается лишь перед символами предикатов, называются приведенной формой. Так, х P1(x)х P2(x, у) – приведенная формула, а формулы хР(х)хQ(x,y), хР(х)хQ(x,y) – не приведенные формулы (т.к. “”
Так ху( P1(x)P2(x, у)) – приведенная П.Н.Ф., а ху( P1(x)P2(x, у)) – П.Н.Ф., но не предваренная формуле. 4)Законы переименования связанных переменных: хР(х) уР(у), хР(х) уР(у). Эти равносильности означают, что переименование связанных переменных не меняет истинности высказываний. Утверждения. 1) Для любой предикатной формулы существует равносильная ей приведенная форма. 2)Для любой предикатной формулы существует эквивалентная ей П.Н.Ф. КЛАССИЧЕСКИЕ ЛОГИЧЕСКИЕ ИСЧИСЛЕНИЯ. Понятие “исчисление” является экспликацией интуитивных понятий “вывод”, “доказательство”, “оперирование”, “вычисление”. В математической логике исчисление является частным случаем формальных (дедуктивных) систем F.S. вида Ниже будем изучать классические исчисления высказываний (И.В.) и предикатов (И.П.) как гомоморфные отображения (модели) логики высказываний и логики предикатов. Цель классических И.В. и И.П. Целью И.В. и И.П. является описание кланов всех общезначимых (тождественно-истинных) формул (часто называемых тавтологиями, или законами). Метасимволика И.В. и И.П. Г- множество посылок (гипотез). Обычно Г записывают в виде Г=А1, А2,…, Аn (Г читается как “гамма”) Ф – теорема; Аi – метаформула; R(J) – множество правил вывода в исчислении; | - символ отношения дедуктивного вывода. Пример. Запись Г|Ф ( из гипотез Г дедуктивно выводима формула Ф) означает А1, А2,…, Аn |Ф, или А1, А2,…, Аn Ф Пример. Запись |А означает, что А доказуема. Пример. Запись А1, А2,…, Аn | означает, что множество посылок противоречива. Пример. |=, 1 |= 2, 1 | 2 – метавысказывания. Замечание. Специфика отношений |= и | в том, что в отличие от логических связок (отношений отрицания, конъюнкции, дизъюнкции) они реализуются не на денотатах высказываний, а на пропозициональных формулах. Построение логических исчислений. Построение (задание) исчислений качественно отличаются видом аксиоматики – конечным или бесконечным множеством аксиом. Аксиома – формула объектного языка, в рамках которого строится исчисление. Система аксиом – конечное множество аксиом. Бесконечное множество аксиом задается перечислением конечного множества схем аксиом. Схема аксиом – выражение метаязыка, представляющее бесконечное множество формул определенной структуры. КЛАССИЧЕСКОЕ И.В. Ниже рассмотрим различные И.В., отличающиеся аксиоматикой. Задание классического И.В. в Я.Л.В. будем осуществлять с привлечением схем аксиом и одного вывода. a) I1 A I2 (AB)((A) I3 (AB) ((A(BC)) (AC I4 (AB) I5 (AB)B I6 A (B (AB)) I7 A (AB) I8 B (AB) I9 (AC) ((BC) ((AB)C)) I10 Правило вывода для этой аксиоматики – правило модус-поненс (Modus ponens, m.p.), часто называемого правилом отделения: ТЕОРИЯ АЛГОРИТМОВ. Вводные положения. |