На головну

 ВІДНОСИНИ |  ФОРМУЛИ логіки ВИСЛОВЛЮВАНЬ |  ФОРМАЛЬНІ СИСТЕМИ (ТЕОРІЇ) |  обчислення висловлювань |  обчислення предикатів |  Зведення формул до пропозицій |  Правило резолюції для обчислення висловлювань |  Правила резолюції для обчислення предикатів |  Спростування методом резолюції |  K-значна логіка |

І ТЕОРІЯ АЛГОРИТМІВ

  1.  I РОЗДІЛ. ТЕОРІЯ І ПРАКТИКА СОЦІАЛЬНОЇ ПСИХОЛОГІЇ
  2.  I. ТЕОРІЯ ЙМОВІРНОСТЕЙ
  3.  IV. "Економічна теорія".
  4.  V. Т. Рибо. Моторна теорія уваги.
  5.  XIII. Теорія відтворення Дестюта де Траси
  6.  XV. Е. Трейсман. Теорія інтеграції ознак.
  7.  А. Н. Леонтьєв і психологія діяльності в працях його послідовників. Теорія поетапного формування розумових дій П. Я. Гальперіна.

МАТЕМАТИЧНА ЛОГІКА

І ТЕОРІЯ АЛГОРИТМІВ

Навчальний посібник

Воронеж 2007


ГОУВПО «Воронезький державний

технічний університет"

Н. А. Ююкіна С. І. Моїсеєв Г. Ф. Федотенко

МАТЕМАТИЧНА ЛОГІКА

І ТЕОРІЯ АЛГОРИТМІВ

Затверджено Редакційно-видавничим радою

університету як навчальний посібник

Воронеж 2007

УДК 510 (075)

Ююкмн Н. А. Математична логіка і теорія алгоритмів: навч. посібник / Н. А. Ююкіна, С. І. Моїсеєв, Г. Ф. Федотенко. Воронеж: ГОУВПО «Воронезький державний технічний університет», 2007. 90 с.

У навчальному посібнику розглядаються короткі теоретичні відомості з теорії множин, бінарним відносин, алгебраїчним системам, булевим функціям, k - Значной логіці, формальним системам, формалізації поняття алгоритму і оцінки його складності.

Навчальний посібник відповідає вимогам державного освітнього стандарту вищої професійної освіти за напрямом 090100 «Інформаційна безпека», спеціальностями 090102 «Комп'ютерна безпека», спеціальності 090105 «Комплексне забезпечення інформаційної безпеки автоматизованих систем», дисципліни «Математична логіка та теорія алгоритмів»

Бібліогр .: 8 назв.

Науковий редактор д-р фіз.-мат. наук, проф. І. Л. Батаронов

Рецензенти: кафедра вищої математики Воронезького ін-

туту МВС Росії (зав. кафедрою д-р фіз.-

мат. наук, проф. В. В. Менших);

д-р фіз.-мат. наук, проф. В. Н. Нечаєв

© Ююкіна Н. А., Моісеєв С. І., Федотенко Г. Ф., 2007

© Оформлення. ГОУВПО «Воронезький

державний технічний університет », 200
 
7

ВСТУП

Даний посібник призначений для студентів ВДТУ, які навчаються за спеціальностями:

090102 - Комп'ютерна безпека;

090105 - Комплексне забезпечення інформаційної безпеки автоматизованих систем.

Дисципліна "Математична логіка і теорія алгоритмів" забезпечує набуття знань і умінь відповідно до Державного загальноосвітнім стандартом і при цьому сприяє фундаменталізації освіти, формування світогляду і розвитку логічного мислення.

Математична логіка і теорія алгоритмів є розділ математики, в якому вивчаються підстави математики, логіки і загальні властивості алгоритмів, які включають: формули алгебри висловлювань; уявлення булевих функцій формулами; критерії повноти систем булевих функцій; критерії повноти систем функцій  -значний логіки; класифікацію функцій  -значний логіки; мінімізацію булевих функцій; числення висловів і предикатів, основні підходи до формалізації поняття алгоритму; поняття про складність алгоритмів; обчислювальні алгоритми; дедуктивні процедури виведення в логіці першого порядку; принцип резолюцій для логіки висловлювань і логіки предикатів; реляционную алгебру і реляційне числення; а також виробляються практичні навички з використання вищенаведених понять.

Метою курсу є формування у студентів теоретичних знань, практичних умінь і навичок в області моделювання процесів і явищ в природознавстві і техніці з можливістю вживання математичних символів для вираження кількісних і якісних відносин об'єктів, необхідних для виконання службової діяльності в області захисту інформації на високому професійному рівні.

Досягненню даної мети служать наступні завдання:

вивчити максимально широке коло понять математичної логіки і теорії алгоритмів;

отримати навички вирішення навчальних і практичних завдань;

опанувати методами алгоритмізації;

ознайомитися з основами формальних математичних систем (теорій) і автоматичним доказом теорем;

виробити навички постановки і рішення інформаційних завдань, моделювання та аналізу інформації.

Дисципліна "Математична логіка і теорія алгоритмів" відноситься до числа прикладних математичних дисциплін. Вона ґрунтується на знаннях, набутих студентами при вивченні дисципліни "Алгебра". Знання та навички, отримані при вивченні дисципліни "Математична логіка і теорія алгоритмів", використовуються при вивченні загально і спеціальних дисциплін.


1. КОРОТКІ ВІДОМОСТІ ПРО безліч,

ВІДНОСИНАХ І АЛГЕБРАЇЧНИХ СИСТЕМАХ

1.1. ЕЛЕМЕНТИ ТЕОРІЇ МНОЖИН

1.1.1. Основні поняття

У математиці поняття множини належить до числа первинних, тобто невизначених через більш прості. Це поняття лише прояснюється, тобто дається опис його основних властивостей.

безліччю називається будь-яка сукупність певних і помітних між собою об'єктів нашої інтуїції та інтелекту, мислима, як єдине ціле. Ці об'єкти називаються елементами множини. Безлічі позначаються великими літерами латинського алфавіту, а їх елементи - малими. запис xIX означає, що елемент x належить множині X, В іншому випадку пишуть xIX.

У цьому "визначенні" сукупність предметів розглядається, як один загальний об'єкт і при цьому предмети як би збираються в один мішок, а далі працюють з цим мішком, як з єдиним цілим, не замислюючись про його зміст. Такий підхід відомий в біології, де рослини і тварини, класифікуються за видами, класами, загонам і т. Д. При цьому увага переноситься з окремих представників на загальні властивості групи, як сукупності. У мові це відбивається в словах "компанія", "зграя", "стадо" і т.д.

В "визначенні" безлічі немає ніяких обмежень на природу елементів. Це може бути безліч студентів другого курсу, безліч плям на сонці, безліч зелених яблук, безліч зірок на небі і так далі. Зауважимо, що в якості елементів множин можуть бути також безлічі. Наприклад: з одного боку, група студентів - це безліч, що складається з людей, а з іншого боку, ця група є елементом множини всіх груп в інституті.

У математиці часто використовують числові безлічі, Елементами якого є числа. Зі шкільної алгебри відомі числові безлічі N - Натуральних, Z - Цілих, Q - Раціональних, I - Ірраціональних, R - Дійсних чисел.

Геометрично безліч дійсних чисел зображується точками числової осі, тобто прямий на якій вибрано: 1) початок відліку, 2) позитивний напрямок і 3) одиниця масштабу.

Між безліччю дійсних чисел і точками числової осі існує взаємно однозначна відповідність.

безлічі точок X числовій осі називаються:

a ? x ? b - відрізком,

a - інтервалом,

a - напівінтервалів,

Всі зазначені безлічі називаються проміжками.

Всякий інтервал, що містить точку a, Називається околицею точки a.

Якщо безліч містить кінцеве число елементів, то воно називається кінцевим, А в іншому випадку - нескінченним.

Кінцеве безліч зазвичай задається перерахуванням його елементів з висновком їх у фігурні дужки, тобто

X = {x1, x2,, ..., Xn}.

Однак перелік елементів громіздко для опису великих множин і не може бути застосовано для нескінченних множин. Такі безлічі задаються за допомогою характеристичних властивостей. нехай P (x) деякий пропозицію, залежне від x, Яке може бути істинним або хибним залежно від x, Тоді запис X = {x | P (x)}, означає, що xIX тоді і тільки тоді, коли P (x) істинне твердження.

наприклад: A = {1,2} = {xIN | x <3}.

підмножиною A безлічі B (AIB) або (A міститься в B) Називається безліч A, Кожен елемент якого належить B. Графічно це зображується за допомогою кіл Ейлера, як показано на малюнку.

 
 

 безлічі A и B називаються рівними (A = B), Якщо AIB и BIA.

Безліч, що не містить жодного елемента, називається порожнім і позначається O. Сукупність усіх допустимих об'єктів в рамках розв'язуваної задачі називається універсальним безліччю і позначається U.

Сукупність усіх підмножин множини А називається безліччю-ступенем і позначається P (А), тобто P (А)= {ВcВIА}.

1.1.2. Операції над множинами

об'єднання AEB є безліч всіх елементів належать A або B. Слід мати на увазі, що існують два значення союзу або:

1) «виключає або» - або те, або інше і третього не дано;

2) "не виключає або» - то чи інше, або те й інше разом.

У визначенні об'єднання множин мається на увазі друге "що не виключає або", тобто елемент може належати тільки A, тільки B, А також одночасно цим

безлічам

Перетин множин З = ACB, Є безліч елементів належать A и B.

різниця A \ B, Є безліч, що складається з елементів A, Що не входять в безліч В.


симетрична різниця

Прямим (декартовим) твором двох множин АхВ називається безліч всіх упорядкованих пар (а, b), В яких перший елемент аIА, а другий bIВ.

ступенем безлічі А називається його пряме твір самого на себе, тобто .

доповненням безлічі A називається безліч A, Що складається з елементів універсальної множини, які не є елементами безліччю A.

 



 Схемних реалізація мінімізованої Функції |  множинами
© um.co.ua - учбові матеріали та реферати