Приклад 1. Встановити істинність висловлювання · Рішення. До складу складного висловлювання входять 3 простих висловлювання: А, У, З.

У таблиці заповнюються стовпчики значеннями (0, 1). Вказуються всі можливі ситуації. Прості висловлювання від складних відокремлюються подвійною вертикальною межею. При складанні таблиці треба стежити, щоб не переплутати порядок дій; заповнюючи стовпці, слід рухатися “зсередини назовні”, тобто. від елементарних формул до більш складних; стовпець, що заповнюється останнім, містить значення вихідної формули.

А	У	З		А+		· З
0	0	0	1	1	0	0
0	0	1	1	1	0	0
0	1	0	0	0	1	0
0	1	1	0	0	1	1
1	0	0	1	1	0	0
1	0	1	1	1	0	0
1	1	0	0	1	0	0
1	1	1	0	1	0	0

З таблиці видно, що це висловлювання істинно лише у разі, коли А=0, В=1, С=1. У решті випадків воно хибне.

Ви також можете знайти цікаву інформацію в науковому пошуковику Otvety.Online. Скористайтеся формою пошуку:

Ще за темою 1. Встановлення істинності складних висловлювань.

1. 29. Проблема дозвільності в алгебрі висловлювань (АВ). Алгоритми перевірки формул алгебри висловлювань тотожну істинність: складання таблиці істинності, виконання рівносильних перетворень (аналіз КНФ), алгоритм редукції, алгоритм Квайна. Переваги та недоліки зазначених методів.
2. Питання 6. Обчислення висловлювань. Аксіоми. Правило виведення. Висновок. Тотожна істинність формул, що виводяться (довести). Несуперечність обчислення висловлювань. Теорема про повноту обчислення висловлювань. Проблема розв'язності. Обчислення висловлювань. Проблема розв'язності

Значення істинності

Ця стаття або розділ – грубий переклад статті іншою мовою (див. Перевірка перекладів). Він міг бути згенерований програмою-перекладачем або зроблений людиною зі слабкими знаннями у мові оригіналу. ¬( Шаблон:Mvar∧Шаблон:Mvar) ⇔ ¬Шаблон:Mvar ∨ ¬Шаблон:Mvar ¬( Шаблон:Mvar∨Шаблон:Mvar) ⇔ ¬Шаблон:Mvar ∧ ¬Шаблон:Mvar Багатозначна логіка Багатозначна логіка (наприклад, нечітка логіка дозволяє більше двох значень істинності, які, можливо, містять деякі внутрішні структури. Алгебраїчна семантика Не всі логічні системи істинно-ціннісні у цьому сенсі, що логічні зв'язки може бути інтерпретовані як істина функцій. Наприклад, в інтуїціоністській логіці відсутня повний набір значень істинності, тому що його семантика визначається в термінах доказовості умови, а не безпосередньо в термінах обов'язкової вірності формул. В інших теоріях Інтуїціоністська теорія типів використовує типи замість значень істинності. Топос теорії використовує значення істинності в особливому значенні: істина значення топос є глобальним елементом х подоб'єктом класифікатором. Маючи значення істинності у сенсі немає ціннісної логіки істини. Див. також Посилання Wikimedia Foundation. 2010 . Дивитись що таке "Значення істинності" в інших словниках: Зміст, позначений тим чи іншим мовним словом, пропозицією, знаком тощо. Питання про З. мовних виразів досліджується лінгвістикою, семіотикою та логічною семантикою. Розрізняють предметне, смислове та експресивне З. мовних … Філософська енциклопедія Значення істинності (у логіці), значення, яке набуває Висловлювання (пропозиція, судження), що розглядається стосовно змісту, що в ньому відображається. У звичайній (класичній) логіці використовуються два І. з. "істинно", "хибно"; в… … Велика Радянська Енциклопедія Таблиця істинності таблиця, що описує логічну функцію. Під «логічною функцією» в даному випадку розуміється функція, у якої значення змінних (параметрів функції) та значення самої функції виражають логічну істинність. Таблиця, за допомогою якої встановлюється істиннісне значення складного висловлювання при даних значеннях простих висловлювань, що входять до нього. У класичній математичній логіці передбачається, що кожне просте (що не містить логічних… Словник термінів логіки Денотат (від лат. denotatum позначене), термін лінгвістики та екстенсіональної логіки, що означає 1) екстенсіонал, 2) десігнат, 3) референт та 4) семантичне ядро ​​значення. Зміст 1 Денотат як екстенсіонал 2 Денотат як десігнат … Вікіпедія Однією з можливих характеристик висловлювання з погляду відповідності його описуваному фрагменту дійсності. Якщо допускається, що кожне висловлювання є або істинним, або хибним (тобто воно відповідає дійсності …). Словник термінів логіки Сукупність логічних систем, що спираються на принцип багатозначності. У класичній двозначній логіці висловлювання при інтерпретації набувають лише двох значень «істинно» і «хибно», в М.Л. розглядаються та ін значення, напр. «невизначено», … Філософська енциклопедія - (Від лат. factum зроблене, що відбулося) 1) синонім понять «істина», «подія», «результат»; щось реальне на противагу вигаданому; конкретне, одиничне на відміну абстрактного та загального; 2) у філософії науки особливого роду п... Філософська енциклопедія - (В л о г і к е) - істинність пропозиції (судження, висловлювання), обумовлена, на відміну від т.зв. логіч. істинності, змістом цієї пропозиції. Інакше кажучи, пропозиція є фактично істинною, коли її істинність залежить від значень. Філософська енциклопедія Стереометрична семантика- трактування логіки як науки отримання справжніх наслідків з справжніх посилок дедалі більше поступається місцем ширшої концепції, пов'язаної чи з узагальненням поняття слідування, заснованого на традиційної істиннісної оцінці і практичних… … Проектний філософський словник Книги Як щиро повірити в Бога, або Єдине, що має значення для розвитку віри, Враджев В.. Перш ніж зробити перші кроки в духовне життя, кожна людина завжди ставить питання: Чи існує Бог насправді? навколишній світ за допомогою…

1.1 . Які з наведених пропозицій є висловлюваннями?

а) Москва - столиця Росії.

б) студент фізико-математичного факультету педагогічного інституту.

в) Трикутник ABC подібний до трикутника А "В"С".

г) Місяць є супутником Марса.

е) Кисень - газ.

ж) Каша – смачна страва.

з) Математика – цікавий предмет.

і) Картини Пікассо надто абстрактні.

к) Залізо важче за свинець.

л) Хай живуть музи!

м) Трикутник називається рівностороннім, якщо його сторони рівні.

н) Якщо у трикутнику всі кути рівні, то він рівнобічний.

о) Сьогодні погана погода.

п) У романі А. З. Пушкіна «Євгеній Онєгін» 136 245 букв.

р) Річка Ангара впадає у озеро Байкал.

Рішення. б) Ця пропозиція не є висловлюванням, тому що вона нічого не стверджує про студента.

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

ж) Пропозиція не є висловлюванням, оскільки поняття «смачне блюдо» надто невизначене.

п) Пропозиція – висловлювання, але з'ясування його значення істинності потрібно витратити чимало часу.

1.2. Вкажіть, які з висловлювань попереднього завдання є істинними, а які є хибними.

1.3. Сформулюйте заперечення таких висловлювань; вкажіть значення істинності даних висловлювань та їх заперечень:

а) Волга впадає у Каспійське море.

б) Число 28 не поділяється на число 7.

д) Усі прості числа непарні.

1.4. Встановіть, які з висловлювань у наступних парах є запереченнями один одного і які ні (поясніть чому):

а) 2< 0, 2 > 0. -

б) 6< 9, 6  9.

в) "Трикутник ABC прямокутний", "Трикутник ABC тупокутний".

г) «Натуральне число nпарно», «Натуральне число nнепарно».

д) «Функція fнепарна», «Функція fпарна».

е) «Усі прості числа непарні», «Усі прості числа парні».

ж) «Усі прості числа непарні», «Існує просте парне число».

з) «Людині відомі всі види тварин, що мешкають на Землі», «На Землі існує вид тварин, не відомий людині».

і) «Існують ірраціональні числа», «Всі числа раціональні».

Рішення.а) Вислів «2 > 0» не є запереченням «висловлювання «2< 0», потому что требование не быть меньше 0 оставляет две возможности: быть равным 0 и быть больше 0. Таким образом, отрицанием высказывания «2 < 0» является высказывание «2  0».

1.5. Наступні висловлювання запишіть без знаку заперечення:

а)
; в)
;

б)
; г)
.

1.6.

а) Ленінград розташований на Неві та 2 + 3 = 5.

б) 7 - просте число та 9 - просте число.

в) 7 - просте число або 9 - просте число.

г) Число 2 парне або число просте.

д) 2  3, 2  3, 2 2  4, 2 2  4.

е) 22 = 4 або білі ведмеді живуть в Африці.

ж) 2 2 = 4, і 2 2  5, і 2 2  4.

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

1.7. Визначте значення істинності висловлювань А, В, С, D та Е, якщо:

 справжні висловлювання, а

 хибні.

Рішення.в) Диз'юнкція висловлювань є справжнє висловлювання лише у разі, коли щонайменше одне з входять до диз'юнкції складових висловлювань (членів диз'юнкції) істинно. У нашому випадку друге складове висловлювання «2 2 = 5» хибне, а диз'юнкція двох висловлювань істинна. Тому перший складовий вислів Зістинно.

1.8. Сформулюйте та запишіть у вигляді кон'юнкції чи диз'юнкції умову істинності кожної пропозиції ( аі b- дійсні числа):

а)
г) ж)

б)
д)
з)

в)
е)
і)

Рішення.г) Дроб дорівнює нулю лише у разі, коли чисельник дорівнює нулю і знаменник не дорівнює нулю, тобто ( а = 0) & (b  0).

1.9. Визначте значення істинності таких висловлювань:

а) Якщо 12 ділиться на 6, то 12 ділиться на 3.

б) Якщо 11 ділиться на 6, то 11 ділиться на 3.

в) Якщо 15 ділиться на 6, то 15 ділиться на 3.

г) Якщо 15 ділиться на 3, то 15 ділиться на 6.

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

е) 12 ділиться на 6 і тоді, коли 12 ділиться на 3.

ж) 11 ділиться на 6 і тоді, коли 11 ділиться на 3.

з) 15 ділиться на 6 і тоді, коли 15 ділиться на 3.

і) 15 ділиться на 5 і тоді, коли 15 ділиться на 4.

к) Тіло масою mмає потенційну енергію mghтоді і лише тоді, коли воно знаходиться на висоті hнад поверхнею землі.

Рішення.а) Оскільки висловлювання-посилка «12 ділиться на 6» істинно і, висловлювання-наслідок «12 ділиться на 3» істинно, те й складове висловлювання виходячи з визначення імплікації також істинно.

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

1.10. Нехай через А позначено вислів «9 ділиться на 3», а через В – вислів «8 ділиться на 3». Визначте значення істинності таких висловлювань:

а)
г)
ж)
к)

б)
д)
з)
л)

в)
е)
і)
м)

Рішення.е) Маємо
,
. Тому

1.11.

а) Якщо 4 – парне число, то А.

б) Якщо В, то 4 – непарне число.

в) Якщо 4 – парне число, то С.

г) Якщо D, то 4 – непарне число.

Рішення.а) Імплікація двох висловлювань є хибне висловлювання лише у разі, коли посилка істинна, а висновок хибно. У разі посилка «4  парне число» істинна і за умовою все висловлювання також істинно. Тому висновок А помилковим не може, т. е. висловлювання А істинно.

1.12. Визначте значення істинності висловлювань А, В, С і D у наступних реченнях, з яких перші два істинні, а останні два помилкові:

а)
; б)
;

в)
; г)
.

1.13. Нехай через А позначено вислів «Цей трикутник рівнобедрений», а через В – вислів «Цей трикутник рівносторонній». Прочитайте такі висловлювання:

а)
г)

б)
д)

в)
е)

Рішення.е) Якщо трикутник рівнобедрений і нерівносторонній, то невірно, що він нерівностегновий.

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

а) Якщо 18 ділиться на 2 і не ділиться на 3, воно не ділиться на 6.

б) Добуток трьох чисел дорівнює нулю і тоді, коли одне їх дорівнює нулю.

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

г) Якщо у трикутнику медіана не є висотою та бісектрисою, то цей трикутник не рівнобедрений і не рівносторонній.

Рішення.г) Виділимо і в такий спосіб позначимо найпростіші складові висловлювання:

А: "У трикутнику медіана є висотою";

В: «У трикутнику медіана є бісектриса»;

З: «Цей трикутник рівнобедрений»;

D: "Цей трикутник рівносторонній".

Тоді цей вислів символічно записується так:

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

а) істинно тоді й лише тоді, коли обидва дані висловлювання хибні;

б) хибно тоді й лише тоді, коли обидва дані висловлювання дійсні.

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

1.17. Нехай висловлювання
істинно. Що можна сказати про логічне значення висловлювання?

1.18. Якщо висловлювання
істинно (хибно), те що можна сказати про логічне значення висловлювань:

а)
; б)
; в)
; г)
?

1.19. Якщо висловлювання
істинно, а висловлювання
хибно, що можна сказати про логічне значення висловлювання
?

1.20. Чи існують три такі висловлювання А, В, С, щоб одночасно висловлювання
було істинним, висловлювання
 хибним та висловлювання
 хибним?

1.21. Для кожного з наведених нижче висловлювань визначте, чи достатньо наведених відомостей, щоб встановити його логічне значення. Якщо достатньо, то вкажіть це значення. Якщо недостатньо, то покажіть, що можливі і те, й інше істинні значення:

Рішення.а) Оскільки висновок імплікації є істинним, то і вся імплікація буде істинним висловом незалежно від логічного значення посилки.

Властивості

Розглянемо кілька властивостей декартового твору:

1. Якщо A,B- кінцеві множини, то A× B- Кінцеве. І навпаки, якщо одна з множин-множників нескінченна, то і результат їх твору - нескінченна множина.

2. Кількість елементів у декартовому творі дорівнює добутку чисел елементів множин-співмножників (у разі їхньої кінцівки, зрозуміло): | A× B|=|A|⋅|B| .

3. A np ≠(A n) p- у першому випадку доцільно розглянути результат декартового твору як матрицю розмірів 1× np, у другому ж - як матрицю розмірів n× p .

4. Комутативний закон не виконується, т.к. пари елементів результату декартового твору впорядковано: A× B≠B× A .

5. Асоціативний закон не виконується: ( A× B)× C≠A×( B× C) .

6. Має місце дистрибутивність щодо основних операцій на множинах: ( A∗B)× C=(A× C)∗(B× C),∗∈{∩,∪,∖}

11. Поняття висловлювання. Елементарні та складові висловлювання.

Висловлювання- це твердження чи оповідне речення, про яку можна сказати, що воно істинно (І-1) або хибно (Л-0), але не те й інше одночасно.

Наприклад, "Сьогодні йде дощ", "Іванов виконав лабораторну роботу №2 з фізики".

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

Хоча висловлювання типу «Сьогодні не четвер» не складено з двох різних простих висловлювань, для одноманітності конструкції воно також розглядається як складове, оскільки його істиннісне значення визначається істинним значенням іншого висловлювання «Сьогодні четвер»

приклад 2.Наступні висловлювання розглядаються як складові:

Я читаю «Московський комсомолець» і читаю «Комерсант».

Якщо він сказав це, значить, це правильно.

Сонце не є зіркою.

Якщо буде сонячно і температура перевищить 25 0, я приїду поїздом чи автомобілем

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

12. Операції над висловлюваннями.

1. Операція заперечення.

Запереченням висловлювання А (читається «не А», «Невірно, що А»), яке істинно, коли Ахибно і хибно, коли А- Істинно.

Висловлювання, що заперечують одне одного Аі називаються протилежними.

2. Операція кон'юнкції.

Кон'юнкцієювисловлювань Аі Уназивається висловлювання, що позначається А В(читається « Аі У»), справжні значення якого визначаються в тому і лише тому випадку, коли обидва висловлювання Аі Уістинні.

Кон'юнкцію висловлювань називають логічним твором та часто позначають АВ.

Нехай дано висловлювання А– «у березні температура повітря від 0 Сдо + 7 С» та висловлювання У- «У Вітебську йде дощ». Тоді А Вбуде наступною: «у березні температура повітря від 0 Сдо + 7 Сі у Вітебську йде дощ». Ця кон'юнкція буде істинною, якщо будуть висловлювання Аі Уістинними. Якщо ж виявиться, що температура була меншою 0 Сабо у Вітебську не було дощу, то А Вбуде хибною.

3 . Операція диз'юнкції.

диз'юнкцієювисловлювань Аі Уназивається висловлювання А В (Аабо У), яке істинно тоді і тільки тоді, коли хоча б одне з висловлювань істинне і хибне – коли обидва висловлювання хибні.

Диз'юнкцію висловлювань називають також логічною сумою А+В.

Висловлювання « 4<5 або 4=5 » є істинним. Бо висловлювання 4<5 » - Істинне, а вислів « 4=5 » - хибне, то А Вє справжнім висловлюванням « 4 5 ».

4 . Операція імплікації.

Імплікацієювисловлювань Аі Уназивається висловлювання А В(«якщо А, то У», «з Аслід У»), значення якого помилкове тоді і тільки тоді, коли Аістинно, а Упомилково.

В імплікації А Ввисловлювання Аназивають основою,або посилкою, а висловлювання У – наслідком,або висновок.

13. Таблиці істинності висловлювань.

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

Таблиці істинності застосовуються для:

Обчислення істинності складних висловлювань;

встановлення еквівалентності висловлювань;

Визначення тавтологій.

Встановлення істинності складних висловлювань.

приклад 1.Встановити істинність висловлювання · З

Рішення.До складу складного висловлювання входять 3 простих висловлювання: А, У, З. У таблиці заповнюються колонки значеннями (0, 1). Вказуються всі можливі ситуації. Прості висловлювання від складних відокремлюються подвійною вертикальною межею.
При складанні таблиці треба стежити, щоб не переплутати порядок дій; заповнюючи стовпці, слід рухатися “зсередини назовні”, тобто. від елементарних формул до більш складних; стовпець, що заповнюється останнім, містить значення вихідної формули.

А	У	З		А+		· З

З таблиці видно, що це висловлювання істинно лише у разі, коли А=0, В=1, С=1. У решті випадків воно хибне.

14. Рівносильні формули.

Дві формули Аі Уназиваються рівносильними, якщо вони набувають однакових логічних значень при будь-якому наборі значень вхідних у формулу елементарних висловлювань.

Рівносильність позначається знаком «». Для перетворення формул у рівносильні важливу роль відіграють основні рівносильності, що виражають одні логічні операції через інші, рівносильності, що виражають основні закони логіки алгебри.

Для будь-яких формул А, У, Зсправедливі рівносильності.

I. Основні рівносильності

закон ідемпотентності

1-істина

0-брехня

Закон протиріччя

Закон виключеного третього

закон поглинання

формули розщеплення

закон склеювання

ІІ. Рівносильності, що виражають одні логічні операції через інші.

закон де Моргана

ІІІ. Рівносильності, що виражають основні закони логіки алгебри.

комутативний закон

асоціативний закон

дистрибутивний закон

15. Формули логіки висловлювань.

Види формул класичної логіки висловлювань– у логіці висловлювань розрізняють такі види формул:

1. Закони(тотожно-справжні формули) – формули, які за будь-яких інтерпретацій пропозиційних змінних набувають значення «істинно»;

2. Протиріччя(тотожно-хибні формули) – формули, які за будь-яких інтерпретацій пропозиційних змінних набувають значення «хибно»;

3. Здійсненні формули– такі, що набувають значення «істинно»хоча б при одному наборі значень істинності входять до їх складу змінних змінних.

Основні закони класичної логіки висловлювань:

1. Закон тотожності: ;

2. Закон протиріччя: ;

3. Закон виключеного третього: ;

4. Закони комутативності та: , ;

5. Закони дистрибутивності щодо ,і навпаки: , ;

6. Закон видалення істинного члена кон'юнкції: ;

7. Закон видалення хибного члена диз'юнкції: ;

8. Закон контрапозиції: ;

9. Закони взаємовиразності пропозиційних зв'язок: , , , , , .

Процедура розв'язання– метод, що дозволяє кожної формули встановити є вона законом, протиріччям чи здійсненної формулою. Найпоширенішою процедурою розв'язання є метод істиннісних таблиць. Однак він не єдиний. Ефективним методом розв'язності є метод нормальних формдля формул логіки висловлювань. Нормальною формоюФормули логіки висловлювань є форма, яка не містить знака імплікації «». Розрізняють кон'юнктивну та диз'юнктивну нормальні форми. Кон'юнктивна форма містить лише знаки кон'юнкції «». Якщо у формулі, наведеній до кон'юнктивної нормальної форми, зустрічається підформула виду, то вся формула в цьому випадку є протиріччям. Диз'юнктивна форма містить лише знаки диз'юнкції « ». Якщо у формулі, наведеній до диз'юнктивної нормальної форми, зустрічається підформула виду, то вся формула в цьому випадку є законом. У всіх інших випадках формула є здійсненною формулою.

16. Предикати та операції з них. Квантори.

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

Залежно від кількості змінних, які входять у пропозицію, розрізняють одномісні, двомісні, тримісні тощо. предикати, що позначаються відповідно: А( х), В( х, у), С( х, у, z).

Якщо заданий певний предикат, то з ним пов'язані дві множини:

1. Безліч (область) визначення Х, Що складається з усіх значень змінних, при підстановці яких предикат останній звертається у висловлювання. При заданні предикату зазвичай вказують область визначення.

2. Безліч істинності Т,що складається з усіх значень змінних, при підстановці яких у предикат виходить справжнє висловлювання.

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

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

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

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

Безліч істинності предикату є доповненням до множини істинності предикату А( х). Позначимо через Т А безліч істинності предикату А( х), а через Т - безліч істинності предикату. Тоді.

2. Кон'юнкцієюпредикатів А( х) і В( хх) В( х хХ, за яких обидва предикати звертаються до справжніх висловлювань.

Безліч істинності кон'юнкції предикатів є перетин множин істинності предикату А( х) В( х). Якщо позначити безліч істинності предикату А(х) через Т А, а безліч істинності предикату В(х) через Т і безліч істинності предикату А(х) В(х) через , то

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

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

4.Імплікацієюпредикатів А( х) і В( х), заданих на множині Х, називається предикат А( х) В( х), який закладений за тих і тих значеннях змінної, у яких перший предикат звертається у справжнє висловлювання, а другий – у хибне.

Безліч істинності імплікації предикатів є об'єднання безлічі істинності предикату ( х) з доповненням до безлічі істинності предикату А ( х), тобто.

5. Еквіваленцієюпредикатів А( х) і В( х), заданих на безлічі Х, називається предикат , який звертається у справжнє висловлювання за всіх тих і лише тих значеннях змінної, у яких обидва предикату звертаються або у справжні висловлювання, чи хибні висловлювання.

Безліч істинності еквіваленції предикатів є перетин безлічі істинності предикату з безліччю істинності предикату.

Кванторні операції над предикатами

Предикат можна перевести у висловлювання способом підстановки та способом «навішування квантора».

Про числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 можна сказати: а) всідані числа прості; б) деякіз цих чисел парні.

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

Якщо з пропозиції «а» прибрати слово «все», та якщо з пропозиції «б» - слово «деякі», отримаємо такі предикати: «дані числа прості», «дані числа непарні».

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

Розрізняють два основні види кванторів: квантор спільності та квантор існування.

Терміни «кожний», «будь-який», «кожен» носять назву – квантор загальності.Позначається.

Нехай А ( х) – певний предикат, заданий на множині Х. Під виразом А( х) розумітимемо вислів істинний, коли А( х) істинно для кожного елемента з множини Х, і хибне в іншому випадку.

У прикладі 1 для R 1область визначення: , множина значень - . Для R 2Область визначення: , безліч значень: .

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

У першому випадку вибирають дві взаємно перпендикулярні лінії як горизонтальну і вертикальну осі. На горизонтальній осі відкладають елементи множини Aта через кожну точку проводять вертикальну лінію. На вертикальній осі відкладають елементи множини Bчерез кожну точку проводять горизонтальну лінію. Точки перетину горизонтальних та вертикальних ліній зображують елементи прямого твору

18. Способи завдання бінарних відносин.

Будь-яке підмножина декартового твору A×B називається бінарним ставленням, визначеним на парі множин A і B (латиною «біс» позначає «двічі»). У загальному випадку за аналогією з бінарними можна розглядати і n-арні відносини як упорядковані послідовності елементів, взятих по одному з n множин.

Для позначення бінарного відношення застосовують знак R. Оскільки R- це підмножина множини A×B, можна записати R⊆A×. Якщо ж потрібно зазначити, що (a, b) ∈ R, тобто між елементами a ∈ A та b ∈ B існує відношення R, то пишуть aRb.

Способи завдання бінарних відносин:

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

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

На (рисунку 1.16) зображено координатну сітку для множин. Точкам перетину трьох вертикальних ліній із шістьма горизонтальними відповідають елементи множини A×B. Кружочками на сітці відзначені елементи відношення aRb, де a ∈ A та b ∈ B, R позначає відношення «ділить».

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

3. Спосіб завдання відносин за допомогою перерізів використовується рідше, тому розглядати його не будемо.

19. Рефлексивність бінарних відносин. приклад.

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

Властивість рефлексивності при заданих відносинах матрицею характеризується тим, що це діагональні елементи матриці дорівнюють 1; при заданих відносинах графом кожен елемент має петлю – дугу (х, х).

Якщо ця умова не виконана для жодного елемента множини, то відношення називається антирефлексивним.

Якщо антирефлексивне відношення задано матрицею, всі діагональні елементи є нульовими. За завдання такого відношення графом кожна вершина немає петлі - немає дуг виду (х, х).

Формально антирефлексивність відносини визначається як: .

Якщо умова рефлексивності виконано задля всіх елементів множини, кажуть, що ставлення нерефлексивно.

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

Встановлення істинності складних висловлювань.

приклад 1.Встановити істинність висловлювання · З

Рішення.До складу складного висловлювання входять 3 простих висловлювання: А, У, З. У таблиці заповнюються колонки значеннями (0, 1). Вказуються всі можливі ситуації. Прості висловлювання від складних відокремлюються подвійною вертикальною межею.
При складанні таблиці треба стежити, щоб не переплутати порядок дій; заповнюючи стовпці, слід рухатися “зсередини назовні”, тобто. від елементарних формул до більш складних; стовпець, що заповнюється останнім, містить значення вихідної формули.

А	У	З		А+		· З

З таблиці видно, що це висловлювання істинно лише у разі, коли А=0, В=1, С=1. У решті випадків воно хибне.

13. Рівносильні формули.

Дві формули Аі Уназиваються рівносильними, якщо вони набувають однакових логічних значень при будь-якому наборі значень вхідних у формулу елементарних висловлювань.

Рівносильність позначається знаком «». Для перетворення формул у рівносильні важливу роль відіграють основні рівносильності, що виражають одні логічні операції через інші, рівносильності, що виражають основні закони логіки алгебри.

Для будь-яких формул А, У, Зсправедливі рівносильності.

I. Основні рівносильності

закон ідемпотентності

1-істина

0-брехня

Закон протиріччя

Закон виключеного третього

закон поглинання

формули розщеплення

закон склеювання

ІІ. Рівносильності, що виражають одні логічні операції через інші.

закон де Моргана

ІІІ. Рівносильності, що виражають основні закони логіки алгебри.

комутативний закон

асоціативний закон

дистрибутивний закон

14. Формули логіки висловлювань.

Види формул класичної логіки висловлювань– у логіці висловлювань розрізняють такі види формул:

1. Закони(тотожно-справжні формули) – формули, які за будь-яких інтерпретацій пропозиційних змінних набувають значення «істинно»;

2. Протиріччя(тотожно-хибні формули) – формули, які за будь-яких інтерпретацій пропозиційних змінних набувають значення «хибно»;

3. Здійсненні формули– такі, що набувають значення «істинно»хоча б при одному наборі значень істинності входять до їх складу змінних змінних.

Основні закони класичної логіки висловлювань:

1. Закон тотожності: ;

2. Закон протиріччя: ;

3. Закон виключеного третього: ;

4. Закони комутативності та: , ;

5. Закони дистрибутивності щодо ,і навпаки: , ;

6. Закон видалення істинного члена кон'юнкції: ;

7. Закон видалення хибного члена диз'юнкції: ;

8. Закон контрапозиції: ;

9. Закони взаємовиразності пропозиційних зв'язок: , , , , , .

Процедура розв'язання– метод, що дозволяє кожної формули встановити є вона законом, протиріччям чи здійсненної формулою. Найпоширенішою процедурою розв'язання є метод істиннісних таблиць. Однак він не єдиний. Ефективним методом розв'язності є метод нормальних формдля формул логіки висловлювань. Нормальною формоюФормули логіки висловлювань є форма, яка не містить знака імплікації «». Розрізняють кон'юнктивну та диз'юнктивну нормальні форми. Кон'юнктивна форма містить лише знаки кон'юнкції «». Якщо у формулі, наведеній до кон'юнктивної нормальної форми, зустрічається підформула виду, то вся формула в цьому випадку є протиріччям. Диз'юнктивна форма містить лише знаки диз'юнкції « ». Якщо у формулі, наведеній до диз'юнктивної нормальної форми, зустрічається підформула виду, то вся формула в цьому випадку є законом. У всіх інших випадках формула є здійсненною формулою.

15. Предикати та операції з них. Квантори.

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

Залежно від кількості змінних, які входять у пропозицію, розрізняють одномісні, двомісні, тримісні тощо. предикати, що позначаються відповідно: А( х), В( х, у), С( х, у, z).

Якщо заданий певний предикат, то з ним пов'язані дві множини:

1. Безліч (область) визначення Х, Що складається з усіх значень змінних, при підстановці яких предикат останній звертається у висловлювання. При заданні предикату зазвичай вказують область визначення.

2. Безліч істинності Т,що складається з усіх значень змінних, при підстановці яких у предикат виходить справжнє висловлювання.

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

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

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

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

Безліч істинності предикату є доповненням до множини істинності предикату А( х). Позначимо через Т А безліч істинності предикату А( х), а через Т - безліч істинності предикату. Тоді.

2. Кон'юнкцієюпредикатів А( х) і В( хх) В( х хХ, за яких обидва предикати звертаються до справжніх висловлювань.

Безліч істинності кон'юнкції предикатів є перетин множин істинності предикату А( х) В( х). Якщо позначити безліч істинності предикату А(х) через Т А, а безліч істинності предикату В(х) через Т і безліч істинності предикату А(х) В(х) через , то

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

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

4.Імплікацієюпредикатів А( х) і В( х), заданих на множині Х, називається предикат А( х) В( х), який закладений за тих і тих значеннях змінної, у яких перший предикат звертається у справжнє висловлювання, а другий – у хибне.

Безліч істинності імплікації предикатів є об'єднання безлічі істинності предикату ( х) з доповненням до безлічі істинності предикату А ( х), тобто.

5. Еквіваленцієюпредикатів А( х) і В( х), заданих на безлічі Х, називається предикат , який звертається у справжнє висловлювання за всіх тих і лише тих значеннях змінної, у яких обидва предикату звертаються або у справжні висловлювання, чи хибні висловлювання.

Безліч істинності еквіваленції предикатів є перетин безлічі істинності предикату з безліччю істинності предикату.

Кванторні операції над предикатами

Предикат можна перевести у висловлювання способом підстановки та способом «навішування квантора».

Про числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 можна сказати: а) всідані числа прості; б) деякіз цих чисел парні.

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

Якщо з пропозиції «а» прибрати слово «все», та якщо з пропозиції «б» - слово «деякі», отримаємо такі предикати: «дані числа прості», «дані числа непарні».

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

Розрізняють два основні види кванторів: квантор спільності та квантор існування.

Терміни «кожний», «будь-який», «кожен» носять назву – квантор загальності.Позначається.

Нехай А ( х) – певний предикат, заданий на множині Х. Під виразом А( х) розумітимемо вислів істинний, коли А( х) істинно для кожного елемента з множини Х, і хибне в іншому випадку.

Істинність висловлювань із квантором спільності встановлюється шляхом доказу. Щоб переконатися в хибності таких висловлювань (спростувати їх), достатньо навести контрприклад.

16. Визначення бінарного відношення між множинами А та В.

Бінарним ставленням між множинами A та Bназивається підмножина R прямого твору. У тому випадку, коли можна просто говорити про ставлення Rна A.

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

Область визначення Rє безліч всіх елементів з Aтаких, що для деяких елементів маємо . Іншими словами область визначення Rє безліч усіх перших координат упорядкованих пар з R.

Безліч значеньвідносини Rє безліч всіх таких, що для деяких . Тобто безліч значень Rє безліч всіх других координат упорядкованих пар з R.

У прикладі 1 для R 1область визначення: , множина значень - . Для R 2Область визначення: , безліч значень: .

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

У першому випадку вибирають дві взаємно перпендикулярні лінії як горизонтальну і вертикальну осі. На горизонтальній осі відкладають елементи множини Aта через кожну точку проводять вертикальну лінію. На вертикальній осі відкладають елементи множини Bчерез кожну точку проводять горизонтальну лінію. Точки перетину горизонтальних та вертикальних ліній зображують елементи прямого твору

17. Способи завдання бінарних відносин.

Будь-яке підмножина декартового твору A×B називається бінарним ставленням, визначеним на парі множин A і B (латиною «біс» позначає «двічі»). У загальному випадку за аналогією з бінарними можна розглядати і n-арні відносини як упорядковані послідовності елементів, взятих по одному з n множин.

Для позначення бінарного відношення застосовують знак R. Оскільки R- це підмножина множини A×B, можна записати R⊆A×. Якщо ж потрібно зазначити, що (a, b) ∈ R, тобто між елементами a ∈ A та b ∈ B існує відношення R, то пишуть aRb.

Способи завдання бінарних відносин:

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

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

На (рисунку 1.16) зображено координатну сітку для множин. Точкам перетину трьох вертикальних ліній із шістьма горизонтальними відповідають елементи множини A×B. Кружочками на сітці відзначені елементи відношення aRb, де a ∈ A та b ∈ B, R позначає відношення «ділить».

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

3. Спосіб завдання відносин за допомогою перерізів використовується рідше, тому розглядати його не будемо.

18. Рефлексивність бінарних відносин. приклад.

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

Властивість рефлексивності при заданих відносинах матрицею характеризується тим, що це діагональні елементи матриці дорівнюють 1; при заданих відносинах графом кожен елемент має петлю – дугу (х, х).

Якщо ця умова не виконана для жодного елемента множини, то відношення називається антирефлексивним.

Якщо антирефлексивне відношення задано матрицею, всі діагональні елементи є нульовими. За завдання такого відношення графом кожна вершина немає петлі - немає дуг виду (х, х).

Формально антирефлексивність відносини визначається як: .

Якщо умова рефлексивності виконано задля всіх елементів множини, кажуть, що ставлення нерефлексивно.