Курсовая работа (т): Алгебра логики высказываний

б. r’= r₁r₂

В результате операции пересечения получается отношение, представленное в таблице 13.

Таблица 13 - Результат выполнения операции r’= r₁r₂

в. В результате операции разности получается отношение, представленное в таблице 14.

Таблица 14 - Результат выполнения операции r’= r₁ \ r₂

г. Выполнить заданную композицию операций

В данном пункте требует выполнить следующую композицию операций: r’= δ((r₁>^Θ<r₂, (r₁.A₇=r_2.A₇)), d(r_1.A3)=c₁)

Данное задание представляет собой композицию двух операций, поэтому для ее выполнения требуется получить сначала промежуточное отношение, представляющее собой результат выполнения операции условного соединения над отношениями r₁ и r₂. Результирующее отношение представлено в таблице 15. После этого необходимо выполнить операцию выборки над полученным отношением, выбрав заданные по условию операции кортежи отношения. Результат выполнения операции выборки представлен в таблице 16.

Таблица 15 - Результат выполнения операции r’= r₁>^Θ<r₂, r₁.A₇=r_2.A₇

Таблица 16 - Результат выполнения операции r’= δ((r₁>^Θ<r₂, (r₁.A₇=r_2.A₇)), d(r_1.A3)=c₁)

. Построение таблицы истинности для логической формулы

.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);.