| Пошукова робота
на тему:
Елементи логіки
1. Висловлення та формули
Одним з основних понять логіки є висловлення
– розповідне речення, про яке можна стверджувати, що воно є або істинним, або хибним.
Звичайно, в мові існують речення, про які не можна сказати, істинні вони чи хибні. Наприклад, речення "Це речення є хибним". Якщо припустити, що воно є істинним, то з нього випливає його хибність, а якщо воно є хибним, то маємо, що воно істинне. Отже, це речення не можна розглядати як висловлення. Насправді воно є варіантом відомого парадокса брехуна
: неможливо сказати, чи є істинною або хибною фраза брехуна "Я брешу".
Проте наявність таких парадоксальних речень не заважатиме нам далі, оскільки математичні знання формулюються саме висловленнями.
Хибність чи істинність висловлень може змінюватися, наприклад, у часі ("Зараз ніч"), у просторі ("Ми летимо над Африкою") тощо. Будемо дивитися на висловлення як на змінну, що може мати одне з двох значень – "хибність" або "істина", позначені 0 і 1 відповідно. Ці значення вважаються протилежними
одне до одного.
Означення.
Змінна з можливими значеннями "хибність" або "істина" називається пропозиційною
.
Будемо позначати пропозиційні змінні великими літерами A
, B
, C
, …, можливо, з індексами. Ці літери також називаються пропозиційними
.
З висловлень можна одержувати інші висловлення, пов'язуючи їх сполучниками "та", "або", "якщо …, то …" та іншими. Ці сполучники позначаються спеціальними знаками й називаються пропозиційними
зв'язками
. Означимо їх.
Означення.
Висловлення вигляду "Не A
" записується ØA
й називається запереченням
висловлення A
. Його значення є протилежним до значення A
.
Означення.
Висловлення вигляду "A
та B
" записується як A
&B
або A
ÙB
або A
×B
і називається кон'юнкцією
висловлень A
і B
, або їх логічним добутком
. Висловлення A
і B
називаються співмножниками
кон'юнкції. Вона істинна, коли кожний із співмножників істинний. Якщо ж хоча б один із них хибний, то й вона хибна. Її ще записують у вигляді .
Означення.
Висловлення вигляду "A
або B
" записується як A
ÚB
і називається диз'юнкцією
висловлень A
і B
, або логічною сумою
(доданків
диз'юнкції). Вона істинна, коли хоча б один із доданків істинний (можливо, і обидва). Якщо ж обидва доданки хибні, то й вона хибна. Її ще записують у вигляді .
Означення.
Висловлення вигляду "Якщо A
, то B
" записується як A
®B
і називається імплікацією
з засновком
A
і висновком
B
. Імплікація хибна, коли засновок істинний, а висновок хибний. В усіх інших випадках вона істинна. Наприклад, висловлення "Якщо 2*2=4, то Сонце обертається навколо Землі" за цим означенням є хибним, а висловлення "Якщо 2*2=5, то Сонце обертається навколо Землі" – істинним. Імплікацію часто позначають знаком "Þ": A
ÞB
.
Зауважимо, що запис A
®B
читається також, як "B
є необхідною умовою
для A
", або як "A
є достатньою
умовою
для B
", або як "З A
випливає B
", або як "A
тільки тоді
, коли B
", або як "B
тоді, коли
A
".
Імплікація "З не B
випливає не A
", що позначається (ØB
)®(ØA
), називається висловленням, протилежним
до висловлення A
®B
. Імплікація "З B
випливає A
", що позначається B
®A
, називається висловленням, оберненим
до висловлення A
®B
.
Означення.
Висловлення вигляду "A
тоді й тільки тоді, коли B
" записується як A
«B
і називається еквівалентністю висловлень
A
і B
. Вона істинна, коли значення висловлень A
і B
збігаються. Якщо ж вони різні, то еквівалентність хибна. Наприклад, висловлення "Якщо 2*2=5, то Сонце обертається навколо Землі" є істинним. Еквівалентність часто позначають не знаком "«", а знаком "Û".
Зауважимо, що запис A
«B
читається також як "B
є необхідною і достатньою умовою
для A
", а також як "Якщо A
, то B
, і якщо B
, то A
". Заперечення еквівалентності Ø(A
«B
) читається як "Або A
, або B
". Складений сполучник "або …, або …" інколи називається "виключне або
". Підкреслимо, що диз'юнкція A
ÚB
відрізняється від заперечення еквівалентності Ø(A
«B
).
Означення.
Висловлення записують у вигляді формул
за такими правилами:
1) пропозиційна літера є формулою;
2) якщо X
і Y
– формули, то (ØX
), (X
ÙY
), (X
ÚY
), (X
®Y
), (X
«Y
) також є формулами;
3) інших формул немає.
За цими правилами, наприклад, Ø(A
®B
), ((A
«B
)&(Ø(A
ÚB
))) є формулами, A
ÚB
ÙC
– ні. Далі ми розглянемо узгодження, які дозволяють скорочувати запис формул. Зокрема, ці узгодження дозволяють розглядати A
ÚB
ÙC
як формулу. Тут лише зауважимо, що можна не записувати зовнішні дужки формул, наприклад, писати X
®Y
.
2. Таблиці істинності формул і закони
Формула є словом
, тобто послідовністю символів – імен пропозиційних змінних, знаків зв'язок і дужок. Це слово має певну структуру, обмежену правилами побудови формул. Підслово цього слова, яке є формулою, називається підформулою
. Наприклад, у формулі ((A
«B
)&(Ø(A
ÚB
))) є підформули A
, B
, (A
«B
), (A
ÚB
), (Ø(A
ÚB
)).
Формула, що позначає висловлення, складене з інших, простіших, має значення, яке залежить від значень цих складових висловлень. Для його обчислення спочатку кожній пропозиційній змінній ставиться у відповідність одне зі значень "хибність" чи "істина" (0 чи 1). Далі за означеннями пропозиційних зв'язок обчислюється значення підформул, починаючи від найпростіших і закінчуючи всією формулою. Значення формул з однією двомісною зв'язкою при всіх можливих наборах значень змінних наведено в таблиці:
| A
B
|
A
Ù
B
|
A
Ú
B
|
A
®
B
|
A
«
B
|
| 0 0
|
0
|
0
|
1
|
1
|
| 0 1
|
0
|
1
|
1
|
0
|
| 1 0
|
0
|
1
|
0
|
0
|
| 1 1
|
1
|
1
|
1
|
1
|
Обчислимо значення формули, наприклад, (A
®B
)&(B
®A
) при всіх можливих наборах значень змінних A
і B
. Обчислення подамо такою таблицею:
| A
B
|
A
®
B
|
B
®
A
|
(
A
®
B
)
&(B
®
A
)
|
| 0 0
|
1
|
1
|
1
|
| 0 1
|
1
|
0
|
0
|
| 1 0
|
0
|
1
|
0
|
| 1 1
|
1
|
1
|
1
|
Таблиці, в яких представлено залежність значень формул від пропозиційних змінних, називаються таблицями істинності
.
Розглянемо узгодження, які дозволяють скорочувати запис формул. Пропозиційні зв'язки упорядковуються за "силою тяжіння до формул
" подібно до знаків арифметичних операцій. Всі розуміють, що вираз 1+2´3 позначає суму 1 і 2´3, а не добуток 1+2 і 3, тобто знак множення "притягується" сильніше за знак додавання. Зв'язка Ø вважається найсильнішою, тобто ØA
ÙB
є скороченням від (ØA
)ÙB
, а не від Ø(A
ÙB
). Далі за спаданням "сили тяжіння" двомісні зв'язки ідуть у такому порядку: &, Ú, ®, º. Отже, формулу A
ÚB
ÙC
можна розглядати, як скорочений запис формули A
Ú(B
ÙC
), а формулу A
ºB
®C
ÚA
– як A
º(B
®(C
ÚA
)).
Всі двомісні зв'язки мають властивість лівобічного зв'язування
. Це означає, що якщо праворуч і ліворуч від підформули записано без дужок знаки двомісних зв'язок, "сила тяжіння" яких однакова, то першою до підформули застосовується ліва з них. Наприклад, A
ÚB
ÚC
є скороченим записом формули (A
ÚB
)ÚC
.
Означення.
Дві формули називаються еквівалентними
, або рівносильними
, якщо приймають однакові значення при всіх можливих значеннях пропозиційних змінних. Рівносильність формул позначається знаком º і в логіці називається законом
.
Наприклад, неважко переконатися, що за довільних формул A
, B
, C
наступні рівносильності є законами (праворуч указано назви деяких з них):
(1) A
ÙB
º B
ÙA
, A
ÚB
º B
ÚA
– закони комутативності
(2) A
Ù(B
ÙC
) º (A
ÙB
)ÙC
, A
Ú(B
ÚC
) º (A
ÚB
)ÚC
– закони асоціативності
(3) A
Ù(B
ÚC
) º (A
ÙB
)Ú(A
ÙC
), A
Ú(B
ÙC
) º (A
ÚB
)Ù(A
ÚC
) – закони дистрибутивності кон'юнкції відносно диз'юнкції та диз'юнкції відносно кон'юнкції
(4) A
ÙA
º A
, A
ÚA
º A
– закони ідемпотентності
(5) A
Ú(A
ÙB
) º A
, A
Ù(A
ÚB
) º A
(6) Ø(A
ÚB
) º ØA
ÙØB
, Ø(A
ÙB
) º ØA
ÚØB
– закони Де Моргана
(7) ØØA
º A
– закон подвійного заперечення
(8) A
Ù0 º 0, A
Ù1 º A
, A
Ú0 º A
, A
Ú1 º 1 – закони поглинання
(9) A
ÚØA
º 1 – закон виключеного третього
(10) A
ÙØA
º 0 – закон суперечності
(11) A
®B
º ØB
®ØA
– закон контрапозиції
Корисно також пам'ятати ще два закони:
(12) A
®B
º ØA
ÚB
(13) A
«B
º (A
®B
)Ù(B
®A
).
На законах грунтуються так звані рівносильні
перетворення
формул, коли формула або її підформула заміняється на рівносильну їй. В результаті одержується формула, рівносильна початковій. Такі перетворення бувають потрібні для спрощення формул. Наприклад, формула A
Ú(ØA
®B
) має рівносильні формули A
Ú(ØØA
ÚB
), A
Ú(A
ÚB
), (A
ÚA
)ÚB
, A
ÚB
, що одержуються послідовним застосуванням законів (12), (7), (2), (4).
3. Нормальні форми висловлень
Розглянемо два різновиди формул, що мають певні структурні особливості. Саме структура цих формул зумовлює їх використання у таких важливих галузях застосування математичної логіки, як автоматизація доведення тверджень і логічне програмування.
Закони (2) стверджують асоціативність зв'язок кон'юнкції. Звідси формула вигляду ((…((A
1
ÙA
2
)ÙA
3
)Ù…)ÙAn
) має еквівалентний запис A
1
ÙA
2
ÙA
3
Ù…ÙAn
. Формула в такому записі називається кон'юнкцією
формул
A
1
, A
2
, A
3
, …, An
.
Означення.
Елементарною
кон'юнкцією
називається кон'юнкція формул, кожна з яких є або пропозиційною змінною, або запереченням такої. Наприклад, A
1
ÙØA
2
ÙA
3
.
Означення.
Диз'юнктивною нормальною формою
(скорочено ДНФ
) називається диз'юнкція елементарних кон'юнкцій. Наприклад, формула A
ÙB
ÚB
ÙC
ÚD
. Зауважимо, що її структуру краще видно в записі A
×B
ÚB
×C
ÚD
або в записі .
Будь-яка формула може бути перетворена до ДНФ. Ми не будемо доводити це твердження, а лише опишемо потрібні рівносильні перетворення. Застосуванням законів (13) і (12) можна позбутися зв'язок « і ®, тобто перетворити формулу до рівносильної, у якій є лише зв'язки Ø, Ú і Ù. Далі, якщо у формулі є заперечення диз'юнкцій чи кон'юнкцій, то вони "спускаються" до пропозиційних змінних застосуванням законів Де Моргана (6). Далі, якщо у формулі є множники-диз'юнкції, то їх можна позбутися застосуванням першого з законів дистрибутивності (3). В результаті всі множники у кон'юнкціях формули є елементарними, і вона являє собою ДНФ. Застосування законів (1), (2), (4), (5), (7)-(10) може скоротити цей процес.
Приклад. Розглянемо перетворення (A
®B
)«(C
®B
). Після знаків º у дужках указано номери законів, застосованих при черговому перетворенні:
(A
®B
)«(B
®C
) º(13, 12)
º(Ø(ØA
ÚB
)Ú(ØC
ÚB
))×(Ø(ØC
ÚB
)Ú(ØA
ÚB
)) º(6, 7, 2)
º (A
×ØB
ÚØC
ÚB
)×(ØB
×C
ÚØA
ÚB
) º(3)
º A
×ØB
×ØB
×C
ÚA
×ØB
×ØA
ÚA
×ØB
×B
ÚØC
×ØB
×C
ÚØC
×ØA
ÚØC
×B
Ú
ÚB
×ØB
×C
ÚB
×ØA
ÚB
×B
º(1, 4, 9, 8)
º A
×ØB
×C
ÚØA
×ØC
ÚB
×ØC
ÚB
×ØA
ÚB
º(5)
º A
×ØB
×C
ÚØA
×ØC
ÚB
За законами (2) зв'язки диз'юнкції також асоціативні, звідки формули ((…((A
1
ÚA
2
)Ú A
3
)Ú …)ÚAn
) і A
1
ÚA
2
ÚA
3
Ú…ÚAn
також є еквівалентними. Остання з них називається диз'юнкцією
формул
A
1
, A
2
, A
3
, …, An
.
Означення.
Елементарною
диз'юнкцією
називається диз'юнкція формул, кожна з яких є або пропозиційною змінною, або запереченням такої. Наприклад, A
1
ÚØA
2
ÚA
3
.
Означення.
Кон'юнктивною нормальною формою
(скорочено КНФ
) називається кон'юнкція елементарних диз'юнкцій. Наприклад, формула (A
ÚB
)Ù(ØB
ÚC
ÚØD
), яку можна подати також у вигляді .
Будь-яка формула перетворюється до рівносильної їй КНФ з використанням тих самих законів, тільки замість першого з законів дистрибутивності (3) вживається другий: A
Ú(B
ÙC
) º (A
ÚB
)Ù(A
ÚC
).
Приклад. Розглянемо перетворення формули (A
®B
)«(C
®B
) після одержання формули (A
×ØB
ÚØC
ÚB
)×(ØB
×C
ÚØA
ÚB
):
(A
×ØB
ÚØC
ÚB
)×(ØB
×C
ÚØA
ÚB
) º(3)
º (A
×ØB
ÚØC
)(A
×ØB
ÚB
)×(ØB
×C
ÚØA
)×(ØB
×C
ÚB
) º(3)
º (A
ÚØC
)×(ØB
ÚØC
)×(A
ÚB
)×(ØB
ÚB
)×(ØB
ÚØA
)×(C
ÚØA
)×
×(ØB
ÚB
)×(C
ÚB
) º(9)
º (A
ÚØC
)×(ØB
ÚØC
)×(A
ÚB
)×(ØB
ÚØA
)×(C
ÚØA
)×(C
ÚB
)
4. Тавтології, суперечності та логічні висновки
Означення.
Формула називається тотожньо істинною
, або тавтологією
, якщо має значення 1 при всіх можливих значеннях пропозиційних змінних.
Наприклад, A
ÚØA
чи (A
®B
)Ú(B
®A
). Неважко також переконатися, що заміною знаків º на зв'язку « у законах (1)-(13), наведених у п.1.1, одержуються саме тавтології.
Тавтології характерні тим, що коли всі входження тієї самої літери замінити на будь-яке, але одне й те саме висловлення, то нове висловлення буде істинним. Наприклад, підставимо у тавтологію ((A
ÚB
)ÙØB
)®A
замість літери A
висловлення "світить сонце", а замість літери B
– "світять зорі". Одержане висловлення "Якщо світить сонце або світять зорі, і не світять зорі, то світить сонце" є істинним. Підкреслимо, що сама по собі структура цього висловлення вже забезпечує його істинність.
Неважко переконатися, що якщо тавтологіями є деяка формула X
і формула X
®Y
, то Y
також є тавтологією.
Означення.
Формула називається тотожньо хибною
, або суперечністю
, якщо має значення 0 при всіх можливих значеннях пропозиційних змінних.
Одним із характерних прикладів суперечності є висловлення A
ÙØA
. Ця суперечність використовується у доведенні тверджень вигляду A
®B
методом "від супротивного
". Припускають істинність заперечення Ø(A
®B
), тобто істинність A
ÙØB
. З істинності ØB
виводять ØA
, одержуючи суперечність A
ÙØA
. Вона свідчить про хибність A
ÙØB
, тобто істинність A
®B
.
Зауважимо, що для доведення істинності A
®B
достатньо з ØB
вивести ØA
, тобто довести істинність протилежного твердження ØB
®ØA
. Адже за законом контрапозиції (11) A
®B
º ØB
®ØA
Очевидно, що заперечення будь-якої тавтології є суперечністю, і навпаки. На відміну від тавтологій, підстановка висловлень у суперечності породжує хибні висловлення.
Тепер розглянемо поняття логічного висновку
. У математиці, як і у звичайному житті, доводиться з'ясовувати, чи випливає деяке твердження з одного або кількох інших, тобто чи є це твердження їх логічним висновком
.
Приклад. Припустимо, що купівельна спроможність грошей падає, якщо зростають податки, і що люди незадоволені, коли падає купівельна спроможність грошей. Припустимо також, що податки зростають. Звідси можна дійти висновку, що люди незадоволені.
Для цього позначимо висловлення літерами:
A
– "податки зростають",
B
– "купівельна спроможність грошей падає",
C
– "люди незадоволені".
Припущення прикладу висловимо формулою:
(A
®B
)Ù(B
®C
)ÙA
.
Доведемо, за істинності такої умови істинним буде висловлення C
. Перетворимо (A
®B
)Ù(B
®C
)ÙA
до ДНФ:
(A
®B
)Ù(B
®C
)ÙA
º (ØA
ÚB
)Ù(ØB
ÚC
)ÙA
º A
Ù(ØA
ÚB
)Ù(ØB
ÚC
) º
º (A
ÙØA
)Ù(A
ÙB
)Ù(ØB
ÚC
) º (A
ÙB
)Ù(ØB
ÚC
) º
º (A
ÙB
ÙØB
)Ú(A
ÙB
ÙC
) º A
ÙB
ÙC
.
Отже, маємо, що істинною є формула A
ÙB
ÙC
. Але вона істинна лише тоді, коли кожний співмножник істинний. Звідси висловлення C
є істинним.
Таким чином, з істинності формул (A
®B
), (B
®C
) і A
випливає істинність C
. У такому випадку C
називається логічним висновком
цих формул.
Означення.
Формула Y
називається логічним висновком
формул X
1
, X
2
, …, Xn
, якщо з істинності X
1
ÙX
2
Ù…ÙXn
випливає істинність формули Y
. Формули X
1
, X
2
, …, Xn
називаються засновками
Y
.
Перевірити, чи є одна формула логічним висновком інших, можна за допомогою порівняння таблиць істинності цієї формули та кон'юнкції інших. Але можна діяти зовсім іншим способом на основі двох наступних тверджень.
Теорема 1
. Формула Y
є логічним висновком формул X
1
, X
2
, …, Xn
тоді й тільки тоді, коли формула (X
1
ÙX
2
Ù…ÙXn
)®Y
є тавтологією.
Доведення.
1 (Необхідність). Припустимо, що формула Y
є логічним висновком формул X
1
, X
2
, …, Xn
. Якщо за деяких значень літер у формулах X
1
, X
2
, …, Xn
хоча б одна з них хибна, то за означенням імплікації (X
1
ÙX
2
Ù…ÙXn
)®Y
істинна. Якщо ж за деяких значень літер у формулах X
1
, X
2
, …, Xn
всі вони істинні, X
1
ÙX
2
Ù…ÙXn
також істинна. Але формула Y
є логічним висновком формул X
1
, X
2
, …, Xn
, тому вона також істинна. Тоді істинна і формула (X
1
ÙX
2
Ù…ÙXn
)®Y
. Отже, за будь-яких значень літер (X
1
ÙX
2
Ù…ÙXn
)®Y
істинна, тобто є тавтологією.
2 (Достатність). Припустимо, що (X
1
ÙX
2
Ù…ÙXn
)®Y
є тавтологією. Тоді якщо за якихось значень літер у формулах X
1
, X
2
, …, Xn
всі вони істинні, то Y
також істинна, тобто є їх логічним висновком.
Теорема 2.
Формула Y
є логічним висновком формул X
1
, X
2
, …, Xn
тоді й тільки тоді, коли формула (X
1
ÙX
2
Ù…ÙXn
ÙØY
) є суперечністю.
Доведення.
За теоремою 1, формула Y
є логічним висновком формул X
1
, X
2
, …, Xn
тоді й тільки тоді, коли формула (X
1
ÙX
2
Ù…ÙXn
)®Y
є тавтологією. Звідси Y
є логічним висновком формул X
1
, X
2
, …, Xn
тоді й тільки тоді, коли заперечення Ø((X
1
ÙX
2
Ù…ÙXn
)®Y
)є суперечністю. Але
Ø((X
1
ÙX
2
Ù…ÙXn
)®Y
) º Ø(Ø(X
1
ÙX
2
Ù…ÙXn
)ÚY
) º
º Ø(Ø(X
1
ÙX
2
Ù…ÙXn
))ÙØY
º X
1
ÙX
2
Ù…ÙXn
ÙØY
.
Таким чином, твердження теореми істинне.
Розглянемо приклад застосування наведених теорем. Доведемо, що формула B
є логічним висновком формул A
®B
і A
. Перетворимо формулу (A
®B
)ÙA
ÙØB
:
(A
®B
)ÙA
ÙØB
º (ØA
ÚB
)ÙA
ÙØB
º (ØA
ÙA
ÙØB
)Ú(B
ÙA
ÙØB
) º 0Ú0 º 0.
Отже, формула (A
®B
)ÙA
ÙØB
суперечлива, і за теоремою 2 формула B
є логічним висновком формул A
®B
і A
.
Той факт, що формула B
є логічним висновком формул A
®B
і A
, відіграє в математиці дуже важливу роль. Він дозволяє з уже відомих істинних тверджень A
®B
і A
одержати нове істинне твердження B
. Зауважимо, що такий спосіб одержання, або виведення
нових тверджень у математичній логіці є одним із основних. Таке виведення задається спеціальним правилом виведення
, яке має вигляд і назву modus
ponens
(правило відокремлення
). Воно дозволяє одержати висновок B
твердження A
®B
як окреме висловлення, тобто відокремити його вид засновку A
. У математичній логіці існують і інші правила виведення, але тут ми їх не розглядаємо.
Підіб'ємо невеличкий неформальний підсумок. Ми познайомилися з двома принципово різними способами одержання нових висловлень. Перший полягає в тому, що ми будуємо складні висловлення з простіших за допомогою логічних зв'язок, а також "перебудовуємо" їх, виконуючи рівносильні перетворення на основі законів. Описані способи побудови та перетворення висловлень складають основу алгебри висловлень
.
Другий спосіб одержання нових істинних висловлень полягає в застосуванні згаданих правил виведення до вже відомих істинних висловлень. При цьому формулюється система висловлень-тавтологій, що складає основу для виведення інших. Вони називаються аксіомами
, а висловлення, що виводяться, – теоремами
. Прикладом аксіоми може служити висловлення AÚØA, яке називається законом виключеного третього. Такий спосіб породження висловлень називається численням висловлень
.
Підкреслимо ще раз, що в цьому розділі нашою метою є лише знайомство з основними поняттями і мовою позначень логіки, тому ми не торкаємося її суттєвих питань. Вони розкриваються у багатьох джерелах (див. список рекомендованої літератури).
5. Неформальне знайомство з кванторами
У математиці, як і у повсякденному житті, виникають твердження зі специфічною структурою. Ця структура робить можливими міркування, які не можна відтворити виведенням висловлень. Класичним прикладом таких міркувань є:
Кожна людина смертна.
Сократ – людина.
Звідси випливає, що Сократ смертний.
Очевидно, що висловлення "Сократ смертний" не є логічним висновком засновків "Кожна людина смертна" і "Сократ – людина". Проте коректність наведених міркувань ні в кого не викликає сумніву. Очевидно, що вона зумовлена якимсь особливим змістом слова "кожна".
Введемо додаткові позначення. Нехай x
позначає деяку змінну, значення якої можуть мати деяку властивість P
. Такі змінні називаються предметними
. Висловлення "x
має властивість P
" позначимо P
(x
). Наприклад, висловлення "Ціле число x
є парним" позначимо E
(x
). Значення такого висловлення залежить від значення цієї змінної. При x
=1 висловлення E
(x
) хибне, при x
=2 – істинне. Замість літери x
можна записати її значення, наприклад, E
(2).
Речення "Кожне значення x
має властивість P
", або "Всі значення x
мають властивість P
", або "Всі x
мають властивість P
", або "При всіх x
справджується властивість P
" позначимо записом "x
P
(x
). У цьому записі частина "x
називається квантором загальності
. Слово "квантор" походить від слова "квантифікація", що означає "кількісне вираження". Продовжуючи приклад про парні числа, зауважимо, що твердження "x
E
(x
) є хибним.
Речення "Існує значення x
, що має властивість P
", або "Деякі значення x
мають властивість P
", або "При деякому значенні x
справджується властивість P
", або "Деякі x
мають властивість P
" позначимо записом $x
P
(x
). У цьому записі частина $x
називається квантором існування
. Очевидно, що у прикладі про парні числа твердження $x
E
(x
) є істинним.
Очевидно, що
"x
P
(x
) ® $x
P
(x
),
причому твердження "x
P
(x
) і $x
P
(x
) нерівносильні.
Розглянемо деякі з можливих застосувань пропозиційних зв'язок до виразів із кванторами. Заперечення Ø("x
P
(x
)) читається як "неістинно, що всі значення x
мають властивість P
", тобто як "існує значення x
, що не має властивості P
". Таке речення можна позначити як $x
ØP
(x
). Таким чином,
Ø("x
P
(x
)) º $x
ØP
(x
).
Аналогічно
Ø($x
ØP
(x
)) º "x
ØP
(x
).
Висловлення "x
P
(x
) Ù "x
Q
(x
) читається як "всі значення x
мають властивість P
і всі значення x
мають властивість Q
", тобто "всі значення x
мають властивість P
і властивість Q
". Таким чином,
("x
P
(x
))Ù("x
Q
(x
)) º "x
(P
(x
)ÙQ
(x
)).
Висловлення "x
P
(x
) Ú "x
Q
(x
) читається як "усі значення x
мають властивість P
або всі значення x
мають властивість Q
". З цього речення випливає, що "усі значення x
мають властивість P
або властивість Q
", але ці два речення не рівносильні. Таким чином, "x
(P
(x
)ÚQ
(x
)) є логічним висновком висловлення ("x
P
(x
))Ú("x
Q
(x
)), тобто
(("x
P
(x
))Ú("x
Q
(x
))) ® "x
(P
(x
)ÚQ
(x
)),
але вони нерівносильні.
Приклад. Якщо P
(x
) позначає речення "x
– парне число", а Q
(x
) – "x
– непарне число", то висловлення "x
(P
(x
)ÚQ
(x
)) є істинним, а ("x
P
(x
))Ú("x
Q
(x
)) – хибним.
Насамкінець, розглянемо речення з двома й більше кванторами. Вони з'являються, коли йдеться про властивості пар, трійок тощо змінних. Наприклад, речення "При будь-якому натуральному значенні x
існує значення y
, таке, що x
є дільником y
" можна записати як
"x
($y
D
(x
, y
)),
де D
(x
, y
) позначає речення "x
є дільником y
".
Речення вигляду "При будь-якому значенні x
справджується, що при будь-якому значенні y
істинно A
(x
, y
)" можна позначити так:
"x
("y
A
(x
, y
)).
Будемо опускати дужки, записуючи, наприклад, "x
$y
D
(x
, y
) або "x
"y
A
(x
, y
). Останній вираз можна прочитати також, як "При будь-якому значенні x
і при будь-якому значенні y
істинно A
(x
, y
)".
Аналогічно речення вигляду " При будь-якому значенні x
і при будь-якому значенні y
і при будь-якому значенні z
істинно A
(x
, y
, z
)" можна позначити виразом
"x
"y
"z
A
(x
, y
, z
).
І так далі. Розглянемо, наприклад, твердження великої теореми Ферма:
Рівняння
zn
=
xn
+
yn
, де
n
– ціле число, більше 2, не має розв'язків у цілих додатних числах
.
Одним із можливих записів цього твердження є такий:
"x
"y
"z
"n
((n
>2) ® (zn
¹xn
+yn
)).
|