Курсовая работа: Методы решений задач логики высказываний, логики предикатов и реляционной логики
В середине 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>qqq=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.