Алгебра логики высказываний
Содержание
Введение
. Логика
высказываний
. Логика
предикатов
. Реляционная
логика
. Построение
таблицы истинности для логической формулы
.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.
Рисунок 6 - Граф вывода пустой резольвенты
2. Логика
предикатов
Рассмотрим вариант 19.
а.
Привести выражение к виду ПНФ
б.
Привести выражение к виду ССФ. Для приведения к виду ССФ воспользуемся
алгоритмом Сколема, поэтому будут проведены следующие замены:
Для
приведения к виду ССФ воспользуемся алгоритмом Сколема, поэтому будут проведены
следующие замены:
=a,
где
a - предметная постоянная
В
результате получится следующее выражение:
в. Доказать истинность заключения методом дедуктивного вывода (с
построением графа дедуктивного вывода):
Представим нашу формулу в следующем виде:
Построим
граф дедуктивного вывода для доказательства выводимости заключения из данного
множества посылок:
Рисунок 7 - Граф дедуктивного вывода
г. Доказать истинность заключения методом резолюции (с построением графа
вывода пустой резольвенты)
Построим граф вывода пустой резольвенты, представленный на рисунке 8.
Рисунок 8 - Граф вывода пустой резольвенты
Рассмотрим вариант 49.
а.
Привести выражение к виду ПНФ
б.
Привести выражение к виду ССФ Для приведения к виду ССФ воспользуемся
алгоритмом Сколема, поэтому будут проведены следующие замены:
с=f(z),
где f(z) - предметная постоянная
В результате получится следующее выражение:
в. Доказать истинность заключения методом дедуктивного вывода (с
построением графа дедуктивного вывода):
Представим формулу в следующем виде:
Построим
граф дедуктивного вывода для доказательства выводимости заключения из данного
множества посылок:
Рисунок 9 -Граф дедуктивного вывода
г. Доказать истинность заключения методом резолюции (с построением графа
вывода пустой резольвенты)
Построим
граф вывода пустой резольвенты, представленный на рисунке 10.
Рисунок 10 - Граф вывода пустой резольвенты
3.
Реляционная логика
Рассмотрим вариант 19.
В данном подразделе курсовой работы, бинарные операции и составление
результирующих таблиц, будут выполнятся над двумя отношениями заданными
следующими условиями: r1: (3,1), (4,2), (7,5), (8,8), r2: (3,3), (4,4), (7,5), (8,8).
Составление отношения r1 и r2 получается из
заданного по условию отношения путем удаления соответствующих заданию пар
элементов (столбец, строка).
В результате данных операций получаются отношения, представленные в
таблицах 3 и 4.
предикат логический формула алгоритм
Таблица 3 - Отношение r1
Таблица
4 - Отношение r2
|
r1
|
|
A1
|
A2
|
A5
|
A6
|
|
а3
|
b4
|
3
|
4
|
|
а4
|
b1
|
4
|
1
|
b2
|
3
|
2
|
|
а3
|
b3
|
2
|
1
|
|
r2
|
|
|
A1
|
A2
|
A5
|
A6
|
|
|
a1
|
b2
|
1
|
2
|
|
|
a2
|
b3
|
2
|
3
|
|
|
a2
|
b2
|
3
|
2
|
|
|
a3
|
b3
|
2
|
1
|
|
|
|
|
|
|
|
|
|
а. r’= r1
r2
В результате операции объединения получается отношение, представленное в
таблице 5.
Таблица 5 - Результат выполнения операции r’= r1r2
|
r’
|
|
A1
|
A2
|
A5
|
A6
|
|
а3
|
b4
|
3
|
4
|
|
а4
|
b1
|
4
|
1
|
|
а2
|
b2
|
3
|
2
|
|
а3
|
b3
|
2
|
1
|
|
a1
|
b2
|
1
|
2
|
|
a2
|
b3
|
2
|
3
|
б. r’= r1
r2
В результате операции пересечения получается отношение, представленное в
таблице 6.
Таблица 6 - Результат выполнения операции r’= r1r2
|
r’
|
|
A1
|
A2
|
A5
|
A6
|
|
а2
|
b2
|
3
|
2
|
|
а3
|
b3
|
2
|
1
|
в. r’= r1 \ r2
В результате операции разности получается отношение, представленное в
таблице 7.
Таблица 7 - Результат выполнения операции r’= r1 \ r2
|
r’
|
|
A1
|
A2
|
A5
|
A6
|
|
а3
|
b4
|
3
|
4
|
|
а4
|
b1
|
4
|
1
|
г. Выполнить заданную композицию операций
В данном пункте требует выполнить следующую композицию операций:
r’= π(r1.A1, r2.A2, r1.A5,
r2.A6)(r1>Θ<r2, r1.A5=r2.A6).в
Данное задание представляет собой композицию двух операций, поэтому для
ее выполнения требуется получить сначала промежуточное отношение,
представляющее собой результат выполнения операции условного соединения над
отношениями r1 и r2. Результирующее отношение представлено в таблице 8. После
этого необходимо выполнить операцию проекции над полученным отношением, выбрав
заданные по условию операции атрибуты отношения. Результат выполнения операции
проекции представлен в таблице 9.
Таблица 8 - Результат выполнения операции r’= r1>Θ<r2, r1.A5=r2.A6
|
r’
|
|
r1.A1
|
r1.A2
|
r1.A5
|
r1.A6
|
r2.A1
|
r2.A2
|
r2.A5
|
r2.A6
|
|
a3
|
b4
|
3
|
4
|
a2
|
b3
|
2
|
3
|
|
a2
|
b2
|
3
|
2
|
a2
|
b3
|
2
|
3
|
|
a3
|
b3
|
2
|
1
|
a1
|
b2
|
1
|
2
|
Таблица 9 - Результат выполнения операции r’= π(r1.A1, r2.A2, r1.A5, r2.A6)(r1>Θ<r2, r1.A5=r2.A6)
|
r’
|
|
r1.A1
|
r1.A5
|
r2.A2
|
r2.A6
|
|
a3
|
3
|
b3
|
3
|
|
a2
|
3
|
b3
|
3
|
|
a3
|
2
|
b2
|
2
|
Рассмотрим вариант 49
В данном подразделе курсовой работы, бинарные операции и составление
результирующих таблиц будут выполнятся над двумя отношениями заданными
следующими условиями: r1: (1,1), (2,2), (5,7), (6,8), r2: (1,2), (2,5), (5,7), (6,8).
Составление отношения r1 и r2 получается из
заданного по условию отношения путем удаления соответствующих заданию пар
элементов (столбец, строка).
В результате данных операций получаются отношения, представленные в
таблицах 10 и 11.
Таблица 10 - Отношение r1
Таблица 11 -
Отношение r2
|
r1
|
|
A3
|
A4
|
A7
|
A8
|
|
с1
|
d2
|
1
|
2
|
|
с2
|
d3
|
2
|
3
|
|
с1
|
d1
|
2
|
1
|
|
с2
|
d2
|
1
|
4
|
|
r2
|
|
A3
|
A4
|
A7
|
A8
|
|
c3
|
d4
|
3
|
4
|
|
c1
|
d2
|
1
|
2
|
|
c2
|
d3
|
2
|
3
|
|
c2
|
d2
|
1
|
4
|
а. r’= r1r2
В результате операции объединения получается отношение, представленное в
таблице 12.
Таблица 12 - Результат выполнения операции r’= r1r2
|
r’
|
|
A3
|
A4
|
A7
|
A8
|
|
с1
|
d2
|
1
|
2
|
|
с2
|
d3
|
2
|
3
|
|
с1
|
d1
|
2
|
1
|
|
с2
|
d2
|
1
|
4
|
|
c3
|
d4
|
3
|
4
|
б. r’= r1r2
В результате операции пересечения получается отношение, представленное в
таблице 13.
Таблица 13 - Результат выполнения операции r’= r1r2
|
r’
|
|
A3
|
A4
|
A7
|
A8
|
|
с1
|
d2
|
1
|
2
|
|
с2
|
d3
|
2
|
3
|
|
с2
|
d2
|
1
|
4
|
в. В результате операции разности получается отношение, представленное в
таблице 14.
Таблица 14 - Результат выполнения операции r’= r1 \ r2
г. Выполнить заданную композицию операций
В данном пункте требует выполнить следующую композицию операций: r’= δ((r1>Θ<r2, (r1.A7=r2.A7)), d(r1.A3)=c1)
Данное задание представляет собой композицию двух операций, поэтому для
ее выполнения требуется получить сначала промежуточное отношение,
представляющее собой результат выполнения операции условного соединения над
отношениями r1 и r2. Результирующее отношение представлено в таблице 15. После
этого необходимо выполнить операцию выборки над полученным отношением, выбрав
заданные по условию операции кортежи отношения. Результат выполнения операции
выборки представлен в таблице 16.
Таблица 15 - Результат выполнения операции r’= r1>Θ<r2, r1.A7=r2.A7
|
r’
|
|
r1.A3
|
r1.A4
|
r1.A7
|
r1.A8
|
r2.A3
|
r2.A4
|
r2.A7
|
r2.A8
|
|
с1
|
d2
|
1
|
2
|
с1
|
d2
|
1
|
2
|
|
с1
|
d2
|
1
|
2
|
с2
|
d2
|
1
|
4
|
|
c2
|
d3
|
2
|
3
|
с2
|
d3
|
2
|
3
|
|
с1
|
d1
|
2
|
1
|
с2
|
d3
|
2
|
3
|
|
c2
|
d2
|
1
|
4
|
с1
|
d2
|
1
|
2
|
|
c2
|
d2
|
1
|
4
|
с2
|
d2
|
1
|
4
|
Таблица 16 - Результат выполнения операции r’= δ((r1>Θ<r2, (r1.A7=r2.A7)), d(r1.A3)=c1)
|
r’
|
|
r1.A3
|
r1.A4
|
r1.A7
|
r1.A8
|
r2.A3
|
r2.A4
|
r2.A7
|
r2.A8
|
|
с1
|
d2
|
1
|
2
|
с1
|
d2
|
1
|
2
|
|
с1
|
d2
|
1
|
2
|
с2
|
d2
|
1
|
4
|
|
с1
|
d1
|
2
|
1
|
с2
|
d3
|
2
|
3
|
. Построение
таблицы истинности для логической формулы
.1
Обоснование выбора структур данных
Для решения нашей задачи можно воспользоваться такими структурами данных
как строки, ведь именно в них помещается исходное выражение и постфиксная форма
выражения.
4.2 Описание
алгоритма решения задачи
Алгоритм построения таблицы истинности для произвольной логической
формулы.
. Ввод пользователем произвольной логической формулы.
. Перевод введенной формулы из инфиксной формы записи в префиксную
форму записи.
. Заполнение таблицы истинности.
. Вывод таблицы истинности на экран.
.3 Описание
пользовательского интерфейса
Пользовательский интерфейс программы представляет окно командной строки,
для ввода логической формулы представлен на рисунке 11
Рисунок 11 - окно ввода формулы
Результаты работы программы представлены на рисунке 12 и на рисунке 13.
Рисунок 12 - пример выполнения программы
Рисунок 13 - пример выполнения программы
Заключение
В процессе выполнения данной работы были изучены различные литературные
источники, решены задания по математической логике на различные темы, а также
была реализована программа создания таблицы истинности для произвольной
логической формулы.
Цель работы, заключавшуюся в закреплении знаний по математической логике
и их применении, можно считать успешно выполненной, однако необходимо
дополнительное изучение предмета математической логики и различных литературных
источников в будущем с целью дальнейшего накопления знаний и их использования
на практике при решении различных задач.
Список
литературы
1. Игошин,
В.И. Математическая логика и теория алгоритмов :учеб. пособие для вузов /
Владимир Иванович Игошин . - М. :Академия , 2004. - 446, [1] с. (Высшее
профессиональноеобразование).
2. Кондаков,
Н. И. Введение в логику: [Текст] / Н. И. Кондаков. - М.: Наука, 1967. - 467 с.
. Лавров,
И. А. Задачи по теории множеств, математической логике и теории алгоритмов/ И.
А. Лавров, Л. Л. Максимова. -М.:Физматлит, 2002. - 240 с.
. Лихтарников,
Л.М. Математическая логика: [Текст] / Л.М. Лихтарников, Т.Г. Сукачева. - СПб.:
Лань, 1999. - 288 с.
5. Никольская,
И.Л. Математическая логика. Учебник / И.Л. Никольская. - М.: Высшая школа,
1981. - 127с.
6. Шапорев,
С. Д.Математическая логика. Курс лекций и практических занятий: Учебник/С.Д.
Шапорев. - СПб.: БХВ-Петербург, 2005. - 416 с.
Приложение А
(обязательное)
Листинг
программы
Program Tabl_ist;
uses crt;BoolToInt : array [ boolean ] of integer = ( 0, 1 )
; //Перевод булевых
значений в числа: array [ 0..1 ] of boolean = (
false, true ) ; //Перевод чисел в булево значение
//Элемент стека= ^Elem;= record: string;:PElem;;_ : PElem; //Указатель на вершину
стека: string; //Строка, в которую помещается исходное выражение_str:string;
//Вспомогательная строка_str : string; //Строка содержащая постфиксную форму
выражения_per : integer; //Количество переменных в выражении:integer; // 2 в
степени kol_per хранит количество строк в таблице: array of string; //каждый
элемент это отдельное подвыражение из основного выражения: array [,] of
integer; // матрица, в которой будет храниться таблица истиности
//Приорететы выполнения операцийprice(ch:string):integer;
beginch[1] of
'(' : price:=0;
'+' : price:=3;
'=' : price:=1;
'>' : price:=2;
'!' : price:=5;
'*' : price:=4;;;
//Занесение элемента в стекpush(ch:string);p:PElem;(p);^.value:=ch;^.next:=Top_;_:=p;;
//Чтение элемента из стекаpop():string;p:PElem;:=Top_^.value;:=Top_;_:=Top_^.next;(p);;
//Проверка на наличие в стеке элементов
function void(): boolean;:= Top_ = nil;
end;
//Заполнение таблици истинности с помощью постфиксной формы выражения
procedure zapolnenie();,j,stl1,stl2:
integer;pr(z:string);(cap,Length(cap)+1);(tabl,(Length(tabl) div
pow)+1,pow);:=StrToInt(pop());:=StrToInt(pop());(IntToStr(High(cap)));[High(cap)]:='('+cap[stl1]+z+cap[stl2]+')';;i:=1
to Length(post_str) dopost_str[i] of
'A'..'Z' :(IntToStr(Pos(post_str[i],help_str)-1));;
'+' :(' + ');j:=0 to pow-1
do[High(cap),j]:=BoolToInt[(IntToBool[tabl[stl2,j]]) or
(IntToBool[tabl[stl1,j]])];;
'*' :(' * ');j:=0 to pow-1
do[High(cap),j]:=BoolToInt[(IntToBool[tabl[stl2,j]]) and
(IntToBool[tabl[stl1,j]])];;
'=' :(' = ');j:=0 to pow-1 do[High(cap),j]:=BoolToInt[((not
(IntToBool[tabl[stl1,j]])) or (IntToBool[tabl[stl2,j]])) and ((not
(IntToBool[tabl[stl2,j]])) or (IntToBool[tabl[stl1,j]]))];;
'>' :(' > ');j:=0 to pow-1
do[High(cap),j]:=BoolToInt[(not (IntToBool[tabl[stl1,j]])) or (IntToBool[tabl[stl2,j]])];;
'!'
:(cap,Length(cap)+1);(tabl,Length(tabl)+1,pow);:=StrToInt(pop());(IntToStr(High(cap)));[High(cap)]:='!'+cap[stl1];j:=0
to pow-1 do[High(cap),j]:=BoolToInt[not(IntToBool[tabl[stl1,j]])];
end;;;;
//Реализаця алгоритма Дейкстры для перевода выражения в постфиксную форму
function
Deykstri():boolean;:string;:boolean;:integer;:=false;i:=1 to Length(str)
do:=false;str[i] of
'A'..'Z'
:_str:=Concat(post_str,str[i]);pos(str[i],help_str)=0 then begin inc(kol_per);
help_str:=Concat(help_str,str[i]); end;;
'*','+','=','!','>' ::=true;void then push(str[i])
elseflag dovoid then(str[i]);;;:=pop();price(str[i])>=price(ch)
then(ch);(str[i]);:=false;post_str:=Concat(post_str,ch);;;
'(' :('(');;
')' ::=false;not void then:=pop();ch<>'(' then
post_str:=Concat(post_str,ch);flag:=true;(ch='(') or flag;:=flag;flag then
begin writeln('Ошибка при расстановке скобок! Проверьте
выражение и попробуйте снова'); Deykstri:=true; end;
end;;;not flag thennot void do:=pop(); ch='(' then begin writeln('Ошибка при расстановке скобок!
Проверьте выражение и попробуйте снова'); Deykstri:=true; break;
end
else post_str:=post_str+ch;
end;;
//Заполнение матрици начальными значениями
procedure start_values();,j,k:integer;:boolean;i:=0 to
kol_per-1 do[i]:=help_str[i+1];:=true;j:=0 to Round(Exp((i+1)*Ln(2)))-1 doflag
then flag:=false else flag:=true;k:=0 to pow div Round(Exp((i+1)*Ln(2)))-1
do[i,j*(pow div Round(Exp((i+1)*Ln(2))))+k]:=BoolToInt[flag];
end;;;
//Вывод таблици истинности на экран
procedure pokaz();,j: integer;i:=0 to High(cap) do
write(cap[i]+' ');();j:=0 to pow-1 doi:=0 to High(cap) do(tabl[i,j]+' ' :
Length(cap[i])+2);;();;;
//Основной код программы
writeln('Введите выражение, при этом используя следующие операции:
');('> импликация');('* конъюнкция');('+ дизъюнкция');('=
эквивалентность');('! отрицание');('Используемые переменные - {A..Z} и
{a..z}');
writeln();_str:='';:='';_str:='';_per:=0;_:=nil;(str);:=Trim(str);:=UpperCase(str);();not
Deykstri() then:=Round(Exp(kol_per*Ln(2)));(tabl, kol_per, pow);(cap,kol_per);_values();();();;('--------------------------------------');
until (false);.