Курсовая работа: Методы решений задач логики высказываний, логики предикатов и реляционной логики

В середине XX века развитие вычислительной техники привело к появлению логических электронных элементов, логических блоков и устройств вычислительной техники, что было связано с дополнительной разработкой таких областей логики.

Дата добавления на сайт: 19 февраля 2025
Введение

В середине 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

Таблица 4- Таблица отношения r2

А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>qr1.А1r1.А2r1.А5r1.А6r2.А1r2.А2r2.А5r2.А6a3b434a2b323a2b232a2b323a3b321a1b212a3b321a2b232
Π (r1A1,r1А2,r1А5,r2А6) (r1>qr1.А1r1.А2r1.А5r2.А6a3b433a2b233a3b322a3b322
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=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>qr1.А3r1.А4r1.А7r1.А8c1d123c1d123c1d123c1d121c1d121c1d121
Заключение
доказательство истинность дедуктивный бинарный
Вместе с развитием вычислительных систем, стремительно развиваются и другие отрасли цифрового мира. С каждым днем цифровые технологии все больше входят в нашу жизнь. И уже сложно представить себе окружающий мир без различных цифровых устройств, которые с каждой секундой появляются все новые и новые, и становятся все интеллектуальнее и интеллектуальнее.
Цель данной курсовой была достигнута.
В работы решены все поставленные задачи, такие как, ознакомление с алгеброй высказываний и исчислением высказываний, рассмотрение алгебры предикатов и исчисления предикатов, изучение реляционной алгебры.
В ходе работы над курсовой работой была изучена научная и учебная литература по теме «Математическая логика и теория алгоритмов» и изучены материалы Интернет-ресурсов.
Литература

)Олькина Е. В. Методические указания по оформлению пояснительных записок к дипломным, курсовым проектам (работам) и отчетов по практикам в соответствии с требованиями государственных стандартов./ Е. В. Олькина. - Орёл: Полиграфическая база ОрёлГТУ, 2011. - 54с. - 50 экз.
)Пономарев В.Ф. Математическая логика. часть 1. Логика высказываний. Логика предикатов. Учебное пособие./[Текст] В.Ф. Пономарев - Калининград: КГТУ, 2009. - 140с.
3)Пономарев В.Ф. Математическая логика. часть 2. Логика реляционная. Логика нечеткая. Учебное пособие./ В.Ф. Пономарев - Калининград: КГТУ, 2011.

Комментарии:

Вы не можете оставлять комментарии. Пожалуйста, зарегистрируйтесь.