|
Читайте также: |
Из теоремы 1 следует, что теория Тнепротиворечива.
РАЗРЕШИМОСТЬ::::
Теория Тразрешима как формальная теория.
Алгоритм, который определяет для любой формулы
теории, явл. ли эта формула теоремой теории,
может состоять в вычислении истинностных значений
формулы в каждой интерпретации. Принципиально это
выполнимо за конечное время в силу конечности числа
интерпретаций и числа операций, присутствующих в
формуле.
58. Предикат: n-местный (n=0, n>0). Предикатные формулы. Связь между предикатами, отношениями и функциями. Модель в логике предикатов.
1) Под 0-местным предикатом понимается произвольное высказывание.
2) Элементарной формулой называется всякая пропозициональная переменная, а также любая m -местная предикатная переменная (m > 0).
__Из элементарных формул строятся предикатные формулы:
1) Все элементарные формулы суть формулы;
2) Если А и В — формулы, то выражения (А & В), (А Ú В), (А ® В), (А ~ В), ØА считаются формулами;
3) если А — формула, x — предметная переменная, то " x А и $ x В суть формулы.
Виды математических предикатов:
__Предикат тождества E(x1,x2): N 2 ® B: E (a 1, a 2) = 1 тогда и только тогда, когда a 1 = a 2, xi ÎN
__Предикат порядка Q (x1,x2): N 2 ® B: Q (a 1, a 2) = 1 тогда и только тогда, когда a 1 £ a 2, xi ÎN
__Предикат делимости D (x1,x2): N 2 ® B: D (a 1, a 2) = 1 тогда и только тогда, когда a 1 делится на a 2, xi ÎN
__Предикат суммы S (x1,x2,x3): N 3 ® B: S (a 1, a 2, a 3) = 1 тогда и только тогда, когда a 1 + a 2 = a 3, xi ÎN
__Предикат произведения P (x1,x2,x3): N 3 ® B: P (a 1, a 2, a 3) = 1 тогда и только тогда, когда a 1 * a 2 = a 3, xi ÎN
СВЯЗЬ МЕЖДУ ПРЕДИКАТАМИ,ОТНОШЕНИЯМИ И ФУНКЦИЯМИ:
____Всякой n-местной функции f(x1, …,xn), f:M1 ´ M2 ´…´ Mn® M соответствует n+1 - местный предикат P(x1, …,xn,xn+1), P: M1 ´ M2 ´…´ Mn+1 ® B, такой, что P(a1, …,an, an+1) = 1, если и только если f(a1, …,an) = an+1.
____Понятие предиката шире понятия функции, поэтому обратное соответствие (от (n + 1)-местного предиката к n-местной функции) возможно не всегда, а только для таких предикатов P¢ для которых выполняется условие:
если P¢(a1, …,an, an+1) = 1, то для любого
a¢n+1 ¹ an+1 P¢(a1, …,an, a¢n+1) = 0.
МОДЕЛЬ В ЛОГИКЕ ПРЕДИКАТОВ:::
__Моделью M в логике предикатов называется множ. М вместе с заданной на нем совокупностью предикатов S={ P 1, …, Pk }: M = (М; P 1, …, Pk),
где М — основное множ. модели M;
S={ P 1, …, Pk } — сигнатура модели M.
___Аналогично предыдущему определяются формулы, выполнимые на модели M, тождественно-истинные и тождественно-ложные на модели M.
59. Квантор всеобщности и квантор существования. Область действия квантора. Связанное и свободное вхождение переменной в формулу.
Пусть P (x) — предикат, определенный на M
__Высказывание «для всех x из M предикат P (x) истинен» обозначается " xP (x). Знак " x называется квантором общности;
__Высказывание «существует такой x из M, что предикат P (x) истинен» обозначается $ xP (x). Знак $ x называется квантором существования.
__Переход от P (x) к " x P (x) или $ x P (x) называется связыванием переменной x, а также навешиванием квантора на переменную x (или на предикат P), иногда — квантификацией переменной x.
__Переменная, на которую навешен квантор, называется связанной; несвязанная переменная называется свободной.
ОБЛАСТЬ ДЕЙСТВИЯ КВАНТОРА:::
__Выражения " xP (x), $ xP (x) не зависят от х и при фиксированных Р и М имеют вполне определенные значения, представляя вполне конкретное высказывание относительно всех х предметной области М.
__Выражение, на которое навешивается квантор " x или $ x называется областью действия квантора;
__Все вхождения переменной x в это выражение явл. связанными.
__Навешивание предиката на многоместный предикат уменьшает в нем число свободных переменных и превращает его в предикат от меньшего числа переменных.
60. Предикаты. Выполнимая, тождественно истинная и тождественно ложная формула на множестве М. Общезначимая и противоречивая формулы. Методы определения истинностных значений предиката: подстановкой, прямым доказательством, методом от противного.
__Предикат – повествовательное предложение, содержащее предметные переменные xi ÎMi, определенные на соответствующих множествах Mi
__Если в множестве М для формулы F существует такая подстановка констант вместо всех переменных, что F становится истинным высказыванием, то формула F называется выполнимой в области М. Если существует область М, где F выполнима, то F называется просто выполнимой.
__Если формула F выполнима в М при любых подстановках констант, то она называется тождественно истинной в М. Формула, тождественно истинная в любых М называется тождественно истинной или общезначимой.
__Если формула F невыполнима в М, она называется тождественно ложной в М. Если F невыполнима ни в каких М, она называется тождественно ложной, или противоречивой.
ОБЩЕЗНАЧИМАЯ И ПРОТИВОРЕЧИВАЯ Ф_ЛЫ????????
МЕТОДЫ ОПРЕД,, ПОДСТАНОВКОЙ:::
__Оценить истинностное значение предиката "(x) S(x,y,x), где S(x,y,x) – предикат суммы на множествах N0, N.
__На множестве N0 существует единственная подстановка константы вместо переменной y, такая что для любого х выражение x+y=x истинно. Очевидно, что y=0. Т.е. данный предикат выполним на множестве N0.
___Очевидно, что на множестве N такой подстановки не существует, т.е. данный предикат тождественно ложный на множестве N.
__Так как существует множ. на котором он выполним, то рассматриваемый предикат просто выполним.
ПРЯМОЕ ДОК_ВО::::
__Пример1: Оценить истинностное значение предиката $(x)(P(x)&ùP(x)), где P(x) – любой предикат.
При подстановке любого значения а из любого множ. М вместо переменной х возможны две ситуации Р(а)=1 и Р(а)=0. Рассмотрим каждую из них.
Если Р(а)=1, тогда ùP(а)=0 и формула P(а)&ùP(а)=1&0=0.
Если Р(а)=0, тогда ùP(а)=1 и формула P(а)&ùP(а)=0&1=0.
Таким образом, рассматриваемый предикат явл. тождественно ложным.
__Пример 2: Оценить истинностное значение предиката
ù "хP(х) → $(x) ù P(х), где P(x) – любой предикат
Следующие рассуждения верны для любого множ. М. Если не верно, что для любого значения а из множ. М высказывание Р(а) истинно, то это означает, что существует х=а для которого Р(а) – «ложно» (т.е. ùP(а)=1). Таким образом левая и правая часть всегда имеют одинаковые значения либо 0 → 0 = 1, либо 1 → 1 = 1. Как видно, в любом случае это высказывание истинно и при этом не зависит от выбора множ. М. Таким образом, рассматриваемый предикат явл. тождественно истинным.
МЕТОД ОТ ПРОТИВНОГО::::
__Пример: Оценить истинностное значение предиката " x ((P(x)&Q(x)) →P(x)), где P(x), Q(x) – любые предикаты.
Предположим противное. Пусть формула ложна, т.е. не для всех х формула (P(x)&Q(x)) →P(x) истина. Тогда существует значение а, подстановка которой в формулу делает ее ложной (P(а)&Q(а)) →P(а) =0. Такая ситуация возможна если
P(а)&Q(а) = 1 (1)
P(а) = 0 (2)
Из (1) следует, что P(а)=1, что противоречит (2)
Принятое предположение относительно ложности формулы
привело к противоречию, поэтому оно не верно и, следовательно,
формула " x ((P(x)&Q(x)) →P(x)) тождественно истинна
61. Эквивалентные соотношения логики предикатов. Префиксная нормальная форма. Процедура получения ПНФ.
ЭКВИВ. СООТНОШ.::::
1) ù($ x P(x)) ~ " x ù P(x)
2) ù (" x P(x)) ~ $ x ù P(x)
3) " x (P 1 (x) & P 2 (x)) ~ ( " x P 1 (x) & " x P 2 (x)) дистрибутивность квантора " относительно &
4) $ x (P 1 (x) v P 2 (x)) ~ ( $ x P 1 (x) v $ x P 2 (x)) дистрибутивность квантора $ относительно v
5) " x " y P(x,y) ~ " y " x P(x,y) коммутативность квантора "
6) $ x $ y P(x,y) ~ $ y $ x P(x,y) коммутативность квантора $
7) " x (P(x) & Y) ~ ( " x P(x) & Y), где Y не зависит от х
8) $ x (P(x) & Y) ~ ( $ x P(x) & Y), где Y не зависит от х
9) " x (P(x) v Y) ~ ( " x P(x) v Y), где Y не зависит от х
10) $ x (P(x) v Y) ~ ( $ x P(x) v Y), где Y не зависит от х
ПРЕФИКСНАЯ И НОРМ ФОРМА:::::
__Префиксной нормальной формой (ПНФ) называется формула, имеющая вид
Q 1 x 1, Q 2 x 2, …, QnxnF — кванторы; F — формула, не имеющая кванторов, с операциями {&, Ú, ù}.
___В логике предикатов для любой формулы существует эквивалентная ей префиксная нормальная форма.
ПРОЦЕДУРА ПОЛУЧЕНИЯ ПНФ:
1) Заменить операции →, ~ на булевы
A → B = ù A v B
A ~ B = (ù A v B) & (A v ù B)
2) При помощи эквивалентных соотношений спустить символы отрицания на предикаты
3) Если к формуле, не имеющей вид ПНФ, не применимы эквивалентные соотношения, то следует использовать правила переименования переменных
4) С помощью эквивалентных соотношений получить ПНФ
62. Конечный автомат. Способы задания: таблицей, диаграммой.
___Конечным автоматом называется система M ={ А, B, S, j, y }, в которой
n А = {а1,..., am} – конечный входной алфавит,
n B ={b1,..., bk} — конечный выходной алфавит,
n S ={s1,..., sn} — конечный алфавит состояний,
n j: А ´ S ® S — функция переходов,
n y: А ´ S ® B — функция выходов.
Если в автомате M выделено одно состояние, называемое начальным (обычно будет считаться, что это s1), то полученный автомат называется инициальным и обозначается (M, s1).
АВТОМАТНАЯ ТАБЛИЦА::
Дата добавления: 2015-11-16; просмотров: 100 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| СДНФ приводим к минимальной ДНФ | | | Ориентированный мультиграф, называемый графом переходов или диаграммой переходов |