Квантори спільності та існування. Квантори Значення формули логіки предикатів

У зв'язку із введенням кванторів необхідно врахувати таке:

1. Формула логіки предикатів не може містити те саме предметне змінне, яке було б пов'язане в одній частині формули і вільно в іншій.

2. Одне й те змінне неспроможна перебувати у сфері двоїстих один одному кванторов.

Порушення цих умов називають колізією змінних.

Як встановлюється значення істинності висловлювання із квантором?

Для доказу затвердження із квантором спільності необхідно переконатися у тому, що з підстановці кожного з значень ху предикат Р(х)останній звертається до справжнього висловлювання. Якщо безліч Х звичайно, це можна зробити шляхом перебору всіх випадків; якщо ж безліч Х нескінченно, необхідно провести міркування в загальному вигляді.

Висловлювання (х) Р(х)хибно, якщо можна вказати таке значення аХ, за якого Р(х)звертається у хибне висловлювання Р(а).Тому, для спростування висловлювання з квантором спільності достатньо навести приклад.

Висловлювання (х) Р(х)істинно, якщо можна вказати таке значення аХ, за якого Р(х)звертається до справжнього висловлювання Р(а). Тому, щоб переконатися у істинності висловлювання з квантором існування , достатньо навести приклад і в такий спосіб довести.

Для того щоб переконатися у хибності висловлювання з квантором існування (х) Р(х),необхідно переконатися у хибності кожного Р(х), Р(х), …, Р(х). Якщо безліч Хзвичайно, це можна зробити перебором. Якщо ж безліч Хнескінченно, необхідно провести міркування в загальному вигляді.

Приклади.

1. Знайти значення істинності «средичисел 1, 2, 3, 4 знайдеться просте число».

Рішення:Вислів містить квантор існування і тому може бути поданий у вигляді диз'юнкції висловлювань: « 1 - просте число» або « 2 - просте число» або « 3 - просте число» або « 4 - просте число". Для доказу істинності диз'юнкції достатньо істинності хоча б одного висловлювання, наприклад, « 3 - просте число», яке є істинним. Отже, істинний і вихідний вислів.

2. Доведемо, що будь-який квадрат є прямокутником.

Рішення:Вислів містить квантор спільності. Тому воно може бути представлене у вигляді кон'юнкції: "квадрат - прямокутник" і "квадрат - прямокутник" і "квадрат - прямокутник" і т.д. Оскільки всі ці висловлювання є істинними, то істинна кон'юнкція цих висловлювань, отже, істинна і вихідна пропозиція.

3. «Будь-який трикутник рівнобедрений». Це хибне висловлювання. Щоб переконатися в цьому, достатньо накреслити трикутник, що не є рівнобедреним.

Для побудови заперечення висловлювання з кванторамитреба:

1) квантор спільності замінити квантором існування, а квантор існування – квантором спільності;

2) предикат замінити його запереченням.

приклад. Сформулюємо заперечення для наступних висловлювань:

а) всі елементи множини Zпарні; b) деякі дієслова відповідають питанням «що робити?».

Рішення:а) Замінимо квантор спільності квантором існування, а висловлювання його запереченням: деякі елементи множини Zнепарні.

b) Замінимо квантор існування квантором спільності, а вираз його запереченням: усі дієслова не відповідають питанням «що робити?».

Предикат (лат. praedicatum- заявлене, згадане, сказане) - будь-який математичний вислів, у якому є щонайменше одна змінна. Предикат є основним об'єктом вивчення логіки першого ладу.

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

Вирази: x > 5, x > y – предикати.

Предика́т ( n-місцевий, або n-арний) - це функція з безліччю значень (0,1) (або «брехня» та «істина»), визначена на множині . Таким чином, кожен набір елементів множини Mхарактеризується або як «істинний», або як «хибний».

Предикат можна пов'язати з математичним ставленням: якщо n-ка належить відношенню, то предикат повертатиме на ній 1. Зокрема, одномісний предикат визначає відношення належності до деякої множини.

Предикат - один із елементів логіки першого та вищих порядків. Починаючи з логіки другого порядку, у формулах можна ставити квантори з предикатів.

Предикат називають тотожно-істиннимі пишуть:

якщо будь-якому наборі аргументів він приймає значення 1.

Предикат називають тотожно-хибнимі пишуть:

якщо на будь-якому наборі аргументів він набуває значення 0.

Предикат називають здійсненнимякщо хоча б на одному наборі аргументів він приймає значення 1.

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

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

Квантор загальності(позначення: , читається: «для всіх…», «для кожного…» або «кожен…», «будь-який…», «для будь-якого…»).

Квантор існування(Позначення: , Читається: «існує ...» або «Знайдеться ...»).

Приклади

Позначимо P(x) предикат « xділиться на 5». Використовуючи квантор спільності, можна формально записати такі висловлювання (звичайно, хибні):

будь-яке натуральне число кратно 5;

кожне натуральне число кратне 5;

усі натуральні числа кратні 5;

наступним чином:

.

Наступні (вже справжні) висловлювання використовують квантор існування:

існують натуральні числа, кратні 5;

знайдеться натуральне число, кратне 5;

хоча б одне натуральне число кратне 5.

Їх формальний запис:

. Введення у поняття

Нехай на множині Х простих чисел заданий предикат Р(х): «Просте число х - непарно». Підставимо перед цим предикатом слово «будь-яке». Отримаємо хибне висловлювання «будь-яке просте число х непарно» (це висловлювання хибне, оскільки 2 - просте парне число).

Підставивши перед даним предикатом Р(х) слово «існує», отримаємо справжнє висловлювання «Існує просте число х є непарним» (наприклад, х=3).

Отже, перетворити предикат на висловлювання можна, поставивши перед предикатом слова: «все», «існує», та інших., звані в логіці кванторами.

Квантори з математичної логіки

Висловлювання означає, що область значень змінної xвключена в область істинності предикату P(x).

(«При всіх значеннях (x) твердження вірне»).

Висловлювання означає, що область істинності предикату P(x) Непорожня.

(«Існує (x) у якому твердження правильне»).

Вопрос31 Граф та її елементи. Основні поняття. Інцидентність, кратність, петля, суміжність. Типи графів. Маршрут у графі та його довжина. Класифікація маршрутів. Матриці суміжності орієнтованого та неорієнтованого графів.

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

Об'єкти видаються як вершини, або вузли графа, а зв'язки – як дуги, чи ребра. Для різних областей застосування види графів можуть відрізнятися спрямованістю, обмеженнями на кількість зв'язків та додатковими даними про вершини або ребра.

Шляхом (або ланцюгом) у графі називають кінцеву послідовність вершин, в якій кожна вершина (крім останньої) з'єднана з наступною в послідовності вершин ребром.

Орієнтованим шляхом в орграфі називають кінцеву послідовність вершин v iдля якої всі пари ( v i,v i+ 1) є (орієнтованими) ребрами.

Циклом називають шлях, у якому перша та остання вершини збігаються. При цьому довжиною шляху (або циклу) називають число його складових ребер. Зауважимо, що якщо вершини uі vє кінцями деякого ребра, то згідно з цим визначенням, послідовність ( u,v,u) є циклом. Щоб уникнути таких вироджених випадків, вводять такі поняття.

Шлях (або цикл) називають простим, якщо ребра у ньому не повторюються; елементарним, якщо він простий і вершини у ньому не повторюються. Нескладно бачити, що:

Кожен шлях, що з'єднує дві вершини, містить елементарний шлях, що з'єднує ті самі дві вершини.

Будь-який простий неелементарнийшлях містить елементарний цикл.

Кожен простийцикл, що проходить через деяку вершину (або ребро), містить елементарний(Під-)цикл, що проходить через ту ж вершину (або ребро).

Петля – елементарний цикл.

Граф чи неорієнтований граф G- це впорядкована пара G: = (V,E

V

Eце безліч пар (у разі неорієнтованого графа – невпорядкованих) вершин, званих ребрами.

V(а значить і E, інакше воно було б мультимножиною) зазвичай вважаються кінцевими множинами. Багато хороших результатів, отриманих для кінцевих графів, неправильні (або будь-яким чином відрізняються) для нескінченних графів. Це тому, що ряд міркувань стає хибним у разі нескінченних множин.

Вершини та ребра графа називаються також елементами графа, число вершин у графі | V| - порядком, число ребер | E| - Розміром графа.

Вершини uі vназиваються кінцевими вершинами (або просто кінцями) ребра e = {u,v). Ребро, своєю чергою, з'єднує ці вершини. Дві кінцеві вершини того самого ребра називаються сусідніми.

Два ребра називаються суміжними, якщо вони мають загальну кінцеву вершину.

Два ребра називаються кратними, якщо множини їх кінцевих вершин збігаються.

Ребро називається петлею, якщо його кінці збігаються, тобто e = {v,v}.

Ступенем deg Vвершини Vназивають кількість інцидентних їй ребер (при цьому петлі вважають двічі).

Вершина називається ізольованою, якщо вона не є кінцем для жодного ребра; висячою (або листом), якщо вона є кінцем рівно одного ребра.

Орієнтований граф (скорочено орграф) G- це впорядкована пара G: = (V,A), для якої виконані такі умови:

Vце непорожня безліч вершин або вузлів,

Aце безліч (упорядкованих) пар різних вершин, званих дугами чи орієнтованими ребрами.

Дуга- це впорядкована пара вершин (v, w), де вершину vназивають початком, а w- кінцем дуги. Можна сказати, що дуга веде від вершини vдо вершини w.

Змішаний граф

Змішаний граф G- це граф, у якому деякі ребра можуть бути орієнтованими, а деякі – неорієнтованими. Записується впорядкованою трійкою G: = (V,E,A), де V, Eі Aвизначено так само, як вище.

Орієнтований та неорієнтований графи є окремими випадками змішаного.

Ізоморфні графи(?)

Граф Gназивається ізоморфним графу Hякщо існує біекція fз безлічі вершин графа Gу безліч вершин графа H, що має таку властивість: якщо у графі Gє ребро з вершини Aу вершину B, то у графі H f(A) у вершину f(B) і навпаки - якщо у графі Hє ребро з вершини Aу вершину B, то у графі Gмає бути ребро з вершини f − 1 (A) у вершину f − 1 (B). У разі орієнтованого графа ця бієкція також має зберігати орієнтацію ребра. У разі виваженого графа бієкція також має зберігати вагу ребра.

Матриця суміжності графа Gз кінцевим числом вершин n(пронумерованих числами від 1 до n) - це квадратна матриця Aрозміру n, в якій значення елемента a ijдорівнює числу ребер з i-ї вершини графа в j-ю вершину.

Іноді, особливо у разі неорієнтованого графа, петля (ребро з i-й вершини в саму себе) вважається за два ребра, тобто значення діагонального елемента a iiу цьому випадку дорівнює подвійному числу петель навколо i-ї вершини.

Матриця суміжності простого графа (що не містить петель та кратних ребер) є бінарною матрицею і містить нулі на головній діагоналі.

Вопрос32 Функція. Методи завдання. Класифікація функций. Основні елементарні функції та їх графіки. Композиція функцій. Елементарні функції.

Функція - математичне поняття, що відбиває зв'язок між елементами множин. Можна сміливо сказати, що функція це «закон», яким кожному елементу однієї множини (названому областю визначення ) ставиться у відповідність певний елемент іншої множини (названої областю значень ).

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

Способи завдання функції

Аналітичний спосіб

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

Завдання функції користуються выражением: . При цьому, xє змінна, що пробігає область визначення функції, а y- Область значень. Цей запис говорить про наявність функціональної залежності між елементами множин. хі yможуть пробігати будь-які об'єкти будь-якої природи. Це можуть бути числа, вектори, матриці, яблука, кольори веселки. Пояснимо на прикладі:

Нехай є безліч яблуко, літак, груша, стілецьі безліч людина, паровоз, квадрат. Задамо функцію f наступним чином: (яблуко, людина), (літак, паровоз), (груша, квадрат), (стілець, людина). Якщо ввести змінну x, що пробігає множину і змінну y, що пробігає множину, вказану функцію можна задати аналітично, як: .

Аналогічно можна задавати числові функції. Наприклад: де x пробігає безліч дійсних чисел задає деяку функцію f. Важливо розуміти, що вираз не є функцією. Функція як об'єкт є безліч (упорядкованих пар). А це вираз як об'єкт є рівність двох змінних. Воно задає функцію, але з нею.

Однак, у багатьох розділах математики, можна позначати через f(x) як саму функцію, так і аналітичний вираз, що її задає. Ця синтаксична угода є вкрай зручною та виправданою.

Графічний спосіб

Числові функції також можна задавати за допомогою графіка. Нехай - речова функція n змінних.

Розглянемо деякий (n+1)-мірний лінійний простір над полем дійсних чисел (оскільки функція речова). Виберемо у цьому просторі будь-який базис (). Кожній точці функції можна порівняти вектор: . Таким чином, ми матимемо безліч векторів лінійного простору, які відповідають точкам цієї функції за вказаним правилом. Точки відповідного афінного простору утворюватимуть деяку поверхню.

Якщо в якості лінійного простору взяти евклідово простір вільних геометричних векторів (спрямованих відрізків), а число аргументів функції f не перевищує 2, вказане безліч точок можна зобразити у вигляді креслення (графіка). Якщо навіть вихідний базис взяти ортонормованим, отримаємо "шкільне" визначення графіка функції.

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

Однак, і для таких функцій можна вигадати наочне напівгеометричне уявлення (наприклад кожному значенню четвертої координати точки зіставити деякий колір на графіку)

Пропорційні величини.Якщо змінні yі x прямо пропорційні

y = k x ,

де k- Постійна величина ( коефіцієнт пропорційності).

Графік прямої пропорційності- Пряма лінія, що проходить через початок координат і утворює з віссю Xкут, тангенс якого дорівнює k: tan = k(Рис.8). Тому, коефіцієнт пропорційності називається також кутовим коефіцієнтом. На рис.8 показано три графіки для k = 1/3, k= 1 і k = 3 .

Лінійна функція.Якщо змінні yі xпов'язані рівнянням 1-го ступеня:

A x + B y = C ,

де принаймні одне з чисел Aабо Bне дорівнює нулю, то графіком цієї функціональної залежності є пряма лінія. Якщо C= 0, вона проходить через початок координат, інакше - немає. Графіки лінійних функцій для різних комбінацій A,B,Cпоказано на рис.9.

Назад пропорційність.Якщо змінні yі x назад пропорційні, то функціональна залежність між ними виражається рівнянням:

y = k / x ,

де k- Постійна величина.

Графік зворотної пропорційності – гіпербола(Рис.10). Ця крива має дві гілки. Гіперболи виходять при перетині кругового конуса площиною (про конічні перерізи див. розділ "Конус" у розділі "Стереометрія"). Як показано на рис.10, добуток координат точок гіперболи є величина постійна, у нашому прикладі дорівнює 1. У загальному випадку ця величина дорівнює k, що випливає з рівняння гіперболи: xy = k.

Основні характеристики та властивості гіперболи:

x 0, область значень: y 0 ;

Функція монотонна (зменшується) при x< 0і при x > 0, але не

монотонна загалом через точку розриву x = 0);

Функція необмежена, розривна у точці x= 0, непарна, неперіодична;

- нулів функція немає.

Квадратична функція.Це функція: y = ax 2 + bx + c, де a, b, c- постійні, a b=c= 0 і y = ax 2 . Графік цієї функції квадратна парабола - OY, яка називається віссю параболи.Крапка O вершиною параболи.

Квадратична функція.Це функція: y = ax 2 + bx + c, де a, b, c- постійні, a 0. У найпростішому випадку маємо: b=c= 0 і y = ax 2 . Графік цієї функції квадратна парабола -крива, що проходить через початок координат (рис.11). Кожна парабола має вісь симетрії OY, яка називається віссю параболи.Крапка Oперетину параболи з її віссю називається вершиною параболи.

Графік функції y = ax 2 + bx + c- теж квадратна парабола того ж виду, що й y = ax 2 але її вершина лежить не на початку координат, а в точці з координатами:

Форма та розташування квадратної параболи в системі координат повністю залежить від двох параметрів: коефіцієнта aпри x 2 та дискримінанта D:D = b 2 – 4ac. Ці властивості випливають із аналізу коренів квадратного рівняння (див. відповідний розділ у розділі «Алгебра»). Усі можливі різні випадки для квадратної параболи показано на рис.12.

Основні характеристики та властивості квадратної параболи:

Область визначення функції:  < x+ (тобто. x R), а область

значень: … (відповідайте, будь ласка, це питання самі!);

Функція загалом не монотонна, але справа чи ліворуч від вершини

веде себе, як монотонна;

Функція необмежена, скрізь безперервна, парна при b = c = 0,

та неперіодична;

- при D< 0 не имеет нулей.

Показова функція.Функція y = a x, де a- Позитивне постійне число, називається показовою функцією.Аргумент xприймає будь-які дійсні значення; як значення функції розглядаються тільки позитивні числа, тому що інакше ми маємо багатозначну функцію. Так, функція y = 81xмає при x= 1/4 чотири різні значення: y = 3, y = 3, y = 3 iі y = 3 i(перевірте будь ласка!). Але ми розглядаємо як значення функції лише y= 3. Графіки показової функції для a= 2 і a= 1/2 представлені на рис.17. Вони проходять через точку (0, 1). При a= 1 ми маємо графік прямої лінії, паралельної осі Х, Тобто. функція перетворюється на постійну величину, рівну 1. При a> 1 показова функція зростає, a за 0< a < 1 – убывает. Основные характеристики и свойства показательной функции:

Область визначення функції:  < x+ (тобто. x R);

область значень: y> 0 ;

Функція монотонна: зростає при a> 1 і меншає при 0< a < 1;

- нулів функція немає.

Логарифмічна функція.Функція y= log a x, де a- Постійне позитивне число, не рівне 1, називається логарифмічної. Ця функція є зворотною до показової функції; її графік (рис.18) можна отримати поворотом графіка показової функції навколо бісектриси 1-го координатного кута.

Основні характеристики та властивості логарифмічної функції:

Область визначення функції: x> 0,а область значень:  < y+

(Тобто. y R);

Це монотонна функція: вона зростає при a> 1 і меншає при 0< a < 1;

Функція необмежена, всюди безперервна, неперіодична;

У функції є один нуль: x = 1.

Тригонометричні функції.При побудові тригонометричних функцій ми використовуємо радіальнуміру вимірювання кутів.Тоді функція y= sin xпредставляється графіком (рис.19). Ця крива називається синусоїдою.

Графік функції y= cos xпредставлений на рис.20; це також синусоїда, отримана в результаті переміщення графіка y= sin xвздовж осі Хліворуч на 2

З цих графіків очевидні властивості і характеристики цих функций:

Область визначення:  < x+ область значень: 1 y +1;

Ці функції періодичні: їх період 2;

Функції обмежені (| y| , всюди безперервні, не монотонні, але

мають так звані інтервали монотонності, всередині яких вони

поводяться як монотонні функції (див. графіки рис.19 і рис.20);

Функції мають безліч нулів (докладніше див. розділ

«Тригонометричні рівняння»).

Графіки функцій y= tan xі y= cot xпоказані відповідно на рис.21 та рис.22

З графіків видно, що ці функції: періодичні (їх період ,

необмежені, загалом не монотонні, але мають інтервали монотонності

(які?), розривні (які точки розриву мають ці функції?). Область

визначення та область значень цих функцій:

Функції y= Arcsin x(рис.23) та y= Arccos x(рис.24) багатозначні, необмежені; їх область визначення та область значень відповідно: 1 x+1 та  < y+ . Оскільки ці функції багатозначні, не

розглядаються в елементарній математиці, як зворотні тригонометричні функції розглядаються їх головні значення: y= arcsin xі y= arccos x; їх графіки виділені на рис.23 та рис.24 жирними лініями.

Функції y= arcsin xі y= arccos xволодіють наступними характеристиками та властивостями:

У обох функцій та сама область визначення: 1 x +1 ;

їх області значень:  /2 y/2 для y= arcsin xта 0 yдля y= arccos x;

(y= arcsin x- Зростаюча функція; y= arccos x –спадна);

Кожна функція має по одному нулю ( x= 0 у функції y= arcsin xі

x= 1 у функції y= arccos x).

Функції y= Arctan x(рис.25) та y= Arccot x(Мал.26) - багатозначні, необмежені функції; їх область визначення:  x+. Їхні головні значення y= arctan xі y= arccot xрозглядаються як зворотні тригонометричні функції; їх графіки виділені на рис.25 та рис.26 жирними гілками.

Функції y= arctan xі y= arccot xмають такі характеристики та властивості:

У обох функцій та сама область визначення:  x + ;

їх області значень:  /2<y < /2 для y= arctan xта 0< y < для y= arccos x;

Функції обмежені, неперіодичні, безперервні та монотонні

(y= arctan x- Зростаюча функція; y= arccot x –спадна);

Тільки функція y= arctan xмає єдиний нуль ( x= 0);

функція y= arccot xнулів немає.

Композиція функцій

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

Рис.1.30.Наскрізне відображення з