Методы решений задач логики высказываний, логики предикатов и реляционной логики
Введение
В середине XX века развитие вычислительной
техники привело к появлению логических электронных элементов, логических блоков
и устройств вычислительной техники, что было связано с дополнительной
разработкой таких областей логики, как проблемы логического синтеза, логическое
проектирование и логического моделирования логических устройств и средств
вычислительной техники. Эти проблемы изучает теория алгоритмов, основанная на
математике, и математической логике в частности. Математическая логика нашла широкое
применение в языках программирования. А в 80-х годах XX века начались
исследования в области искусственного интеллекта на базе языков и систем
логического программирования. Это направление является самым развивающимся и
перспективным.
Поэтому целью данной курсовой работы является
знакомство с методами решений задач логики высказываний, логики предикатов и
реляционной логики.
Задачами, которые будут решаться в работе,
являются:
ознакомиться с алгеброй логики высказываний и
исчислением высказываний,
рассмотреть алгебру логики предикатов и
исчисление предикатов,
изучить реляционную алгебру.
Для решения поставленных задач использовался
теоретический материал научных работ Лаврова И.А., Максимовой Л.Л. и Пономарева
В.Ф.
1 Логика высказываний
1.1 Выполнить задания по алгебре высказываний и
исчислению высказываний:
{(A®(B®C));(
ØDÚA);B}|-(D®C)
F= A®(B®C)
G=ØDÚA
H=B J= D®C
Таблица 1 - Таблица
истинности
|
A
|
B
|
C
|
D
|
B®C
|
A®(1)
|
ØDÚA
|
D®C
|
|
H
|
|
|
(1)
|
F
|
G
|
J
|
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
1
|
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
В таблице истинности жирным шрифтом выделены
столбцы с посылками, а жирным и курсивом выделено заключение. Смотря на те
строчки, в которых истины все посылки одновременно (в данном случае это пятая,
седьмая, пятнадцатая и шестнадцатая строчки, которые выделены жирной рамкой),
видно, что заключение также истинно. Поэтому можно сделать вывод, что данное
заключение выводимо из данного множества посылок.
Упростить посылки и заключения, т.е. привести их
к базису {Ø, &, Ú}
с минимальным числом операций:
F = A®
(B®C) = ØAÚ(BàC)
= ØAÚØBÚC=
D®C
= ØDÚC
Формулы G
и H остаются без
изменения.
в. Привести посылки и заключение к базисам {Ø,
&} и {Ø, Ú}:
F = Aà(BàC)
= ØAÚØBÚC
= Ø(ØØA&Ø(ØBÚC))
= Ø(A&ØØB&ØC)
=
= Ø(A&B&ØC)
(в базисе {Ø, &})
F = Aà(BàC)
= ØAÚØBÚC
(в
базисе
{Ø,
Ú})=ØDÚA
= ØDÚA=Ø
(ØØD&ØA)
= Ø(D&ØA)
(в
базисе
{Ø,
&})=ØDÚA
(в базисе {Ø, Ú})
J = DàC
= ØDÚC
= Ø (ØØD&ØC)
= Ø(D&ØC)
(в базисе {Ø, &})
J = DàC
= ØDÚC
(в базисе {Ø, Ú})
Формула H
остается без изменения.
Для посылок и заключения построить КНФ, ДНФ,
СКНФ, СДНФ:
F = Aà(BàC)
= ØAÚØBÚC
(КНФ,
ДНФ,
СКНФ)=(ØA&ØB&ØC)
Ú
(ØA&ØB&C)
Ú
(ØA&B&ØC)
Ú
(ØA&B&C)
Ú
(A&ØB&ØC)
Ú
(A&ØB&C)
Ú
(A&B&C)
(СДНФ, построенная с помощью таблицы истинности)
J= D®C
= ØDÚC
(КНФ, ДНФ, СКНФ)
J = (D&C)
Ú (ØD&C)
Ú (ØD&ØC)
(СДНФ, построенная с помощью таблицы истинности);
G=ØDÚA
(КНФ, ДНФ, СКНФ)
G = (D&ØA)
Ú (D&A)
Ú(ØD&A)
(СДНФ, построенная с помощью таблицы истинности)
Формула H
остается без изменения
Доказать истинность заключения путём построения
дерева доказательства
Рисунок 1 -дерево доказательства
Доказать истинность заключения методом
дедуктивного вывода (с построением графа дедуктивного вывода):
Рисунок 2 - Граф дедуктивного вывода
Доказать истинность заключения методом резолюции
(с построением графа вывода пустой резольвенты):
Приведем посылки и отрицание заключения к виду
КНФ:
F= A®
(B®C) = ØAÚØBÚC=ØDÚA=B
ØJ=
Ø(D®C)=
Ø(ØDÚC)=D&ØC
Рисунок 3 -Граф вывода пустой резольвенты
1.2 Выполнить задания по алгебре высказываний и
исчислению высказываний
(A®(B®C));(A®B);|-(A®C)=
A®(B®C)
G= A®B
J= (A®C)
Таблица 2 - Таблица истинности
|
A
|
B
|
C
|
B®C
|
A®(1)
|
A®B
|
A®C
|
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
В таблице истинности жирным шрифтом выделены
столбцы с посылками, а жирным и курсивом выделено заключение. Смотря на те
строчки, в которых истины все посылки одновременно (в данном случае это 1-ая,
2-ая, 3-ая, 4-ая и 8-ая строчки, которые выделены жирной рамкой), видно, что
заключение также истинно. Поэтому можно сделать вывод, что данное заключение
выводимо из данного множества посылок.
Упростить посылки и заключения, т.е. привести их
к базису {Ø, &, Ú}
с минимальным числом операций:
F = A®
(B®C) = ØAÚ(BàC)
= ØAÚØBÚC=
A®B=ØAÚB=
(A®C)
=ØAÚC
Привести посылки и заключение к базисам {Ø,
&} и {Ø, Ú}:
F = Aà(BàC)
= ØAÚØBÚC
= Ø(ØØA&Ø(ØBÚC))
= Ø(A&ØØB&ØC)
=
= Ø(A&B&ØC)
(в базисе {Ø, &})
F = Aà(BàC)
= ØAÚØBÚC
(в
базисе
{Ø,
Ú})=
A®B=ØAÚB=Ø
(ØØA&ØB)
= Ø(A&ØB)
(в
базисе
{Ø,
&})= A®B=ØAÚB
(в
базисе
{Ø,
Ú})=
(A®C)
=ØAÚC
=Ø (ØØA&ØC)
= Ø(A&ØC)
(в
базисе
{Ø,
&})= (A®C) =ØAÚC
(в
базисе
{Ø,
Ú})
Для посылок и заключения построить КНФ, ДНФ,
СКНФ, СДНФ:
F = Aà(BàC)
= ØAÚØBÚC
(КНФ,
ДНФ,
СКНФ)=(A&B&C)
Ú (A&B&ØC)
Ú (A&ØB&C)
Ú (A&ØB&ØC)
Ú (ØA&B&C)
Ú (ØA&B&ØC)
Ú (ØA&ØB&ØC)
(СДНФ, построенная с помощью таблицы истинности)
J= A®B=
ØAÚB
(КНФ,
ДНФ,
СКНФ)=(A&B)Ú(A&ØB)Ú(ØA&B)
(СДНФ, построенная с помощью таблицы истинности);
J= (A®C)
=ØAÚC
(КНФ,
ДНФ,
СКНФ)=(A&C)Ú(A&ØC)Ú(ØA&ØC)
(СДНФ, построенная с помощью таблицы истинности)
Доказать истинность заключения путём построения
дерева доказательства
1) {A→(B→С)}
| A→(B→С)
{A} | A
{ A→(B→C),
A}| A→(B→С)
{ A→(B→C),
A}| A
{ A→(B→C),
A}| B→С
{A→B}
| A→B
{A} |- A
{A→B,A}
|- A→B
{A→B,A}
|- A
{A→B,A}
|- B
) { A→(B→C),
A}| B→С
{A→B,A}
|- B
{ A→(B→C),
A, A→B}
|- B→С { A→(B→C),
A, A→B}
|- B
{ A→(B→C),
A→B}
|- С
{ A→(B→C),
A→B}
|- A→С
Рисунок 4 -Дерево доказательства
Доказать истинность заключения методом
дедуктивного вывода (с построением графа дедуктивного вывода):
Построим граф дедуктивного вывода.
Рисунок 5 - Граф дедуктивного вывода
Приведем посылки и отрицание заключения к виду
КНФ:
Рисунок 6 - Граф вывода пустой резольвенты
2 Логика предикатов
2.1 Выполнить задание по алгебре предикатов и
исчислению предикатов:
F = "x
(¬A(x)® $y(B(y)))→
(¬B(y)→A(x))
Привести выражение к виду ПНФ
F = "x
(¬A(x)® $y(B(y)))→
(¬B(y)→A(x))=
=¬( "x
(A(x) V $y(B(y)))) V(B(y) V
A(x))=
=$m"n
(¬A(m) &¬B(n)) V (B(y) V A(x))=
=$m"n
((¬A(m)V B(y) V A(x)) & (¬B(n) V B(y) V A(x)))
Привести выражение к виду ССФ
Для приведения к виду ССФ воспользуемся
алгоритмом Сколема, поэтому будут проведены следующие замены:
m = a,
где a - предметная
постоянная
В результате получится следующее выражение:
F= "n
(¬A(a) V B(y) V A(x)) & (¬B(n) V B(y) V A(x))
в. Доказать истинность заключения методом
дедуктивного вывода (с построением графа дедуктивного вывода):
Рисунок 7-Граф дедуктивного вывода
Доказать истинность заключения методом резолюции
(с построением графа вывода пустой резольвенты)
F = "x
(¬A(x)® $y(B(y)))=
"x
(A(x) V $y(B(y)))=
="x
(A(x) V B(f(x)))
ØN = Ø(ØB(y)
®A(x))=ØB(x)&ØA(x)
Д= { A(x) V B(f(x)),
ØB(x),ØA(x)}
Построим граф вывода пустой резольвенты:
Рисунок 8 -Граф вывода пустой резольвенты
2.2 Выполнить задание по алгебре предикатов и
исчислению предикатов:
F="x(A(x)
→B(x))& $y(B(x) →C(y))&
$z(C(y) →D(z))
Привести выражение к виду ПНФ
F="x(A(x)
→B(x))& $y(B(x) →C(y))&
$z(C(y) →D(z))=
="v(Ø
A(x) V B(x))& $y(Ø
B(x) VC(y))& $z(Ø
C(y) V D(z))=
="v$w$z
((Ø
A(v) V B(v))& (Ø B(x) VC(w))& (Ø
C(y) V D(z))
Привести выражение к виду ССФ
Для приведения к виду ССФ воспользуемся
алгоритмом Сколема, поэтому будут проведены следующие замены:
v = a,
где a - предметная
постоянная
w = b,
где b - предметная
постоянная
t = c,
где c - предметная
постоянная
В результате получится следующее выражение:
F= ((Ø
A(F(v)) V B(F(v)))& (Ø B(x) VC(n))& (Ø
C(y) V D(F(v)))
Доказать истинность заключения методом
дедуктивного вывода (с построением графа дедуктивного вывода):
F="x(A(x)
→B(x))& $y(B(x) →C(y))&
$z(C(y) →D(z))
Если
A=B=C=D=1=B=C=D=0=0,B=1,C=1,D=1=0,B=0,C=1,D=1=0,B=0,C=0,D=1 , то
F=1
Доказать истинность заключения методом резолюции
(с построением графа вывода пустой резольвенты)
F="x(A(x)
→B(x))& $y(B(x) →C(y))&
$z(C(y) →D(z))
Если
A=B=C=D=1=B=C=D=0=0,B=1,C=1,D=1=0,B=0,C=1,D=1=0,B=0,C=0,D=1 , то
F=1
3 Реляционная алгебра
3.1 Выполнить следующие бинарные операции и
составить результирующие таблицы.
1) (r1Èr2)
) (r1Çr2)
) (r1
\ r2)
) Выполнить заданную композицию операций
Таблица 3 - Таблица отношения r1
|
А1
|
А2
|
А5
|
А6
|
|
a3
|
b4
|
3
|
4
|
|
а4
|
b1
|
4
|
1
|
|
a2
|
b2
|
3
|
2
|
|
a3
|
b3
|
2
|
1
|
А1А2А5А6
|
|
|
|
|
a1
|
b2
|
1
|
2
|
|
a2
|
b3
|
2
|
3
|
|
a2
|
b2
|
3
|
2
|
|
a3
|
b3
|
2
|
1
|
Таблица 5 - Объединение r1
и r2
|
А1
|
А2
|
А5
|
А6
|
|
a3
|
b4
|
3
|
4
|
|
а4
|
b1
|
4
|
1
|
|
a2
|
b2
|
3
|
2
|
|
a3
|
b3
|
2
|
1
|
|
a1
|
b2
|
1
|
2
|
Таблица 6 - Пересечение r1
и r2
|
A1
|
A2
|
A5
|
A6
|
|
a2
|
b2
|
3
|
2
|
|
a3
|
b3
|
2
|
1
|
Таблица 7 - Вычитание из r1
r2
|
А1
|
А2
|
А5
|
А6
|
|
a3
|
b4
|
3
|
4
|
|
а4
|
b1
|
4
|
1
|
r1>q<r2
,r1A5=r2A6
Таблица 8- Тета соединение r1
и r2
|
r1.А1
|
r1.А2
|
r1.А5
|
r1.А6
|
r2.А1
|
r2.А2
|
r2.А5
|
r2.А6
|
|
a3
|
b4
|
3
|
4
|
a2
|
b3
|
2
|
3
|
|
a2
|
b2
|
3
|
2
|
a2
|
b3
|
2
|
3
|
|
a3
|
b3
|
2
|
1
|
a1
|
b2
|
1
|
2
|
|
a3
|
b3
|
2
|
1
|
a2
|
b2
|
3
|
2
|
Π (r1A1,r1А2,r1А5,r2А6)
(r1>q<r2 ,r1A5=r2A6)
Таблица 9 - Проекция отношений r1
и r2
|
r1.А1
|
r1.А2
|
r1.А5
|
r2.А6
|
|
a3
|
b4
|
3
|
3
|
|
a2
|
b2
|
3
|
3
|
|
a3
|
b3
|
2
|
2
|
|
a3
|
b3
|
2
|
2
|
3.2 Выполнить следующие бинарные операции и
составить результирующие таблицы
1) (r1Èr2)
) (r1Çr2)
) (r1
\ r2)
Таблица 10 - Таблица отношения r1
|
A3
|
A4
|
A7
|
A8
|
|
c1
|
d2
|
1
|
2
|
|
c1
|
d2
|
2
|
3
|
|
c1
|
d1
|
2
|
1
|
|
c2
|
d2
|
1
|
4
|
Таблица 11- Таблица отношения r2
|
A3
|
A4
|
A7
|
A8
|
|
C3
|
D4
|
3
|
4
|
|
c4
|
d1
|
4
|
1
|
|
c1
|
d1
|
2
|
1
|
|
c2
|
d2
|
1
|
4
|
Таблица 12 - Объединение r1
и r2
|
A3
|
A4
|
A7
|
A8
|
|
c1
|
d2
|
1
|
2
|
|
c1
|
d2
|
2
|
3
|
|
c1
|
d1
|
2
|
1
|
|
c2
|
d2
|
1
|
4
|
|
c3
|
d4
|
3
|
4
|
|
c4
|
d1
|
4
|
1
|
Таблица 13 - Пересечение r1
и r2
|
A3A4A7A8
|
|
|
|
|
c1
|
d1
|
2
|
1
|
|
c2
|
d2
|
1
|
4
|
Таблица 14 - Вычитание из r1
r2
|
A3A4A7A8
|
|
|
|
|
c1
|
d2
|
1
|
2
|
|
c1
|
d2
|
2
|
3
|
4) r1>q<r2,
d(A7>=2),
r1.A7=r2.A7=A7
Таблица 15- Тета соединение r1
и r2
|
r1.А3
|
r1.А4
|
r1.А7
|
r1.А8
|
r2.А3
|
r2.А4
|
r2.А7
|
r2.А8
|
|
c1
|
d2
|
1
|
2
|
c2
|
d2
|
1
|
4
|
|
c1
|
d2
|
2
|
3
|
c1
|
d1
|
2
|
1
|
|
c1
|
d1
|
2
|
1
|
c1
|
d1
|
2
|
1
|
|
c2
|
d2
|
1
|
4
|
c2
|
d2
|
1
|
4
|
d((r1>q<r2
r1.A7=r2.A7=A7 d(r1.A3)=c1)
Таблица 16 - Таблица выбора кортежей r1
и r2
|
r1.А3
|
r1.А4
|
r1.А7
|
r1.А8
|
|
c1
|
d1
|
2
|
3
|
|
c1
|
d1
|
2
|
3
|
|
c1
|
d1
|
2
|
3
|
|
c1
|
d1
|
2
|
1
|
|
c1
|
d1
|
2
|
1
|
|
c1
|
d1
|
2
|
1
|
Заключение
доказательство
истинность дедуктивный бинарный
Вместе с развитием вычислительных систем,
стремительно развиваются и другие отрасли цифрового мира. С каждым днем
цифровые технологии все больше входят в нашу жизнь. И уже сложно представить
себе окружающий мир без различных цифровых устройств, которые с каждой секундой
появляются все новые и новые, и становятся все интеллектуальнее и
интеллектуальнее.
Цель данной курсовой была достигнута.
В работы решены все поставленные задачи, такие
как, ознакомление с алгеброй высказываний и исчислением высказываний,
рассмотрение алгебры предикатов и исчисления предикатов, изучение реляционной
алгебры.
В ходе работы над курсовой работой была изучена
научная и учебная литература по теме «Математическая логика и теория
алгоритмов» и изучены материалы Интернет-ресурсов.
Литература
) Олькина
Е. В. Методические указания по оформлению пояснительных записок к дипломным,
курсовым проектам (работам) и отчетов по практикам в соответствии с требованиями
государственных стандартов./ Е. В. Олькина. - Орёл: Полиграфическая база
ОрёлГТУ, 2011. - 54с. -
50 экз.
) Пономарев
В.Ф. Математическая логика. часть 1. Логика высказываний. Логика предикатов.
Учебное пособие./[Текст] В.Ф. Пономарев - Калининград: КГТУ, 2009. - 140с.
3) Пономарев
В.Ф. Математическая логика. часть 2. Логика реляционная. Логика нечеткая.
Учебное пособие./ В.Ф. Пономарев - Калининград:
КГТУ, 2011.
Похожие работы на - Методы решений задач логики высказываний, логики предикатов и реляционной логики
|