Коротка методичка з логіки

Посторінковий перелік понять і теорем.

Логіка. Мова. Висловлення. Істинне висловлювання. Хибне висловлювання. Істина. Брехня. Позначення для істини. Позначення для брехні. Истинностное значення висловлювання. Рівносильні висловлювання. Синоніми для істинного висловлювання. Доказ. Правило виведення. Позначення для конструктивного правила. Компоненти конструктивного правила. Посилки конструктивного правила. Укладання конструктивного правила. Индуктивная послідовність об'єктів. Правила породження індуктивної послідовності. Формальний мову. Логічні знаки. Допоміжні знаки. n-местные функціональні знаки. n-местные предикатні знаки. Змінні. Алфавітний порядок знаків. Вислів. Синоніми висловлення. позначення для нульместных функціональних знаків. позначення для функціональних знаків. позначення для предикатных знаків. позначення для висловів. позначення для змінних. Позначення для сполуки висловів. Терм. Правила породження термов. позначення для термов. Индуктивная послідовність термов.

Висловлення. Синоніми для висловлювання. Правила породження висловлювань. Индуктивная послідовність висловлювань. позначення для висловлювань. Угоди про скасування скобок. Константа. Квантор загальності. Квантор існування. Предикат. Елементарна висловлювання. Компонента висловлювання. Синонім для компоненти висловлювання. Пропозициональная компонента висловлювання. Інтерпретація формального мови. Універсум інтерпретації. Синонім для універсуму. Значення перемінної. Значення функціонального знака. Значення предикатного знака. Значення терма. Значення висловлювання. Денотати термов і висловлювань. Індуктивне визначення значення терма. Індуктивне визначення значення висловлювання. Узагальнення висловлювання з цієї перемінної. Синоніми висловлення узагальнення. Підтвердження висловлювання з цієї перемінної. Синоніми для висловлювання підтвердження. Заперечення висловлювання. Синоніми висловлення заперечення. А высказываний.

Конъюнкты. Синоніми висловлення конъюнкции. Диз’юнкція висловлювань. Дизъюнкты. Синоніми висловлення диз’юнкції. Імплікація висловлювань. Відправка імплікації. Укладання імплікації. Синоніми висловлення імплікації. Эквиваленция висловлювань. Ліва і права частини эквиваленции. Синоніми висловлення эквиваленции.

Зауваження про мовної суміші. Зауваження про використання знака рівності для висловлювань. Пропозициональная логіка. Синонім для пропозициональной логіки. Логічні (пропозициональные) операції. Истинностная таблиця висловлювань. Вхідні і результуючі стовпчики истинностной таблиці. Тавтологія і його синонім. Тавтологічну слідство. Теорему про запереченні заперечення. Теорему про запереченні конъюнкции. Теорему про запереченні диз’юнкції. Теорему про виключення імплікації. Теорему про виключення эквиваленции. Теорему про усунення альтернативи. Теорему про коммутативности… Теорему про равносильности. Теорему про тавтологическом слідстві. Арифметична запис висловлювань. 12 рівностей. Правило відділення. Теорему виведення в пропозициональной логіці. Теорему про самодостатньою виразності пропозициональной логики.

Кванторная логіка. Синонім для кванторной логіки. Кванторные операції. Кванторологически справжнє висловлювання. Кванторологическое слідство. Пов’язане входження перемінної. Вільне входження перемінної. Результат підстановки в висловлювання терма замість перемінної та її позначення. Допустимий замінник. Замкнутий висловлювання. Відкрите высказывание.

Теорему про всезначности перемінної. Теорему про запереченні узагальнення і підтвердження. Теорему про взаимоисключении кванторів. Теорему про перестановочности кванторів. Типові кванторы. Теорему про равносильной заміні. Позитивне висловлювання. Позитивна форма висловлювання. Теорему про позитивної формі. Теорему виведення з логіки предикатів. Правило тавтології. Правило відділення. Правило узагальнення. Правило підтвердження. Правило общевнесения. Правило сущевнесения.

Егалітарна логіка. Синонім для егалітарної логіки. Егалітарна інтерпретація. Логічне слідство. Позначення для логічного слідства. Логічно справжнє висловлювання. Позначення для логічно істинного висловлювання. Правило тотожності. Правило рівності. Правило нерозрізненості. Теорему про егалітарної заміні. Теорему про транзитивності логічного слідства. Теорему про розширення списку гіпотез. Теорему про конъюнктивизации гіпотез. Теорему дедукції. Теорему виведення в егалітарної логіці. Теорему про порівняльної силі висновків. Алгоритм. Теорему про нерозв’язності проблеми логічного слідства. Теорему про нерозв’язності проблеми логічного істинності. Зауваження про слові ЛОГИКА.

Формальні теорії. Аксіоми формальної теорії. Теореми формальної теорії. Доказовий текст. Дев’ять основних правил вывода.

Способи компактизации доказових текстів. Операційна форма записи для двомісних функціональних і предикатных знаків. Угоду про скасування скобок. Угоду про порівняльної силі зв’язку логічних і нелогических знаків. Спеціальні начерки знаків. Знакові фигуры.

Визначальна аксіома для створення нового предикатного знака. Визначальна аксіома для створення нового функціонального знака. Теорему про визначеннях. Правило відділення конъюнкта. Правило приєднання дизъюнкта. Теорему про методі від супротивного. Формальна арифметика. Що Визначають аксіоми для 2 3 4 5 (?? ?.

Безліч. Елемент безлічі. Х (А. Х (А. Підмножина. А (В. A (B. {а (р}. Байдуже безліч та її позначення. {Х1,…Хn,}. Об'єднання двох множин та її позначення. Перетин двох множин та її позначення. Доповнення безлічі У щодо безлічі А, його позначення і синонім. Позначення для безлічі натуральних, цілих і дійсних чисел. Упорядкована n-ка, її позначення і синоніми. k-ая компонента упорядкованого набору, її позначення і синонім. Декартово твір множин та її позначення. К-ая проекція n-мерного числа й її позначення Аn.

Функція. Область визначення функції, її синонім і позначення. Область значень функції, її синонім і позначення. Значення функції F в x та її позначення. Образ безлічі щодо функції та її обозначение.

Відображення безлічі в безліч. Відображення безлічі силою-силенною. F (А (У. Звуження функції. Розширення функції. Зворотний функція. Симетричність поняття зворотної функції. n-аргументная функція. Позначення F ((Х1,…, Хn)). Однозначна функція. Багатозначна функція. Взаимнооднозначная функція і його синонім. Послідовність. n-ий член послідовності. Нескінченне безліч. Кінцеве множество.

Тема 1. Предмет й захопити основні поняття логики.

Логіка — наука про мисленні, наука про мовному вираженні думок. Мова — знакова система, призначена для фіксації, передачі й переробки інформації. Висловлення — мовне вираз, про яку представляється природним запитати, істинно воно чи брехливо. Висловлення є істинним, якщо його зміст чи реальні; у протилежному разі висловлювання бреше. Т. про. будь-яке висловлювання є або істинним або хибним і тим самим служить позначенням або істини або брехні, які ми можемо розглядати, як два різних умоглядних об'єкта, які охоплюють зазвичай літерами І, Л і званих истинностными значеннями висловлювань: І якщо є истинностное значення істинного висловлювання, Л є истинностное значення помилкового висловлювання. Висловлювання з истинностными значеннями називаються рівносильними. Про справжнє висловлювання кажуть, що його справедливо, вірно, має місце. Доказом називається кінцева послідовність висловлювань, в котрої кожен висловлювання виходить з деяких попередніх з якогоабо правилу виведення. Правила виведення — це конструктивні операції над висловлюваннями, зберігають властивість істинності, т. е. таких операцій, в результаті чого з істинних висловлювань виходять істинні висловлювання. Конструктивне правило перетворення об'єктів u1,., un-1 в об'єкт un будемо нотувати у вигляді (u1,…, un. У цьому u1,…, un називаються компонентами, останню з яких називається укладанням, а інші посилками. Послідовність об'єктів називається індуктивної щодо деякого набору правил, якщо кожне її член виходить з попередніх по якогось із цих правил, які називаються правилами породження даної послідовності. Наприклад, зростаюча послідовність всіх непарних чисел і послідовність 1, 3, 1, 5, 7, 3 є индуктивными щодо правил (1 і (x, х+2, а послідовність 1, 3, 7 перестав бути індуктивної щодо цього набору правил.

Тема 2. Уніфікація языка.

Для чіткого висловлювання думок вчені придумали формальний мову, в якому всі осмислені висловлювання будуються за правилами з наступних знаків, символов:

Логічні знаки (((((((допоміжні знаки (), нульместные функціональні знаки f[pic] f [pic] f[pic] f[pic] … одномісні функціональні знаки f[pic] f[pic] f[pic] f[pic]…

… нульместные предикатні знаки g[pic] g[pic] g[pic] g[pic]… одномісні предикатні знаки g[pic] g[pic] g[pic] g[pic]…

… перемінні (0 (1 (2 (3 … Порядок у якому тут перераховані знаки, називається алфавітним порядком.

Вираженням, знакосочетанием, символосочетанием у тому формальному мові називається кілька записаних друг за іншому у бік зліва на право знаків. з, c0, c1, … позначають нульместные функціональні знаки. f, f0, f1, … позначають функціональні знаки. g, g0, g1, … позначають предикатні знаки. u, v, w, u0, v0, w0, u1, v1, w1, … позначають висловлювання. x, y, z, х0, y0, z0, х1, y1, z1, … позначають перемінні. uv позначає результат написання висловлювання v після висловлювання u.

Термами називаються знакосочетания з цими породжують правилами:

(х.

(c.

(u1,…, un, f (u1, …, un). f n-местный, n (0.

позначення для термов: a, b, a0, b0, a1, b1, …

Приклад індуктивної послідовності термов: f[pic].

(1 f[pic] ((1, f[pic]) f[pic] ((1, (1, f[pic]((1, f[pic])).

(2 f[pic]((1, f[pic], f[pic]((1, f[pic]), (2) f[pic]((2) f[pic](f[pic]((2)).

Висловлюваннями, співвідношеннями, формулами називаються знакосочетания з цими правилами порождения:

(g тут g нульместный.

(g (а1,…, аn) тут g n-местный, n (0.

(u, (x (u).

(u, (x (u).

(u, ((u).

(u, v, (u)((v).

(u, v, (u)((v).

(u, v, (u)((v).

(u, v, (u)((v).

Приклад індуктивної послідовності формул (з урахуванням термов з попереднього прикладу) g[pic](f[pic], (1) g[pic].

((5(g[pic]).

((1(g[pic](f[pic], (1)).

((((5(g[pic])) g[pic].

(g[pic])((((5(g[pic])) g[pic](f[pic]((1, f[pic]), (2, (2).

Позначками для висловлювань: p, q, r, p. s, t, p0, q0, r0, s0, t0,…

З метою зручності огляду формул деякі скобочные диады можна опускати, приймаючи угоду про правобічній угрупованню скобок для кількох однакових логічних знаків і Шенгенська угода про убывании сили зв’язку в алфавітному порядку логічних знаків. Приклад: p (q (r означає (p)(((q)(®), а запис ((xp (q (r тлумачать як ((((x (p)))(((q)(®). Слід пам’ятати, що будь-який висловлювання з пропущеними парами скобок не є висловлюваннями формального мови, є лише позначенням відповідного высказывания.

Нульместные функціональні знаки називаються константами. Знакосочетание (x називається квантором загальності по x, а (x — квантором існування по x. Початок з предикатного знака висловлювання називається предикатом. Висловлення називається елементарним, коли вона починається з квантора чи предикатного знака. Висловлення q називається подвысказыванием чи компонентом висловлювання р, якщо q є частка р. Елементарна компонента q висловлювання р називається його пропозициональной компонентом, якщо q має хоча одне таке входження у р, яке є вступом до якусь іншу елементарну компоненту висловлювання р. Наприклад, висловлювання ((5(g[pic](g[pic])(g[pic] має п’ять компонент: ((5(g[pic](g[pic]), g[pic], g[pic], g[pic](g[pic], ((5(g[pic](g[pic])(g[pic], із яких лише перші три є елементарними, два — пропозициональными, лише g[pic] і g[pic] - предикатными.

Інтерпретація формального мови. Змінна висловлює, нотирует, позначає довільний із деякого не порожнього безлічі, яке називається денотарием чи універсумом інтерпретації і елементи якого цим є денотатами чи значеннями перемінної. n-местный функціональний знак позначає n-местную операцію на универсуме. n-местный предикатный знак позначає початкову взаємозв'язок між будь-якими n об'єктами універсуму. Терми позначають об'єкти універсуму, а висловлювання позначають істину чи нахабна брехня, т. е. денотатами термов є об'єкти універсуму, а денотатами висловлювань є істина і брехня. Поставити інтерпретацію формального мови отже поставити її універсум і з ним значення всіх потрібних нам функціональних і предикатных знаків; тоді значення всіх потрібних термов і формул за будь-яких значеннях фігуруючих у них змінних визначаються індукцією з їхньої побудові з урахуванням такий інтерпретації логічних знаків: (xp — узагальнення висловлювання р по x є справжнім тттк р є істинним всім значень перемінної x; синоніми: р кожному за x, р для будь-якого x, р всім x, р для довільного x. (xp — підтвердження висловлювання р по x є справжнім тттк р є істинним хоча для одного значення перемінної x; синоніми: існує x т.ч. р, р для деякого x. (p — заперечення висловлювання р є справжнім тттк р бреше; синоніми: не р, не так що р. p (q — з'єднання висловлювань р, q є істинної тттк обидва її конъюнкта р, q є «справжніми; синоніми: р і q, і р і q. p (q — диз’юнкція висловлювань p, q хибна тттк обидва її дизъюнкта р, q є хибними; синоніми: р чи q, чи р чи q. p (q — імплікація висловлювань p, q хибна тттк посилка р є істинної, а висновок q бреше; синоніми: р лише коли q, якщо р то q, q якщо р, р тоді q, q коли р, щоб р необхідно щоб q, щоб q досить щоб р, р отже q, речей що р слід що q. p (q — эквиваленция висловлювань р, q є істинної тттк її частки р, q обидві є «справжніми чи обидві є хибними; синоніми: р як і лише якщо q, р тоді й тільки тоді коли q, щоб р необхідне й досить щоб q, р еквівалентно q.

Зауваження. Іноді висловлювання записують на суміші формального, звичайного і математичного мови. Усі такі записи розглядатимемо її як позначення відповідних висловлювань формального языка.

Зауваження. Запровадження позначень для висловлювань породжує двозначність використання знака рівності, оскільки самі висловлювання є деякими позначками, саме позначками істини чи брехні. За наявності ієрархії позначень таку двозначність зазвичай знімають угодою тому, що рівність сприймається як рівність між вихідними об'єктами. Т. про. рівність p=q означає, що р і q мають однакові истинностные значення т. е. є равносильными.

Приклад. Кожен кулику своє болото хвалит.

Універсум — безліч куликов і боліт g[pic](x) — x є кулику g[pic](x) — x є болото g[pic](x, у) — x хвалить у g[pic](x, у) — у своє для х.

((1((((g[pic]((1))((g[pic]((2)))((g[pic]((1, (2)))((g[pic]((1, (2))).

Приклад. Сума квадратів двох позитивних чисел менше квадрата їх суммы.

Універсум — безліч позитивних чисел. f[pic](x) — квадрат числа x f[pic](x, y) — сума чисел x, y g[pic](x, y) — x менше y.

g[pic](f[pic](f[pic]((1), f[pic]((2)), f[pic](f[pic]((1, (2))).

Можна записати інакше: універсум — безліч дійсних чисел f[pic] - число 0.

((g[pic](f[pic], (1))((g[pic](f[pic], (2)))((g[pic](f[pic](f[pic]((1), f[pic]((2)), f[pic](f[pic]((1, (2))).

Приклад. Я тільки тепер один знаю про этом.

Універсум — безліч людей f[pic] - я g[pic](x) — x це g[pic](x, y) — x ідентичний y.

(g[pic](f[pic]))((((1((((g[pic]((1, f[pic])))((((g[pic]((1)))).

Ніхто не це: ((1(((g[pic]((1))).

Усім фахівцям відомо звідси: ((1(g[pic]((1)).

Хтось це: ((1(g[pic]((1)).

Приклад. Тут холодно, але з сиро: (g[pic])((((g[pic])).

Приклад. Ні p ні q: (p і (q.

Приклад. Якщо p то q інакше r: (p (q)(((p®.

Приклад. p або q: p ((q ((p (q.

Приклад. p тому q: p ((p (q).

Приклад. Чай без цукру не солодкий і смачний. g[pic] - чай містить цукор g[pic] - чай солодкий g[pic] - чай вкусный.

(((g[pic]))(((((g[pic]))((((g[pic]))).

Можливий інший перевод:

((((g[pic]))((((g[pic])))(((((g[pic]))(((((g[pic]))).

Приклад. Його батько слюсар, проте брати токари.

Універсум — безліч чоловіків f[pic] - він f[pic](x) — батько для x g[pic](x) — x є слюсар g[pic](x) — x є токар g[pic](x, y) — x ідентичний y.

(g[pic](f[pic](f[pic])))((((1(((((g[pic]((1, f[pic])))((g[pic](f[pic]((1), (f[pic](f[pic]))))((g[pic]((1)))).

Тема 3. Пропозициональная логика.

чи логіка елементарних висловлювань вивчає властивості логічних операцій (, (, (, (, (, котрі за змісту запровадження мит є операціями над истинностными значениями:

|p |q |(p |p (q |p (q |p (q |p (q | |Л |Л |І |Л |Л |І |І | |Л |І |І |Л |І |І |Л | |І |Л |Л |Л |І |Л |Л | |І |І |Л |І |І |І |І |.

Якщо висловлювання р, q різняться елементарні, ця таблиця називається истинностной таблицею висловлювань (p, q,) (p, p (q, p (q, p (q, p (q. У випадку під час складання истинностной таблиці будь-якого переліку висловлювань треба помістити їхньому вхід все різні пропозициональные компоненти цих висловлювань, зробити повний перебір истинностных значень у вхідних шпальтах та не записати відповідні истинностные значення результирующих столбцах.

Приклад. У кімнаті без вікон темно і неуютно.

Універсум — безліч кімнат g[pic]((1) — (1 має вікно p — кімната має вікно g[pic]((1) — в (1 темно q — у кімнаті темно g[pic]((1) — в (1 затишно r — у кімнаті уютно.

(((g[pic]((1)))(((g[pic]((1))((((g[pic]((1)))) (p (q ((r p q r.

|p |q |r |(p |(r |q ((r |(p (q ((r | |Л |Л |Л |І |І |Л |Л | |Л |Л |І |І |Л |Л |Л | |Л |І |Л |І |І |І |І | |Л |І |І |І |Л |Л |Л | |І |Л |Л |Л |І |Л |І | |І |Л |І |Л |Л |Л |І | |І |І |Л |Л |І |І |І | |І |І |І |Л |Л |Л |І |.

Тавтологія чи тавтологически справжнє висловлювання — це висловлювання зі суцільними, А тоді в стовпці його истинностной таблиці. Висловлення q називається тавтологічним наслідком (з) висловлювань p1,…, pn, тоді як истинностной таблиці висловлювань p1,…, pn, q стовпець q містить І на будь-який рядку, що містить І переважають у всіх шпальтах p1,…, pn. Наприклад, побудована вище таблиця показує, что:

(p (q ((r — є тавтологічну слідство з (p, q ((r;

(r, q є тавтологическими наслідками з q ((r; r є тавтологічну слідство з p, (p.

Теорему про запереченні заперечення: ((p = p.

Теорему про запереченні конъюнкции: ((p (q) = (p ((q.

Теорему про запереченні диз’юнкції: ((p (q) = (p ((q.

Теорему про виключення імплікації: p (q = (p (q.

Теорему про виключення эквиваленции: p (q = p (q ((p ((q.

Теорему про усунення альтернативи: p ((p (q = p (q, (p (p (q = (p (q.

Теорему про коммутативности конъюнкции: p (q = q (p.

Теорему про коммутативности диз’юнкції: p (q = q (p.

Теорему про асоціативності конъюнкции: p ((q® = (p (q)(r.

Теорему про асоціативності диз’юнкції: p ((q® = (p (q)(r.

Теорему про дистрибутивности конъюнкции: p ((q® = (p (q)((p®.

Теорему про дистрибутивности диз’юнкції: p ((q® = (p (q)((p®.

Теорему про равносильности: р = q тоді й тільки тоді коли p (q = И.

Теорему про тавтологическом слідстві: q є тавтологічним наслідком з р1,…, pn тттк р1(…(р (q є тавтологією. Ці три теореми легко доводяться з допомогою истинностных таблиц.

Арифметичний спосіб записи висловлювань: виключаються знаки (, (і тоді замість Л, І, (p, p (q, p (q вживаються відповідно 0, 1, (p, p q, p + q. Наприклад, арифметичній записом висловлювання (r (p (q® буде [pic]. При арифметичній записи висловлювань з ними звертатися оскільки ніби позначають числа 0, 1, а. Логічний плюс відрізняється від арифметичного лише, що 1 + 1 = 1. У цьому корисно пам’ятати такі рівності: p (q = (p + q [pic] p (q = p q + (p (q p p = p.

[pic] p + p = p.

[pic] p (p = 0 p + (p q = p + q p +(p = 1 p + p q = (p + q 1 + p = 1.

Рівності який у лівій колонці є іншу запис вже доведених вище теорем, а рівності у правій колонці встановлюються безпосередньої перевіркою з урахуванням рівностей 0 = 1, 1 = 0.

Приклад. Доказ тавтологічності высказываний:

p (q (p =(p + (q (p) =(p +(q + p =(p + p +(q = 1 +(q = 1 p (q (p (q =(p +(q + p q =[pic] + p q = 1.

((p ((q)(((q (p)(q = [pic] +q =(q p +(q (p + q = (q (p +(p) + q =(q + q =.

Приклад. Виразна достатність пар ((, ((, ((.

p (q = (((p ((q) = ((p ((q) p (q = (((p ((q) = (p (q p (q = ((p ((q) = (p (q p (q = ((((p (q)((((p ((q)) p (q = (((p (q)(((p (q) p (q = (((p (q)(((q (p)).

Доказ останнього рівності: p (q = p q +(p (q.

(((p (q)(((q (p)) = [pic] = ((p + q)(q +(p) = (p (q +(p p +(q q + q p.

=(p (q + 0 + 0 + q p = p q +(p (q.

Приклад. Спрощення высказываний.

((p ((q (®((q ((p)((p (q)(q = ((p +(q +®(q +(p) + q ((p + q) = ((p + q)((p +(q +(r + q) = ((p + q)(1 +(p + ® = (p + q = p (q.

(p (q)(p = [pic] + p = p (q + p = p ((q + 1) = p 1 = p.

Приклад. Доказ равносильности высказываний.

((p ((q ((r (= (p ((q (r = (p +(q (r = p +(q (r.

{((p ((q)(((p (®} = ((p ((q)((p (® = (p +(q)(p +® = p + p (r +(q p.

+(q (r = p (1 +(r +(q) +(q (r = p +(q (r.

Т. про. (…(= {…} т. е. є рівносильними два раніше отриманих перекладу висловлювання «чай …».

Правилом відділення називається правило (p, (p)((q), q.

Теорему виведення в пропозициональной логіці: висловлювання p0 є тавтологічним наслідком з p1,…, pn тттк може бути отримати гроші з p1,…, pn з допомогою правила відділення і нижченаведених п’ятнадцяти беспосылочных правил:

(p (q (p.

((p (p (q)((p (q).

((p (q)(((q®((p®).

(p (q (p.

(p (q (q.

((p (q)(((p®((p (q®).

(p (p (q.

(q (p (q.

((p®(((q®((p (q®).

((p (q)((p (q).

((p (q)((q (p).

((p (q)(((q (p)((p (q)).

((p (q)(((q ((p).

(p (((p.

(((p (p.

Інакше кажучи, какое-либо висловлювання p0 є тавтологічним наслідком з p1,…, pn тттк p0 можна зробити членом послідовності висловлювань, що є індуктивної стосовно цих шістнадцяти правив і правил (p1,…, (pn. Теорему виключає випадок n = 0.

Теорему про самодостатньою виразності пропозициональной логіки: для будь-який истинностной таблиці з n вхідними стовпчиками p1,…, pn і жодного розподілу истинностных значень у її результуючому стовпці можна скласти відповідне цьому стовпцю висловлювання: праворуч від всіх рядків з істиною в результуючому стовпці записуємо конъюнкцию p1… pn, потім над деякими pk ставимо риску заперечення те щоб всі ці конъюнкции всім рядків були істинними, потім складаємо диз’юнкцію із конъюнкций. Наприклад: p q r? 0 0 0 0 0 0 1 0 0 1 0 1 p q (r 0 1 1 0 1 0 0 1 p (q (r 1 0 1 0 1 1 0 1 p q (r 1 1 1 0.

(p q (r + p (q (r + p q (r = (p q (r + p (r ((q + q) =(p q (r + p (r =(r ((p q + p) =(r (p + q) = (r ((p (q).

Зауваження. Якщо результуючому стовпці міститься лише Л, то ролі шуканого висловлювання можна взяти p1((p1.

Приклад застосування теореми про самодостатньою виразності. Турист приїхав до країну, де кожен житель завжди бреше або завжди каже правду. Яке питання має поставити турист місцевому жителю, щоб отримати, яка з двох доріг веде до столицю. p — житель каже правду q — цей шлях веде до столицю r — висловлювання для питання |p |q |r |Потрібний відповідь | | |0 |0 |1 |Ні |(p (q | |0 |1 |0 |Так | | |1 |0 |0 |Ні | | |1 |1 |1 |Так |p q |.

r =(p (q + p q = p (q т. e. турист повинен запитати: чи правильно, що ви скажіть правду як і лише коли цей шлях веде до столицу.

Приклад перевірки міркування «(Профспілки підтримають президента на майбутні вибори (p) лише коли (він підпише законопроект про підвищення зарплати (q). (Фермери нададуть президенту підтримку ® лише коли (накладе вето на законопроект (p.s). Вочевидь, що не підпише законопроекту або накладе нею вето. Отже президент втратить голоси профспілковиків чи голоси фермерів». (p (q)((r (s)(((p ((s) ((p ((r = [pic] +(p +(r =(p q + r p. s + q p. s +(p +(r = [pic] + q p. s = [pic] + q p. s =(p +(q +(r +(p.s +q p. s =(p +(r + [pic] + q p. s = (p +(r +1 = 1 — тавтологія, тобто. міркування правильное.

Приклад перевірки міркування «(У бюджеті виникне дефіцит (p), якщо (не підвищать мита ((q). Якщо бюджеті буде дефіцит, то (державні Витрати загальносуспільні потреби скоротяться (r). Отже, якщо підвищать мита, то державні Витрати загальносуспільні потреби не скоротяться». ((q (p)((p®((q (® = [pic] +(q + (r =(q (p + p (r +(q +(r = (q ((p +1) +(r (p + 1) =(q +(r = [pic] - не тавтологія, тобто. не можна сказати, що міркування правильно.

Приклад перевірки міркування «Якщо (підозрюваний зробив цю крадіжку (p), то (у неї старанно підготовлена (q) чи (він мав співучасника (r). Якби крадіжка було підготовлено старанно, то, якби був співучасник, вкрадено було б вулицю значно більше. Отже, підозрюваний невинний». (p (q®((q ((r ((p))((p = [pic] +(p = p (q (r + p q r +(p = q r +(q (r +(p — не тавтология.

Приклад перевірки міркування «(Якщо настане світ (p), то (виникне депресія (q), хіба що для (країна проведе програму переозброєння (r) чи здійснить грандіозну соціальну програму (p.s). Але домовитися про цілях такий грандіозної програми неможливо. Отже якщо настане світ образу і нічого очікувати депресії, він здійснювати програму перевооружения».

(p (q ((q ((r (s))((s (p ((q (r = [pic] = [pic] тобто. міркування правильное.

Приклад скорочення тексту «Члени фінансового комітету мають обиратися серед членів дирекції. Не можна бути одночасно членом дирекції і членом бібліотечного ради, який був членом фінансового комітету. Член бібліотечного ради може бути членом фінансового комитета».

p — він член фінансового комітету q — він член дирекції r — він член бібліотечного фонду (p (q)(((p (((q®)((r ((p) = ((p + q)(p +(q +®((r +(p) = ((p +q)[pic] = ((p + q)[pic]=((p + q)((p (q +® = ((p + q)((p + q)(q +® = ((p + q)((q +® = (p (q)(((q® Отже, можна відкинути підкреслену частина текста.

Приклад аналізу міркування «(цей злочин припадають на Кустанаї (q). (Петров під час злочину був у Ростові (r). Отже (Петров не робив цього злочину ((p)». q (r ((p — не тавтология.

«Злочин припадають на Кустанаї. Тому якщо Петров зробив це злочин, то (він під час злочину був у Кустанаї (p.s). Але Петрова тим часом у Кустанаї був. Отже, Петров не робив цього злочину». q ((q (p (s)((p = … = 1 — тавтологія тобто. міркування правильное.

Міркування залишиться правильним, коли з нього викинути перше пропозицію відкинув і посилання нього у другому предложении:

(p (s)((s ((p = [pic] +(p = [pic] +(p = p + p. s +(p = 1 + p. s = 1.

Завдання. З’ясувати, хто із чотирьох винен з урахуванням інформації «Петров винен, лише коли винен Кулагин. Неправильно, що винність Родіонова тягне винність Сидорова І що Кулагин винен, а Сидоров немає». p, q, r, p. s — винен Петров, Кулагин, Родіонов, Сидоров. (p (q)(((r (s)(((q ((s) = ((p + q)[pic] = ((p + q) r (s ((q + p. s) = ((p + q)(r s (q = (p (q r (s тобто. Родіонов винен, інші не виновны.

Завдання Кислера. Обвинувачувані на підробці податкових документів Браун, Джонс і Сміт дають під присягою такі показания.

Браун: Джонс винен, а Сміт не виновен.

Джонс: Якщо Браун винен, то винен і Смит.

Сміт: Не винен, а хоча б них двох виновен.

Питання 1: Сумісні чи дані показания?

Питання 2: Яке показання випливає з другого?

Питання 3: Якщо всі винні, то хто лжесвидетельствует?

Питання 4: Якщо всі сказали правду, то хто виновен?

Питання 5: Якщо безневинний каже правду, а винний бреше, то хто винен, хто ж невиновен?

Б — винен Браун.

Д — винен Джонс.

З — винен Смит.

|Б |Д |З |(Б |(Д |(З |Б (Д |Д ((С |Б (С |(С ((Б (Д) | |Л |Л |Л |І |І |І |Л |Л |І |Л | |Л |Л |І |І |І |Л |Л |Л |І |Л | |Л |І |Л |І |Л |І |І |І |І |І | |Л |І |І |І |Л |Л |І |Л |І |Л | |І |Л |Л |Л |І |І |І |Л |Л |І | |І |Л |І |Л |І |Л |І |Л |І |Л | |І |І |Л |Л |Л |І |І |І |Л |І | |І |І |І |Л |Л |Л |І |Л |І |Л | |Свідчення |Брауна|Джонса |Сміта |.

1. Так, тільки завдяки традиційному третьої строки.

2. З першого третье.

3. Браун і Смит.

4. Джонс винен, інші невиновны.

5. Джонс невинний, інші виновны.

Тема 4. Кванторная логика.

чи логіка предикатів є розширенням пропозициональной логіки шляхом вивчення операцій (, (. З визначення операцій слід, що значення висловлювань (хp, (хp, розуміються відповідно як з'єднання p1(p2(p3(… і диз’юнкція p1(p2(p3(… значень висловлювання p для різноманітних значень перемінної x. Висловлення p називається кванторологически істинним за будь-якої интерпретации.

З визначень слід, що тавттологически справжнє висловлювання є кванторологически істинним. Протилежне власне кажучи неправильно: висловлювання (хp ((хp є кванторологически істинним, а не тавтологически истинным.

Истинностная таблиця. |(хp |(хp |(хp ((хp | |Л |Л |І | |Л |І |І | |І |Л |Л | |І |І |І |.

Истинностная схема. |p1, p2, p3… |(хp |(хp |(хp ((хp | | |p1(p2(p3(… |p1(p2(p3(… | | |ЛЛЛ… |Л |Л |І | |ЛЛЛ… |Л |І |І | |… |… |… |… | |ДІВ… |І |І |І |.

Висловлення q називається кванторологическим наслідком (з) висловлювань р1,…, pn, якщо p є справжнім у будь-якій інтерпретації, в якої істинними є p1,…, pn.

Входженням перемінної (в висловлювання p називається пов’язаним, якщо є вступом до деяке подвысказывание виду (х (q) чи виду (х (q); інакше це входження називається вільним. Наприклад, друге входження (1 в висловлювання ((g[pic]((1))((g[pic]((1, (2)))((((1(g[pic]((1))) є вільними, а третє і четверте — пов’язаними. Через р{х, а} позначається результат підстановки терма, а замість всіх вільних входжень перемінної x в висловлювання р, причому, якщо такий підстановці все входження змінних з, а залишаються вільними, то терм, а називається допустимим замінником для x в р. Наприклад, терм f[pic]((5) є допустимим замінником для (6 в висловлюванні g[pic](((5, ((6), і перестав бути допустимим замінником для (6 в висловлюванні ((5 (g[pic]((5, (6)). Висловлення р називається замкнутим (відкритим), якщо вона має вільних (пов'язаних) входжень переменных.

Теорему про всезначности перемінної: р = І тттк (хр = И.

Теорему про запереченні узагальнення і подтверждения:

((хр рівносильне (х (р

((хр рівносильне (х (р

Теорему про взаимоисключении кванторов:

(хр рівносильне ((х (р

(хр рівносильне ((х (р

Теорему про перестановочности кванторов:

(х (ур рівносильне (у (хр

(х (ур рівносильне (у (хр

Типові кванторы. Запис (qхр позначає висловлювання (х (q (р), а запис (qхр позначає висловлювання (х (q (р).

Теорему про равносильной заміні: нехай q є результатом заміни в висловлюванні р будь-якого входження подвысказывания r1 на висловлювання r2; тоді якщо r1 і r2 рівнозначні, то р і q теж равносильны.

Позитивним висловлюваннями називається таке, яка має входжень знака (. Позитивної формою висловлювання р називається будь-яке равносильное йому позитивне висловлення .

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

Приклад побудови позитивної форми заперечення висловлювання: «для кожного позитивного числа е існує позитивне число (т.ч. для кожного числа x з х.