Задание №1

Из данной совокупности секвенций выбрать доказуемые, построить их доказательства, для недоказуемых показать их недоказуемость с помощью:

4. Алгоритма Квайна

5. Алгоритма редукции

6. Метода резолюций

Среди этих доказательств недоказуемости выбрать оптимальный в каждом конкретном случае.

5. XXY XY.

6. XUZ,XZ,UY XY.

7. (XX).

8. XYZ YXZ.

Решение:

1. XXY XY; Данная секвенция доказуема! (по таблицам истинности).

X X; _{12 12} Y Y;

XXY X ; XXY Y; ₁

₁₂ XY XY; XXY XY);

₁₀ XXY XY ; XXY (XY);

₉ XXY ;

₇ XXY Y;

XXY XY;

Следовательно, данная секвенция доказуема!

2. XUZ,XZ,UY XY.

Данная секвенция недоказуема! (по таблице истинности)

Метод Квайна: XUZ,XZ,UY XY

Пусть X=0 , тогда: Пусть X=1 , тогда:

(0UZ)(1Z)(UY) 1; 1Z(UY) Y;

(UZ)1(UY) 1; Пусть Y=0 , тогда:

1ZU 0;

Пусть Y=0 , тогда: Пусть Y=1 , тогда: Пусть Z=0 , тогда: Пусть Z=1 , тогда:

(UZ)1U 1; (UZ)11 1; 0 0; 11U 0;

Пусть Z=0 , тогда: Пусть Z=1 , тогда: Пусть U=0 , тогда: Пусть U=0 , тогда:

11U 1; U11 1; 0 0; 11 0;

Пусть U=0 , тогда: Пусть U=1 , тогда: 1 0;

1 1; 1 1; тождественно ложно

Следовательно, данная секвенция недоказуема.

Метод редукции : XUZ,XZ,UY XY;

XUZ,XZ,UYXY

Предположим противное, т.е

Докажем что при XY=0, (XUZ)XZ)UY)=1;

Чтобы выполнялось XY=0 надо, чтобы выполнялось:

X= 1, Y = 0.

Тогда:

(1UZ)0Z)U0)=1ZU =ZU=1.

Следовательно, Z=1, U=0. Значит при X= 1, Y = 0, Z=1, U=0 наше предположение истинно, следовательно, данная секвенция недоказуема!

Метод резолюций: XUZ,XZ,UYXY.

Докажем противоречивость:

XUZ , XZ ,UY , XY)

Приведем формулы XUZ , XZ ,UY , XY) к КНФ.

XUZ , XZ ,UY , XY.

XUZ , XZ ,UY , XY.

(1) XUZ;

(2) XZ;

(3) UY;

(4) X;

(5) Y;

(6) res_X,Z((1),(2)) =U;

(7) res_Y((3),(5)) = U;

(8) res_U((6),(7)) = 0.

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

3. (XX).

Данная секвенция доказуема! (по таблице истинности)

₂ XXXX; XXXX; ₃

₁₀ XXX ; XXX;

₉ XX;

(XX)

Следовательно, данная секвенция доказуема!

4. XYZXYXZ.

Данная секвенция недоказуема! (по таблице истинности)

Метод Квайна: XYZXYXZ.

Пусть X=0 , тогда: Пусть X=1 , тогда:

ZYZ; 11;

Пусть Y=0 , тогда: Пусть Y=1 , тогда: далее док-во не требуется.

ZZ; Z1;

Пусть Z=0 , тогда: Пусть Z=1 , тогда:

10; 01;

тождественно ложно.

Метод редукции: XYZXYXZ.

XYZXYXZ.

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

Докажем что при YXZ = 0, XYZX =1;

Чтобы выполнялось YXZ = 0, надо, чтобы X=0, Y=0, Z=0.

Тогда при X=0, Y=0, Z=0 выражение XYZX =1 тождественно истинно, т.к 11.

Значит при X=0, Y=0, Z=0 данная секвенция недоказуема!

Метод резолюций: XYZXYXZ.

Приведем формулу XYZX, (YXZ) к КНФ

XYZX, YXZ;

XZ , Y , X , Z.

1. XZ;

2. Y;

3. X;

4. Z;

5. res_X((1),(2)) = Z;

Множество формул непротиворечиво, следовательно, данная секвенция недоказуема.

Задание №2

Найти формулу исчисления предикатов, истинную на алгебраической системе A и ложную на B.

A = <Q; + > , B = <N; +>.

Решение:

 : xyz ((x+y=z)(x+z=x));

 : xyz ((x+y=z)(x+z=x));

x+z=x означает, что z=0; значит, x+y в сумме должны давать 0. Но если взять положительный x (x>0) то, чтобы получился 0, y должен быть меньше 0, но y<0  N.

Задание №3

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

x P(x)xP(x)

Решение:

₁₂ xP(x)xP(x)

₁₀ xP(x),xP(x)xP(x) xP(x), xP(x)

₉ xP(x),xP(x) xP(x),xP(x) ₉

₇ xP(x)xP(x) xP(x)xP(x) ₇

₁ xP(x)xP(x); xP(x)xP(x);

((xP(x)xP(x))(xP(x)xP(x)));

x P(x)xP(x)

Задание №4

Установить, выполнима ли следующая формула и если выполнима, то построить модель этой формулы.

xyzu (P(x,y)P(x,z)P(x,u)R(y,z,u))  x R(x,x,x).

Решение:

1. Вынесем поочередно кванторы во внешнюю часть:

xyzu (P(x,y)P(x,z)P(x,u)R(y,z,u))  x R(x,x,x) 

xyzuv P(x,y)P(x,z)P(x,u)R(y,z,u)  R(v,v,v) - ПНФ

2. Получили ПНФ. Приведем к КлНФ.

y = f(x); z = g(x); u = h(x);

P(x,f(x)) , P(x,g(x)) , P(x,h(x)) , R(f(x),g(x),h(x)) , R(v,v,v) – КлНФ.

3. Методом резолюций проверим выполнимость данной формулы:

7. P(x,f(x));

8. P(x,g(x));

9. P(x,h(x));

10. R(f(x),g(x),h(x));

11. R(v,v,v);

Невозможно сделать резолютивный вывод из данного множества формул, следовательно существует

модель.

Строим модель:

A = {a , b};

0 = R(a,a,a) = ложно =R(b,b,b).

f(a) = b; g(a) = a; h(a) = a;

f(b) = a; g(b) = b; h(b) = b;

Полагаем, что:

P(a,b) = P(b,a) = истинно;

P(a,a) = P(b,b) = истинно;

R(b,a,a) = истинно = R(a,b,b).

Задание №5

Привести к пренексной и клазуальной нормальным формам следующую формулу:

x (y P(x,y)  y Q(x,y)  x (y P(x,y)y Q(x,y))).