Курсовая работа (т): Алгебра логики высказываний
Алгебра логики высказываний
Содержание
Введение
. Логика высказываний
. Логика предикатов
. Реляционная логика
. Построение таблицы истинности для логической формулы
.1 Обоснование выбора структур данных
.2 Описание алгоритма решения задачи
.3 Описание пользовательского интерфейса
Заключение
Список литературы
Приложение А
(обязательное) Листинг программы
Введение
Выполнение данной курсовой работы направлено на закрепление знаний и навыков, полученных в процессе изучения дисциплины, а именно алгебры логики высказываний и исчислению высказываний, алгебры логики предикатов и исчисления предикатов, реляционной логике и теории алгоритмов.
В ходе написания программы, которая реализует построение таблицы
истинности для произвольной логической формулы, были использованы знания,
полученные в ходе прохождения данного курса, и навыки программирования.
1 Логика высказываний
Рассмотрим вариант 19.
а. Построить таблицу истинности
Таблица 1 - Таблица истинности логического выражения
|
A |
B |
C |
|
|
|
|
|
|
|
|
|
2 |
F |
G |
3 |
H |
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
|
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
|
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
В таблице истинности жирным шрифтом выделены столбцы с посылками, а жирным и курсивом выделено заключение. Смотря на те строчки, в которых истины все посылки одновременно (в данном случае это первая, вторая, пятая, шестая и последняя строчка, которая выделена жирной рамкой), видно, что заключение также истинно. Поэтому можно сказать вывод, что данное заключение выводимо из данного множества посылок.
б. Упростить посылки и заключения, т.е. привести к базису 
с минимальным числом операций:
в. Упростить посылки и заключения, т.е. привести их к базису {¬, &} и {¬, ∨} с минимальным числом операций:
= ( B® ( A® C)) = ¬ B Ú (A ® C) = (¬ (B&A& ¬ C)
г.
Для посылок и заключения построить КНФ, ДНФ, СКНФ, СДНФ:
(КНФ, ДНФ, СКНФ)
(СДНФ,
построенная с помощью таблицы истинности)
(КНФ,
ДНФ, СКНФ)
(СДНФ,
построенная с помощью таблицы истинности)
(КНФ,
ДНФ, СКНФ)
(СДНФ,
построенная с помощью таблицы истинности)
д. Доказать истинность заключения путём построения дерева доказательства, представленного на рисунке 1.
Рисунок
1 - Дерево доказательства, лист 1
(1)
На
основании аксиомы имеем:
Рисунок
1 - Дерево доказательства, лист 2
е.
Доказать истинность заключения методом дедуктивного вывода (с построением графа
дедуктивного вывода):
Если
, то 
Если
, то , если 
, тогда имеем следующее выражение: 
Если
, то 
Если
, то , если 
, тогда имеем следующее выражение: 
Рисунок 2 - Граф дедуктивного вывода
ж. Доказать истинность заключения методом резолюции (с построением графа вывода пустой резольвенты):
Приведем посылки и отрицание заключения к виду КНФ:
Построим
граф вывода пустой резольвенты, представленный на рисунке 3.
Рисунок 3 - Граф вывода пустой резольвенты
Рассмотрим вариант 49.
а.
Построить таблицу истинности.
Таблица 2 - Таблица истинности суждения
|
A |
B |
C |
|
|
|
|
||||
|
|
G |
|
F |
1 |
2 |
H |
||||
|
0 |
0 |
0 |
1 |
1 |
0 |
1 |
||||
|
0 |
0 |
1 |
1 |
0 |
1 |
1 |
||||
|
0 |
1 |
0 |
1 |
1 |
1 |
1 |
||||
|
0 |
1 |
1 |
1 |
0 |
1 |
1 |
||||
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|||
|
1 |
0 |
1 |
0 |
0 |
1 |
1 |
|
|||
|
1 |
1 |
0 |
1 |
0 |
1 |
1 |
|
|||
|
1 |
1 |
1 |
1 |
0 |
1 |
1 |
|
|||
В таблице истинности жирным шрифтом выделены столбцы с посылками, а жирным и курсивом выделено заключение. Смотря на те строчки, в которых истины все посылки одновременно (в данном случае это третья, четвертая, седьмая и последняя строчка, которая выделена жирной рамкой), видно, что заключение также истинно. Поэтому можно сказать вывод, что данное заключение выводимо из данного множества посылок.
б. Упростить посылки и заключения, т.е. привести к базису с минимальным числом операций:
Формула G остается без изменения.
в. Упростить посылки и заключения, т.е. привести их к базису {¬, &} и {¬, ∨}с минимальным числом операций:
Формула G остается без изменения.
г. Для посылок и заключения построить КНФ, ДНФ, СКНФ, СДНФ:
(КНФ,
ДНФ, СКНФ)
(СДНФ,
построенная с помощью таблицы истинности)
(КНФ,
ДНФ, СКНФ)
(СДНФ,
построенная с помощью таблицы истинности)
Формула G остается без изменения.
д.
Доказать истинность заключения путём построения дерева доказательства,
представленного на рисунке 4.
Рисунок 4 -Дерево доказательства
е. Доказать истинность заключения методом дедуктивного вывода (с построением графа дедуктивного вывода):
Построим
граф дедуктивного вывода, представленный на рисунке 5.
Рисунок
5 - Граф дедуктивного вывода
ж. Доказать истинность заключения методом резолюции (с построением графа вывода пустой резольвенты):
Приведем
посылки и отрицание заключения к виду КНФ:
Построим граф вывода пустой резольвенты, представленный на рисунке 6.
