Введення
У середині 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 - Таблиця істинності
ABCDB ® CA ® (1)? D? AD ® CH(1)FGJ00001111000111000010111100111101010001110101010001101111011111011000111110011110101011111011111111000011110100101110111111111111
У таблиці істинності жирним шрифтом виділено стовпці з посилками, а жирним і курсивом виділено висновок. Дивлячись на ті рядки, в яких істини всі посилки одночасно (в даному випадку це п'ята, сьома, п'ятнадцятий і шістнадцята строчки, які виділені жирною рамкою), видно, що висновок також істинно. Тому можна зробити висновок, що даний висновок виводиться з даної множини посилок.
Спростити посилки і укладання, тобто привести їх до базису {? , Amp ;,? } З мінімальним числом операцій:
F=A ® (B ® C) =? A? (B? C) =? A ?? B? C=D ® C =? D? C
Формули G і H залишаються без зміни.
в. Привести посилки і висновок до базисам {? , Amp;} і {? ,? }:
F=A? (B? C) =? A ?? B? C =? (?? A amp;? (? B? C)) =? (A amp; ?? B amp;? C)=
=? (A amp; B amp;? C) (в базисі {?, Amp;})
F=A? (B? C) =? A ?? B? C (в базисі {?,?}) =? D? A =? D? A =? (?? D amp;? A) =? (D amp;? A) (в базисі {?, Amp;}) =? D? A (в базисі {?,?})
J=D? C =? D? C =? (?? D amp;? C) =? (D amp;? C) (в базисі {?, Amp;})
J=D? C =? D? C (в базисі {?,?})
Формула H залишається без зміни.
Для посилок і висновку побудувати КНФ, ДНФ, СКНФ, СДНФ:
F=A? (B? C) =? A ?? B? C (КНФ, ДНФ, СКНФ)=(? A amp;? B amp;? C)? (? A amp;? B amp; C)? (? A amp; B amp;? C)? (? A amp; B amp; C)? (A amp;? B amp;? C)? (A amp;? B amp; C)? (A amp; B amp; C) (СДНФ, побудована за допомогою таблиці істинності)
J=D ® C =? D? C (КНФ, ДНФ, СКНФ)
J=(D amp; C)? (? D amp; C)? (? D amp;? C) (СДНФ, побудована за допомогою таблиці істинності);
G =? D? A (КНФ, ДНФ, СКНФ)
G=(D amp;? A)? (D amp; A)? (? D amp; A) (СДНФ, побудована за допомогою таблиці істинності)
Формула H залишається без зміни
Довести істинність висновку шляхом побудови дерева докази
Малюнок 1 -дерево докази
Довести істинність висновку методом дедуктивного виводу (з побудовою графа дедуктивного виводу):
Малюнок 2 - Граф дедуктивного виведення
Довести істинність висновку методом резолюції (з побудовою графа виведення порожній резольвенти):
Наведемо посилки і заперечення укладення до виду КНФ:
F=A ® (B ® C) =? A ?? B? C =? D? A=B
? J =? (D ® C) =? (? D? C)=D amp; ? C
Малюнок 3 -Граф виведення порожній резольвенти
1.2 Виконати завдання з алгебри ...
