Логічні висловлювання прикладів. Введення в алгебру висловлювань

Тут: 1 – істина, 0 – брехня.

• 1. Х: трикутник АВС- Гострокутний. Х: не так, що трикутник АВС - гострокутний. Це все одно, що: Х: трикутник АВС - прямокутний або тупокутний
• 2. А: Іванова М. На іспиті з математики отримала 4. : Невірно, що Іванова М. з математики отримала 4.

Визначення: Диз'юнкцією висловлювання А і В називається висловлювання АВ, дійсне за умови, що хоча б одне з висловлювань А або В істинно.

Його читають «А чи В».

Таблиця істинності для АВ

Приклад: 1. Цього разу відповідач прийшов і суд відбувся. - істина

2. У прямокутному трикутникусума двох будь-яких кутів більша або дорівнює третьому куту і гіпотенуза менше катета. - брехня

Визначення: Імплікацією висловлювань А і В називається висловлювання АВ, хибне лише за умови, що А істинно, а хибно.

Його читають: "Якщо А, то В".

Таблиця істинності

Приклад: 1. Якщо здам залік, то піду в кіно.

2. Якщо трикутник рівнобедрений, то кути за його підстави рівні. Визначення: Еквіваленцією висловлювань А і В називається висловлювання АВ, істинне в тому і тільки в тому випадку, коли А і В мають одну і ту ж істинність (тобто або обидва істинні, або обидва помилкові).

Читають: «А тоді і тільки тоді, коли» або «А необхідно і достатньо для»

Таблиця істинності

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

Приклад: Якщо Саратов розташований березі Неви, то Африці мешкають білі ведмеді.

А: Саратов розташований березі річки Неви;

В: В Африці мешкають білі ведмеді

Визначення: Формула, яка істинна незалежно від того, які значення набувають виразні змінні, що входять до неї, називається тавтологією або тотожно істинною формулою.

Визначення: Формули F 1 і F 2 називаються рівносильними, якщо їхня еквіваленція - тавтологія.

Визначення: Якщо формули F 1 і F 2 рівносильні, пропозиції Р 1 і Р 2 , які ініціюють ці формули, називаються рівносильними в логіці висловлювань.

Основні рівносильності, що найчастіше зустрічаються, називають законами логіки. Перерахуємо деякі з них:

• 1. Х Х - закон тотожності
• 2. Х Л – закон протиріччя
• 3. Х І - закон виключення третього
• 4. Х - закон подвійного заперечення

• 5. закони комутативності
• 6. Х (У Z) (Х У) Z закон асоціативності

Х (У Z) (Х У) Z закон дистрибутивності

7. закони Де Моргана

8. закони зчленування змінної з константою

Використовуючи закони логіки, можна перетворювати формули.

4. З безлічі формул, рівносильних між собою, розглянемо дві. Це - досконала кон'юнктивна нормальна форма(СКНФ) та досконала диз'юнктивна нормальна форма (СДНФ). Вони будуються для цієї формули з урахуванням її таблиці істинності.

Побудова СДНФ:

• - Вибираються рядки, що відповідають значенням істинності (1) даної формули;
• -- для кожного виділеного рядка складаємо кон'юнкцію змінних або їх заперечень так, щоб набори значень змінних, представлених у рядку, відповідали справжні значеннякон'юнкції (для цього треба змінні, які в цьому рядку приймали значення брехня (0) взяти зі знаком заперечення, а змінні, що приймають значення істинності (1) без заперечення);
• - Складається диз'юнкція отриманих кон'юнкцій.

З алгоритму випливає, що з будь-якої формули можна скласти СДНФ, і до того ж єдину, якщо формула є тотожно хибною, тобто. приймає лише помилкові значення.

Складання СКНФ здійснюється за таким алгоритмом:

• - Виділити ті рядки таблиці, в яких формула набуває значення брехня (0);
• - Зі змінних, що стоять у кожному такому рядку, скласти диз'юнкцію, яка повинна приймати значення - брехня (0). Для цього всі змінні повинні увійти до неї зі значенням брехня, отже ті, які є істинними (1), треба замінити їх запереченням;
• - З отриманих диз'юнкцій скласти кон'юнкцію.

Очевидно, що будь-яка формула, яка не є тавтологією, має СКНФ.

СДНФ та СКНФ використовуються для отримання наслідків з даної формули.

Приклад: Скласти таблицю істинності СДНФ та СКНФ для формули: .

Таблиця істинності СДНФ та СКНФ

5. Розглянемо висловлювальну форму «Річка впадає в Чорне море». Вона містить одну змінну і може бути представлена ​​у вигляді "Річка х впадає в Чорне море".

Залежно від значень змінної Х речення чи справжнім, чи хибним, тобто. задається відображення множини річок на двох елементне безліч. Позначимо це відображення, тоді:

Таким чином, маємо функцію, всі значення якої належать множині.

Визначення: Функція, всі значення якої належать множині, називається предикатом.

Літери, що позначають предикати, називаються предикатними символами.

Предикати можуть задаватися:

a) висловлювальною формулою,

b) формулою, тобто. задаючи інтерпретацію предикатного символу,

c) таблицею.

1) Р – «впадати у Чорне море».

Ця формула означає, що "Річка а впадає в Чорне море".

• 2) Предикат Р заданий висловлювальною формулою: «бути простим числомна множині перших 15 натуральних чисел».
• 3) У табличній форміпредикат має вигляд:

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

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

Якщо предикат містить одну змінну, його називають одномісним, дві змінні - двомісним, n змінних - n-місцевим предикатом.

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

Над предикатами виконуються також операції: заперечення, кон'юнкції, диз'юнкції, імплікації, еквіваленції.

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

Безліч істинності позначається.

Визначення: Запереченням предикату Р називається предикат, хибний при наборах значень змінних, які звертають Р в істинний, і істинний при тих наборах значень змінних, які звертають Р в хибний предикат.

Позначається заперечення.

Бути студентом АБІКу.

Не бути студентом АБІКу.

Якщо, то множина, де М - множина, на якій задані предикати Р і Q .

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

Бути футболістом

Бути студентом

: бути футболістом та бути студентом

Визначення: диз'юнкцією предикатів і називається предикат хибний при тих наборах змінних, що входять до нього, які обертають обидва предикати в хибні

Бути парним натуральним числом

Бути непарним натуральним числом

: бути натуральним числом

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

Позначається:

Бути простим числом на множині N

Бути непарним числом

Несправжній при і справжнім при інших натуральних числах.

Визначення: Еквіваленцією предикатів і називається предикат, який стає істинним, якщо обидва предикати і істинні, або обидва помилкові.

Позначається:

- "Виграти", тобто. х виграє у

Краще знати шахову історію, х знає краще у

позначає, що х виграє у у шахи тоді і тільки тоді, коли він краще знає теорію.

Визначення: Предикат випливає з предикату якщо імплікація істинна за будь-яких змінних, що входять до неї.

Позначаються прямування: .

Бути студентом

Ходити до інституту

Для перетворення предикату на висловлювання існують 2 шляхи:

1) надання змінної конкретного значення

; х – студент

Іванов – студент.

2) Навішування кванторів - будь-який, кожен, кожен

Існує, є.

Запис, де має властивість Р означає, що кожен предмет х має властивість Р. Або інакше, «всі х мають властивість Р».

Запис означає, що існує предмет х, що має властивість Р.

), яке висловлює деякий сенсі є або істинним, або хибнимале не тим і іншим відразу. Як правило, висловлювання мають дескриптивний, або описовий характер, і їх основним завданням є опис певної дійсності. Тим самим висловлювання виявляється або істинним або хибним; іноді допускається, що вона здатна приймати деякі «невизначені» значення істинності, проміжні між повною істиною та повною брехнею. Висловлювання, що розуміється таким чином, протиставляється зазвичай наказовим, запитальним, безглуздим і взагалі будь-яким іншим пропозиціям (наприклад, оцінки, норми, тимчасові твердження, що змінюють своє значення істинності з плином часу), оцінка істинності чи хибності яких неможлива. Поряд з оцінкою істинності висловлювання також розглядається у зв'язку з тими чи іншими модальностями("ймовірно", "можливо", "неможливо", "необхідно" та іншими). У сучасній логіці висловлювання формалізуються і застосовуються, головним чином, при застосуванні логічних обчислень у будь-якій конкретній галузі об'єктів.

За визначенням, будь-яке висловлювання має граматичніі логічніаспекти. Граматичний аспектвисловлювання виражається оповідальним пропозицією (простим чи складним), а логічний - його змістом і істинним значенням. Висловлювання, що включає інші висловлювання, називається складним(Складним); що не включає таких - простим(Неподільним). Будь-яке висловлювання висловлює деяку думка, що є його змістомі званою змістом висловлювання. Та чи інша істинна оцінка висловлювання називається його істинним значенням. Об'єкт, до якого належить висловлювання, називається предметом висловлювання.

У зв'язку з мовною практикоювиділяють методи вживання висловлювань. Мається на увазі, що висловлювання вживається ствердно, якщо метою його вживання є вираження правдивої думки. Ствердне вживання висловлювання - це їх найбільше часте вживання, оскільки висловлюючи свої думки, люди зазвичай претендують з їхньої істинність. Але висловлювання може вживатися просто як синтаксичне вираз. У разі, коли істинність змісту висловлювання однозначно не стверджується, мається на увазі нествердне вживання висловлювання. Одним із способів нествердного вживання висловлювань є їх непряме вживання. Воно має на меті не утвердження істинності думки, а лише передачу її змісту. Від різних видівВживання висловлювань слід відрізняти їх цитування, яке має на меті повідомити точний текст висловлювання (і лише за допомогою цього повідомлення висловити думку, що міститься в ньому). Тому цитовані висловлювання (які зазвичай входять до складу інших висловлювань) виділяються за допомогою тих чи інших знакових засобів (наприклад, за допомогою лапок). Непряме вживання висловлювань мало зустрічається у найбільш уживаних логічних обчисленнях, оскільки його припущення призводить до значних труднощів у формалізації.

У природних мовахоцінка висловлювань з погляду істинності часто залежить від цього, хто, коли у якому контексті застосував те чи інше висловлювання. Виразом цієї залежності є слова-індикатори, що включаються до висловлювань: «я», «ти», «тепер», «там» і так далі; Значення цих слів буває різним залежно від ситуації. При побудові штучних мов- інтерпретованих обчислень математичної логіки або мов-посередників при перекладі з однієї природної мови на іншу (див.) - відволікаються від залежності оцінки висловлювання від зазначених обставин, тобто виключають із розгляду прагматику мови (див. ), що дозволяє зробити поняття «висловлювання» точнішим.

При побудові найбільш елементарного логічного обчислення - двозначного обчислення висловлювань - виходять лише з розчленування висловлювань складові висловлювання. Ті висловлювання, які піддаються подальшому членування на складові, називаються елементарними. З них за допомогою логічних спілок (зазвичай для цього вибирається п'ять загальновідомих граматичних зв'язок: «ні», «і», «або», «якщо…, то» та «якщо…, і тільки якщо») складаються складні висловлювання. При побудові обчислення предикатів виходять із глибшого розчленування висловлювань окремі терміни (та інші мовні освіти). У основі аналізу висловлювань (зокрема елементарних) математичної логіки перебуває поняття предикату, чи логічної функції, тобто функції, яка кожному предмету аналізованої області предметів відносить або істину, або брехня. Логічні функції - те, що у логічному обчисленні зазвичай відповідає поняттям змістовного людського мислення. Наприклад, логічна функція, яка кожному з чисел 1 і 2 відносить істину, а кожному з чисел 3, 4, 5, … і так далі - брехня, відповідає поняттю "бути менше 3" (область предметів - цілі позитивні числа).

Висловлювання, які у мові логічні функції, власними силами не істинні і хибні, тобто є висловлюваннями. Такі висловлювання містять змінні і перетворюються на висловлювання при підстановці замість них імен предметів з цієї галузі (див. ). Таке, наприклад, вираз « x x вірно, що x x, яке менше 3», перше з них хибне, а друге істинно.

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

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

Слід зазначити, що поряд з терміном «висловлювання» іноді вживають також терміни «пропозиція» і «судження» - або як синоніми або за ними закріплюються значення, що їх розрізняють. Розрізнення зазначених понять відноситься до логічної семантики(див.), при цьому в логічній та філософській літературі з ним пов'язаний ряд дискусій. У цілому нині, дані розрізнення зводяться до наступного. Пропозиція як синтаксична освіта, що розглядається лише за формою, незалежно від змісту та оцінок істинності чи модальності, називають граматичною пропозицією. Висловлювання, що належать різним мовамі навіть тому самому мові, можуть висловлювати одну й ту саму думку. Якщо пропозиції, які мають однаковий зміст, але різняться як синтаксичні утворення, розглядаються як одне й те саме висловлювання, їх називають судженнями. Слід, проте, пам'ятати, що у сучасної логіці зазвичай користуються терміном «висловлювання», тоді як термін «судження» використовувався у традиційній логіці (див. ). У цілому нині, перелік різних видів висловлювань, досліджуваних логікою, показує, що область поняття висловлювання є гетерогенною і немає чітких кордонів.

Висловлювання – це розповідне речення(ствердження), про який можна говорити, що воно істинне чи хибне.

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

Приклад 1: А: "Москва - столиця Росії" - справжнє висловлювання.b= «Волга впадає у Чорне море» – хибне висловлювання.

Значення істинності висловлювань позначаються буквами І- «Істина» і Л- «брехня» або цифрами 1 - «Істина» і 0 - «брехня». Тобто, А= 1(І), b= 0 (Л).

Не всяке речення є висловлюванням. Так, до висловлювань не належать запитальні, і окликувальні пропозиції, оскільки говорити про їх істинність чи хибність немає сенсу. Не є висловлюваннями й такі пропозиції: Каша – смачна страва, Математика – цікавий предмет. Не може бути єдиної думки про те, чи є ці пропозиції правдивими. Пропозицію «Існують інопланетні цивілізації» слід вважати висловлюванням, оскільки об'єктивно вона або істинна, або хибна, хоча поки що ніхто не знає, яка саме.

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

Розглянемо пропозиції: «Він рудоволосий» та «Кількість ділиться на 7». Ці пропозиції не містять змінних у явному вигляді, але, проте, є висловлювальними формами: перше з них стає висловлюванням (справжнім чи хибним) лише після заміни займенника «він» ім'ям конкретної людини з деякої множини людей чоловічої статі; друге стає висловлюванням, якщо замість слова «число» підставляти цілі числа. Інакше ці пропозиції можна записати так: «Людина хрудоволосий», «Кількість уділиться на 7».

З висловлювальних форм можна отримувати висловлювання також за допомогою спеціальних слів, так званих кванторів. Їх два: 1) квантор загальності - (будь-який, кожен, кожен); 2) квантор існування – (є, знайдеться, є, деякий, щонайменше, один). Наприклад, з висловлювальної форми «Площа кімнати 20 м 2» можна за допомогою кванторів отримати висловлювання: «Площа будь-якої кімнати 20 м 2» – хибна, «Існує кімната, площа якої 20 м 2» – справжня. Пропозиції, утворені за допомогою квантора загальності, називаються загальноствердними ; пропозиції, утворені за допомогою квантора існування, називаються приватноствердними .

З цих пропозицій можна утворювати нові пропозиції з допомогою спілок «і», «або», «чи», «якщо…, то…», «…тоді і тоді, коли…» та інших. За допомогою частки «не» та словосполучення «невірно, що…» з однієї пропозиції можна отримати нове. Найбільш уживаними є спілки «і», «або», «якщо…, то…» та «…тоді й тільки тоді, коли». Інші спілки вважають близькими за змістом одному з перерахованих спілок.

Союзи «і», «або», «якщо, то», «тоді й тільки тоді, коли», а також частинку «не» (словосполучення «неправильно, що») називають логічними зв'язками.

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

Приклад 2: З пропозицій «Сонце сходить на сході» та «Сонце заходить на заході» можна отримати наступні складові висловлювання: «Сонце сходить на сході ізаходить на заході»; «Сонце сходить на сході абозаходить на заході»; « Якщосонце сходить на сході, товоно заходить на заході»; «Сонце сходить на сході тоді і лише тоді, коливоно заходить на заході»; «Сонце несходить на сході» або « Невірно, щосонце заходить на заході».

У граматиці розрізняють пропозиції прості та складні. Пропозиція, просте за своєю граматичною структурою, може бути складною з погляду логіки. Наприклад, просте з погляду граматики пропозиція «На вулиці холодно і сиро» вважається у логіці складною, оскільки утворена за допомогою логічного зв'язування «і» з двох елементарних пропозицій «На вулиці холодно» та «На вулиці сиро». Проста пропозиція «Завтра не буде опадів» за своєю логічною структурою не є елементарною, оскільки містить логічну зв'язку «не».

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

Процес отримання складових висловлювань за допомогою логічних зв'язок називається логічною операцією.

За кількістю логічних зв'язок виділяють п'ять логічних операцій.

1. Негація (заперечення) - єдина операція, яка може застосовуватися до одного висловлювання.

Негацією висловлювання називається нове висловлювання, яке істинно тоді і тільки тоді, коли саме висловлювання хибне і хибне, коли саме висловлювання істинне.

Негація позначається , або ¬ b, читається: "не А" або "невірно, що А".

Наприклад, висловлювання А= «Місяць – супутник Марса» – хибне, а висловлювання = «Невірно, що Місяць – супутник Марса» – дійсне.

Для довільного висловлювання Авизначення зручно записувати за допомогою так званої таблиці істинності:

Приклад 3:Сформулювати заперечення висловлювань: А= «Курган – велике місто»; У= «Сир роблять із молока»; З= "32 не ділиться на 4"; D= "Всі пси потрапляють до раю".

Рішення. = « Невірно, щоКурган – велике місто»; = «Сир роблять нез молока»; = "32 ділиться на 4"; = « Невсі пси потрапляють до раю» = « Деякіпси непотрапляють до раю».

Заперечення складних висловлювань найчастіше формулюються за допомогою словосполучення «невірно, що…». Наприклад: Висловлювання Е = «23 березня 1917 року у Москві ранок було морозним і сонячним»; заперечення: = « Невірно, що 23 березня 1917 року в Москві ранок був морозним та сонячним»

2. Кон'юнкція (логічне множення) – від латинського conjunctio- З'єднання.

Кон'юнкцією двох висловлювань називається нове висловлювання, яке істинно тоді й тільки тоді, коли обидва висловлювання є істинними.

Кон'юнкція позначається
або А&B; читається: « Аі У».

Таблиця істинності для кон'юнкції виглядає так:

Приклад 4:Визначити значення істинності висловлювань «Париж розташований на Сені та 2+3=5»; «1 – просте число та 2 – просте число»; «Число 3 – парне та ведмеді живуть в Африці».

Рішення.Перше висловлювання є кон'юнкцією двох висловлювань А =«Париж розташований на Сені» та УАУ= 1. Отже,
= 1.

Друге висловлювання є кон'юнкцією висловлювань А= «1 – просте число» ( А= 0) та У= «2 – просте число» ( У= 1). Отже,
= 0.

Третій вислів є кон'юнкцією двох хибних висловлювань, отже,
=0.

3. Диз'юнкція (логічне додавання) – від латинського disjunction- Поділ.

Диз'юнкцією двох висловлювань є нове висловлювання, яке хибне тоді і тільки тоді, коли обидва висловлювання хибні.

Диз'юнкція позначається
і читається « Аабо У».

Таблиця істинності для диз'юнкції виглядає так:

Приклад 5:Визначити значення істинності висловлювань «Париж розташований на Сені або 2+3=5»; "1 - просте число або 2 - просте число"; "Число 3 - парне або ведмеді живуть в Африці".

Рішення.Перше висловлювання є диз'юнкцією двох висловлювань А =«Париж розташований на Сені» та У= "2 + 3 = 5". Значення істинності висловлювання А= 1 та значення істинності висловлювання У= 1. Отже,
= 1.

Друге висловлювання є диз'юнкцією висловлювань А= «1 – просте число» ( А= 0) та У= «2 – просте число» ( У= 1). Отже,
= 1.

Третій вислів є диз'юнкцією двох хибних висловлювань, отже,
=0.

4. Імплікація (логічне слідство).

Імплікацією двох висловлювань називається нове висловлювання, яке є хибним тоді і тільки тоді, коли перше висловлювання істинне, а друге – хибне.

Імплікація позначається
або
, читається «Якщо А, то У» («Коли Атоді У», « А, отже У»).

Таблиця істинності імплікації виглядає так:

Компоненти імплікації мають власні «імена»: пропозиція Аназивається посилкою або антецедентом , пропозиція У – висновком або консеквентом .

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

1)
= «Якщо дощ іде, то асфальт мокрий = 1;

2)
= "Якщо дощ йде, то асфальт сухий" = 0;

3)
= "Якщо дощ не йде, то асфальт мокрий" = 1 (пройшла поливальна машина або розтанув сніг);

4)
= "Якщо дощ не йде, то асфальт сухий" = 1.

Прийняте визначення імплікації відповідає вживанню союзу «якщо…, то…» у математиці, а й у повсякденної, повсякденної промови. Так, наприклад, звернення приятеля «Якщо буде хороша погода, то я прийду до тебе в гості» ви розціните як брехню в тому і тільки в тому випадку, якщо погода буде гарною, а приятель до вас у гості не прийде.

Водночас визначення імплікації змушує вважати істинними висловлюваннями такі пропозиції, як «Якщо 2×2 = 4, то Москва – столиця Росії» або «Якщо 2×2 = 5, то є відьми». Ці пропозиції, мабуть, здаються безглуздими. Справа в тому, що ми звикли поєднувати союзом «якщо…, то…» (так само, як і іншими спілками) пропозиції, пов'язані за змістом. Але визначеннями логічних операцій значення складових висловлювань не враховується; вони сприймаються як об'єкти, які мають єдиним властивістю – бути істинними чи хибними. Тому не варто бентежитися «безглуздістю» деяких складових висловлювань, їхній зміст не входить до нашого розгляду.

5. Еквіваленція (логічна рівносильність).

Еквіваленцією двох висловлювань називається нове висловлювання, яке істинно тоді і лише тоді, коли обидва висловлювання одночасно істинні чи хибні.

Еквівалент позначається
або
читається « Атоді і лише тоді, коли У».

Таблиця істинності для еквіваленції виглядає так:

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

Приклад 7:Нехай через Апозначено вислів «9 ділиться на 3», а через У- Вислів «10 ділиться на 3». Складіть висловлювання, що мають логічну структуру: а)
; б)
; в)
; г)
; д)
; е)
та визначте їх значення істинності.

Рішення.а)
= "Якщо 9 ділиться на 3, то 10 ділиться на 3" = 0, т.к. А= 1, а У= 0. б)
= "Якщо 10 ділиться на 3, то 9 ділиться на 3" = 1. в)
= "9 ділиться на 3 тоді і тільки тоді, коли 10 ділиться на 3" = 0. г)
= "10 ділиться на 3 тоді і тільки тоді, коли 9 ділиться на 3" = 0. д)
= «Якщо 9 ділиться на 3, то 10 ділиться на 3» = 1 (т.к. А= 1, то = 0 і У= 0, отже,
= 1). е)
= "9 ділиться на 3 тоді і тільки тоді, коли 10 не ділиться на 3" = 1 ( А= 1 і = 1, тоді
= 1).

Основним (невизначуваним) поняттям математичної логіки є поняття «простого висловлювання».

Під висловлюванням зазвичай розуміють будь-яке оповідальне речення, що стверджує щось про що-небудь, і при цьому ми можемо сказати, істинно воно або хибно в даних умовах місця і часу. Логічними значеннями висловлювань є «істина» та «брехня».

Наведемо приклади висловлювань:

1) Новгород стоїть на Волхові.

2) Париж – столиця Англії.

3) Карась не риба.

4) Число 6 ділиться на 2 та на 3.

5) Якщо юнак закінчив середню школу, він отримує атестат зрілості.

Висловлювання 1), 4), 5) істинні, а 2) та 3) – хибні.

Очевидно, пропозиція «Хай живуть наші спортсмени!» не є висловлюванням.

Висловлювання, що є одним твердженням, прийнято називати простим або елементарним. Прикладами елементарних висловлювань можуть бути висловлювання 1) і 2).

Висловлювання, що виходять з елементарних за допомогою граматичних зв'язок «не», «і», «або», «якщо…, то…», «тоді й тільки тоді», прийнято називати складними чи складовими. Так, висловлювання 3) виходить із простого висловлювання «Карась – риба» за допомогою заперечення «не», висловлювання 4) утворено з елементарних висловлювань «Число 6 ділиться на 2», «Число 6 ділиться на 3», з'єднаних союзом «і». 5) виходить з простих висловлювань«Юнак закінчив середню школу», «Юнак отримує атестат зрілості» за допомогою граматичної зв'язки «якщо …,
то …». Аналогічно складні висловлювання можуть бути отримані із простих висловлювань за допомогою граматичних зв'язок «або», «тоді й тільки тоді».

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

Надалі елементарні висловлювання позначатимемо літерами латинського алфавіту: a, b, c, …, x, y, z, …;справжнє значення – буквою І чи цифрою 1, а хибне значення – буквою Л чи цифрою 0.

Якщо висловлювання аістинно, то писатимемо а=1якщо ж хибно, то а=0.

Логічні висловлювання прийнято поділяти на два види: елементарні логічні висловлювання та складові логічні висловлювання.

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

Логічна зв'язка – це будь-яка логічна операція над висловлюванням. Наприклад, вживані у звичайній мові слова та словосполучення "ні", "і", "або", "якщо… , то", "тоді і тільки тоді"є логічними зв'язками.

Елементарні логічні висловлювання- це висловлювання, що не належать до складових.

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

46. ​​Елементи алгебри логіки

Алгебра логіки – це розділ математичної логіки, значення всіх елементів (функцій та аргументів) якої визначено у двоелементній множині: 0 та 1. Алгебра логіки оперує з логічними висловлюваннями.

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

Висловлювання:

– “Зараз йде сніг” – це твердження може бути істинним чи хибним;

- "Вашингтон - столиця США" - справжнє твердження;

- "Приватне від розподілу 10 на 2 дорівнює 3" – хибне твердження.

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

Найпростішими операціями в алгебрі логіки є операції логічного додавання (інакше: операція АБО(OR), операція диз'юнкції)і логічного множення(інакше: операція І (AND),операція кон'юнкції).Для позначення операції логічного додавання використовують символи + або V, а логічного множення – символи або Правила виконання операцій в алгебрі логіки визначаються рядом аксіом, теорем та наслідків. Зокрема, для алгебри логіки застосовні закони:

1. Сполучний:

47. (a + b) + с = а +(b + с),

48. (а b) з= а(b з).

2. Пересувний:

49. (а + b) = (b + a),

50. (а b)= (b а).

3. Розподільний:

51. а (b + с) = а b + (aс),

52. (а + b) с = а с + b с.

Справедливі співвідношення, зокрема:

53. а + а = аа + b = b,якщо а ≤ b,

54. а а = аа b= а, якщо a ≤ b,

a + a b = aa b = b,якщо а≥ b,

а + b = а,якщо а≥ b.

Найменшим елементом логіки алгебри є 0, найбільшим елементом- 1. В алгебрі логіки також вводиться ще одна операція - заперечення(операція НЕ (NOT), інверсія),що позначається рисою над елементом.

За визначенням

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

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

Тема 2. Висловлювання. Логічні операції з них

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

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

приклад.Не є висловлюваннями речення:

1) число 0,00000001 дуже мало;

2) чи існує число, квадрат якого дорівнює 2?

4) .

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

Пропозиція, про яку неможливо однозначно вирішити питання, істинно вона чи хибна, висловлюванням не є.

Будь-яке висловлювання є або істинним, або хибним(Закон виключеного третього).

Жодне висловлювання не може бути одночасно істинним і хибним(Закон протиріччя).

Невизначені висловлювання

Позначатимемо через N безліч усіх натуральних чисел. Через х позначимо довільний елементмножини N. Розглянемо такі пропозиції:

,

.

Пропозиції A(x), B(x), C(x), D(x) висловлюваннями є, т.к. про істинність, наприклад, A(x) ми нічого не можемо сказати, поки нам не відомо число х. Однак, підставляючи в A(x) замість х різні натуральні числа, ми отримуватимемо висловлювання про натуральні числа – іноді справжні, іноді помилкові. Наприклад:

Справжнє висловлювання;

Помилкове висловлювання.

Пропозиції A(x), B(x), C(x), D(x), що містять змінну х , називають невизначеними висловлюваннями (предикатами).Якщо замість х підставити число, ми отримаємо звичайне висловлювання.

Невизначений вислів може бути поставлений на будь-якій множині. Воно є висловом про якийсь елемент х розглянутої множини.

Часто доводиться розглядати невизначені висловлювання, до яких входить не одне, а два чи більша кількістьзмінних.

приклад. ;

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

- справжнє висловлювання;

- хибне висловлювання;

- хибне висловлювання;

- хибне висловлювання;

- справжнє висловлювання.

Логічні операції над висловлюваннями

Висловлювання позначають латинськими літерами A, B, C, …, їх значення істина і брехня відповідно, через «І» та «Л». Складні висловлювання отримують із простих за допомогою логічних операцій, до яких належать заперечення, кон'юнкція, диз'юнкція, імплікація, еквівалентність(еквівалентність) .

1. Якщо А- Висловлювання, то заперечення висловлювання А визначається як такий вислів, який істинний тоді і тільки тоді, коли висловлювання Апомилково. Заперечення висловлювання Апозначається (або Ø А) і читається « не А».

Істинність-хибність операції заперечення висловлює істинна таблиця 1.1.

Таблиця 1.1

приклад. 1); .

2) ; .

3) ; .

4) ; .

Яким би не було висловлювання А, із двох висловлювань А, А одне є істинним, а інше – хибним.

Закон заперечення заперечення: Подвійне заперечення А істинно в тому і тільки в тому випадку, якщо істинно саме висловлювання А (тобто якщо А істинно, то й А істинно, а якщо А хибно, то і А хибно).

2. Кон'юнкцією двох висловлюваньназивається таке висловлювання, яке істинно тоді і тільки тоді, коли обидва складові її висловлювання є істинними.

Якщо А, У- висловлювання, їх кон'юнкція позначається A Ù B(або А & B) і читається « Аі У».

Кон'юнкції відповідає істинна таблиця 1.2.

Таблиця 1.2

Приклад:Висловлювання - істинно, висловлювання - істинно, тому істинна та його кон'юнкція .

3. Диз'юнкцією двох висловлюваньназивається таке висловлювання, яке хибне тоді і тільки тоді, коли обидва складові її висловлювання хибні.

Якщо А, У- два висловлювання, то їхня диз'юнкція позначається А Ú Уі читається « Аабо У». Союз «або» тут вживається в сполучному, а не в розділовому значенні, тобто для істинності висловлювання А Ú Удопускається також випадок істинності обох висловлювань А, У.

Операції диз'юнкції відповідає істинна таблиця 1.3.

Таблиця 1.3

Приклад:Висловлювання - істинно, висловлювання - Помилково. Тоді висловлювання - Істинно.

4. Імплікація висловлювань А, Ввизначається як таке висловлювання, яке помилкове тоді і тільки тоді, коли висловлювання Аістинно, а висловлювання Упомилково. Імплікація двох висловлювань А, Упозначається АÞ Уі читається «якщо А, то У». Висловлювання Аназивається посилкою імплікації , а У - висновком .

Імплікації відповідає істинна таблиця 1.4.

Таблиця 1.4

5. Еквівалентність двох висловлювань А, Увизначається як висловлювання, яке істинно тоді і лише тоді, коли висловлювання А, Уобидва істинні або обидва помилкові. Позначається А Û Уі читається « Атоді і лише тоді, коли У»(«якщо А, то У, і якщо У, то А», « Ає необхідна та достатня умова для У»). Значення еквівалентності визначені в таблиці 1.5.

Таблиця 1.5

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

Тоді ознаку ділимості на 3 можна записати як (Число ділиться на 3 тоді і тільки тоді, коли сума його цифр ділиться на три).

Якщо теорема сформульована у вигляді AÞ B, то вона називається ознакою або достатньою умовою для B, де A, B- Деякі висловлювання.

Теорема типу У Þ Аназивається зворотній для теореми AÞ B.

Якщо теорема має вигляд AÛ B, то вона називається критерієм або необхідними та достатніми умовами для B.

Теорема такого типу поєднує пряму та зворотну теореми.

Теорема типу називається протилежної до зворотної теореми .

Висловлювання AÞ Bістинно тоді і тільки тоді, коли істинно висловлювання . На цьому факті засновано метод доказу від протилежного .

Приклад:Нехай висловлювання, а. Тоді .

Цю теоремуприйнято висловлювати в наступному вигляді:

А є достатньою умовою для Ст.

У є необхідною умовою для А.

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

©2015-2019 сайт
Усі права належати їх авторам. Цей сайт не претендує на авторства, а надає безкоштовне використання.
Дата створення сторінки: 2017-10-25