Математическая логика и теория алгоритмов. Галуев Г.А. - 20 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 20 из 64
© 2003 Галуев Геннадий Анатольевич
Полученная в результате
эквивалентных преобразова-
ний пропозиционная формула
значительно проще исходной.
Синтезированная по этой фор-
муле комбинационная схема
имеет вид, как показано на
рис.4. Эта схема эквивалентна
схеме на рис.3, но значительно
проще её.
Рис.4
Наряду с рассмотренными выше примерами аппарат исчисления высказываний
широко использовался при создании систем искусственного интеллекта (автоматиче-
ское доказательство теорем), представление знаний и получение новых знаний в экс-
пертных системах и т.д. Перейдём теперь к рассмотрению другого важного раздела
математической логики, который непосредственно связан с исчислением высказыва-
ний и
получил название исчисление предикатов.
Исчисление предикатов.
Кванторы, формулы, выражения, свободные и связанные перемен-
ные.
Исчисление высказываний оперирует высказываниями, не вдаваясь в структуру
последних. Там мы изучали логические отношения между пропозиционными буквами,
которые различными способами при помощи операций &, ∨, ⎤, →, ↔ связывались ме-
жду собой, образуя более сложные пропозиционные формы (высказывания). При
этом нас не интересовала внутренняя структура блоков, из которых строились выска-
зывания. В тоже время не все виды логических рассуждений могут быть обоснованы и
представлены в рамках такого подхода. Например: Все люди смертны. Сократ чело-
век. Следовательно, Сократ смертен.
Такой вывод нельзя получить в рамках исчисления высказываний, т.к. здесь ис-
пользуется внутренняя структура предложений.
В исчислении предикатов можно реализовать выводы такого
типа. Для этого вво-
дятся две новые операции: ∀ (для любого, для всякого, для всех) и ∃ (существует,
для некоторого, существует по крайней мере один). Дадим им формальное определе-
ние.
Если P(X) означает, что X обладает свойством P, то посредством ∀X P(X) будем
обозначать утверждение: «для всякого или для любого X свойство P выполнено» или
«все
X обладают свойством P».
Запись ∃X P(X) означает, что «существует по крайней мере один X, обладающий
свойством P».
В выражении ∀X P(X) часть ∀X называется квантором всеобщности, а часть ∃X в
выражении ∃X P(X) называется квантором существования.
С помощью этих кванторов представленное выше умозаключение можно фор-
мально записать в виде:
∀X (Ч(X)→C(X))
Ч(X)
C(X)
Дадим теперь определение формул и выражений исчисления предикатов.
Для построения выражений будем использовать те же символы, что и в исчисле-
нии высказываний: запятые, скобки, знаки ⎤, →; вместо пропозиционных букв будут
использоваться их обобщения – предикатные буквы
k
n
1
1
A,...,A , а также предметные
Z
1
X
2
X
3
X
4
X
&
&
1

Страницы