|
A
|
B
|
C
|
D
|
1à2
|
3à2
|
1Ú3
|
4à7
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
В таблице истинности жирным шрифтом выделены столбцы с
посылками, а жирным и курсивом выделено заключение. Смотря на те строчки, в
которых истины все посылки одновременно (в данном случае это первая, третья,
девятая, которые выделены жирной рамкой), видно, что заключение также истинно.
Поэтому можно сделать вывод, что данное заключение выводимо из данного
множества посылок.
Б. Упростить посылки и заключения, т.е. привести их к
базисному множеству {Ø, &, Ú} с минимальным числом
операций:
F1=А - формула остается без изменений;
F2=B - формула остается без изменений;
F3=C - формула остается без изменений;
F4=D - формула остается без изменений;
F5=AàB = ØAÚB;6=
CàB = ØCÚB;7= AÚC - формула остается без
изменений;
F8=Dà(AÚC) = ØDÚAÚC;
в. Привести посылки и заключение к базисам {Ø, &} и {Ø, Ú}:
Базис {Ø, Ú}:
F1=А - формула остается без изменений;
F2=B - формула остается без изменений;
F3=C - формула остается без изменений;
F4=D - формула остается без изменений;
F5=AàB = ØAÚB;6=
CàB = ØCÚB;7= AÚC - формула остается без
изменений;
F8=Dà(AÚC) = ØDÚAÚC;
Базис {Ø, &}:
F1= А - формула остается без изменений;
F2= B - формула остается без изменений;
F3= C - формула остается без изменений;
F4= D - формула остается без изменений;
F5= AàB = Ø(A&ØB);6=
CàB = Ø(C&ØB);7=
AÚC = Ø(ØA&ØC);8=
Dà(AÚC) = ØDÚAÚC = Ø(D&ØA&ØC);
г. Для посылок и заключения построить КНФ, ДНФ, СКНФ, СДНФ:
КНФ:
F1= А - формула остается без изменений;
F2= B - формула остается без изменений;
F3= C - формула остается без изменений;
F4= D - формула остается без изменений;
F5= AàB = (ØAÚB)&;6=
CàB = (ØCÚB)&;7=
AÚC = (AÚC)&;8=
Dà(AÚC) = (ØDÚAÚC)&;
ДНФ:
F1= А - формула остается без изменений;
F2= B - формула остается без изменений;
F3= C - формула остается без изменений;
F4= D - формула остается без изменений;
F5= AàB = Ø(A&ØB) Ú;6=
CàB = Ø (C&ØB) Ú;7=
AÚC = Ø (ØA&ØC) Ú;8=
Dà(AÚC) = Ø DÚØ(ØA&ØC) Ú;
СКНФ:
СКНФ строится по значениям «л» заключения в таблице истинности;
F2= (AÚØBÚCÚD) & (AÚØBÚCÚØD) & (AÚØBÚØCÚD) & &
(AÚØBÚØCÚØD) & (ØAÚØBÚCÚD) & (ØAÚØBÚCÚØD) & &
(ØAÚØBÚCÚØD) & (ØAÚØBÚØCÚD) & (ØAÚØBÚØCÚØD);
СДНФ:
СДНФ строится по значениям «и» заключения в таблице
истинности;
F2= (A&B&C&D) Ú
(A&B&C&ØD) Ú (A&B&ØC&D) Ú Ú (A&B&ØC&ØD) Ú (ØA&B&C&D)
Ú (ØA&B&ØC&D) Ú (ØA&B&C&ØD) Ú
Ú (ØA&B&ØC&ØD);
д. Доказать истинность заключения путём построения дерева
доказательства:
{AàB, CàB, Dà(AÚC), D} | - B
У. à
У. à
У. à
е. Доказать истинность заключения методом дедуктивного вывода
(с построением графа дедуктивного вывода):
Построим граф дедуктивного вывода.
AàB CàB Dà(AÚC) D
m.p.
AÚC
m.p.
m.p.
B
Рисунок A.3 - Граф дедуктивного вывода
ж. Доказать истинность заключения методом резолюции (с
построением графа вывода пустой резольвенты):
Приведем посылки и отрицание заключения к виду КНФ:
F4= D - формула остается без изменений;
F5= AàB = ØAÚB;6=
CàB = ØCÚB;8=
Dà(AÚC) = ØDÚAÚC;
Ø J = ØF2=
ØB;={D, ØAÚB, ØCÚB, ØDÚAÚC, ØB}
Построим граф вывода пустой резольвенты:
ØB ØAÚB ØCÚB ØDÚAÚC D
AÚС
AÚB
B
Рисунок А.4 - Граф вывода пустой резольвенты
2 Выполнить задание по алгебре предикатов и
исчислению предикатов:
истинность предикат доказательство резолюция
Вариант 22: F= "x (B(x)) ® $y (A(y) ® B(x))
а. Привести выражение к виду ПНФ:
F= "x (B(x)) ® $y (A(y) ® B(x)) = Ø"x (ØB(x)) V $y (A(y) ® B(x)) =
= $x (ØB(x)) V $y (ØA(y) V B(x)) = $v (ØB(v)) V $w (ØA(w) V B(x)) =
= $v$w (ØB(v) V ØA(w) V B(x));
б. Привести выражение к виду ССФ:
Для приведения к виду ССФ воспользуемся алгоритмом Сколема,
поэтому будут проведены следующие замены:
v = a, где a - предметная постоянная
w = b, где b - предметная постоянная
В результате получится следующее выражение:
F= ØB(a) V ØA(b) V B(x);
в. Доказать истинность заключения методом дедуктивного вывода
(с построением графа дедуктивного вывода):
Представим нашу формулу в следующем виде:
{"x (B(x))} | - $y (A(y) ® B(x))
Построим граф дедуктивного вывода для доказательства
выводимости заключения из данного множества посылок:
"x (B(x))
У "
B(x)
A(y) ®B(x)
B $
$y
(A(y) ® B(x))
Рисунок A.5 - Граф дедуктивного вывода
г. Доказать истинность заключения методом резолюции (с
построением графа вывода пустой резольвенты):
ØF= Ø("x (B(x)) ® $y (A(y) ® B(x))) = Ø(Ø"x (B(x)) V $y (ØA(y) V B(x))) =
= "x (B(x)) & Ø$y (ØA(y) V B(x)) =
"x (B(x)) & "y (A(y) & ØB(x)) =
= "v (B(v)) & "w (A(w) & ØB(x)) = "v"w (B(v) &
A(w) & ØB(x));
Д= {B(v), A(w),
ØB(x)};
Построим граф вывода пустой резольвенты:
B(v) ØB(x) A(w)
B(v) ®(B(v) V A(w))
x ∫v
ØB(v) V ØB(v) V B(v) V
A(w)
Рисунок А.6 - Граф вывода пустой резольвенты
Вариант 39:
F= "x (B(x) ® A(y)) &
(B(x) ® "y (A(y) ® C(z))) ® $z (B(x)®C(z));
а. Привести выражение к виду ПНФ:
F= "x (B(x) ® A(y)) & (B(x) ® "y (A(y) ® C(z))) ® $z (B(x)®C(z)) =
= Ø("x (B(x) ® A(y)) & (B(x) ® "y (A(y)®C(z)))) V $z (B(x)®C(z)) =
= Ø"x (B(x) ® A(y)) V Ø(B(x) ® "y (A(y)®C(z))) V $z (B(x)®C(z)) =
= Ø"x (ØB(x) VA(y)) V Ø(ØB(x) V "y (ØA(y) V C(z))) V $z (ØB(x) V C(z)) =
= Ø"x (ØB(x) VA(y)) V (B(x) & Ø"y (ØA(y) V C(z)))
V $z (ØB(x) V C(z)) =
= $x (B(x)& ØA(y)) V (B(x) & $y (A(y) & ØC(z))) V $z (ØB(x) V C(z)) =
= $v (B(v)& ØA(y)) V (B(x) & $w (A(w) & ØC(z))) V $t (ØB(x) V C(t)) =
= $v$w$t((B(v)& ØA(y)) V B(x)
& (A(w) & ØC(z)) V (ØB(x) V C(t));
б. Привести выражение к виду ССФ:
Для приведения к виду ССФ воспользуемся алгоритмом Сколема,
поэтому будут проведены следующие замены:
v = a, где a - предметная постоянная;
w = b, где b - предметная постоянная;
t = d, где d - предметная постоянная;
В результате получится следующее выражение:
F= (B(a)& ØA(y)) V B(x)
& (A(b) & ØC(z)) V (ØB(x) V C(d));
в. Доказать истинность заключения методом дедуктивного вывода
(с построением графа дедуктивного вывода):
Представим нашу формулу в следующем виде:
{"x (B(x) ® A(y)); B(x) ® "y (A(y) ® C(z))}| - $z (B(x)®C(z))
Построим граф дедуктивного вывода для доказательства
выводимости заключения из данного множества посылок:
"x (B(x) ® A(y)) B(x) ® "y (A(y) ® C(z))
У " У
"
B(x) ® A(y) B(x)
® (A(y) ® C(z))
B(x) ®C(z)
В $
$z
(B(x)®C(z))
Рисунок A.7 - Граф дедуктивного вывода
г. Доказать истинность заключения методом резолюции (с
построением
графа вывода пустой резольвенты):
F= Ø("x (B(x) ® A(y)) & (B(x) ® "y (A(y)
® C(z))) ® $z (B(x)®C(z))) =
= Ø(Ø(("x (B(x) ® A(y))) & (B(x) ® "y (A(y) ® C(z)))) V $z (B(x)®C(z))) =
= Ø(Ø"x (B(x) ® A(y)) V Ø(B(x) ® "y (A(y) ® C(z))) V $z (ØB(x) V C(z))) =
= "x (B(x) ® A(y)) & (B(x) ® "y (A(y) ® C(z))) & Ø$z (ØB(x) V C(z)) =
= "x (ØB(x) V A(y)) & (ØB(x) V "y (ØA(y) V C(z))) & "z (B(x)& ØC(z)) =
= "v (ØB(v) V A(y)) & (ØB(x) V "w (ØA(w) V C(z))) & "d (B(x)& ØC(d)) =
= "v"w"d((ØB(v) V A(y)) & (ØB(x) V ØA(w) V C(z)) & (B(x)& ØC(d));
Д= {B(x); ØC(d); ØB(v) V A(y); ØB(x) V ØA(W) V C(z)};
Построим граф вывода пустой резольвенты:
B(x) ØC(d) ØB(v) V A(y) ØB(x) V ØA(W) V C(z)
y ∫w x ∫v
x ∫v
ØB(v) V A(w) V ØA(w) V C(z) V ØB(v)
z ∫d
ØB(v) V C(d) V ØC(d)
Рисунок А.8 - Граф вывода пустой резольвенты
. Реляционная алгебра
Выполнить следующие бинарные операции и составить
результирующие таблицы.
) (r1Èr2)
) (r1Çr2)
) (r1 \ r2)
) Выполнить заданную композицию операций
Вариант №48
Таблица r1
|
А3
|
А4
|
А7
|
А8
|
|
с1
|
d2
|
1
|
2
|
|
с2
|
d3
|
2
|
3
|
|
с1
|
d1
|
2
|
1
|
|
с2
|
d2
|
1
|
4
|
Таблица r2
|
А3А4А7А8
|
|
|
|
|
c3
|
d4
|
3
|
4
|
|
c1
|
d2
|
1
|
2
|
|
c1
|
d1
|
2
|
1
|
|
c2
|
d2
|
1
|
4
|
1) (r1Èr2)
|
А3А4А7А8
|
|
|
|
|
c1
|
d2
|
1
|
2
|
|
c2
|
d3
|
2
|
3
|
|
c1
|
d1
|
2
|
1
|
|
c2
|
d2
|
1
|
4
|
|
c3
|
d4
|
3
|
4
|
2) (r1Çr2)
|
A3A4A7A8
|
|
|
|
|
c1
|
d2
|
1
|
2
|
|
c2
|
d3
|
2
|
3
|
|
с1
|
d1
|
2
|
1
|
) (r1 \ r2)
) r1>q<r2,
d (r1.A7)= d(r2.A7)
|
r1A3
|
r1A4
|
r1A7
|
r1A8
|
r2A3
|
r2A4
|
r2A7
|
r2A8
|
|
с1
|
d2
|
1
|
2
|
c1
|
d2
|
1
|
2
|
|
с1
|
d2
|
1
|
2
|
c2
|
d2
|
1
|
4
|
|
с2
|
d3
|
2
|
3
|
c1
|
d1
|
2
|
1
|
|
с1
|
d1
|
2
|
1
|
c1
|
d1
|
2
|
1
|
|
с2
|
d2
|
1
|
4
|
c1
|
d2
|
1
|
2
|
|
с2
|
d2
|
1
|
4
|
c2
|
d2
|
1
|
4
|
) p(r1.A1, r2.A2, r1×A5,r2.A6)(r1>q<r2, d (r1.A7)=d(r2.A7))
|
r1A3r1A4r1A7r1A8r2A3r2A4r2A7r2A8
|
|
|
|
|
|
|
|
|
с1
|
d2
|
1
|
2
|
c1
|
d2
|
1
|
2
|
|
с1
|
d2
|
1
|
2
|
c2
|
d2
|
1
|
4
|
|
с2
|
d3
|
2
|
3
|
c1
|
d1
|
2
|
1
|
|
с1
|
d1
|
2
|
1
|
c1
|
d1
|
2
|
1
|
|
с2
|
d2
|
1
|
4
|
c1
|
d2
|
1
|
2
|
|
с2
|
d2
|
1
|
4
|
c2
|
d2
|
1
|
4
|
Вариант №31
Таблица r1
|
А1
|
А2
|
А5
|
А6
|
|
a4
|
b1
|
4
|
1
|
|
a1
|
b1
|
4
|
3
|
|
a3
|
b3
|
2
|
1
|
|
a4
|
b4
|
1
|
4
|
Таблица r2
|
А1А2А5А6
|
|
|
|
|
a1
|
b2
|
1
|
2
|
|
a2
|
b3
|
2
|
3
|
|
a1
|
b1
|
4
|
3
|
|
a2
|
b2
|
3
|
2
|
1) (r1Èr2)
|
А1А2А5А6
|
|
|
|
|
a4
|
b1
|
4
|
1
|
|
a1
|
b1
|
4
|
3
|
|
a3
|
b3
|
2
|
1
|
|
a4
|
b4
|
1
|
4
|
|
a1
|
b2
|
2
|
|
a2
|
b3
|
2
|
3
|
|
a2
|
b2
|
3
|
2
|
2) (r1Çr2)
3) (r1 \ r2)
|
А1А2А5А6
|
|
|
|
|
a4
|
b1
|
4
|
1
|
|
a3
|
b3
|
2
|
1
|
|
a4
|
b4
|
1
|
4
|
4) r1>q<r2,
d(A5)= 4; r1.A5=r2.A5
|
r1A1
|
r1A2
|
r1A5
|
r1A6
|
r2A1
|
r2A2
|
r2A5
|
r2A6
|
|
a4
|
b1
|
4
|
1
|
a1
|
b1
|
4
|
3
|
|
a1
|
b1
|
4
|
3
|
a1
|
b1
|
4
|
3
|
) p(r1.A1, r2.A4, r2×A5,r1.A6) (r1>q<r2, d(A5)= 4)
|
r1A1
|
r1A6
|
r2A5
|
|
a4
|
1
|
4
|
|
a1
|
3
|
4
|
Заключение
В результате проделанной работы, били закреплены практические
навыки решения задач по математической логике. Было решено 2 варианта заданий
по математической логике и исчислению высказываний, математической логике и
исчислению предикатов, реляционной логике.
Литература
1)
Игошин, В.И. Математическая логика и теория алгоритмов: Учеб. пособие для вузов
[Текст] / В.И. Игошин. - М.: Академия, 2004 г.