Формальные системы

МИНОБРНАУКИ РОССИИ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ

ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

«ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА)

Кафедра ИС

Задание к книге №4

по дисциплине «Интеллектуальные информационные системы»

Тема:  Формальные системы

Санкт-Петербург

2021

1. Покажите на примере, что композиция подстановок не коммутативна.

Q1#Q2= {g(x,y)|z}#{A|x, B|y, c|w, D|Z} = {g(A,B)|z, A|x, B|y, c|w}.

Q2#Q1= {A|x, B|y, c|w,D|Z}#{g(x,y)|z} = {A|x, B|y, c|w, D|Z, g(x,y)|z}

Q1#Q2 не равно Q2#Q1

1. Найдите наиболее общий унификатор для {P(x,y, z) P(w,u,w) P(a,u,u)))}

НОУ: (a|x, a|w, u|y, a|z, a|u)

1. Покажите логичность резолюции, то есть покажите, что резольвента двух предложений логически следует из этих двух предложений.

Теорема дедукции. Пусть Г – множество формул, А, В – формулы. Тогда Г, А├ В => Г├ А → В.

В частности, если Г = ∅, то если А├ В => ├ А → В

𝐶1, 𝐶2 – резольвируемые предложения, а 𝐶1 ′ ∨ 𝐶2 ′ - резольвента.

Теорема: резольвента логически следует из резольвируемых предложений.

Доказательство:

В вышеприведенных обозначениях, нам нужно 𝐶1 → (𝐶2 → (𝐶1 ′ ∨ 𝐶2 ′ )) - тавтология (по теореме дедукции).

Предположим, что

[pic 1]

Полученное противоречие доказывает утверждение теоремы.

1. Определить являются выполнимыми или общезначимыми формулы:

((p→q)→((p→(q→c))→(p→c);

((p→q)→((p→c)→(p→(q&c))

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

Таблица истинности для первой формулы: