Курсовая работа: Комбінаторика

4. якщо хру і урz , то хрz для будь-яких х, у, z є А, тобто якщо (х, у) є Р і (у, z) є Р, то і (х, z) є Р для будь яких пар (х, у) (у, z) є А І.

Так відношення р: „ х < у у множині А = {1, 2, 3, 4, 5} є відношенням строгого порядку, тому що воно антирефлексивне, антисиметричне, транзитивне.

Відношення р називається відношенням нестрогого (часткового) порядку, якщо воно рефлексивне, антисиметричне і транзитивне.

Так, відношення „число х – дільник числа у” у множині А = {1, 2, 3, 4, 5} є відношенням часткового порядку, тому що воно транзитивне, рефлексивне і антисиметричне.

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

Відношення строгого (нестрогого) порядку називається відношенням лінійного строгого (нестрогого) порядку, якщо для будь-яких різних елементів х і у із А здійснюється одне із відношень хру або урх .

Проілюструємо сказане на прикладі. Нехай А – множина студентів групи. Р – відношення „студент х вищий за студента у”. Це відношення антирефлексивне, антисиметричне і транзитивне.

Значить, воно відношення строгого порядку. Якщо в даній множині А немає студентів однакового росту, то тоді про будь-яких двох студентів можна сказати, що або студент х вищий за у або студент у вищий студента х . Отже, відношення Р є відношенням строгого лінійного порядку.

Множина А називається лінійною упорядкованою, якщо в А введено відношення Р і для будь-якої пари (х, у) є А І, якщо х ≠ у, то хру або

урх .

Так, множина натуральних чисел лінійно упорядкована відношенням строгого порядку „менше”, тобто N = {1, 2, 3, 4, ....}

Розділ 3. СИМВОЛІКА МАТЕМАТИЧНОЇ ЛОГІКИ

§ 3. 1. Поняття висловлення

Під математичною логікою або символічною логікою розуміють логіку, що розвивається за допомогою математичних методів. Математичний апарат до логіки вперше застосував у XIX ст. англійський математик Джордж Буль.

Д. Буль (1815 – 1864 р.р.), батько відомої англійської письменниці Войнич (її чоловік був революціонером), автора роману „Овод”. Темп розвитку математичної логіки різко зростає у XIX ст. У 90-х роках ХХ ст.. математична логіка дістає широке застосування в технічних науках, наприклад, електротехніці. Зараз вона є складовою частиною теоретичного фундаменту кібернетики.

Основним поняттям математичної логіки є висловлювання. Висловлювання належить до первинних понять, воно не визначеється через інші поняття, а вводяться за допомогою опису.

Під висловлюванням розуміють будь-яке твердження , відносно якого можна з’ясувати, істинне воно чи хибне. Наприклад,

1. Діагональ квадрата не сумірна з його стороною – „і” висловлювання

2. 5 > 8 – „х” висловлення

3. О котрій годині ти повернешся вчора додому? – не є висловленням.

Висловлення позначаються малими латинськими буквами: p, q, r, s, ......

Множину усіх висловлювань, яку позначимо буквою S, ділять на дві підмножини (класи)

Т – клас усіх істинних висловлювань

F – клас усіх хибних висловлювань

Два висловлювання p і q називаються рівносильними (логічно рівними), якщо вони належать до одного й того самого класу і записують

p q

Із означення рівносильності висловлювань виникають властивості:

1. р р

2. Якщо р q , то q р – симетричність

3. Якщо р q і q r ,то р r – транзитивність

§ 3. 2. Операції над висловленнями

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

а) Логічне множення (кон’юнкція)

Логічним добутком (кон’юнкцією) двох висловлень p і q називається

таке висловлення „p і q ”, яке істинне тоді і тільки тоді, коли p і q одночасно істинні. Позначається: p q.