Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Шпоры по матлогике - файл Шпоры по матлогике(2 курс).doc


Шпоры по матлогике
скачать (24.1 kb.)

Доступные файлы (1):

Шпоры по матлогике(2 курс).doc106kb.13.01.2005 04:36скачать

содержание
Загрузка...

Шпоры по матлогике(2 курс).doc

Реклама MarketGid:
Загрузка...
Определение высказывания:

Всякое предложение, о котором можно определённо сказать истинно оно или ложно называется высказыванием
Конъюнкцией двух высказываний А и В, называется высказывание А&В которое истинно тогда и только тогда, когда истинны одновременно оба высказывания (союз и)
Дизъюнкцией двух высказываний А и В называется высказывание А\/В, которое ложно тогда и только тогда, когда ложны одновременно оба высказывания (союз или)
Импликацией двух высказываний А и В, называется высказывание А-В, которое ложно тогда и только тогда, когда высказывание А истинно а В ложно. В обычной речи если..то
Эквивалентностью двух высказываний А и В называется высказывание А↔В, которое истинно тогда и только тогда, когда оба данных высказывания имеют одинаковые значения, т.е. либо оба истинны, либо оба ложны (тогда и только тогда)
Отрицанием высказывания А называется высказывание А\, которое истинно тогда и только тогда, когда А ложно
Формулы: 1.переменные высказывания X,Y,Z,Xi,Yi,Zi,i € N, являются формулами

2. Если F1 и F2 –формулы, то выражения Fi\, I=1,2, (F1&F2),(F1\/F2),(F1→F2),(F1↔F2) также являются формулами

3. Никаких других формул нет

Замечание1: для всякого выражения в алфавите {X,Y,Z,Xi,Yi,Zi, I € N, ‾ ,&,\/, →,↔, ( , )}, используя пункты 1, 2 определения, очевидно, можно выяснить, является оно формулой или нет.

Замечание 2: Во всякой формуле число открывающихся скобок очевидно равно числу закрывающихся скобок. Скобки, учавствующие в формуле, определяют порядок логических операций фигурирующих в выражении формулы.
^ Интерпретация формулы - высказывание, получаемое из формулы подставлением конкр. Высказываний вместо переменных

Классификация формул
Формула F(X1,X2,…,Xn) называется выполнимой (опровержимой), если существует её истинная (ложная) интерпретация.
Формула F(X1,X2,…,Xn) называется тавтологией (противоречием), если любая её интерпретация истинна (ложна). Если тавт. то ╞F(X1,X2,…,Xn)
Равносильность

Две формулы F(X1,X2,…,Xn),G(X1,X2,…,Xn), будем называть равносильными, если для любых конкретных высказываний А1,А2,….,Аn их интерпретации совпадают, т.е. F(А1,А2,…,Аn)=G(A1,A2,…An)

Типичные равносильности


  1. (X&Y)\≡(X\)\/(Y\)

  2. (X\/Y)\≡(X\)&(Y\)

  3. X&Y≡Y&X, X\/Y≡Y\/X

  4. X&(Y&Z)≡(X&Y)&Z, X\/(Y\/Z)≡(X\/Y)\/Z

  5. X&X≡X, X\/X≡X

  6. X&0≡0, X&1≡X, X\/0≡X, X\/1≡1

  7. X\/(Y&Z)≡(X\/Y)&(X\/Z), X&(Y\/Z)≡(X&Y)\/(X&Z)

  8. X\/(X&Y)≡X, X&(X\/Y)≡X

  9. X→Y≡(X\)\/Y

  10. X↔Y≡(X→Y)&(Y→X)≡((X\)\/Y)&((Y\)\/X)

  11. X&(X\)≡0, X\/(X\)≡1


Лемма (о замене) Пусть F(X1,…,Xi-1,Xi,Xi+1,…,Xn) – произвольная формула и G(Y1,Y2,…,Ys)≡H(Y1,Y2,…,Ys). Тогда F(X1,…,Xi-1, G(Y1,Y2,…,Ys),Xi+1,…,Xn) ≡ F(X1,…,Xi-1, H(Y1,Y2,…,Ys),Xi+1,…,Xn)
^ Нормальные формы
Формула K=Xm1i1&Xm2i2&….&Xmkik, где Xa={x,если a=1,(x\), если a=0} называется конъюнктивным одночленом
Дизъюнкция конъюнктивных одночленов К1\/К2…\/Km называется дизъюнктивной нормальной формулой.
Формула D=Xm1i1&Xm2i2&….&Xmkik называется дизъюнктивным одночленом
Конъюнкция дизъюнктивных одночленов D1&D2…&Dm называется к.н.ф.
Замечание: в определениях одночленов никаких ограничений на переменные в них нет
Теорема 1 : Любая формула равносильными преобразованиями может быть приведена к д.н.ф.(к.н.ф.)
Из определений д.н.ф. и к.н.ф. видно, что в любой д.н.ф., к.н.ф. участвуют только операции вида ‾,\/,&, причём отрицание может встречаться только над переменными. Отсюда равносильными преобразованиями ф-лы F(X1,X2,…,Xn) привод. Её к к.н.ф., д.н.ф. явл-ся :

  1. X→Y≡(X\)\/Y, X↔Y≡((X\)\/Y)&((Y\)\/X)

  2. (X&Y)\≡(X\)\/(Y\), (X\/Y)\≡(X\)&(Y\)

  3. X&(Y\/Z)≡X&Y\/X&Z (X\/(Y&Z)≡(X\/Y)&(X\/Z))

Осуществл. в приводим. Посл-сти (3 п. к к.н.ф.)
Теорема 2: Формула F(X1,X2,…,Xn) явл-ся тавтологией (противоречием) тогда и только тогда, когда её к.н.ф.(д.н.ф.) в каждом дизъюнктивном(конъюнктивном) одночлене некоторая переменная встреч. Со своим отрицанием.
Кон. Одночлен назыв. Совершенным если в нём каждая переменная встречается один раз с отрицанием или без, т.е. :

Xm11&Xm22&…&Xmnn
Диз. Одночлен назыв совершенным (то же):

Xm11\/Xm22\/…\/Xmnn
^ Диз. Норм. Ф-ла назыв. Соверш., если в ней все кон. Одночлены совершенны.
СКНФ-аналогично

Логическое следование: Формула G(x1,x2,…,xn) называется логическим следствием формулы F(x1,x2,…,xn), если для любых конкрет. Высказываний А12,…,Аn из истинности F(A1,…,An) следует истинность G(А12,…,Аn)

Обознач.:F├ G
Теорема : F├ G ↔├ F→G
Формула G назыв. Логич. Следствием формул F1,F2….Fm, если для любых конкретных высказываний A1,A2,…,An из одновременной истинности

формул F1,F2….Fm (F1(A1,…An)=1,…,Fm(A1,…,An)=1) истинность формулы G(G(A1,..,An)=1) :

F1,F2….Fm ├ G( ф-лы посылки, G- следствие)
Теорема: Условия

  1. F1,F2….Fm ├ G

  2. F1&F2&…&Fm├ G

3. ├F1&F2&…&Fm→G

Являются эквивалентными
Теорема: Для того чтобы ф-ла G не являющаяся тавталогией была логич следствием ф-л F1,F2….Fm из к-рых по крайней мере одна не явл-ся тавтологией, необходимо и достаточно, чтобы в СКНФ ф-лы G все диз одночлены были из СКНФ ф-лы F1&F2&…&Fm
^ Правила вывода : Если в процессе дедуктивного рассуждения некоторое утв. G выводится из утв-ий дуктивного рассуждения некоторое утв. ыми. дена к д.н.ф.(

F1,F2….Fm , то говорят, что справедливо правило вывода равносильно F1,F2….Fm ├ G


^ Осн. Правила. Вывода:
правило заключения
правило цепного заключения
з-н контрпозиции



правила разъединения и объединения посылок
законы Моргана



Правило сведения к абсурду



Правила удаления и введения конъюнкции
^ ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ (АЛ) И ИХ ПРИЛОЖЕНИЯ


Определение 1. Функция алгебры логики f(x1, x2, …, xn) от n переменных есть отображение n-ой декартовой степени множества {0,1} в множество {0,1}, т.е.

{0,1}nf->{0,1}
Опр2. Говорят функция алгебры логики f(x1,…,xi,…,xn) несущественно зависит от переменной xi, если для любых (1, 2,…, i-1,0, i+1,…, n), (1,…, i-1,1, i+1,…, n) из области определения f(x1,x2,…,xn) имеет место f(1,…, i-1,0, i+1,…, n)=f(1,…, i-1,1, i+1,…, n)
Опр3. Если f(x1,x2,…,xn), g1(y11,y12,…,y1m), g2(y21,y22,…,y2m2), … , gn(yn1, yn2,…,ynmn) функции алгебры логики соответственно от n, m1, m2,…, mn переменных, то функция f(g1(y11,…,y1m), g2(y21,…,y2m2),…, gn(yn1, yn2,…,ynmn)) называется суперпозицией функций g1(y11,…,y1m), g2(y21,…,y2m2),…, gn(yn1, yn2,…,ynmn) в функцию f(x1,x2,…,xn).
Опр4. Многжество функций алгебры логики R называется замкнутым, если любая суперпозиция ф-ций из множества R принадлежит множеству R.
Опр5. Система ф-ций А.Л. S={f1,f2,…,fs,…} называется полной, если для любой ф-ции АЛ f{x1,x2,…,xn) найдётся суперпозиция ф-ций из S совпадающая с f(x1,x2,…,xn).
Опр6ю Ф-я f(x1,x2,…,xn) АЛ принадлежит классу ф-ций T0, сохраняющих константу ноль, тогда и только тогда, когда f(0,0,…,0)=0.
Опр7. Ф-я АЛ принадлежит классу ф-ций T1, сохраняющих константу 1, тогда и только тогда, когда f(1,1,…,1)=1.
Опр8. Ф-я f*(x1,x2,…,xn) Называется двойственной к ф-ции f(x1,x2,…,xn) , если для любого набора (1, 2,…, n)

F*(1, 2,…, n)=‾f‾ (‾1‾,‾2‾, …,‾n‾).
Опр9. Ф-я f(x1,x2,…,xn) принадлежит классу самодвойственых ф-ций S тогда и только тогда, когда

F*(x1,x2,…,xn)=f(x1,x2,…,xn),

Т.е. когда двойственная ф-я совпадает с ней самой.
Опр10. Ф-я f(x1,x2,…,xn) АЛ принадлежит классу монотонных функций АЛ M тогда и только тогда, когда для любых двух наборов ‾‾=(1,2,…,n), ‾β‾= (β1, β2,…, βn) таких, что ‾‾ ≤ ‾β‾ имеет место f(‾‾)≤ f(‾β‾).
Опр11. Ф-я f(x1,x2,…,xn) АЛ принадлежит классу линейных ф-ций АЛ L тогда и только тогда, когда

F(x1,x2,…,xn) = a0+a1x1+a2x2+…+anxn, где ai Є {0,1}, а + есть сумма по модулю 2.
^ ЛОГИКА ПРЕДИКАТОВ
Опр1. n-местным предикатом, заданным на множестах M1,M2,…,Mn, называется выражение, содержащее n переменных x1, x2, …, xn, которое становится высказыванием при подстановке вместо этих переменных элементов a1,a2,..,an из множества M1,M2,…,Mn соответственно.

Предикаты обозначаются как P(x1,x2,…,xn) и представляют собой отображения P: M1xM2x…xMn {0,1}. То есть, упорядоченному набору эл-тов (a1,a2,…,an) из множеств M1x…xMn ставится в соответствие один из элементов множества {0,1}, причём 0, если P(a1,…,an) – ложное высказывние и 1, если истинное. Местностью предиката называется число различных аргументов, от которых зависит предикат.
Опр2. ^ Множеством истинности рпедиката называется совокупность таких упорядоченных наборов элементов (a1,a2,…,an) из M1xM2x…xMn, для которых высказывание P(a1,…,an) является истинным. Обозначение P+={(a1,a2,…,an) : λ(P(a1,a2,…,an))=1}.
Опр3. Два предиката P(x1,x2,…,xn) и Q(x1,x2,…,xn) заданные на одном и тои же множестве M1xM2x…xMn называются равносильными, если оба предиката принимают истинные значения на одних и тех же наборах (a1,a2,…,an) из множества M1xM2x…xMn, т.е. если P+= Q+. Предикат Q(x1,x2,…,xn) , заданный на множестве M1xM2x…xMn, называется следствием предиката P(a1,…,an), заданного на том же множестве, если он становится истинныи высказыванием при всех значениях переменных x1,x2,…,xn из соответствующих множеств M1xM2x…xMn, при которых истинным высказыванием становится предикат P(x1,x2,…,xn), т.е. если P+ Q+.
Опр4. Отрицанием предиката P(x1,x2,…,xn) , заданного на множестве M1xM2x…xMn, называется новый предикат, ‾P‾ (x1,x2,…,xn) , заданный на том же множестве, который становится истинным высказыванием при таких значениях (a1,a2,…,an) из множества M1xM2x…xMn, при которых P(a1,a2,…,an) является ложным высказыванием, если P(a1,a2,…,an).
Опр5. Конъюнкцией двух n-местных предикатов P(x1,x2,…,xn) и Q(x1,x2,…,xn) заданных на множестве M1xM2x…xMn называется новый n-местный предикат P(x1,x2,…,xn) ^Q(x1,x2,…,xn), который становится истинным высказыванием только для таких элементов (a1,a2,…,an) из множества M1xM2x…xMn, для которых P(x1,x2,…,xn) и Q(x1,x2,…,xn) являются истинными высказываниями.
Опр6. Дизъюнкцией двух n-местных предикатов P(x1,x2,…,xn) и Q(x1,x2,…,xn) заданных на множестве M1xM2x…xMn называется новый n-местный предикат P(x1,x2,…,xn) vQ(x1,x2,…,xn), который становится ложным высказыванием только для таких элементов (a1,a2,…,an) из множества M1xM2x…xMn, для которых P(x1,x2,…,xn) и Q(x1,x2,…,xn) являются ложными высказываниями, а для остальных элементов – истинным высказыванием.
Опр7. Импликацией двух n-местных предикатов P(x1,x2,…,xn) и Q(x1,x2,…,xn) заданных на множестве M1xM2x…xMn называется новый n-местный предикат P(x1,x2,…,xn) Q(x1,x2,…,xn), который становится ложным высказыванием только для таких элементов (a1,a2,…,an) из множества M1xM2x…xMn, для которых P(x1,x2,…,xn) и Q(x1,x2,…,xn) являются истинными высказываниями, а Q(x1,x2,…,xn) является ложным. В остальных случаях – истинным.
Опр8. Эквивалентностью двух n-местных предикатов P(x1,x2,…,xn) и Q(x1,x2,…,xn) заданных на множестве M1xM2x…xMn называется новый n-местный предикат P(x1,x2,…,xn) > Q(x1,x2,…,xn), который становится истинным высказыванием только для таких элементов (a1,a2,…,an) из множества M1xM2x…xMn, для которых высказывания P(x1,x2,…,xn) и Q(x1,x2,…,xn) либо одновременно являются истинными , либо ложными. В остальных случаях – ложным.
Если предикаты P(x1,x2,…,xn) и Q(y1,y2,…,ym) заданы на разных множествах, то в результате применения операций конъюнкции, дизъюнкции, импликации и эквивалентности к этим предикатам, получим (n+m) местный предикат.
Теоретико-множественный смысл предикатов.

При определении множества истинности предиката, составленого из нескольких предикатов при помощи логических связок, можно воспользоваться соотношениями для их множеств истинности. Для двух n-местных предикатов P(x1,x2,…,xn) и Q(x1,x2,…,xn) заданных на множестве M1xM2x…xMn, верны следующие соотношения для их множеств истинности:

1) множество истинности отрицания предиката P равно дополнению множества истинности этого предиката, т.е. (‾P‾)+=(‾ P+ ‾)

2) Множество истинности конъюнкции двух предикатов P и Q равно пересечению множеств истинности P+ и Q+, т.е. (P^Q) += P+∩ Q+,

3) множество истинности дизъюнкции двух предикатов P и Q равно объединению множеств истинности P+ и Q+,т.е. (PvQ) += P+ UQ+,

4) множество истинности импликации двух предикатов P и Q равно (PQ) +=(‾P‾)+ UQ+,

5) множество истинности эквивалентности двух предикатов P и Q равно

(P>Q) +=((‾P‾)+ UQ+)∩((‾Q‾)+ UP+)
Опр9. Предикат P(x1,x2,…,xn), заданный на множестве M1xM2x…xMn, называется тождественно истинным, если для всех элементов (a1,a2,..,an) из множества M1xM2x…xMn высказывания P(a1,a2,…,an) будут истинными и тождественно ложным, если для всех элементов (a1,a2,..,an) из множества M1xM2x…xMn высказывания P(a1,a2,…,an) будут ложными. Предикат P(x1,x2,…,xn), заданный на множестве M1xM2x…xMn, называется выполнимым, если существует хотя бы один элемент ai из множества M1xM2x…xMn, для которого высказывание P(a1,a2,…,an) будет истинным, и опровержимым, если хотя бы для одного элемента ai из множества M1xM2x…xMn высказывание P(a1,a2,…,an) будет ложным.

В соответствии с классификацией предикатов истинность нульместных предикатов, содержащих кванторы, можно определить следующим образом. Высказывание x P(x) будет истинным, если предикат P(x) является тождественно истинным предикатом. В противном случае – ложным. Высказывание x P(x) будет истинным, если предикат P(x) является выполнимым, и будет ложным в противном случае.
Формулы логики предикатов.

Опр10. Формулами ЛП являются:

  1. предметные переменные: x,y,z, xi, yi, xi,… (i Є N);

  2. нульместные предикатные переменные P,Q,R,Pi,Qi,Ri, (i Є N);

  3. любой n-местный предикат P(x1,x2,…,xn), Q(x1,x2,…,xn), R(x1,x2,…,xn),…;

  4. если F, G - формулы, не содержащие предметных переменных, которые связаны квантором в одной формуле и свободны в другой, то выражения (‾F‾), (FG), (FG), (FG), (FG) также будут формулами;

  5. если F формула, а x - предметная переменная, входящая свободно в F, то выражения

x F(x) и x F(x) также будут формулами;

6) других формул нет.

Из определения формулы ЛП следует, что все формулы АВ являются также формулами ЛП.
^ Равносильность формул ЛП.

Опр11. Две формулы F и G называются равносильными, если при подстановке в эти формулы вместо предикатных, а вместо предметных переменных конкретных предикатов, а вместо предметных переменных конкретных элементов, эти формулы преобразуются в высказывания с одинаковыми логическими значениями, то есть, либо оба в истинные высказывания, либо оба в ложные.
Опр12. Формула F ЛП называется выполнимой (опровержимой) на множестве М, если можно найти такие конкретные предикаты, заданные на том же множестве, при подстановке которых вместо предикатных переменных, она преобразуется в выполнимый (опровержимый) предикат.. Формула ЛП называется тождественно истинной (тождественно ложной) на множестве М, если при подстановке вместо предикатных переменных любых конкретных предикатов, заданных на этом же множестве, она преобразуется в тождественно истинный (тождественно ложный) предикат. Формула ЛА называется тавтологией (противоречием), если при подстановке вместо предикатных переменных любых конкретных предикатов, заданных на любом множестве, она преобразуется в тождественно истинный (тождественно ложный) предикат. Критерием равносильности формул является тавтологичность формулы (FG).
Опр13. Формула F’, равносильная F , называется её приведённой нормальной формой, если F’ из логических связок содержит тоько отрицание, конъюнкцию и дизъюнкцию, а отрицание только над переменными. Предварённой нормальной формой формулы F называется такая её приведённая форма, в которой все кванторы вынесены в начало формулы, а область действия каждого квантора распространяется до конца формулы

Одной из задач классификации формул является проблема разрешимости, которая состоит в следующем. Необходимо найти алгоритм, при помощи которого для произвольной формулы ЛП можно определить, будет она тавтологией или нет. В отличие от АВ, для формул ЛП общего алгоритма не существует. То есть, проблема разрешимости имеет отрицательное решение. Несмотря на отсуствие алгоритма в общем случае, в некоторых частных случаях такой алгоритм существует. Например, для формул, содержащих только одноместные предикаты.
Опр14. Формула H называется логическим следствием формул F1, F2, …,Fn, если при подстановке в формулы F1, F2,…,Fn, H вместопредикатных переменных конкретных предикатов, вместо предметных переменных конкретных элементов будут истинными полученные в результате высказывания F1, F2,…,Fn, то истинным должно быть также высказывание H.
Будем считать что аксиоматическая теория Th задана если выполнены след. условия:

  1. Задано некоторое множество символов теории Th . Причём конечные последовательности символов называются выражениями теории Th.

  2. определено некоторое подмножество выражений называемых формулами

  3. выделено некоторое подмножество формул называемых аксиомами теории Th.

  4. Имеется некоторое множество правил, которые позволяют из одних формул теории Th получать другие.


Выводом в Th называется посл-сть формул A1,….,An такая, что для любого I формула Ai есть либо аксиома теории Т, либо непосредственное следствие каких-либо предыдущих формул по одному из правил вывода
Формула А теории Th называется теоремой (или выводимой формулой ) если существует вывод в Th, в котором последней формулой явл-ся ф-ла А
Формула А называется следствием множества формул F в Th тогда и только тогда когда существует такая посл-сть формул A1…An, что An cовпадает c А и для любого I Ai есть либо аксиома, либо элемент F, либо непосредственное следствие некоторых предыдущих формул. Эл-ты F назыв. гипотезами вывода
^ Аксиоматическая теория L


  1. Символами L являются ‾, , (,), и буквы латинского алфавита с целыми положительными числами в качестве индексов. Символы ‾,  называются логическими связками, а буквы лат. алфавита с индексами – пропозициональными буквами.

  2. Все пропозициональные буквы суть формулы. Если А, В – есть формулы, то ‾А‾ и АВ – тоже есть формулы.

  3. Каковы бы ни были формулы А, В, С теории L, следующие формулы суть аксиомы L:

(A1) (A(BA));

(A2) (A(BC))((AB)(AC));

^ (A3) (‾B‾‾A‾)((‾B‾A)B).

  1. Единственными правилами вывода служат правило подстановки и правило заключения (или modus ponens, или сокращённо МР).

^ Правило подстановки заключается в следующем. Пусть F – формула, содержащая букву А. Тогда, если F – выводимая формула, то, заменив в ней букву А всюду, где она входит, произвольной фориулой G, мы также получим выводимую формулу. Согласно правилу заключения, если FG и F – выводимые формулы, то F – также выводимая формула.
Опр5. ^ Аксиоматическая теория называется непротиворечивой, если ни для какого утверждения А, сформулированного в терминах этой теории, само утверждение А и его отрицание ‾А‾ не могут быть теоремами данной теории. Если длянекоторого утверждения А теории оба утверждения А и ‾А‾ - теоремы этой теории, то аксиоматическая теория называется противоречивой.

В противоречивой аксиоматической теории любая формула является теоремой.
Опр6. ^ Аксиоматическая теория называется разрешимой, если существует алгоритм, позволяющий для любой формулы этой теории ответить на вопрос, будет или нет эта формула теоремой этой теории.


Скачать файл (24.1 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru